架构师训练营第 1 期第 5 周作业

github地址：https://github.com/kesai123/Architecture01/tree/main/consistentHashing



一致性哈希组件主要实现以下对外接口:

AddNode(): 向集群添加节点

RemoveNode(): 从集群删除节点

GetKV(): 从集群读取KV数据

SetKV(): 向集群写入KV数据

SetKV(): 从集群删除KV数据



组件维护如下信息：

节点名字与物理节点的映射

虚拟节点的hashcode与物理节点的映射

每个物理节点划分为多少虚拟节点（初始化时配置好）

保存所有虚拟节点hashcode的哈希环



为了代码实现简单，当前版本中，哈希环使用slice实现。其缺点是，每次增删物理节点后，整个哈希环要排序重建一遍，如果集群中配置的虚拟节点很多，这个过程可能影响性能。

后续优化可能会使用红黑树替代slice实现哈希环，增删物理节点时，不需要整个重建，对哈希环整体影响较小，性能会更好。



哈希函数使用了crc32算法，后续可将哈希算法抽象为接口，提供更灵活的选择。



由于为了测试一致性哈希算法的均衡性，没有使用真实的分布式集群缓存环境。基于cache接口，实现一个简单的基于链表的cache存储来测试百万KV存储。



当物理节点数10，每物理节点的虚拟节点数10时，获得的标准差如下：

node 1 : 131375

node 2 : 129091

node 3 : 63166

node 4 : 103941

node 5 : 98896

node 6 : 74780

node 7 : 144620

node 8 : 140026

node 9 : 56630

node 10 : 57475

Everage: 100000

Deviation: 33350.527372



其他参数不变，调整每物理节点的虚拟节点数100时，执行获得的标准差如下：

node 1 : 115537

node 2 : 111895

node 3 : 129077

node 4 : 76672

node 5 : 81871

node 6 : 100447

node 7 : 123541

node 8 : 75295

node 9 : 79826

node 10 : 105839

Everage: 100000

Deviation: 19253.615920



可见物理节点数不变，虚拟节点数设置的越多，标准差越小，一致性哈希得到的均衡性越好。

总体来说，即使在没有动态增删物理节点的情况下，当前算法得到的标准差也是比较大的。后续可能会尝试crc32以外的算法，验证一下哈希算法对均衡性计算的影响。