文档章节

一致性哈希

dokia
 dokia
发布于 2015/05/12 15:00
字数 652
阅读 111
收藏 2

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

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
粉丝 3
博文 30
码字总数 37393
作品 0
海淀
程序员
使用虚拟节点改进的一致性哈希算法

分布式存储中的应用 ---在分布式存储系统中,将数据分布至多个节点的方式之一是使用哈希算法。假设初始节点数为 N,则传统的对 N 取模的映射方式存在一个问题在于:当节点增删,即 N 值变化时...

lionets
2014/07/07
0
6
百度海量日志处理——任务调度实践与优化

作者简介 运小军 百度高级研发工程师 负责百度运维部大规模日志处理、海量事件数据存储相关设计研发工作,在分布式系统架构、大数据存储计算、高性能网络服务和即时通讯服务有广泛实践经验。...

g2v13ah
2017/11/02
0
0
5分钟带你理解一致性Hash算法。

QQ用得起来越少了,现在就加入300+技术微信群,公众号回复"微信群"即可加入。 一致性Hash算法背景 一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是...

架构之路
2017/12/03
0
0
一致性哈希算法及其在分布式系统中的应用

摘要 本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题场景,借此介绍一致性哈希算法以及...

abing_hu
2013/09/01
0
0
一致性(连续性)hash算法(Consistent hashing)

一致性(连续性)hash算法(Consistent hashing) Consistent hashing is a scheme that provides hash table functionality in a way that the addition or removal of one slot does not s......

程序员诗人
2017/08/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何在Windows平台用Java代码暴力破解WIFI密码

由于新搬的地方没有覆盖移动的宽带,最近手头又紧。所以暂时先没安宽带,但是一天用流量,也撑不住啊。看着流量哗啦啦的溜走。住的地方在6楼,然后房子是底商的格局,于是就动起了蹭网的小心...

耒耒耒耒耒
刚刚
0
0
兄弟连区块链教程以太坊源码分析core-vm-stack-memory源码分析

vm使用了stack.go里面的对象Stack来作为虚拟机的堆栈。memory代表了虚拟机里面使用的内存对象。 stack 比较简单,就是用1024个big.Int的定长数组来作为堆栈的存储。 构造 // stack is an...

兄弟连区块链入门教程
2分钟前
0
0
zabbix报错cannot set resource limit: [13] Permission denied解决方法

zabbix报错cannot set resource limit: [13] Permission denied解决方法 zabbix-server启动时出现以下错误: 1 2 3 4 2912:20180326:050930.023 using configuration file: /etc/zabbix/zab......

linjin200
6分钟前
0
0
kotlin使用spring mvc(四)

使用Interceptor拦截器 Filter 是在 Servlet 规范中定义的,是 Servlet 容器支持的。而拦截器是在 Spring容器内的,是Spring框架支持的。Filter在只在 Servlet 前后起作用。Filters 通常将 ...

weidedong
12分钟前
0
0
DAC测试链(TestNet)记录

20181022 DAC测试链(TestNet)记录 1、DAC 文档 https://github.com/linkdt-tech/DAC/blob/master/doc/createAsset.md 2、按照文档安装后,进入 dacd 目录 cd /opt/cd dacd_testnet/** 直......

wwzzhh166
16分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部