Day 49: Consistent Hashing

System Design with Data Structures & Algorithms ~10 min read 60 min hands-on

Alright, engineers. Welcome back. Today, we're diving into a concept that underpins some of the most resilient and scalable systems on the planet: Consistent Hashing. If you've ever wondered how Netflix streams flawlessly, how Facebook keeps your feed consistent across billions of users, or how a global CDN serves cached content with minimal latency, you're looking at systems where Consistent Hashing plays a pivotal, often invisible, role.

This isn't just about distributing data; it's about intelligently distributing data and requests in a way that minimizes disruption when your infrastructure inevitably changes. And trust me, in a world of microservices, cloud elasticity, and continuous deployment, change is the only constant.

The Problem with Naive Hashing in Distributed Systems

Let's set the stage. Imagine you have a cluster of N servers (or cache nodes). You want to distribute K keys (e.g., user IDs, video chunks, cached objects) across these N servers. The simplest approach?
server_index = hash(key) % N

Seems fine, right? For a fixed N, it works. But what happens when you add a new server (N+1) or remove a failing one (N-1)?
Suddenly, hash(key) % (N+1) or hash(key) % (N-1) will likely map almost every single key to a different server.

This is catastrophic.

  • Cache Invalidation Storm: If it's a cache, nearly all cached items become "missing," leading to massive traffic hitting your backend database.

  • Data Migration Nightmare: If it's a distributed database, you'd have to move almost all data, leading to massive I/O, network strain, and prolonged unavailability.

  • Thundering Herd: Multiple clients attempting to fetch the same "missing" data could overwhelm remaining servers.

This is the fundamental problem Consistent Hashing solves: minimizing key remapping when nodes are added or removed.

Core Concept: The Hash Ring and Virtual Nodes

Consistent Hashing introduces a "hash ring" (or a circular hash space). Both your servers (nodes) and your keys are hashed onto this same ring.

  1. The Ring: Imagine a circle representing the range of possible hash values (e.g., 0 to 2^32 - 1).

  2. Node Placement: Each server is hashed to one or more points on this ring.

  3. Key Placement: Each data key is also hashed to a point on this ring.

  4. Mapping: To find which server owns a key, you traverse the ring clockwise from the key's hash point until you hit the first server's hash point. That's your server.

The Magic of Virtual Nodes:
If you only place physical servers on the ring, and you have, say, 3 servers, a new server might land right next to an existing one, taking a huge chunk of its keys, while another server remains unaffected. This leads to unbalanced distribution.

This is where Virtual Nodes (vnodes) come in. Instead of hashing each physical server once, we hash it multiple times, creating many "virtual" copies of each server on the ring. For example, server_A_vnode_1, server_A_vnode_2, ..., server_A_vnode_X. Each virtual node maps back to the same physical server.

Keep going with the full lesson

The rest of this lesson — plus its implementation guide, runnable scripts and source code — is included with the course or an All Access plan. Create a free account to start the free lessons in every course.

Already a member? Sign in