1、Ring實(shí)現(xiàn)原理剖析,簡(jiǎn)介,在分布式對(duì)象存儲(chǔ)中的一個(gè)關(guān)鍵問(wèn)題是數(shù)據(jù)該如何存放。Ring是Swift中最重要的組件，用于記錄存儲(chǔ)對(duì)象與物理位置間映射關(guān)系。在涉及查詢account、container、object信息時(shí)就需要查詢集群的ring信息。 Ring用來(lái)確定數(shù)據(jù)駐留在集群中的位置。有單獨(dú)對(duì)應(yīng)于Account數(shù)據(jù)庫(kù)、container數(shù)據(jù)庫(kù)和單個(gè)object的ring。 Ring中每個(gè)partition在集群中都(默認(rèn))有3個(gè)replica。每個(gè)partition的位置由ring來(lái)維護(hù),并存儲(chǔ)在映射中。 Ring使用zone的概念來(lái)保證數(shù)據(jù)的隔離。每個(gè)partition的replica都確

2、保放在了不同的zone中。一個(gè)zone可以是一個(gè)硬盤(pán)，一個(gè)服務(wù)器，一個(gè)機(jī)架，一個(gè)交換機(jī)，甚至是一個(gè)數(shù)據(jù)中心。,普通Hash算法與場(chǎng)景分析,假設(shè)我們手里有N臺(tái)存儲(chǔ)服務(wù)器（以下簡(jiǎn)稱node），打算用于圖片文件存儲(chǔ)，為了使服務(wù)器的負(fù)載均衡，需要把對(duì)象均勻地映射到每臺(tái)服務(wù)器上，通常會(huì)使用哈希算法來(lái)實(shí)現(xiàn)，計(jì)算步驟如下： 1.計(jì)算object的hash值Key 2.計(jì)算Key mod N值 假設(shè)有100個(gè)node的集群，將10000000項(xiàng)數(shù)據(jù)使用md5 hash算法分配到每個(gè)node中，Python代碼如下： from hashlib import md5 from struct import unpa

