Consistent Hashing

Maps both servers and keys onto a hash ring; a key belongs to the first server clockwise from it. Adding or removing a server only reshuffles the keys between it and its neighbour, unlike plain hash % N which remaps almost everything when N changes.

Category: Hashing
Time complexity: O(log n) w/ sorted ring
Space complexity: O(n + k)

Pseudocode

place each server at hash(server) on a ring
place each key at hash(key) on the same ring
key's owner = first server clockwise from it
node join/leave only affects its neighbouring arc

Reference implementation

ring = sorted((hash(s), s) for s in servers)
def owner(key):
    pos = hash(key)
    for spos, s in ring:
        if spos &gt;= pos: return s
    return ring[0][1]  # wrap around

Open the interactive Consistent Hashing visualisation →