Consistent hashing in one minute: lessons from production

The One-Minute Insight

Consistent hashing in one minute: imagine a circular ring where both servers and cache keys land based on a hash function, and each key belongs to the first server you encounter moving clockwise. When you add a new server, only the keys between the old server and the new one need to move—not your entire dataset. This is the difference between a scaled system that keeps working smoothly and one that grinds to a halt during growth.

I learned this the hard way during Day 11 of rebuilding a cache layer for a ride-hailing platform. We were losing 80% of our Redis hits every time we added capacity. Consistent hashing changed that conversation from "scaling is painful" to "scaling is routine."

Keys and Servers on a Hash Ring

The core idea is deceptively simple: imagine a circle numbered 0 to 2^32 - 1 (or any large hash space). Both your cache keys and your servers get hashed onto this ring using the same hash function.

Let's say you have three servers: Server A, Server B, and Server C. When you hash their identities, they land at specific positions:

• Server A hashes to position 10
• Server B hashes to position 100
• Server C hashes to position 200

A cache key like "user:12345" also gets hashed. Say it lands at position 85. To find which server owns it, you move clockwise from position 85 until you hit the next server. In this case, that's Server B at position 100.

This simple rule—each key belongs to the first server clockwise from its hash position—is the foundation of consistent hashing. It's deterministic, local, and scalable.

Here's what that lookup looks like in code:

class ConsistentHash {
  private ring: Map<number, string> = new Map(); // hash position -> server ID
  private sortedPositions: number[] = [];

  addServer(serverId: string): void {
    const hash = this.hashFunction(serverId);
    this.ring.set(hash, serverId);
    this.sortedPositions.push(hash);
    this.sortedPositions.sort((a, b) => a - b);
  }

  getServer(key: string): string {
    const keyHash = this.hashFunction(key);
    
    // Find the first position >= keyHash
    for (const pos of this.sortedPositions) {
      if (pos >= keyHash) {
        return this.ring.get(pos)!;
      }
    }
    
    // Wrap around: return the first server on the ring
    return this.ring.get(this.sortedPositions[0])!;
  }

  private hashFunction(input: string): number {
    let hash = 0;
    for (let i = 0; i < input.length; i++) {
      hash = ((hash << 5) - hash) + input.charCodeAt(i);
      hash = hash & hash; // Convert to 32-bit integer
    }
    return Math.abs(hash) % (2 ** 32);
  }
}

Notice the wrap-around logic: if no server exists clockwise from your key, you circle back to the beginning of the ring. This ensures every key maps to exactly one server.

Each Key Belongs to the Next Server Clockwise

The clockwise assignment rule is what makes consistent hashing work. Without it, you'd have arbitrary ownership, and scaling would cause chaos.

Let me walk through a real scenario from our e-commerce platform. We had:

• Cache key "product:5001" hashing to position 45
• Cache key "product:5002" hashing to position 120
• Servers at positions 50, 110, 200

Using the clockwise rule:

• "product:5001" (position 45) → next server clockwise is at 50 → Server A
• "product:5002" (position 120) → next server clockwise is at 200 → Server C

This determinism is crucial. The same key always hashes to the same position, and the same position always finds the same server (until you change the ring). Your client libraries don't need to talk to a central registry. They can compute the server location locally.

In a distributed system, this means:

• No single point of failure for mapping decisions
• Every client independently makes the same choice
• Reduced latency—direct to the right server

That's why Memcached, Redis Cluster, and Kafka partitioning all rely on this principle. It's not magic; it's math that scales.

Adding a Server Moves Only Nearby Keys

Here's where consistent hashing shines in production. When you add a new server, only the keys between the old server and the new one need to move. Everything else stays put.

Traditional modulo hashing—where a key maps to server index (hash(key) % number_of_servers)—reshuffles almost everything when you add a server. If you had 10 servers and add an 11th, roughly 10/11 of all keys get reassigned. That's a thundering herd hitting your database.

Consistent hashing is gentler. Let's visualize adding a new server to our earlier example:

More precisely: any key that was assigned to Server B (100) but hashes between 75 and 100 now belongs to Server D (75) instead. Server D "steals" a slice of Server B's load. Servers A and C are unaffected.

If you have 100 servers and add 1, roughly 1/100 of your keys migrate. Compare that to modulo hashing, where roughly 100/101 migrate. That's the power of the ring.

Here's how you'd add a server and identify migrations:

