一致性Hash(Consistent Hashing)

一、产生背景

在业务开发中，我们常把数据持久化到数据库中。如果需要读取这些数据，除了直接从数据库中读取外，为了减轻数据库的访问压力以及提高访问速度，我们更多地引入缓存来对数据进行存取。读取数据的过程一般为：先访问缓存，如果缓存存在就从缓存中读取数据，如果缓存不存在就从数据库中读取数据，然后将数据写入缓存

例如有n个服务器，m为机器编号，o为对象名称，我们要将一个对象均匀映射到n个服务器上，采用下面这个式子来定位对象缓存服务器:

m = hash(o) mod n

但是运用这种方式有一定的弊端，比如当机器需要扩容或者机器宕机的时候，我们需要重新计算所有数据的hash值cache会大规模的实效，数据的访问会直接访问后面的数据库服务器。一致性hash算法正是为了解决此类问题的方法，它可以保证当机器增加或者减少时，对缓存访问命中的概率影响减至很小。

二、一致性Hash环

这个环的起点是0，终点是2^32 - 1，且起点与终点连接，环的中间的整数按逆时针分布，故这个环的整数分布范围是[0, 2^32-1]，如图所示：

（一）将对象放置到Hash环

假设有4个对象o1,o2,o3,o4。然后使用hash得到4个对象的hash值m1,m2,m3,m4，将这四个值放到hash环上面，如图：

（二）将机器放置到Hash环

使用同样的hash函数，将机器放到hash环上面，假设缓存服务器为c1,c2,c3，得到的hash值为t1,t2,t3，如图：

（三）为对象选择机器

将对象和机器都放置到同一个hash环后，在hash环上顺时针查找距离这个对象的hash值最近的机器，即是这个对象所属的机器。如图：

（四）处理机器增减的情况

例如增加机器c4的部署并将机器c4加入到hash环的机器c3与c2之间。这时，只有机器c3与c4之间的对象需要重新分配新的机器。对于我们的例子，只有对象o4被重新分配到了c4，其他对象仍在原有机器上。

或者机器c1下线（当然，也有可能是机器c1宕机），这时，只有原有被分配到机器c1对象需要被重新分配到新的机器。对于我们的例子，只有对象o2被重新分配到机器c3，其他对象仍在原有机器上。如图：

（五）虚拟节点

不过从上面可以看出来新加入的机器c4只分担了机器c2的负载，机器c1与c3的负载并没有因为机器c4的加入而减少负载压力。如果4台机器的性能是一样的，那么这种结果并不是我们想要的。所以我们因入虚拟节点来解决负载不均衡的问题。

将每台物理机器虚拟为一组虚拟机器，将虚拟机器放置到hash环上，如果需要确定对象的机器，先确定对象的虚拟机器，再由虚拟机器确定物理机器。

假如开始时存在缓存机器c1，c2，c3，对于每个缓存机器，都有3个虚拟节点对应，其一致性hash环结构如图：

假设对于对象o1，其对应的虚拟节点为c11，而虚拟节点c11对象缓存机器c1，故对象o1被分配到机器c1中。

新加入缓存机器c4，其对应的虚拟节点为c41，c42，c43，将这三个虚拟节点添加到hash环中，得到的hash环结构如图：

新加入的缓存机器c4对应一组虚拟节点c41，c42，c43，加入到hash环后，影响的虚拟节点包括c31，c22，c11（顺时针查找到第一个节点），而这3个虚拟节点分别对应机器c3，c2，c1。即新加入的一台机器，同时影响到原有的3台机器。理想情况下，新加入的机器平等地分担了原有机器的负载，这正是虚拟节点带来的好处

三、groupcache中的consistent hash

consistenthash/consistenthash.go

//Hash是函数类型，返回值是无符号32位整数
type Hash func(data []byte) uint32

//
type Map struct {
	hash     Hash
	replicas int   //副本数，对应上面的虚拟节点
	keys     []int // key为hash环上的一个点，其实就是一致性hash圆环
	hashMap  map[int]string  // hash环上的一个点到服务器名的映射，上面的keys包含服务器名和副本名，所以这里存储服务器及其各个副本都映射到同一个string
}

//初始化副本数，hash函数，hashmap表，
func New(replicas int, fn Hash) *Map {
	m := &Map{
		replicas: replicas,
		hash:     fn,
		hashMap:  make(map[int]string), // key对应cache服务器或者副本的hash值，value为具体的cache服务器，这样就完成了c11，c12，c13全部映射到c1的功能
	}
	if m.hash == nil {
		m.hash = crc32.ChecksumIEEE  //func ChecksumIEEE(data []byte) uint32返回crc32校验和
	}
	return m
}

//判断map是否为空
func (m *Map) IsEmpty() bool {
	return len(m.keys) == 0
}

//将缓存服务器加到Map中，比如C1、C2作为keys，如果副本数指定的是2，那么Map中存的数据是C1#1、C1#2、C2#1、C2#2的hash结果
func (m *Map) Add(keys ...string) {  // 这里的keys相当于缓存服务器
  //遍历要增加的key集合
	for _, key := range keys {
    //这里是为了产生虚拟结点
		for i := 0; i < m.replicas; i++ {
      //将i与key拼接后进行hash
			hash := int(m.hash([]byte(strconv.Itoa(i) + key)))  // 将i转为字符串
      //keys结构体增加key
			m.keys = append(m.keys, hash)
      //hashmap中增加key与hash结果的映射，比如hash是80，key为c1，这样就保存了hash环上面80到c1的映射，就像上面讲的c11，c22，c33，对应的key为c1是一个意思（c11，c12，c13的hashmap[hash]对应的value都是key）
			m.hashMap[hash] = key
		}
	}
  //升序排列
	sort.Ints(m.keys)
}

//函数根据key找到对应的节点
func (m *Map) Get(key string) string {
	if m.IsEmpty() {
		return ""
	}
  // 找到key对应的hash值
	hash := int(m.hash([]byte(key)))

  // 用二分法查找锁定一个使m.keys[i] >= hash的最小值i，就是找到了顺时针离要存储key最近的缓存服务器
	// Binary search for appropriate replica.
	idx := sort.Search(len(m.keys), func(i int) bool { return m.keys[i] >= hash })

	// Means we have cycled back to the first replica.
	if idx == len(m.keys) {
		idx = 0
	}
  // 得到真实用来存数据的服务区
	return m.hashMap[m.keys[idx]]
}