Consistent Hashing is kinda cool

📝 摘要 #

本文从水平扩展的场景出发，系统讲解了一致性哈希（Consistent Hashing）的原理与演进。首先指出了传统取模哈希 hash(key) % N 的致命缺陷——服务器数量变化时几乎全部键需要重新映射，导致缓存命中率骤降。随后引入一致性哈希的核心思想：将键和服务器映射到固定的哈希环上，键沿顺时针找到第一个服务器，从而在增减服务器时仅影响相邻区间的键。文章进一步讨论了哈希环上的分布不均匀问题，引入虚拟节点（Virtual Nodes / Vnodes）使物理服务器在环上拥有多个位置以实现均衡分布。最后分析了热点（Hot Spot）问题——极热门键仍然会集中在单一服务器——并给出两种解决方案：热键多副本复制和键加盐（Key Salting）。

核心概念： 一致性哈希通过将键和服务器映射到固定哈希空间（环）而非依赖服务器数量，实现了增减节点时最小化的键重映射，是分布式系统水平扩展的关键技术。

关键技术栈 / 关键要点：

1. 取模哈希的局限 — hash(key) % N 依赖服务器数量 N，N 变化时大量键被重新映射，缓存命中率暴跌
2. 一致性哈希环 — 将键和服务器映射到 0 ~ 2³²-1 的固定哈希空间，键顺时针找到首个服务器，增减节点仅影响相邻区间
3. 虚拟节点（Vnodes） — 为每个物理服务器创建多个虚拟位置（如 S1-V1, S1-V2…），分散在环的不同位置，解决服务器分布不均匀问题
4. 热点问题（Hot Spot） — 极热门键（如名人账号）始终路由到同一服务器，导致单节点过载
5. 热键复制与键加盐 — 将热键复制到多服务器分发流量，或对键添加后缀（如 user:messi-1/-2/-3）使其哈希到不同位置

关键结论 / 实践建议： 一致性哈希是分布式缓存和数据库分片（Sharding）的基础算法，配合虚拟节点可有效解决数据分布均衡性，但热点问题需额外策略（复制/加盐）应对。

Hii in this blog I will try to cover consistent hashing in detail from top to bottom.

But before getting into consistent hashing, let’s first understand the problem it is trying to solve.

Let's say you built an application and suddenly it went viral overnight on twitter. Initially, you have a single server running your application. As more and more users start using it, the server starts getting overloaded. It may not have enough CPU, RAM, storage or other resources to handle the increasing traffic.

Now you have two basic options:

The first option is to make your existing server more powerful. You can add more CPU, RAM, storage, etc. This is called vertical scaling, or scaling up.

The second option is to add more servers and distribute the workload between them. This is called horizontal scaling or scaling out.

Horizontal and Vertical Scaling Visualization

Since consistent hashing is commonly used in horizontally scaled systems, especially for things like partitioning and distributed caches, I will stick with horizontal scaling here.

Now we have multiple servers. But this creates another question:

How do we decide which server should handle a particular piece of data?

This problem appears in several distributed systems, such as distributed caches and databases.

In a database, for example, we can use sharding (partitioning) to distribute data across multiple servers. There are different ways to decide which server should store a particular piece of data and hashing is one of them.

Similarly, in a distributed cache, we need to decide which cache server should store a particular key. For simplicity, let's use a distributed cache as our example.

Let's say our application has users like:

We need some way to distribute these users across our servers.

One simple approach is to use a hash function:

server = hash(key) % number_of_servers

For example, if we have 3 servers:

So visually:

visual diagram of modulo hashing how it works

ignore the actual hash calculation for now and focus on how the keys are mapped to servers.

From the diagram and the table above, we can now see how the keys are distributed across the servers. Everything looks fine: we hash each key, use the modulo operation, and route it to the corresponding server.

Now let's add one more server and see what happens. Here is the new table after adding a new server:

so visually:

After adding a new server

