Lab 12 · Consistent Hashing

Run it: make lab-12
Source: labs/lab-12-consistent-hashing/main.go

The Problem

You have a pool of N CDN edge nodes. You want to route each URL to the same node consistently — so the same URL is always cached at the same node, maximizing cache reuse. How do you map URLs to nodes?

The Naive Approach: Modular Hashing

node := hash(url) % N   // assign URL to node index

This works — until you add or remove a node. When N changes to N+1:

hash(url) % N   →  different node for almost every URL

Remapping fraction ≈ (N-1)/N. With 10 nodes, adding one node remaps 90% of all cache keys to different nodes. 90% of your cache invalidates instantly — a thundering herd against your origin.

This is why CDNs don’t use modular hashing for node selection.

Consistent Hashing (Karger et al., 1997)

Consistent hashing places both nodes and keys on a virtual ring (a circle with positions 0 to 2^32 or 2^64). A key is assigned to the first node clockwise from the key’s position on the ring.

Ring (0 to 2^32)

         0
    ───────────
   /     N1     \
  │    (pos=15)  │
  │         ●   │
  │              │
  │    ●    ●   │
  │   K1   N2   │
  │              │
  │              │
   \   N3   K2  /
    ─────────────
         max

K1 (pos=45) → first clockwise node → N2 (pos=60)
K2 (pos=90) → first clockwise node → N3 (pos=95)

When a node is added: only the keys that fall between the new node’s position and its predecessor need to move. Expected remapping: only 1/N of all keys, regardless of N.

When a node is removed: only keys assigned to that node need to move to the next node. Again, only 1/N remapped.

Virtual Nodes (Vnodes)

With only one ring position per node, the key distribution is uneven — some nodes get more keys than others, especially with few nodes.

The solution: each physical node occupies multiple positions on the ring (virtual nodes). The buraksezer/consistent library defaults to 100 vnodes per node:

Physical node A → virtual nodes at positions: 15, 234, 567, 891, 1043, ...
Physical node B → virtual nodes at positions: 72, 310, 640, 958, 1200, ...

With 100 vnodes per node and 3 nodes: 300 ring positions. Key distribution becomes approximately uniform (σ ≈ 10% of mean load per node).

Tradeoff: more vnodes = better balance, but more ring metadata to maintain. At 1000 nodes × 100 vnodes = 100,000 ring positions. Still trivial in memory.

Implementation with buraksezer/consistent

import "github.com/buraksezer/consistent"

type Member string
func (m Member) String() string { return string(m) }

// Create ring
cfg := consistent.Config{
    PartitionCount:    271,   // prime number for distribution
    ReplicationFactor: 40,    // vnodes per member
    Load:              1.25,  // max load imbalance factor
    Hasher:            hasher{},
}
c := consistent.New(nil, cfg)

// Add nodes
c.Add(Member("node-1"))
c.Add(Member("node-2"))
c.Add(Member("node-3"))

// Route a key
member := c.LocateKey([]byte(url))  // returns the responsible node
// member.String() → "node-2"

Important API note: LocateKey returns a consistent.Member interface, not a (Member, error) pair. It always returns one member (the ring is never empty once populated). If the ring is empty, it panics — guard with a node count check.

The PartitionCount Parameter

Consistent library’s PartitionCount (not to be confused with Kafka partitions) divides the hash space into PartitionCount slices. Each partition is assigned to a member. Better explanation of the API:

PartitionCount:    271  → 271 hash space segments (prime to minimize collisions)
ReplicationFactor: 40   → each member appears in ~40 partitions

With 3 members and ReplicationFactor=40, each member owns ~89 partitions (271/3 ≈ 90, slight imbalance due to prime).

Applications in CDN Architecture

1. Shield routing (Lab 13)

Origin Shield uses consistent hashing to route all requests for a URL to the same shield PoP. This maximizes the shield’s cache utilization: if 10 edge PoPs all forward misses for /popular-image to the same shield node, that shield node only fetches from origin once.

2. Peer-to-peer CDN (BitTorrent-style)

CDN nodes use consistent hashing to decide which peer to request cached content from before going to origin. Key = object ID, ring = all CDN nodes in a region.

3. Memcache cluster routing

Client-side consistent hashing for memcached clusters. The application client routes each key to the same cache server. Adding a new cache server only remaps 1/N keys (instead of all keys with modular hashing). This was described in Facebook’s 2013 memcache paper.

4. Load balancing with session stickiness

Route users to the same backend server (for session data stored in-process) using consistent hashing on the client IP or session cookie.

Failure Modes

Hot Keys

Consistent hashing assigns each key to exactly one node. If a key is extremely popular (a viral video URL), one node gets all the traffic.

Solutions:

1. Consistent hash → multiple replicas: store popular objects on K nodes (the primary plus K-1 successors), distribute reads randomly among them.
2. Application-level scatter: Nginx upstream zones with least_conn (route to least-loaded backend).
3. Per-node in-memory cache: popular objects are already in L1 on every node; consistent hashing only affects L2 and origin routing.

Cloudflare’s Argo routing uses a variant: route based on real-time network latency and node load rather than pure hash, accepting the cache inefficiency for better tail latency.

Try It

make lab-12

# Route URLs to nodes — each URL consistently maps to the same node
curl http://localhost:8080/route/article/1
curl http://localhost:8080/route/article/1  # same node every time

# Show distribution
curl http://localhost:8080/stats

# Simulate node removal — minimal remapping
curl -X DELETE http://localhost:8080/nodes/node-2
curl http://localhost:8080/stats  # articles on node-2 moved to next node