一致性哈希(Consistent Hash)简介

在文章的最后面我会贴两篇我参考的文章，写得很好，图也很漂亮，新手的话你可以先看下，然后不理解的话再来看我这篇，我是看了那两篇以后，还有一点点不是很理解，然后才会有这篇文章。嗯。好，开始了。

consistent hashing 是一种分布式系统中常用的算法。简单的说，在移除或添加一个 cache 时，它能够尽可能小的改变已存在 key 映射关系，尽可能的满足单调性的要求。 一个分布式的存储系统，要将数据存储到具体的节点上，如果采用普通的hash方法，将数据映射到具体的节点上，如key%N，key是数据的key，N是机器节点数，如果有一个机器加入或退出这个集群，则所有的数据映射都无效了，如果是持久化存储则要做数据迁移，如果是分布式缓存，则其他缓存就失效了。
因此，引入了一致性哈希算法.

1,需要知道的3个东西

.1,真实机器和虚拟节点的映射表(请允许我暂时称它为node表吧)

1.2,一种hash规则

1.3,根据object的哈希值得到server的哈希值的规则

废话少说，我先画张图吧。

好了，画完了。就是这样子了。

首先我们要明确一点，就是我们手头上是有两个东西（暂且让称它为client和server吧）要做哈希的,哈希表的目的就是为了建立和client和server的联系。

例如有1000个用户要访问我们的网站，我需要让10台服务器去处理。我希望根据每个用户（根据不同的pin值和信息做成一个key来判别）每次来的时候都能访问相同的服务器，如果我们简单的用key%n=n,去得到一个数，然后根据这个数n去访问服务器n,那么这只是一层映射，如果你加减一个服务器，key%(n+1),key%(n-1)都会令大部分用户访问的服务器改变了。
所以我们需要的是一种映射关系(或者叫哈希空间，通常的 hash 算法都是将 value 映射到一个 32 为的 key 值，也即是 0~2^32-1 次方的数值空间；)，client映射到上面是一个数字，server映射到上面也是一个数字，然后，我们按照client的数字取比它大最少的而且有服务器对应的一个数字，然后取出这个数字对应的服务器作为它要访问的服务器。 这样一来，如果加减服务器的话，原来的client对应的哈希值是没有变的，而原来没坏了的服务器因为机器名字没变，所以它的哈希值也没变，所以它们之间的对应是没有问题的。那么原来对应那台坏了的客户请求就会迁移到另外一台服务器上。
这时候问题来了。这又会造成一个“雪崩”的情况，即下一个节点由于承担了前个节点的数据，所以下一个节点的负载会变高，该节点很容易也宕机，这样依次下去，这样造成整个集群都挂了。 为此，引入了“虚拟节点”的概念：即把想象在这个环上有很多“虚拟节点”，数据的存储是沿着环的顺时针方向找一个虚拟节点，每个虚拟节点都会关联到一个真实节点，这就是 为什么我们需要一个node表的原因了。这张表就是维护真实节点和虚拟节点的映射关系。 将真实的节点虚拟成160倍（倍数越多越均匀）的虚拟节点所以你看到的node表应该是一个个哈希后的数字和该数字对应的服务器的信息。例{“1234123”，ip=168.0.0.1}
这时候逻辑就是这样:

好了.接下来就是hash算法的选择。
hash有很多种，像加法这些简单的碰撞率太高了，所以我们要挑种高效碰撞率又低的。现在一般是选择MD5，fvn,murmur等， 这有几种python实现的快速的算法pyfasthash.你可以看下。
我这里用的是murmurhash,因为据说比较快和碰撞率比较低，而且是我正在看nginx，nginx的ngx-http-split-clients模块也是用的murmurhash(可以参照源码). murmurhash根据需求位数可分为很多种，这里提供了几种C/C++实现的版本murmur_hash.cpp，我用的就是里面的murmurhash64B。

可以参照下面的lua代码，哈希方法用C做成一个动态链接库放进来了。

--load lib
package.loadlib("/home/test/www/libhashlib.so", "luaopen_hashlib")()
--real machine
local shards = {
{name="",ip="127.0.0.1",port=81,weight=1},
{name="",ip="127.0.0.2",port=82,weight=1},
{name="machine3",ip="127.0.0.3",port=83,weight=1},
}
--char to number base on ascii
function chartonumber(char)
local i=32
local temp_char=char
 while i<126 do
 if temp_char == string.format('%c', i) then
 return i
 end
 i=i+1
 end
end
--table for keep virtual nodes and real nodes
nodes={} 
--inital virtual nodes
function virnode_init(shards,nodes)
for i,shardinfo in pairs(shards) do
-- print("i="..i,"shardinfo="..shardinfo.ip..":"..shardinfo.port,"weight:"..shardinfo.weight)
  if shardinfo.name==nil or shardinfo.name == "" then
        for n=0,160*shardinfo.weight do
        table.insert(nodes,{hashlib.murmurhash64b("SHARD-"..i.."-NODE-"..n),shardinfo})
        end
  else
        for n=0,160*shardinfo.weight do
        table.insert(nodes,{hashlib.murmurhash64b(shardinfo.name.."*"..shardinfo.weight..n),shardinfo})
        --i can not understand why add this for nodes.key,why not add shardinfo.name only
        end
  end
end
return
end     
function getshardinfo(nodes,key)
local i=0
local nodeinfo=nil
key=hashlib.murmurhash64b(key)
print("key:"..key)
table.sort(nodes,function(a,b) return a[1]<b[1] end)--nodes sort by nodes.name
  for i, nodeinfo in pairs(nodes) do
    if key<=nodeinfo[1] then
      return nodes[i]
    end
--print(nodeinfo[1],key)
  end
  return nodes[1]
end

参考资料：
一致性hash算法详解
一致性哈希算法与Java实现
Redis Java Client Jedis 源码分析