文档章节

一致性哈希

dokia
 dokia
发布于 2015/05/12 15:00
字数 652
阅读 110
收藏 2
点赞 0
评论 0

对于键值的哈希算法,一般是将得到的哈希值对哈希空间长度取余,即

hash(key) % len; //key为键值,len为哈希空间长度

然后将键值按哈希值存储在数组下标中。

这种哈希处理有个问题,即当哈希空间长度动态变化时,已存储的键值对(key-value)无法再通过键值获得,为了防止这种情况,需要对整个哈希空间的键值对进行rehashing。在分布式系统中,数据经常以跨节点(如主机等)的方式存储。系统的可扩展性要求能够动态地添加或删除(主要是添加)节点,这样造成哈希空间也会随着动态变化,从而造成整个系统内数据的rehashing。

为了解决这个问题,一致性哈希(consistent hashing)提出了不同的哈希处理方式,下面将具体介绍一致性哈希的设计:

  1. 环形哈希空间

    与传统哈希空间不同,在一致性哈希算法中,哈希空间被设计成一个环形空间,空间首尾相连。

  2. 键值对哈希映射

    通过哈希算法将输入的键值对映射到环形哈希空间上去。

  3. 节点哈希映射

    和键值对类似的,将系统内的节点也映射到同一个哈希空间上去(节点的键值可以是节点的IP或者唯一的别名)。

  4. 键值对-节点映射

    通过以上步骤,我们会得到一个环形哈希空间。在这个空间里,键值对和节点交错嵌入其中。接下来,我们把所有的键值对都映射到沿着环形空间顺时针遇到的第一个节点上。

  5. 增添/删除节点

    当需要增添一个新节点A时,我们按步骤3将新节点映射到环形哈希空间上来,然后从这个位置开始,逆时针一直遍历到下个节点B为止,将之间的键值对都映射到新节点A上来。

    需要删除一个节点A时,我们首先找到顺时针的下个节点B,从A的位置开始,逆时针一直遍历到下个节点C为止,将之间的键值对都映射到节点B上来。

在一致性哈希中,当增添或删除一个节点时,只需要部分数据的rehashing,从而大大降低了系统负载。

© 著作权归作者所有

共有 人打赏支持
dokia
粉丝 2
博文 21
码字总数 13612
作品 0
海淀
程序员

暂无相关文章

vim编辑模式、vim命令模式、vim实践

vim编辑模式 编辑模式用来输入或修改文本内容,编辑模式除了Esc外其他键几乎都是输入 如何进入编辑模式 一般模式输入以下按键,均可进入编辑模式,左下角提示 insert(中文为插入) 字样 i ...

蛋黄Yolks ⋅ 30分钟前 ⋅ 0

大数据入门基础:SSH介绍

什么是ssh 简单说,SSH是一种网络协议,用于计算机之间的加密登录。 如果一个用户从本地计算机,使用SSH协议登录另一台远程计算机,我们就可以认为,这种登录是安全的,即使被中途截获,密码...

董黎明 ⋅ 48分钟前 ⋅ 0

web3j教程

web3j是一个轻量级、高度模块化、响应式、类型安全的Java和Android类库提供丰富API,用于处理以太坊智能合约及与以太坊网络上的客户端(节点)进行集成。 汇智网最新发布的web3j教程,详细讲解...

汇智网教程 ⋅ 56分钟前 ⋅ 0

谷歌:安全问题机制并不如你想象中安全

腾讯科技讯 5月25日,如今的你或许已经对许多网站所使用的“安全问题机制”习以为常了,但你真的认为包括“你第一个宠物的名字是什么?”这些问题能够保障你的帐户安全吗? 根据谷歌(微博)安...

问题终结者 ⋅ 56分钟前 ⋅ 0

聊聊spring cloud gateway的RedisRateLimiter

序 本文主要研究下spring cloud gateway的RedisRateLimiter GatewayRedisAutoConfiguration spring-cloud-gateway-core-2.0.0.RELEASE-sources.jar!/org/springframework/cloud/gateway/con......

go4it ⋅ 今天 ⋅ 0

169. Majority Element - LeetCode

Question 169. Majority Element Solution 思路:构造一个map存储每个数字出现的次数,然后遍历map返回出现次数大于数组一半的数字. 还有一种思路是:对这个数组排序,次数超过n/2的元素必然在中...

yysue ⋅ 今天 ⋅ 0

NFS

14.1 NFS介绍 NFS是Network File System的缩写 NFS最早由Sun公司开发,分2,3,4三个版本,2和3由Sun起草开发,4.0开始Netapp公司参与并主导开发,最新为4.1版本 NFS数据传输基于RPC协议,RPC...

派派菠菜 ⋅ 今天 ⋅ 0

18.进入编辑模式 vim命令模式 实践

5.5 进入编辑模式 5.6 vim命令模式 5.7 vim实践 5.5 进入编辑模式: i 在当前字符前插入 I 在光标所在行的行首插入 a 在当前字符后插入 A 在光标所在行的行尾插入 o 在当前所在行的下一行插入...

王鑫linux ⋅ 今天 ⋅ 0

阻塞队列(2)--LinkedBlockingDeque底层实现

2.1 LinkedBlockingQueue是什么? 1.1 LinkedBlockingQueue是一个阻塞式的队列,继承自AbstractBlockingQueue,间接的实现了Queue接口和Collection接口。底层以链表的形式保存数据(双向链表,...

yokol ⋅ 今天 ⋅ 0

NFS介绍 NFS服务端安装配置 NFS配置选项

14.1 NFS介绍 14.2 NFS服务端安装配置 14.3 NFS配置选项 NFS介绍 NFS是Network File System的缩写;这个文件系统是基于网路层面,通过网络层面实现数据同步 NFS最早由Sun公司开发,分2,3,4三...

lyy549745 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部