0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

一致性哈希算法简介

算法与数据结构 来源:labuladong 2023-04-04 11:53 次阅读

最近有一位读者跟我交流,说除了算法题之外,系统设计题是一大痛点。算法题起码有很多刷题平台可以动手实践,但系统设计类的题目一般很难实践,所以看一些教程总结也只是一知半解,遇到让写代码实现系统的就懵了。

比如他最近被问到一个大型爬虫系统的设计题,让手写一致性哈希算法,加上一系列 follow up,就被难住了。

说实话这个算法的实现并不难,所以本文就结合一致性哈希算法在工程中的应用场景介绍一下这个算法算法,并给出代码实现,避免大家重蹈覆辙。

一致性哈希算法简介

这个名词大家肯定不陌生,应该也大概理解这个算法的逻辑,不过我这里还是要再介绍一下。

一致性哈希主要解决把数据平均分配到多个节点上的问题,并且某些节点上线/下线后依然能够做到自动负载均衡。

其原理就是抽象出一个哈希环,把服务器节点的 id 通过哈希函数映射到这个哈希环上:

ca0e0d10-d298-11ed-bfe3-dac502259ad0.jpg

同时,把需要处理的数据也通过哈希函数映射到这个哈希环上,然后顺时针找,遇到的第一个服务器节点来负责处理这个数据:

ca202ab8-d298-11ed-bfe3-dac502259ad0.jpg

这样一来,我们其实已经提供了一种机制将若干数据分布在若干服务节点上了,不妨称它为 V1 版本的一致性哈希算法。

但 V1 版本的算法还有问题:负载分布很可能不均衡。由于哈希函数的结果是难以预测的,所以可能出现这种情况:

ca2baf28-d298-11ed-bfe3-dac502259ad0.jpg

即某些服务器节点要负责的哈希环很长,而其他服务器负责的哈希环很短。这就会导致某些服务器负载很高,而其他的服务器负载很低,很不均衡。

而且,当某个服务器节点下线后,它的负载会顺时针转移到下一个节点上,那么某些特定的节点下线顺序很可能导致某些服务器节点负责的哈希环不断加长,负载不断增加。专业点说,这就是「数据倾斜」。

如何解决数据倾斜的问题呢?可以给每个服务器节点添加若干「虚拟节点」分布在哈希环上,我们不妨称其为 V2 版的一致性哈希算法:

ca39e728-d298-11ed-bfe3-dac502259ad0.jpg

上图给每个 Node 设置了 4 个虚拟节点,这样一来,由于哈希函数的随机性,每个服务器节点的虚拟节点能够平均分布在哈希环上,那么数据就能够比较均匀地分配到所有服务器节点上。

如果某个服务器节点下线,那么该服务器节点的所有虚拟节点都会从哈希环上摘除,它们的负载会迁移到顺时针的下一个服务器节点上。

和 V1 版算法不同的是,因为虚拟节点有多个,它们的下一位不太可能是同一台服务器的虚拟节点,所以它们的负载大概率会均分到多台服务器的虚拟节点上。

综上,V2 版算法通过虚拟节点的方式完美解决了数据倾斜的问题,是不是很巧妙?不过俗话说,纸上得来终觉浅,绝知此事要躬行,我们需要实践才能真正写出正确的一致性哈希算法。

比方说,应该用什么数据结构实现哈希环?如果哈希函数出现哈希冲突怎么办?真正写代码的时候,这些细节问题都是要考虑的。

下面我们就结合代码和实际场景来看看一致性哈希算法的真实应用

实际场景分析

就以消息队列的消费模型为例吧,我在前文用消息队列做一个联机游戏介绍过 Apache Pulsar 的消费模型,Pulsar 通过 subscription 的抽象提供多种订阅模式,其中 key_shared 模式比较有意思:

每条消息会有一个 key,Pulsar 可以根据这个 key 分发消息,保证带有相同 key 的消息分发到同一个消费者上。

官网的这幅图比较好理解,图中的K就是指消息的 key,V就是指消息的数据:

