1. Consistent Hashing
Consider the following two scenarios. Describe in each case why consistent hashing is likely to perform better than hashing.
Scenario 1: There is a fixed set of cache servers implementing consistent hashing and a population of clients who have incomplete views of the system i.e. each client only knows about a fraction of the servers
Scenario 2: There is a set of cache servers that change i.e. nodes come and go.

Answer 1:
Hashing:
Hashing is an easy to implement and quick to evaluate algorithm. Let us consider that the fixed set of cache servers are ‘n’, that is the number of nodes. Let us number the computers 0, 1, 2,…,n-1. According to the hashing algorithm, the key value pair (k, v) will be stored on the cache ‘hash(k) mod n’ where hash() is any function that converts the arbitrary string k to a non-negative integer. Keys are distributed evenly in a cluster for any reasonable number of keys, if the hash function being used in hash(k) mod n is a good hash function.
Consistent Hashing:
Consistent hashing is a cleverer algorithm compared to hashing. Here, the output range of the hash function is treated as a ring or fixed circular space. The largest hash value wraps around to the smallest hash value to form the ring. Each node in the system is assigned a random value which represents its ‘position’ on the ring. Each data item identified by a key k is assigned to a node by hashing data item’s key to yield a position on the ring. We walk clockwise on the ring to find the first node with a position larger than the item’s position. If one of the cache servers is down, we go to the next one, and so on. In this way, each node is responsible for the region on the ring between it and its predecessor node on the ring.
Let us assume that we are wrapping the unit interval [0,1) onto a unit circle. So the cache servers 0,1,2,…,n-1 will be mapped onto this unit circle. If the hash function has range [0,R), then we rescale the hash function via k to hash(k)/R.
So we want to store a key value pair (k, v) on the ring. We hash the key onto the circle and then store the key value pair on the first server that appears clockwise on the key’s hash point. Roughly, 1/n of the key-value pairs will get stored on any single machine. This is because of the uniformity of the hash function.
Scenario 1:
Fixed set of cache servers implementing consistent hashing but the population of clients have incomplete views of the system.
In Hashing,
The hash function is fixed which is hash(k) mod n. So if the client does not know the hash function or does not have a view to all the nodes, the client will look for data on a server on which it does not exist. If the data cannot be fetched from other nodes due to lack of communication between the nodes, data will be fetched from the main database every time there is a new query from the client and the client is unaware of its location node. Thus this will cause one object to be assigned to a lot of different caches disturbing the ‘spread’ property of consistency. Similarly, over all the client views, the number of distinct objects assigned to a particular cache is large due to data replication thus causing the ‘load’ to increase. Time taken to fetch data will be high if the client is looking for data on the wrong cache.
In Consistent Hashing,
Each machine is aware of a constant fraction of the currently operating caches because of its ring topology. A client uses a consistent hash function to map an object to one of the caches in its view. The hash functions is constructed in such a way that even if the client is unware of the nodes, the hash value will lie in a particular range of values on the ring. Consistent hashing will follow a clockwise direction on the ring to locate the node with the value that the client is looking for. Here, even in the presence of inconsistent views, references for a given object are directed only to a small number of caching machines. Total number of different caches to which an object is assigned is small and the number of distinct objects assigned to a particular cache is small. Thus the ‘spread’ and ‘load’ properties of consistency are maintained. Time taken to fetch data will be very less compared to hashing.
Scenario 2:
Now when the set of cache servers is changing, the number of nodes will change. Say, if we add a node then n will become ‘n+1’ and if we remove a node then n will become ‘n-1’.
In Hashing,
Instead of computing hash(k) mod n, we will have to compute hash(k) mod (n+1) or hash(k) mod (n-1). This will cause key value pairs to be reallocated to new locations. These new locations will be completely random across the cluster. For a large n value, we will essentially require to move nearly all data to different servers.
The problem with this are:
1) Data moving process is slow and expensive.
2) Cache will be unavailable at the time when data is being moved.
3) Databases will experience traffic issues due to movement from DB to new cache.
4) The high amount of load on the database can make the entire system crash.
In Consistent Hashing,
The hash function being used is more consistent so as to maintain the ‘smoothness’, ‘spread’ and ‘load’ properties. We know that for a range [0,R) of the hash values, the hash function via k will be hash(k)/R. Thus, when a node is added or removed, only the data that needs to live on that node or that needs to be removed from that node respectively, has to be moved. All the other data of the system stays where it is. So when a new node is added, only the fraction of data that lies in it and its predecessor’s range on the ring will be moved to the new node. If a node is removed, all the data on that node will be moved to the next node on the ring in the anticlockwise direction.
The advantages are:
1) Only fraction of data objects need to be moved and not all.
2) The moving of data will take less time avoiding the cache and database availability issue.
3) Even in the presence of inconsistent views, references for a given object are directed only to a small number of caching machines.
4) Since data being moved is less, no one cache is assigned an unreasonable number of objects.