一致性哈希

当我们在做数据库分库分表或者是分布式缓存时，不可避免的都会遇到一个问题：如何将数据均匀的分散到各个节点中，并且尽量的在加减节点时能使受影响的数据最少。

最经典的方式就是hash取模了，即将传入的Key按照 index=hash(key)%N 这样来计算出需要存放的节点。其中hash函数是一个将字符串转换为正整数的哈希映射方法，N就是节点的数量。这样可以满足数据的均匀分配，但是这个算法的容错性和扩展性都较差。比如增加或删除了一个节点时，所有的Key都需要重新计算，显然这样成本较高，为此需要一个算法满足分布均匀同时也要有良好的容错性和拓展性。

一致性hash作为一个负载均衡算法，可以用在分布式缓存、数据库的分库分表等场景中，还可以应用在负载均衡器中作为作为负载均衡算法。在有多台服务器时，对于某个请求资源通过hash算法，映射到某一个台服务器，当增加或减少一台服务器时，可能会改变这些资源对应的hash值，这样可能导致一部分缓存或数据失效了。一致性hash就是尽可能在将同一个资源请求路由到同一台服务器中。

一致性哈希是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对K/n个关键字重新映射，其中K是关键字的数量，n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

环构建

一致Hash算法是将所有的哈希值构成了一个环，其范围在0~2^32-1。之后将各个节点哈希到这个环上，可以用节点的IP、hostname这样的唯一性字段作为Key进行hash计算取值。客户端根据自身的某些数据hash之后也定位到这个环中，通过顺时针找到离他最近的一个节点，也就是这次路由的服务节点。

当节点发生故障下线，或者增加新的节点时候，依然根据顺时针方向，k2和k3保持不变，只有k1被重新映射到了N3。这样就很好的保证了容错性，当一个节点宕机时只会影响到少少部分的数据。

虚拟节点

考虑到服务节点的个数以及hash算法的问题导致环中的数据分布不均匀时引入了虚拟节点。

Java中一致性哈希算法的实现

我们可以选择用某个有序数组或者TreeMap来模拟一致性哈希中的环：

初始化一个长度为N的数组。
将服务节点通过hash算法得到的正整数，同时将节点自身的数据（hashcode、ip、端口等）存放在这里。
完成节点存放后将整个数组进行排序（排序算法有多种）。
客户端获取路由节点时，将自身进行hash也得到一个正整数；
遍历这个数组直到找到一个数据大于等于当前客户端的hash值，就将当前节点作为该客户端所路由的节点。
如果没有发现比客户端大的数据就返回第一个节点（满足环的特性）。

只使用了TreeMap的一些API：

写入数据候，TreeMap可以保证key的自然排序。
tailMap可以获取比当前key大的部分数据。
当这个方法有数据返回时取第一个就是顺时针中的第一个节点了。
如果没有返回那就直接取整个Map的第一个节点，同样也实现了环形结构。

Go中一致性哈希算法的实现与应用

func (m *Map) Add(nodes ...string) {
    for _, n := range nodes {
        for i := 0; i < m.replicas; i++ {
            hash := int(m.hash([]byte(strconv.Itoa(i) + " " + n)))
            m.nodes = append(m.nodes, hash)
            m.hashMap[hash] = n
        }
    }
    sort.Ints(m.nodes)
}

func (m *Map) Get(key string) string {
    hash := int(m.hash([]byte(key)))
    idx := sort.Search(len(m.keys),
        func(i int) bool { return m.keys[i] >= hash }
    )
    if idx == len(m.keys) {
        idx = 0
    }
    return m.hashMap[m.keys[idx]]
}

Links

最近更新于0001-01-01