一致性哈希算法应用与分析-阿里云开发者社区

开发者社区> 旭东的博客> 正文

一致性哈希算法应用与分析

简介:   一致性哈希算法主要使用在分布式数据存储系统中,按照一定的策略将数据尽可能均匀分布到所有的存储节点上去,使得系统具有良好的负载均衡性能和扩展性。感觉一致性哈希与数据结构中的“循环队列”还是有一点联系的。
+关注继续查看

  一致性哈希算法主要使用在分布式数据存储系统中,按照一定的策略将数据尽可能均匀分布到所有的存储节点上去,使得系统具有良好的负载均衡性能和扩展性。感觉一致性哈希与数据结构中的“循环队列”还是有一点联系的。

1.简单哈希算法

  哈希(hash)计箅是常见的数据分布技术,其通过求模运算来计算哈希值,然后据此将数据映射到存储空间中。由于只是采用了简单的求模运算.使得简单哈希计算存在很多不足:
  1)增删市点时,更新效率低。当系统中存储节点数量发生增加或减少时,映射公式将发生变化为hash(object)%(N±1),这将使得所有obiect的映射位置发生变化,整个系统数据对象的映射位置都需要重新进行计算,系统无法对外界访问进行正常响应,将导致系统处于崩溃状态。

  2)平衡性差,未考虑节点性能差异。由于硬件性能的提升,新添加的节点具有更好的承载能力,如何对算法进行改进,使节点性能可以得到较好利用。

  3)单调性不足。衡量数据分布技术的一项重要指标是单调性,单调性是指如果已经有一些内容通过哈希计算分派到了相应的缓冲中,当又有新的缓冲加入到系统中时,哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

2.一致性哈希算法的工作原理

2.1 数据保存

  一致性哈希,是对简单哈希算法进行了修正,它的原理分为两步。

  首先,对“存储节点”的哈希值进行计算,其将存储空间抽象为一个。如下图中的1、2、3三个节点就可以理解为三个可以存储数据的“存储节点”。其次,对要存储的数据进行同样的哈希计算,按顺时针方向将其映射到离其最近的节点上去。  

 2.2 节点失效情况

   当有存储节点出现故障离线时,按照映射方法,受影响的仅仅为从环上故障节点开始逆时针方向至前一个节点之间区间的数据对象。而这些对象本身就是映射到故障节点之上的。

  例如在存储节点4出现故障时,只会影响那些数据的哈希值在存储节点3到存储节点4哈希值之间的数据节点,影响不会进一步扩大。

  

2.3增加存储节点时

  当有节点增加时,比如,在存储节点2和存储节点3之间重新添加一个存储节点5。受影响的也仅仅是存储节点5逆时针遍历直到存储节点2之间的数据对象,将这些重新映射到5上即可,因此,当有节点出现变动时,不会使得整个存储空间上的数据都进行重新映射。解决了简单哈希算法增删节点,重新映射所有数据带来的效
率低下的问题。

3.虚拟节点的概念

  一致性哈希算法具有随机性。当存储节点数量较少时节点在环上分布不够均匀。为解决这个问题,提出了基于虚拟节点的改进算法,其核心思路是引入虚拟节点。

  每个虚拟节点都有一个对应的物理节点,而每个物理节点可以对应若干个虚拟节点。

  在2.1的图中有存储节点1、2、3、4可以看出分布不均匀。假定四个存储节点型号相同,可以说节点4的负载量最小的,节点3最大。为了负载均衡,可以由物理存储节点来引入了虚拟节点4''',如下图所示。可以将虚拟节点理解为一个“符号标记”,按照2.1中的规则将数据的保存在存储节点上,只是应在虚拟节点保存的数据实际保存在对应的物理节点4上。这样就在一定程度上解决了负载均衡

  

  

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
一文快速搞定Redis_数据类型及JavaApi操作
大家好,我是**ChinaManor**,直译过来就是中国码农的意思,我希望自己能成为国家复兴道路的铺路人,大数据领域的耕耘者,平凡但不甘于平庸的人。
7 0
计算机基础1 | 学习笔记
快速学习计算机基础1。
7 0
计算机基础2 | 学习笔记
快速学习计算机基础2。
10 0
Vue 仿钉钉流程图(流程节点绘制 vue+Ant【如果用其他UI库需要替换几个组件】 附 demo)
# [这里是git地址](https://gitee.com/xiaoyaoluntian/imitating-dingding-flow-chart/tree/comdemo/)
6 0
偏序关系
偏序 关系 离散数学
6 0
数据类型-数值和字符串 | 学习笔记
快速学习数据类型-数值和字符串。
5 0
一文快速了解ClickHouse 战斗民族的开源搜索引擎(超详细解读+快速入门)
大家好,我是**ChinaManor**,直译过来就是中国码农的意思,俺希望自己能成为国家复兴道路的铺路人,大数据领域的耕耘者,一个平凡而不平庸的人。
8 0
PG+MySQL第9课-实时精准营销
通常业务场景会涉及基于标签条件圈选目标客户、基于用户特征值扩选相似人群、群体用户画像分析这些技术,本文将围绕这三个场景去介绍在实施精准营销里面的PG数据库的使用
5 0
Redis高可用架构演进
Redis是目前使用最广泛的缓存程序之一,也被应用于多种场景,例如数据缓存、分布式锁等,Redis官方提供了多种部署架构,以满足不同应用场景下对于高可用和扩展性的要求。
6 0
MySQL高可用架构演进
MySQL是数据库领域当之无愧的霸主之一,其在各行各业被广泛应用,随着广泛使用,对于MySQL本身的高可用性的要求就是不可避免的话题,而MySQL的高可用方案也随着MySQL功能的完善经历了多次升级,本文将对MySQL的各种高可用架构进行分析,以此来了解架构的演进。
6 0
+关注
旭东的博客
从事互联网开发工作,写博客,记录问题与学习支持,并分析
194
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载