OpenStack_Swift源代码分析——Ring基本原理及一致性Hash算法

1、Ring的基本概念

Ring是swfit中最重要的组件。用于记录存储对象与物理位置之间的映射关系,当用户须要对Account、Container、Object操作时,就须要查询相应的Ring文件(Account、Container、Object都有自己相应的Ring),Ring 使用Region(近期几个版本号中新增加的)、Zone、Device、Partition和Replica来维护这些信息,对于每个对象,依据你在部署swift设置的Replica数量,集群中会存有Replica个对象。部署完毕后,相应的Ring文件也创建,如我上篇博客中部署演示样例,在/etc/swift中会存有Ring文件。

2、Ring基本原理及一致性Hash算法

2、1一致性Hash算法

Swift利用一致性Hash算法构建了一个冗余扩展的分布式对象存储集群、Swift採用一致性哈希的主要目的是在改变集群的device数量时。可以尽可能少地改变已存在Key和device的映射关系。本文将对一致性Hash算法进行一些理解性的介绍,关于一致性Hash算法其它參考资料做详细的理解。

swift中一致性hash算法的详细代码实现,我将在下边几篇博客中详细介绍。

2、2、1 Ring环形空间

OpenStack_Swift源代码分析——Ring基本原理及一致性Hash算法

图1 环形Ring

如图所看到的的。hash算法将value映射成一个0—2**32-1的数值空间。

2.1.2 对象映射到Ring

如果有四个对象、通过hash函数计算每个对象相应的hash值在环上的分布例如以下。

swift中利用了MD5哈希算法,依据对象的名字进行hash的:

hash(object1)=key1;

...........

hash(object4)=key4

OpenStack_Swift源代码分析——Ring基本原理及一致性Hash算法

图2 object的key值映射到Ring

2.1.3 存储设备映射到Ring

相应存储设备,利用相同的Hash算法。将value映射到环上。假如有三个设备device1。device2。device3。他们相应的hash值为dev1,dev2,dev3,其在Ring上的分布例如以下图所看到的。

OpenStack_Swift源代码分析——Ring基本原理及一致性Hash算法

图3 设备映射到Ring

2.1.4 对象和设备的映射

如今设备和对象通过hash算法都映射到了Ring上。那么怎样将对象映射到将要存储的设备上呐,在这个环。每个对象从自己在环上的位置開始,按顺时针方向移动,直到遇到一个设备,则把对象存入到此设备上,如上图所看到的。则key1会映射到dev2。key4映射到dev3,key3,key2映射到dev1。假设添加一个设备device4,若其hash值为dev5。其在Ring上的映射为

OpenStack_Swift源代码分析——Ring基本原理及一致性Hash算法

图4 新增设备后的Ring

对于新增的设备device4。环中须要变动的对象仅仅有key3所相应的对象。它在按顺时针找设备时找到的是device4而不是device1,其它的数据存储不变。这样降低了数据的迁移。

2.1.5虚拟节点

平衡性是hash算法的一个重要指标,平衡性是指对于存储的全部对象,尽可能均匀的分不到全部的设备上去。如上图所看到的,若是hash算法所算出的对象hash值大多数落在顺时针方向的key4到key2之间时。还是按如上方法对象映射设备,device2就得到非常少的对象存储。以至于其它三个设备承受了比較大的压力。显然这样设计是不符合实际需求的。引入虚拟节点能非常好的解决此问题。

虚拟节点实际上是实际节点在空间中的复制品,一个实际的节点相应若干个虚拟的节点,增加虚拟节点后,对象的存储从对象—设备的映射转换为对象——虚拟节点——设备的映射,虚拟节点在空间中按hash值排列。

假如虚拟节点为20个,他们均匀的分布在Ring中。每个设备对一个的虚拟节点为5个。对象映射设备时变为如图所看到的的过程:

OpenStack_Swift源代码分析——Ring基本原理及一致性Hash算法

图5 对象—虚拟节点—设备映射过程

2.2 Ring 基本原理

2.2.1Replica

假设数据在整个集群中仅仅有一份,一旦发生问题就可能会造成数据的永久性丢失。因此。须要有冗余的副本来保证数据安全。Swift中引入了Replica的概念,其默认值为3,在部署时可也指定详细的本分树。理论根据主要来源于NWR策略(也叫Quorum协议)。

NWR是一种在分布式存储系统中用于控制一致性级别的策略。在Amazon的Dynamo云存储系统中,使用了NWR来控制一致性。

