CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 3 of 8 · 2 min read

The hash ring

Putting servers and keys on a circle and walking clockwise.

Think of a clock face with the numbers 0 to 99 instead of 1 to 12. Four people stand at different places on the edge. A parcel is put down at some point on the edge, and it goes to the first person met walking clockwise. If you walk past 99, you come round to 0.

The book describes the construction.

  1. Pick a hash function. The book uses SHA-1, whose output ranges from 0 to 2 to the power 160, minus 1. This range is the hash space.
  2. Join the two ends of the range into a circle: the hash ring.
  3. Hash each server (by its IP address or name) with the same function, and put it on the ring.
  4. Hash each key with the same function (no modulus is used) and put it on the ring.
  5. To find the server for a key, go clockwise from the key's position until a server is found.

Hash ring

A hash ring is the range of hash values bent into a circle. Servers and keys sit at the positions given by their hashes. A key belongs to the first server found going clockwise from it.

Example: on a ring of 0 to 99, servers S0, S1, S2, S3 sit at 10, 35, 60 and 85. A key at 20 belongs to S1 (the first server at or after 20).

A worked example on that ring. Servers: S0 at 10, S1 at 35, S2 at 60, S3 at 85. Five keys:

Key Position First server clockwise Owner
k0 5 10 S0
k1 20 35 S1
k2 50 60 S2
k3 70 85 S3
k4 90 passes 99, wraps to 0, then reaches 10 S0

Each server owns the stretch of ring that ends at its position and begins just after the previous server:

Server Owns positions Share of the ring
S0 86 to 99 and 0 to 10 25 of 100
S1 11 to 35 25
S2 36 to 60 25
S3 61 to 85 25

Read it as

The server's position is the end of its territory. The territory runs back (anticlockwise) to the previous server.

Check yourself:

  • On the ring above, which server owns a key at position 86? At 61? At 10?
  • Why is no modulus used when hashing the keys onto the ring?