Consistent Hashing

Consistent hashing is a scaling pattern where both database/cache nodes and data keys are mapped onto a circular hash ring.

This limits the number of keys remapped when nodes are added or removed to K / N (where K is the total number of keys, and N is the number of nodes).

📊 The Hash Ring

              Node A (0)
             .─-──-──.
        Keys /         \ Key 1 -> Node B
      Mapped/           \
           |             | Node B (120)
            \           /
        Keys \         / Key 2 -> Node A
             '─-──-──'
              Node C (240)

• Mechanism: To locate a node for a key, hash the key and walk clockwise along the ring until you hit the first node.
• Virtual Nodes: To ensure even distribution of keys across nodes, map multiple virtual labels (e.g., NodeA-1, NodeA-2) for each physical node onto the ring.

When to use? Essential for distributed cache systems (like Memcached or Redis Cluster) and distributed databases (like DynamoDB or Cassandra) to prevent catastrophic cache stampedes during scaling.