Reprinted from :

One 、 summary

1、 our memcache The client uses consistency hash Algorithm ketama Select data storage node . And conventional hash The idea of the algorithm is different , It's just for us to store data key Conduct hash Calculation , Allocate storage to different nodes . Uniformity hash The algorithm is for the server where we want to store the data hash Calculation , And then confirm that each key Storage location .

 2、 routine hash The application of the algorithm and its disadvantages

The most conventional way is hash The way to take the mold . For example, the number of available machines in the cluster is N, that key The value is K It's easy to route your data requests to hash(K) mod N Corresponding machine . You bet , This structure is simple , It's also practical . But in some high-speed development web In the system , There are still some flaws in such a solution . With the increasing pressure of system access , The cache system has to increase the speed and data capacity of the cluster by increasing the number of machine nodes . Adding machines means following hash The way to take the mold , At the moment of adding machine nodes , A lot of caches don't work , Cache data needs to be rebuilt , Even the overall cache data migration , The moment will give DB Bring very high system load , Setting causes DB Server down .

  3、 Design distributed cache System time , Uniformity hash What problems can algorithms help us solve ?

The core of distributed cache design : In designing distributed cache System time , We need to get key The distribution is balanced , And it's increasing cache server after ,cache To minimize the migration of .

The consistency mentioned here hash Algorithm ketama The approach is : Choosing a specific machine node does not depend only on the data that needs to be cached key Of hash In itself , It's the machine node itself hash operation .

Two 、 Consistent hash algorithm scenario description ( Reprint )

1、 hash Machine nodes

First of all, find out the hash value ( How to calculate the machine node hash?ip It can be used as hash The parameters of .. Of course, there are other ways ), And then distribute it to 0~2^32 On a ring of ( Clockwise distribution ). As shown in the figure below :

There are machines in the cluster :A , B, C, D, E Five machines , Through certain hash We distribute it over the ring as shown in the figure above .

2、 access

If there is a request to write to the cache , among Key The value is K, Calculator hash value Hash(K), Hash(K) It corresponds to Fig – 1 A point in the ring , If the corresponding point is not mapped to a specific machine node , So look clockwise , Until the node with the mapping machine is found for the first time , This node is the determined target node , If you exceed 2^32 Still can't find node , Then hit the first machine node . such as Hash(K) The value is between A~B Between , So the hit machine node should be B node ( Pictured above ).

3、 Add node processing

Pictured above – 1, We want to add a machine on the basis of the original cluster F, The increase process is as follows :

Compute the number of machine nodes Hash value , Map the machine to a node in the ring , Here's the picture :

Add machine nodes F after , Access policy does not change , Still, in accordance with the (2) Access in the way of , At this time, the situation of cache failure is still inevitable , The data that can't be hit is hash(K) Fall in before adding nodes C~F Data between . Although there is still a hit problem caused by node increase , But more traditional hash The way to take the mold , Uniformity hash We've minimized the number of missed data .

Consistent Hashing Maximum restraint hash Re division of the key cloth . In addition, better load balancing effect should be achieved , When the number of servers is relatively small, virtual nodes need to be added to ensure that the servers can be evenly distributed on the ring . Because the general hash Method , The mapping locations of servers are very uneven . The idea of using virtual nodes , For each physical node ( The server ) Assign on circle 100~200 A little bit . This will suppress uneven distribution , Minimize cache redistribution when servers increase or decrease . User data mapped on virtual node , It means that the real storage location of user data is on the actual physical server represented by the virtual node .
Here is a diagram describing the virtual nodes that need to be added for each physical server .

3、 ... and 、 With spymemcache Source code to demonstrate the virtual node application

1、 The consistency of the above description Hash One potential problem with the algorithm is :
     (1)、 The nodes hash It's distributed unevenly over the ring , So many key When looking for nodes , Will exist key The probability of hitting each node is quite different , Can't achieve effective load balancing .
     (2)、 If there are three nodes Node1,Node2,Node3, The three nodes are very close when they are distributed on the ring , On the ring key When looking for nodes , A lot of key Clockwise is always assigned to Node2, And the probability that the other two nodes will be found is very small .

