当单台机器无法容纳全部数据时，我们需要将数据分散到多台机器上，这就是分区（Partitioning）。哈希分区是最常见的分区策略之一，通过哈希函数将数据均匀分布到各个节点。本文将深入探讨哈希分区的演进历程：从最朴素的取模哈希，到解决扩容问题的一致性哈希（Consistent Hashing），再到 Google 提出的 Jump Consistent Hash 和 Maglev Hashing，以及它们在 Cassandra、Riak、TiKV 等真实系统中的应用。
一、朴素哈希：取模的困境
1.1 最简单的方案
最直观的哈希分区方法是对键做哈希，然后对节点数取模：
def get_node(key, num_nodes):
"""朴素的哈希分区"""
hash_value = hash(key)
return hash_value % num_nodes假设我们有 3 台服务器（node0、node1、node2），数据分布如下：
keys = ["user:1001", "user:1002", "user:1003", "user:1004", "user:1005"]
# 使用 Python 内置 hash 函数（为演示目的）
for key in keys:
h = hash(key)
node = h % 3
print(f"{key} -> hash={h} -> node{node}")这个方案简单高效，哈希函数保证了数据的均匀分布，查找时间是 O(1)。然而，它有一个致命缺陷：当节点数量变化时，几乎所有数据都需要迁移。
1.2 扩容的噩梦
假设我们从 3 个节点扩容到 4 个节点，来看数据迁移情况：
import hashlib
def consistent_hash_value(key):
"""使用 MD5 生成稳定的哈希值"""
return int(hashlib.md5(key.encode()).hexdigest(), 16)
keys = ["user:1001", "user:1002", "user:1003", "user:1004", "user:1005",
"user:1006", "user:1007", "user:1008", "user:1009", "user:1010"]
print("原始 3 节点分布：")
old_mapping = {}
for key in keys:
h = consistent_hash_value(key)
node = h % 3
old_mapping[key] = node
print(f"{key} -> node{node}")
print("\n扩容到 4 节点后：")
migrations = 0
for key in keys:
h = consistent_hash_value(key)
new_node = h % 4
if old_mapping[key] != new_node:
migrations += 1
print(f"{key}: node{old_mapping[key]} -> node{new_node} (需要迁移)")
else:
print(f"{key}: 仍在 node{new_node}")
print(f"\n迁移率：{migrations}/{len(keys)} = {migrations/len(keys)*100:.1f}%")运行结果显示，扩容时约有 75% 的数据需要迁移。在生产环境中，这意味着：
- 大量网络流量：TB 级数据在节点间传输
- 服务抖动：迁移期间请求可能路由到错误节点
- 性能下降：磁盘 I/O 和网络带宽被迁移任务占用
对于从 N 个节点变化到 M 个节点，理论上只有 1/M 的数据应该保持不变，其余都需要重新分配。这就是朴素哈希的根本问题：不具备单调性（Monotonicity）。
二、一致性哈希：环形空间的智慧
2.1 核心思想
一致性哈希（Consistent Hashing）由 Karger 等人在 1997 年的论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中提出，最初是为了解决分布式缓存的问题。
核心思想是将哈希空间组织成一个环（通常是 0 到 2^32-1 或 2^160-1）：
- 节点哈希：将每个物理节点的标识（如 IP 地址）哈希到环上
- 数据哈希：将每个数据键哈希到环上
- 顺时针查找：数据被分配到其哈希值顺时针方向遇到的第一个节点
2.2 基础实现
import hashlib
import bisect
class ConsistentHash:
def __init__(self):
self.ring = [] # 有序的哈希值列表
self.ring_dict = {} # 哈希值到节点的映射
def _hash(self, key):
"""使用 MD5 生成 32 位哈希值"""
md5 = hashlib.md5(key.encode())
return int(md5.hexdigest()[:8], 16)
def add_node(self, node):
"""添加物理节点"""
hash_value = self._hash(node)
if hash_value not in self.ring_dict:
self.ring.append(hash_value)
self.ring.sort() # 保持有序
self.ring_dict[hash_value] = node
def remove_node(self, node):
"""移除物理节点"""
hash_value = self._hash(node)
if hash_value in self.ring_dict:
self.ring.remove(hash_value)
del self.ring_dict[hash_value]
def get_node(self, key):
"""获取键对应的节点"""
if not self.ring:
return None
hash_value = self._hash(key)
# 二分查找第一个大于等于 hash_value 的位置
index = bisect.bisect_right(self.ring, hash_value)
# 如果超出范围，回到环的起点
if index == len(self.ring):
index = 0
return self.ring_dict[self.ring[index]]
# 测试
ch = ConsistentHash()
nodes = ["node0", "node1", "node2"]
for node in nodes:
ch.add_node(node)
keys = ["user:1001", "user:1002", "user:1003", "user:1004", "user:1005"]
print("初始分布（3 节点）：")
initial = {}
for key in keys:
node = ch.get_node(key)
initial[key] = node
print(f"{key} -> {node}")
# 添加新节点
print("\n添加 node3 后：")
ch.add_node("node3")
migrations = 0
for key in keys:
node = ch.get_node(key)
if initial[key] != node:
print(f"{key}: {initial[key]} -> {node} (迁移)")
migrations += 1
else:
print(f"{key}: 仍在 {node}")
print(f"\n迁移率：{migrations}/{len(keys)} = {migrations/len(keys)*100:.1f}%")2.3 单调性保证
一致性哈希的关键优势是单调性：添加或删除节点时，只有约 K/N 的数据需要迁移（K 是键的总数，N 是节点总数），而不是朴素哈希的大部分数据。
具体来说： - 添加节点：新节点只接管其逆时针方向到前一个节点之间的数据 - 删除节点：被删除节点的数据转移到其顺时针方向的下一个节点
理论上，添加第 N+1 个节点时，平均迁移率是 1/(N+1)。
2.4 负载不均衡问题
基础的一致性哈希存在严重的负载不均衡问题。假设有 3 个节点：
import matplotlib.pyplot as plt
import numpy as np
# 模拟环形哈希空间
def simulate_basic_consistent_hash():
max_hash = 2**32
nodes = {
"node0": 123456789,
"node1": 987654321,
"node2": 1500000000
}
# 计算每个节点负责的范围
sorted_nodes = sorted(nodes.items(), key=lambda x: x[1])
for i, (name, hash_val) in enumerate(sorted_nodes):
next_i = (i + 1) % len(sorted_nodes)
next_hash = sorted_nodes[next_i][1]
if next_hash > hash_val:
range_size = next_hash - hash_val
else:
range_size = (max_hash - hash_val) + next_hash
percentage = (range_size / max_hash) * 100
print(f"{name}: 负责 {percentage:.1f}% 的哈希空间")
simulate_basic_consistent_hash()由于节点哈希值的随机性，某个节点可能负责 50% 的哈希空间，而另一个节点只负责 10%。这在实际系统中是不可接受的。
三、虚拟节点：解决负载均衡
3.1 虚拟节点机制
虚拟节点（Virtual Nodes）是解决一致性哈希负载不均的标准方案。核心思想是：
- 每个物理节点不是只在环上占一个位置，而是映射为多个虚拟节点
- 每个虚拟节点在环上占据不同的位置
- 虚拟节点数量越多，负载分布越均匀
3.2 带虚拟节点的实现
class ConsistentHashWithVirtualNodes:
def __init__(self, virtual_nodes=150):
self.virtual_nodes = virtual_nodes
self.ring = []
self.ring_dict = {}
self.nodes = set()
def _hash(self, key):
md5 = hashlib.md5(key.encode())
return int(md5.hexdigest()[:8], 16)
def add_node(self, node):
"""添加物理节点，生成多个虚拟节点"""
self.nodes.add(node)
for i in range(self.virtual_nodes):
virtual_key = f"{node}:vnode{i}"
hash_value = self._hash(virtual_key)
self.ring.append(hash_value)
self.ring_dict[hash_value] = node
self.ring.sort()
def remove_node(self, node):
"""移除物理节点及其所有虚拟节点"""
self.nodes.discard(node)
for i in range(self.virtual_nodes):
virtual_key = f"{node}:vnode{i}"
hash_value = self._hash(virtual_key)
if hash_value in self.ring_dict:
self.ring.remove(hash_value)
del self.ring_dict[hash_value]
def get_node(self, key):
if not self.ring:
return None
hash_value = self._hash(key)
index = bisect.bisect_right(self.ring, hash_value)
if index == len(self.ring):
index = 0
return self.ring_dict[self.ring[index]]
# 测试负载分布
def test_load_distribution():
ch = ConsistentHashWithVirtualNodes(virtual_nodes=150)
nodes = ["node0", "node1", "node2", "node3"]
for node in nodes:
ch.add_node(node)
# 生成 10000 个随机键
distribution = {node: 0 for node in nodes}
num_keys = 10000
for i in range(num_keys):
key = f"key:{i}"
node = ch.get_node(key)
distribution[node] += 1
print("虚拟节点数 = 150 时的负载分布：")
for node, count in sorted(distribution.items()):
percentage = (count / num_keys) * 100
print(f"{node}: {count} keys ({percentage:.2f}%)")
# 计算标准差
values = list(distribution.values())
mean = num_keys / len(nodes)
variance = sum((x - mean) ** 2 for x in values) / len(values)
std_dev = variance ** 0.5
print(f"\n标准差：{std_dev:.2f} (理想为 0)")
print(f"变异系数：{(std_dev / mean) * 100:.2f}%")
test_load_distribution()3.3 虚拟节点数量的选择
虚拟节点数量影响：
- 太少：负载仍然不均衡
- 太多：查找开销增加（二分查找的对数复杂度）
实践中的选择： - Cassandra：默认 256 个虚拟节点（可配置） - Riak：默认 64 个虚拟节点 - Voldemort：支持配置虚拟节点，建议 100-200 个
经验法则：150-200 个虚拟节点可以使标准差降到 5% 以内。
3.3.1 虚拟节点调优实践
虚拟节点数量并非越多越好。Cassandra
的演进历程充分说明了这一点：早期版本默认使用 256
个虚拟节点，但在新版本中将推荐值降低到 16 个（通过配置
num_tokens: 16 并搭配
-Dcassandra.allocate_tokens_for_local_replication_factor=3
实现智能 token 分配）。
减少虚拟节点数量的原因：
- 修复开销增大：每个虚拟节点是独立的修复单元（repair unit），256 个 vnode 意味着每次修复操作需要处理 256 个独立的数据范围
- 流式传输时间延长：节点启动（bootstrap）时需要从多个源节点拉取数据，vnode 越多，需要建立的流式连接越多
- 元数据内存消耗：token ring 中每个 vnode 条目约占用 100 字节内存；256 vnodes x 1000 节点 = 256K 条目，约 25MB 内存，虽可接受但随集群规模增长会持续累积
不同集群规模的推荐配置：
| 集群规模 | 节点数量 | 推荐 vnode 数量 | 理由 |
|---|---|---|---|
| 小型集群 | 3-10 节点 | 16-32 | 节点少，少量 vnode 即可实现均衡分布 |
| 中型集群 | 10-100 节点 | 32-64 | 兼顾均衡性与运维复杂度 |
| 大型集群 | 100+ 节点 | 64-128 | 需要更细粒度的负载均衡，但不宜过多 |
对再平衡速度的影响：
vnode 数量直接影响再平衡过程的并行度。更多 vnode 意味着可以建立更多的并行数据流进行迁移，但每个数据流传输的数据量较小；更少的 vnode 意味着更少的并行流，但每个流传输的数据量更大。在网络带宽充足的场景下，较少的 vnode 反而能减少连接建立的开销，提高整体迁移效率。
实践建议：从较少的 vnode 数量开始配置（如 16-32 个），监控集群的负载分布情况。只有在观察到明显的负载不均衡时，才逐步增加 vnode 数量。过多的 vnode 带来的运维复杂度往往超过其在负载均衡方面的边际收益。
3.4 权重虚拟节点
不同物理节点的性能可能不同（CPU、内存、磁盘），可以根据权重分配不同数量的虚拟节点：
class WeightedConsistentHash:
def __init__(self, base_virtual_nodes=100):
self.base_virtual_nodes = base_virtual_nodes
self.ring = []
self.ring_dict = {}
self.node_weights = {}
def add_node(self, node, weight=1.0):
"""添加节点，weight 表示相对权重"""
self.node_weights[node] = weight
num_vnodes = int(self.base_virtual_nodes * weight)
for i in range(num_vnodes):
virtual_key = f"{node}:vnode{i}"
hash_value = self._hash(virtual_key)
self.ring.append(hash_value)
self.ring_dict[hash_value] = node
self.ring.sort()
def _hash(self, key):
md5 = hashlib.md5(key.encode())
return int(md5.hexdigest()[:8], 16)
def get_node(self, key):
if not self.ring:
return None
hash_value = self._hash(key)
index = bisect.bisect_right(self.ring, hash_value)
if index == len(self.ring):
index = 0
return self.ring_dict[self.ring[index]]
# 测试权重
wch = WeightedConsistentHash(base_virtual_nodes=100)
wch.add_node("high_perf_node", weight=2.0) # 高性能节点
wch.add_node("normal_node1", weight=1.0)
wch.add_node("normal_node2", weight=1.0)
wch.add_node("low_perf_node", weight=0.5) # 低性能节点
distribution = {"high_perf_node": 0, "normal_node1": 0,
"normal_node2": 0, "low_perf_node": 0}
for i in range(10000):
key = f"key:{i}"
node = wch.get_node(key)
distribution[node] += 1
print("加权虚拟节点的负载分布：")
for node, count in sorted(distribution.items()):
print(f"{node}: {count} keys ({count/100:.1f}%)")四、Jump Consistent Hash：算法的极致优化
4.1 论文背景
2014 年，Google 的 John Lamping 和 Eric Veach 发表论文《A Fast, Minimal Memory, Consistent Hash Algorithm》，提出了 Jump Consistent Hash。这个算法极其简洁，只有 6 行代码，却实现了：
- O(ln n) 时间复杂度：而不是一致性哈希的 O(log N)（N 是虚拟节点数）
- 零内存开销：不需要维护环形结构
- 完美均衡：负载几乎完全均匀
4.2 算法原理
核心思想基于伪随机数生成器的跳跃：
- 从桶 0 开始（bucket = 0）
- 使用线性同余生成器生成伪随机数
- 根据随机数决定是否”跳跃”到下一个桶
- 重复直到不能再跳（超出桶数量）
// 原始 C++ 实现
int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
int64_t b = -1, j = 0;
while (j < num_buckets) {
b = j;
key = key * 2862933555777941757ULL + 1;
j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
}
return b;
}4.3 Python 实现
def jump_consistent_hash(key, num_buckets):
"""
Jump Consistent Hash 实现
参数:
key: 64 位整数键
num_buckets: 桶（节点）数量
返回:
桶的索引 (0 到 num_buckets-1)
"""
b, j = -1, 0
while j < num_buckets:
b = j
key = ((key * 2862933555777941757) + 1) & 0xFFFFFFFFFFFFFFFF
j = int((b + 1) * (2**31 / ((key >> 33) + 1)))
return int(b)
def string_to_key(s):
"""将字符串转换为 64 位整数"""
import hashlib
h = hashlib.md5(s.encode()).digest()
return int.from_bytes(h[:8], 'little')
# 测试
num_buckets = 10
test_keys = [f"user:{i}" for i in range(1000, 1020)]
print("Jump Consistent Hash 分布：")
for key_str in test_keys:
key = string_to_key(key_str)
bucket = jump_consistent_hash(key, num_buckets)
print(f"{key_str} -> bucket {bucket}")
# 测试负载分布
def test_jump_hash_distribution():
num_buckets = 5
num_keys = 10000
distribution = [0] * num_buckets
for i in range(num_keys):
key = string_to_key(f"key:{i}")
bucket = jump_consistent_hash(key, num_buckets)
distribution[bucket] += 1
print(f"\n负载分布（{num_buckets} 个桶，{num_keys} 个键）：")
for i, count in enumerate(distribution):
print(f"Bucket {i}: {count} ({count/num_keys*100:.2f}%)")
test_jump_hash_distribution()4.4 单调性验证
def test_jump_hash_monotonicity():
"""验证添加桶时的单调性"""
num_keys = 100
keys = [string_to_key(f"key:{i}") for i in range(num_keys)]
# 5 个桶的分布
buckets_5 = [jump_consistent_hash(k, 5) for k in keys]
# 扩容到 6 个桶
buckets_6 = [jump_consistent_hash(k, 6) for k in keys]
# 统计变化
unchanged = sum(1 for i in range(num_keys) if buckets_5[i] == buckets_6[i])
moved_to_new = sum(1 for i in range(num_keys) if buckets_6[i] == 5)
print(f"从 5 桶扩容到 6 桶：")
print(f"保持不变：{unchanged} ({unchanged/num_keys*100:.1f}%)")
print(f"移动到新桶：{moved_to_new} ({moved_to_new/num_keys*100:.1f}%)")
print(f"预期移动到新桶：{100/6:.1f}%")
# 验证只移动到新桶
other_moves = 0
for i in range(num_keys):
if buckets_5[i] != buckets_6[i] and buckets_6[i] != 5:
other_moves += 1
print(f"移动到其他旧桶：{other_moves} (应该为 0)")
test_jump_hash_monotonicity()4.5 局限性
Jump Consistent Hash 的致命缺陷：只能在末尾添加桶，不能删除或插入。
- ✅ 支持：从 N 个桶扩容到 N+1 个桶
- ❌ 不支持：删除第 3 个桶
- ❌ 不支持：在中间插入桶
这使得它只适用于节点只增不减的场景，或者节点编号可以复用的场景（即删除节点时，其编号保留，不分配数据）。
4.6 适用场景
Jump Consistent Hash 适合：
- 缓存分片：Memcached 集群，节点很少移除
- 日志分片：按时间分片，分片数单调增加
- 无状态服务：负载均衡，节点下线时可以用占位符
不适合：
- 有状态存储：需要频繁增删节点，如数据库分片
- 节点异构：无法设置权重
五、Rendezvous Hashing：最高随机权重
5.1 算法思想
Rendezvous Hashing（也称 HRW，Highest Random Weight）由 Thaler 和 Ravishankar 在 1996 年提出。核心思想：
- 对于每个键，计算它与所有节点的组合哈希值
- 选择哈希值最大的节点
- 这样每个键都有一个确定的节点选择
5.2 实现
class RendezvousHash:
def __init__(self):
self.nodes = []
def add_node(self, node):
if node not in self.nodes:
self.nodes.append(node)
def remove_node(self, node):
if node in self.nodes:
self.nodes.remove(node)
def _hash(self, key, node):
"""计算键和节点的组合哈希"""
combined = f"{key}:{node}"
return int(hashlib.md5(combined.encode()).hexdigest(), 16)
def get_node(self, key):
"""选择哈希值最高的节点"""
if not self.nodes:
return None
max_hash = -1
selected_node = None
for node in self.nodes:
h = self._hash(key, node)
if h > max_hash:
max_hash = h
selected_node = node
return selected_node
# 测试
rh = RendezvousHash()
nodes = ["node0", "node1", "node2", "node3"]
for node in nodes:
rh.add_node(node)
keys = [f"user:{i}" for i in range(1001, 1011)]
print("Rendezvous Hash 分布：")
initial = {}
for key in keys:
node = rh.get_node(key)
initial[key] = node
print(f"{key} -> {node}")
# 移除一个节点
print("\n移除 node1 后：")
rh.remove_node("node1")
migrations = 0
for key in keys:
node = rh.get_node(key)
if initial[key] != node:
if initial[key] == "node1":
print(f"{key}: node1 -> {node} (必须迁移)")
else:
print(f"{key}: {initial[key]} -> {node} (不应该迁移！)")
migrations += 1
else:
print(f"{key}: 仍在 {node}")
print(f"\n迁移率：{migrations}/{len(keys)}")5.3 特性分析
优点： - 删除友好：删除节点时，只有该节点的数据需要迁移 - 无需额外结构：不需要环或查找表 - 支持权重：可以通过调整哈希函数实现
缺点： - O(N) 查找：每次查找需要计算所有节点的哈希 - 节点数多时性能差：100 个节点就需要 100 次哈希计算
5.4 优化：缓存和预计算
class OptimizedRendezvousHash:
def __init__(self):
self.nodes = []
self.cache = {}
self.cache_size = 10000
def add_node(self, node):
if node not in self.nodes:
self.nodes.append(node)
self.cache.clear() # 清空缓存
def remove_node(self, node):
if node in self.nodes:
self.nodes.remove(node)
self.cache.clear()
def _hash(self, key, node):
combined = f"{key}:{node}"
return int(hashlib.md5(combined.encode()).hexdigest(), 16)
def get_node(self, key):
# 先查缓存
if key in self.cache:
return self.cache[key]
if not self.nodes:
return None
max_hash = -1
selected_node = None
for node in self.nodes:
h = self._hash(key, node)
if h > max_hash:
max_hash = h
selected_node = node
# 缓存结果
if len(self.cache) < self.cache_size:
self.cache[key] = selected_node
return selected_node六、Maglev Hashing：查表的艺术
6.1 Google Maglev 负载均衡器
Maglev 是 Google 在 2016 年公开的网络负载均衡器（论文《Maglev: A Fast and Reliable Software Network Load Balancer》），其哈希算法专为以下目标设计：
- 快速查找：O(1) 时间，适合高速网络包转发
- 最小化中断：节点变化时尽量少迁移
- 均匀分布：几乎完美的负载均衡
6.2 算法原理
Maglev Hashing 的核心是预构建一个查找表（lookup table）：
- 生成偏好列表：每个节点对表的每个位置有一个偏好顺序
- 填充查找表：轮询每个节点，按偏好顺序填充表中的空位
- 查找：hash(key) % table_size 得到索引，直接查表
class MaglevHash:
def __init__(self, table_size=65537): # 质数
self.table_size = table_size
self.nodes = []
self.lookup_table = None
def _hash(self, key, seed=0):
"""计算哈希值"""
combined = f"{key}:{seed}"
h = hashlib.md5(combined.encode()).digest()
return int.from_bytes(h[:8], 'little')
def _generate_permutation(self, node):
"""为节点生成偏好顺序"""
offset = self._hash(node, 0) % self.table_size
skip = self._hash(node, 1) % (self.table_size - 1) + 1
permutation = []
for j in range(self.table_size):
permutation.append((offset + j * skip) % self.table_size)
return permutation
def build_lookup_table(self):
"""构建查找表"""
if not self.nodes:
self.lookup_table = []
return
n = len(self.nodes)
self.lookup_table = [None] * self.table_size
# 为每个节点生成偏好列表
permutations = {}
for node in self.nodes:
permutations[node] = self._generate_permutation(node)
# 填充查找表
next_indices = {node: 0 for node in self.nodes}
filled = 0
while filled < self.table_size:
for node in self.nodes:
# 获取该节点的下一个偏好位置
idx = next_indices[node]
while idx < self.table_size:
pos = permutations[node][idx]
next_indices[node] = idx + 1
# 如果该位置为空，填充
if self.lookup_table[pos] is None:
self.lookup_table[pos] = node
filled += 1
break
idx += 1
if filled >= self.table_size:
break
def add_node(self, node):
if node not in self.nodes:
self.nodes.append(node)
self.build_lookup_table()
def remove_node(self, node):
if node in self.nodes:
self.nodes.remove(node)
self.build_lookup_table()
def get_node(self, key):
if not self.lookup_table:
return None
hash_value = self._hash(key)
index = hash_value % self.table_size
return self.lookup_table[index]
# 测试
print("Maglev Hash 构建和查找：")
mh = MaglevHash(table_size=1009) # 使用较小的质数测试
nodes = ["backend1", "backend2", "backend3", "backend4"]
for node in nodes:
mh.add_node(node)
print(f"\n查找表大小：{mh.table_size}")
print(f"节点数：{len(mh.nodes)}")
# 测试分布
distribution = {node: 0 for node in nodes}
num_keys = 10000
for i in range(num_keys):
key = f"request:{i}"
node = mh.get_node(key)
distribution[node] += 1
print("\n负载分布：")
for node, count in sorted(distribution.items()):
print(f"{node}: {count} ({count/num_keys*100:.2f}%)")
# 测试中断
print("\n移除 backend2 后：")
initial_mapping = {}
for i in range(100):
key = f"test:{i}"
initial_mapping[key] = mh.get_node(key)
mh.remove_node("backend2")
migrations = 0
for key, old_node in initial_mapping.items():
new_node = mh.get_node(key)
if old_node != new_node:
migrations += 1
print(f"迁移率：{migrations}/100 = {migrations}%")6.3 性能特性
查找性能： - 单次查找：1 次哈希 + 1 次数组访问 = O(1) - 构建开销：O(M × N)，M 是表大小，N 是节点数
负载均衡： - 表大小为质数时，分布非常均匀 - 推荐表大小：65537（2^16 + 1）
中断最小化： - 添加节点：约 1/(N+1) 的数据迁移 - 删除节点：只有该节点的数据迁移到其他节点
6.4 实际应用
Maglev 在 Google 生产环境中的应用：
- 网络负载均衡：每秒数百万包的转发
- GFE（Google Front End）：HTTP 请求分发
- 连接保持：同一客户端的连接路由到同一后端
七、真实系统中的选择
7.1 Apache Cassandra
方案：一致性哈希 + 虚拟节点
# cassandra.yaml 配置
num_tokens: 256 # 虚拟节点数量
partitioner: org.apache.cassandra.dht.Murmur3Partitioner
# Token 范围：[-2^63, 2^63-1]工作原理：
- 每个节点在启动时随机选择 256 个 token（虚拟节点）
- 使用 Murmur3 哈希函数计算键的哈希值
- 通过 token 范围确定数据归属节点
- 复制时按环的顺序选择后续节点
# Cassandra 的分区键哈希
def cassandra_token(partition_key):
"""模拟 Cassandra Murmur3 分区"""
# Murmur3 生成 64 位哈希
import mmh3
return mmh3.hash64(partition_key.encode())[0]
# 例子
key = "user:12345"
token = cassandra_token(key)
print(f"Partition key: {key}")
print(f"Token: {token}")优势： - 自动负载均衡 - 扩容时数据自动重分配 - 支持异构节点（不同节点可设置不同 token 数）
7.2 Riak
方案：一致性哈希环 + 64 个虚拟节点
%% riak.conf
ring_size = 64 %% 环的分区数Riak 的特点：
- 固定分区数：环被预先分为 64 或 128 或 256 个分区
- vnodes：每个物理节点负责多个分区
- 偏好列表：每个分区有一个偏好节点列表
class RiakStyleRing:
def __init__(self, ring_size=64):
self.ring_size = ring_size
self.partitions = list(range(ring_size))
self.partition_to_node = {}
def add_node(self, node, num_partitions):
"""节点声明负责若干分区"""
import random
available = [p for p in self.partitions
if p not in self.partition_to_node]
assigned = random.sample(available,
min(num_partitions, len(available)))
for p in assigned:
self.partition_to_node[p] = node
def get_partition(self, key):
"""获取键对应的分区"""
h = int(hashlib.md5(key.encode()).hexdigest(), 16)
return h % self.ring_size
def get_node(self, key):
partition = self.get_partition(key)
return self.partition_to_node.get(partition)
# 模拟 3 节点的 Riak 环
ring = RiakStyleRing(ring_size=64)
ring.add_node("node1", 21)
ring.add_node("node2", 21)
ring.add_node("node3", 22)
for i in range(10):
key = f"key:{i}"
partition = ring.get_partition(key)
node = ring.get_node(key)
print(f"{key} -> partition {partition} -> {node}")7.3 TiKV（TiDB）
方案：Range 分区为主，但键的路由涉及哈希
TiKV 实际使用范围分区（Range Partition），但为了理解其架构：
- Region：数据按范围分为 Region（默认 96MB）
- Range：每个 Region 负责一个连续的键范围
- 分裂：Region 过大时自动分裂
- 调度：PD（Placement Driver）负责 Region 的调度
虽然不是纯哈希分区，但可以通过哈希前缀实现哈希分区：
-- TiDB 中的哈希分区表
CREATE TABLE users (
id BIGINT,
name VARCHAR(255),
email VARCHAR(255)
) PARTITION BY HASH(id) PARTITIONS 16;内部实现：
def tidb_hash_partition(key, num_partitions):
"""TiDB 的哈希分区函数"""
# 使用 MySQL 兼容的哈希函数
import binascii
h = binascii.crc32(str(key).encode()) & 0xFFFFFFFF
return h % num_partitions
# 测试
for user_id in [100, 101, 102, 103, 104]:
partition = tidb_hash_partition(user_id, 16)
print(f"User {user_id} -> Partition {partition}")7.4 Redis Cluster
方案：哈希槽（Hash Slots）
Redis Cluster 使用 16384 个哈希槽：
def redis_crc16(key):
"""Redis 的 CRC16 实现"""
import binascii
# 简化版，实际使用 CRC16-CCITT
return binascii.crc_hqx(key.encode(), 0)
def redis_hash_slot(key):
"""计算 Redis 键的哈希槽"""
# 处理哈希标签 {tag}
if '{' in key:
start = key.index('{')
end = key.index('}', start)
if end > start + 1:
key = key[start+1:end]
return redis_crc16(key) % 16384
# Redis Cluster 配置
cluster_config = {
"node1": list(range(0, 5461)), # 0-5460
"node2": list(range(5461, 10923)), # 5461-10922
"node3": list(range(10923, 16384)) # 10923-16383
}
def get_redis_node(key):
slot = redis_hash_slot(key)
for node, slots in cluster_config.items():
if slot in slots:
return node, slot
return None, slot
# 测试
keys = ["user:1001", "user:1002", "order:5001", "{user:1001}:profile"]
for key in keys:
node, slot = get_redis_node(key)
print(f"{key} -> slot {slot} -> {node}")特点： - 固定 16384 个槽，便于管理 - 支持哈希标签，确保相关键在同一节点 - 槽可以在节点间迁移
7.5 MySQL Vitess
方案：VSchema + Vindexes（虚拟索引）
Vitess 支持多种分区策略：
{
"sharded": true,
"vindexes": {
"hash": {
"type": "hash"
},
"xxhash": {
"type": "xxhash"
}
},
"tables": {
"users": {
"column_vindexes": [
{
"column": "user_id",
"name": "hash"
}
]
}
}
}支持的 Vindex 类型： - hash：简单哈希 - xxhash：xxHash 算法 - consistent_lookup：一致性查找 - region_json：基于地理位置
7.6 Amazon DynamoDB
方案：一致性哈希 + 虚拟节点 + 自动分区管理
DynamoDB 采用一致性哈希与虚拟节点相结合的方式进行分区管理。每条数据的分区键（Partition Key）经过哈希函数计算后，被映射到对应的分区上。
分区容量限制：
每个分区存在三重上限约束：
- 读取容量：最多 3000 RCU（Read Capacity Units）
- 写入容量：最多 1000 WCU（Write Capacity Units）
- 存储容量：最多 10GB 数据
当任一维度超过限制时，DynamoDB 会自动执行分区拆分（partition split），将数据重新分布到新的分区中。
热分区问题的解决方案：
- 自适应容量（Adaptive Capacity）：DynamoDB 会自动检测热分区，并将未被充分利用的分区容量重新分配给热分区，确保热点数据不会因为分区级别的容量限制而被限流
- 突发容量（Burst Capacity）：每个分区会保留最近 300 秒内未使用的容量作为突发额度，允许分区在短时间内超过其预配置的容量上限
全局表与冲突解决：
DynamoDB 全局表（Global Tables）采用 last-writer-wins 策略进行跨区域冲突解决，以最后写入的时间戳作为仲裁依据。
分区键选择对数据分布的影响：
import hashlib
def dynamodb_partition_simulation(items, num_partitions=10):
"""模拟 DynamoDB 分区键选择对数据分布的影响"""
partition_counts = {}
for item in items:
partition_key = item["pk"]
hash_value = int(hashlib.md5(partition_key.encode()).hexdigest(), 16)
partition_id = hash_value % num_partitions
partition_counts[partition_id] = partition_counts.get(partition_id, 0) + 1
return partition_counts
# 不良分区键：使用日期作为分区键，导致数据集中在少数分区
bad_items = [{"pk": "2024-01-15", "data": f"record_{i}"} for i in range(10000)]
bad_distribution = dynamodb_partition_simulation(bad_items)
print("不良分区键（日期）- 所有数据集中在同一分区：")
print(f" 分区分布: {bad_distribution}")
# 良好分区键：使用用户 ID 作为分区键，数据均匀分布
good_items = [{"pk": f"user_{i}", "data": f"record_{i}"} for i in range(10000)]
good_distribution = dynamodb_partition_simulation(good_items)
print("\n良好分区键（用户ID）- 数据均匀分布：")
for pid in sorted(good_distribution.keys()):
count = good_distribution[pid]
print(f" 分区 {pid}: {count} 条记录 ({count/100:.1f}%)")这个示例清晰地展示了分区键选择的重要性：使用日期作为分区键会导致同一天的所有数据被映射到同一个分区，形成严重的热点；而使用用户 ID 等高基数字段作为分区键则能实现较为均匀的数据分布。
八、方案对比与选择
8.1 算法对比表
| 算法 | 查找时间 | 内存开销 | 负载均衡 | 单调性 | 支持删除 | 支持权重 |
|---|---|---|---|---|---|---|
| 朴素哈希 | O(1) | O(1) | 完美 | ❌ | ✅ | ✅ |
| 一致性哈希 | O(log N) | O(N) | 差 | ✅ | ✅ | ❌ |
| 一致性哈希+虚拟节点 | O(log VN) | O(V×N) | 好 | ✅ | ✅ | ✅ |
| Jump Hash | O(ln N) | O(1) | 完美 | ✅ | ❌ | ❌ |
| Rendezvous | O(N) | O(N) | 完美 | ✅ | ✅ | ✅ |
| Maglev | O(1) | O(M) | 完美 | ✅ | ✅ | ✅ |
注：N = 节点数，V = 虚拟节点数，M = 查找表大小
8.2 迁移成本对比
import random
def measure_migration_rate(hash_func_before, hash_func_after, num_keys=10000):
"""测量迁移率"""
migrations = 0
for i in range(num_keys):
key = f"key:{i}"
if hash_func_before(key) != hash_func_after(key):
migrations += 1
return migrations / num_keys
# 模拟不同算法的迁移率
def test_all_algorithms():
num_keys = 10000
# 1. 朴素哈希：3 -> 4 节点
migrations_naive = 0
for i in range(num_keys):
h = hash(f"key:{i}")
if h % 3 != h % 4:
migrations_naive += 1
print(f"朴素哈希 (3->4): {migrations_naive/num_keys*100:.1f}%")
# 2. 一致性哈希（虚拟节点）
ch_before = ConsistentHashWithVirtualNodes(150)
for i in range(3):
ch_before.add_node(f"node{i}")
ch_after = ConsistentHashWithVirtualNodes(150)
for i in range(4):
ch_after.add_node(f"node{i}")
migrations_ch = 0
for i in range(num_keys):
key = f"key:{i}"
if ch_before.get_node(key) != ch_after.get_node(key):
migrations_ch += 1
print(f"一致性哈希+虚拟节点 (3->4): {migrations_ch/num_keys*100:.1f}%")
# 3. Jump Hash
migrations_jump = 0
for i in range(num_keys):
key_int = int(hashlib.md5(f"key:{i}".encode()).hexdigest(), 16)
if jump_consistent_hash(key_int, 3) != jump_consistent_hash(key_int, 4):
migrations_jump += 1
print(f"Jump Hash (3->4): {migrations_jump/num_keys*100:.1f}%")
# 4. Maglev
mh_before = MaglevHash(table_size=1009)
for i in range(3):
mh_before.add_node(f"node{i}")
mh_after = MaglevHash(table_size=1009)
for i in range(4):
mh_after.add_node(f"node{i}")
migrations_maglev = 0
for i in range(num_keys):
key = f"key:{i}"
if mh_before.get_node(key) != mh_after.get_node(key):
migrations_maglev += 1
print(f"Maglev (3->4): {migrations_maglev/num_keys*100:.1f}%")
print("迁移率对比（从 3 节点扩容到 4 节点）：")
test_all_algorithms()8.2.1 迁移成本的数学分析
理解不同哈希算法的迁移成本，需要从数学角度进行严谨分析。
朴素取模哈希的迁移代价：
当节点数从 N 变为 M 时，需要迁移的键的比例约为
1 - gcd(N, M) / max(N, M)。在最常见的逐步扩容场景中（例如从
N 扩展到 N+1），由于
gcd(N, N+1) = 1，迁移比例为
1 - 1/(N+1) = N/(N+1)，即接近
(N-1)/N
的数据需要迁移。节点越多，迁移比例越趋近 100%。
一致性哈希的迁移代价：
向 N 个节点的集群中添加 1 个新节点时，约有
K/N 个键需要迁移（K
为总键数）。这已经接近理论最优值：新节点应承担
1/(N+1)
的数据量，而实际迁移量略高于此值。这种迁移特性是一致性哈希最核心的优势。
Jump Hash 的迁移代价：
添加第 N+1 个节点时，恰好有 K/(N+1)
个键需要迁移，这是数学上的理论最优值。每个键以
1/(N+1)
的概率被分配到新节点，其余键保持不变。
最优迁移量公式：
\[\text{最优迁移量} = \frac{K}{N+1}\]
其中 K 为总键数，N 为当前节点数。
具体示例：10 亿个键，100 个节点，添加 1 个新节点
| 算法 | 迁移键数 | 迁移比例 | 说明 |
|---|---|---|---|
| 朴素取模哈希 | 约 9.9 亿 | 约 99% | 几乎所有数据需要重新分布 |
| 一致性哈希 | 约 1000 万 | 约 1% | 仅新节点接管的范围内的数据迁移 |
| Jump Hash | 约 990 万 | 约 0.99% | 理论最优，精确的 K/(N+1) |
迁移带宽估算：假设每个键值对平均大小为 1KB，则 1000 万个键的迁移量约为 10GB 的网络传输。在千兆网络环境下，这意味着约 80 秒的纯传输时间；在万兆网络下仅需约 8 秒。而朴素取模哈希的 9.9 亿键迁移则意味着约 990GB 的网络传输，即使在万兆网络下也需要约 800 秒，期间服务质量会严重下降。
flowchart TD
A[添加第 N+1 个节点] --> B{使用哪种哈希算法?}
B -->|取模哈希| C["迁移量: K * (N-1)/N"]
B -->|一致性哈希| D["迁移量: K / (N+1)"]
B -->|Jump Hash| E["迁移量: K / (N+1)"]
C --> F["100 节点加 1 个: 约 99% 数据迁移"]
D --> G["100 节点加 1 个: 约 1% 数据迁移"]
E --> H["100 节点加 1 个: 约 0.99% 数据迁移"]
F --> I[服务中断风险高]
G --> J[平滑扩容]
H --> K[最优迁移量]上述对比图清晰地展示了一致性哈希与 Jump Hash 在动态扩容场景中的决定性优势。朴素取模哈希在扩容时会引发灾难性的数据迁移，导致集群在迁移期间面临严重的服务中断风险。而一致性哈希和 Jump Hash 均能将迁移量控制在理论最优附近，实现真正意义上的平滑扩容。
8.3 性能基准测试
import time
def benchmark_lookup(hash_obj, keys, name):
"""测试查找性能"""
start = time.time()
for key in keys:
_ = hash_obj.get_node(key)
elapsed = time.time() - start
ops_per_sec = len(keys) / elapsed
print(f"{name}: {ops_per_sec:.0f} ops/sec ({elapsed*1000:.2f} ms)")
# 准备测试数据
num_keys = 100000
test_keys = [f"key:{i}" for i in range(num_keys)]
print("查找性能基准测试（100,000 次查找）：")
# 一致性哈希
ch = ConsistentHashWithVirtualNodes(150)
for i in range(10):
ch.add_node(f"node{i}")
benchmark_lookup(ch, test_keys, "一致性哈希+虚拟节点")
# Rendezvous
rh = RendezvousHash()
for i in range(10):
rh.add_node(f"node{i}")
benchmark_lookup(rh, test_keys, "Rendezvous Hash ")
# Maglev
mh = MaglevHash(table_size=65537)
for i in range(10):
mh.add_node(f"node{i}")
benchmark_lookup(mh, test_keys, "Maglev Hash ")8.4 选择指南
选择一致性哈希 + 虚拟节点： - 节点频繁增删 - 需要支持异构节点（权重） - 可以接受 O(log N) 查找 - 如：Cassandra、Riak、DynamoDB
选择 Jump Hash： - 节点只增不减 - 追求极致的性能和内存效率 - 负载均衡要求高 - 如：Google 内部缓存系统
选择 Rendezvous Hash： - 节点数量较少（< 100） - 需要精确的删除行为 - 可以接受 O(N) 查找 - 如：Ceph（用于 PG 到 OSD 映射）
选择 Maglev Hash： - 对查找性能要求极高（网络数据包转发） - 节点数量适中（< 1000） - 可以接受大内存（MB 级查找表） - 如：Google Maglev 负载均衡器、Katran
选择哈希槽（Hash Slots）： - 需要迁移控制（手动调度） - 支持哈希标签（相关键聚集） - 固定槽数量，动态分配到节点 - 如：Redis Cluster
flowchart TD
START[选择哈希分区算法] --> Q1{是否需要删除节点?}
Q1 -->|是| Q2{节点数量级?}
Q1 -->|否| Q3{是否只追加节点?}
Q2 -->|少于100| R1[Rendezvous Hash]
Q2 -->|100以上| Q4{查找延迟要求?}
Q4 -->|微秒级| R2[Maglev Hash]
Q4 -->|毫秒级可接受| R3[一致性哈希 + 虚拟节点]
Q3 -->|是| R4[Jump Hash]
Q3 -->|否| R3上述决策树基于实际运维中最关键的操作需求来引导算法选择。核心判断维度在于节点是否需要动态增删以及系统对查找性能的要求。对于只追加节点的场景，Jump Hash 提供了最优的性能和均衡性；对于需要灵活增删节点的场景，则需根据集群规模和延迟要求在 Rendezvous Hash、Maglev Hash 和一致性哈希之间做出权衡。
九、代码示例：完整实现
9.1 生产级一致性哈希实现
import hashlib
import bisect
from typing import List, Optional, Dict, Set
class ProductionConsistentHash:
"""生产级一致性哈希实现"""
def __init__(self,
virtual_nodes: int = 150,
hash_func: str = 'md5'):
"""
初始化一致性哈希
Args:
virtual_nodes: 每个物理节点的虚拟节点数
hash_func: 哈希函数类型 ('md5', 'sha1', 'sha256')
"""
self.virtual_nodes = virtual_nodes
self.hash_func = hash_func
self.ring: List[int] = []
self.ring_dict: Dict[int, str] = {}
self.nodes: Set[str] = set()
self.node_weights: Dict[str, float] = {}
def _hash(self, key: str) -> int:
"""计算哈希值"""
if self.hash_func == 'md5':
h = hashlib.md5(key.encode())
elif self.hash_func == 'sha1':
h = hashlib.sha1(key.encode())
elif self.hash_func == 'sha256':
h = hashlib.sha256(key.encode())
else:
raise ValueError(f"Unsupported hash function: {self.hash_func}")
return int(h.hexdigest()[:16], 16)
def add_node(self, node: str, weight: float = 1.0):
"""
添加节点
Args:
node: 节点标识
weight: 节点权重（相对容量）
"""
if node in self.nodes:
return
self.nodes.add(node)
self.node_weights[node] = weight
# 根据权重计算虚拟节点数
num_vnodes = int(self.virtual_nodes * weight)
for i in range(num_vnodes):
virtual_key = f"{node}:vnode{i}"
hash_value = self._hash(virtual_key)
# 处理哈希冲突（虽然极其罕见）
while hash_value in self.ring_dict:
virtual_key = f"{virtual_key}:conflict"
hash_value = self._hash(virtual_key)
# 使用二分插入保持有序
bisect.insort(self.ring, hash_value)
self.ring_dict[hash_value] = node
def remove_node(self, node: str):
"""移除节点"""
if node not in self.nodes:
return
self.nodes.discard(node)
weight = self.node_weights.pop(node, 1.0)
num_vnodes = int(self.virtual_nodes * weight)
for i in range(num_vnodes):
virtual_key = f"{node}:vnode{i}"
hash_value = self._hash(virtual_key)
# 移除可能经过冲突处理的虚拟节点
while hash_value in self.ring_dict and self.ring_dict[hash_value] == node:
self.ring.remove(hash_value)
del self.ring_dict[hash_value]
virtual_key = f"{virtual_key}:conflict"
hash_value = self._hash(virtual_key)
def get_node(self, key: str) -> Optional[str]:
"""获取键对应的节点"""
if not self.ring:
return None
hash_value = self._hash(key)
index = bisect.bisect_right(self.ring, hash_value)
if index == len(self.ring):
index = 0
return self.ring_dict[self.ring[index]]
def get_nodes(self, key: str, count: int) -> List[str]:
"""
获取键对应的多个节点（用于副本）
Args:
key: 数据键
count: 需要的节点数量
Returns:
节点列表，按顺时针顺序
"""
if not self.ring or count <= 0:
return []
hash_value = self._hash(key)
index = bisect.bisect_right(self.ring, hash_value)
if index == len(self.ring):
index = 0
result = []
seen = set()
# 顺时针遍历，收集不同的物理节点
for _ in range(len(self.ring)):
node = self.ring_dict[self.ring[index]]
if node not in seen:
result.append(node)
seen.add(node)
if len(result) >= count:
break
index = (index + 1) % len(self.ring)
return result
def get_distribution(self) -> Dict[str, float]:
"""获取节点的负载分布（理论值）"""
if not self.ring:
return {}
distribution = {node: 0 for node in self.nodes}
total_space = 2 ** 64 # 假设哈希空间是 64 位
for i, hash_value in enumerate(self.ring):
# 计算该虚拟节点负责的哈希空间
if i == 0:
space = (self.ring[0] + (total_space - self.ring[-1]))
else:
space = hash_value - self.ring[i-1]
node = self.ring_dict[hash_value]
distribution[node] += space
# 转换为百分比
for node in distribution:
distribution[node] = (distribution[node] / total_space) * 100
return distribution
# 使用示例
if __name__ == "__main__":
# 创建一致性哈希环
ch = ProductionConsistentHash(virtual_nodes=150)
# 添加节点（包括异构节点）
ch.add_node("high-perf-1", weight=2.0) # 高性能节点
ch.add_node("standard-1", weight=1.0)
ch.add_node("standard-2", weight=1.0)
ch.add_node("low-perf-1", weight=0.5) # 低性能节点
# 查询分布
print("节点负载分布（理论）：")
dist = ch.get_distribution()
for node, percentage in sorted(dist.items()):
print(f"{node}: {percentage:.2f}%")
# 数据路由
print("\n数据路由示例：")
for i in range(10):
key = f"data:item:{i}"
primary = ch.get_node(key)
replicas = ch.get_nodes(key, 3)
print(f"{key} -> primary: {primary}, replicas: {replicas}")
# 节点变更
print("\n移除 standard-2 节点...")
ch.remove_node("standard-2")
print("新的节点负载分布：")
dist = ch.get_distribution()
for node, percentage in sorted(dist.items()):
print(f"{node}: {percentage:.2f}%")9.2 Jump Hash Go 实现
package jumphash
// JumpHash implements the jump consistent hash algorithm.
// It provides a fast, minimal memory consistent hash.
func JumpHash(key uint64, numBuckets int32) int32 {
var b int64 = -1
var j int64 = 0
for j < int64(numBuckets) {
b = j
key = key*2862933555777941757 + 1
j = int64(float64(b+1) * (float64(int64(1)<<31) / float64((key>>33)+1)))
}
return int32(b)
}
// Example usage
func main() {
import (
"fmt"
"hash/fnv"
)
// Hash a string to get uint64 key
h := fnv.New64a()
h.Write([]byte("user:12345"))
key := h.Sum64()
// Get bucket
numBuckets := int32(10)
bucket := JumpHash(key, numBuckets)
fmt.Printf("Key: user:12345, Bucket: %d\n", bucket)
}十、总结与展望
10.1 核心要点回顾
- 朴素哈希：简单但扩容成本高，不适合动态环境
- 一致性哈希：通过环形结构实现单调性，虚拟节点解决负载均衡
- Jump Hash：极致优化，但只支持追加节点
- Rendezvous Hash：删除友好，但查找是 O(N)
- Maglev Hash：O(1) 查找，适合高性能场景
- 真实系统：根据场景选择，没有银弹
10.2 选择决策树
是否需要频繁删除节点？
├─ 是 → 节点数量多吗（> 100）？
│ ├─ 是 → Maglev Hash 或一致性哈希
│ └─ 否 → Rendezvous Hash
└─ 否 → 是否只追加节点？
├─ 是 → Jump Hash（最优）
└─ 否 → 一致性哈希 + 虚拟节点10.3 未来方向
研究前沿： - 自适应虚拟节点：根据负载动态调整虚拟节点数量 - NUMA 感知：考虑硬件拓扑的哈希分区 - ML 驱动：使用机器学习预测热点，动态调整分区
工程实践： - 混合策略：粗粒度范围分区 + 细粒度哈希分区 - 迁移优化：增量迁移、双写策略、迁移限流 - 监控可观测：分区热度、倾斜度、迁移进度
哈希分区是分布式系统的基础技术之一，理解其原理和权衡对于设计高性能、高可用的分布式系统至关重要。下一篇文章我们将探讨范围分区（Range Partition），它与哈希分区互补，各有优劣。
参考文献
Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., & Lewin, D. (1997). Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. ACM Symposium on Theory of Computing.
Lamping, J., & Veach, E. (2014). A Fast, Minimal Memory, Consistent Hash Algorithm. arXiv:1406.2294.
Thaler, D., & Ravishankar, C. (1996). Using Name-Based Mappings to Increase Hit Rates. IEEE/ACM Transactions on Networking.
Eisenbud, D. E., Yi, C., Contavalli, C., Smith, C., Kononov, R., Mann-Hielscher, E., … & Vahdat, A. (2016). Maglev: A Fast and Reliable Software Network Load Balancer. NSDI.
Lakshman, A., & Malik, P. (2010). Cassandra: A Decentralized Structured Storage System. ACM SIGOPS Operating Systems Review.
DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., … & Vogels, W. (2007). Dynamo: Amazon’s Highly Available Key-value Store. ACM SIGOPS Operating Systems Review.
Weil, S. A., Brandt, S. A., Miller, E. L., Long, D. D., & Maltzahn, C. (2006). Ceph: A Scalable, High-Performance Distributed File System. OSDI.