文先生的博客 求职,坐标深圳。(wenfh2020@126.com)

[算法] 一致性哈希算法

2024-01-08

一致性哈希算法,是后端比较常用的一种数据路由策略。本文介绍一下它的算法原理,以及使用场景。


1. 应用场景

一致性哈希算法,是后端比较常用的一种数据路由策略,它主要解决了两个问题:

  1. 数据比较均匀地路由到各个节点(负载均衡)。
  2. 当对应的服务集群节点发生抖动(添加,删除)时,数据路由的路径变化不会很大,这样避免了服务节点上的用户数据缓存出现大面积失效。

2. 原理

  • 实体节点,通过哈希算法模拟出一层虚拟节点进行映射,并将虚拟节点相对均匀地插入到哈希环上。
  • 用户通过哈希环,顺时针查找与哈希值相近的虚拟节点,再通过虚拟节点的映射,从而找到对应的实体节点。

3. 算法实现

3.1. 哈希环

std::map 是有序的键值对容器,可以通过它实现哈希环,将虚拟节点添加到哈希环上,实现虚拟节点和实体节点进行映射。

1
2
3
4
5
6
class Nodes {
  private:
    /* 虚拟节点到真实节点的映射。
    * key: vnode(hash) -> node. */
    typedef std::map<uint32_t, node_t*> VNODE2NODE_MAP;
};

3.2. 创建虚拟节点

创建分布均匀的散列虚拟节点(虚拟节点 其实是一个 uint32_t 的哈希数值)。

为了让虚拟节点,能在哈希环上均匀分布,采用对真实节点信息进行组合,生成 16 个字节的 md5 字符串,该字符串分为 4 组,每组 4 个字节,4 个字节的字符串通过移位组合成 4 个字节的 uint32 key。因为 md5 字符串里面的字母都是随机的,理论上,随机产生的数据应该是均匀的。这样 200 个散列 key 能映射到实体节点上,这样比较符合一致性哈希算法原理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
std::vector<uint32_t>
Nodes::gen_vnodes(const std::string& node_id) {
    std::string s;
    int hash_point = 4;
    std::vector<uint32_t> vnodes;

    /* 为了兼顾性能,可以默认每个真实节点生成对应的 200 个虚拟节点。*/
    for (int i = 0; i < m_vnode_cnt / hash_point; i++) {
        s = md5(format_str("%d@%s#%d", m_vnode_cnt - i, node_id.c_str(), i));
        for (int j = 0; j < hash_point; j++) {
            uint32_t v = ((uint32_t)(s[3 + j * hash_point] & 0xFF) << 24) |
                         ((uint32_t)(s[2 + j * hash_point] & 0xFF) << 16) |
                         ((uint32_t)(s[1 + j * hash_point] & 0xFF) << 8) |
                         (s[j * hash_point] & 0xFF);
            vnodes.push_back(v);
        }
    }
    return vnodes;
}

3.3. 哈希转换

用户数据,通过对应的哈希算法进行哈希,得出一个哈希值,通过该哈希值,到哈希环上查找虚拟节点。

1
2
3
4
5
6
7
8
9
uint32_t Nodes::hash(const std::string& obj) {
    if (m_ha == HASH_ALGORITHM::FNV1_64) {
        return hash_fnv1_64(obj.c_str(), obj.size());
    } else if (m_ha == HASH_ALGORITHM::MURMUR3_32) {
        return murmur3_32(obj.c_str(), obj.size(), 0x000001b3);
    } else {
        return hash_fnv1a_64(obj.c_str(), obj.size());
    }
}

4. 服务应用实现

4.1. 数据结构

  • 为了节点发现,发送给 zookeeper 的节点信息,为了方便服务之间数据交换,设计成 protobuf 结构。
1
2
3
4
5
6
7
8
/* 节点发现信息。 */
message zk_node {
    string path = 1;       /* zookeeper path. store which return from zk. */
    string type = 2 ;      /* node type. */
    string ip = 3;         /* node ip. */
    uint32 port = 4;       /* node port. */
    uint32 worker_cnt = 5; /* node worker count. */
}
  • 真实节点的节点信息。保存了与它建立映射的虚拟节点,方便删除操作。
1
2
3
4
5
6
7
8
9
/* 真实节点信息。 */
typedef struct node_s {
    std::string id;               /* node id: "ip:port.worker_index" */
    std::string type;             /* node type. */
    std::string ip;               /* node ip. */
    int port;                     /* node port. */
    std::vector<uint32_t> vnodes; /* virtual nodes which point to me. */
    double active_time;           /* time for checking online. */
} node_t;
  • 一致性哈希节点管理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Nodes {
  private:
    /* 真实节点信息。
    * key: node_id, value: node info. */
    std::unordered_map<std::string, node_t*> m_nodes;

    /* 虚拟节点到真实节点的映射。
    * key: vnode(hash) -> node. */
    typedef std::map<uint32_t, node_t*> VNODE2NODE_MAP;

    /* 服务集群里有不同类型的服务节点,需要根据节点类型分类节点。
    * key: node type, value: (vnodes -> node) */
    std::unordered_map<std::string, VNODE2NODE_MAP> m_vnodes;
};

