The hash function

Daily heard of MD5 algorithm, SHA1 algorithm are hash function model.

This article will not explain the implementation principle of hash functions, because there are at least hundreds of popular hash functions on the market at present, each of which has a different principle, but the characteristics they want to maintain are the same.

1. The nature of the

Classical Hash model: out = f (in)

  • Property 1: The input field of in is infinite. For example, a string of any length can be passed in. However, in some projects, input fields are also scoped.

  • Property 2: The output field of out is relatively limited. For example, the output field of MD5 algorithm is [0, (2^64) -1]. The output field of SHA1 algorithm is [0, (2^128) -1]; The output field of the Hash algorithm specified in Java is [0, (2^32) -1]. You can think of the output field as large, but it must be infinite.

    The reason why the Hash function needs to have the above two properties is that there are many similar problems in practical engineering. For example, we need a function that can process whatever information is passed to the function to get a hexadecimal number. So if we use the MD5 algorithm, we end up with a hexadecimal number of length 16; If we use SHA1, we end up with a hexadecimal number of length 32.

  • Property 3: Input same in, output same out (same in — > same out). For example, if you pass “ABC” to a Hash function multiple times, the Hash function returns the same value. Indicates that there is no random component in the Hash function.

  • Property 4: Because the input field of IN is infinite, and the output field of out is finite, there must be different in, and the output of the same out (dif in — > same out). This is called a Hash collision, and the probability of a Hash collision is extremely low, but it exists.

  • Property 5: No matter how many in Hash functions are passed in, the final output out is uniformly discrete in the output field. Thus the uniformity and discreteness are guaranteed.

    Uniformity: Set up a number of equal size true subsets of out output fields. Using these true subsets to map to the output fields, it will be found that the number of Out in each true subset is the same.

    Discreteness: In corresponds to out without regularity in the output field. Even if in is very similar, out is not similar.

    If discreteness does not exist, then the concentration of a region in the output field can be made by input similar in, so that uniformity does not exist. So uniformity and discreteness exist at the same time and complement each other.

    The more discrete and uniform a Hash function is, the better it will be.

2. The promotion

Hash functions have the following generalizations:

Suppose the input samples are IN1, IN2, in3… Hash function to get out1, out2, out3… (assuming no collisions), then we add an operation to touch %m for each out, resulting in m1, m2, m3… . Due to property 5, we know that out is uniformly discrete in the output field, so after %m, we can guarantee that M is uniformly distributed in the range [0, m-1].

According to the generalization, we can solve some typical engineering problems.

Suppose you have a large file that contains 4 billion unsigned integers, each of which has a range of [0, (2^32) -1], which in base 10 is more than [04.2 billion]. If you only have 1 gigabyte of memory, how do you get the most frequent number in your file?

Analysis:

The classic way to solve this problem, if you’re using Java, is to use HashMap in Java. Key is an Integer that represents the number in the file. Value is an Integer that indicates the number of occurrences of the number. We then iterate through the file, and at the end of the loop, the Key corresponding to the largest Value in the HashMap is the number that occurs most often.

However, the problem only gives you 1 gigabyte of memory, so is it enough to use HashMap?

It is known that a record in a HashMap has two Spaces, including the space of the Key and the space of the Value. Both keys and values are int types and have four bytes. Therefore, a record in a HashMap needs at least eight bytes. In addition, the HashMap requires some space to store the index internally, and we assume that the index doesn’t take up space. Four billion numbers, worst-case four billion different numbers, so that’s four billion records stored in the HashMap. Each record is eight bytes long, and four billion records require 32 billion bytes, or 32 GIGABytes of memory. Therefore, you cannot use the HashMap provided in Java to do this.

We find that the space occupied by HashMap is only related to the type of Key. In this case, it is related to the type of number in the file. Multiple occurrences of the same type of number will not increase the space occupied by HashMap. So in this case, we’re not afraid of one number appearing many times, we’re afraid of many different numbers.

Solution:

Pass all the numbers in the file to the Hash function to compute 4 billion out, which is %100, to get a number in the range of 0, 99. Create file 0 99 and store out after %100 in the corresponding file. Assuming that there are 4 billion different numbers in the worst-case scenario, we can also guarantee that each file in numbers 0 to 99 will store about the same number and type distribution of numbers.

