文档章节

分布式存储和一致性hash

令飞
 令飞
发布于 2015/04/23 17:54
字数 1921
阅读 9950
收藏 32
点赞 2
评论 4

本文我将对一致性算法作介绍,同时谈谈自己对一致性hash和一般意义上的hash算法的区别

hash是什么

hash即hash算法,又称为散列算法,百度百科的定义是

哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。

1.这句话有几个很重要的地方,首先是任意长度二进制,在java中,可以代表所有对象(序列化)

2.固定长度,使得hashmap等可以按照高低位进行位操作,同时能够提供统一的方式(有种协议的感觉)

3.数据唯一的数值,使得hashcode可以作为查找的依据(快速查找的根本)

为什么hash

说为什么首先要说说如果没有会怎么样。

csdn有这样一篇文章讲的很有意思,我们有一堆猪,怎么根据体重找到对应的一头。如果没有hash的思想,我们会比较每头猪,但是如果有1000头你也这样做么。引入hash,每头猪的重量hash到一个hashcode,hashcode会映射到对应的猪圈,我们只要比较每个猪圈的猪就行了,而最理想的情况就是每个猪圈的猪都一样多(注:每个猪圈一个是好,但是空间消耗巨大)

http://blog.csdn.net/ok7758521ok/article/details/4003476)

而java中,hash也是采用这样的方式,通过hashcode与桶数取模的方式(当然时间是通过位操作,性能更高)自然映射到具体的桶中。

关于分布式存储

当hash遇上分布式,单台机子的hashmap存储已经不能满足我们的key-value需求,怎么办,我们需要把存储内容分布到不同的实体机上,这时需要一种把key映射到不同机器的方法,我们想起了hash,可以把实体机当做是桶,采用和hashmap实现一样的思路,通过和实体机的数量取模,自然映射到不同的机器。

ok,搞定,分布式确实可以实现。但现在问题来了,如果其中一台机子挂了,或者又加了一台机子怎么办,这时出现两种情况:

    1.不做任何改变,那么挂了的数据将无法得到恢复,新增的机子也无法得到利用

    2.rehash 这种情况,桶的数量将会改变,所有的值将重新映射,最终数据会得到存储,这有两个问题,rehash的时刻,所有key将重新映射,这时,对于大并发的情形,是灾难的,所有请求将不经过任何缓存,服务器面临崩溃的风险,再者,老的数据依然还在,并且不会被用到,浪费存储空间。

那么,怎么办


引入一致性hash

consistent hashing 是这样一种 hash 算法,简单的说,在移除 / 添加一个 节点(机器,ip)时,它能够尽可能小的改变已存在 key 映射关系,尽可能的满足单调性()的要求。

hash回环

任何的hash值都是固定长度的,因此可以通过一个回环来承载所有的hash值(为什么用环后面会说)


映射

hash最总要的一步就是把对象映射到对应的桶,而与通常的hash做法相比,一致性hash会比较特殊,一致性hash不会将key直接映射到桶,而将key和桶分别映射到回环的对应hash值节点


        映射key


 

        映射桶

接下来是最重要的一步,把key映射到对应的桶

寻桶

现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了,接下来要考虑的就是如何将对象映射到 cache 上面了。

在这个环形空间中,如果沿着顺时针方向从对象的 key 值出发,直到遇见一个 cache ,那么就将该对象存储在这个 cache 上,因为对象和 cache  hash 值是固定的,因此这个 cache 必然是唯一和确定的。这样不就找到了对象和 cache 的映射方法了吗?!

依然继续上面的例子(参见图 3 ),那么根据上面的方法,对象 object1 将被存储到 cache A 上; object2 object3 对应到 cache C  object4 对应到 cache B 


好处

我们讲了这么多一致性hash的算法,那么他究竟带来了什么,我们分添加和删除的情况考虑

    添加

    

我们添加一个新的节点D,按照顺时针的方式,原先映射到C的object2会映射到D,而object3则还是映射到C,这样添加只会影响到object2,事实上是B和D之间的对象,这种影响相比传统的方式,影响是很小的

删除


与添加类似,删除也只会影响A和B之间的对象