ca532dfa-d298-11ed-bfe3-dac502259ad0.png

通过某些算法,所有的消息都会有消费者去处理,比如上图就是consumerA负责处理key=K3的消息,consumerB负责处理key=K1的消息,consumerC负责处理key=K2的消息。

当然,如果有 consumer 加入或者离开,消息的分配会重置。比如consumerA下线,那么key=K3的消息会被分配给其他消费者消费;如果有新的消费者consumerD加入,那么当前的分配方案也可能会改变。

简单总结就是:

1、在没有 consumer 加入或者离开的前提下,保证 key 相同的消息都会分配到固定的 consumer,不能一会儿分配到consumerA,一会儿分配给consumerB。

2、如果有 consumer 加入或者离开,可以重新进行分配每个 consumer 负责的 key,要求尽量把 key 平均分配给 consumer,避免出现某些 consumer 负责过多 key 的情况导致数据倾斜。

3、以上两个操作,尤其是给 consumer 重新分配 key 的操作,效率要尽可能高。

对于上述场景,你如何设计分配算法,把这些带有 key 的消息高效地、均匀地分配给所有 consumer 呢

我们来看看 Pulsar 是如何做的,官网对这部分的实现原理描述的比较清楚,参考链接如下:

https://pulsar.apache.org/docs/next/concepts-messaging/#key_shared

结合我之前在学习开源项目的套路中介绍的查看源码背景信息的技巧,可以发现 Pulsar 的 key_shared 模式的消费者实现其实是经历了一些演进的。

最开始的默认实现方式叫做 Auto-split Hash Range,即抽象出来一个[0, 65535]的哈希区间,让每个 consumer 负责这个区间的一部分。比如有C1~C44 个 consumer,那么它们会平分整个哈希区间:

016,38432,76849,15265,536
|-------C3------|-------C2------|-------C4------|-------C1------|

然后我们可以对每条消息的 key 计算哈希值并求模映射到[0, 65535]的区间中,这样我们就可以选出负责处理这条消息的 consumer 了,而且 key 相同的消息总会分配到这个 consumer 上。

那么如果有 consumer 上线或者下线怎么处理呢?

如果有 consumer 下线,那么它负责的哈希区间会直接交给右侧的 consumer。比如上例中C4下线,那么哈希区间就会变成这样:

016,38432,76865,536
|-------C3------|-------C2------|----------------C1---------------|

当然这里也有个特殊情况,就是下线的那个 consumer 右边没有其他 consumer 的情况,我们可以让它左边的 consumer 顶上来。比如现在的C1下线,那么就让左边的C2负责C1的区间:

016,38465,536
|-------C3------|--------------------------C2-----------------------|

如果有 consumer 上线,那么算法可以把最长的哈希区间平分,分一半给新来的 consumer。比如此时C5上线,我们就可以把C2负责的一半哈希区间分给C5:

016,38440,96065,536
|-------C3------|-----------C5-----------|----------C2----------|

这就是 Auto-split Hash Range 的方案,不算复杂,具体的实现可以看 Pulsar 源码中HashRangeAutoSplitStickyKeyConsumerSelector这个类,我在这里就不列举了。

这个方案的问题主要还是数据倾斜,比如上面的例子出现的这种情况,C2的负载显然比C3多很多:

016,38465,536
|-------C3------|--------------------------C2-----------------------|

按照这个算法逻辑,一些 consumer 下线后很容易产生这种数据倾斜的情况,所以这个解决方案并不能均匀地把 key 分配给 consumer

那么如何优化这个算法呢?就要用到一致性哈希算法了。

一致性哈希算法的实现

结合我在本文开头对一致性哈希算法的介绍,应该很容易想到优化思路。其实现在 Pulsar 就是使用一致性哈希算法来实现的 key_shared 订阅。

首先抽象出一个值在[0, MAX_INT]的哈希环,然后给每个 consumer 分配 100 个虚拟节点映射到这个哈希环上。接下来,我们把 key 的哈希值放在哈希环上,顺时针方向找到最近的 consumer 虚拟节点,也就找到了负责处理这个 key 的 consumer。

