需求

任何东西的存在都是因为有需求。

在一个稍微大型的分布式系统中，尤其是分布式缓存中，单台机器的容量有限，需要通过N台机器共同提供服务。那么针对N台机器最简单的负载均衡策略就是hash(object) % N。通过这种方式，只要选择一个比较分散的hash算法，就可以比较好的平均的把请求分散到N台机器上去了。但是这种策略缺点在哪呢？那就是这个N的值一旦发生变化，比如增加一台机器或者有一台机器挂掉了，这时% N的结果就会发生剧烈的变化，导致大量的缓存失效，大量的负载会穿透到缓存的后台，给整个系统产生剧烈的震荡。

一致性hash

从上面传统的hash策略可以看出，一旦发生节点数量变化，几乎所有的关键字都要重新hash。而一致性hash可以做到只有K/n个关键词需要迁移。其中K是关键词的数量，n是节点数量。

一致性hash的核心思想是，每一个节点对应了hash算法的一段区间域，当一个节点失效的时候，其所对应的区间域会被合并到临近的其他节点的区间域中。其他区间域不受影响。

举例

假设一个hash算法产生的区间域是[0, 100)，这时，我们有3个节点，他们被分散到0， 30， 80。分别表示[0, 30)，[30, 80)，[80, 100)区间的key都指向对应的节点。假设这时候，第二个节点，也就是30挂掉了，那么[0, 80)区间的所有key就自动全部指向0。这时，第三个节点80是不受影响的。同样，当我们增加一个节点，他被分配到20，那么[20, 30)区间就会指向20，不再指向0。

上面在死掉一个节点的时候，会产生0负责的区域过大的问题。这里，我们可以通过建立虚拟节点的方式来优化。也就是一个实际的物理节点拥有若干个虚拟节点，然后让这些虚拟节点放到hash的区间域中。这样，一个实际的物理节点，负责的会是hash域的多个区间段。挂掉之后，这若干的区间段会被合并到不同的虚拟节点上去，也就相当于合并到不同的物理机器上去了。

源码分析

这里我们使用一个Go语言写的一致性hash库consistent来举例。

1
2
3
4
5
6
7
8
type Consistent struct {
    circle           map[uint32]string
    members          map[string]struct{}
    sortedHashes     uints
    NumberOfReplicas int
    count            int64
    sync.RWMutex
}

这是一致性hash的核心的一个类型。

circle指的是整个hash域中，值与虚拟节点的映射关系。这个虚拟节点一般是物理机器的ip:port或者hostname:port加上虚拟节点编号的一个字符串。

members虽然是一个map类型，但在这里只是用来作为一个set使用的。用来记录实际的物理节点的地址。

sortedHashes是一个[]uint32类型。也就是用来维护所有虚拟节点在hash域中对应的值的顺序。

NumberOfReplicas就是默认一个物理节点产生多少个虚拟节点。

count是物理节点的数量

sync.RWMutex是一把读写锁。

然后我们来看增加一个物理节点：

1
2
3
4
5
6
7
8
9
// need c.Lock() before calling
func (c *Consistent) add(elt string) {
    for i := 0; i < c.NumberOfReplicas; i++ {
        c.circle[c.hashKey(c.eltKey(elt, i))] = elt
    }
    c.members[elt] = null
    c.updateSortedHashes()
    c.count++
}

首先是产生虚拟节点，并映射到实际的物理节点地址。然后将物理节点加入set，然后更新SortedHashes。最后计数加一。

这个updateSortedHashes其实很简单，就是把所有序号排序，便于后面Get的时候进行二分查找。

再来看Get，也就是知道，某个key应该存储哪个物理节点上去。

1
2
3
4
5
6
7
8
9
10
11
// Get returns an element close to where name hashes to in the circle.
func (c *Consistent) Get(name string) (string, error) {
    c.RLock()
    defer c.RUnlock()
    if len(c.circle) == 0 {
        return "", ErrEmptyCircle
    }
    key := c.hashKey(name)
    i := c.search(key)
    return c.circle[c.sortedHashes[i]], nil
}

过程很简单，除了开头加锁，特殊情况处理，接下来先算一下给定key的hash值，然后search找到在整个hash域对应的是哪个虚拟节点号。这个search就是在上面提到的sortedHashes上进行二分查找。最后就是返回物理节点的信息。

总结

总得看来，一致性hash还是很好理解的，尤其是结合源码来看。

参考资料

每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)

Consistent Hashing and Random Trees