Consistent hashing一致性算法原理

Stella981
• 阅读 470

最近在整理redis分布式集群,首先就整理一下分布式算法原理。常见的分区规则有哈希分区和顺序分区两种,Redis采用的是哈希分区规则。

  • 节点取余分区

使用特定的数据,如Redis的键或用户ID为key,节点数量为N,则:hash(key)%N,计算出哈希值,然后决定映射到哪个节点上,如节点数为4时,哈希值的结果可能为0、1、2,3. 现假设有4个redis节点,HashCode值为1~20的20个数据,那么

redis节点

HashCode

HashCode

HashCode

HashCode

HashCode

redis0

4

8

12

16

20

redis1

1

5

9

13

17

redis2

2

6

10

14

18

redis3

3

7

11

15

19

当增加一个redis节点时,如下图只有1,2,3,20这4个命中了,即4/20=20%

redis节点

HashCode

HashCode

HashCode

HashCode

redis0

5

10

15

20

redis1

1

6

11

16

redis2

2

7

12

17

redis3

3

8

13

18

redis4

4

9

14

19

优点:简单 缺点:当节点数量变化时,如扩容或收缩节点,数据节点映射关系需要重新计算,会导致数据的重新迁移。

  • Consistent hashing一致性算法原理 一致性算法也叫环形hash算法。 基本思想:将对象和cache都映射到同一个hash数值空间中,并且使用相同的hash算法。

算法过程:构造长度为的2³²的整数环,根据节点名称的Hash值,将缓存服务器节点放置在这个Hash环上,然后根据需要缓存的数据的key值计算得到Hash值,然后在Hash环上顺时针查找这个key的Hash最近的服务器节点,完成key到服务器的映射查找。 keyA、keyB、keyC为三个节点,对象为key1,key2,key3,key4:

Consistent hashing一致性算法原理

可以分析一下,当移除一个节点时,影响的是该节点到逆时针到达下一个节点的这部分,如移除keyB,keyB到KeyA的值会重新指向keyC;添加节点时,影响的是添加的节点逆时针到达下一个节点的一部分,不会对其它节点造成影响。_一致性算法,明显的抑制对象的键的重新分布。_ 理想状态下,3个节点是均匀分布在环上的,可是实际一般不会均匀分布,会出现hash倾斜,如下图,A B C三个节点挨的比较紧密: Consistent hashing一致性算法原理

缺点: 加减节点会造成哈希环中部分数据无法命中,需要手动处理或者忽略这部分数据,因此一致性哈希常用于缓存场景中。 节点比较少时,节点变化将大范围影响哈希环中数据映射,因此不适合少量节点的分布式场景。 普通的一致性哈希分区在增减节点时,需要增加一倍或减去一般节点才能保证数据和负载的均衡。

虚拟槽分区 如下图,每个节点增加一个虚拟节点,这样对象1、3指向节点A,4、5指向节点B,2、6指向节点C,明显抑制了hash一致性分布不均匀的现象。 Consistent hashing一致性算法原理

使用分散度良好的哈希函数把所有数据映射到一个固定范围的整数集合中,整数定义为槽。这个范围一般远大于节点数,槽是集群内数据管理和迁移的基本单位。采用大范围槽的主要目的是为了方便数据拆分和集群扩展。 命中率计算公式: (1-n/(n+m))*100% n是服务器台数 m是新增服务器台数,新增服务器台数越多命中率越大,所有增加虚拟节点命中率也会增加。

增加虚拟节点,每个实际节点设置100~500虚拟节点,可以抑制hash一致性分布不均匀的现象。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4天前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
2年前
Mysql 表分区分类
针对Mysql数据库,表分区类型简析。【1】表分区类型(1)Range分区:按范围分区。按列值的范围区间进行分区存储;比如:id小于10存储在一个分区;id大于10小于20存储在另外一个分区;(2)List分区:按离散值集合分区。与range分区类似,不过它是按离散值进行分区。(3)Hash分区:按hash算法结果分区。对用户定义的表达式所返
Wesley13 Wesley13
2年前
Java之一致性hash算法原理及实现
一致性哈希算法是分布式系统中常用的算法。比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节点上,如key%N,key是数据的key,N是机器节点数,如果有一个机器加入或退出这个集群,则所有的数据映射都无效了。一致性哈希算法,解决了普通余数Hash算法伸缩性差的问题,可以保证在上线、下线服务
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
5个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这