The Problem of Uneven Distribution in Consistent Hashing
{collapse}
{collapse-item label="一、背景" open}
1.线上出现连接器server多个IP一致性哈希到了同一个连接器client id上，导致请求都代理到了一个连接器client上。
一致性哈希算法实现的https://github.com/stathat/consistent 针对这个库做一些优化
{/collapse-item}
{collapse-item label="二、优化方案" open}
1.增加哈希环上的虚拟节点个数
每个新增节点对应虚拟节点从20依次增加
| 虚拟节点个数 | 连接器实例uuid个数 | 哈希的ip个数 | 方差 | ip哈希总耗时 |
|---|---|---|---|---|
| 20 | 100 | 10000 | 1493.7 | 2ms |
| 100 | 100 | 10000 | 1018.96 | 2ms |
| 200 | 100 | 10000 | 727.86 | 3ms |
| 300 | 100 | 10000 | 515.46 | 3ms |
| 500 | 100 | 10000 | 250.52 | 4ms |
2.修改生成虚拟节点哈希时的字符串
| 生成哈希字符串 | 连接器实例uuid个数 | 哈希的ip个数 | 方差 |
|---|---|---|---|
| 连接器实例id+虚拟节点序号 | 100 | 10000 | 1692 |
| 连接器实例id+虚拟节点序号+1-100随机数 | 100 | 10000 | 588.74 |
| 连接器实例id+虚拟节点序号+1-1000随机数 | 100 | 10000 | 517.12 |
| 连接器实例id+虚拟节点序号+时间戳 | 100 | 10000 | 706.74 |
3.同时新增虚拟节点和修改哈希的字符串
| 虚拟节点个数 | 生成哈希字符串 | 连接器实例uuid个数 | 哈希ip个数 | 方差 | 公网ip哈希总耗时 |
|---|---|---|---|---|---|
| 20 | 连接器实例id+虚拟节点序号 | 100 | 10000 | 1521.8 | 2ms |
| 50 | 连接器实例id+虚拟节点序号+1-1000随机数 | 100 | 10000 | 328.1 | 2ms |
| 100 | 连接器实例id+虚拟节点序号+1-1000随机数 | 100 | 10000 | 209.1 | 2ms |
| 150 | 连接器实例id+虚拟节点序号+1-1000随机数 | 100 | 10000 | 156.16 | 2ms |
| 200 | 连接器实例id+虚拟节点序号+1-1000随机数 | 100 | 10000 | 144.74 | 3ms |
| 300 | 连接器实例id+虚拟节点序号+1-1000随机数 | 100 | 10000 | 147.32 | 3ms |
4.修改哈希算法
查询100000次
| 哈希算法 | 分布离均匀值得偏差 | 总耗时 |
|---|---|---|
| Murmur3 | 0.8% | 15.602ms |
| CRC32 | 6% | 20.1744ms |
| 特性 | CRC32 | Murmur3 |
|---|---|---|
| 设计初衷 | 数据校验（错误检测） | 哈希表/散列优化 |
| 设计目标 | 检测传输错误（如网络包校验） | 实现均匀的键值分布 |
| 雪崩效应 | 弱（微小输入变化→微小输出变化） | 强（微小输入变化→巨大输出变化） |
算法特性对比
{card-describe title="CRC32的问题"}
多项式校验特性：CRC32基于多项式除法，设计目标是检测突发错误（如连续比特错误）
对相似输入（如连续数字ID）会产生相似的哈希值
示例：CRC32("user100") 和 CRC32("user101") 可能只有最后几位不同
由于构建哈希环虚拟节点使用的key是id+自增序号会导致哈希值非常相似
{/card-describe}
Murmur3的优势
{alert type="info"}
结合乘法、移位、异或等操作打乱数据 对输入数据的每个字节进行多次混合运算
{/alert}
雪崩效应：
murmur3("user100") → 0x58a7f2d1
murmur3("user101") → 0x3c8bf0e7 # 输入微小变化导致输出完全不同{/collapse-item}
{collapse-item label="三、结论" open}
- 测试发现选择虚拟节点数150，生成哈希字符串选择连接器实例id+虚拟节点序号+1-1000随机数，相对来说，哈希到的连接器id相对均匀一些
- 每个连接器id被哈希到的平均次数时100次，从哈希出来的结果来看相对均匀。
- 由于连接器server是分布式的 每台节点随机值不一样会导致构建的哈希环不一样，故只能增加一致性哈希的虚拟节点
- 修改key的哈希算法不使用CRC32改成murmur3
{/collapse-item}
{/collapse}