520 · 一致性哈希 II

 

链接:LintCode 炼码 - ChatGPT!更高效的学习体验!

题解: 

class Solution{
  private:
    int n;
    const int mVirtualNodeCount;
    map<int, int> mVirtualNodeToMachineIdMap;
    set<int> mVirtualNodeSet;
  public:
    Solution(int n,int virtualNodeCount):n(n),mVirtualNodeCount(virtualNodeCount){
    }
    // @param n a positive integer
    // @param k a positive integer
    // @return a Solution object
    static Solution create(int n, int virtualNodeCount){
        // Write your code here
        Solution solution = Solution(n,virtualNodeCount);
        return solution;
    }

    // @param machine_id an integer
    // @return a list of shard mSlots
    vector<int> addMachine(int machine_id){
        // 机器对应的虚拟节点
        vector<int> machine_virtualNode;
        // 为该机器随机生成k个虚拟节点
        for (int _ = 0; _ < this->mVirtualNodeCount; ++_){
            // 随机生成一个不在this->mSlots中的槽Id
            int virtualNodeId;
            do{
                virtualNodeId = rand() % this->n;
            } while (this->mVirtualNodeSet.count(virtualNodeId));
            // 将槽Id添加到this->mSlots和random_nums中
            this->mVirtualNodeSet.insert(virtualNodeId);
            machine_virtualNode.push_back(virtualNodeId);
            // 将槽Id与机器向绑定
            this->mVirtualNodeToMachineIdMap[virtualNodeId] = machine_id;
        }
        // 对机器的虚拟节点进行排序,便于展示
        sort(machine_virtualNode.begin(), machine_virtualNode.end());
        return machine_virtualNode;
    }

    // 根据key的hashcode为其指定对应的机器
    // @param hashcode an integer
    // @return a machine id
    int getMachineIdByHashCode(int hashcode){
        // Write your code here
        auto it = this->mVirtualNodeToMachineIdMap.lower_bound(hashcode);
        if (it != mVirtualNodeToMachineIdMap.end())
            return it->second;
        else
            return this->mVirtualNodeToMachineIdMap.begin()->second;
    }
};

24-一致性哈希:如何高效地均衡负载?

你好,我是陶辉。

还记得我们在[第22讲] 谈到的Cassandra数据库吗?它将服务器节点组成一个环来存储数据,所使用的就是一致性哈希算法。那这一讲,我们就来看看一致性哈希算法是怎样工作的。

使用哈希算法扩展系统时,最大的问题在于代表哈希桶的服务器节点数发生变化时,哈希函数就改变了,数据与节点间的映射关系自然发生了变化,结果大量数据就得在服务器间迁移。特别是含有多份冗余数据的系统,迁移工作量更是会成倍提高。

同时,为了在整体上更加充分地使用IT资源,我们必须解决分布式系统扩展时可能出现的两个问题:数据分布不均衡和访问量不均衡。比如,对于包含10个服务器节点、持久化1亿条用户数据的有状态服务,如果采用关键字模10(key%10)的哈希算法作为路由策略,就很难保证每个节点处理1千万条数据,那些可能还未达到一半设计容量的节点会浪费大量磁盘空间。

即使节点间存储的数据非常均匀,但这些数据间的活跃程度也不相同,存放热点数据较多的节点访问量非常大,很容易率先达到CPU瓶颈,在许多主机节点还很空闲时,我们就得扩容系统。

特别是我们很难保证集群内的所有节点都是同构的,如果哈希算法不能区别对待不同配置的服务器,也会抬高IT成本。

一致性哈希算法可以解决上述问题,它在许多流行的开源软件上都有很广泛的应用。这一讲我们将介绍一致性哈希算法的工作原理,以及如何通过虚拟节点提升算法的均衡性。

如何减少扩容、缩容时迁移的数据量?

在主机硬件达到性能瓶颈后,有状态服务可以沿AKF立方体Z轴(参见[第21讲]),基于哈希算法扩展为分布式系统。下图系统中拥有5个节点,哈希算法将每条数据的关键字模5得出的数字作为哈希桶序号,从而将数据映射到节点上(如果关键字是字符串或者其他结构化数据,可以先通过其他哈希算法转换为整数,再进行模运算):

