Consistent Hashing
distributed, scalable system
09 Mar 2019
View Comments
#computer
#programming
#consistent
#hashing
#cache
#caching
#DHT
#distributed
#cloud
#system
We live in a world with so much data that we are always looking for a bit of more efficient ways to store/retrieve things. Consistent hashing is one of the essential concepts used in a scalable and distributed world like cloud system.
Before we talk about what this “Consistent hashing” is, let’s first explore the basic of hashing. As you may already know, a “hashed” item requires a unique hash function which maps the key to the value uniformly. In the case of un-uniformly distributed hash, we may end up with the hash collision which would map a single “key” with multiple “values.”
Internally, a hash function is used to compute the index (exact location) to a block of space where the item is placed. Usually, the array is a great data structure to store such values mapped from the hashed key (as access time is O(1) on them).
index = hash_function(key)This index then is used to map to the location where the appropriate item is. What happens when there is a limited # of spaces allocated for us? For example, the maximum space available on that array is 5. Then we’d have to place in as much value as we can within that five space.
One easy and naive approach here would be using the mod to find the index, “mod size” (% size). To be exact, “hash_function(key) % size”. And use the index found to place within that limited “5” spaces.
Using the simplistic and intuitive hashing approach, “hash_function(key) % size,” we can consider the following examples. For simplicity, let’s assume we have three servers that one of these servers hold the caches to these “key” items:
- “item 1” (hash value=1723171%3) mapping to server 1
- “item 2” (hash value=2532539%3) mapping to server 2
- “item 3” (hash value=3758232%3) mapping to server 0
The example works fine until we make changes to the number of servers holding caches. For instance, if we remove server #3 from the # of servers above, mapping of those above 3 items change. Notice we are with 2 servers now, instead of 3.
- “item 1” (hash value=1723171%2) mapping to server 1
- “item 2” (hash value=2532539%2) mapping to server 1
- “item 3” (hash value=3758232%2) mapping to server 0
Similarly, if we add an extra server to our original 3 servers, you will notice, it also changes the index-mapping from the original.
- “item 1” (hash value=1723171%4) mapping to server 3
- “item 2” (hash value=2532539%4) mapping to server 3
- “item 3” (hash value=3758232%4) mapping to server 0
You may naively think what if we cache one by one (in rotation) to each server, that will undoubtedly distribute the data uniformly! And yes, that will absolutely distribute the load evenly. However, maximizing the uniform data distribution is not the goal here. For a cache, we need to be able to pinpoint where this “item” belongs to and be able to retrieve it.
The method is not a scalable and efficient way to uniformly distribute the data. Also, rebuilding the cache whenever we add/lose a server is quite expensive (cache misses) and we may need to recompute the hash which is another costly task. All this may eventually degrade the entire system performance badly which then raises a question, could there be a solution where we do not depend directly on the number of servers?
Consistent Hashing
Consistent Hashing for the rescue! Consistent Hashing is a useful strategy for a distributed caching system (DHT). The strategy allows us to spread the data without having to reorganize too much. So adding/removing a server is not a huge burden anymore.
In Consistent Hashing, when the hash table resizes (e.g. a new cache host is added/removed to/from the system), only remapped keys are on average, ‘k/n,’ where ‘k’ is the total number of keys and ‘n’ is the total number of servers. With the traditional method, like the example I provided above, we ended up remapping nearly all keys which cause a lot of unnecessary cache-misses and degrades overall performance badly.
How does it do that?!
After you read through this part, you will be astounded by how simple the method is. Just like any other typical hash function, consistent hashing maps a key to an integer, but the changing of the size of nodes (servers) do not affect the hash key that assigning to the server.
For example, let’s say our hash function maps to the indices from 0 to 255. Imagine there is a ring that starts from 0 ending in 255. The numbers could be ranging from 0 to a million if that was what hash function uniformly distribute. To simplify our example, let’s stick to 0 to 255 numbers.
Let’s assume there are 3 servers to start, A, B, and C. Then we use hash_function for the location of these 3 servers (distributed between 0-255). Once we have the position of these servers, we allocate anything that’s in between the servers or from the starting position to the nearest left or right one (successor or predecessor). Below is showing how these “key hashes” distributed for each server:
server A: 0 - 84
server B: 85 - 170
server C: 171 - 255Let’s say we have some of these data mapped to the ring as such:
- key “abcd” => hash_function(key) = 75. This is mapped to server A
- key “foobar” => hash_function(key) = 88. This is mapped to server B
- key “xyz” => hash_function(key) = 200. This is assigned to server C.
When we add a server to the above server list, server D, gives us the location of the new server(“hash_function(Server D)”). Say this is in between server A and B.
server A: 0 - 39
server D: 40 - 84
server B: 85 - 170
server C: 171 - 255Uh oh, there is a problem. The key “abcd” we mapped earlier (with hash id 75) which used to map in Server A should now be assigned to server D. Therefore it is inevitable not to make a little bit of adjusting (shifting/moving) when we add/remove a server. However, this is far better than changing the entire hash table though. We might have a few cache misses but not in all of the servers. Removing a server follows a similar concept as adding a server. Data (key) will all need to be moved to the nearest successor or predecessor when a server goes out of the ring. The critical point here is that a server addition or removal do not directly update hash id of the every other server keys.
Like you noticed above, it all the sudden is vital to choose a good hash function for both choosing positions of the server and to choose the server of our key (data). When they are not uniformly distributed, there could end up with a server that handles the majority of data. However, it is not easy to come up with such functions which uniformly distributes every nodes and data.
That’s when we introduce “virtual replicas” of the servers. “virtual replicas” exploits multiple hashes to come up for one server to uniformly distributed on the ring. So say we had server hash, “hash_function(server A) = 10”. We then introduce similar variated second hash function, “hash_function2(server A) = 100”. We can even introduce a third hash function, “hash_function3(server A) = 200”. Similarly, for other servers, we can apply similar logic to allocate these servers uniformly in the ring. Basically, they are imaginary servers (not like virtual machines), the nodes are virtually created.
With “virtual replicas,” chances of having one server with a high load is low because we can distribute these servers across the ring more conviniently which means keys will be more balanced.
To see a simple python implementation code, see the example below. Note below implementation covers only the Consistent Hash part (as with this entire post) — actual caching of data handled in each server via MemCached, NoSQL etc.
