DHT和一致性哈希算法总结

DHT和一致性哈希算法总结 Hash算法比较重要的考量点有两个:1.单调性(新增或者减少映射节点时,尽量不影响原有映射关系)2.平衡性(尽量均匀分布) 分布式领域常见负载均衡算法:(1)取余法:%n如果有3个节点,Hash之后取模求余 Hash(x)%3,如果加一个节点,则Hash(x)%4。 这种方法带来的问题:1一个cache服务器mdown掉了(在实际应用中必…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

 

Hash算法比较重要的考量点有两个:

1.单调性(新增或者减少映射节点时,尽量不影响原有映射关系) 2.平衡性(尽量均匀分布)

 

分布式领域常见负载均衡算法:

(1)取余法:%n

如果有3个节点,Hash之后取模求余  Hash(x)%3,

如果加一个节点,则 Hash(x)%4。

 

这种方法带来的问题:

1 一个 cache 服务器 m down 掉了(在实际应用中必须要考虑这种情况),这样所有映射到 cache m 的对象都会失效,怎么办,需要把 cache m 从 cache 中移除,这时候 cache 是 N-1 台,映射公式变成了 hash(object)%(N-1) ; 2 由于访问加重,需要添加 cache ,这时候 cache 是 N+1 台,映射公式变成了 hash(object)%(N+1) ; 1 和 2 意味着什么?这意味着突然之间几乎所有的 cache 都失效了。对于服务器而言,这是一场灾难,洪水般的访问都会直接冲向后台服务器; 再来考虑第三个问题,由于硬件能力越来越强,你可能想让后面添加的节点多做点活,显然上面的 hash 算法也做不到。 有什么方法可以改变这个状况呢,这就是 consistent hashing…

 解释下为什么cache会失效:

  假如有6个数据分别是1,2,3,4,5,6,有3台机器,用取余算法%3。设定余数为0对应的是第一台机器,余数为1对应的是第二台机器,余数为2对应的是第三台机器。那么数据3和6存储在第一台机器,1和4存储在第二台机器,2和5存储在第三台机器。如果这时候增加一台机器变成4台,用取余算法%4实现,映射到某台机器的规则和之前的类似,那么数据4存储在第一台机器,数据1和5存储在第二台机器,数据2和6存储在第三台机器,数据3存储在第4台机器。

  原来3台机器: M1:(3,6) M2: (1,4)  M3: (2,5)

  变成4台机器:M1: (4) M2: (1,5) M3: (2,6) M4: (3) 

   可以看到1,2,3,4台机器的数据都将会有变化。

而如果采用一致性hash算法,则能减少数据变化的机器。

 

(2)一致性hash算法

  实现步骤:

第一步:采用一种hash算法,把服务器地址或者主机名映射到一个2的32次方的环上。为什么是2的32次方?IPv4的ip地址占4个字节,可以存储2的32次方比特位信息。

第二步:把要存储的key采用同样的hash算法映射到环上,如果命中某个服务器地址则存在该台服务器,如果在服务器1和服务器2的地址的中间,则按从小到大去搜索,找到的第一个服务器,就映射到该台服务器上。

好处:增加和减少节点时,只影响附近的一个节点,不会像取余法一样影响全部节点的数据。

 

改进:

另外,一致性哈希算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜问题。例如系统中只有两台服务器,可能大量的数据都存在一台服务器,另一台服务器只存储了很少的数据。为了解决这种情况,可以增加虚拟环。

DHT和一致性哈希算法总结

为了解决这种数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,注意,这里的多个哈希算法应该使得结果尽量分布均匀,才能最大程度减少数据倾斜的情况。每个计算结果位置都放置一个此服务节点,称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况,可以为每台服务器计算三个虚拟节点,于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值。同时数据定位算法不变,只是多了一步虚拟节点到实际节点的映射,例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中,通常将虚拟节点数设置为32甚至更大,因此即使很少的服务节点也能做到相对均匀的数据分布。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164579.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 大数据的应用实例_net开源开发web框架

    大数据的应用实例_net开源开发web框架NetAdvantage的整套组件中,应该说WebGrid是应用最多的。但是网上的关于这方面的资料非常少。这段时间刚好项目处于收尾阶段,因为空余下来。而有一个项目中完全的运用了WebGrid。因此有了一些心得,现在共享大家这里我主要结合常见项目进销存中的一个入库单来讲解WebGrid在B/S开发中的便利我先把做好的界面和效果展示给大家,让大家有一个直观的了解当我在订单编号中输入订单编号后,我使用一

  • QTreeWidget 遍历所有子节点(QTreeWidgetItem)[通俗易懂]

    QTreeWidget 遍历所有子节点(QTreeWidgetItem)[通俗易懂]这恐怕是最简单的写法了,逛论坛发现的,亲测好用//ui文件中定义//QTreeWidget*treeWidget;//…//遍历treeWidgetQTreeWidgetItemIteratorit(ui.treeWidget);while(*it){//dosomethinglike…

  • 缓冲区溢出攻击实验「建议收藏」

    缓冲区溢出攻击实验「建议收藏」又一个计系系统的实验。

  • 线程池实现原理_最通俗易懂的解读比特币相关原理

    线程池实现原理_最通俗易懂的解读比特币相关原理本篇内容综合广大网友提供内容,笔者经过整理,对数据库连接池原理和实现过程做个很系统的并且通俗易懂的分析讲解,以及手写一个连接池实现过程作为演示。一、早期通过JDBC方式操作数据库我们先来看早期使用JDBC的方式操作数据库的过程,这里以mysql数据库为例讲解JDBC操作数据库原理:一般来说,java应用程序访问数据库的过程是:   ①装载数据库驱动程序;   ②通过jdbc…

  • 工程机械核心部件寿命预测前三名方案总结与2022年最新方案分享(万文详解)[通俗易懂]

    工程机械核心部件寿命预测前三名方案总结与2022年最新方案分享(万文详解)[通俗易懂]1.比赛学习方法论2.工业寿命预测赛题讲解2.1赛题背景2.2赛题任务和数据介绍2.3评测标准2.4初赛与复赛排行榜2.5数据分析2.6数据预处理2.7特征提取3.前三名数据预处理方法比较4.前三名特征工程方法比较4.1特征构建4.2特征选择5.前三名模型构建比较6.代码与数据7.2022年最新思路分享………

  • 卡商卡盟在线批发平台_易玩卡盟怎么样

    卡商卡盟在线批发平台_易玩卡盟怎么样支持一键装修主站,一键对接货源,自定义后台登录背景,前台风格自定义背景等,已集成易支付接口对接易支付充值接口,修复BUG等服务器系统可以:Windows64/Linux64/cenos6.864位安装宝塔环境:apache2.4+mysql5.5+php5.6cenos6.8系统安装宝塔命令:yuminstall-ywgetamp;amp;wget-Oinstall.shhttp://downlo…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号