这个方案实现简单,运算速度也快,但它最大的问题是在系统扩容或者缩容时,必须迁移改变了映射关系的数据。然而,取模哈希函数中基数的变化,往往会导致绝大部分映射关系改变,比如上例中的5个关键字,在下图中集群节点数(即基数)从5降为4时,原映射关系全部失效,这5条数据都得迁移到其他节点:

1997年发布的《Consistent Hashing and Random Trees》论文提出了一致性哈希算法,可以大幅度减少数据迁移量。一致性哈希算法是通过以下2个步骤来建立数据与主机节点间映射关系的:

  • 首先,将关键字经由通用的哈希函数映射为32位整型哈希值。这些哈希值会形成1个环,最大的数字 ${2^{32}}$ 相当于0。
  • 其次,设集群节点数为N,将哈希环由小至大分成N段,每个主机节点处理哈希值落在该段内的数据。比如下图中,当节点数N等于3且均匀地分段时,节点0处理哈希值在 [0, $\frac{1}{3} * {2^{32}}$] 范围内的关键字,节点1处理 [$\frac{1}{3} * {2^{32}}$, $\frac{2}{3} * {2^{32}}$] 范围内的关键字,而节点2则处理的范围是 [$\frac{2}{3} * {2^{32}}$, ${2^{32}}$]:

当然,在生产环境中主机节点很可能是异构的,所以我们要给高规格的服务器节点赋予更高的权重。一致性哈希算法改变节点的权重非常简单,只需要给每个节点分配更大的弧长即可。例如,如果上图中的节点0拥有更高的硬件配置,那么可以将原本均匀分布的3个节点调整为2:1:1的权重,这样节点0处理的哈希值范围调整为 [0, ${2^{31}}$],节点1的处理范围调整为 [${2^{31}}$, ${3} * {2^{30}}$],节点2的处理范围调整为 [${3} * {2^{30}}$, ${2^{32}}$],如下图所示:

而扩容、缩容时,虽然节点数发生了变化,但只要小幅度调整环上各节点的位置,就不会导致大量数据的迁移。比如下图中我们将3个节点的集群扩容为4个节点,只需要将节点0上一半的数据迁移至节点3即可,其他节点不受影响:

接下来我们从成本上分析下一致性哈希算法的优劣。假设总数据条数为M,而节点个数为N,先来看映射函数的时间复杂度。传统的哈希算法以N为基数执行取模运算,时间复杂度为O(1)(参见[第3讲]);一致性哈希算法需要将关键字先转换为32位整型(这1步的时间复杂度也是O(1)),再根据哈希环中各节点的处理范围,找到所属的节点。由于所有节点是有序排列的,所以采用二分法,可以在O(logN)时间复杂度内,完成关键字到节点位置的映射。

再来评估下数据的迁移规模。节点变化会导致传统哈希算法的映射结果不可控,最坏情况下所有数据都需要迁移,所以它的数据迁移规模是O(M);对于一致性哈希算法,我们可以通过调整节点位置,任意设定迁移规模。在环中各节点均匀分布的情况下,数据迁移规模是O(M/N)。

因此,一致性哈希算法的缺点是将映射函数的时间复杂度从O(1)提高到了O(logN),它的优点是将数据迁移规模从O(M)降低至O(M/N)。由于数据条数M远大于主机节点数N,而且数据迁移的成本很大,所以一致性哈希算法更划算,它的适用场景也更广!

如何通过虚拟节点提高均衡度?

一致性哈希算法虽然降低了数据的迁移量,但却遗留了两个问题没有解决。

首先,如果映射后哈希环中的数字分布不均匀,就会导致各节点处理的数据不均衡,从而降低了系统的运行效率与性能。在无法找出分布规律时,我们也无法通过调整环中节点的权重,平衡各节点处理的数据量。

其次,容灾与扩容时,哈希环上的相邻节点容易受到过大影响。比如下图中,当节点0宕机后,根据一致性哈希算法的规则,其上数据应该全部迁移到相邻的节点1上,这样,节点1的数据量、访问量都会迅速增加1倍,一旦新增的压力超过了节点1的处理能力上限,就会导致节点1崩溃,进而形成雪崩式的连锁反应:

系统扩容时也面临着同样的问题,除非同时调整环中各节点的位置,否则扩容节点也只会减轻相邻节点的负载。

当数据存在多份冗余时,这两类问题会被进一步放大。

