Consistent Hashing
Consistent hashing is a hashing technique used in distributed systems. It is also a somewhat optimized re-hashing/ remapping technique. While the idea is old (in CS timelines), I think it became popular after the Akamai article and the dynamo paper.
What
Consistent hashing distributes keys evenly across a few servers (shards, nodes, etc.). The data could be the data in a partitioned DBMS**, distributed cache or requests in a distributed system, etc. And when those items need to be remapped (because say a shard becomes full, goes down, gets added), the technique reduces the number of items which need to be remapped and redistributed, and avoids the remapping/ re-hashing of the whole data.
How
For ease of understanding the servers/ partitions are considered to be on a ring. The data key is hashed. The hash value may fall within a range of values (in simplest way, the hash-value % number of servers) and is allocated to the clockwise next server on the ring.
This is very similar to slot/ bucket allocation in traditional hashing. When a server gets added (due to a higher load) or goes down, in traditional techniques the whole data will be rehashed and remapped again.
Consistent hashing avoids this by hashing not just requests (data) but servers (generally, IPs or UUIDs of servers) as well. When servers are placed on the ring, or later when a new server is added on the ring, it’s done in a deterministic manner with the use of a hash function. The server hash function need not be same hash function as used in hashing data keys. It could be much simpler as number of servers « number of data items. But like all hash functions the function has to be deterministic- if you pass same value multiple times to the function, it should map to the same output hash. A server with smaller hash value is placed before- on the hash ring going clockwise- another server with bigger hash value. It is easy to visualize a ring and going clockwise, but generally BST is used in practice. Think about it, what is needed is basically an ability to tell which server is to be placed before another server and later easily finding a server to allocate the data to and later if a new server gets added finding the right spot for it. Thus a binary search tree works well with O(log(n)) complexity.
An Example
For ease of understanding let’s say that your system is a distributed cache. You are caching biography webpages of Greek mythological characters. And you chose a hash function such that the hashes turn out to be the characters’ Greek names. The above image shows the current in progress state of your system. ServerA contains cached pages of characters A thr’ E; ServerF from F to J, etc. Now if you know a bit of Greek mythology, you would naturally see that ServerA is already bleeding- there’s a lot of bad blood between the characters. How would it accommodate Athena, Aphrodite, Apollo? Ideally, you should question your hash function if it lets you add Apollo and Achilles in the same bucket. But just to take it easy for now, you decide to add a new server say ServerC and let the mythological characters take their own fateful course. You may consider yourself a duct tape programmer but I am telling you, you should be a statesman. Now if you add any new page of a character whose name begins with A or B, it goes to ServerA. C, D, E go to ServerC. But what about existing pages cached in ServerA like Cassandra, Clytemnestra? When ServerC gets added you could aggressively move these from ServerA to ServerC. That way when you look up a page for Cassandra, you could directly go to ServerC. Alternatively, you could let the irrelevant pages in ServerA be evicted; and when a request for Cassandra lookup comes in you take a cache-miss and fetch the page from main server and this time you cache it on ServerC. Depends on trade-offs you choose. Important point is that you had to re-arrange/ remap only the data that was hosted on the ServerA. The rest of the data on other servers did not have to move. A somewhat similar arrangement takes place when a server goes out. Suppose ServerF from above image crashes, data from which server will move to which server?
No Silver Bullet
Consistent hashing has some limitations like celebrity effect (hotkey) where a few keys receive massive traffic (for example, the page for Zeus and respective server in the Greek Mythology example above may receive disproportionately- well, maybe proportionately because he’s quite a character- high traffic). Also one server crashing can send a wave of cascading failure down the ring. And, physical limitations like Fallacies of distributed computing play a part.
Improvements
There are some improvements over this basic idea. First of all a better hash function which distributes data evenly is far better than anything else. But you could also add a level of indirection and have virtual nodes. And there are trade-offs dictated by usage pattern, etc. For example, you could replicate data and use quorum (Amazon’s Dynamo paper mentioned sloppy quorum based on their service requirements).
** DDIA book first edition says about consistent hashing in data partitioning chapter: this particular approach actually doesn’t work very well for databases, so it is rarely used in practice (the documentation of some databases still refers to consistent hashing, but it is often inaccurate)…
I haven’t yet read the second edition which came out recently, but the author has updated the the description. Here’s what it says now: The sharding algorithm used by Cassandra and ScyllaDB is similar to the original definition of consistent hashing, but several other consistent hashing algorithms have also been proposed, such as highest random weight, also known as rendezvous hashing, and jump consistent hashing. With these approaches, rather than a small number of existing shards being split into subranges to create new shards for a node that is added, the new node is instead assigned individual keys that were previously scattered across all the other nodes. Which is preferable depends on the application.
So I think we are good.
My Greek mythology knowledge is quite limited. I have read a book or two before. Recently listened to Stephen Fry’s audiobooks Mythos and Troy again. I will recommend those. Somehow I did not like Madeline Miller’s Song Of Achilles in the past even though it’s quite popular. Now started Stephen Fry’s audiobook Odyssey. He’s talked about the Greek mythology a number of times on youtube and I recently watched his appearance on Anita Anand and William Dalrymple’s Empire podcast. But if you are ok with a bit of off-colored humor (and why shouldn’t you be) here’s a joke he told on QI.