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.
- 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.
- Join the two ends of the range into a circle: the hash ring.
- Hash each server (by its IP address or name) with the same function, and put it on the ring.
- Hash each key with the same function (no modulus is used) and put it on the ring.
- 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?