资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

【负载均衡——一致性哈希算法】

创作时间:

作者:

@小白创作中心

【负载均衡——一致性哈希算法】

引用

CSDN

https://blog.csdn.net/qq_45467608/article/details/137560863

一致性哈希算法是分布式系统中常用的负载均衡算法之一，它通过将存储节点和数据映射到一个环状结构中，实现了数据的均匀分布和高效访问。本文将详细介绍一致性哈希的基本原理、应用场景以及如何通过虚拟节点优化其性能，并提供Go语言实现的代码示例。

1. 一致性哈希是什么

一致性哈希算法很好地解决了分布式系统在扩容或缩容时发生过多数据迁移的问题。与传统哈希算法不同，一致性哈希算法对2^32进行取模运算，是一个固定的值。一致性哈希需要进行两步哈希：

对存储节点进行哈希计算，即对存储节点做哈希映射，例如根据节点的IP地址进行哈希
当对数据进行存储或访问时，对数据进行哈希映射

一致性哈希是指将存储节点和数据都映射到一个首尾相连的哈希环上。

首先，对key进行哈希计算，确定此key在环上的位置
然后，从这个位置沿着顺时针方向走，遇到的第一节点就是存储key的节点

2. 使用场景是什么

在负载均衡问题中，不同的负载均衡算法对应不同的分配策略，适应的业务场景也不同。

最简单的方式是引入一个中间的负载均衡层，让它将外界的请求"轮流"转发给内部的集群
考虑到每个节点的硬件配置有所区别，可以引入权重值，将硬件配置更好的节点的权重值设高，然后根据各个节点的权重值，按照一定比重分配在不同的节点上，让硬件配置更好的节点承担更多的请求，这种算法叫做加权轮询

但是，加权轮询算法无法应对"分布式系统（数据分片的系统）"，因为分布式系统中，每个节点存储的数据是不同的。例如，一个分布式KV（key-value）缓存系统，某个key应该到哪个或者哪些节点上获得，应该是确定的，不是说任意访问一个节点都可以得到缓存结果的。

3. 使用哈希算法的问题

哈希算法能够对同一个关键字进行哈希计算，每次计算都是相同的值，这样就可以将某个key确定到一个节点，可以满足分布式系统的负载均衡需求。但是存在致命问题：如果节点数量发生了变化，也就是在对系统做扩容或缩容时，必须迁移改变了映射关系的数据，否则会出现查询不到数据的问题。

要解决这个问题的办法，就需要进行数据迁移。例如，节点的数量从3变化为4时，要基于新的计算公式hash(key) % 4，重新对数据和节点做映射。假设总数据条数为M，哈希算法在面对节点数量变化时，最坏情况下所有数据都需要迁移，所以它的数据迁移规模是O(M)，这样数据的迁移成本太高了。

4. 一致性哈希算法进阶

4.1 一致性哈希算法存在的问题

一致性哈希算法并不保证节点能够在哈希环上分布均匀，这样就会带来一个问题，会有大量的请求集中在一个节点上。

上图中如果节点A被移除了，当节点A宕机后，根据一致性哈希算法的规则，其上数据应该全部迁移到相邻的节点B上，这样，节点B的数据量、访问量都会迅速增加很多倍，一旦新增的压力超过了节点B的处理能力上限，就会导致节点B崩溃，进而形成雪崩式的连锁反应。

所以，一致性哈希算法虽然减少了数据迁移量，但是存在节点分布不均匀的问题。

4.2 通过虚拟节点提高均衡度

要想解决节点能在哈希环上分配不均匀的问题，就是要有大量的节点，节点数越多，哈希环上的节点分布的就越均匀。但问题是，实际中我们没有那么多节点。所以这个时候我们就加入虚拟节点，也就是对一个真实节点做多个副本。

具体做法是，不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，所以这里有"两层"映射关系。

例如，对每个节点分别设置3个虚拟节点：

对节点A加上编号来作为虚拟节点：A-01、A-02、A-03
对节点B加上编号来作为虚拟节点：B-01、B-02、B-03
对节点C加上编号来作为虚拟节点：C-01、C-02、C-03

引入虚拟节点后，原本哈希环上只有3个节点的情况，就会变成有9个虚拟节点映射到哈希环上，哈希环上的节点数量多了3倍。

节点数量多了后，节点在哈希环上的分布就相对均匀了。这时候，如果有访问请求寻址到"A-01"这个虚拟节点，接着再通过"A-01"虚拟节点找到真实节点A，这样请求就能访问到真实节点A了。

总结：

一个真实节点对应N个虚拟节点
一个虚拟节点对应N个key

5. 代码实现

下面是用Go实现的代码：

import (
    "hash/crc32"
    "sort"
    "strconv"
)

// Hash map bytes to uint32
type Hash func(data []byte) uint32

// 包含所有的hashed keys
type Map struct {
    hash     Hash           //Hash 函数
    replicas int            //虚拟节点倍数
    keys     []int          //虚拟节点的哈希环
    hashMap  map[int]string //虚拟节点与真实节点的映射表,键是虚拟节点的哈希值，值是真实节点的名称。
}

// New create a Map instance
func New(replicas int, fn Hash) *Map {
    m := &Map{
        replicas: replicas,
        hash:     fn,
        hashMap:  make(map[int]string),
    }
    if m.hash == nil {
        m.hash = crc32.ChecksumIEEE
    }
    return m
}

func (m *Map) Add(keys ...string) {
    for _, key := range keys {
        for i := 0; i < m.replicas; i++ {
            // 虚拟节点在哈希环上的hash值
            hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
            m.keys = append(m.keys, hash)
            // 虚拟节点和真实节点的映射
            m.hashMap[hash] = key
        }
    }
    sort.Ints(m.keys)
}

func (m *Map) Get(key string) string {
    if len(m.keys) == 0 {
        return ""
    }
    // 要查询的key的hash
    hash := int(m.hash([]byte(key)))
    // 找到最近的虚拟节点对应的下标idx
    idx := sort.Search(len(m.keys), func(i int) bool {
        return m.keys[i] >= hash
    })
    //顺时针找到第一个匹配的虚拟节点的下标 idx，从 m.keys 中获取到对应的哈希值。如果 idx == len(m.keys)，说明应选择 m.keys[0]，因为 m.keys 是一个环状结构，所以用取余数的方式来处理这种情况。
    //m.keys[idx%len(m.keys)]获得虚拟节点的hash
    //根据虚拟节点的hash值获取真实节点
    return m.hashMap[m.keys[idx%len(m.keys)]]
}