No Headback

一致性哈希详解

Xargin -

网站做大了以后，因为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算法。