一致性哈希算法

  在分布式领域中各技术组件都有实现KV形式的存储,在实现各类工作能力的同时还简化了算法实现。以Raft分布式协议为例,它通过在领导者采用KV存储来简化算法实现和共识协商,但同时也限制所有写请求只能在领导者节点上进行处理,从而导致集群退化为单机模式。
  没有什么是加一个中间层解决不了的问题,那么有那就再加一层。为实现既要又要的目的,可以通过分集群来突破单集群的性能限制,然后再各集群节点和客户端之间加一个哈希代理层进行路由。

简单的哈希算法

公式:m = hash(o) mod n
o:需要被哈希函数作用的对象值
n:集群中节点的个数

  假设集群中有A、B和C三个节点、对象值为1到10十个数据,经过简单哈希函数公式m = hash(o) mod n计算后得:

节点数据
节点A3、6、9
节点B1、4、7、10
节点C2、5、8

  如果增加一个D节点,那么此时公式中的n就由3变成了4。上述十个数据就得重新代入哈希函数计算一个新值,计算后得:

节点数据
节点A4、8
节点B1、5、9
节点C2、6、10
节点D3、7

  对比两组数据发现只有1和2经过哈希函数重新计算后没有被移动,当前还只有十个数据,如果当集群中数据量很大是,那么每次扩容和缩容带来的数据迁移成本可谓是相当巨大,更有甚者会导致宕机,由此可以使用一致性哈希来解决数据迁移成本高的问题。

一致性哈希算法

  一致性哈希算法是1997年发布的《Consistent Hashing and Random Trees》论文中提出的,使用此算法可以大幅度减少数据迁移量,它可以保证在进行扩容和缩容时,节点之间的数据迁移只限于两个节点之间,不会像上述简单的哈希函数那样造成大规模的数据迁移。

哈希环

  一致性哈希算法也用了取模运算,与普通哈希算法直接对节点的数量进行取模运算有所不同,一致性哈希算法是对232进行取模运算。即将数据映射到0~(232-1)的数字空间,将这些数字头尾相连可以组织成一个虚拟的圆环,也就是哈希环:
image.png
  上图所示哈希环的空间是按顺时针方向组织的,圆环的正上方的点代表原点0,0 点右侧的第一个点代表 1,以此类推,2、3、4、5、6……直到232-1,即0点左侧的第一个点代表232-1。

映射节点到哈希环

  在一致性哈希算法中,可以通过执行自定义的哈希算法将节点映射到哈希环上,那么每个节点就能确定其在哈希环上的位置了:
image.png

映射数据到哈希环

  同理执行自定义的哈希算法计算出每个数据对应的key值,然后散列到哈希环上,hash(o1) = key1、hash(o2) = key2、hash(o3) = key3、hash(o4) = key4:
image.png

存储数据到节点

  将节点和数据都映射到同一个哈希环上之后,然后以原点0为起点顺时针转动,在转动过程中数据遇到的第一个节点就是该数据的归属,然后读写数据的时候就可以按照此到对应的节点上去寻找。

节点数据
节点Akey1、key4
节点Bkey2
节点Ckey3

扩容和缩容

扩容

  扩容即向集群中增加一个节点D,节点D经过上述同样自定义的哈希函数后计算后,然后将其映射到哈希环上,如下图所示。
image.png
  此时再根据顺时针存储的规则进行数据迁移:

节点数据
节点Akey1
节点Bkey2
节点Ckey3
节点Dkey4

  扩容之后发现只有key4从之前的节点A迁移到了节点D上,数据的移动仅发生在节点A和节点D之间,其他节点上的数据并未受到影响。

缩容

  缩容即向集群中减少一个节点C,先将节点C从哈希环上移除,然后再根据顺时针存储的规则进行数据的迁移:
image.png

节点数据
节点Akey1、key3、key4
节点Bkey2

  缩容之后发现只是将节点C的所属的数据迁移到了节点A上,其他数据并未受到影响。
  总的来说,使用了一致性哈希算法后,扩容或缩容的时候,都只需要重定位哈希环中的一小部分数据。也就是说,一致性哈希算法具有较好的容错性和可扩展性。

复杂度

  假设总数据条数是M,节点个数是N。

哈希函数时间复杂度
  • 传统哈希算法,以N为基数执行取模运算,时间复杂度为O(1)。
  • 一致性哈希算法,首先将关键字先转换为 32 位整型,然后采用二分法(所有节点在哈希环上是有序排列的)确定节点在哈希环上的处理范围,综合时间复杂度为O(logN) 。