当中。N代表同一份数据的Replica的份数,W是更新一个数据对象时须要确保成功更新的份数。R代表读取一个数据须要读取的Replica的份数。
公式W+R>N,保证某个数据不被两个不同的事务同一时候读和写。公式W>N/2保证两个事务不能并发写某一个数据。

在分布式系统中,数据的单点是不同意存在的。即线上正常存在的Replica数量为1的情况是很危急的,由于一旦这个Replica再次出错,就可能发生数据的永久性错误。

假如我们把N设置成为2,那么仅仅要有一个存储节点发生损坏,就会有单点的存在。所以N必须大于2。N越高。系统的维护成本和总体成本就越高。

工业界通常把N设置为3。

2.2.2 Zone

假设全部的设备都在一个机架或一个机房中。那么一旦发生断电、网络故障等。都将造成用户无法訪问。因此须要一种机制对机器的物理位置进行隔离,以满足分区容忍性(CAP理论中的P)。因此。Ring中引入了Zone的概念,把集群的device分配到每一个Zone中。

在swift 中当中同一个Partition的Replica不能在同一个Zone内,也就是说全部的数据备份应该分布在不同的zone中。在近期版本号的swift 中又引入了比Zone更大的概念Region。

2.2.3  Weight

在Ring每个设备引入了weight概念。weight 的作用就是,假如一个集群中有的设备容量为1T。有的为2T、3T,对于不共同的设备,在存储数据时,我们肯定希望容量的更大的设备有很多其它的被选择的机会。存储很多其它的对象,通过设置weight。存储容量多的设备有更大的权重。它也就有了更大的part_wants,那么就会有很多其它的虚拟节点和它映射,有很多其它的虚拟节点映射后,对象就有更大的可能落在它所相应的虚拟节点上,这样就会有很多其它的机会得到对象。

2.2.4 数据迁移时间

在部署swift 时能够设定数据的 最小迁移时间如我上篇博客swift部署中指示的为1个小时

swift-ring-builder object.builder create 18 3 1

3 一致性Hash算法在Ring中的应用

上两节介绍了Ring的基本原理以及一致性hash算法的原理,如今解说Ring是怎样使用一致性hash算法的。

在Ring 中有一个replica2part2dev(备份到分区到设备的映射),replica2part2dev是含有replica(replica为正整数时。)个子list的list,,每个子list含有2**power个元素。当replica为>1的float值时会有int[replica]+1个子list,当中最后一个list长度为(replica-int[replica])*2**power。比方在2.2.4中部署时指示的power为18
。replica为3,而每个元素中存放的是设备的id。

例如以下所看到的power为8。replica为3。3个设备且在三个zone中,经过reassign_parts后得到的replica2part2dev,0,1,2即为设备的ID。