哈希环我们一般用 TreeMap 实现,直接看 Pulsar 源码中ConsistentHashingStickyKeyConsumerSelector的实现吧,我提取了其中的关键逻辑并添加了详细的注释:

classConsistentHashingStickyKeyConsumerSelector{
//哈希环,虚拟节点的哈希值->consumer列表
//因为存在哈希冲突,多个虚拟节点可能映射到同一个哈希值,所以值为List类型
NavigableMap>hashRing=newTreeMap<>();
//每个consumer有100个虚拟节点
intnumberOfPoints=100;

//将该consumer的100个虚拟节点添加到哈希环上
publicvoidaddConsumer(Consumerconsumer){
for(inti=0;i< numberOfPoints; i++) {
            // 计算虚拟节点在哈希环上的位置
            String key = consumer.consumerName() + i;
            int hash = Murmur3_32Hash.getInstance().makeHash(key.getBytes());
            // 把虚拟节点放到哈希环上
            hashRing.putIfAbsent(hash, new ArrayList<>());
hashRing.get(hash).add(consumer);
}
}

//在哈希环上删除该consumer的所有虚拟节点
publicvoidremoveConsumer(Consumerconsumer){
for(inti=0;i< numberOfPoints; i++) {
            // 计算虚拟节点在哈希环上的位置
            String key = consumer.consumerName() + i;
            int hash = Murmur3_32Hash.getInstance().makeHash(key.getBytes());
            // 删除虚拟节点
            if (hashRing.containsKey(hash)) {
                hashRing.get(hash).remove(consumer);
            }
        }
    }

    // 通过 key 的哈希值选择 consumer
    public Consumer select(int hash) {
        if (hashRing.isEmpty()) {
            return null;
        }
        // 选择顺时针方向的第一个 consumer
        Map.Entry>ceilingEntry=hashRing.ceilingEntry(hash);
ListconsumerList;
if(ceilingEntry!=null){
consumerList=ceilingEntry.getValue();
}else{
//哈希环顺时针转一圈,回到开头寻找第一个节点
consumerList=hashRing.firstEntry().getValue();
}
//保证相同的key都会分配到同一个consumer
returnconsumerList.get(hash%consumerList.size());
}
}

当消息被发送过来后,Pulsar 可以通过select方法选择对应的 consumer 来处理数据;当新的 consumer 上线时,可以通过addConsumer将它的虚拟节点放到哈希环上并开始接收消息;当有 consumer 下线时,可以通过removeConsumer将它的虚拟节点从哈希环上摘除,由其他 consumer 承担它的工作。

因为每个 consumer 有 100 个虚拟节点,所以在 consumer 下线时,负载其实是均匀地分配给了其他 consumer,因此一致性哈希算法能够解决之前 Auto-split Hash Range 方案数据倾斜的问题。




审核编辑:刘清

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 虚拟机
    +关注

    关注

    1

    文章

    914

    浏览量

    28161
  • 哈希算法
    +关注

    关注

    1

    文章

    56

    浏览量

    10744

原文标题:一致性哈希算法设计题,栽了

