一致性哈希算法

使用

• 运行环境：Linux
• 运行命令
  • make -- 编译
  • make run -- 运行，在控制台输出结果
  • make run2 -- 运行，在out.txt中输出结果
  • make clean -- 清理生成文件

学习

1. 基本场景： 假设有N个cache服务器，对服务器集群的管理，路由算法至关重要，就和负载均衡算法一样，路由算法决定着究竟该访问集群中的哪台服务器。
2. 余数哈希： 计算 object 的 hash 值，然后均匀的映射到到 N 个 cache 服务器； hash(object) % N 但是当需要增加或者减少cache服务器的时候，这个算法的问题就暴露出来了，将导致几乎所有的cache服务器失效。
3. 一致性哈希： 一致性哈希是一种hash算法，通过一个叫做一致性hash环的数据结构实现key到cache服务器的hash映射。

以下分步骤阐述一致性hash算法原理：

• 环形hash空间。构造一个长度为$2^{32}$的整数环（这个环被称为一致性Hash环）
• 把cache服务器映射到hash空间。根据节点名称的Hash值（其分布为[0, $2^{32}-1$]）将缓存服务器节点放置在这个Hash环上
• 把对象映射到hash空间和cache服务器。根据需要缓存的数据的Key值计算得到其Hash值（其分布也为[0, $2^{32}-1$]），然后在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。
• 当cache服务器数量发生改变。当新增一个cache服务器的时候，受影响的将仅是那些沿着新增cache服务器顺时针遍历直到下一个cache服务器之间的对象，其他的不会有影响；当减少一个cache服务器的时候，受影响的将仅是那些沿着新增cache服务器逆时针遍历直到下一个cache服务器之间的对象，其他的不会有影响；
• 虚拟节点。“虚拟节点”（ virtual node ）是实际节点在 hash 空间的复制品（ replica ），一个实际节点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以 hash 值排列。

实现

项目中一致性哈希算法的哈希值hash值的计算通过Murmurhash算法计算得到， MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。 由Austin Appleby在2008年发明， 并出现了多个变种，都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。