Consistent hash, virtual node, bloom filter

 

Let's say the picture above A,B,C It's three servers , Now there is 6 Ten thousand pictures , In order to distribute evenly on each server , We store ：

Extract picture keywords % Number of servers （3）

Remainder is 0 It's stored in A The server , Remainder is 1 It's stored in B The server , Remainder is 2 Put it in C The server

Suppose we add another server now D, Then it will happen ：

6%3=0,6%4=2, Originally A Photos of the server , Turned into C The server .

Because the server has changed , The data in the server is affected （ All data ）

So we think of the three servers as a ring ：

  This is a circle , We think there are countless points on this circle , Now suppose that there exists on this circle 2^32 A little bit , Each point has a number , from 0 To 2^32, arc AB On the server B, arc BC On the server C On , arc CA Store on the server A On . At this time, the keyword pair of the picture 2^32 Remainder , The result depends on which server it is stored on .

At this time, if you are adding a server D：

  At this time, it will be found that only the data on the green arc is affected , Other arcs are not affected , Compared with the previous one , The impact is small , But in reality, the services of the three stations will not be equally on the circle 1/3 light , For example, below the picture ：

  This condition is called hash skew , So we introduce the concept of virtual node ：

  Virtual nodes are nonexistent points , Imaginary point

The bloon filter ：

Suppose we now have a lot of integer values , No repetition , Now we need to determine a number X In this group of data ？

Hash mentioned before is that there is a corresponding relationship between data and storage location , there The bloom filter is actually a very long binary vector + A set of hash functions .

Suppose we now have three different hash functions A,B,C.

  This is a 20 Binary bits , Or save 1, Or save 0, At first it was all 0.

Now? , We will 100,200,300 The following values are calculated by three hash functions （ here A,B,C Three hash functions are not given , So the value we get is what we assume ）

  Then we will change all the binary bits of the obtained value to 1, The following results are obtained ：

  Suppose we need to judge 250 Is it in this array , We just need to put 250 Calculate through hash function , Here are the results （ The result is also hypothetical ）

  We found that 3 and 9 The location of the for 1, however 19 The location of the for 0, in other words , If 250 It really exists , that 250 The positions of the results calculated by the three hash functions should all be 1, Just one for 0, Then there must be no .

If 250 The following results are obtained through three hash functions ：

250——>A——>6

250——>B——>9

250——>C——>15

We found that 6,9 and 15 All positions are 1, however 250 It doesn't exist in our array , So you can't get 250 It must exist in this array , But as long as there is one position 0, Then there must be no .

Here is a summary of Bloom filter ：