StackDoc

人人IT網-StackDoc

當前位置: 主頁 > 編程語言 > PHP >

深入雲存儲系統Swift核心組件:Ring實現原理剖析

時間:2012-06-22 11:02來源:Internet 作者:Internet 點擊:
簡介 OpenStack是一個美國國家航空航天局和Rackspace合作研發的開源雲計算項目,並成为Apache下的一個重要開源項目,目前已經發展到了180家公司参與其中。 OpenStack Obj

簡介

OpenStack是一個美國國家航空航天局和Rackspace合作研發的開源雲計算項目,並成为Apache下的一個重要開源項目,目前已經發展到了180家公司参與其中。

OpenStack Object StorageSwiftOpenStack開源雲計算項目的子項目之一。Swift的目的是使用普通硬件來構建冗餘的、可擴展的分布式對象存儲集群,存儲容量可達PB級。OpenStack Object Storage 最初由 Rackspace 采用Python語言開發,並於 2010 7 月貢獻给 OpenStack ,作为該開源項目的一部分。它的目的是用於托管 Rackspace Cloud Files service ,原始項目代號是 swift,所以沿用至今。

在分布式對象存儲中的一個關鍵問題是數據該如何存放。RingSwift中最重要的組件,用於記錄存儲對象與物理位置間映射關系。在涉及查詢accountcontainerobject信息時就需要查詢集群的ring信息。

 

先來看一下Swift文檔中關於Ring的描述:

       Ring用來確定數據駐留在集群中的位置。有單獨對應於Account數據庫、container數據庫和單個objectring

       Ring中每個partition在集群中都(默認)3replica。每個partition的位置由ring來維護,並存儲在映射中。

       Ring使用zone的概念來保證數據的隔離。每個partitionreplica都確保放在了不同的zone中。一個zone可以是一個硬盤,一個服務器,一個機架,一個交換機,甚至是一個數據中心............

.......

 

在上述Ring的特性描述中提到了Ring使用zonedevicepartitionreplica等等來維護數據和磁盤間的映射信息。那麼在Ring的背後采用什麼算法,使用了什麼機制來保證數據的安全、高效和可擴展呢?這些概念對於數據存儲帶來了什麼好處?本文逐步深入探討了Swift如何通過Ring組件來實現冗餘的、可擴展的目的。

 

 

1.      普通Hash算法與場景分析

 

 

先來看一個簡單的例子假設我們手裏有N台存儲服務器(以下簡稱node),打算用於圖片文件存儲,为了使服務器的負載均衡,需要把對象均勻地映射到每台服務器上,通常會使用哈希算法來實現,計算步驟如下:

 

1.計算objecthashKey

2.計算Key mod N

      

N個存儲節點,將KeyN得到的餘數就是該Key對應的值需要存放的節點。比如,N2,那麼值为01234Key需要分別存放在01010號節點上。如果哈希算法是均勻的,數據就會被平均分配到兩個節點中。如果每個數據的訪問量比較平均,負載也會被平均分配到兩個節點上。

但是,當數據量和訪問量進一步增加,兩個節點無法滿足需求的時候,需要增加一個節點來服務客戶端的請求。這時,N變成了3,映射關系變成了Key mod (N+1),因此,上述哈希值为234的數據需要重新分配(2->server 23 -> server 04 -> server 1)。如果數據量很大的話,那麼數據量的遷移工作將會非常大。當N已經很大,從N加入一個節點變成N+1個節點的過程,會導致整個哈希環的重新分配,這個過程幾乎是無法容忍的,幾乎全部的數據都要重新移動一遍。

       我們舉例說明,假設有100node的集群,將107項數據使用md5 hash算法分配到每個node中,Python代碼如下:

from hashlib import md5
from struct import unpack_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)
   
# This just pulls part of the hash out as an integer

    hsh = unpack_from(
'>I', md5(data_id).digest())[0]
    node_id = hsh % NODE_COUNT
    node_counts[node_id] +=
1

desired_count = DATA_ID_COUNT / NODE_COUNT
print '%d: Desired data 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 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

      

分布結果如下所示:

    

名稱

數據項數量

百分比值

數據項均值

100000

0%

最多數據項節點

100695

