Consistent Hashing

Limits: 3s, 512 MB

In modern software development, hashing is an important concept. It involves generating unique integer key for objects (instance of struct/class) where different values for each key is distributed over some range and unique. It helps to store and lookup these objects for different kinds of future queries. In distributed systems things are bit harder where we need to transfer these objects (thus distributing data and workload among connected workstations) when new workstation can join or existing ones can leave due to network disconnection or workstation shutdown. Consistent hashing is a concept used in distributed systems, so that we can move objects within workstations that affects the system less. To apply consistent hashing algorithm, we assume workstations in a distributed system are connected as a ring network and objects with their keys are stored in between these workstations. Here every object are stored to the workstation which comes first in clockwise direction. For the sake of simplicity let’s assume that we have sequential keys starting from 0 to N-1 (for N keys) and are distributed in a circular fashion.


This is a companion discussion topic for the original entry at https://toph.co/p/consistent-hashing