Each number one file is then processed separately using HashMap. If 4 billion records are placed in one file using HashMap processing requires 32GB of memory, and 4 billion records are evenly distributed across a hundred files, using HashMap processing on one of those files requires only 320M of memory. We do file one file one file so that we don’t get full memory. Every number one file will have a number that appears most frequently after the HashMap processing, and the same number must only appear in the same number of files. So after all the files are processed, you get 100 of the most common numbers, and 100 of them are different. And the answer is to find the number that occurs the most often.

Hash table

In the daily brushing process, only the use of hash table is involved, and I know that the performance of adding, deleting, modifying and checking hash table is O(1).

This paper only describes the most classical structure of hash table principle, optimization will not be deeply studied.

1. Classic structure

Hash tables are implemented based on Hash functions.

If the initial region size is set to 17, there will be regions 0 to 16.

The most commonly used hash tables in Java are HashMap and HashSet. They have the same structure and principle, but the difference is that HashMap has an accompanying Value while HashSet does not. This article uses HashMap as an example to explain the structure.

If you want to store Key=” ABC “and Value=1 into a hash table, the hash table will first evaluate the Key using the hash function to get out, and then out and %17 will get a number between 0 and 16, assuming 1. The hash table is then iterated over region 1. If region 1 is empty, a one-way linked list is created after region 1, joining Key=” ABC “, Value=1 as a node in the single necklace list. Add a few pairs of key-values and do the same, and you end up with a classic hash table.

Because of the nature of the Hash function, we know that the single necklace list joined by each region of the Hash table is basically uniformly lengthened.

If we want to find the corresponding Value by Key, we can go through the process of storing key-value again. If the current Key=” ABC “, then the hash table uses the hash function to calculate the Key to get out, then out and %17 to get 1, and then iterates through the one-way list of region 1 to find the corresponding node and get Value=1.

Expansion and 2.

If you add a large number of key-values to the hash table above, assuming N key-value pairs, then the average length of the hash table traversal is N/17. If the hash table capacity is always 17, then the performance of the hash table operation is far from O(1).

Therefore, we need to count the length of each one-way linked list in the hash table. Once the length of a one-way linked list exceeds a threshold value, the expansion mechanism of the hash table will be triggered.

Assuming that each expansion is doubled, the area capacity becomes 34 when the expansion mechanism is triggered. All the nodes in the original one-way linked list need to be recalculated, modulated, and remounted into the new hash table. All nodes were evenly divided by 17 regions, now they are evenly divided by 34 regions, so we can halve the length of all one-way lists in the original hash table.

After expansion, suppose we need to perform query operations in the hash table, the time complexity of hash function for Key calculation is O(1), the time complexity of modulus extraction is O(1), and the time complexity of traversing the unidirectional linked list is O(K) (assuming that there are K nodes in the chain, if the unidirectional linked list can not be too long, So the time complexity of adding, deleting, modifying and checking in a one-way list is O(1)).

The calculation of capacity expansion complexity is complicated. Assuming that N pairs of key-values are added and the capacity is doubled as long as the length of the unidirectional linked list exceeds 2, the capacity expansion will take logN times at most. If the single-necklace table capacity expansion threshold is greater than 2, then the number of capacity expansion is less than logN, but the complexity is O(logN) level, but the constant terms are different. After each expansion, N nodes need to recalculate the hash value, re-take the modulus, and re-mount to the heart of the hash table, the overall time complexity is O(N). Therefore, when the capacity is expanded to accommodate N key-value pairs for several times, the total cost for capacity expansion is O(NlogN), and the cost for a single capacity expansion is O(NlogN/N). So you can think of the average cost of a single add, delete, change in a hash table as O(logN).

Although the time complexity of hash function calculation is O(1), in fact the constant is relatively large, but the index is O(1).

Why is it O(1) when we use hash tables?

Because we can set the threshold of expansion of one-way linked list to be very long, let’s say 10, the speed of traversing 10 nodes is still very fast, but the cost of expansion can be greatly reduced. So order logN becomes a very small constant, so to speak, close to order one.

3. Offline capacity expansion

This technology is not available in just-in-time memory requisitions languages such as C++, but can be implemented in Java and some virtual machine hosting languages.

This technology can further accelerate the capacity expansion described above.

Suppose the user is using hash table A. The one-way linked list in hash table A is already very long. Although the operation time complexity can still reach O(1), the constant is relatively large. So the user wants to expand hash table A.

