本项目实现了多种一致性哈希算法，并对它们进行了全面的测试和对比分析。
- 直接哈希取模 (Mod Hash)
- 哈希环 (Hash Ring)
- 跳跃一致性哈希 (Jump Consistent Hash)
- Maglev哈希 (Maglev Consistent Hash)
- Rendezvous哈希 (Rendezvous Consistent Hash)
- AnchorHash
- DxHash
- Multi-Probe一致性哈希 (Multi-Probe Consistent Hash)
测试结果含义解释
分布均匀性测试衡量的是当大量键被分配到固定数量的节点时，每个节点被分配到的键数量是否接近平均值。我们使用标准差来衡量分布均匀性：
- 标准差越小：表示各节点被分配到的键数量越接近平均值，分布越均匀
- 标准差越大：表示某些节点被分配到的键数量远高于或低于平均值，分布不均匀
例如，在100个节点、100,000个键的测试中，平均每个节点应该分配到1000个键：
- 跳跃一致性哈希的标准差为25.34，表示大部分节点分配到的键数量在975到1025之间
- AnchorHash的标准差为8954.69，表示节点间的分配极不均匀
值得注意的是，Multi-Probe一致性哈希随着探针数量从5增加到21，分布均匀性显著改善（标准差从362.18降到144.83）。
查询性能测试衡量的是算法处理单个键查询的速度：
- 时间越短：表示算法查询速度越快，性能越好
- 时间越长：表示算法查询速度越慢，性能越差
例如，在1000个节点、100,000个键的测试中：
- Maglev哈希处理100,000次查询仅需12.42毫秒
- Multi-Probe一致性哈希(k=21)处理同样数量的查询需要超过4分钟
随着Multi-Probe一致性哈希的探针数量从5增加到21，查询时间也从1分钟增加到4分钟以上，这是由于需要计算更多的哈希值。
重映射测试衡量的是当系统中增加新节点时，有多少比例的键需要重新分配到不同的节点：
- 重映射比例越低：表示系统扩展时对现有服务的影响越小
- 重映射比例越高：表示系统扩展时对现有服务的影响越大
例如，在1000个初始节点新增10个节点的测试中：
- AnchorHash只有0.47%的键需要重映射
- 直接哈希取模几乎所有的键(98.97%)都需要重映射
Multi-Probe一致性哈希随着探针数量增加，重映射比例略有改善（从1.00%降到0.99%）。
基准测试各项数据含义解释
基准测试是Go语言中用于测量代码性能的标准方法。以下是对各项数据的详细解释：
格式：数字（例如：10207114）
- 表示在测试期间执行的操作次数
- 数字越大表示算法执行速度越快
- 例如：BenchmarkModHash-8执行了10,207,114次操作
格式：数字 ns/op（例如：112.8 ns/op）
- 表示每个操作的平均执行时间，单位为纳秒（nanoseconds）
- 数字越小表示算法执行速度越快
- 例如：ModHash每个操作平均耗时112.8纳秒
格式：数字 B/op（例如：15 B/op）
- 表示每个操作平均分配的内存量，单位为字节（Bytes）
- 数字越小表示内存效率越高
- 例如：MaglevHash每个操作平均分配15字节内存
格式：数字 allocs/op（例如：1 allocs/op）
- 表示每个操作平均进行的内存分配次数
- 数字越小表示内存分配效率越高
- 例如：MaglevHash每个操作平均进行1次内存分配
格式：BenchmarkName-数字（例如：BenchmarkModHash-8）
- 表示测试运行时使用的并发数（GOMAXPROCS）
- 通常与CPU核心数相关
| 算法 | 标准差 | 说明 |
|---|---|---|
| 跳跃一致性哈希 | 25.34 | 优秀的分布均匀性 |
| 直接哈希取模 | 29.18 | 优秀的分布均匀性 |
| Rendezvous哈希 | 32.13 | 优秀的分布均匀性 |
| Maglev哈希(65537表长) | 35.74 | 优秀的分布均匀性 |
| Maglev哈希(2039表长) | 39.55 | 优秀的分布均匀性 |
| 哈希环(160个虚拟节点) | 83.59 | 良好的分布均匀性 |
| 哈希环(40个虚拟节点) | 161.68 | 较差的分布均匀性 |
| Multi-Probe(k=21) | 144.83 | 通过增加探针数量改善分布 |
| Multi-Probe(k=5) | 362.18 | 分布均匀性较差 |
| DxHash | 317.53 | 分布均匀性较差 |
| AnchorHash(2000长度) | 8964.89 | 分布极不均匀 |
| 算法 | 耗时 | 说明 | 服务器测试耗时 |
|---|---|---|---|
| 直接哈希取模 | 10.644ms | 最快的查询速度 | 19.706591ms |
| Maglev哈希(2039表长) | 12.074ms | 快速查询 | 22.974077ms |
| Maglev哈希(65537表长) | 12.459ms | 快速查询 | 24.88155ms |
| 跳跃一致性哈希 | 17.629ms | 快速查询 | 31.788193ms |
| 哈希环(40个虚拟节点) | 19.617ms | 中等查询速度 | 36.433776ms |
| 哈希环(160个虚拟节点) | 23.178ms | 中等查询速度 | 42.116708ms |
| AnchorHash(2000长度) | 64.653ms | 中等查询速度 | 151.905067ms |
| DxHash | 36.642ms | 中等查询速度 | 70.662662ms |
| Rendezvous哈希 | 12.450s | 查询速度较慢 | 20.63148257s |
| Multi-Probe(k=5) | 13.756s | 查询速度较慢 | 25.063274667s |
| Multi-Probe(k=21) | 16.820s | 查询速度最慢 | 34.097989474s |
| 算法 | 重映射键数 | 重映射比例 | 添加节点耗时 | 服务器添加节点耗时 | 说明 |
|---|---|---|---|---|---|
| 直接哈希取模 | 98971 | 98.97% | 18.167µs | 1.768µs | 几乎全部需要重映射 |
| AnchorHash(2000长度) | 717 | 0.72% | 14.291µs | 9.559µs | 最小化重映射 |
| 跳跃一致性哈希 | 969 | 0.97% | 2.75µs | 1.914µs | 最小化重映射 |
| Rendezvous哈希 | 977 | 0.98% | 1.610ms | 9.375µs | 最小化重映射 |
| Multi-Probe(k=21) | 989 | 0.99% | 8.875µs | 1.868µs | 最小化重映射 |
| Multi-Probe(k=5) | 1003 | 1.00% | 8.666µs | 1.986µs | 最小化重映射 |
| DxHash | 1297 | 1.30% | 11.541µs | 4.67µs | 较少重映射 |
| 哈希环(40个虚拟节点) | 953 | 0.95% | 45.486ms | 86.825183ms | 最小化重映射 |
| 哈希环(160个虚拟节点) | 1078 | 1.08% | 193.207ms | 389.603399ms | 较少重映射 |
| Maglev哈希(2039表长) | 3504 | 3.50% | 3.261ms | 5.424627ms | 中等重映射 |
| Maglev哈希(65537表长) | 3418 | 3.42% | 30.797ms | 51.864982ms | 中等重映射 |
| 算法 | 平均耗时 | 内存分配 (内存分配次数) | 说明 |
|---|---|---|---|
| Maglev哈希(2039表长) | 123.7 ns/op | 15 B/op (1 allocs/op) | 最优 |
| Maglev哈希(65537表长) | 134.6 ns/op | 15 B/op (1 allocs/op) | 优秀 |
| 跳跃一致性哈希 | 193.8 ns/op | 0 B/op (0 allocs/op) | 优秀 |
| 哈希环(40个虚拟节点) | 233.5 ns/op | 0 B/op (0 allocs/op) | 良好 |
| 哈希环(160个虚拟节点) | 227.3 ns/op | 0 B/op (0 allocs/op) | 良好 |
| AnchorHash(2000长度) | 743.5 ns/op | 23 B/op (1 allocs/op) | 良好 |
| DxHash | 372.0 ns/op | 43 B/op (2 allocs/op) | 一般 |
| 直接哈希取模 | 114.4 ns/op | 0 B/op (0 allocs/op) | 优秀 |
| Rendezvous哈希 | 111451 ns/op | 0 B/op (0 allocs/op) | 很差 |
| Multi-Probe CH(k=5) | 126842 ns/op | 23467 B/op (1006 allocs/op) | 极差 |
| Multi-Probe CH(k=21) | 160526 ns/op | 23705 B/op (1022 allocs/op) | 极差 |
- 优点：
- 实现简单
- 查询性能好（O(1)）
- 内存占用小
- 缺点：
- 添加节点时重映射比例极高（98.97%）
- 分布均匀性一般
- 适用场景：节点数量固定或变化很少的场景
- 优点：
- 实现简单，概念清晰
- 通过虚拟节点可调节分布均匀性
- 缺点：
- 查询性能一般（O(log N)）
- 分布均匀性一般
- 适用场景：对性能要求不高，实现简单优先的场景
- 优点：
- 内存占用极小，无需存储额外数据结构
- 查询性能好
- 分布均匀性最好
- 添加节点时重映射最少
- 缺点：
- 只能在尾部增删节点
- 适用场景：节点变化较少，且主要在尾部操作的场景
- 优点：
- 查询性能最好（O(1)）
- 分布均匀性良好
- 缺点：
- 需要预先计算查找表，内存占用大
- 添加节点时重映射比例较高
- 表重建耗时较长
- 适用场景：查询频率高，对查询性能要求极高的场景
- 优点：
- 分布均匀性好
- 可以在任意位置增删节点
- 添加节点时重映射较少
- 缺点：
- 查询性能最差（O(N)）
- 适用场景：节点数量不多，对分布均匀性要求高，查询频率不高的场景
- 优点：
- 添加节点时重映射最少（0.72%）
- 删除节点只影响直接映射到该节点的key
- 缺点：
- 分布均匀性很差（标准差8032.47）
- 查询性能一般
- 实现复杂度高
- 适用场景：对重映射要求极高的场景，可以接受分布不均匀的情况
- 优点：
- 添加节点时重映射较少（1.30%）
- 支持动态扩容
- 缺点：
- 分布均匀性较差（标准差317.53）
- 查询性能一般
- 实现复杂度较高
- 适用场景：需要动态扩容且对重映射有一定要求的场景
- 优点：
- 可通过调整探针数量平衡分布均匀性和重映射
- 添加节点时重映射较少
- 缺点：
- 查询性能极差
- 内存占用大
- 随着探针数量增加，性能显著下降
- 适用场景：
- 对分布均匀性和重映射要求高，但查询频率不高的场景
- k=5适用于一般需求，k=21适用于对分布均匀性要求极高的场景
| 算法 | 查询性能 | 分布均匀性 | 重映射比例 | 内存占用 |
|---|---|---|---|---|
| 直接哈希取模 | ⭐⭐⭐⭐⭐ | ⭐⭐⭐ | ⭐ | ⭐⭐⭐⭐⭐ |
| 跳跃一致性哈希 | ⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ |
| Maglev哈希 | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐ | ⭐⭐⭐ | ⭐⭐ |
| Rendezvous哈希 | ⭐ | ⭐⭐⭐⭐ | ⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ |
| 哈希环 | ⭐⭐⭐ | ⭐⭐ | ⭐⭐⭐ | ⭐⭐⭐ |
| AnchorHash | ⭐⭐⭐ | ⭐ | ⭐⭐⭐⭐⭐ | ⭐⭐⭐ |
| DxHash | ⭐⭐⭐ | ⭐⭐ | ⭐⭐⭐ | ⭐⭐⭐ |
| Multi-Probe CH(k=5) | ⭐⭐ | ⭐⭐ | ⭐⭐⭐ | ⭐⭐ |
| Multi-Probe CH(k=21) | ⭐ | ⭐⭐⭐ | ⭐⭐⭐ | ⭐ |
每种一致性哈希算法都有其特点和适用场景:
- AnchorHash: 在最小化重映射方面表现出色，但分布均匀性极差，适用于对重映射极其敏感但对分布均匀性要求不高的场景
- 跳跃一致性哈希: 在分布均匀性和重映射控制方面表现优秀，查询性能良好，是一种非常均衡的算法
- Maglev哈希: 在查询性能和分布均匀性之间取得了很好的平衡，是大多数场景下的优秀选择
- 哈希环: 实现简单，通过调整虚拟节点数量可以平衡性能和均匀性，适合对算法复杂度有要求的场景
- Rendezvous哈希: 分布均匀性优秀，但查询性能较差，适用于对查询频率要求不高的场景
- 直接哈希取模: 查询性能最佳，但节点变化时需要重映射所有键，适用于节点数量固定的场景
本地环境
- CPU: Apple M3
- OS: macOS
- Go版本: 1.22+
服务器环境
- CPU: Intel(R) Xeon(R) Platinum 8352Y CPU @ 2.20GHz
- OS: CentOS Linux release 8.2.2004 (Core)
# 运行演示程序
go run cmd/main.go
# 运行功能测试
go test ./tests/
# 运行基准测试
go test -bench=. ./tests/