Consistent Hashing from Scratch

July 2, 2026 · distributed-systems · system-design · go

Say you're sharding a cache across three servers. The obvious scheme is:

server := servers[hash(key)%len(servers)]

It works — until you add a fourth server. Now % 3 becomes % 4, and almost every key maps somewhere new. A single capacity change stampedes the whole cache and hammers the database behind it.

The problem, precisely

With modulo sharding, adding or removing one node out of N remaps roughly (N-1)/N of all keys. Growing a three-node cluster to four moves about three quarters of your keys. The entire point of adding capacity is undone by the cache-miss storm it triggers.

We want the opposite property: changing the cluster size should move as few keys as possible — ideally only the ones that truly have to move.

The ring

Consistent hashing places both keys and servers on the same circular keyspace, say 0 to 2³²-1. Hash each server's ID onto the ring. To locate a key, hash it too, then walk clockwise to the first server you meet. That server owns it.

The ring, read clockwise (positions 0 … 2³²-1):

    … ─ s2 ─ [key] ─ s1 ─ s3 ─ (wraps around to 0) ─ …

A key belongs to the first node clockwise from it — here, s1. Now add s4: only the keys sitting on the arc between s4 and its predecessor move. Every other key stays put. Removing a node is the mirror image — its keys fall to the next server clockwise, and nothing else shifts.

Adding the Nth node relocates about 1/N of the keys, not (N-1)/N. That's the whole trick.

Virtual nodes

There's a catch: with only a handful of servers, the ring is lumpy. A server that happens to own a large arc gets a disproportionate share of keys, and if it leaves, all of its load lands on a single neighbor.

The fix is virtual nodes: hash each physical server onto the ring many times — say 100–200 — under derived keys like s1#0, s1#1, and so on. Each physical server now owns many small arcs scattered around the circle. Load smooths out, and when a server leaves, its share spreads across many neighbors instead of one.

A small Go implementation

type Ring struct {
    replicas int
    keys     []uint32          // sorted hash positions
    owners   map[uint32]string // position → server
}

func New(replicas int) *Ring {
    return &Ring{replicas: replicas, owners: map[uint32]string{}}
}

func (r *Ring) Add(server string) {
    for i := 0; i < r.replicas; i++ {
        h := crc32.ChecksumIEEE([]byte(fmt.Sprintf("%s#%d", server, i)))
        r.keys = append(r.keys, h)
        r.owners[h] = server
    }
    sort.Slice(r.keys, func(i, j int) bool { return r.keys[i] < r.keys[j] })
}

func (r *Ring) Get(key string) string {
    if len(r.keys) == 0 {
        return ""
    }
    h := crc32.ChecksumIEEE([]byte(key))
    // First position clockwise from h; wrap to the start at the end.
    i := sort.Search(len(r.keys), func(i int) bool { return r.keys[i] >= h })
    if i == len(r.keys) {
        i = 0
    }
    return r.owners[r.keys[i]]
}

Get is O(log V), a binary search over the V virtual-node positions.

Where you've already seen it

• Amazon Dynamo and its descendants (Cassandra, Riak) partition data this way.
• memcached clients use the ketama variant to avoid remapping on node changes.
• CDNs and load balancers route requests to backends with it.

Consistent hashing doesn't make rebalancing free — it makes it proportional. And when you're paged at 3am to add capacity, proportional is the difference between a routine deploy and an outage.