那如何提高均衡性呢?在真实的数据节点与哈希环之间引入一个虚拟节点层,就可以解决上述问题。例如下图中的集群含有4个节点,但我们并不直接将哈希环分为4份,而是将它均匀地分为32份并赋予32个虚拟节点,因此每个虚拟节点会处理 ${2^{27}}$ 个哈希值,再将32个虚拟节点通过某个哈希函数(比如CRC32)映射到4个真实节点上(比如图中8个绿色虚拟节点皆由同色的主机节点0处理):

这样,如果图中绿色的节点0宕机,按照哈希环上数据的迁移规则,8个绿色虚拟节点上的数据就会沿着顺时针方向,分别迁移至相邻的虚拟节点上,最终会迁移到真实节点1(橙色)、节点2(蓝色)、节点3(水红色)上。所以,宕机节点上的数据会迁移到其他所有节点上。

扩容时也是一样的,通过虚拟节点环,新增节点可以分担现有全部节点的压力。至于虚拟节点为什么可以让数据的分布更均衡,这是因为在虚拟节点与真实节点间,又增加了一层哈希映射,哈希函数会将原本不均匀的数字进一步打散。上图为了方便你理解,每个真实节点仅包含4个虚拟节点,这样能起到的均衡效果其实很有限。而在实际的工程中,虚拟节点的数量会大很多,比如Nginx的一致性哈希算法,每个权重为1的真实节点就含有160个虚拟节点。

当然,有了虚拟节点后,为异构的服务器节点设置权重也更方便。只需要为权重高的真实节点,赋予更多的虚拟节点即可。注意,虚拟节点增多虽然会提升均衡性,但也会消耗更多的内存与计算力。

上面我们仅讨论了数据分布的均衡性,当热点数据导致访问量不均衡时,因为这一新维度的信息还没有反馈在系统中,所以你需要搜集各节点的访问量信息,基于它来动态地调整真实节点的权重,进而从热点数据更多的节点中迁移出部分数据,以此提高均衡性。

小结

这一讲我们介绍了一致性哈希算法的工作原理。

传统哈希函数中,主机节点的变化会导致大量数据发生迁移。一致性哈希算法将32位哈希值构成环,并将它分段赋予各节点,这样,扩容、缩容动作就只影响相邻节点,大幅度减少了数据迁移量。一致性哈希算法虽然将数据的迁移量从O(M)降为O(M/N),却也将映射函数的时间复杂度从O(1)提高到O(logN),但由于节点数量N并不会很大,所以一致性哈希算法的性价比还是很高的。

当哈希值分布不均匀时,数据分布也不会均衡。在哈希环与真实节点间,添加虚拟节点层,可以通过新的哈希函数,分散不均匀的数据。每个真实节点含有的虚拟节点数越多,数据分布便会越均衡,但同时也会消耗更多的内存与计算力。

虚拟节点带来的最大优点,是宕机时由所有节点共同分担流量缺口,这避免了可能产生的雪崩效应。同时,扩容的新节点也会分流所有节点的压力,这也提升了系统整体资源的利用率。

思考题

最后,留给你一道思考题。提升数据分布、访问的平衡性,并不是只有一致性哈希这一个方案。比如,我们将数据与节点的映射关系放在另一个服务中持久化存储,通过反向代理或者客户端SDK,在访问数据节点前,先从元数据服务中获取到数据的映射关系,再访问对应的节点,也是可以的,如下图所示:

你觉得上述方案与一致性哈希相比,有何优劣?各自适用的场景又是什么?欢迎你在留言区与大家一起探讨。

感谢阅读,如果你觉得这节课让你掌握了一致性哈希算法这个新工具,并能够用它提升分布式系统的运行效率,也欢迎把今天的内容分享给你的朋友。

精选留言:

  • 唐朝首都 2020-07-03 09:03:24

    中心化元数据服务:
    (1)优点:寻找效率更高;集群维护更为集中高效。
    (2)缺点:单点故障;性能、容量存在扩展的上限。
    (3)适用场景:不太适用于大量小文件的场景。 [1赞]


  • 唐朝首都 2020-07-03 09:03:10

    中心化元数据服务:
    (1)优点:寻找效率更高;集群维护更为集中高效。
    (2)缺点:单点故障;性能、容量存在扩展的上限。
    (3)适用场景:不太适用于大量小文件的场景。


  • test 2020-07-03 08:50:08

    使用存储的话,需要维护多一个服务,以及该服务的可靠性、可用性,优点是不需要实时计算哈希值,减少了算力的需要。


  • 0xFE 2020-07-03 08:50:07

    不知道三层交换机上是否有相关一致性哈希的配置,目前接入层的流量就不太均衡😂

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/50325.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SpringBoot房屋租赁系统【附ppt|万字文档(LW)和搭建文档】