4.2. 接口

4.2.1. 添加节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
bool
Nodes::add_node(const std::string& node_type, const std::string& ip, int port, int worker) {
    LOG_INFO("add node, node type: %s, ip: %s, port: %d, worker: %d",
             node_type.c_str(), ip.c_str(), port, worker);

    /* 每个真实节点信息,将它的数据格式化出一个对应 id(ip:port.worker_index),方便查找。*/
    std::string node_id = format_identity(ip, port, worker);
    if (m_nodes.find(node_id) != m_nodes.end()) {
        LOG_DEBUG("node (%s) has been added!", node_id.c_str());
        return true;
    }

    /* 真实节点信息。 */
    node_t* node;
    /* 虚拟节点数组。 */
    std::vector<uint32_t> vnodes;
    /* 虚拟节点映射真实节点。 */
    VNODE2NODE_MAP& vnode2node = m_vnodes[node_type];
    int old_vnode_cnt = vnode2node.size();

    /* 为真实节点生成虚拟节点。 */
    vnodes = gen_vnodes(node_id);
    node = new node_t{node_id, node_type, ip, port, vnodes, time_now()};

    /* 虚拟节点与真实节点建立映射。 */
    for (auto& v : vnodes) {
        if (!vnode2node.insert({v, node}).second) {
            LOG_WARN(
                "duplicate virtual nodes! "
                "vnode: %lu, node type: %s, ip: %s, port: %d, worker: %d.",
                v, node_type.c_str(), ip.c_str(), port, worker);
            continue;
        }
    }

    if (vnode2node.size() == old_vnode_cnt) {
        LOG_ERROR("add virtual nodes failed! node id: %s, node type: %s",
                  node->id.c_str(), node->type.c_str());
        SAFE_DELETE(node);
        return false;
    }

    m_nodes[node_id] = node;
    return true;
}

4.2.2. 删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool Nodes::del_node(const std::string& node_id) {
    LOG_INFO("delete node: %s", node_id.c_str());
    auto it = m_nodes.find(node_id);
    if (it == m_nodes.end()) {
        return false;
    }

    /* clear vnode. */
    node_t* node = it->second;
    auto itr = m_vnodes.find(node->type);
    if (itr != m_vnodes.end()) {
        /* 删除真实节点映射的所有虚拟节点。 */
        for (auto& v : node->vnodes) {
            itr->second.erase(v);
        }
    }

    /* 删除真实节点。 */
    LOG_INFO("delete node: %s done!", node->id.c_str());
    delete node;
    m_nodes.erase(it);
    return true;
}

4.2.3. 获取节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
node_t* Nodes::get_node_in_hash(const std::string& node_type, const std::string& obj) {
    auto it = m_vnodes.find(node_type);
    if (it == m_vnodes.end()) {
        return nullptr;
    }

    /* obj 通过哈希算法,生成一个 uint32_t 的哈希键。 */
    uint32_t hash_key = hash(obj);
    const VNODE2NODE_MAP& vnode2node = it->second;
    if (vnode2node.size() == 0) {
        LOG_WARN(
            "can't not find node in virtual nodes. node type: %s, obj: %s, hash key: %lu",
            node_type.c_str(), obj.c_str(), hash_key);
        return nullptr;
    }

    /* 顺时针查找不小于哈希键的最小的一个虚拟节点(虚拟节点是一个 uint32_t 数值)。*/
    auto itr = vnode2node.lower_bound(hash_key);
    if (itr == vnode2node.end()) {
        itr = vnode2node.begin();
    }
    return itr->second;
}

4.3. 测试结果

4.3.1. 数据分布

模拟 1000 w 个不同用户,它们路由到 10 个节点上的数据分布情况,每个节点数据量相差不大,分布基本均匀,在 100w 上下浮动,但是最大值和最小值相差 23.5 %,所以这个分布算法还有改进空间。

(1087975-880813) / 880813.0 == 0.235194076382

节点数据分布情况


4.3.2. 增加节点

增加节点后,旧节点上的数据变化情况,下图主要显示了每次增加节点后,数据仍然路由到原节点的百分比,节点越多,节点上的数据变化越稳定。

增加节点数据变化


4.3.3. 删除节点

删除节点,剩余节点上的原有数据位置没有变化,被删除节点上的数据,将重新路由到剩余节点中去。重新路由的数据分布情况请参考上面说的 数据分布

既然旧节点上的原有数据没变化就不上图了,这也符合一致性哈希算法预期。


5. 性能开销

下图是节点数据通信压力测试火焰图,查找虚拟节点这个接口的调用就占了整个系统性能的 2.81%,损耗不大,单系统就是这样,每添加一个新的功能,都会蚕食系统的整体性能,累积下来,损耗就是一个很可观的数字了。

火焰图负载

火焰图参考:如何生成火焰图🔥


作者公众号
微信公众号,干货持续更新~