挖比特币有什么意义:一致性哈希算法的两种优化方案

  简介

  一致性哈希算法的提出当然也同样伴随着新的问题出现,那就是当某一个服务器结点挂掉之后,它的任务就会分配到它的下一个服务器结点,那么这就有悖于分布式系统中需要满足平衡性的要求。

  雪崩效应

  在服务器上会有一些数据会经常被访问,这些数据的访问次数远远高于其他数据,那么这些数据就被称为热点数据,理所当然在分布式服务器中承载这些热点数据的服务器的负载就要大于其他服务器。当对热点数据的访问量超过服务器的承受限度的时候,服务器就会挂掉。

  按照一致性哈希算法,这个服务器的数据就会托管给下一个服务器,下一个服务器当然也无法承担这么大的请求量,不一会它也会挂掉,接着下一个服务器也会挂掉,直到最后整个服务器挂掉。这就是雪崩

  优化方案

  这里有两种优化方案,第一种简单粗暴,那就是增加承载热点数据的服务器数量。另一种更好的方案是使用虚拟结点技术,这种方法的原理就是将一个物理结点拆分问多个虚拟结点,让这些虚拟结点均匀的分布在哈希环之上。这样就解决了某个结点删除后,它的数据资源分配不平衡的问题。

  

  如图红色的结点3就相当于承载热点数据的服务器,右图中把每个物理结点拆分为了两个虚拟结点,并均匀的分布在哈希环之上。

  这种解决方案的优势是与此同时也解决了当增加结点时,新结点从其他节点拉取资源后导致的结点资源分布不均问题。

  例如,有ABD三个结点分配一百个资源,当要在BD之间加入一个结点C的时候,C结点会直接从D结点拉取相应的结点,这就会导致AB分配的资源肯定要多于CD所分配的资源,这也就不满足服务器的负载均衡的要求。而当插入一个物理结点时把它拆分为几个虚拟结点并均匀分布在哈希环之上就可以解决这个问题。

  时间复杂度

  做到这一步好像一致性哈希已经很完美了,但是我们还忽略了一个问题,那就是一致性哈希的查找时间复杂度。一致性哈希不像普通哈希,时间复杂度是0(1),这是因为普通的哈希是基于数组的,而一致性哈希为了满足可伸缩性一般会选择链表作为基础数据结构。那么时间复杂度就会变为O(N)。

  优化方案

  这里O(N)的时间复杂度对于哈希算法是不能忍受的,在这里我们使用一种叫做跳转表的技术来解决这个问题。

  

  如上图在这个跳转表中,每个结点记录距离自己 1,2,4 距离的数字所存的结点,这样不管查询落在哪个节点上,对整个哈希环上任意的查询一次都可以至少跳过一半的查询空间,这样递归下去很快就可以定位到数据是存在哪个结点上。这样时间复杂度就降为了O(logN)。但是这样也同样会带来一个问题就是会占用服务器的存储空间。

  第二种解决方案就是不选用链表作为基础的数据结构,换成二叉查找树结构。因为哈希查找的过程实际上就是在二叉树中查找不小于查找数的最小数值的过程,所以我们可以按照需求选取AVL树,红黑树作基础数据结构。这样也可以降低时间复杂度到O(logN)。

  声明:本文由入驻区块网专栏作者撰写,观点仅代表作者本人,绝不代表区块网赞同其观点或证实其描述。

  更多名家专栏精品文章:http://www.qukuaiwang.com.cn/zhuanlan.html

文章内容系本站作者个人观点,不代表本站对其观点赞同或支持,文章的版权归该作者所有。如需转载,请注明文章来源。本文地址:http://www.cis.net.cn/kejikuaixun/44198.html
留言与评论(共有 条评论)
验证码:

最新文章

一致性哈希算法的两种优化方案

科技快讯
简介一致性哈希算法的提出当然也同样伴随着新的问题出现,那就是当某一个服务器结点挂掉之后,它的任务就会分配到它的下一个服务器结点,那么这就有悖于分布式系统中需要满足平衡性的要求。雪崩效应在服务器上会有一些数据会经常被访问,这些数据的访问次数远远高于其他数据,那么这些数据就被称为热点数据,理所当然在分布式服务器中承

区块链机器人——你还在养猫、养狗、养马?中机上线区块链机器人,前沿区块链商业实践。

科技快讯
中机布局区块链机器人中机做工业领域人工智能技术的领航者,中机区块链实验室上线区块链机器人,养猫养狗不如养个机器人,如果区块链猫、区块链狗都值1亿的话,那么区块链机器人会不会价值几十亿呢?中机区块链实验室,正在研发区块链的机器人,进入中机商圈(robot.cmeplaza.com)平台,你就可以免费领养

投资数字货币最重要的网站目录

科技快讯
内容整理得这么完整的好文章,是不是要收藏或转发一下?国内交易所:国内可以提ETH的市场:yunbi.comszzc.combter.comchbtc.com1、比特币中国:?(比特、莱特)2、币行OKCoin:?(比特、莱特)3、火币网:?(

MaiCoin创始人刘世伟:STO将让台湾拥抱国际金融市场

科技快讯
台湾的证券型代币发行(STO)是否只接受台湾人的投资?MaiCoin集团创始人暨执行长刘世伟(AlexLiu)表示,STO可以协助发行公司接纳国际投资。而最终的目标,是希望台湾能够提供本土企业一个新的、受监管、可自由交易的募资管道,让台湾具备亚洲金融中心的潜力。台湾证券型代币监管规则将在6月份出炉,届时金管会将会公布发行标准与规范,而Maico

朱啸虎再评区块链 这次他又说了啥?

科技快讯
混币圈的朋友都知道,在今年2月末,金沙江创业投资合伙人、“独角兽捕手”朱啸虎隔空手撕了以蔡文胜和陈伟星为代表的“3点钟区块链”微信群,并毫不客气地炮轰搞区块链I*C*O都是骗子。然而,如果你认为朱啸虎会就此撇清他同区块链的恩恩怨怨,那你就图样了――就在近日,朱啸虎再度高调发声称:“没看到必须用区块链的场景。”并重申他不

【STO功能与限制】证券型代币是币圈蓝海或是海市蜃楼?

科技快讯
许多人预测2019年为证券代币年,事实上这样的期待在2018年中期或是更早,人们就已预期这个趋势。因为证券本身就不是新鲜事,把代表有货币价值的权利化做证明文件,这样的文件作为金融工具,衍生出十分庞大的市场,例如:股票、股息或利息等。而证券型代币,约略来说,就是把证券代币化

日本房地产也开始接受比特币了 这栋楼售价547个比特币

科技快讯
作为全球最大的数字货币市场之一,如今日本房地产也开始拥抱比特币了。CCN网站报道,一家位于日本东京的房地产公司Yitanzi将在未来的几周内以547个比特币的售价出售一幢商业楼,据悉这是全日本首个使用比特币出售的建筑。如果换算成美元,那么这幢大楼的售价则为600万美元。除此之外,该公司的网站上还有其他以比特币出售的建筑

第十七届上海理财博览会2019专业观众预登记系统已上线

科技快讯
第十七届上海理财博览会将于2019年12月13-15日在上海展览中心再次启幕,展会由《理财周刊》和VNU欧洲展览集团共同主办,届时会吸引上百家国内外知名金融机构、逾十万名业内人士及个人投资者前来参会。为了方便专业观众尽早安排日程,通过专业观众预登记系统提前进行预注册及时掌握展会第一手资讯,有效规划您的参观行程!