什么是一致性hash算法（负载均衡一致性hash算法）

小君 2023-05-17 02:39:17 101

什么是一致性hash算法（负载均衡一致性hash算法）根据一致性哈希算法，数据A就被绑定到了server01上，D被绑定到了server02上，B、C在server03上，是按照顺时针找最近服务节点方法假如我们有数据A、B、C和D，经过哈希计算后位置如下：下一步将各个服务器使用哈希算法计算出每台机器的位置，具体可以使用服务器的IP地址或者主机名作为关键字，并且是按照顺时针排列：//这里我选择crc32，具体情况具体安排 func hashKey(host string) uint32 { scratch := []byte(host) return crc32.ChecksumIEEE(scratch) }这里我们假设三台节点memcache经计算后位置如下：//add the node c.Add("Memcache_server01") c.Add("Memcache_server02")

什么是一致性hash算法（负载均衡一致性hash算法）(1)

讲一致性hash算法前，先简述一下求余hash算法：

hash(object)%N

一个缓存服务器宕机了，这样所有映射到这台服务器的对象都会失效，我们需要把属于该服务器中的缓存移除，这时候缓存服务器是 N-1 台，映射公式变成了 hash(object)%(N-1) ；
由于QPS升高，我们需要添加多一台服务器，这时候服务器是 N 1 台，映射公式变成了 hash(object)%(N 1) 。

1 和 2 的改变都会出现所有服务器需要进行数据迁移。

一致性HASH算法

一致性HASH算法的出现有效的解决了上面普通求余算法在节点变动后面临全部缓存失效的问题：

type Consistent struct { numOfVirtualNode int hashSortednodes []uint32 circle map[uint32]string nodes map[string]bool }

简单地说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某空间哈希函数H的值空间是0-2^32-1（即哈希值是一个32位无符号整形），整个哈希空间如下：

什么是一致性hash算法（负载均衡一致性hash算法）(2)

下一步将各个服务器使用哈希算法计算出每台机器的位置，具体可以使用服务器的IP地址或者主机名作为关键字，并且是按照顺时针排列：

//这里我选择crc32，具体情况具体安排 func hashKey(host string) uint32 { scratch := []byte(host) return crc32.ChecksumIEEE(scratch) }

这里我们假设三台节点memcache经计算后位置如下：

什么是一致性hash算法（负载均衡一致性hash算法）(3)

//add the node c.Add("Memcache_server01") c.Add("Memcache_server02") c.Add("Memcache_server03") func (c *Consistent) Add(node string) error { if _ ok := c.nodes[node]; ok { return errors.New("host already existed") } c.nodes[node] = true // add virtual node for i := 0; i < c.numOfVirtualNode; i { virtualKey := getVirtualKey(i node) c.circle[virtualKey] = node c.hashSortedNodes = append(c.hashSortedNodes virtualKey) } sort.Slice(c.hashSortedNodes func(i j int) bool { return c.hashSortedNodes[i] < c.hashSortedNodes[j] }) return nil }

接下来使用相同算法计算出数据的哈希值并由此确定数据在此哈希环上的位置

假如我们有数据A、B、C和D，经过哈希计算后位置如下：

什么是一致性hash算法（负载均衡一致性hash算法）(4)