Because the hash table A is hosted by the JVM, it remains in memory even if the user does not use it. Then we can expand hash table A to generate hash table B elsewhere in memory, without preventing users from using hash table A during expansion. After the capacity expansion is successful, the pointer of hash table A points to hash table B and hash table A is destroyed. This further reduces the expansion cost of the hash table.

So that’s why you can say that the time complexity of a hash table is order 1 at the use level, but not in theory, so in theory it’s order logN.

4. Different languages

The exact implementation of a hash table varies from language to language, because different languages may use other data structures to optimize the table again.

Java changed the single-linked hash table into a red-black tree, but C++ kept the classic hash table structure.

RandomPool structure

Topic:

Design a structure that has the following three functions:

  1. Insert (key) : adds a key to the structure without adding it again.
  2. Delete (key) : Removes a key from the structure.
  3. GetRandom () : randomly returns any Key in the structure with equal probability.

The requirement is that the time complexity of the above three methods is O(1).

Analysis:

This problem is a data structure design using hash surface, will not use the principle of hash table.

Ontology uses two hash tables to assist each other to achieve RandomPool structure, one of the hash table is stored in the key – index, another hash table is stored in the index – key. Index is used to associate data between two tables, and two-way data search can be completed.

The INSERT and getRandom operations are nothing special; the key is the DELETE operation. If a Key and its corresponding Index in the structure are deleted directly, Index discontinuity will be caused, resulting in vulnerability. In this way, at Random, multiple Random generated indexes will occur, but the Index currently stored in the hash table cannot be hit. Therefore, when deleting, we will overwrite the last hash Key, reuse the Index of the target Key, and then physically delete the last hash Key. This logically removes the target Key without causing Index vulnerabilities.

Code:

public class RandomPool {

    private int size;

    private final HashMap<K, Integer> keyIndexMap;

    private final HashMap<Integer, K> indexKeyMap;

    public RandomPool(a) {
        size = 0;
        keyIndexMap = new HashMap<K, Integer>();
        indexKeyMap = new HashMap<Integer, K>();
    }

    // insert(key) : adds a key to the structure without adding it again.
    public void insert(K key) {
        // If the Key does not exist, perform insert
        if (!keyIndexMap.containsKey(key)) {
            keyIndexMap.put(key, size);
            indexKeyMap.put(size ++, key);
        }
    }

