《一致性哈希算法》

一致性哈希（Consistent Hashing）解决的是分布式系统在节点增删时，简单取模运算命中率急剧下降的问题，被广泛应用于分布式缓存（如 Memcached、Redis Cluster）、负载均衡和数据分片等场景。

1 问题背景：为什么不能用取模

假设有 3 台缓存服务器，把 key 通过 hash(key) % 3 分布到各节点。一旦服务器数量从 3 变为 4 或 2，绝大部分 key 的哈希结果都会变化，映射到别的节点，导致缓存大面积失效（缓存雪崩），请求在切换瞬间直接打到数据库。

因此需要一种「节点数量变化时，已有映射关系基本保持不变」的哈希算法，一致性哈希正是为此设计。

2 哈希环

一致性哈希通过一个称为 哈希环 的数据结构实现：

环的起点是 0，终点是 2^32 - 1，起点与终点首尾相连；
环上的整数范围是 [0, 2^32 - 1]，整个哈希空间被组织成一个环。

2.1 将服务器映射到环

假设有 3 台机器 c1、c2、c3，用同一个哈希函数计算它们的哈希值：

hash(c1) = t1
hash(c2) = t2
hash(c3) = t3

每个服务器占据环上 1 个点。

2.2 将对象映射到环

假设有 4 个对象 o1、o2、o3、o4，用同样的哈希函数计算哈希值（范围也是 0 ~ 2^32 - 1）：

hash(o1) = m1
hash(o2) = m2
hash(o3) = m3
hash(o4) = m4

2.3 为对象选择服务器

把服务器和对象都放到同一个环上之后，在环上顺时针查找离该对象哈希值最近的一台服务器，该服务器就是对象所属的节点。

3 数据倾斜与虚拟节点

当服务器较少时，节点在环上分布可能非常不均匀，导致大部分对象集中落在少数几台机器上，这就是数据倾斜（数据偏斜）。

解决办法是引入虚拟节点：把每台物理机器虚拟成一组虚拟节点，分别放置到环上。

hash(c1#1) = t1
hash(c1#2) = t2
hash(c1#3) = t3

hash(c2#1) = t4
hash(c2#2) = t5
hash(c2#3) = t6

hash(c3#1) = t7
hash(c3#2) = t8
hash(c3#3) = t9

查找对象时：先根据哈希值找到对应的虚拟节点，再由虚拟节点映射到物理机器。虚拟节点越多，各机器的负载越均匀；同时当某台物理机挂掉时，其虚拟节点上的数据也能平滑地迁移到相邻节点，缓解雪崩效应。

4 一致性哈希需要满足的性质

一个良好的分布式缓存一致性哈希算法应满足以下五点：

平衡性（Balance）：哈希结果应尽可能均匀地分布到所有节点，充分利用所有缓冲空间；
单调性（Monotonicity）：已有内容通过哈希分派到缓冲后，若新增缓冲区，原内容应能映射到新增的缓冲区，而不是被映射到旧缓冲中的其它缓冲区；
分散性（Spread）：在分布式环境中，同一内容不应被不同终端映射到不同缓冲区；
负载（Load）：从缓冲角度出发，一个缓冲区也不应被不同用户映射为不同内容；
平滑性（Smoothness）：缓存服务器数目平滑改变时，缓存对象的映射也应平滑改变。

5 参考实现（Python）

hash_ring 是一个经典的 Python 一致性哈希实现（Amir Salihefendic）：

        
      
import math
from bisect import bisect
import hashlib


class HashRing(object):
    def __init__(self, nodes=None, weights=None):
        self.ring = dict()
        self._sorted_keys = []
        self.nodes = nodes
        self.weights = weights or {}
        self._generate_circle()

    def _generate_circle(self):
        total_weight = 0
        for node in self.nodes:
            total_weight += self.weights.get(node, 1)

        for node in self.nodes:
            weight = self.weights.get(node, 1)
            factor = math.floor((40 * len(self.nodes) * weight) / total_weight)

            for j in range(0, int(factor)):
                b_key = self._hash_digest('%s-%s' % (node, j))
                for i in range(0, 3):
                    key = self._hash_val(b_key, lambda x: x + i * 4)
                    self.ring[key] = node
                    self._sorted_keys.append(key)

        self._sorted_keys.sort()

    def get_node(self, string_key):
        pos = self.get_node_pos(string_key)
        if pos is None:
            return None
        return self.ring[self._sorted_keys[pos]]

    def get_node_pos(self, string_key):
        if not self.ring:
            return None
        key = self.gen_key(string_key)
        nodes = self._sorted_keys
        pos = bisect(nodes, key)
        if pos == len(nodes):
            return 0
        return pos

    def gen_key(self, key):
        b_key = self._hash_digest(key)
        return self._hash_val(b_key, lambda x: x)

    def _hash_val(self, b_key, entry_fn):
        return ((b_key[entry_fn(3)] << 24)
                | (b_key[entry_fn(2)] << 16)
                | (b_key[entry_fn(1)] << 8)
                | b_key[entry_fn(0)])

    def _hash_digest(self, key):
        m = hashlib.md5()
        m.update(key.encode('utf-8'))
        return list(m.digest())

使用示例：

        
      
memcache_servers = ['192.168.0.246:11212',
                    '192.168.0.247:11212',
                    '192.168.0.249:11212']

ring = HashRing(memcache_servers)
server = ring.get_node('my_key')

6 复杂度与评价

查找一个 key 的时间复杂度为 O(log n)（在有序哈希环上二分定位）；
相比取模哈希，节点增删时只有少量 key 的映射发生变化，命中率损失小；
引入虚拟节点后负载更均匀，但环上节点数量增多，占用内存略有上升。

7 典型应用

分布式缓存：Memcached / Redis Cluster 的 slot 分布；
负载均衡：根据请求来源 IP 一致性哈希，保证同一用户会话固定打到同一后端；
数据分片：数据库分库分表、消息队列分区路由。

8 面试常考关键词

缓存雪崩、hash环、虚拟节点、数据倾斜。延伸考点：一致性哈希与取模哈希的对比、虚拟节点数量如何权衡、Redis Cluster 的 16384 个 slot 机制。

阅读 — · 全站 —