文章出处:【微信号:TheAlgorithm,微信公众号:算法与数据结构】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    顺序一致性和TSO一致性分别是什么?SC和TSO到底哪个好?

    内存一致性之顺序一致性(sequential consistency)可以说,最直观的内存一致性模型是sequentially consistent(SC):内存访问执行的顺序与程序指定的顺序相同
    发表于 07-19 14:54

    一致性规划研究

    针对一致性规划的高度求解复杂度,分析主流一致性规划器的求解策略,给出影响一致性规划器性能的主要因素:启发信息的有效,信念状态表示方法的紧凑
    发表于 04-06 08:43 12次下载

    CMP中Cache一致性协议的验证

    CMP是处理器体系结构发展的个重要方向,其中Cache一致性问题的验证是CMP设计中的项重要课题。基于MESI一致性协议,本文建立了CMP的Cache
    发表于 07-20 14:18 38次下载

    加速器一致性接口

    Zynq PS上的加速器一致性接口(Accelerator Coherency Port, ACP)是个兼容AXI3的64位从机接口,连接到SCU(Snoop Control Unit),为PL
    发表于 11-17 15:04 3674次阅读

    分布式一致性算法Yac

    传统静态拓扑主从模型分布式一致性算法存在严重负载不均及单点性能瓶颈效应,且崩溃节点大于集群规模的50qo时算法无法正常工作。针对上述问题,提出基于动态拓扑及有限表决思想的分布式一致性
    发表于 11-27 17:49 0次下载
    分布式<b class='flag-5'>一致性</b><b class='flag-5'>算法</b>Yac

    基于轨迹标签的谣言一致性维护算法

    针对发布/订阅系统中缓存副本一致性维护问题,首先,对原有基于谣言的一致性维护算法进行改进,提出种基于轨迹标签的谣言一致性维护
    发表于 12-17 11:35 0次下载
    基于轨迹标签的谣言<b class='flag-5'>一致性</b>维护<b class='flag-5'>算法</b>

    Cache一致性协议优化研究

    问题的由来.总结了多核时代高速缓存一致性协议设计的关键问题,综述了近年来学术界对一致性的研究.从程序访存行为模式、目录组织结构、一致性粒度、一致性协议流量、目录协议的可扩展性等方面,阐
    发表于 12-30 15:04 0次下载
    Cache<b class='flag-5'>一致性</b>协议优化研究

    优化模型的乘偏好关系一致性改进

    针对乘偏好信息下的决策问题,引入乘偏好关系的有序一致性、满意一致性以及一致性指数等概念,建立以偏差变量最小化为目标函数的优化模型,进而构
    发表于 03-20 17:28 0次下载

    一致性哈希是什么?为什么它是可扩展的分布式系统架构的个必要工具

    在本文中,我们将了解一致性哈希是什么、为什么它是可扩展的分布式系统架构中的个必要工具。
    的头像 发表于 07-17 17:57 4397次阅读

    哈希图一致性算法已被验证为异步拜占庭容错

    HederaHashgraph在下代公共分类帐中拥有多样化的治理。它最近宣布哈希图一致性算法已被验证为异步拜占庭容错。这是通过使用Coq系统的计算机检查的数学证明完成的。
    发表于 10-23 11:07 1856次阅读

    基于改进一致性的多无人机编队控制算法

    基于改进一致性的多无人机编队控制算法
    发表于 06-22 16:02 16次下载

    Dubbo负载均衡策略之一致性哈希

    本文主要讲解了一致性哈希算法的原理以及其存在的数据倾斜的问题,然后引出解决数据倾斜问题的方法,最后分析一致性哈希
    的头像 发表于 06-16 15:30 748次阅读
    Dubbo负载均衡策略之<b class='flag-5'>一致性</b><b class='flag-5'>哈希</b>

    如何保证缓存一致性

    “ 本文的参考文章是2022年HOT 34上Intel Rob Blakenship关于CXL缓存一致性篇介绍。”
    的头像 发表于 10-19 17:42 1093次阅读
    如何保证缓存<b class='flag-5'>一致性</b>

    DDR一致性测试的操作步骤

    DDR一致性测试的操作步骤  DDR(双数据率)一致性测试是对DDR内存模块进行测试以确保其性能和可靠。在进行DDR一致性测试时,需要遵循
    的头像 发表于 02-01 16:24 1508次阅读

    深入理解数据备份的关键原则:应用一致性与崩溃一致性的区别

    深入理解数据备份的关键原则:应用一致性与崩溃一致性的区别 在数字化时代,数据备份成为了企业信息安全的核心环节。但在备份过程中,两个关键概念——应用一致性和崩溃一致性,常常被误解或混淆。
    的头像 发表于 03-11 11:29 900次阅读
    深入理解数据备份的关键原则:应用<b class='flag-5'>一致性</b>与崩溃<b class='flag-5'>一致性</b>的区别