2、 The solution to this problem can be :
     improve Hash Algorithm , Distribute the nodes evenly to the ring ;[ a citation ] The idea of using virtual nodes , For each physical node ( The server ) Assign on circle 100~200 A little bit . This will suppress uneven distribution , Minimize cache redistribution when servers increase or decrease . User data mapped on virtual node , It means that the real storage location of user data is on the actual physical server represented by the virtual node .

In the view Spy Memcached client when , It's found that it uses a method called Ketama Of Hash Algorithm , With the idea of virtual node , solve Memcached The distributed problem of .

3、 Source code description

The client use TreeMap Store all nodes , Simulate a circular logical relationship . In this ring , There is an order relationship before the node , therefore TreeMap Of key Must be realized Comparator Interface .
How do nodes fit into this ring ?

 protected void setKetamaNodes(List<MemcachedNode> nodes) {
TreeMap<Long, MemcachedNode> newNodeMap = new TreeMap<Long, MemcachedNode>();
int numReps= config.getNodeRepetitions();
for(MemcachedNode node : nodes) {
// Ketama does some special work with md5 where it reuses chunks.
if(hashAlg == HashAlgorithm.KETAMA_HASH) {
for(int i=; i<numReps / ; i++) {
byte[] digest=HashAlgorithm.computeMd5(config.getKeyForNode(node, i));
for(int h=;h<;h++) {
Long k = ((long)(digest[+h*]&0xFF) << )
| ((long)(digest[+h*]&0xFF) << )
| ((long)(digest[+h*]&0xFF) << )
| (digest[h*]&0xFF);
newNodeMap.put(k, node);
getLogger().debug("Adding node %s in position %d", node, k);
} }
} else {
for(int i=; i<numReps; i++) {
newNodeMap.put(hashAlg.hash(config.getKeyForNode(node, i)), node);
assert newNodeMap.size() == numReps * nodes.size();
ketamaNodes = newNodeMap;

The above process can be summarized as follows : Four virtual nodes in a group , With getKeyForNode Method to get the name,Md5 After the coding , Each virtual node corresponds to Md5 code 16 In bytes 4 individual , Form a long Type value , As the only virtual node in the ring key. The first 10 That's ok k Why Long The type of ? Because of Long Type a implements Comparator Interface .

After dealing with the distribution of formal nodes on the ring , You can start key The game of finding nodes on the ring .
For each key Still have to complete the above steps : To calculate the Md5, according to Md5 Byte array of , adopt Kemata Hash The algorithm gets key The position in this ring .

5、 ... and 、 summary

1、 Uniformity hash The algorithm just helps us reduce cache When the number of machines in the cluster increases or decreases ,cache The least amount of data can be reconstructed . as long as cache Clustered server The number has changed , The problem of data hit is inevitable

2、 For the problem of data distribution equilibrium , Through the idea of virtual node to achieve balanced distribution . Of course , We cache server The fewer nodes, the more virtual nodes are needed to balance the load .

3、 our cache The client doesn't maintain one at all map To record each key Where is it stored , It's all through key Of hash and cacheserver( Maybe ip It can be used as a parameter ) Of hash Calculate the current key On which node should it be stored .


memcached More articles on consistent hashing algorithms

  1. memcached Distributed consistent hash algorithm

    <span style="font-family: FangSong_GB2312; background-color: rgb(255, 255, 255);"> If ...

  2. Consistent hash algorithm and its application PHP Realization

    When doing server load balancing, there are many load balancing algorithms to choose from , Include :  Round robin algorithm (Round Robin). The hash algorithm (HASH). Least connection algorithm (Least Connection). Response speed algorithm (Respons ...

  3. Consistent hash algorithm —— The core problem of the algorithm is when slot When the number changes , Be able to move as little data as possible

    Consistent hash algorithm Excerpt from : Brief introduction of algorithm Consistent hash algorithm (Consistent Hashi ...

  4. memcached Consistent hashing and php Client implementation

    1.memcached Distributed algorithms memcached The distributed is realized by the algorithm of client , Suppose the key name is $key, The number of servers is N, There are two ways to implement it : Modulo hash crc32($key)%N, With this algorithm, the key ...

  5. Consistent hash algorithm (Consistent Hashing Algorithm)

    Consistent hash algorithm (Consistent Hashing Algorithm) On consistency Hash Principle and Application   We're talking about consistency Hash Let's talk about a problem first . problem : There are now hundreds of millions of users , Tens of millions of orders are generated every day , Such as ...

  6. Nginx Third party module installation and consistent hash algorithm use

    Nginx Third party module installation and consistent hash algorithm use Third party module installation method summary : With ngx_http_php_memcache_standard_balancer-master For example 1: decompression To pat ...

  7. Go -- Consistent hash algorithm

    The consistency hash algorithm 1997 By the Massachusetts Institute of Technology Karger People are working on Distributed Cache Proposed in , The design goal is to solve the hot spots in the Internet (Hot spot) problem , Original intention and CARP Very similar . Consistency hash fixed CARP Use ...

  8. Consistency hash algorithm and Java Realization

    original text : Consistent hash algorithm is a common algorithm in distributed system . such as , A distributed storage system , To store data in ...

  9. Five minutes to understand the consistency hash algorithm (consistent hashing)

    Reprint please explain the source : The consistency hash algorithm 1997 A distributed hash proposed by MIT in (DHT) Implementation algorithm ...

Random recommendation

  1. linux install ArcSDE10.1

    The experiment was not successful , The steps are for reference only . 1: First of all, check that Linux Under the operating system Oracle Whether the database can be started , Whether it can be connected, etc [oracle@localhost ~]$ sqlplus SQL*Plus: Rele ...

  2. Hadoop MapReduce Programming API Entry series of compression and counter ( thirty )

    Not much to say , Go straight to the code . Hadoop MapReduce Programming API Introduction series of small file merge ( Twenty-nine ) Generated results , As an input source . Code package zhouls.bigdata.myMapReduce. ...

  3. hrbust oj 1526+2028 Tree array

    Bubble sorting If a number after a number and this number do not conform to the sorting rules Then this number will be exchanged with that number in a bubble in the future It's used here Tree array to find the reverse number of ways to do It should be noted that 2028 You can't change the size of the array directly 1 ...

  4. linux FILE type .

    stdio.h Header file , There are the following ( Use the internal line number to explain ): /* The opaque type of streams. This is the definition used elsewhere. * ...

  5. javascript - Work notes ( Event three )

    I won't say much about the definition , There are two kinds of events One , Bubbling Events This is a IE Implementation of event model in browser , seeing the name of a thing one thinks of its function , It's like a bubble in the water , From the bottom up , The parent element it passes through will trigger the corresponding event . namely : The parent element of the trigger element triggers before the trigger element , see dem ...

  6. MySQL-5.6.36- Deployment installation ( Compiled version )

    1. System environment ( This site uses centos6.8_x64) [root@centos ~]# cat /etc/redhat-release CentOS release 6.8 (Final) 2.yum Ann ...

  7. Novice learning cocos2dx,centos7 Next installation process

    background I'm going to learn to write games , Novice , Of course from cocos2d-x Start . I saw cocos Documents , The installation is for ubuntu Of , Record here centos7 Installation on . compile . The process of running tests . If you already have ubuntu, This is not recommended ...

  8. python Development _shelve_ Full version _ Bloggers recommend

    ''' python Medium shelve modular , Can provide some simple data operation He and python Medium dbm Very similar . The difference between the following : They all save data in the form of key value pairs , But in the shelve Module , key Must be a string , And the value can be ...

  9. gulp-usemin The plug-in USES

    About what is gulp, It and grunt What's the difference , There is no introduction here . This article mainly introduces how to use gulp-usemin This plug-in , At the same time, we will also briefly introduce some plug-ins used in this article . What is? gulp-usemin Used to put H ...

  10. JavaScript Array loop traversal of forEach

    1.  js Array loop traversal . Array loop variables , The first thing that comes to mind is for(var i=0;i<count;i++) In this way . besides , You can also use the simpler forEach The way 2.  forEac ...