consistent hash(一致性哈希算法)

一、产生背景

今天咱不去长篇大论特别详细地讲解consistent hash，我争取用最轻松的方式告诉你consistent hash算法是什么，如果需要深入，Google一下~。

举个栗子吧：

比如有 N 个 cache 服务器，需要将一个object 映射到 N 个 cache 上，我们可以用类似下面的方法计算 object 的 hash 值，然后均匀的映射到到 N 个 cache 上：

hash(object)%N

比如object是“hello”，hash（object）是100，N为3，100%3=1，这个数据会被存到第1个cache上（0、1、2三个cache）。这样就能解决一堆数据放到N个cache上的问题。

现在有个突发情况，0、1、2三个cache中1损坏了！

怎么办呢，cache 1上的数据首先需要迁移，可用cache数量变为2，这个时候我们需要重新计算所有数据的hash值，上面的公式变成了这样：

hash(object)%(N-1)

这次重新计算意味着每一份数据hash之后的结果几乎都变了！也就是意味着在cache系统中会发生大规模cache失效，数据访问会直接冲击cache后面的服务器，好玩了，崩了。

咋个办呢，consistent hash出现了！

二、算法原理

consistent hash简单的说，就是要在cache数量变化时，能够尽可能小的改变已存在 key 映射关系，也就是增加一个cache或者减少一个cache服务器，对已经存在的缓存数据不要产生大影响。怎么做到呢，，，

我们先想象一条链子，第一个格子是0，最后一个格子是2^32-1，这条链子就是一个地址空间为2^32的hash值空间，现在将链子首位相连，组成一个ring，就像下面这样（这里画图太麻烦了，下面的环环相关的图来自互联网，侵删吧）：

然后考虑我们由object1~object4这样四个数据，通过hash算法后映射到这个ring上【类似这样：hash(object1)=key1】

这里应该很好理解，4个数据得到4个key，接下来我们要将cache服务器也映射到这个ring上，假设由3个cache服务器，分别是cache A、cache B、cache C，然后用hash算法：hash(cache A)=key A，将3个cache服务器丢到这个ring上，就可用得到如下结果（计算cache服务器的hash值时可以用其ip等信息）：

然后顺着这个ring，收集object数据，遇到cache的时候就丢进去，这样就可以将数据和cache对应起来，于是我们可以得到如下结果：

object1：Cache A

object4：Cache B

object2/object3： Cache C

ok，这样就完成了数据映射，然后我们考虑一下前面普通hash算法遇到的cache服务器数量变化的情况，看一下ring hash是否解决了这个问题。

假设cache B掉线

这个时候可以发现只有原先映射到Cache B上的object4收到了影响，需要转移到Cache C上。

如果增加一个Cache结点呢？假设增加一个Cache D：

这个时候只需要将object2转移到Cache D上，其他的没有变化。是不是很神奇？

这里可能大家会意识到一个问题，当cache服务器数量少的时候，这个算法很容易导致数据分布不均匀，所以ring hash中还有一个虚拟节点的概念，前面只剩下cache A和cache C的例子中A上有1个数据，而C中存了3个，我们将cache（假设用ip值表示）加上一个编号，然后进行hash运算，得到更多的虚拟cache结点：

hash("192.168.0.1#1")

hash("192.168.0.1#2")

hash("192.168.0.2#1")

hash("192.168.0.2#2")

类似上面这样，一个cache服务器就对应了2个hash值，这样我们再丢到ring上就会得到如下结果：

这时候object1就会落在Cache A2上，object2会落在Cache A1上，物理上其实A1和A2都是cache A，通过这种方式直观看我们将原先的1、3分布变成了2、2分布（A上1个数据C上3个数据变成A上2个数据B上2个数据）

引入“虚拟节点”后，映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 }，于是乎这个算法的平衡性就更好了。

ok，一致性hash算法的原理就介绍到这里，下面可以看groupcahce中的consistent hash如何实现了。

三、groupcache中的consistent hash

终于要看代码了！！！

源码主要就如下几个package，今天我们看一下第一个package：【package consistenthash】的内容

从上图我们可以看到，这里只需要关注consistenthash.go这源码文件，里面有2个类型：Hash和Map，1个函数New，Map类型有4个不可导出的属性以继3个绑定的方法。

下面一个个看吧~

1、类型Hash（需要记得Hash是一个函数类型哦）。

2、Map类型（Map类型的第一个属性就是上面的Hash类型变量hash，replicas属性表示的是副本数，还记得上面我们提到的为了解决平衡性问题而引入的虚拟节点的概念吗？这些虚拟节点这是这里描述的副本数）。

3、New()函数（这个函数明显就是用来获取上面的Map类型变量实例的，初始化副本数、hash函数、hashMap表，hashMap表的key是一个表示cache服务器或者副本的hash值，value为一个具体的cache服务器，这样就完成了Cache A、Cache A1、Cache A2等副本全部映射到Cache A的功能。

4、IsEmpty()函数(这个函数就没啥可讲的了，非空判断）

5、Add()函数（将缓存服务器加到Map中，比如Cache A、Cache B作为keys，如果副本数指定的是2，那么Map中存的数据是Cache A#1、Cache A#2、Cache B#1、Cache B#2的hash结果）

6、Get()函数（这个函数相对复杂一点，比如有一个数据：name="张三"这条数据需要存，这时候通过这个函数选择一个cache服务器，返回的string类型可以是服务器ip，比如："192.168.0.1",从而调用者能够将name="张三"存到"192.168.0.1"上）

ok，讲完了，今天的内容有点多，可能需要多花点时间消化一下~

下一讲我们介绍groupcachepb这个package，当然不可避免地要介绍一下Protocol Buffers了，行，今天就讲到这里！