《深入云存储系统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_COUN
16、T)%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%数据？引入虚拟节点(PartitiOn)考虑到哈希算法并不是保证绝对的平衡，尤其node较少的话，对象并不能被均匀的映射到node上。为Jz解决这种情况，一致性哈希引入了“虚拟节点”
17、的概念：“虚拟节点”是实际节点在环形空间的复制品，一个实际节点对应了假设干个“虚拟节点”，“虚拟节点”在哈希空间中以哈希值排列。图3虚拟节点引入了“虚拟节点”后，映射关系就从object-node转换成了objectvirtualnodenodeo查询object所在node的映射关系如下列图所示。图4对象、虚结点、节点间的映射关系对100个node细分为1000个vnode,使用Vnode_range_starts来指定vnode的开始范围，vnode2node表示Vnode到node的指派，然后增加一个node,完成VnOde的重新分配，并计算所移动的数据项：frombisectimpor
18、tbisectjeftfromhashlibimportmd5fromstructimportunpack_fromNODE_COUNT=100DATA_ID_COUNT=10000000VNODE_COUNT=1000vnode_range_starts=vnode2node=forvnodejdinxrange(VNODE_COUNT):vnode_range_starts.append(DATAJD_COUNT/VNODE_COUNT*vnodejd)vnode2node.append(vnodejd%NODE_COUNT)new_vnode2node=Iist(vnode2node)n
19、ew_node_id=NODE_COUNTNEW_NODE_COUNT=NODE_COUNT+1vnodes_to_reassign=VNODE-CONT/NEW_NODE_COUNTwhilevnodes_to_reassign0:fornode_to_take_frominxrange(NODE_COUNT):forvnodejd,node_idinenumerate(new_vnode2node):ifnode_id=node_to_take_from:new_vnode2nodevnode_id=new_node_idvnodes_to_reassign-=1ifvnodes_to_r
20、eassign=0:breakifvnodes_to_reassign,zmd5(str(dataJd).digest()0vnodejd=bisect_left(vnode_range_starts,hsh%DATA_ID_COUNT)%VNODE_COUNTnodejd=vnode2nodevnodejdnew_node_id=new_vnode2nodevnode_idifnodejd!=new_node_id:movedjds+=1percent_moved=100.0*movedjds/DA17_ID_COUNTprint,%didsmoved,%.02f%,%(movedjds,p
21、ercent_moved)90108idsmoved,0.90%结果显示，仅移动了09%的数据。与前面相比，整个集群的性能大大提高了。add 一兴 CaPab三ty增加1%的能力=移动0.9%数据固化虚节点到数据项的映射由于虚节点个数在集群的整个生命周期中是不会变化的，它与数据项的映射关系不会发生变化，改变的仅是vnode与node的映射关系，所以需对以上代码进行优化。fromstructimportunpack_fromfromhashlibimportmd5fromtimeimporttimeNODE_COUNT=100DATA_ID_COUNT=10000000VNODE_COUNT=1
22、000begin=time()vnode2node=forvnode_idinxrange(VNODE_COUNT):vnode2node.append(vnodejd%NODE_COUNT)new_vnode2node=Iist(vnode2node)new_node_id=NODE_COUNTvnodes_to_assign=VNODE_COUNT/(NODE_COUNT+1)whilevnodes_to_assign0:fornode_to_take_frominxrange(NODE_COUNT):forvnodejd,nodejdinenumerate(vnode2node):ifn
23、odejd=node_to_take_from:vnode2nodevnodejd=new_node_idvnodes_to_assign-=1ifvnodes_to_assign=0:breakifvnodes_to_assign,zmd5(str(dataJd).digest()0vnodejd=hsh%VNODE_COUNT#nodejd=vnode2nodevnodejdnewnodeid=newvnode2nodevnodeidifnodejd!=new_node_id:movedjd+=1percent_moved=100.0*movedjd/DA1A_ID_COUNTprint%
24、didsmoved,%.02%(movedjd,percent_moved)print%dsecondspass.,%(time()-begin)90108idsmoved,0.90%预设合理的虚结点数现在已构建好了一致性哈希ring的原型。但是存在一个问题，以上例子中，1000个虚结点对应着100个结点，结点变动时，虚结点就需要重新分配到结点。当100个结点扩展到IoOl个结点时，此时至少有一个结点分配不到虚结点，那么就需要再增加虚结点数，而虚结点是与数据项对应的哈希关系，如果改变了虚节点数，那么就需要重新分配所有的数据项，这将导致移动大量的数据。所以在设置虚结点数的时候，需要对系统预期的规
25、模做充分考虑，假设集群的规模不会超过6000个结点，那么可以将虚结点数设置为结点数的100倍。这样，变动任意一个结点的负载仅影响1%的数据项。此时有6百万个vnode数，使用2bytes来存储结点数(065535)根本的内存占用是6*106*2bytes=12Mb,对于效劳器来说完全可以承受。在此，引入了2个概念：在SWift中，为了区分VnOde和node,将Vnode称为PartitiOn。位操作代替取模操作此夕卜，在计算机中使用位操作来确定Partition的位置比取模更快。所以，在此引入了partitionpowerS概念。继续改良ring的代码，设有65536个node(216),有
26、128(27)倍个PartitiOn数(2八23)。由于MD5码是32位的，使用PARTrnoN_SHIFT(等于32-PARTrnoN_POWER)将数据项的MD5哈希值映射到partition的2八23的空间中。fromarrayimportarrayfromhashlibimportmd5fromstructimportunpack_fromPARTITION_POWER=23PARTITION_SHIFT=32-PARTITION_POWERNODE-CONT=65536DATA_ID_COUNT=100000000part2node=array(,H,)forpartinrange(
27、2*PARTITION_POWER):part2node.append(part%NODE_COUNT)node_counts=0*NODE_COUNTfordatajdinxrange(DA7A_ID_COUNT):data_id=str(datajd)part=unpack-from(,*zmd5(str(dataJd).digest()0PARTITION_SHIFTnodejd=part2nodepartnode_countsnode_id+=1desired_count=DATA_ID_COUNT/NODE_COUNTprint%d:Desireddataidspernode%des
28、ired_countmax_count=max(node_counts)over=100.0*(max_count-desired_count)/desired_countprint,%d:Mostdataidsononenode,%.02f%over,%(max-countzover)min_count=min(node_counts)under=100.0*(desired_count-min-count)/desired_countprint,%d:Leastdataidsononenode,%.02f%under%(min-count7under)1525:Desireddataids
29、pernode1683:Mostdataidsononenode,10.36%over1360:Leastdataidsononenode,10.82%under数据不均衡的原因在于数据项相对于PartitiOn数太小了(IoA8对2八23),假设数据项越多，分布越均衡。保证数据平安，引入replica到目前为止，在集群中的数据在本地节点上只有一份，节点一旦发生故障就可能会造成数据的永久性丧失。因此，SWift中引入replica的概念使用冗余副本来保证数据的平安。replica的默认值为3,其理论依据主要来源于NWR策略。NWR是种在分布式存储系统中用于控制一致性级别的种策略。在Amazon
30、的Dynamo云存储系统中，就应用NWR来控制一致性。每个字母的涵义如下：N：同一份数据的Replica的份数W：是更新一个数据对象的时候需要确保成功更新的份数R：读取个数据需要读取的Replica的份数在分布式系统中，数据的单点是不允许存在的。即线上正常存在的Replica数量是1的情况是非常危险的，因为一旦这个RePliCa再次错误，就可能发生数据的永久性错误。假设我们把N设置成为2,那么，只要有一个存储节点发生损坏，就会有单点的存在。所以N必须大于2。N约高，系统的维护和整体本钱就越高。工业界通常把N设置为3。因此，在ring的代码中引入replica,数量设置为3,其中nodeds记录
31、的是3个replica存放的nodeid。Part2nodepart是根据partitionid找到对应的nodeid。fromarrayimportarrayfromhashlibimportmd5fromstructimportunpack_fromREPLICAS=3PARTITION_POWER=16PARTITION_SHIFT=32-PARTITION_POWERPARTITION_MAX=2*PARTITION_POWER-1NODE_COUNT=256DATA_ID_COUNT=10000000part2node=array(,H,)forpartinxrange(2*PART
32、ITION_POWER):part2node.叩Pend(Part%NODE_COUNT)node_counts=0*NODE_COUNTfordataJdinxrange(DATA_ID_COUNT):data_id=str(datajd)part=unpack-from(,zmd5(str(datajd).digest()PARTITION_SHIFTnodejds=part2nodepartnode_countsnode_ids0+=1forreplicainxrange(lzREPLICAS):whilepart2nodepartinnodejds:part+=1ifpartPARTI
33、TION_MAX:part=0nodejds.append(part2nodepart)node_countsnode_ids-l+=1desired_count=DA1A_ID_COUNT/NODE_COUNT*REPLICASprint%d:Desireddataidspernode%desired_countmax_count=ma(node-counts)over=100.0*(max_count-desired_count)/desired_countprint,%d:Mostdataidsononenode,%.02f%over,%(max_count,over)min_count
34、=min(node_counts)under=100.0*(desired_count-min-count)/desired_countprint,%d:Leastdataidsononenode,%.02f%under%(min-countzunder)117186:Desireddataidspernode118133:Mostdataidsononenode,0.81%over116093:Leastdataidsononenode,0.93%under结果如上，由于使用了256个node,分布约有1%的波动，比拟均匀了。但是存在有2个问题：随机分配映射首先part2node是基于顺序分
35、配的,对于给定的node,它所有partition的copies均在另两个node上，假设某个node频繁宕机,与它相应的两个node上的数据项需要频繁复制。解决方法是随机分配partition到node的映射。分区容忍性和引入ZOne其次是当前的集群不满足CAP原理中的分区容忍性(PartitionTolerance)。Gilbert和LynCh将分区容忍性定义如下：Nosetoffailureslessthantotalnetworkfailureisallowedtocausethesystemtorespondincorrectlyo翻译一下，就是除了全部网络节点发生故障以外，所有子节
36、点集合的故障都不允许导致整个系统的响应故障。现在为止，这些node都在一个机架上，一旦发生断电，网络故障，那么将丧失这一性质。因此就需要一种机制对机器的物理位置进行隔离。所以引入了zone的概念。在ring代码中引入Zone_count,把这些node分割到16个zone中去。其中partition的replica不能放在同一个node上或同一个zone内。fromarrayimportarrayfromhashlibimportmd5fromrandomimportshufflefromstructimportunpack_fromREPLICAS=3PARTITIONPOWER=16PAR
37、TITION_SHIFT=32-PARTITION_POWERPARTITION_MAX=2*PARTITION_POWER-1NODE_COUNT=256ZONE_COUNT=16DATA_ID_COUNT=10000000node2zone=whileIen(node2zone)NODE_COUNT:zone=0whilezoneZONE_COUNTandIen(node2zone),zmd5(str(datajd).digest()PARTITION_SHIFTnodejds=part2nodepartzones=node2zonenodejds011node_countsnode_id
38、s0+=1zone_countszones0+=1forreplicainxrange(lzREPLICAS):whilepart2nodepartinnodejdsandnode2zonepart2nodepartinzones:part+=1ifpartPARTITION_MAX:part=0nodejds.append(part2nodepart)zones.append(node2zonenodejds-l)node_countsnode_ids-l+=1zone_countszones-l+=1desired_count=DA7AJD_COUNT/NODE_COUNT*REPLICA
39、Sprint,%d:Desireddataidspernode%desired_countmax-count=max(node_counts)over=100.0*(max_count-desired_count)/desired-countprint%d:Mostdataidsononenode,%.02f%over,%(max-countzover)min_count=min(node_counts)under=100.0*(desired_count-min_count)/desired_countprint,%d:Leastdataidsononenode,%.02f%under1%(
40、min-countzunder)desired_count=DATA_ID_COUNT/ZONE_COUNT*REPLICASprint,%d:Desireddataidsperzone%desired_countmax-count=max(zone_counts)over=100.0*(max_count-desired_count)/desired_countprint%d:Mostdataidsinonezone,%.02f%over,%(max-countzover)min_count=min(zone_counts)under=100.0*(desired_count-min_cou
41、nt)/desired_countprint,%d:Leastdataidsinonezone,%.02f%under%(min-countzunder)117186:Desireddataidspernode118782:Mostdataidsononenode,1.36%over115632:Leastdataidsononenode,1.33%under1875000:Desireddataidsperzone1878533:Mostdataidsinonezone,0.19%over1869070:Leastdataidsinonezone,0.32%under到目前为止，ring的根
42、本功能都已经有了:一致性哈希ring、partitionpartitionpowerreplica、zoneo目前还差weight以及将以上代码改写为类封装成moduleoweight引入weight的概念，目的是“能者多劳”：解决未来添加存储能力更大的node时，使得可以分配到更多的partitiono例如，2T容量的node的partition数为IT的两倍。在ring的构建中，参加了Weight属性。本例中Weight简单地取1和2两个值，根据每个结点在Weight和中的比例分配所需partition数。fromarrayimportarrayfromhashlibimportmd5fr
43、omrandomimportshufflefromstructimportunpack_fromfromtimeimporttimeclassRing(Object):def_init_(Selfnodes,part2nodezreplicas):self.nodes=nodesself.part2node=part2nodeself.replicas=replicaspartition_power=1while2*partition_power,md5(dataJd).digest()0self.partition_shiftnodejds=self.part2nodepartzones=s
44、elf.nodesnodejds0forreplicainxrange(l,self.replicas):whileself.part2nodepartinnodejdsandself.nodesself.part2nodepartinzones:part+=1ifpart=Ien(self.part2node):part=0nodejds.append(self.part2nodepart)zones.append(self.nodesnodejds-l)returnself.nodesnforninnodejdsdefbuild_ring(nodes,partition-power;replicas):begin=time()parts=2*partition_powertotal_weight=float(sum(n,