+0.69%

最少數據項節點

99073

-0.93%

 

       從數據分布上來看擁有最多/最少數據項的節點沒有超出平均值的1%。現在假設增加一個節點提供負載能力,不過得重新分配數據項到新的節點上,代碼如下:

 

from hashlib import md5
from struct import unpack_from 

NODE_COUNT =
100

NEW_NODE_COUNT =
101
DATA_ID_COUNT =
10000000

moved_ids =
0
for data_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_COUNT
   
if
node_id != new_node_id:
        moved_ids +=
1

percent_moved =
100.0 * moved_ids / DATA_ID_COUNT
print '%d ids moved, %.02f%%'
% (moved_ids, percent_moved)

9900989 ids moved, 99.01
%

 

通過計算我們發現,为了提高集群1%的存儲能力,我們需要移動9900989個數據項,也就是99.01%的數據項!顯然,這種算法嚴重地影響了系統的性能和可擴展性。

clip_image002[4]增加1%的存儲能力=移動99%的數據?

 

 這種虧本生意顯然做不得,那麼怎麼辦呢?一致性哈希算法就是为了解决這個問題而來。

 

 

2.      一致性哈希算法

      

一致性哈希算法是由D. Darger、E. Lehman和T. Leighton 等人於1997年在論文Consistent Hashing and Random Trees:Distributed Caching Protocols for Relieving Hot Spots On the World Wide Web首次提出,目的主要是为了解决分布式網络中的熱點問題。在其論文中,提出了一致性哈希算法並给出了衡量一個哈希算法的4個指標:

 

平衡性(Balance)

       平衡性是指Hash的結果能夠盡可能分布均勻,充分利用所有緩存空間

單調性(Monotonicity)

       單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中,又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖中去,而不會被映射到舊的緩沖集合中的其他緩沖區。

分散性(Spread)

       分散性定義了分布式環境中,不同終端通過Hash過程將內容映射至緩存上時,因可見緩存不同,Hash結果不一致,相同的內容被映射至不同的緩沖區。

負載(Load)

       負載是對分散性要求的另一個緯度。既然不同的終端可以將相同的內容映射到不同的緩沖區中,那麼對於一個特定的緩沖區而言,也可能被不同的用戶映射为不同的內容。

 

Swift使用該算法的主要目的是在改變集群的node數量時(增加/刪除服務器),能夠盡可能少地改變已存在keynode的映射關系,以滿足單調性。一致性哈希一般兩種思路:

1.遷移为主要特點(swift初期采用)

2.引入虛結點,減少移動为特點(swift現采用)

       具體步驟如下:

       1.    首先求出每個節點(機器名或者是IP地址)的哈希值,並將其分配到一個圓環區間上(這裏取0-2^32)。

       2.    求出需要存儲對象的哈希值,也將其分配到這個圓環上。

       3.    從對象映射到的位置開始順時針查找,將對象保存到找到的第一個節點上。

       其中這個從哈希到位置映射的圓環,我們就可以理解为何使用術語“Ring”來表示了。哈希環空間上的分布如圖1所示:

 

clip_image004[4]

1 哈希環空間

  假設在這個環形哈希空間中,Cache5被映射在Cache3Cache4之間,那麼受影響的將僅是沿Cache5逆時針遍曆直到下一個CacheCache3)之間的對象(它們本來映射到Cache4上)。

clip_image006[4]

2 一致性哈希算法的數據移動

 

   現在,使用該算法在集群中增加一個node,同時要保證每個節點的數據項數量均衡,代碼如下所示,其中node_range_starts表示每個node的數據項的開始位置。

from bisect import bisect_left
from hashlib import md5
from struct import unpack_from

NODE_COUNT =
100

NEW_NODE_COUNT =
101
DATA_ID_COUNT =
10000000

node_range_starts = []
for node_id in xrange(NODE_COUNT):
    node_range_starts.append(DATA_ID_COUNT /
                             NODE_COUNT * node_id)
new_node_range_starts = []

for
new_node_id in xrange(NEW_NODE_COUNT):
    new_node_range_starts.append(DATA_ID_COUNT /
                              NEW_NODE_COUNT * new_node_id)
moved_ids =
0

