Design consistent hashing

The problem

You have a cluster of cache or storage servers and need a rule that says which server holds which key. The first idea is server = hash(key) mod N. It works until N changes, which it always does: a server fails, or you add capacity.

100%

Figure SDA-CSD-02-1 · Why mod-N hashing breaks when N changes · © forcsguy.com

When N changes, almost every key maps somewhere new. A cache suddenly misses on nearly everything and the database behind it is flooded. A storage cluster would have to shuffle most of its data.

Goal: when a server joins or leaves, only about 1/N of the keys should move.

The idea: a hash ring

1. Imagine hash values arranged in a circle (the ring), from 0 up to a maximum and wrapping around.
2. Hash each server onto the ring.
3. Hash each key onto the same ring.
4. A key belongs to the first server clockwise from its position.

100%

Figure SDA-CSD-02-2 · Hash ring ownership · © forcsguy.com

Adding a server D between A and B takes over only the keys that fall between A and D. Everything else stays where it is. Removing a server hands its keys to its clockwise neighbour. Either way, only the neighbouring arc moves.

Finding the owner efficiently

Keep the server positions in a sorted list. To place a key, hash it and use a binary search for the first position greater than or equal to it, wrapping to the first server if you pass the end. That is O(log N) per lookup.

Two problems with the basic ring

100%

Figure SDA-CSD-02-3 · Why a plain ring can be unfair · © forcsguy.com

Fixing uneven load: virtual nodes

With only a handful of servers, the arcs between them are uneven, so some servers hold far more keys. And when a server dies, all its load lands on a single neighbour.

The fix is virtual nodes: each physical server is hashed at many points (say 100 to 200) on the ring.

100%

Figure SDA-CSD-02-4 · Virtual nodes per server · © forcsguy.com

• Keys spread much more evenly.
• When a server leaves, its load is shared among many others.
• A bigger server can be given more virtual nodes than a smaller one.

The cost is a larger ring to store and update.

Which keys move, exactly

When a server joins, find the previous server going anticlockwise from it; only the keys between that neighbour and the new server move, and they all move to the new server. When a server leaves, the keys it held (the span back to its anticlockwise neighbour) move to the next server clockwise. Nothing else is touched, which is why the data transfer stays small and predictable.

Spreading keys evenly also reduces hotspots: without it, several very popular keys can land on the same server and overload it. With many virtual nodes per server, the spread gets tighter (published experiments show the imbalance shrinking from around 10 percent to about 5 percent as virtual nodes per server go from roughly 100 to 200), at the price of more ring metadata to store, so the count is a tuning knob.

100%

Figure SDA-CSD-02-5 · Adding a server to the ring · © forcsguy.com

100%

Figure SDA-CSD-02-6 · Removing a server from the ring · © forcsguy.com

Where it is used

• Distributed caches (so adding a node does not wipe the cache).
• Partitioned databases such as Dynamo-style stores, where each key is also copied to the next few servers clockwise for replication (next lesson).
• Load balancing with stickiness, where the same client keeps hitting the same backend.
• Content delivery to decide which edge server holds an object.

Things to watch

• Hot keys: one very popular key still loads its owner. Replicate it or add a local cache.
• Choose a good hash function: uniform distribution matters more than cryptographic strength.
• Membership changes must be learned by all clients consistently, through a config service or gossip, otherwise two clients disagree about the owner.

More on this site