文档章节

一致性哈希

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
粉丝 2
博文 29
码字总数 36553
作品 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
Cassandra的一致性哈希(Consistent Hashing)和虚拟节点(Virtual Nodes)的关系

本文原文出处: http://blog.csdn.net/bluishglc/article/details/52847591 严禁任何形式的转载,否则将委托CSDN官方维护权益! 一致性哈希所要解决的问题 一般的哈希算法存在的问题是:当“模...

bluishglc
2016/10/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

go语言学习总结

一、描述 go语言是直接将源码编译成二进制机器码的语言;它支持面向对象、也支持函数式编程;支持并发很容易; 二、基本语法学习路径 https://studygolang.com/subject/2...

盼望明天
25分钟前
1
0
JSP 九大内置对象及其作用域

JSP 中一共预先定义了 9 个这样的对象,分别为:request、response、session、application、out、pagecontext、config、page、exception ,下面就简单介绍下。 1、request 对象 request 对象...

几个栗子
36分钟前
0
0
Java中的坑之方括号

Java中的坑之方括号 这一段时间,在做项目的时候,发现了一个坑,这个坑说大不大,说小不小,不知道的足够喝一壶,知道的就可以轻松解决。 问题描述 在做数据统计的时候,遇见了如下形式的数...

星汉
46分钟前
1
0
[雪峰磁针石博客]python机器学习、web开发等书籍汇总

Building Machine Learning Systems with Python Third Edition - 2018.pdf 下载地址 Get more from your data by creating practical machine learning systems with Python Key Features ......

python测试开发人工智能安全
57分钟前
1
0
文件的压缩与解压(linux)

Linux下*.tar.gz文件解压缩命令 1.压缩命令:   命令格式:tar -zcvf 压缩后文件名.tar.gz 被压缩文件名 可先切换到当前目录下。压缩文件名和被压缩文件名都可加入路径。 2.解压缩命令: ...

qimh
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部