for data_id in xrange(DATA_ID_COUNT):
    data_id = str(data_id)
    hsh = unpack_from(
'>I', md5(str(data_id)).digest())[0
]
    node_id = bisect_left(node_range_starts,
                          hsh % DATA_ID_COUNT) % NODE_COUNT
    new_node_id = bisect_left(new_node_range_starts,
                          hsh % DATA_ID_COUNT) % NEW_NODE_COUNT
   
if
node_id != new_node_id:
        moved_ids +=
1

percent_moved =
100.0 * moved_ids / DATA_ID_COUNT
print '%d ids moved, %.02f%%'
% (moved_ids, percent_moved)

4901707 ids moved, 49.02
%

      

結果雖然比之前好了些,但是提高1%的性能與移動50%的數據仍不理想。

clip_image008[4]

增加1%能力=移動50%數據?

引入虛擬節點(Partition)

 

考慮到哈希算法並不是保證絕對的平衡,尤其node較少的話,對象並不能被均勻的映射到 node上。为了解决這種情況,一致性哈希引入了“虛擬節點”的概念: “虛擬節點”是實際節點在環形空間的复制品,一個實際節點對應了若幹個“虛擬節點”,“虛擬節點”在哈希空間中以哈希值排列。

clip_image010[4]

3 虛擬節點

       引入了“虛擬節點”後,映射關系就從【object--->node】轉換成了【object--->virtual node---> node】。查詢object所在node的映射關系如下圖所示。

clip_image012[4]

4 對象、虛結點、節點間的映射關系

 

       100node細分为1000vnode,使用vnode_range_starts來指定vnode的開始範圍,vnode2node表示vnodenode的指派,然後增加一個node,完成vnode的重新分配,並計算所移動的數據項:

from bisect import bisect_left
from hashlib import md5
from struct import unpack_from

NODE_COUNT =
100

DATA_ID_COUNT =
10000000
VNODE_COUNT =
1000

vnode_range_starts = []
vnode2node = []