虚拟节点(一下完全引自:http://my.oschina.net/jsan/blog/49702)

考量 Hash 算法的另一个指标是平衡性 (Balance) ,定义如下:

平衡性

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。

hash 算法并不是保证绝对的平衡,如果 cache 较少的话,对象并不能被均匀的映射到 cache 上,比如在上面的例子中,仅部署 cache A  cache C 的情况下,在 4 个对象中, cache A 仅存储了 object1 ,而 cache C 则存储了 object2  object3  object4 ;分布是很不均衡的。

为了解决这种情况, consistent hashing 引入了“虚拟节点”的概念,它可以如下定义:

“虚拟节点”( virtual node )是实际节点在 hash 空间的复制品( replica ),一实际个节点对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。

仍以仅部署 cache A  cache C 的情况为例,在图 4 中我们已经看到, cache 分布并不均匀。现在我们引入虚拟节点,并设置“复制个数”为 2 ,这就意味着一共会存在 4 个“虚拟节点”, cache A1, cache A2 代表了 cache A  cache C1, cache C2 代表了 cache C ;假设一种比较理想的情况,参见图 6 

virtual nodes

 引入“虚拟节点”后的映射关系

 

此时,对象到“虚拟节点”的映射关系为:

objec1->cache A2  objec2->cache A1  objec3->cache C1  objec4->cache C2 

因此对象 object1  object2 都被映射到了 cache A 上,而 object3  object4 映射到了 cache C 上;平衡性有了很大提高。

引入“虚拟节点”后,映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache时的映射关系如图 7 所示。

map

 查询对象所在 cache

 

“虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 cache A  IP 地址为202.168.14.241 

引入“虚拟节点”前,计算 cache A  hash 值:

Hash(“202.168.14.241”);

引入“虚拟节点”后,计算“虚拟节”点 cache A1  cache A2  hash 值:

Hash(“202.168.14.241#1”);  // cache A1

Hash(“202.168.14.241#2”);  // cache A2


参考

http://my.oschina.net/u/1166485/blog/136663

http://my.oschina.net/jsan/blog/49702


© 著作权归作者所有

共有 人打赏支持
令飞
粉丝 45
博文 21
码字总数 14127
作品 0
杭州
程序员
加载中

评论(4)

z
zsyn
我尽量用直白的语言总结了自己对一致性hash的理解,欢迎交流
http://www.zsythink.net/archives/1182
一叶舟troy
一叶舟troy
都说从网上抄袭的 时间不是这样用的呢
一叶舟troy
一叶舟troy
加入新增机器,相邻的节点key 仍然需要重新分配,对外无法访问业务,没有完全解决这个问题呀?
【策略】一致性Hash算法

转载请说明出处:http://blog.csdn.net/cywosp/article/details/23397179 一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Ho...

无信不立 ⋅ 2017/05/17 ⋅ 0

[算法] 从 Memcached 分布式应用看一致性哈希散列函数的选择

一致性哈希算法来源于 P2P 网络的路由算法,目前主流的 P2P 软件就是利用我们所熟知的 DHT (Distributed Hash Table,分布式哈希表) 来定位整个分布式网络的信息,另外此算法在目前火热的云计...

长平狐 ⋅ 2012/11/19 ⋅ 0

Java-No.09 一致性哈希算法原理及实现

一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简 单哈希算...

shawntime ⋅ 2015/07/16 ⋅ 0

五分钟理解一致性哈希算法(consistent hashing)

简介: 一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简 ...

MLGKO ⋅ 2015/11/16 ⋅ 0

[置顶] 每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)

一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简 单哈希算...

zh119893 ⋅ 2014/05/24 ⋅ 0

五分钟理解一致性哈希算法(consistent hashing)

一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hotspot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法...

天天顺利 ⋅ 2015/09/16 ⋅ 0

五分钟理解一致性哈希算法(consistent hashing)

转载请说明出处:http://blog.csdn.net/cywosp/article/details/23397179 一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Ho...

tragedyhome ⋅ 2015/08/21 ⋅ 0

一致性哈希算法——虚拟节点

一致性哈希算法——虚拟节点 一致性哈希算法是分布式系统中常用的算法。比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节点上,如k...

秋风醉了 ⋅ 2015/03/12 ⋅ 0

memcache的一致性hash算法使用

一、概述 1、我们的memcache客户端(这里我看的spymemcache的源码),使用了一致性hash算法ketama进行数据存储节点的选择。与常规的hash算法思路不同,只是对我们要存储数据的key进行hash计算...

技术小胖子 ⋅ 2017/11/09 ⋅ 0

分布式设计与开发

分布式设计与开发 CAP原理和最终一致性(Eventually Consistency) 分布式算法 [分布式Paxos算法] 分布式一致性Hash算法 轮循算法(Round Robin) Hash求余算法(Hash) 最少连接算法(Least C...

陶邦仁 ⋅ 2015/12/08 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spring | IOC AOP 注解 简单使用

写在前面的话 很久没更新笔记了,有人会抱怨:小冯啊,你是不是在偷懒啊,没有学习了。老哥,真的冤枉:我觉得我自己很菜,还在努力学习呢,正在学习Vue.js做管理系统呢。即便这样,我还是不...

Wenyi_Feng ⋅ 今天 ⋅ 0

博客迁移到 https://www.jianshu.com/u/aa501451a235

博客迁移到 https://www.jianshu.com/u/aa501451a235 本博客不再更新

为为02 ⋅ 今天 ⋅ 0

win10怎么彻底关闭自动更新

win10自带的更新每天都很多,每一次下载都要占用大量网络,而且安装要等得时间也蛮久的。 工具/原料 Win10 方法/步骤 单击左下角开始菜单点击设置图标进入设置界面 在设置窗口中输入“服务”...

阿K1225 ⋅ 今天 ⋅ 0

Elasticsearch 6.3.0 SQL功能使用案例分享

The best elasticsearch highlevel java rest api-----bboss Elasticsearch 6.3.0 官方新推出的SQL检索插件非常不错,本文一个实际案例来介绍其使用方法。 1.代码中的sql检索 @Testpu...

bboss ⋅ 今天 ⋅ 0

informix数据库在linux中的安装以及用java/c/c++访问

一、安装前准备 安装JDK(略) 到IBM官网上下载informix软件:iif.12.10.FC9DE.linux-x86_64.tar放在某个大家都可以访问的目录比如:/mypkg,并解压到该目录下。 我也放到了百度云和天翼云上...

wangxuwei ⋅ 今天 ⋅ 0

PHP语言系统ZBLOG或许无法重现月光博客的闪耀历史[图]

最近在写博客,希望通过自己努力打造一个优秀的教育类主题博客,名动江湖,但是问题来了,现在写博客还有前途吗?面对强大的自媒体站点围剿,还有信心和可能型吗? 至于程序部分,我选择了P...

原创小博客 ⋅ 今天 ⋅ 0

IntelliJ IDEA 2018.1新特性

工欲善其事必先利其器,如果有一款IDE可以让你更高效地专注于开发以及源码阅读,为什么不试一试? 本文转载自:netty技术内幕 3月27日,jetbrains正式发布期待已久的IntelliJ IDEA 2018.1,再...

Romane ⋅ 今天 ⋅ 0

浅谈设计模式之工厂模式

工厂模式(Factory Pattern)是 Java 中最常用的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。 在工厂模式中,我们在创建对象时不会对客户端暴露创建逻...

佛系程序猿灬 ⋅ 今天 ⋅ 0

Dockerfile基础命令总结

FROM 指定使用的基础base image FROM scratch # 制作base image ,不使用任何基础imageFROM centos # 使用base imageFROM ubuntu:14.04 尽量使用官方的base image,为了安全 LABEL 描述作...

ExtreU ⋅ 昨天 ⋅ 0

存储,对比私有云和公有云的不同

导读 说起公共存储,很难不与后网络公司时代的选择性外包联系起来,但尽管如此,它还是具备着简单和固有的可用性。公共存储的名字听起来也缺乏专有性,很像是把东西直接堆放在那里而不会得到...

问题终结者 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部