主要功能 前台登录&#xff1a; ①首页&#xff1a;公告信息、房屋信息展示、查看更多等 ②房屋信息、房屋类型、我要当房主、公告信息、留言反馈等 ③个人中心&#xff1a;可以查看自己的信息、更新图片、更新信息、退出登录、我的收藏 后台登录&#xff1a; ①首页、个人中心…

软件测试-基础阶段学习

目录 一、测试介绍 二、测试常用分类 三、模型 四、测试流程 五、测试用例 六、用例设计方法 七、缺陷 八、html 资料获取方法 阶段目标 能独立针对web项目实施功能测试 一、测试介绍 什么是软件测试 使用技术手段验证软件是否满足需求 测试主流技能 功能测试自…

golang,gin框架的请求参数(一)--推荐

golang&#xff0c;gin框架的请求参数&#xff08;一&#xff09; gin框架的重要性不过多的强调&#xff0c;重点就gin使用中的参数传递&#xff0c;获取进行梳理文件&#xff0c;满足使用需求。 获取前端请求参数的几种方法&#xff1a; 一、获取参数【浏览器地址获取参数】…

【业务功能篇58】Springboot + Spring Security 权限管理 【中篇】

4.2.3 认证 4.2.3.1 什么是认证&#xff08;Authentication&#xff09; 通俗地讲就是验证当前用户的身份&#xff0c;证明“你是你自己”&#xff08;比如&#xff1a;你每天上下班打卡&#xff0c;都需要通过指纹打卡&#xff0c;当你的指纹和系统里录入的指纹相匹配时&…

图注意力网络论文详解和PyTorch实现

图神经网络(gnn)是一类功能强大的神经网络&#xff0c;它对图结构数据进行操作。它们通过从节点的局部邻域聚合信息来学习节点表示(嵌入)。这个概念在图表示学习文献中被称为“消息传递”。 消息(嵌入)通过多个GNN层在图中的节点之间传递。每个节点聚合来自其邻居的消息以更新其…

【小白必看】Python爬虫实战之批量下载女神图片并保存到本地

文章目录 前言运行结果部分图片1. 引入所需库2. 发送请求获取网页内容3. 解析网页内容并提取图片地址和名称4. 下载并保存图片完整代码关键代码讲解 结束语 前言 爬取网络上的图片是一种常见的需求&#xff0c;它可以帮助我们批量下载大量图片并进行后续处理。本文将介绍如何使…

django学习笔记(1)

django创建项目 先创建一个文件夹用来放django的项目&#xff0c;我这里是My_Django_it 之后打开到该文件下&#xff0c;并用下面的指令来创建myDjango1项目 D:\>cd My_Django_itD:\My_Django_it>"D:\zzu_it\Django_learn\Scripts\django-admin.exe" startpr…

echarts遇到的问题

文章目录 折线图-区域面积图 areaStyley轴只有整数y轴不从0开始y轴数值不确定&#xff0c;有大有小&#xff0c;需要动态处理折线-显示label标线legend的格式化和默认选中状态x轴的lable超长处理x轴的相关设置 echarts各个场景遇到的问题 折线图-区域面积图 areaStyle areaStyl…

分库分表之基于Shardingjdbc+docker+mysql主从架构实现读写分离(二)

说明&#xff1a;如果实现了docker部署mysql并完成主从复制的话再继续&#xff0c;本篇文章主要说明springboot配置实现Shardingjdbc进行读写分离操作。 如果没实现docker部署mysql实现主从架构的话点击我 Shardingjdbc配置介绍&#xff08;版本&#xff1a;5.3.2&#xff09;…

STM32 Flash学习(一)