for vnode_id in xrange(VNODE_COUNT):
    vnode_range_starts.append(DATA_ID_COUNT /
                              VNODE_COUNT * vnode_id)
    vnode2node.append(vnode_id % 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
while vnodes_to_reassign > 0:
   
for
node_to_take_from in xrange(NODE_COUNT):
       
for
vnode_id, node_id in enumerate(new_vnode2node):
           
if
node_id == node_to_take_from:
                new_vnode2node[vnode_id] = new_node_id
                vnodes_to_reassign -=
1

               
if vnodes_to_reassign <= 0:
                   
break

       
if vnodes_to_reassign <= 0:
           
break

moved_ids =
0
for data_id in xrange(DATA_ID_COUNT):
    data_id = str(data_id)
    hsh = unpack_from(
'>I', md5(str(data_id)).digest())[0
]
    vnode_id = bisect_left(vnode_range_starts,
                         hsh % DATA_ID_COUNT) % VNODE_COUNT
    node_id = vnode2node[vnode_id]
    new_node_id = new_vnode2node[vnode_id]
   
if
node_id != new_node_id:
        moved_ids +=
1

percent_moved =
100.0 * moved_ids / DATA_ID_COUNT
print '%d ids moved, %.02f%%'
% (moved_ids, percent_moved)

90108 ids moved, 0.90
%

      

結果顯示,僅移動了0.9%的數據。與前面相比,整個集群的性能大大提高了。

clip_image014[4]增加1%的能力=移動0.9%數據

 

  固化虛節點到數據項的映射

 

由於虛節點個數在集群的整個生命周期中是不會變化的,它與數據項的映射關系不會發生變化,改變的僅是vnodenode的映射關系,所以需對以上代碼進行優化。

from struct import unpack_from
from hashlib import md5
from time import time

NODE_COUNT =
100

DATA_ID_COUNT =
10000000
VNODE_COUNT =
1000

begin = time()
vnode2node = []

for vnode_id in xrange(VNODE_COUNT):
    vnode2node.append(vnode_id % NODE_COUNT)
new_vnode2node = list(vnode2node)
new_node_id = NODE_COUNT
vnodes_to_assign = VNODE_COUNT / (NODE_COUNT +
1
)
while vnodes_to_assign > 0
:
   
for
node_to_take_from in xrange(NODE_COUNT):
       
for
vnode_id, node_id in enumerate(vnode2node):
           
if
node_id == node_to_take_from:
                vnode2node[vnode_id] = new_node_id
                vnodes_to_assign -=
1

               
if vnodes_to_assign <= 0:
                   
break

       
if vnodes_to_assign <= 0:
           
break

moved_id =
0
for data_id in xrange(DATA_ID_COUNT):
    data_id = str(data_id)
    hsh = unpack_from(
'>I', md5(str(data_id)).digest())[0
]
    vnode_id = hsh % VNODE_COUNT
#(1)

    node_id = vnode2node[vnode_id]
    new_node_id = new_vnode2node[vnode_id]
   
if node_id != new_node_id:
        moved_id +=
1

percent_moved =
100.0 * moved_id / DATA_ID_COUNT
print '%d ids moved, %.02f%%'
% (moved_id, percent_moved)
print '%d seconds pass ...'
% (time() - begin)

90108 ids moved, 0.90
%

 

 

  預設合理的虛結點數

 

       現在已構建好了一致性哈希ring的原型。但是存在一個問題,以上例子中,1000個虛結點對應着100個結點,結點變動時,虛結點就需要重新分配到結點。當100個結點擴展到1001個結點時,此時至少有一個結點分配不到虛結點,那麼就需要再增加虛結點數,而虛結點是與數據項對應的哈希關系,如果改變了虛節點數,那麼就需要重新分配所有的數據項,這將導致移動大量的數據。

       所以在設置虛結點數的時候,需要對系統預期的規模做充分考慮,假如集群的規模不會超過6000個結點,那麼可以將虛結點數設置为結點數的100倍。這样,變動任意一個結點的負載僅影響1%的數據項。此時有6百萬個vnode數,使用2bytes來存儲結點數(0~65535)。基本的內存占用是6*106*2bytes=12Mb,對於服務器來說完全可以承受。

       在此,引入了2個概念:

       swift中,为了區分vnodenode,將vnode稱为partition

 

  位操作代替取模操作

 

       此外,在計算機中使用位操作來確定partition的位置比取模更快。所以,在此引入了partition power的概念。

       繼續改進ring的代碼,設有65536node(2^16),有1282^7)倍個partition(2^23)。由於MD5碼是32位的,使用PARTITION_SHIFT(等於32- PARTITION_POWER)將數據項的MD5哈希值映射到partition2^23的空間中。

from array import array
from hashlib import md5
from struct import unpack_from

PARTITION_POWER =
23

PARTITION_SHIFT =
32 - PARTITION_POWER
NODE_COUNT =
65536

DATA_ID_COUNT =
100000000

part2node = array(
'H')
for part in xrange(2
** PARTITION_POWER):
    part2node.append(part % NODE_COUNT)
node_counts = [
0
] * NODE_COUNT
for
data_id in xrange(DATA_ID_COUNT):
    data_id = str(data_id)
    part = unpack_from(
'>I'
,
        md5(str(data_id)).digest())[
0
] >> PARTITION_SHIFT
    node_id = part2node[part]
    node_counts[node_id] +=
1

desired_count = DATA_ID_COUNT / NODE_COUNT
print '%d: Desired data 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 on one node, %.02f%% under'
% \
    (min_count, under)


1525
: Desired data ids per node
1683: Most data ids on one node, 10.36
% over
1360: Least data ids on one node, 10.82
% under

       數據不均衡的原因在於數據項相對於partition數太小了(10^82^23),若數據項越多,分布越均衡。

 

保證數據安全,引入replica

 

到目前为止,在集群中的數據在本地節點上只有一份,節點一旦發生故障就可能會造成數據的永久性丟失。因此,Swift中引入replica的概念使用冗餘副本來保證數據的安全。replica的默認值为3,其理論依據主要來源於NWR策略。

       NWR是一種在分布式存儲系統中用於控制一致性級別的一種策略。在AmazonDynamo雲存儲系統中,就應用NWR來控制一致性。每個字母的涵義如下:

       N:同一份數據的Replica的份數
       W
