深入云存储系统Swift核心组件：Ring实现原理剖析.docx

《深入云存储系统Swift核心组件：Ring实现原理剖析.docx》由会员分享，可在线阅读，更多相关《深入云存储系统Swift核心组件：Ring实现原理剖析.docx（12页珍藏版）》请在优知文库上搜索。

1、深入云存储系统SWift核心组件：Ring实现原理剖析简介OpenStack是个美国国家航空航天局和Rackspace合作研发的开源云计算工程，并成为Apache下的一个重要开源工程，目前已经开展到了180家公司参与其中。OpenStackObjectStorage(Swift)是OPenStaCk开源云计算工程的子工程之、SWift的目的是使用普通硬件来构建冗余的、可扩展的分布式对象存储集群，存储容量可达PB级。OPenStaCkObjeetStOrage最初由RaCkSPaCe采用Python语言开发，并于2010年7月奉献给OpenStack,作为该开源工程的一局部。它的目的是用于托管R

2、ackspace的CloudFilesservice,原始工程代号是swift,所以沿用至今。在分布式对象存储中的一个关键问题是数据该如何存放。Ring是SWift中最重要的组件，用于记录存储对象与物理位置间映射关系。在涉及查询account、containerObjeCt信息时就需要查询集群的ring信息。先来看一下Swift文档中关于Ring的描述：Ring用来确定数据驻留在集群中的位置。有单独对应于ACCOUnt数据库、Container数据库和单个ObjeCt的ring。Ring中每个partition在集群中都(默认)有3个replica。每个partition的位置由ring来维护

3、,并存储在映射中。Ring使用zone的概念来保证数据的隔离。每个partition的replica都确保放在了不同的zone中。一个Zone可以是一个硬盘，一个效劳器，一个机架，一个交换机，甚至是一个数据中心在上述Ring的特性描述中提到了Ring使用zone、device、partition和replica等等来维护数据和磁盘间的映射信息。那么在Ring的背后采用什么算法，使用了什么机制来保证数据的平安、高效和可扩展呢？这些概念对于数据存储带来了什么好处？本文逐步深入探讨了Swift如何通过Ring组件来实现冗余的、可扩展的目的。1 .普通Hash算法与场景分析先来看一个简单的例子假设我们

4、手里有N台存储效劳器(以下简称node),打算用于图片文件存储，为了使效劳器的负载均衡，需要把对象均匀地映射到每台效劳器上，通常会使用哈希算法来实现，计算步骤如下：2 .计算object的hash值Key3 .计算KeymodN值有N个存储节点，将Key模N得到的余数就是该Key对应的值需要存放的节点。比方，N是2,那么值为0、1、2、3、4的Key需要分别存放在0、1、0、1和。号节点上。如果哈希算法是均匀的，数据就会被平均分配到两个节点中。如果每个数据的访问量比拟平均，负载也会被平均分配到两个节点上。但是，当数据量和访问量进一步增加，两个节点无法满足需求的时候，需要增加个节点来效劳客户端的

5、请求。这时，N变成了3,映射关系变成了Keymod(N+1),因此，上述哈希值为2、3、4的数据需要重新分配(2-server2,3-server0,4-server1)o如果数据量很大的话，那么数据量的迁移工作将会非常大。当N已经很大，从N参加一个节点变成N+1个节点的过程，会导致整个哈希环的重新分配，这个过程几乎是无法容忍的，几乎全部的数据都要重新移动一遍。我们举例说明，假设有100个node的集群，将U项数据使用md5hash算法分配到每个node中，Python代码如下：fromhashlibimportmd5fromstructimportunpack_fromNODE_COUNT=

6、100DATA_ID_COUNT=10000000node_counts=0*NODE_COUNTfordata_idinxrange(DA7A_ID_COUNT):datajd=str(datajd)#Thisjustpullspartofthehashoutasanintegerhsh=unpack-from(,zmd5(dataJd).digest()0nodejd=hsh%NODE_COUNTnode_countsnode_id+=1desired_count=DATA_ID_COUNT/NODE_COUNTprint,%d:Desireddataidspernode%desired_

7、countmax-count=max(node_counts)over=100.0*(max_count-desired_count)/desired_countprint,%d:Mostdataidsononenode,%.02f%over,%(max_count,over)min_count=min(node_counts)under=100.0*(desired_count-min-count)/desired_countprint,%d:Leastdataidsononenode,%.02f%under%(min-countzunder)100000:Desireddataidsper

