一致性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,如需转载请自行联系原作者

相关文章
|
jenkins Java 持续交付
Jenkins部署报错问题:已解决
其他更多的Jenkins操作可以看我的其他博客 : 服务搭建篇(九) 使用GitLab+Jenkins搭建CI\CD执行环境 (上) 基础环境搭建 服务搭建篇(十) 使用GitLab+Jenkins搭建CI\CD执行环境 (下) 配置整合
791 0
|
存储 自然语言处理 Java
ResourceBundle.getBundle()来读取自定义的properties配置文件
ResourceBundle.getBundle()来读取自定义的properties配置文件
363 1
|
机器学习/深度学习 自然语言处理 算法
文本分析-使用jieba库进行中文分词和去除停用词(附案例实战)
文本分析-使用jieba库进行中文分词和去除停用词(附案例实战)
6682 0
|
8月前
|
监控 开发者 Perl
perl use HTTP::Server::Simple 轻量级 http server
使用 **HTTP::Server::Simple** 模块,Perl 开发者可以快速创建和配置一个轻量级的HTTP服务器。通过继承和扩展 `handle_request` 方法,可以实现复杂的请求处理逻辑。结合日志记录功能,可以更好地监控服务器运行情况。无论是用于开发测试还是简单的生产环境应用,这种轻量级解决方案都能提供很好的支持。
191 2
|
Shell 开发工具 git
【Git】解决Untracked Files Prevent Checkout的问题
【Git】解决Untracked Files Prevent Checkout的问题
3103 0
|
Java 编译器
Java Annotation Processor(一)
Java Annotation Processor
610 0
|
数据库
IDEA连接数据库之后没有显示数据库里面的表
IDEA连接数据库之后没有显示数据库里面的表
710 0
|
存储 弹性计算 编解码
阿里云服务器计算型c5、c6、c6a、c6e实例规格有什么区别?如何选择?
本文介绍了阿里云服务器计算型c5、c6、c6a、c6e实例规格的区别,以及选择参考。
2459 0
阿里云服务器计算型c5、c6、c6a、c6e实例规格有什么区别?如何选择?
|
Ubuntu Linux 开发工具
linux ubuntu 中文字符集设置图文详解(傻瓜式教程)
linux ubuntu 中文字符集设置图文详解(傻瓜式教程)
1080 1
linux ubuntu 中文字符集设置图文详解(傻瓜式教程)
|
XML 网络协议 测试技术
Network-Emulator-Toolkit网络模拟器使用详细介绍
Network-Emulator-Toolkit网络模拟器使用详细介绍
761 0