一致性哈希详解

网站做大了以后,因为MySQL在较高的qps下表现比较差,如果是创业公司的话,那可能租用的都是公有云的机器来做自己的服务,也许就是个内存2GB,cpu两核的kvm,能够使用的资源非常非常的少,所以数据库的实例本身性能也不会好到哪里去。在整体qps达到一定量级之后必然会遇到性能低下的问题,至于这个临界值,是由具体的机器配置得到的,这里就不给出什么结果了,感兴趣的同学可以自己去搜索。

MySQL抗不住的情况下只能引入缓存来提升整体性能了,网站开发有一个比较著名的二八原则,就是80%的用户其实访问的都是20%的数据。所以实际上你只要把这20%的数据缓存好,就可以让网站整体的响应和吞吐量上一个等级。缓存为什么能比去读数据库快?原理也很简单,大多数的缓存会把数据存储在内存中,而数据库则是要去硬盘读取。这两种介质在速度上相差了好几个数量级。

缓存固然好,但假如你的网站变得越来越大的时候,可能会慢慢发现单台机器已经满足不了自己的需求了。这时候就涉及到缓存分布的问题,如果是一个在学校里没有接触过工程项目的人的话,很容易想出来按照请求@key,然后取模,并将内容缓存到对应的机器上的方案。@key可以唯一的确定某一个请求,例如在php里,可能是class_name+function_name+params,然后再进行序列化得到的一个字符串。但取模的方式会遇到一个问题,就是在一台机器down了,或者添加新的机器的时候,会有大量的缓存迁移,因为取模的结果与原来不一致了嘛,例如:

A       B       C
1-33    34-67   68-100

A       B       C       D
1-25    26-50   51-75   76-100

上面的例子,在添加了一台新机器的时候,原来在A上的26-33就需要迁移到B机器上去,B机器的51-67要迁移到C机器上去,C机器的76-100要迁移到D机器上去。因为这种迁移可能需要采用某种缓存预热机制来实现,如果是预热的话,势必还是得要伪造一些请求来做,实际上要增加不必要的工作量。

这也就是一致性哈希的优势了,来看看一致性哈希是怎么做的。援引一下别人的介绍:

一致性hash算法是:首先求出服务器(节点)的哈希值,并将其配置到0~2^32的圆(continuum)上。然后用同样的方法求出存储数据的键的哈希值,并映射到圆上。然后从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服务器上。如果超过2^32仍然找不到服务器,就会保存到第一台服务器上。
idx=FirstMaxServerIdx(hash(query_key))

consistent hash算法背后最基础的思想就是:对object和cache machine使用相同的hash函数【DHT算法的核心啊,P2P的理论基石啊,资源和地址节点在统一地址空间进行编址】。Consistent Hash适用于每个节点只保存部分数据,而不是像前面几种算法,每个节点保存全量数据。这样做的好处是能够把cache机器映射到一段interval 上,而这段interval就会包含一定数目的对象的hash值。如果某台cache机器被移除了,那么它映射到的interval被和它相邻的一个 cache机器托管,其他所有的cache机器都不用变。

一致性哈希算法最大程度的避免了key在服务节点列表上的重新分布,其他附带的改进就是有的一致性 哈希算法还增加了虚拟服务节点的方法,也就是一个服务节点在环上有多个映射点,这样就能抑制分布不均匀,最大限度地减小服务节点增减时的缓存重新分布。

按照上面的说明,比如我们有3台机器,内网ip分别是:

10.10.39.13
10.10.39.14
10.10.39.15

那么我们用sha1/md5之类的算法,对每一台机器的ip进行hash计算,那么会得到:

hashes_ip_to_hash[] = sort_by_hash({ip1 => hash(ip1), ip2 => hash(ip2), ip3 => hash(ip3)})

当一个请求到来的时候,我们需要对其key先进行hash

hash_val = hash(@key)

然后去上面的机器hashes数组里查找这条纪录应该打到哪一台机器上:

php版;
foreach($hashes as $hash) {
    if($hash > $hash_val) {
        return $hash;
    }
}

//没有找到,那么用第一台机器
return $hashes[0];

上面这是最简单的形式,如果我们要按照描述中的生成虚拟节点,怎么做呢?实际上也很简单:

$hashes = virtual_nodes_algothrithm($hashes);

对$hashes数组做一个简单处理即可。

这里问题就变成了如何生成虚拟节点的算法,关于如何生成虚拟节点,可以参考:
http://www.cnblogs.com/daizhj/archive/2010/08/24/1807324.html

http://www.iteye.com/topic/684087

注:实际上用md5来计算hash值性能较差,想要改善的话,读者可以去搜索一下murmurhash算法。