轉自于：http://www.cnblogs.com/shanno/p/3958298.html?utm_source=tuicool
資料分布是分布式存儲系統的一個重要部分，資料分布算法至少要考慮以下三個因素：
1) 故障域隔離。同份資料的不同副本分布在不同的故障域，降低資料損壞的風險；
2) 負載均衡。資料能夠均勻地分布在磁盤容量不等的存儲節點，避免部分節點空閑部分節點超載，進而影響系統性能；
3) 控制節點加入離開時引起的資料遷移量。當節點離開時，最優的資料遷移是隻有離線節點上的資料被遷移到其它節點，而正常工作的節點的資料不會發生遷移。
對象存儲中一緻性Hash和Ceph的CRUSH算法是使用地比較多的資料分布算法。在Aamzon的Dyanmo鍵值存儲系統中采用一緻性Hash算法，并且對它做了很多優化。OpenStack的Swift對象存儲系統也使用了一緻性Hash算法。
假設資料為 x ，存儲節點數目為 N 。将資料分布到存儲節點的最直接做法是，計算資料 x 的Hash值，并将結果同節點數目 N 取餘數，餘數就是資料x的目的存儲節點。即目的存儲節點為 Hash(x) % N 。對資料計算Hash值的目的為了可以讓資料均勻分布在N個節點中。這種做法的一個嚴重問題是，當加入新節點或則節點離開時，幾乎所有資料都會受到影響，需要重新分布。是以，資料遷移量非常大。
一緻性Hash算法将資料和存儲節點映射到同個Hash空間，如上圖所示。Hash環中的3存儲節點把Hash空間劃分成3個分區，每個存儲節點負責一個分區上的資料。例如，落在分區[N2,N0]上的資料存儲在節點N0。
一緻性Hash算法能夠很好地控制節點加入離開導緻的遷移資料的數量。如圖(b)所示，當節點N0離開時，原來由它負責的[N2, N0]分區将同[N0, N1]分區合并成[N2, N1]分區，并且都由節點N1負責。也就是說，本來存儲在節點N0上的資料都遷移到節點N1，而原來存儲在N1和N2節點的資料不受影響。圖(c)給出了 當節點N3加入時，原來[N2, N0]分區分裂成[N3, N0]和[N2, N3]兩個分區，其中[N3, N0]分區上是資料遷移到新加入的N3節點。
一緻性Hash的一個問題是，存儲節點不能将Hash空間劃分地足夠均勻。如上圖(a)所示，分區[N2, N0]的大小幾乎是其它兩個分區大小之和。這容易讓負責該分區的節點N0負載過重。假設3個節點的磁盤容量相等，那麼當節點N0的磁盤已經寫滿資料時其它 兩個節點上的磁盤還有很大的空閑空間，但此時系統已經無法繼續向分區[N2, N0]寫入資料，進而造成資源浪費。
虛拟節點是相對于實體存儲節點而言的，虛拟節點負責的分區上的資料最終存儲到其對應的實體節點。在一緻性Hash中引入虛拟節點可以把Hash空 間劃分成更多的分區，進而讓資料在存儲節點上的分布更加均勻。如上圖(b)所示，黃顔色的節點代表虛拟節點，Ni_0代表該虛拟節點對應于實體節點i的第 0個虛拟節點。增加虛拟節點後，實體節點N0負責[N1_0, N0]和[N0, N0_0]兩個分區，實體節點N1負責[N0_0, N1]和[N2_0, N1_0]兩個分區，實體節點N2負責[N2, N1]和[N2_0, N2]兩個分區，三個實體節點負責的總的資料量趨于平衡。
實際應用中，可以根據實體節點的磁盤容量的大小來确定其對應的虛拟節點數目。虛拟節點數目越多，節點負責的資料區間也越大。
前文提到，當節點加入或者離開時，分區會相應地進行分裂或合并。這不對新寫入的資料構成影響，但對已經寫入到磁盤的資料需要重新計算Hash值以确定它是 否需要遷移到其它節點。因為需要周遊磁盤中的所有資料，這個計算過程非常耗時。如下圖(a)所示，分區是由落在Hash環上的虛拟節點 Ti 來劃分的，并且分區位置(存儲分區資料的節點)也同虛拟節點相關，即存儲到其順時針方向的第1個虛拟節點。
在Dynamo的論文中提出了分離分區和分區位置的方法來解決這個問題。該方法将Hash空間劃分成固定的若幹個分區，虛拟節點不再用于劃分分區 而用來确定分區的存儲位置。如上圖(b)所示，将Hash空間劃分成[A,B]，[B,C], [C,D]和[D,A]四個固定的分區。虛拟節點用于确定分區位置，例如T1負責分區[B,C]，T2負責分區[C,D]，T0負責[D,A]和 [A,B]兩個分區。由于分區固定，是以遷移資料時可以很容易知道哪些資料需要遷移哪些資料不需要遷移。
上圖(b)中虛拟節點T0負責了[D,A]和[A,B]兩個分區的資料，這是由分區數目和虛拟節點數目不相同導緻的。為讓分區分布地更加均 勻，Dyanmo提出了維持分區數目和虛拟節點數目相等的方法。這樣每個虛拟節點負責一個分區，在實體節點的磁盤容量都相同并且虛拟節點數目都相同的情況 下，每個實體節點負責的分區大小是完全相同的，進而可以達到最佳的資料分布。
Ceph分布資料的過程：首先計算資料 x 的Hash值并将結果和PG數目取餘，以得到資料 x 對應的 PG 編号。然後，通過CRUSH算法将PG映射到一組OSD中。最後把資料 x 存放到PG對應的OSD中。這個過程中包含了兩次映射，第一次是資料 x 到PG的映射。如果把PG當作存儲節點，那麼這和文章開頭提到的普通Hash算法一樣。不同的是，PG是抽象的存儲節點，它不會随着實體節點的加入或則離開而增加或減少，是以資料到PG的映射是穩定的。
在這個過程中，PG起到了兩個作用：第一個作用是劃分資料分區。每個PG管理的資料區間相同，因而資料能夠均勻地分布到PG上；第二個作用是充當 Dyanmo中Token的角色，即決定分區位置。實際上，這和Dynamo中固定分區數目，以及維持分區數目和虛拟節點數目相等的原則是同一回事。
在沒有多副本的情況下，Dynamo中分區的資料直接存儲到Token，而每個Token對應唯一的一個實體存儲節點。在多副本(假設副本數目為 N )的情況下，分區的資料會存儲到連續的 N 個Token中。但這會引入一個新問題：因為副本必須保持在不同的實體節點，但是如果這組Token中存在兩個或多個Token對應到同個實體存儲節點， 那麼就必須要跳過這樣的節點。Dynamo采用Preference清單來記錄每個分區對應的實體節點。然而，Dynmao論文中沒有詳述分區的 Preference清單如何選取實體節點，以及選取實體節點時該如何隔離故障域等問題。
(osd0, osd1, osd2 … osdn) = CRUSH(x)
Ceph的PG擔當起Dynamo中Token、固定分區以及Preference清單的角色，解決的是同樣的問題。PG的Acting集合對應于Dynamo的Preference清單。CRUSH算法解決了Dynamo論文中未提及的問題。
CRUSH算法的目的是，為給定的PG(即分區)配置設定一組存儲資料的OSD節點。選擇OSD節點的過程，要考慮以下幾個因素：
1) PG在OSD間均勻分布。假設每個OSD的磁盤容量都相同，那麼我們希望PG在每個OSD節點上是均勻分布的，也就是說每個OSD節點包含相同數目的 PG。假如節點的磁盤容量不等，那麼容量大的磁盤的節點能夠處理更多數量的PG。 2) PG的OSD分布在不同的故障域。因為PG的OSD清單用于儲存資料的不同副本，副本分布在不同的OSD中可以降低資料損壞的風險。
Ceph使用樹型層級結構描述OSD的空間位置以及權重(同磁盤容量相關)大小。如上圖所示，層級結構描述了OSD所在主機、主機所在機架以及機 架所在機房等空間位置。這些空間位置隐含了故障區域，例如使用不同電源的不同的機架屬于不同的故障域。CRUSH能夠依據一定的規則将副本放置在不同的故 障域。
OSD節點在層級結構中也被稱為Device，它位于層級結構的葉子節點，所有非葉子節點稱為Bucket。Bucket擁有不同的類型，如上圖 所示，所有機架的類型為Rack，所有主機的類型為Host。使用者還可以自己定義Bucket的類型。Device節點的權重代表存儲節點的性能，磁盤 容量是影響權重大小的重要參數。Bucket節點的權重是其子節點的權重之和。
CRUSH通過重複執行Take(bucketID)和Select(n, bucketType)兩個操作選取副本位置。Take(bucketID)指定從給定的bucketID中選取副本位置，例如可以指定從某台機架上選取 副本位置，以實作将不同的副本隔離在不同的故障域; Select(n, bucketType)則在給定的Bucket下選取 n 個類型為bucketType的Bucket，它選取Bucket主要考慮層級結構中節點的容量，以及當節點離線或者加入時的資料遷移量。
上圖給出了CRUSH選取副本的流程圖。
bucket: Take操作指定的bucket；
type: Select操作指定的Bucket的類型；
repnum: Select操作指定的副本數目；
rep：目前選擇的副本編号；
x: 目前選擇的PG編号；
item: 代表目前被選中的Bucket；
c(r, x, in): 代表從Bucket in中為PG x選取第r個副本；
collide: 代表目前選中的副本位置item已經被選中，即出現了沖突；
reject: 代表目前選中的副本位置item被拒絕，例如，在item已經處于out狀态的情況下；
ftotal: 在Descent域中選擇的失敗次數，即選擇一個副本位置的總共的失敗次數；
flocal: 在Local域中選擇的失敗次數；
local_retries: 在Local域選擇沖突時的嘗試次數；
local_fallback_retries: 允許在Local域的總共嘗試次數為bucket.size + local_fallback_retires次，以保證周遊完Buckt的所有子節點；
tries: 在Descent的最大嘗試次數，超過這個次數則放棄這個副本。
當Take操作指定的Bucket和Select操作指定的Bucket類型之間隔着幾層Bucket時，算法直接深度優先地進入到目的 Bucket的直接父母節點。例如，從根節點開始選擇N個Host時，它會深度優先地查找到Rack類型的節點，并在這個節點下選取Host節點。為了方 便表述，将Rack的所有子節點标記為Local域，将Take指定的Bucket的子節點标記為Descent域，如上圖所示。
選取過程中出現沖突、過載或者故障時，算法先在Local域内重新選擇，嘗試有限次數後，如果仍然找不到滿足條件的Bucket，那就回到Descent域重新選擇。每次重新選擇時，修改副本數目為 r += ftotal 。是以每次選擇失敗都會遞增ftotal，是以可以盡量避免選擇時再次選到沖突的節點。
流程圖中的 item=c(r,x,in) 從給定的Bucket in中選取一個子節點。
(待續)