文档章节

一致性哈希

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,从而大大降低了系统负载。

© 著作权归作者所有

共有 人打赏支持
上一篇: 一致性raft算法
下一篇: sync.Pool 内部实现
dokia
粉丝 3
博文 30
码字总数 37393
作品 0
海淀
程序员
私信 提问
查找--深入理解一致性哈希算法

注:本篇博客只是讲述了一致性哈希的思想,我们会在之后讲述分布式哈希表以及一致性哈希的一种实现(Chord算法)。 什么是一致性哈希算法? 引用自维基百科: 一致性哈希是一种特殊的哈希算法...

珩翊
06/26
0
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

没有更多内容

加载失败,请刷新页面

加载更多

关于MySQL 通用查询日志和慢查询日志分析

MySQL中的日志包括:错误日志、二进制日志、通用查询日志、慢查询日志等等。这里主要介绍下比较常用的两个功能:通用查询日志和慢查询日志。 1)通用查询日志:记录建立的客户端连接和执行的...

瑞查德-Jack
19分钟前
0
0
Vue组件封装 参数传递和事件传递

参数传递 子组件先定义好接收的参数和事件 <div > {{title}} <div class="row"> <Button icon="md-refresh" @click="refresh()" >刷新</Button> </div>......

Carbenson
24分钟前
0
0
如何在10分钟内设置EOS钱包和帐户?

由于SuperNode超级节点社区建立在EOS之上,我们希望引导我们的社区成员设置EOS钱包和帐户,以便充分参与我们的生态系统。 虽然设置过程可能不如其他区块链系统那么简单,但不要担心。本指南旨...

笔阁
28分钟前
2
0
8.04-Win10非U盘重装系统

注意:最好准备一个你所需版本的秘钥(不能是数字0开头的) 【所需:Win10的ISO镜像、能够解压ISO格式的解压缩工具、最好准备你所需版本的秘钥(不能是数字0开头的)】 1、创建新的文件系统为...

静以修身2025
29分钟前
1
0
Docker的架构与自制镜像的发布

一. docker 是什么 大家都知道虚拟机吧,windows 上装个 linux 虚拟机是大部分程序员的常用方案。公司生产环境大多也是虚拟机,虚拟机将物理硬件资源虚拟化,按需分配和使用,虚拟机使用起来...

程序猿拿Q
45分钟前
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部