首页 > 代码库 > OpenStack_Swift源码分析——Ring基本原理及一致性Hash算法
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环形空间
图1 环形Ring
如图所示的，hash算法将value映射成一个0—2**32-1的数值空间。
2.1.2 对象映射到Ring
假设有四个对象、通过hash函数计算每一个对象对应的hash值在环上的分布如下。swift中利用了MD5哈希算法，根据对象的名字进行hash的：
hash(object1)=key1;
...........
hash(object4)=key4
图2 object的key值映射到Ring
2.1.3 存储设备映射到Ring
对应存储设备，利用同样的Hash算法，将value映射到环上，假如有三个设备device1，device2，device3，他们对应的hash值为dev1,dev2,dev3,其在Ring上的分布如下图所示。
图3 设备映射到Ring
2.1.4 对象和设备的映射
现在设备和对象通过hash算法都映射到了Ring上，那么如何将对象映射到将要存储的设备上呐，在这个环，每一个对象从自己在环上的位置开始，按顺时针方向移动，直到遇到一个设备，则把对象存入到此设备上，如上图所示，则key1会映射到dev2，key4映射到dev3，key3，key2映射到dev1。如果增加一个设备device4，若其hash值为dev5，其在Ring上的映射为
图4 新增设备后的Ring
对于新增的设备device4，环中需要变动的对象只有key3所对应的对象，它在按顺时针找设备时找到的是device4而不是device1，其他的数据存储不变，这样减少了数据的迁移。
2.1.5虚拟节点
平衡性是hash算法的一个重要指标，平衡性是指对于存储的所有对象，尽可能均匀的分不到所有的设备上去。如上图所示，若是hash算法所算出的对象hash值大多数落在顺时针方向的key4到key2之间时，还是按如上方法对象映射设备，device2就得到很少的对象存储，以至于其他三个设备承受了比较大的压力。显然这样设计是不符合实际需求的。引入虚拟节点能很好的解决此问题。
虚拟节点实际上是实际节点在空间中的复制品，一个实际的节点对应若干个虚拟的节点，加入虚拟节点后，对象的存储从对象—设备的映射转换为对象——虚拟节点——设备的映射，虚拟节点在空间中按hash值排列。假如虚拟节点为20个，他们均匀的分布在Ring中，每一个设备对一个的虚拟节点为5个，对象映射设备时变为如图所示的过程：
图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，他们接收这些请求，将数据存入到设备中。 如图所示环的运行机制
图6 环的运行机制
参考资料：
1、http://www.ibm.com/developerworks/cn/cloud/library/1310_zhanghua_openstackswift/
2、http://blog.csdn.net/sparkliang/article/details/5279393?reload