数据迁移规模
  • 传统哈希算法,因为节点变化需要迁移的数据规模是不可控的,所以综合数据迁移规模为O(M)。
  • 一致性哈希算法,哈希环中各节点均匀分布的情况下,数据迁移规模为O(M/N)。

  综上数据条数 M 远大于主机节点数 N,而且数据迁移的成本很大,所以一致性哈希算法更划算。

数据倾斜

  一致性哈希算法虽然降低了数据的迁移量,但是也存在两个数据倾斜的问题

  1. 如果映射后哈希环中的数字分布不均匀,就会导致各节点处理的数据不均衡、各节点的负载不均衡。
  2. 容灾和扩容时哈希环上相邻节点会受到极大影响,极端情况下,假如节点A出现故障,存储在A上的数据要全部转移到B上,大量的数据导可能会导致节点B的崩溃,之后A和B上所有的数据向节点C迁移,导致节点C也崩溃,由此导致整个集群宕机,产生雪崩效应。
虚拟节点

  想要解决数据倾斜的问题,一来可以让集群中的节点尽可能的多,从而让各个节点均匀的分布在哈希空间中。但是在生产环境中机器的数量往往都是固定的,所以我们只能在物理节点和哈希环之间再加一层虚拟节点层。
  假如集群中有4个节点,首先不是直接将哈希环分为4份,而是将均分地分为32份,每份对应一个虚拟节点共32个虚拟节点;然后再将这32个虚拟节点映射到4个物理节点上。
image.png
  设置虚拟节点层后,为异构的服务器节点设置权重也更方便。只需要为权重高的真实节点,赋予更多的虚拟节点即可。虽然虚拟节点增多可以提升均衡性,但是也会消耗更多的内存与计算力。

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

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

相关文章

TS项目实战二:网页计算器

使用ts实现网页计算器工具,实现计算器相关功能,使用tsify进行项目编译,引入Browserify实现web界面中直接使用模块加载服务。   源码下载:点击下载 讲解视频 TS实战项目四:计算器项目创建 TS实战项目五:B…

龙芯安装使用搜狗输入法

CPU:龙芯3A6000 操作系统:Loongnix 桌面主题:Cartoon 龙芯系统切换输入法的按键一般为:Ctrl空格。 1 安装搜狗输入法 进入Loongnix系统自带的龙芯应用合作社,寻找搜狗输入法,点击安装。 按下Ctrl空格&…

生成树技术华为ICT网络赛道

9.生成树 目录 9.生成树 9.1.生成树技术概述 9.2.STP的基本概念及工作原理 9.3.STP的基础配置 9.4.RSTP对STP的改进 9.5.生成树技术进阶 9.1.生成树技术概述 技术背景:二层交换机网络的冗余性与环路 典型问题1:广播风暴 典型问题2:MA…

C++多态_C++回顾

多态的概念 通俗的说多态就是多种形态,具体点就是去完成某个行为,当不同的对象去完成时会产生出不同的概念。 什么是多态 静态的多态 静态的多态即函数重载,编译时是参数匹配和函数名修饰规则。 动态的多态 运行时实现,跟指…

(篇九)MySQL常用内置函数

目录 ⌛数学函数 ⌛字符串函数 ⌛聚合函数 ⌛日期函数 📐获取当前时间 📐获取时间的某些内容 📐​编辑 📐格式化函数 📏format类型: ⌛系统信息函数 ⌛类型转换函数 数学函数 字符串函数 聚合函…

《计算机网络简易速速上手小册》第6章:网络性能优化(2024 最新版)

文章目录 6.1 带宽管理与 QoS - 让你的网络不再拥堵6.1.1 基础知识6.1.2 重点案例:提高远程办公的视频会议质量实现步骤环境准备Python 脚本示例注意事项 6.1.3 拓展案例1:智能家居系统的网络优化实现思路Python 脚本示例 6.1.4 拓展案例2:提…

Go语言每日一练 ——链表篇(三)