:是更新一個數據對象的時候需要確保成功更新的份數
       R
讀取一個數據需要讀取的Replica
的份數

       在分布式系統中,數據的單點是不允許存在的。即線上正常存在的Replica數量是1的情況是非常危險的,因为一旦這個Replica再次錯誤,就可能發生數據的永久性錯誤。假如我們把N設置成为2,那麼,只要有一個存儲節點發生損壞,就會有單點的存在。所以N必須大於2N約高,系統的維護和整體成本就越高。工業界通常把N設置为3

       因此,在ring的代碼中引入replica,數量設置为3,其中 node_ids記錄的是3replica存放的node idpart2node[part]是根據partition id 找到對應的node id

from array import array
from hashlib import md5
from struct import unpack_from

REPLICAS =
3

PARTITION_POWER =
16
PARTITION_SHIFT =
32 - PARTITION_POWER
PARTITION_MAX =
2 ** PARTITION_POWER - 1

NODE_COUNT =
256
DATA_ID_COUNT =
10000000

part2node = array(
'H')
for part in xrange(2
** PARTITION_POWER):
    part2node.append(part % NODE_COUNT)
node_counts = [
0
] * NODE_COUNT
for
data_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 = [part2node[part]]
    node_counts[node_ids[
0]] += 1

   
for replica in xrange(1, REPLICAS):
       
while
part2node[part] in node_ids:
            part +=
1

           
if part > PARTITION_MAX:
                part =
0

        node_ids.append(part2node[part])
        node_counts[node_ids[-
1]] += 1
desired_count = DATA_ID_COUNT / NODE_COUNT * REPLICAS
print '%d: Desired data 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 on one node, %.02f%% under'
% \
    (min_count, under)


117186
: Desired data ids per node
118133: Most data ids on one node, 0.81
% over
116093: Least data ids on one node, 0.93
% under

      

    結果如上,由於使用了256node,分布約有1%的波動,比較均勻了。

但是存在有2個問題:

  隨機分配映射

       首先part2node是基於順序分配的,對於给定的node,它所有partitioncopies均在另兩個node上,若某個node頻繁宕機,與它相應的兩個node上的數據項需要頻繁复制。解决方法是隨機分配partitionnode的映射。

 

  分區容忍性和引入zone

       其次是當前的集群不滿足CAP原理中的分區容忍性(Partition Tolerance)。Gilbert Lynch分區容忍性定義如下:

       No set of failures less than total network failure is allowed to cause the system to respond incorrectly

         翻譯一下,就是除了全部網络節點發生故障以外,所有子節點集合的故障都不允許導致整個系統的響應故障。

現在为止,這些node都在一個機架上,一旦發生斷電,網络故障,那麼將喪失這一性質。因此就需要一種機制對機器的物理位置進行隔離。所以引入了zone的概念。

       ring代碼中引入zone_count,把這些node分割到16zone中去。其中partitionreplica不能放在同一個node上或同一個zone內。

from array import array
from hashlib import md5
from random import shuffle
from struct import unpack_from

REPLICAS =
3

PARTITION_POWER =
16
PARTITION_SHIFT =
32 - PARTITION_POWER
PARTITION_MAX =
2 ** PARTITION_POWER - 1

NODE_COUNT =
256
ZONE_COUNT =
16
DATA_ID_COUNT =
10000000

node2zone = []
while len(node2zone) < NODE_COUNT:
    zone =
0

   
while zone < ZONE_COUNT and len(node2zone) < NODE_COUNT:
        node2zone.append(zone)
        zone +=
1

part2node = array(
'H')
for part in xrange(2
** PARTITION_POWER):
    part2node.append(part % NODE_COUNT)
shuffle(part2node)
node_counts = [
0
] * NODE_COUNT
zone_counts = [
0
] * ZONE_COUNT
for
data_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 = [part2node[part]]
    zones = [node2zone[node_ids[
0
]]]
    node_counts[node_ids[
0]] += 1

    zone_counts[zones[
0]] += 1
   
for replica in xrange(1, REPLICAS):
       
while
part2node[part] in node_ids and \
                node2zone[part2node[part]] in zones:
            part +=
1

           
if part > PARTITION_MAX:
                part =