    // delete(key) : removes a key from the structure.
    public void delete(String key) {
        // If the Key exists, perform delete
        if (keyIndexMap.containsKey(key)) {
            // The last Key in keyIndexMap overwrites the target Key
            keyIndexMap.put(indexKeyMap.get(size), keyIndexMap.get(key));

            // The last Key in indexKeyMap overwrites the target Key
            indexKeyMap.put(keyIndexMap.get(key), indexKeyMap.get(size));

            Delete the target Key from keyIndexMap
            keyIndexMap.remove(key);

            // Delete the last Key in indexKeyMapindexKeyMap.remove(size); size --; }}// getRandom() : randomly returns any Key in the structure with equal probability.
    public K getRandom(a) {
        if (size == 0) {
            return null;
        }

        int randomIndex = (int) (Math.random() * size);

        returnindexKeyMap.get(randomIndex); }}Copy the code

Bloom filter

1. The introduction of

Bloom filter is mainly used to solve “blacklist system” or “crawler reloading problem” and so on.

Let’s take the blacklisting system as an example. For example, there are 10 million large files made up of urls. These urls are blacklisted, and each URL has a maximum size of 64 bytes, and the company doesn’t want users to be able to access them while using our browser service.

Therefore, we need to build a blacklist system that uses a data structure to organize all urls in a large file and make it quick to query. When a user enters a URL to visit, we can quickly determine whether the URL is in the blacklist by querying the data structure. The data structure does not need to delete a blacklist, but only needs to add a URL to the blacklist and query whether a URL is in the blacklist.

The classic solution is to build a HashSet and store all 10 million urls into the HashSet, which will take up 640 million bytes of memory, or about 5GB. The space overhead of memory will be very large.

If the system is implemented using a Bloom filter, the memory overhead will be greatly reduced, but there will be a certain probability of errors.

Bloom filters are designed to replace collections that store large amounts of data in memory, and only need to add and look up, not delete. Bloom filters take up a small amount of memory, but there is a certain probability that errors occur, and they are inevitable.

There are two kinds of mistakes:

  1. The URL in the blacklist is whitelisted.

  2. The URL that is not in the blacklist is judged to be blacklisted.

Bloom filters do not have the first type of error, only the second type of error is possible. But bloom filters can be artificially designed so that the trigger rate for the second type of error is as low as one in 10,000.

Bloom filter in the project is completely able to be received, even if it is extremely sensitive blacklist, the requirement can not misjudge any blacklist, bloom filter can do “even if the wrong kill 100, also don’t let go of a”, let alone the probability of wrong kill is very low.

2. The bitmap

Before going into detail about the implementation of a Bloom filter, you need to understand bitmaps.

Bitmap, also called Bit Array or Bit Map.

We are all familiar with arrays in Java. We have an array of type int[]. If the initial size is 100, then int[] has 0 to 99 units of space, each of which is 4 bytes. Conceptually, a bitmap is an array of type bit bit[], the same as int[], except that each bit[] occupies only 1bit.

We know that in Java, memory is measured in bytes and bitmap footprint is measured in bits. How do we implement a bitmap in Java?

Using an array of base types to piece together means that you can use the base type to hold the entire bit information, and then operate on each bit through bit operations.

An int of size 10 can represent a bit of size 320.

int[] arr = new int[10]
Copy the code

Arr [0], ARR [1], ARR [2]… Arr [0] represents 0 to 31 bits, and arr[1] represents 32 to 63 bits… And so on.

Now we need to get the 178th bit. If 1 returns the integer 1, and if 0 returns the integer 0, how do we get the 178th bit?

// locate the 178 bit space in int[]
int numIndex = 178 / 32;

// Locate which bit in the cell space
int bitIndex = 178 % 32;

// Get the state on the bit
int status = (arr[numIndex] >> bitIndex) & 1;
Copy the code

If we want to modify the information in bit 178, how?

// Change the 178bit to 1 and save
arr[numIndex] = (1 << bitIndex) | arr[numIndex];
// Change the 178bit to 0 and save
arr[numIndex] = (~(1 << bitIndex)) & arr[numIndex];
Copy the code

3. Design idea

A Bloom filter is a large bitmap with a capacity of m bits [] that actually occupies M /8 bytes.

Add the first blacklist URL1 to the Bloon filter, then URL1 will be calculated by the hash function 1 out1, then out1%m, can calculate a number 0~(m-1), so that can be corresponding to a cell space in bit[], set the bit 1; Then URL1 is calculated by the hash function 2 out2, and then out2%m, and can be corresponding to a cell space in bit[], set the bit 1… Similarly, assuming that there are K hash functions, URL1 will call K hash functions in turn to obtain K out. After modulating M, URL1 will correspond to K cell space in bit[] and set K bit to 1 (there may be overlapping cell space, overlapping bit remains 1, or K cell space may be different independently). When all K hash functions are called, URL1 is stored in the Bloom filter.

URL2, URL3… Url10 million And so on, each URL needs to call K hash functions to get K out, which corresponds to K unit space in bit[] after modulating M, and sets K bit to 1.

Now there is a URL that needs to find whether the URL is blacklist in the Bloom filter, so the URL needs to call K hash functions to get K out, after the touch of m corresponding to the K unit space in bit[], if all bits are 1, then the URL is blacklist; If one bit is not 1, the URL is whitelisted.

There are two parameters that are indeterminate:

  1. How many of K hash functions do I have?
  2. Bitmap capacity m exactly open how big?

Why isn’t there a “blacklist misperceives whitelist” error in the Bloom filter in this case?

The mechanism determines that if the URL is blacklisted, then during the search, we can ensure that the corresponding bit of the URL must be 1.

Why is there a “whitelist misperceives as a blacklist” error in the Bloom filter in this question?

If the capacity m is set very small and the number of urls is very large, then each bit will inevitably overlap a lot. Finally, each bit will be 1, and misjudgment will inevitably occur.

What decision error rate?

The most important factor is the bitmap capacity m, if M is large, then the error rate can be small; If M is small, the error rate goes up, possibly as high as 100%.

What is the status of K, the number of hash functions?

K is actually determined jointly by bitmap capacity M and sample size. Intuitively, this mechanism is actually collecting fingerprints. K hash functions are equivalent to collecting K feature points on a fingerprint sample. If there is only one hash function, it is equivalent to collecting only one feature point, and the error rate is uncontrollable very low. If you have three hash functions, the error rate is lower than if you only have one hash function. However, the number of feature points should not be very large. If 100 feature points need to be collected for each fingerprint, even if M is set reasonably, there is a considerable probability that each bit will be set to 1 after processing a large number of samples.

What is the process of determining M and K?

Firstly, bitmap capacity M is determined according to sample size N and error rate P, and then a most appropriate number of hash functions K is calculated according to sample size n, error rate P and bitmap capacity M.

When the sample size n is determined, the error rate P decreases gradually with the increase of bitmap capacity M, but the decline rate will be slower and slower. According to the expected error rate, a more suitable bitmap capacity m = V can be selected.

In the case that both sample size N and bitmap capacity M are determined, the error rate P gradually decreases with the increase of the number of hash functions K, but when K is very large, M will also be gradually filled up, and the error rate P will gradually increase and finally approach 1. Therefore, we can find the critical point where the error rate P decreases and rises, and the k value corresponding to this point is the most appropriate number of hash functions.

4. Implementation

Criteria for determining whether a system needs to be designed with a Bloom filter:

  • Identify the model of a system that is similar to the blacklist service and does not delete the service.

  • The system allows for a certain amount of error and has a clear expected error rate.

The size of a single sample has nothing to do with the design of the Bloom filter and does not determine any of the details of the bloom filter design, such as the “maximum 64 bytes per URL” in the example above. As long as I set up my hash function to accept a 64-byte URL as an argument and be able to evaluate it.

Only three formulas are needed to design a Bloom filter:

Formula 1 and Formula 2 calculate the theoretical bitmap capacity M and the number of theoretical hash functions K, which will be adjusted accordingly in actual production.

For example, the capacity m=26G calculated by the theoretical bitmap may actually be allocated 32G to M ‘, so that the actual error rate P ‘will be further reduced than the theoretical error rate P.

To calculate the actual error rate P ‘, formula 1 and Formula 2 should be used to calculate M and K, and then formula 3 should be used:

Consistency hashing

1. The introduction of

Consistency hashing is used to discuss problems such as how to organize multiple data servers.

Data servers usually refer to database servers such as MySQL and Oracle.

With a classic Web architecture, there is usually only one data server and no data organization issues. If you have a distributed architecture, then you have multiple data servers. What data does each server store? This involves the problem of how to organize data from multiple data servers.

The classical organization method is:

There are three data servers, no. 0, No. 1 and No. 2, each of which maintains its own proprietary data.

If you now need to store {“name”: “John”, “pass”: “123”}, then the application server will first put the Key (unique identifier) “John” of the data into the hash function to calculate out, and then out%3 will get a number of 0~2, and then store the data server in the cluster.

If you now want to query pass with name = “John”, the application server will also put “John” into the hash function to calculate mode 3 and finally determine which data server in the cluster the data item belongs to, thus extracting “123” from it.

This classical data server organization of data has been able to achieve a good data in each data server evenly distributed, load balancing.

What Key in the data entry is used for this exclusive partitioning of data?

Select a very diverse field from the entry that will not repeat itself as the Key. Such as ID, user name and so on. This will make it easier for hash functions to evenly divide.

A fatal problem with this classical organization approach is that the cost of data migration for both the addition of data servers and the reduction of data servers is total.

If at a certain moment is a large amount of data, the data server is not enough, I want to expand the number of data server, so the cost of data migration will be very big, we need to pick up the original all the data in the data server, and then the hash calculation modulus, restore the uniform data storage to add new data to the server in the cluster.

So we need to think about how to achieve uniform storage of data without “mode”, so that the cost of data migration is not so high?

Consistency hashing.

Principle 2.

There is no “module” operation in consistent hashing, so how to achieve uniform storage of data?

Assuming that the MD5 algorithm is used as the hash function, the calculated hash value range is [0, (2^64) -1]. We abstract the entire hash value range [0, (2^64) -1] into a closed loop.

Assume that there are three data servers: data server 0, data server 1, and data server 2.

The machine information (IP, Host name, MAC address) of each data server is certainly different, and as long as one machine information can be selected to distinguish each data server, that machine information can be used as an argument to the incoming hash function of each data server. For example, if MAC address is used as machine information to distinguish servers, then the hash function will calculate the MAC address of each data server and finally get different Out corresponding to the closed loop.

If you now need to store {“name”: “John”, “pass”: “123”}, then the application server will first put the Key (unique identifier) “John” into the hash function to calculate out, out must correspond to a location in [0, (2^64) -1], Then, the data is stored on the nearest data server in the clockwise direction.

So how is this mechanism implemented?

Each application server maintains an ordered array of hashes calculated by all data servers using MD5(MAC), and each application server also needs to record which data server each hash value corresponds to. The order of the above examples is [(0-1 billion), (1-500 billion), (2-7 trillion)].

If you now want to query for pass by name = “John”, then on the application server that received the request, first put “John” into the hash function to get 450 billion, and then take the 450 billion and do a binary lookup in that sort. The nearest hash in the order greater than 450 billion has a value of 500 billion, so the application server will go to the number 1 data server with a value of 500 billion to retrieve the data item.

If there is a data server whose hash value is exactly 450 billion, the application server goes directly to the data server to retrieve the data entry, without having to go clockwise to the data server.

If the hash function does not find a hash value greater than or equal to that value in the sorting, then it is the data server corresponding to the smallest hash value in the ordered ordering (because it is a closed loop).

What are the benefits of this mechanism?

As shown in the hash ring in the figure below, when no new data server is added, data server 0 stores the data whose hash value falls in area C, data server 1 stores the data whose hash value falls in area A, and data server 2 stores the data whose hash value falls in area B. When a new data server 3 is added to the cluster, only data server 0 is required to migrate data in area C to data server 3, which greatly reduces the cost of data migration when data servers are added/reduced.

However, there are two potential problems:

  • With a small number of data servers, uniform storage of data may not be possible at first. (Because the characteristic of the hash function is that when there is a lot of data, there is an equal amount of data in each segment, not that when there is only three data, three data must fall in three segments.)
  • Even if it is possible to split the hash rings evenly with a small number of data servers, adding/removing one data server immediately causes an imbalance in the load. (For example, three data servers each account for 1/3 of the hash ring. When a new data server is added, two of them still account for 1/3, but the other two account for 1/6 respectively.)

If you solve these two problems, consistent hashing is very useful.

These two potential problems can be solved using one technology, virtual node technology.

Virtual Node technology

1. The introduction of

Suppose that, based on the above example, 1000 virtual nodes (A1, A2… , a1000), also allocate 1000 virtual nodes to data server 1 (B1, B2… , B1000), also allocate 1000 virtual nodes (C1, C2… , c1000).

Instead of data servers 0, 1, and 2 competing for the hash ring, virtual nodes under those data servers are competing for the ring. A representative string is stored in each virtual node, and by passing the string into the hash function, the computed hash value falls on the corresponding position of the hash ring.

Data migration between virtual nodes can be achieved by writing a simple underlying logic. For example, if data from A10 is migrated to B500, A10 searches for data from data server 0 through the routing table and transmits the data to data server 1 corresponding to the VIRTUAL node B500.

Currently, the entire hash ring is contested by 3000 virtual nodes. Among them, 1000 drop points in the hash ring belong to data server 0, 1000 drop points belong to data server 1, 1000 drop points belong to data server 2. Because of the properties of the hash function, the 3000 points are evenly distributed across each segment. Therefore, the number of virtual nodes of A, B, and C is the same. Basically, 1/3 of virtual nodes belong to data server 0, 1/3 to data server 1, and 1/3 to data server 2.

By scrambling for data proportionally, the problem of uneven initial data storage and data storage caused by adding/reducing data servers can be solved.

When a data server is added, another 1000 virtual nodes are created for that data server, and another 1000 drop points are punched into the hash ring. In this case, each data server in the hash ring occupies 1/4 of the drop point, and the new data server must take the same amount of data from the 0, 1 and 2 data servers into itself.

When one data server is reduced, the data server allocates the same amount of its data to the other three data servers, and the data of the other three data servers is also balanced.

2. Manage the load

If the data is scrambled proportionally, consistency hashing has the added benefit of being able to manage the load based on the condition of the actual machine.

For example, in the example above, the performance of data server 0 is better than the performance of data server 1 and data server 2. So we can allocate 2000 virtual nodes to data server 0, 500 virtual nodes to data server 1 and 500 virtual nodes to data server 2.

Today, companies are building distributed databases based on this principle, known as “one of Google’s world-changing technology troika” (GFS, MapReduce, and BigTable).