After adding the new server, many keys are now mapped to different servers. This can significantly reduce the cache hit ratio. For example, if user:101 was stored on Server 0 but is now routed to Server 2, the request will miss the cache and fetch the data from the database.

Now what if this happening to millions of keys. A single server addition could turn a huge number of cache hits into misses, putting unnecessary load on the database.

The problem is that modulo hashing depends directly on the number of servers. When the number of servers changes, many keys get remapped. This makes scaling expensive.

So how can we add or remove servers without reshuffling almost all of our keys?

That's the problem consistent hashing tries to solve. Instead of using the number of servers in the hash calculation, consistent hashing maps both keys and servers onto a fixed hash space.

For example, we can use a 32-bit hash space ranging from 0 to 2³² - 1. A key is hashed to a position within this fixed range and this position doesn't change when we add or remove servers. There is no hash(key) % N where N is the number of servers, so the key's position is independent of the number of servers.

For simplicity, you can visualize this fixed hash space as a circle, where servers are distributed at fixed positions based on their hash values

For example, let's say we have four servers: S0, S1 and S2. We hash each server's identifier and use the resulting hash value as its position on the ring.

But we also need to place the keys on the same ring. When a request arrives, we take the key from the request and hash it to find its position on the ring.

As shown in the diagram, the key is hashed to a position R1 on the ring. From there we move clockwise until we encounter the first server. That server becomes responsible for the key.

Now what happened when we add a new server?

Suppose we add a new server, S3. We hash S3 and place it on the existing ring. Here it lands between S1 and S2.

After adding a new server S3

Before adding S3, keys between S1 and S2 belonged to S2. After adding S3, those keys now fall under S3. We need to remap them because otherwise the routing and the actual location of the data would disagree.

For example, if user:101 is now mapped to S3 but its cached value is still sitting on S2, a request will be sent to S3, which won't find the key. That results in a cache miss. So we move those affected keys from S2 to S3 so that the key's mapping and the actual data location stay in sync.

The distribution problem #

So far, everything looks great. When we add a new server, only a portion of the keys need to move. But there is another problem with our hash ring. Look at the diagram below. What do you think happens if multiple servers end up very close to each other?

The problem is that the servers don't necessarily get an equal share of the hash ring. If several servers happen to land close together, another server may end up owning a much larger portion of the ring.

In this diagram, S1 owns a much larger portion of the ring because there is a large gap between S0 and S1. Any key that lands in this region will be routed to S1, so S1 can end up handling much more traffic than the other servers.

So how do we fix this?

Instead of giving each physical server only one position on the ring, we give it multiple positions. These are called virtual nodes (vnodes). To create them, we take the server's identifier and combine it with a virtual-node number.

For example, for server S1, we can create:

Each virtual node is hashed separately and placed at a different position on the ring. This spreads a single physical server across different parts of the ring, making the distribution of keys much more balanced.

This virtual nodes are not physical servers. They are multiple positions on the ring that all point back to the same physical server. So when a key lands on S1-V3, the actual request still goes to S1.

What the hack is Hot Spots?? #

Virtual nodes solved the distribution problem, but there is still another problem that can happen. Let's say Lionel Messi creates his first Twitter account and posts something. Suddenly, millions of people start requesting his profile at the same time. All those requests are for the same key.

Since the key always hashes to the same position on the ring, all those requests will be routed to the same server. So even though our keys are evenly distributed across the servers, one extremely popular key can still overload a single server. This is called a hotspot or hot key.

There are multiple ways to handle this. One is to replicate the hot key across multiple servers. For example, instead of keeping user:messi only on S1, we can copy it to S2 and S3 as well. Now the requests can be distributed across these servers instead of sending everything to S1.

Another approach is key salting, where we create multiple versions of the key, such as user:messi-1, user:messi-2, and user:messi-3, so they are hashed to different positions on the ring.

And that’s it! Thanks for reading this far. If I missed anything, feel free to let me know in the comments.

That's all folks! #