Consistent Hashing for Data Partitioning

Overview

Consistent hashing is the routing function that keeps distributed caches, databases, and pub/sub systems evenly balanced while nodes join and leave. Instead of mapping keys to shards with modulo arithmetic—which causes full reshuffles on membership changes—consistent hashing arranges nodes on a logical ring so only a narrow slice of keys move.

The approach underpins distributed key-value stores, vector search shards, and most CDN edge caches. Virtual nodes provide fine-grained control over load distribution, helping ops teams rebalance hot partitions without copying petabytes.

This lesson walks through the structure, failure handling, and implementation patterns you need to apply consistent hashing to new services, including how to layer replication factors and locality hints on top of the basic ring.

Core Concepts

• Hash Ring: A circular 0–232 space where both keys and node identifiers are hashed.
• Virtual Nodes: Multiple positions per physical node to smooth load distribution.
• Replication Factor: Number of distinct nodes selected per key to provide redundancy.
• Deterministic Lookup: Route by walking clockwise until the next virtual node; no central registry required.

How It Works

Building the Ring

Each node chooses v tokens by hashing node_id || replica_index. Tokens are stored in a sorted array. To route a key, hash it, binary search for the first token greater than the hash, and fallback to index 0 if you wrap around.

Replication and Preference Lists

To replicate, continue walking clockwise until you collect rf distinct physical nodes. Keep track of rack/region metadata and skip nodes that would violate anti-affinity rules. This yields a stable preference list used by Raft groups in an experimental distributed database.

Practical Applications

• Distributed database storage tiers: Each tenant table uses its own ring to keep noisy neighbors isolated.
• Edge cache invalidation: A CDN deploys consistent hashing to broadcast purge events only to caches responsible for the affected URL prefix.
• Vector index shards: A vector database can use consistent hashing so embeddings from the same tenant land on predictable search shards, simplifying locality-sensitive auth.

Implementation Patterns

• Store tokens in an immutable array and rebuild on membership changes to allow lock-free lookup using atomic pointer swaps.
• Cache search hints per hot keyspace to avoid repeated binary searches in the request path.
• Version the ring and piggyback change announcements over gossip so every node eventually converges to the same layout.
• Instrument key churn (moved keys / total keys) whenever the ring changes; alarms fire if churn exceeds a safe percentage (e.g., 5%).

Code Examples

Go: Building the Token Array

type Token struct {
    Value uint32
    Node  string
}

func buildTokens(nodes []Node, virtuals int) []Token {
    tokens := make([]Token, 0, len(nodes)*virtuals)
    for _, n := range nodes {
        for v := 0; v < virtuals; v++ {
            h := hash32([]byte(fmt.Sprintf("%s-%d", n.ID, v)))
            tokens = append(tokens, Token{Value: h, Node: n.ID})
        }
    }
    sort.Slice(tokens, func(i, j int) bool { return tokens[i].Value < tokens[j].Value })
    return tokens
}

TypeScript: Lookup with Replication Factor

function locate(tokens: Token[], key: string, rf = 3): string[] {
  const hash = murmur(key)
  const owners = new Set()
  let idx = binarySearch(tokens, hash)
  while (owners.size < rf) {
    owners.add(tokens[idx].node)
    idx = (idx + 1) % tokens.length
  }
  return Array.from(owners)
}

Common Pitfalls

• Too few virtual nodes: Causes volatile load distribution; aim for at least 100 tokens per physical node.
• Ignoring heterogeneity: Treating all servers equally overloads small instances when the ring reshuffles.
• Non-monotonic hashing: Changing the hash function reassigns every key; pin the implementation version forever.
• Slow ring propagation: A stale routing table causes split-brain writes; distribute updates via gossip or central config service quickly.

Key Concepts Recap

• Consistent hashing minimizes data movement during membership churn.
• Virtual nodes and weights smooth hot spots and encode hardware capacity.
• Preference lists enable replica placement policies without central coordination.
• Monitoring churn and hash-ring versions keeps control planes honest.