Consistent Hashing

What do you know about hash? C’mon, I know you’ve heard about hash functions like MD5, SHA-256 & etc.

“A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are used to index a fixed-size table called a hash table.” © Wikipedia

Okay, thank you Wikipedia, now we also know what is a hash table (or a hash map). But still let me explain how it basically works.

Imagine that you work as a lawyer and wanna get court decisions under some articles. These articles are very popular and a lot of other lawyers in your company wanna get the same court decisions very often. But obtaining the data from a DB and aggregation of results are expensive operations. Consequently, one of programmers from your company told you that he is going to use a cache in your application to reduce amount of DB calls.

Also he mentioned something like “blah-blah .. distributed cache .. blah-blah .. consistent hashing ..”

If you are curious lawyer, you will read some my articles about cache and cache eviction policies. But now we’ll look at what lies at the heart of the cache and how it works. I’m talking about HashMap.

HashMap

When you wanna put something to the hashMap, the hashCode will be calculated first.

Article 224 of the Law of May 13, 1863 → 1239031166
Section 202 of the National Securities Act of 1 947 → -2057294793
Article 2 of the Act of March 10, 1792 → 1507657450
section 458-B of the Pure Food and Drug Act → 1971618558
Section 412 of the Patriot Act → 148124959

And then it’ll be used to determine in which bucket in the array your value should be put. Let’s simplify all of this. Suppose our keys and their hash codes are:

Article 224 .. → 53
Section 202 .. → 24
Article 2 .. → 77
section 458-B .. → 34
Section 412 .. → 96

And we have a hashMap which based on an array of Nodes and this array has length 10. When we put some value with the key “Article 224”, we need to determine a slot in the array. “Article 224” has a hashCode 53, our array has a length 10, so we can just get the remainder of the division 53 by 10:

53 % 10 = 3

Thus the “Article 224” will be put into the slot with index ‘3’ in the array of Nodes. In the same way we can put the key “Section 202” with the hashCode ‘24’ into slot with index ‘4’. But the key “section 458-B” has the hashCode ‘34’ and need to be stored to the slot with index ‘4’ too. What to do? Don’t worry, we have an array of Nodes and every Node can be connected with another Node. Thus just create a new Node with the key “section 458-B” and connect it with the Node “Article 224”.

What’s the problem?

When the count of elements equals array length (or some else threshold), we’ll need to add more buckets (10, 11, 12 in our case). But then array length will be changed, and if we try to get some element by key, we won’t find it! Look at the formula: it was 53 % 10 = 3, but has become 53 % 13 = 1. Now it should be stored in the slot with index ‘1’ instead of ‘3’. So, we need to calculate new place for every element in the map and move them to their new home. This operation is called Rehash.

Rehash is expensive operation if our map has a lot of elements.

Okay, now let’s move our attention to a distributed cache. Suppose the cache has 1 billion elements (the government doesn’t sleep and produces laws). It needs to allocate a huge amount of memory. We could distribute cache between several servers. For example, 0–3 buckets could be stored on server S0, 4–6 on S1 and 7–9 on S2. If we wanna get decisions by the “Article 224”, we just need to determine a bucket (53 % 10 = 3) and get a server from some storage (we know that 3rd bin is stored on the server S0).

Or we could not store the correspondence of buckets and servers, but calculate the server on the fly. Like to determine the number of bin, we should get the remainder of division by server count: 53 % 3 = 2, it’s mean S2 server (yep, not like on the picture’s table).

What will go wrong when we add new S3 server or server S2 fails? Yes, the same thing like in a simple hashMap. It nothing changes, when the S3 has been added, our map still need a rehash! Because now (when S3 is added) the count of the servers was changed and “Article 224” will be stored at the server S1 instead of S2 (53 % 4 = 1).

Why do we need a rehash in the cache? Because, as I described above, after add one more server we will get a cache miss for every element. Yes, you can just wait and after some time cache will be filled.. if your servers are always prepared for this load of course..

How to avoid full rehash?

Consistent hashing is the answer!

A hashCode() method is return a value with the type “integer”. Array in the hashMap has max length equals Integer.MAX_VALUE. Though, we can split this array on some count of buckets. For simplicity suppose that Integer.MAX_VALUE is 100. Then we can use some count of bins (10 for example) to store values.

“Article 224” has hash code 53 and will be stored to the 6th bucket (50–59), “Section 202” has # 24, so it’ll be stored to the third bin (20–29), and so on. How to determine the number of the bucket in practice? By binary search! Red-black tree in this case will look like this:

