一致性hash算法

  categories:资料  author:

来源:http://blog.chinaunix.net/uid-20196318-id-3013797.html

关于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迁移以及重新分配的情况。



快乐成长 每天进步一点点