一致性hash算法

关于hash函数

hash函数主要用于将“大范围”映射到“小范围”，如MD5将任意长度的数据计算出128bit的签名值，RSHash等函数将任意长度的数据转换成32bit的无符号整型，好的hash函数拥有高性能以及低hash冲突。

 

hash函数主要通过加减乘除及移位等操作来计算最终结果，hash函数的分类参考：

http://nicoleamanda.blog.163.com/blog/static/7499610720091013233598/【1】

http://yuhuafx.blog.hexun.com/58369610_d.html【2】

 

【1】【2】中的hash函数用于将数据序列计算出32bit的hash值，主要通过加减乘除及移位等方式实现，同时【2】中包含各个hash函数的测试情况对比，如下图：

 

 

这些hash函数有一个共同的特性就是高位字符（这里指数据串前面的字符）比低位字符对结果的影响更大，当两个数据串只有少数低位不同时，计算出的hash值非常接近（但这并不能说明hash函数不好，值接近但并没有冲突），通过如下代码验证。

 

void hash_test(int num)

{

     char server[] = "192.168.0.1";

     char buf[1024];

     for(int i = 0; i < num; i++) {

    //    sprintf(buf, "%010d-%s", i, server);  // 对比这两种情况得出的结果

          sprint(buf, “%s-%010d”, server, i);

         printf("%d\n", PJWHash(buf));

     }

}

 

而对于MD5、SHA1等散列函数，则不存在相近的数据串计算出相近结果的情况，其随机性表现得非常好，至于为什么这样，得去探究其实现方法。

 

一致性hash算法

一致性hash在dynamo及memcached这两个大名鼎鼎的系统中得到应用，其相比普通hash的主要优势在于在添加或移除节点时，保证尽量少的cache失效（数据迁移及均衡）。

 

这里就不详细介绍一致性hash的理论了，只关注一致性hash算法的系统仿真，讨论使用一致性hash算法的系统，需要提供那些接口以及接口的实现。（注：这里不考虑服务器端，只考虑在客户端需要做的工作。）

 

客户端需要处理：
（1）有一组server在运行了，如何利用这组server开始work？

（2）添加/删除key应该链接哪个server？

（3）添加/移除服务器时如何重新分配key与server的对应关系？

 

问题（1）：

为了使得节点的分配尽量均衡，通常采用虚拟节点的方式构造出大量的虚节点，假如初始的服务器列表为[“192.168.0.1”, “192.168.0.2”, “192.168.0.3”]，假设每个节点对应100个虚节点（也可根据服务能力的不同分配不同数目的虚节点）。

 

将这些节点分别加上前缀（如果作为后缀，导致结果非常接近，见上面的分析，或采用MD5计算并截取部分字节的方式保证随机），如192.168.0.1对应的100个节点分别为1#192.168.0.1, 2#192.168.0.1等。

 

计算出所有虚节点的hash值，并建立（vnode – server）的映射关系，这个准备好之后，系统就可以开始work了。

 

问题（2）：

当需要访问key时，首选需要定位应该连接哪个server，根据一致性hash算法，首先根据key计算出hash值（这里也需慎重选择hash函数，如果key的范围本身比较小，考虑加入额外信息），并选择第一个大于该hash值的虚节点，通过（vnode – server）的映射关系，就可得知该虚节点属于哪个server，从而确定应该访问的server。

 

问题（3）：

1. 移除节点时，如果是节点信息被持久化存储，则需要将删除节点中的key迁移到其他节点中（持久化存储通常有副本），迁移时服务器的定位方式与问题（2）类似；如果是与memcached类似的缓存系统，则只需更新（vnode-server）的映射关系，从中删除被移除节点对应的vnode。

2. 增加节点时，为了负载均衡，需要将其他节点上的部分key迁移到新节点上（在满足一致性hash的基础上），同时更新（vnode – server）的映射关系。

 

本人简单的模拟了一下（1）（2）（3）的实现，3个server的情况，随机生成多个key，考察虚拟虚拟节点数对key分布的影响，以及增加/移除节点时，key迁移以及重新分配的情况。

 一致性hash仿真.rar