开发者社区> 文艺小青年> 正文

一致性Hash

简介:
+关注继续查看

 一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题,经常用于分布式、负载均衡等。

原理

  一致哈希是一种特殊的哈希算法。在使用一致哈希算法后,哈希表中平均只需要对K/n 个关键字重新映射,其中 K是关键字的数量,n是映射节点数量。然而在传统的哈希表中,添加或删除一个映射节点的几乎需要对所有关键字进行重新映射。

  原来的映射大概是这样的,如下图,没当加入或删除一个新的节点可能都会造成每个节点的映射发生变化,如果黄色的节点代表服务器,那么每一次更新服务器的数量都会造成每个服务器上蓝色的映射节点都会发生变化,当集群数量庞大时每次增删节点所需要的修改操作就会过于庞大。

  而在一致性哈希中映射是这样的,如下图,一般一致性hash取值范围为-2^32~2^32,分布在一个圆上

  下面画的比较丑,就凑合看吧~~

  黄色节点作为映射节点(实节点),蓝色节点为需要映射到映射节点的key节点

  •   首先,看左边的图,把8个蓝色的key通过hash取值散列在一个范围为0~2^32的圆上

  •   其次,选择三个黄色节点作为映射节点,按照圆的顺时针方向,把蓝色节点与黄色节点建立映射关系

  •   最后,由于1节点负载为4,最大,那么我们为了降低1节点的负载情况,增加黄色的映射节点4,依然按照顺时针的方向修改原映射,那么只需要改变蓝色的节点7、8以及黄色节点1

实现

  一般为了方便起见,我们把黄色的映射节点称为实节点,也就是固定不变的,而蓝色的节点称为虚节点,虚节点需要映射到实节点,每次实节点的增删只会影响距离它最近的节点。

  在这里使用C++实现了ConsistentHash算法

  在存储节点方面,本程序只是简单的使用链表,最好的方式当然是红黑树了,当然为了简单起见,就用了链表,主要是理解一致性hash的原理~~


本文转自cococo点点博客园博客,原文链接:http://www.cnblogs.com/coder2012/p/3973877.html,如需转载请自行联系原作者

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

相关文章
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
9467 0
常见的一致性哈希算法#Java实现#
    之前参与过缓存框架的封装与测试工作,并对一致性哈希算法进行了相关的调研。通过对spymemcached与jedis等客户端源码的阅读对一致性哈希算法的Java实现进行调研: 1. 使用TreeMap实现,TreeMap本身继承NavigatableMap,因此具备节点导航的特点 2. 通
2256 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
13802 0
一致性hash算法
https://www.cnblogs.com/xrq730/p/5186728.html http://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653191083&idx=1&sn=c68c8bb...
21437 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
20133 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
18420 0
3576
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载