传送门 牛客面试笔试必刷101题 ---------------- 链表中的节点每k个一组翻转 题目以及解析 题目 解题代码及解析 package main import _"fmt" import . "nc_tools" /** type ListNode struct{* Val int* Next *ListNode* }*//*** 代码中的类名、方…

矩阵的正定(positive definite)性质的作用

1. 定义 注意,本文中正定和半正定矩阵不要求是对称或Hermite的。 2. 性质 3. 作用 (1)Axb直接法求解 cholesky实对称正定矩阵求解复共轭对称正定矩阵求解LDL实对称非正定矩阵求解复共轭对称非正定矩阵求解复对称矩阵求解LU实非对称矩阵求解…

离线环境怎么下载python依赖包

公司内网环境无网络,运行自动化脚本需要安装python模块 1、脚本依赖包及其版本获取,记录在requirements.txt中 pipreqs ./script --encodingutf8 requirements.txt注意,这里是将./script 里的python模块自动扫描并写入到requirements.txt中…

QT学习日记 | 显示类控件

目录 前言 一、QLabel控件 1、属性介绍 2、实战演练 (1)文本格式属性 (2)图片属性 (3)对齐、换行、缩进、边距属性 (4)伙伴属性 二、QLCDNumber控件 1、属性介绍 2、实战…

图灵之旅--二叉树堆排序

目录 树型结构概念树的表示形式 二叉树概念特殊的二叉树二叉树性质二叉树的存储二叉树的遍历前中后序遍历 优先级队列(堆)概念 优先级队列的模拟实现堆的性质概念堆的存储方式堆的创建 堆常用接口介绍PriorityQueue的特性PriorityQueue常用接口介绍优先级队列的构造插入/删除/获…

闲聊电脑(5)装个 Windows(一)

​夜深人静,万籁俱寂,老郭趴在电脑桌上打盹,桌子上的小黄鸭和桌子旁的冰箱又开始窃窃私语…… 小黄鸭:冰箱大哥,上次说到硬盘分区和格式化,弄完之后,就该装系统了吧? 冰箱&#x…

确定问卷调查样本量

目录 1. 问卷数据类型1.1 定性数据&定性分析1.2 定量数据&定量分析 2. 确定初始样本容量:2.1 公式:2.2 Z值2.3 p2.4 e2.5 举例 3.调整初始样本容量:3.1 公式:3.2 结论就是 小结: 1. 问卷数据类型…

消息中间件之RocketMQ源码分析(七)

并行消费和顺序消费 ConsumeMessageService是一个通用的消费服务接口,它包含两个实现类org.apache.rocketmq.client.impl.consumer.ConsumeMessageConcurrentlyService和 org.apache.rocketmq.client.impl.consumer.ConsumeMessageOrderlyService,这两个…

学习并用好大模型

大模型是个好东西,学好并用好益处多多~ 1. 运用大模型服务我们的工作 运用大模型服务于工作,可以从以下几个方面着手: 知识管理与检索: 利用大模型强大的自然语言处理能力,建立企业内部的知识库系统。员工可以通过提问…

03-Java单例模式 ( Singleton Pattern )

单例模式 单例模式设计要点单例模式基础实现摘要实现范例 单例模式的几种实现方式1. 懒汉式,线程不安全2. 懒汉式,线程安全3. 饿汉式4. 双检锁/双重校验锁(DCL,即 double-checked locking)5. 登记式/静态内部类6. 枚举…

记录关于node接收并解析前端上传excel文件formData踩的坑

1.vue2使用插件formidable实现接收文件,首先接口不可以使用任何中间件,否则form.parse()方法不执行。 const express require(express) const multipart require(connect-multiparty); const testController require(../controller/testController)/…

【论文精读】多模态情感分析 —— VLP-MABSA

Vision-Language Pre-Training for Multimodal Aspect-Based Sentiment Analysis 本篇论文发表于ACL-2022 原文链接 https://arxiv.org/abs/2204.07955 源码 GitHub - NUSTM/VLP-MABSA 模态:图像文本 基于多模态方面的情感分析(MABSA)近年来越来越受到关注。然而&am…

【Power Automate】规避流程30天的运行时限(只针对审批流)

众所周知,Power Automate的流程最多只能运行30天,到点之后直接超时,如果我们有超时时间设置的比较长的审批就会很麻烦,可能我们把审批节点的超时时间都设置为25天,结果第一个审批人就把25天拉满了,那第二个…

SpringBoot实战第三天

今天主要完成了: 新增棋子分类 棋子分类列表 获取棋子分类详情 更新棋子分类 更新棋子分类和添加棋子分类_分组校验 新增棋子 新增棋子参数校验 棋子分类列表查询(条件分页) 先给出分类实体类 Data public class Category {private Integer id;//主键IDNot…