Please enable JavaScript.
Coggle requires JavaScript to display documents.
Design Consistent Hashing - Coggle Diagram
Design Consistent Hashing
The rehashing problem
Common formula:
hash(key) % N
N: the number of servers
It works well when number of server is fixed
and the data distribution is even
But most of the key need to be remapped
when a server is added or removed or failed
This cause a storm of cache misses
Consistent Hashing
Space
It depends to the hash function
Example: SHA-1 using 160bit so the space from 0 to 2^160 - 1
Ring
The start and end connects together to create a ring
Servers
The servers are added to the ring by using hash(IP) or hash(name)
Keys
The keys are added to the ring by hash(key)
Server mapping
To find a server, go to clockwise from the key until find a server
Issues
It is impossible to have the same size of partitions on the ring for all of servers
Most of the keys may store on only one server and other servers don't have any data
Virtual servers
Adding more virtual servers to help to balance data distribution
Adding server
To find affected key, go to anticlockwise from added server to the previous sever on the ring.
Removing server
To find affected key, go to anticlockwise from removed server to the previous server on the ring.