0

        node_ids.append(part2node[part])
        zones.append(node2zone[node_ids[-
1]])
        node_counts[node_ids[-
1]] += 1

        zone_counts[zones[-
1]] += 1
desired_count = DATA_ID_COUNT / NODE_COUNT * REPLICAS
print '%d: Desired data 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 on one node, %.02f%% under'
% \
    (min_count, under)
desired_count = DATA_ID_COUNT / ZONE_COUNT * REPLICAS

print '%d: Desired data ids per zone'
% desired_count
max_count = max(zone_counts)
over =
100.0
* (max_count - desired_count) / desired_count
print '%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_count
print '%d: Least data ids in one zone, %.02f%% under'
% \
    (min_count, under)


117186
: Desired data ids per node
118782: Most data ids on one node, 1.36
% over
115632: Least data ids on one node, 1.33
% under
1875000
: Desired data ids per zone
1878533: Most data ids in one zone, 0.19
% over
1869070: Least data ids in one zone, 0.32
% under

       到目前为止,ring的基本功能都已經有了:一致性哈希ringpartitionpartition powerreplicazone。目前還差weight以及將以上代碼改寫为類封裝成module

 

weight

引入weight的概念,目的是“能者多勞”:解决未來添加存儲能力更大的node時,使得可以分配到更多的partition。例如,2T 容量的nodepartition數为1T的兩倍。

       ring的構建中,加入了weight屬性。本例中weight簡單地取12兩個值,根據每個結點在weight和中的比例分配所需partition數。

from array import array
from hashlib import md5
from random import shuffle
from struct import unpack_from
from time import time


class
Ring(object):

   
def __init__
(self, nodes, part2node, replicas):
        self.nodes = nodes
        self.part2node = part2node
        self.replicas = replicas
        partition_power =
1

       
while 2 ** partition_power < len(part2node):
            partition_power +=
1

       
if len(part2node) != 2 ** partition_power:
           
raise Exception("part2node's length is not an "

                           
"exact power of 2")
        self.partition_shift =
32
- partition_power

   
def get_nodes
(self, data_id):
        data_id = str(data_id)
        part = unpack_from(
'>I'
,
           md5(data_id).digest())[
0
] >> self.partition_shift
        node_ids = [self.part2node[part]]
        zones = [self.nodes[node_ids[
0
]]]
       
for replica in xrange(1
, self.replicas):
           
while
self.part2node[part] in node_ids and \
                   self.nodes[self.part2node[part]] in zones:
                part +=
1

               
if part >= len(self.part2node):
                    part =
0

            node_ids.append(self.part2node[part])
            zones.append(self.nodes[node_ids[-
1]])
       
return [self.nodes[n] for
n in node_ids]

def build_ring
(nodes, partition_power, replicas):
    begin = time()
    parts =
2
** partition_power
    total_weight = \
        float(sum(n[
'weight'] for
n in nodes.itervalues()))
   
for
node in nodes.itervalues():
        node[
'desired_parts'
] = \
            parts / total_weight * node[
'weight'
]
    part2node = array(
'H'
)
 
 
for part in xrange(2 ** partition_power):
       
for
node in nodes.itervalues():
           
if node['desired_parts'] >= 1
:
                node[
'desired_parts'] -= 1

                part2node.append(node[
'id'])
               
break

       
else:
           
for
node in nodes.itervalues():
               
if node['desired_parts'] >= 0
:
                    node[
'desired_parts'] -= 1

                    part2node.append(node[
'id'])
                   
break

    shuffle(part2node)
    ring = Ring(nodes, part2node, replicas)
   
print '%.02fs to build ring' % (time() - begin)
   
return
ring

def test_ring
(ring):
    begin = time()
    DATA_ID_COUNT =
10000000

    node_counts = {}
    zone_counts = {}
   
for data_id in xrange(DATA_ID_COUNT):
       
for
node in ring.get_nodes(data_id):
            node_counts[node[
'id'
]] = \
                node_counts.get(node[
'id'], 0) + 1

            zone_counts[node[
'zone']] = \
                zone_counts.get(node[
'zone'], 0) + 1

   
print '%ds to test ring' % (time() - begin)
    total_weight = float(sum(n[
'weight'] for
n in
                             ring.nodes.itervalues()))
    max_over =