3、ck_from NODE_COUNT = 100 DATA_ID_COUNT = 10000000 node_counts = 0 * NODE_COUNT for data_id in xrange(DATA_ID_COUNT): data_id = str(data_id) hsh = unpack_from(I, md5(data_id).digest()0,node_id = hsh % NODE_COUNT node_countsnode_id += 1 desired_count = DATA_ID_COUNT / NODE_COUNT print %d: Desired data

4、 ids per node % desired_count max_count = max(node_counts) over = 100.0 * (max_count - desired_count) / desired_count print %d: Most data ids on one node, %.02f% over % (max_count, over) min_count = min(node_counts) under = 100.0 * (desired_count - min_count) / desired_count print %d: Least data ids

5、 on one node, %.02f% under % (min_count, under) 100000: Desired data ids per node 100695: Most data ids on one node, 0.69% over 99073: Least data ids on one node, 0.93% under 從數(shù)據(jù)分布上來(lái)看擁有最多/最少數(shù)據(jù)項(xiàng)的節(jié)點(diǎn)沒(méi)有超出平均值的1%。,現(xiàn)在假設(shè)增加一個(gè)節(jié)點(diǎn)提供負(fù)載能力，不過(guò)得重新分配數(shù)據(jù)項(xiàng)到新的節(jié)點(diǎn)上 from hashlib import md5from struct import unpack_fromNODE_

6、COUNT =100NEW_NODE_COUNT =101DATA_ID_COUNT =10000000moved_ids =0fordata_id in xrange(DATA_ID_COUNT): data_id = str(data_id) hsh = unpack_from(I, md5(str(data_id).digest()0 node_id = hsh % NODE_COUNT new_node_id = hsh % NEW_NODE_COUNTifnode_id != new_node_id: moved_ids +=1percent_moved =100.0* moved_

7、ids / DATA_ID_COUNTprint%d ids moved, %.02f% (moved_ids, percent_moved)9900989ids moved,99.01% 通過(guò)計(jì)算我們發(fā)現(xiàn)，為了提高集群1%的存儲(chǔ)能力，我們需要移動(dòng)9900989個(gè)數(shù)據(jù)項(xiàng)，也就是99.01%的數(shù)據(jù)項(xiàng)！顯然，這種算法嚴(yán)重地影響了系統(tǒng)的性能和可擴(kuò)展性。,一致性哈希算法,平衡性(Balance) 平衡性是指Hash的結(jié)果能夠盡可能分布均勻，充分利用所有緩存空間。 單調(diào)性(Monotonicity) 單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過(guò)哈希分派到了相應(yīng)的緩沖中，又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證

8、原有已分配的內(nèi)容可以被映射到新的緩沖中去，而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)。 分散性(Spread) 分散性定義了分布式環(huán)境中，不同終端通過(guò)Hash過(guò)程將內(nèi)容映射至緩存上時(shí)，因可見(jiàn)緩存不同，Hash結(jié)果不一致，相同的內(nèi)容被映射至不同的緩沖區(qū)。 負(fù)載(Load) 負(fù)載是對(duì)分散性要求的另一個(gè)緯度。既然不同的終端可以將相同的內(nèi)容映射到不同的緩沖區(qū)中，那么對(duì)于一個(gè)特定的緩沖區(qū)而言，也可能被不同的用戶映射為不同的內(nèi)容。,Swift使用該算法的主要目的是在改變集群的node數(shù)量時(shí)（增加/刪除服務(wù)器），能夠盡可能少地改變已存在key和node的映射關(guān)系，以滿足單調(diào)性。但是性能依舊不是很理想。 考慮到

9、哈希算法在node較少的情況下，改變node數(shù)會(huì)帶來(lái)巨大的數(shù)據(jù)遷移。為了解決這種情況，一致性哈希引入了“虛擬節(jié)點(diǎn)”的概念： “虛擬節(jié)點(diǎn)”是實(shí)際節(jié)點(diǎn)在環(huán)形空間的復(fù)制品，一個(gè)實(shí)際節(jié)點(diǎn)對(duì)應(yīng)了若干個(gè)“虛擬節(jié)點(diǎn)”，“虛擬節(jié)點(diǎn)”在哈?？臻g中以哈希值排列。 查詢object所在node的映射關(guān)系如下圖所示,對(duì)100個(gè)node細(xì)分為1000個(gè)vnode，使用vnode_range_starts來(lái)指定vnode的開(kāi)始范圍，node_range_starts表示每個(gè)node的數(shù)據(jù)項(xiàng)的開(kāi)始位置vnode2node表示vnode到node的指派，然后增加一個(gè)node，完成vnode的重新分配，并計(jì)算所移動(dòng)的數(shù)據(jù)項(xiàng)：

10、from bisect import bisect_leftfrom hashlib import md5from struct import unpack_fromNODE_COUNT =100DATA_ID_COUNT =10000000VNODE_COUNT =1000vnode_range_starts = vnode2node = forvnode_id in xrange(VNODE_COUNT): vnode_range_starts.append(DATA_ID_COUNT / VNODE_COUNT * vnode_id) vnode2node.append(vnode_id

11、 % NODE_COUNT)new_vnode2node = list(vnode2node) new_node_id = NODE_COUNT NEW_NODE_COUNT = NODE_COUNT + 1 vnodes_to_reassign = VNODE_COUNT / NEW_NODE_COUNT,whilevnodes_to_reassign 0:fornode_to_take_from in xrange(NODE_COUNT):forvnode_id, node_id in enumerate(new_vnode2node):ifnode_id = node_to_take_f

12、rom: new_vnode2nodevnode_id = new_node_id vnodes_to_reassign -=1ifvnodes_to_reassign I, md5(str(data_id).digest()0 vnode_id = bisect_left(vnode_range_starts, hsh % DATA_ID_COUNT) % VNODE_COUNT node_id = vnode2nodevnode_id new_node_id = new_vnode2nodevnode_idifnode_id != new_node_id: moved_ids +=1per

13、cent_moved =100.0* moved_ids / DATA_ID_COUNTprint%d ids moved, %.02f% (moved_ids, percent_moved)90108ids moved,0.90% 結(jié)果顯示，僅移動(dòng)了0.9%的數(shù)據(jù)。與前面相比，整個(gè)集群的性能大大提高了。,預(yù)設(shè)合理的虛結(jié)點(diǎn)數(shù),現(xiàn)在已構(gòu)建好了一致性哈希ring的原型。但是存在一個(gè)問(wèn)題，以上例子中，1000個(gè)虛結(jié)點(diǎn)對(duì)應(yīng)著100個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)變動(dòng)時(shí)，虛結(jié)點(diǎn)就需要重新分配到結(jié)點(diǎn)。當(dāng)100個(gè)結(jié)點(diǎn)擴(kuò)展到1001個(gè)結(jié)點(diǎn)時(shí)，此時(shí)至少有一個(gè)結(jié)點(diǎn)分配不到虛結(jié)點(diǎn)，那么就需要再增加虛結(jié)點(diǎn)數(shù)，而虛結(jié)點(diǎn)是與數(shù)據(jù)項(xiàng)對(duì)應(yīng)的哈希

14、關(guān)系，如果改變了虛節(jié)點(diǎn)數(shù)，那么就需要重新分配所有的數(shù)據(jù)項(xiàng)，這將導(dǎo)致移動(dòng)大量的數(shù)據(jù)。 所以在設(shè)置虛結(jié)點(diǎn)數(shù)的時(shí)候，需要對(duì)系統(tǒng)預(yù)期的規(guī)模做充分考慮，假如集群的規(guī)模不會(huì)超過(guò)6000個(gè)結(jié)點(diǎn)，那么可以將虛結(jié)點(diǎn)數(shù)設(shè)置為結(jié)點(diǎn)數(shù)的100倍。這樣，變動(dòng)任意一個(gè)結(jié)點(diǎn)的負(fù)載僅影響1%的數(shù)據(jù)項(xiàng)。此時(shí)有6百萬(wàn)個(gè)vnode數(shù)，使用2bytes來(lái)存儲(chǔ)結(jié)點(diǎn)數(shù)(065535)?；镜膬?nèi)存占用是6*106*2bytes=12Mb，對(duì)于服務(wù)器來(lái)說(shuō)完全可以承受。,分區(qū)容忍性和引入zone,除了全部網(wǎng)絡(luò)節(jié)點(diǎn)發(fā)生故障以外，所有子節(jié)點(diǎn)集合的故障都不允許導(dǎo)致整個(gè)系統(tǒng)的響應(yīng)故障。這些node都在一個(gè)機(jī)架上，一旦發(fā)生斷電，網(wǎng)絡(luò)故障，那么將喪失這一

15、性質(zhì)。因此就需要一種機(jī)制對(duì)機(jī)器的物理位置進(jìn)行隔離。 node_ids記錄的是3個(gè)replica存放的node id。replica不能放在同一個(gè)node上或同一個(gè)zone內(nèi) from array import arrayfrom hashlib import md5from random import shufflefrom struct import unpack_fromREPLICAS =3PARTITION_POWER =16PARTITION_SHIFT =32- PARTITION_POWERPARTITION_MAX =2* PARTITION_POWER -1NODE_COUN

16、T =256ZONE_COUNT =16DATA_ID_COUNT =10000000node2zone = whilelen(node2zone) NODE_COUNT: zone =0whilezone ZONE_COUNT and len(node2zone) NODE_COUNT: node2zone.append(zone) zone +=1part2node = array(H),forpart in xrange(2* PARTITION_POWER): part2node.append(part % NODE_COUNT)shuffle(part2node)node_count

17、s = 0 * NODE_COUNTzone_counts = 0 * ZONE_COUNTfordata_id in xrange(DATA_ID_COUNT): data_id = str(data_id) part = unpack_from(I, md5(str(data_id).digest()0 PARTITION_SHIFT node_ids = part2nodepart zones = node2zonenode_ids0 node_countsnode_ids0 +=1 zone_countszones0 +=1forreplica in xrange(1, REPLICA

18、S):whilepart2nodepart in node_ids and node2zonepart2nodepart in zones: part +=1ifpart PARTITION_MAX: part =0 node_ids.append(part2nodepart) zones.append(node2zonenode_ids-1) node_countsnode_ids-1 +=1 zone_countszones-1 +=1desired_count = DATA_ID_COUNT / NODE_COUNT * REPLICAS,print%d: Desired data ids per zone% desired_countmax_count = max(zone_counts)over =100.0* (max_count - desired_count) / desired_countprint%d: Most data ids in one zone, %.02f% over% (max_count, over)min_count = min(zone_counts)under =100.0* (desired_count - min_count) / desired_countprint%d: Least data i