Consistent Hashing
Consistent hashing is a hashing technique used in distributed systems. It is also a somewhat optimized re-hashing technique. While the technique is old (in CS timelines), I think it became popular after Akamai article and the dynamo paper.
Consistent hashing distributes keys of hashed data evenly across a few servers (shards, nodes, etc.). The data could be requests in a distributed system, data in a partitioned DBMS, distributed cache, 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.
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 IP or UUID of server) 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 same output hash. It also helps identify which hash value is smaller and helps place a server with smaller hash value before- on the hash ring going clockwise- than a server with higher hash value. It is easy to visualize a Ring and going clockwise, but generally BST is used in practice.
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 their 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. How would it accommodate Athena, Aphrodite, Apollo? Ideally, you should question your hash function which 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 just 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?
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. Also, physical limitations like Fallacies of distributed computing play a part.
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). As wikipedia says, in practice, a binary search tree (BST) is used to dynamically maintain the server ID within a cluster or hashring, and to find the successor or minimum within the BST, tree traversal is used.
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.