addServer(serverId: string): string[] {
  const newHash = this.hashFunction(serverId);
  const affectedKeys: string[] = [];

  // Find the previous server on the ring
  const previousPos = this.sortedPositions
    .filter(pos => pos < newHash)
    .pop() ?? this.sortedPositions[this.sortedPositions.length - 1];

  const previousServer = this.ring.get(previousPos)!;

  // In practice, you'd iterate over all cached keys and check:
  // if (getServer(key) changed from previousServer to serverId)
  //   then key needs migration

  this.ring.set(newHash, serverId);
  this.sortedPositions.push(newHash);
  this.sortedPositions.sort((a, b) => a - b);

  return affectedKeys;
}

In production, you'd run this during off-peak hours, use background workers to migrate the affected keys, and monitor cache hit rates to confirm the transition went smoothly. We did exactly this when scaling our trading platform's position cache, and it took minutes instead of the multi-hour outage we'd had before.

Virtual Nodes Spread Load Evenly

There's a catch with basic consistent hashing: if your servers hash unevenly, the ring becomes lopsided. One server might own 50% of the keyspace while another owns only 5%.

The solution is virtual nodes (also called replicas). Instead of placing each server once on the ring, you place it many times using different identifiers.

For example, Server A might exist at positions calculated from:

• hash("ServerA-0")
• hash("ServerA-1")
• hash("ServerA-2")
• ...and so on

With 150 virtual nodes per server, the arc between any two physical servers is divided into roughly equal slices, balancing load automatically. This is what makes consistent hashing practical for real systems.

Here's the improved implementation:

class ConsistentHashWithVirtualNodes {
  private ring: Map<number, string> = new Map();
  private sortedPositions: number[] = [];
  private readonly virtualNodesPerServer = 150;

  addServer(serverId: string): void {
    for (let i = 0; i < this.virtualNodesPerServer; i++) {
      const virtualKey = `${serverId}:${i}`;
      const hash = this.hashFunction(virtualKey);
      this.ring.set(hash, serverId);
      this.sortedPositions.push(hash);
    }
    this.sortedPositions.sort((a, b) => a - b);
  }

  removeServer(serverId: string): void {
    for (let i = 0; i < this.virtualNodesPerServer; i++) {
      const virtualKey = `${serverId}:${i}`;
      const hash = this.hashFunction(virtualKey);
      this.ring.delete(hash);
    }
    this.sortedPositions = Array.from(this.ring.keys()).sort((a, b) => a - b);
  }

  getServer(key: string): string {
    if (this.sortedPositions.length === 0) {
      throw new Error("No servers available");
    }
    const keyHash = this.hashFunction(key);
    for (const pos of this.sortedPositions) {
      if (pos >= keyHash) {
        return this.ring.get(pos)!;
      }
    }
    return this.ring.get(this.sortedPositions[0])!;
  }

  private hashFunction(input: string): number {
    let hash = 0;
    for (let i = 0; i < input.length; i++) {
      hash = ((hash << 5) - hash) + input.charCodeAt(i);
      hash = hash & hash;
    }
    return Math.abs(hash) % (2 ** 32);
  }
}

The number 150 is a heuristic. More virtual nodes = better balance but slower lookups. In practice, 50–200 works for most systems. We use 100 across all our platforms because it's a good middle ground.

Virtual nodes also improve resilience. If a server crashes, its virtual nodes are spread across the ring, so the load doesn't dump onto one neighbor—it distributes naturally.

Common Mistakes

Mistake 1: Using a weak hash function. If your hash function has collisions or poor distribution, keys cluster on the ring instead of spreading evenly. Use SHA-1, MD5, or a solid 32-bit hash. Don't roll your own.

Mistake 2: Not implementing virtual nodes. A few servers on a raw ring will have wildly uneven load. Virtual nodes cost almost nothing and solve this completely.

Mistake 3: Forgetting to account for migration during deployment. Assuming keys teleport instantly when you add a server will lead to cache stampedes and database overload. Plan for gradual migration, use background workers, and monitor.

Mistake 4: Hardcoding the virtual node count. Make it configurable. You may need to tune it as your system grows or as hardware changes. We've had to double our replica count during platform scaling to keep tail latencies acceptable.

Mistake 5: Using consistent hashing for everything.** It's great for distributed caches and message queues, but not ideal for databases where you also need strong consistency and replication logic. Don't over-engineer.

Key Takeaways

• Consistent hashing places servers and keys on a circular ring; each key belongs to the next server clockwise. This is deterministic and requires no central registry.
• When you add a server, only keys between the old and new server positions need to migrate. With 100 servers, that's roughly 1% of your data, not 99%.
• Virtual nodes (replicas) ensure load spreads evenly across the ring. Without them, uneven hashing distributions will bottleneck your system.
• Use a solid hash function, plan for gradual key migration, and monitor the transition. Instant reshuffles will spike your database load.
• Consistent hashing is the backbone of distributed caches, message brokers, and sharded data stores. Understanding it deeply is essential for scaling systems past single-machine limits.