A deliberately tiny deterministic hash (FNV-1a folded onto a 16-bit ring) makes every node and key position a fixed number you can assert against - no random placement, no real hashing library. Every lesson is one concrete spec with exact positions, owners, and move-sets: the first node clockwise with wraparound past the top, a key landing exactly on a node, adding a node that steals only its arc, removing a node that hands its keys to the successor, virtual nodes smoothing a lopsided load, and a replica set that walks clockwise skipping repeat virtual nodes of a node already chosen.
Over 23 lessons you build a consistent hash ring - a library that maps keys (cache entries, user records, shards) to a changing set of nodes so that when a node joins or leaves, only a small, predictable slice of keys has to move. That property is what lets distributed caches and databases add and remove servers without repartitioning everything, and you build the whole thing as an importable library whose public API - place a node, look up a key's owner, add or remove nodes, list a key's replicas - is exactly what you would reach for in a real system.
You start by pinning down a deterministic hash and showing the problem it has to beat: naive modulo hashing (hash(key) % N) remaps almost every key the moment N changes. Then you place nodes and keys on a circular hash space, make a key's owner the first node clockwise, keep node positions in a sorted array and binary-search for the successor with wraparound, and prove the payoff - adding or removing a node moves only about 1/N of the keys while every other key stays put. On top of that core you add virtual nodes to smooth a lopsided load, weight nodes by giving them more virtual positions, and compute a replica set of the next R distinct physical nodes clockwise. The capstone builds a ring with virtual nodes, assigns a set of keys, adds then removes a node, and asserts exactly which few keys moved plus the replica set for a chosen key.
To keep every value hand-checkable the whole project rides on one deliberately small deterministic hash - FNV-1a folded onto a 16-bit ring - so every node and key sits at a fixed, pinnable position. That is a teaching choice, not a limitation of the design: the ring is hash-agnostic, and swapping in SHA-1 or MD5 (what production systems use) changes only the positions, not a line of the ring logic. It is honest about what it stops short of - it is an in-memory, single-threaded library over one ring with a fixed hash, not a networked, concurrent, rebalancing cluster membership service - which is exactly the core that systems like Amazon Dynamo, Cassandra, and consistent-hashing caches wrap with replication policies, failure detection, and data movement.
Every consistent hash ring starts with a hash function that turns a key into a number, the same number every time. Today you build that function - a small, fully specified FNV-1a hash - so that every position on the ring later in the project is a value you can pin down exactly.
Turn a string key into a deterministic 32-bit number with FNV-1a.
Consistent hashing is built on one simple guarantee: a key always lands in the same place. That guarantee comes entirely from the hash function, so we pin it down first. We use FNV-1a, a tiny non-cryptographic hash that needs no library: start from a fixed offset basis, and for each byte of the key, XOR the byte into the running value and multiply by a fixed prime. The multiply is 32-bit and wraps around on overflow, which is what mixes the bits.
Real systems reach for SHA-1 or MD5 here, and the ring you build works with any of
them - it only cares that the hash is deterministic and well spread. We pick FNV-1a
because it is short enough to hold in your head and gives numbers you can reproduce by
hand, which matters when every later lesson asserts an exact position. The empty-string
case is the cleanest check that you started from the right basis: with no bytes to fold
in, Hash("") is the offset basis itself.
// FNV-1a: start from the basis, fold in one byte at a time.func Hash(s string) uint32 {h := uint32(2166136261)for i := 0; i < len(s); i++ {h ^= uint32(s[i]) // XOR the byte inh *= 16777619 // then multiply by the prime (wraps at 2^32)}return h}
A complete, well-tested teaching implementation of a single-process, non-concurrent hash ring whose deliberately tiny 16-bit hash is collision-prone by design: ideal for learning consistent hashing by hand, not for running as-is in a real distributed system.
The 1997 paper that introduced consistent hashing - nodes and keys on a shared circle, a key owned by the nearest node clockwise, and the theorem that adding or removing a node moves only O(K/N) keys. The origin of everything in this project.
The SOSP 2007 paper that made consistent hashing mainstream in production. Read section 4.2 for how Dynamo partitions with a ring, uses virtual nodes for load balance and heterogeneous hardware, and layers replication (the preference list of N nodes) on top - the direction the last chapter of this project points.
A short, well-illustrated walkthrough with a working implementation - the ring as a sorted map, finding the successor, and why virtual nodes matter. The clearest first read after this project.
A different point in the design space: no ring and no per-node storage, just a function mapping a key and a bucket count to a bucket with minimal remapping. Read it to see what consistent hashing looks like when you drop the explicit ring - and what you give up (no arbitrary node names or weighting).
A production system built on a consistent-hashing token ring with virtual nodes (vnodes) and tunable replication. Useful for seeing the ring, virtual nodes, and replica sets you build here operating at cluster scale.