0

    max_under =
0
   
for node in ring.nodes.itervalues():
        desired = DATA_ID_COUNT * REPLICAS * \
            node[
'weight'
] / total_weight
        diff = node_counts[node[
'id'
]] - desired
       
if diff > 0
:
            over =
100.0
* diff / desired
           
if
over > max_over:
                max_over = over
       
else
:
            under =
100.0
* (-diff) / desired
           
if
under > max_under:
                max_under = under
   
print '%.02f%% max node over'
% max_over
   
print '%.02f%% max node under'
% max_under
    max_over =
0

    max_under =
0
   
for zone in set(n['zone'] for n in
                    ring.nodes.itervalues()):
        zone_weight = sum(n[
'weight'] for
n in
            ring.nodes.itervalues()
if n['zone'
] == zone)
        desired = DATA_ID_COUNT * REPLICAS * \
            zone_weight / total_weight
        diff = zone_counts[zone] - desired
       
if diff > 0
:
            over =
100.0
* diff / desired
           
if
over > max_over:
                max_over = over
       
else
:
            under =
100.0
* (-diff) / desired
           
if
under > max_under:
                max_under = under
   
print '%.02f%% max zone over'
% max_over
   
print '%.02f%% max zone under'
% max_under

if __name__ == '__main__'
:
    PARTITION_POWER =
16

    REPLICAS =
3
    NODE_COUNT =
256
    ZONE_COUNT =
16
    nodes = {}
   
while len(nodes) < NODE_COUNT:
        zone =
0

       
while zone < ZONE_COUNT and len(nodes) < NODE_COUNT:
            node_id = len(nodes)
            nodes[node_id] = {
'id': node_id, 'zone'
: zone,
                             
'weight': 1.0 + (node_id % 2
)}
            zone +=
1

    ring = build_ring(nodes, PARTITION_POWER, REPLICAS)
    test_ring(ring)


0.10s to build ring
162
s to test ring
118581: Most data ids on one node,1.19
% over
115537: Least data ids on one node, 1.41
% under
1878343: Most data ids in one zone, 0.18
% over
1870880: Least data ids in one zone, 0.22
% under

       每個node上分布的最大波動为1.19%1.41%,而zone上的波動分布在0.22%以下。

 

總結

       以上就是ring的構建原理分析,引入一致性哈希的原因是为了減少由於增加結點導致數據項移動的數量來提高單調性,引入partition的原因是为了減少由於節點數過少導致移動過多的數據項、引入replica的原因是防止數據單點提高冗餘性,引入zone的原因是为了保證分區容忍性、引入weight的原因是为了保證partition分配的均衡。

那麼Ring的結構是否就此止步了呢,在Swift開發人員的博客中提到,只要發現更好的數據映射機制,就將Ring推倒重來,所以未來Ring會如何演化,咱們也可以参與其中,促其不斷地進化。

 

 

致謝

本文寫於sina SAE實習期間,感謝我的主管@程輝對我技術上的指導。同時也感謝zzcase在討論中给予我的諸多幫助。gholtswift開發博文给了我不少启發。

 

参考文章

http://go.renren.it/tlohg.com/building-a-consistent-hashing-ring-part-1

http://go.renren.it/blog.csdn.net/zzcase/article/details/6709961

http://go.renren.it/blog.csdn.net/sparkliang/article/details/5279393

http://go.renren.it/blog.csdn.net/x15594/article/details/6270242

http://go.renren.it/ultimatearchitecture.net/index.php/2010/06/22/quorum-nwr/

http://go.renren.it/ultimatearchitecture.net/index.php/2010/06/22/consistent_hash_algorithn/

http://go.renren.it/ultimatearchitecture.net/index.php/2010/06/22/eventually_consistency_base-vs-acid/

http://go.renren.it/citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.3738

 

頂一下
(0)
0%
踩一下
(0)
0%
------分隔線----------------------------
發表評論
請自覺遵守互聯網相關的政策法規,嚴禁發布色情、暴力、反動的言論。
評價:
表情:
驗證碼:點擊我更換圖片
欄目列表
推薦內容