[ [2, 2, 0, 0, 2, 0, 0, 2, 1, 0, 0, 0, 2, 0, 1, 2, 2, 0, 1, 0, 0, 0, 1, 2, 1, 1, 1, 2, 0, 2, 2, 0, 1, 0, 2, 1, 1, 0, 2, 0, 2, 1, 0, 1, 1, 0, 1, 1, 0, 2, 0, 1, 1, 1, 2, 2, 0, 2, 1, 1, 2, 2, 2, 2, 1, 1, 0, 2, 1, 1, 0, 2, 0, 0,
1, 1, 1, 2, 0, 0, 0, 1, 0, 2, 0, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 0, 2, 1, 2, 0, 1, 1, 2, 2, 0, 2, 1, 2, 2, 0, 1, 1, 0, 0, 2, 1, 0, 2, 0, 2, 2, 0, 1, 0, 2, 0, 1, 1, 1, 0, 2, 2, 1, 1, 0, 0, 1, 1, 0, 1, 2, 0, 0, 0, 0, 0, 1, 2, 2, 2, 0, 2, 2, 2, 0, 0, 1, 0, 0,
0, 0, 2, 2, 2, 2, 0, 1, 0, 1, 2, 2, 1, 1, 1, 1, 0, 2, 2, 1, 0, 1, 0, 2, 2, 1, 2, 1, 2, 0, 2, 2, 0, 2, 0, 1, 0, 1, 2, 1, 1, 2, 2, 1, 0, 2, 1, 2, 2, 0, 0, 0, 1, 2, 2, 0, 0, 2, 1, 2, 1, 1, 1, 1, 1, 2, 2, 0, 1, 1, 0, 1, 2, 2, 2, 0, 2, 2, 0, 1, 2, 1, 2, 0, 0, 2,
0, 0, 1, 1, 0, 2, 2, 2, 0, 1],

 [1, 1, 1, 1, 1, 1, 1, 0, 2, 2, 1, 2, 1, 1, 0, 1, 1, 2, 0, 2, 1, 2, 0, 1, 2, 0, 0, 0, 1, 0, 1, 1, 2, 2, 1, 0, 2, 2, 0, 2, 1, 2, 1, 0, 0, 1, 2, 2, 2, 0, 2, 2, 0, 0, 1, 0, 2, 1, 2, 2, 1, 1, 0, 0, 0, 2, 1, 0, 2, 2, 2, 1, 1, 1, 0, 0, 2, 0, 2, 2, 2, 0, 2, 0, 2,
2, 0, 0, 0, 0, 2, 2, 1, 0, 0, 0, 1, 1, 0, 1, 2, 0, 2, 1, 1, 1, 0, 0, 0, 0, 1, 2, 2, 2, 2, 1, 2, 2, 1, 2, 0, 1, 1, 0, 1, 0, 2, 0, 0, 2, 2, 1, 0, 0, 2, 1, 1, 2, 0, 2, 0, 1, 2, 2, 1, 2, 1, 0, 1, 1, 1, 2, 0, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 0, 0, 1, 2, 0, 1, 2, 1,
1, 2, 0, 2, 0, 1, 1, 1, 2, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 2, 0, 2, 0, 0, 2, 2, 1, 1, 0, 2, 1, 2, 1, 1, 2, 2, 2, 2, 1, 1, 1, 2, 1, 2, 1, 2, 0, 0, 0, 2, 0, 1, 2, 2, 2, 2, 0, 1, 0, 0, 2, 1, 1, 1, 2, 1, 0, 0, 2, 1, 0, 2, 2, 0, 2, 2, 1, 1, 1, 1, 2],

[0, 0, 2, 2, 0, 2, 2, 1, 0, 1, 2, 1, 0, 2, 2, 0, 0, 1, 2, 1, 2, 1, 2, 0, 0, 2, 2, 1, 2, 1, 0, 2, 0, 1, 0, 2, 0, 1, 1, 1, 0, 0, 2, 2, 2, 2, 0, 0, 1, 1, 1, 0, 2, 2, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 2, 0, 2, 1, 0, 0, 1, 0, 2, 2, 2, 2, 0, 1, 1, 1, 1, 2, 1, 1, 1, 0,
2, 2, 2, 1, 0, 0, 0, 1, 2, 1, 2, 0, 2, 0, 1, 2, 0, 0, 0, 2, 1, 2, 1, 1, 2, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 2, 2, 2, 1, 1, 2, 2, 0, 1, 0, 1, 2, 0, 2, 2, 0, 2, 1, 2, 0, 1, 1, 2, 1, 2, 2, 0, 0, 0, 1, 1, 0, 0, 2, 2, 0, 2, 2, 1, 1, 0, 1, 1, 0, 1, 2, 2, 0, 0, 0,
0, 2, 0, 2, 2, 0, 0, 0, 2, 2, 2, 0, 1, 2, 0, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 2, 1, 0, 0, 0, 0, 2, 2, 2, 0, 1, 0, 1, 0, 0, 1, 2, 0, 1, 1, 1, 0, 0, 2, 0, 0, 2, 1, 1, 2, 1, 1, 1, 2, 0, 1, 0, 0, 0, 2, 0]]

在得到replica2part2dev后,当对象须要存放时,首先 依据对象的名字account/container/object。计算出其相应的hash值。取hash值的前4个字节(32位)。将其右移32-power位。得到值即为partion的值,从partion中取出replica个相应设备的id,依据设备的id得到设备的其它属性返回,设备的其它属性中包括了设备的ip地址。port等信息,通过http请求,和三个设备建立链接,由于三个设备中执行了object-server,他们接收这些请求,将数据存入到设备中。
如图所看到的环的执行机制

OpenStack_Swift源代码分析——Ring基本原理及一致性Hash算法

图6 环的执行机制

參考资料:

1、http://www.ibm.com/developerworks/cn/cloud/library/1310_zhanghua_openstackswift/

2、http://blog.csdn.net/sparkliang/article/details/5279393?reload

上一篇:20175314 实验四 Android开发基础


下一篇:IE8“开发人员工具”使用详解上(各级菜单详解)