Consistent Hashing

Question 1

What is DHT? Whats it for?

Answer 1

Distributed Hash Table (DHT) is one of the fundamental components used in distributed scalable systems. Hash Tables need a key, a value, and a hash function where hash function maps the key to a location where the value is stored.

Question 2

2 Disadvantages of normal hashing

Answer 2

It is NOT horizontally scalable. Whenever a new cache host is added to the system, all existing mappings are broken. It will be a pain point in maintenance if the caching system contains lots of data. Practically, it becomes difficult to schedule a downtime to update all caching mappings.

It may NOT be load balanced, especially for non-uniformly distributed data. In practice, it can be easily assumed that the data will not be distributed uniformly. For the caching system, it translates into some caches becoming hot and saturated while the others idle and are almost empty.

Question 3

What is Consistent Hashing?

Answer 3

Consistent hashing is a very useful strategy for distributed caching system and DHTs. It allows us to distribute data across a cluster in such a way that will minimize reorganization when nodes are added or removed. Hence, the caching system will be easier to scale up or scale down.

Question 4

How does Consistent Hashing work?

Answer 4

1. Given a list of cache servers, hash them to integers in the range.
2. To map a key to a server:
   - - Hash it to a single integer.
   - - Move clockwise on the ring until finding the first cache it encounters.
   - - That cache is the one that contains the key.