STM32 FLASH简介 不同型号的STM32&#xff0c;其Flash容量也不同。 MiniSTM32开发板选择的STM32F103RCT6的FLASH容量为256K字节&#xff0c;属于大容量产品。 STM32的闪存模块由&#xff1a;主存储器、信息块和闪存存储器接口寄存器等3部分组成。 主存储器&#xff0c;该部分…

linux 指令 第3期

cat cat 指令&#xff1a; 首先我们知道一个文件内容属性 我们对文件操作就有两个方面&#xff1a;对文件内容和属性的操作 扩展&#xff1a;echo 指令 直接打印echo后面跟的字符串 看&#xff1a; 这其实是把它打印到了显示器上&#xff0c;我们也可以改变一下它的打印位置…

工业边缘计算为什么?

在工厂环境中使用边缘计算并不新鲜。可编程逻辑控制器&#xff08;PLC&#xff09;、微控制器、服务器和PC进行本地数据处理&#xff0c;甚至是微型数据中心都是边缘技术&#xff0c;已经在工厂系统中存在了几十年。在车间里看到的看板系统&#xff0c;打卡系统&#xff0c;历史…

加解密相关工具网站总结

加解密相关工具&网站总结 文章目录 加解密相关工具&网站总结CMD5&#xff0c;解密&#xff0c;反向查询JSFuck&#xff08;JavaScriptAAEncode加密/解密&#xff08;Javascript在线CTF编码工具开源加解密工具大佬文章&#xff1a;1.30余种加密编码类型的密文特征分析2.…

手把手一起上传本地项目至Gitee仓库

1、Gitee新建仓库 创建自己的Gitee账号&#xff0c;新建仓库&#xff0c;如图所示&#xff1a; 根据自己的项目情况&#xff0c;填写仓库信息&#xff0c;如图所示&#xff1a; 仓库创建完成&#xff0c;如图所示&#xff1a; 2、下载Git 下载地址可用链接: https://registry…

陕西师范大学大学:融合传统与创新的学府之旅

前言 > &#x1f4d5;作者简介&#xff1a;热爱跑步的恒川&#xff0c;致力于C/C、Java、Python等多编程语言&#xff0c;热爱跑步&#xff0c;喜爱音乐的一位博主。 > &#x1f4d7;本文收录于恒川的日常汇报系列&#xff0c;大家有兴趣的可以看一看 > &#x1f4d…

Knowledge-QA-LLM: 基于本地知识库+LLM的开源问答系统

⚠️注意&#xff1a;后续更新&#xff0c;请移步README Knowledge QA LLM 基于本地知识库LLM的问答系统。该项目的思路是由langchain-ChatGLM启发而来。缘由&#xff1a; 之前使用过这个项目&#xff0c;感觉不是太灵活&#xff0c;部署不太友好。借鉴如何用大语言模型构建一…

2023年深圳杯数学建模D题基于机理的致伤工具推断

2023年深圳杯数学建模 D题 基于机理的致伤工具推断 原题再现&#xff1a; 致伤工具的推断一直是法医工作中的热点和难点。由于作用位置、作用方式的不同&#xff0c;相同的致伤工具在人体组织上会形成不同的损伤形态&#xff0c;不同的致伤工具也可能形成相同的损伤形态。致伤…

elementui el-table 封装表格

ps: 1.3版本 案例&#xff1a; 完整代码&#xff1a; 可直接复制粘贴&#xff0c;但一定要全看完&#xff01; v-slot"scopeRows" 是vue3的写法&#xff1b; vue2是 slot-scope"scope" <template><!-- 简单表格、多层表头、页码、没有合并列行…

iOS 应用上架的步骤和工具简介

编辑 APP开发助手是一款能够辅助iOS APP上架到App Store的工具&#xff0c;它解决了iOS APP上架流程繁琐且耗时的问题&#xff0c;帮助跨平台APP开发者顺利将应用上架到苹果应用商店。最重要的是&#xff0c;即使没有配置Mac苹果机&#xff0c;也可以使用该工具完成一系列操作&…

Merge the squares! 2023牛客暑期多校训练营4-H

登录—专业IT笔试面试备考平台_牛客网 题目大意&#xff1a;有n*n个边长为1的小正方形摆放在边长为n的大正方形中&#xff0c;每次可以选择不超过50个正方形&#xff0c;将其合并为一个更大的正方形&#xff0c;求一种可行的操作使所有小正方形都被合并成一个n*n的大正方形 1…