8、node100695:Mostdataidsononenode,0.69%over99073:Leastdataidsononenode,0.93%under分布结果如下所示：名称数据项数量百分比值数据项均值1000000%最多数据项节点100695+0.69%最少数据项节点99073-0.93%从数据分布上来看拥有最多/最少数据项的节点没有超出平均值的1%。现在假设增加一个节点提供负载能力，不过得重新分配数据项到新的节点上，代码如下：fromhashlibimportmd5fromstructimportunpack_fromNODE_COUNT=100NEW_NODE_COUNT=101D

9、ATA_ID_COUNT=10000000movedjds三0fordatajdinrange(DATA_ID_COUNT):datajd=str(datajd)hsh=unpack-from(,zmd5(str(dataJd).digest()0nodejd=hsh%NODE_COUNTnew_node_id=hsh%NEW_NODE_COUNTifnodejd!=new_node_id:movedjds+=1percent_moved=100.0*movedjds/DATA_ID_COUNTprint,%didsmoved,%.02f%,%(moved_idszpercent_moved)

10、9900989idsmoved,99.01%通过计算我们发现，为了提高集群1%的存储能力，我们需要移动9900989个数据项，也就是99.01%的数据项！显然，这种算法严重地影响了系统的性能和可扩展性。增加1%的存储能力=移动99%的数据？这种亏本生意显然做不得，那么怎么办呢？一致性哈希算法就是为了解决这个问题而来。2.一致性哈希算法一致性哈希算法是由D.Darger、E.Lehman和T.Leighton等人于1997年在论文COnSiStentHashingandRandomTreesrDistributedCachingProtocolsforRelievingHotSpotsOnthe

11、WorldWideWeb首次提出，目的主要是为了解决分布式网络中的热点问题。在其论文中，提出了一致性哈希算法并给出了衡量一个哈希算法的4个指标：平衡性（BaIanCe）平衡性是指Hash的结果能够尽可能分布均匀，充分利用所有缓存空间。单调性（MonotoniCity）单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲参加到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。分散性（SPread）分散性定义了分布式环境中，不同终端通过HaSh过程将内容映射至缓存上时，因可见缓存不同，Hash结果不一致，相同的内容被映

12、射至不同的缓冲区。负载（LOad）负载是对分散性要求的另一个纬度。既然不同的终端可以将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。SWift使用该算法的主要目的是在改变集群的node数量时（增加/删除效劳器），能够尽可能少地改变已存在key和node的映射关系，以满足单调性。一致性哈希一般两种思路：1 .迁移为主要特点（SWift初期采用）2 .引入虚结点，减少移动为特点（SWift现采用）具体步骤如下：1 .首先求出每个节点（机器名或者是IP地址）的哈希值，并将其分配到一个圆环区间上（这里取0-232）o2 .求出需要存储对象的哈希值，也

13、将其分配到这个圆环上。3 .从对象映射到的位置开始顺时针查找，将对象保存到找到的第一个节点上。其中这个从哈希到位置映射的圆环，我们就可以理解为何使用术语“Ring”来表示了。哈希环空间上的分布如图1所示：图1哈希环空间假设在这个环形哈希空间中，CacheS被映射在Cache3和Cache4之间，那么受影响的将仅是沿Cache5逆时针遍历直到下一个CaChe（Cache3）之间的对象（它们本来映射到CaChe4上）。图2一致性哈希算法的数据移动现在，使用该算法在集群中增加个node,同时要保证每个节点的数据项数量均衡，代码如下所示，其中node_range_starts表示每个node的数据项的

14、开始位置。frombisectimportbisectjeftfromhashlibimportmd5fromstructimportunpack_fromNODE-CONT=100NEW_NODE_COUNT=101DATA_ID_COUNT=10000000node_range_starts=fornodejdinxrage(NODE-COUNT):node_range_starts.append(DATA_ID_COUNT/NODE_COUNTnodejd)new_node_range_starts=fornew_node_idinxrange(NEW_NODE_COUNT):new_n

15、ode_range_starts.append(DZKTA_ID_COUNT/NEW_NODE_COUNT*new_node_id)movedjds=0fordata_idinxrange(DA7A_ID_COUNT):datajd=str(datajd)hsh=UnPaCk_from(S/,md5(str(dataJd),digest()0nodejd=bisect_left(node_range_starts,hsh%DATA_ID_COUNT)%NODE_COUNTnew_node_id=bisect_left(new_node_range_startszhsh%DATA_ID_COUNT)%NEW_NODE_COUNTifnodejd!=new_node_id:movedjds+=1percent_moved=100.0*movedjds/DA17_ID_COUNTprint,%didsmoved,%.02f%,%(movedjds,percent_moved)4901707idsmoved,49.02%结果虽然比之前好了些，但是提高1%的性能与移动50%的数据仍不理想。增加1%能力=移动50%数据？引入虚拟节点