it should be rebalanced at the left side, of course

We can move backward or forward, it doesn’t matter, but once chosen, we must always move in this direction. “Article 224” -> 53 -> 50; “Section 202” -> 24 -> 20.

Returning to the servers, we can assign server and hash mappings: hashes 0–39 as server S0; 40–69 as S1; 70–99 as S2. Determining of the server in this case will look like:

If we choose backward direction, then 53 will accord to the 40 (S1 server); 24 to 0 (S0 server) and so on.

But again, what if S2 goes down?

Then all it’s requests will be redirected to the server S1, according to backward direction in the servers tree: 77 -> 40 (S1); 96 -> 40 (S1).

I think that the S1 server won’t be happy to work for two. And what to do? Add more servers of course! But virtual. We can assign S0 to buckets with the # 0–9, 30–39, 50–59, 80–89; S1 -> 10–19, 40–49, 60–69; S2 -> 20–29, 70–79, 90–99. Also we can give a label for each bucket, like: S0_0 -> 0–9; S0_5 -> 50–59; S0_8 -> 80–89; S1_1 -> 10–19; S1_4 -> 40–49 …

Servers should be distributed randomly. And now, if S2 fails, according to a backward direction in the # tree, two requests will go to S1 (S2_2 -> S1_1, S2_7 -> S1_6) and one request to S0 (S2_9 -> S0_8).

The more randomly labeled buckets — the better distribution, when one of the servers goes down. You don’t need a full rehash, the elements on the servers S0 & S1 will stay at their place. You will get a cache miss only for elements from S2.

If a new server is added (S3), you should allocate its labels somewhere from 0 to 100. For example, S3_75 -> # 75–79, then S2_7 will be limited by hashes 70–74, instead of 70–79. And you will get a cache miss only for requests with the keys with the hashes 75–79:

“Section 412” -> # 77 -> S3_75 (S3 server).

The old records on the S2 (with # 75–79) will be removed after some time according to its eviction policy.

Java implementation

Let’s create a simple application which could show the consistent hashing in action. It should contain servers with their labels (virtual servers) and distributed between them cache.

Get Alex Kuk’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Create a Server class first, which will store a server name and list of its labels:

ServerLabel class will get range start randomly:

Also we need a ServerTree (hash ring), which will store the available servers (server labels more precisely):

Create a cache based on concurrent hash map:

And DecisionService which can put and get value from distributed cache:

Okay, now we are prepared to create a main method. Let’s go ahead and simply create a three servers with their own cache:

After that add nine virtual servers (labels) to the hash ring (server tree):

And put the values to the distributed cache:

Server tree is looked like this now:

label=’S3_8', rangeStart=79620631
label=’S1_2', rangeStart=457191453
label=’S2_3', rangeStart=476515658
label=’S3_7', rangeStart=831012325
label=’S2_4', rangeStart=1000870721
label=’S1_0', rangeStart=1159297670
label=’S2_5', rangeStart=1206315082
label=’S1_1', rangeStart=1260733873
label=’S3_6', rangeStart=1758698458

Just remind: the key “Section 412 of the Patriot Act” has a hash code 148124959. Thus, this key should be stored at the server S3 with the label S3_8, because it has a nearest fewer range start number 79620631.

Check the caches:

S1 Cache: Article 2 of the Act of March 10, 1792, not guilty
S2 Cache: Article 224 of the Law of May 13, 1863, fully justified
S3 Cache: Section 202 of the National Securities Act of 1 947, partially justified
section 458-B of the Pure Food and Drug Act, almost guilty
Section 412 of the Patriot Act, we doubt

So, “Section 412..” is stored at the server S3, it’s true!

Let’s try to find it:

decisionService.getValue(“Section 412 of the Patriot Act”)

Got it:

we doubt

Let’s imitate the server S3 fails:

s3.getLabels().forEach(serverTree::removeServer);

And try to get the value again:

null

Expectedly. If you check the caches, you will see that all values on their places. But anyway we can’t find the value for the key “Section 412..”, because now we’re trying to find it at another server. Put it again:

decisionService.putValue(“Section 412 of the Patriot Act”, “we doubt”);

And let’s see where it was stored:

S1 Cache: Article 2 of the Act of March 10, 1792, not guilty
Section 412 of the Patriot Act, we doubt

The value went to the server S1. And try to get the value again:

we doubt

Expectedly.

Conclusion

I hope this explanation was clearly. But if not, there is another one based on a hash ring.

You can look at the full code on my github project.

Feel free to shake hand on Medium or Telegram or Twitter.