Ceph的crush算法與一致性hash對比介紹

首先，我們先回顧下一致性hash以及其在經(jīng)典存儲系統(tǒng)中的應(yīng)用。

一致性hash的基本原理

一致性hash的基本思想是，有一個hash函數(shù)，這個hash函數(shù)的值域形成了一個環(huán)(收尾相接：the largest hash value wraps around to the smallest hash value)，然后存儲的節(jié)點也通過這個hash函數(shù)隨機的分配到這個環(huán)上，然后某個key具體存儲到哪個節(jié)點上，是由這個key取hash函數(shù)對應(yīng)到環(huán)的一個位置，然后沿著這個位置順時針找到的第一個節(jié)點負責這個key的存儲。這樣環(huán)上的每個節(jié)點負責和它前面節(jié)點之間的這個區(qū)間的數(shù)據(jù)的存儲。

如上圖所示，hash函數(shù)的總區(qū)間是[A, Z]，有3個存儲節(jié)點分別對應(yīng)到F、M和S的位置上，那么hash值為A或者Z的key將會順時針查找它遇到的第一個節(jié)點，因此會存儲到節(jié)點1上，同理hash值為K的key存儲到第二個節(jié)點上。咱們再觀察下一致性hash在增刪節(jié)點的時候，數(shù)據(jù)遷移的情況，在上圖的場景中，如果刪除節(jié)點2的話，節(jié)點1上面的不會發(fā)生變化，原來存儲在節(jié)點2上的(F,M]區(qū)間會遷移存儲到節(jié)點3上；在上圖的場景中，如果在U位置增加一個節(jié)點的話，原來存儲到節(jié)點1上的(S, F]區(qū)間會分割成兩個區(qū)間其中(S, U]會存儲到新的節(jié)點上，而(U, F]不發(fā)生變化還是存儲到節(jié)點1上。從上面的例子中可以看到，一致性hash在增刪節(jié)點的時候，只影響與其相鄰的節(jié)點，并且需要遷移的數(shù)據(jù)最少。

上面這種樸素的一致性hash有兩個問題，第一個問題是如果節(jié)點較少，節(jié)點在環(huán)上的分布可能不均勻，導(dǎo)致每個節(jié)點的負載不均衡，比如上圖中場景，如果節(jié)點3故障被剔除的話，節(jié)點1和節(jié)點2的負載會非常的不均衡；第二個問題是不支持異構(gòu)的機型，比如如果有的存儲節(jié)點是4TB的，有的存儲節(jié)點是8TB的，每個節(jié)點對應(yīng)環(huán)上的一個位置，無法感知到節(jié)點的權(quán)重。為了解決這兩個問題，一般都是把每個節(jié)點對應(yīng)到環(huán)上的多個位置，稱為vnode，vnode足夠多的話，可以認為是均衡打散的，如果有節(jié)點故障下線的話，這個節(jié)點在環(huán)上對應(yīng)的vnode存儲的數(shù)據(jù)就可以均勻分給其他的vnode，最終存儲到對應(yīng)的node上，因此在增刪節(jié)點的時候，負載都是在所有的節(jié)點中均勻分攤。另外針對異構(gòu)的機型，比如說4TB和8TB的節(jié)點，8TB的節(jié)點的vnode是4TB節(jié)點的2倍就可以了。

如果vnode節(jié)點和環(huán)上的點一一對應(yīng)的話，可以認為是一致性hash的一個特殊的場景，比如說上圖中的例子，這個hash環(huán)一個有A到Z 25個點(A、Z重合了)，如果有25個vnode和其對應(yīng)的話，這樣一致性hash只需要記錄每個物理node節(jié)點到vnode的映射關(guān)系就可以了，會非常的簡單。開源swift對象存儲使用的是這種一致性hash，參考：https://docs.openstack.org/swift/latest/ring_background.html

在分布式系統(tǒng)中為了保障可靠性一般都是多副本存儲的，在dynamo存儲系統(tǒng)中，用一致性hash算法查找到第一個vnode節(jié)點后，會順序的向下找更多vnode節(jié)點，用來存儲多副本(中間會跳過同臺機器上的vnode，以達到隔離故障域的要求)，并且第一個vnode是協(xié)調(diào)節(jié)點。在開源swift對象存儲系統(tǒng)中，節(jié)點會先分組，比如3個一組，形成一個副本對，然后vnode會分配到某組機器上，一組機器上會有很多的vnode，并且這組機器上的vnode的leader節(jié)點在3臺機器上會打散，分攤壓力。

crush算法的核心思想

crush算法是一個偽隨機的路由選擇算法，輸入pg的id，osdmap等元信息，通過crush根據(jù)這個pool配置的crush rule規(guī)則的偽隨機計算，最終輸出存儲這個pd的副本的osd列表。由于是偽隨機的，只要osdmap、crush rule規(guī)則相同，在任意的機器上，針對某個pg id，計算的最終的osd列表都是相同的。

crush算法支持在crush rule上配置故障域，crush會根據(jù)故障域的配置，沿著osdmap，搜索出符合條件的osd，然后由這些osd抽簽來決定由哪個osd來存儲這個pg，crush算法內(nèi)部核心是這個稱為straw2的osd的抽簽算法。straw2的名字來源于draw straw(抽簽：https://en.wikipedia.org/wiki/Drawing_straws)這個短語，針對每個pg，符合故障域配置條件的osd來抽檢決定誰來存儲這個pg，osd抽簽也是一個偽隨機的過程，誰抽到的簽最長，誰贏。并且每個osd的簽的長度，都是osd獨立偽隨機計算的，不依賴于其他osd，這樣當增刪osd節(jié)點時，需要遷移的數(shù)據(jù)最少。

如上圖的一個示例，這是針對某個pg的一次抽簽結(jié)果，從圖中可以看到osd.1的簽最長，所以osd.1贏了，最終osd.1會存儲這個pg，在這個時候，如果osd.4由于故障下線，osd.4的故障下線并不會影響其他osd的抽簽過程，針對這個pg，最終的結(jié)果還是osd.1贏，因此這個pg不會發(fā)生數(shù)據(jù)的遷移；當然，在上圖從場景中，如果osd.1下線的話，osd.1上的pg會遷移到其他的osd上。增加osd節(jié)點的情況類似，比如在上圖的場景中，如果新增加一個osd.5節(jié)點的話，每個osd都是獨立抽簽，只有osd.5贏的那些pg才會遷移到osd.5上，對其他的pg不會產(chǎn)生影響。因此，理論上，crush算法也和一致性hash一樣，在增加刪除osd節(jié)點的時候，需要遷移的數(shù)據(jù)最少。

另外straw2抽簽算法也是支持異構(gòu)的機型的，比如有的osd是4TB，有的osd是8TB，straw2的抽簽算法會保證，8TB的osd抽簽贏的概率是4TB的osd的兩倍。背后的原理是，每個osd有個crush weight，crush weight正比于osd的磁盤大小，比如8TB的osd的crush weight是8左右，4TB的osd的crush weight是4左右。然后每個osd抽簽的過程是，以osd的crush weight為指數(shù)分布的λ，產(chǎn)生一個指數(shù)分布的隨機數(shù)，最后再比大小。

另外在ceph中，每個osd除了crush weight，還有個osd weight，osd weight的范圍是0到1，表示的含義是這個osd故障的概率，crush算法在偽隨機選擇pg放置的osd的時候，如果遇到故障的osd，會進行重試。比如說某個osd weight是0的話，說明這個osd徹底故障了，通過上面straw2步驟計算出來的pg會retry重新分配到其他的osd上，如果某個osd的osd weight是0.8的話，這個osd上20%的pg會被重新放置到其他的osd上。通過把osd weight置為0，可以把某個osd節(jié)點從集群中臨時剔除，通過調(diào)整osd weight也可以微調(diào)osd上的pg的分布。

總結(jié)

ceph分布式存儲系統(tǒng)數(shù)據(jù)分布的基石crush算法，是一個偽隨機的路由分布算法，對比一致性hash，它的核心的優(yōu)點是元數(shù)據(jù)少，集群增刪osd節(jié)點時，要遷移的數(shù)據(jù)少，并且crush算法支持異構(gòu)的機型，支持各種級別的故障域的配置，它的缺點是在實際應(yīng)用中發(fā)現(xiàn)，由于pg會占用一定的資源，一般每個osd最多200個pg左右，導(dǎo)致整個集群中pg數(shù)并不會特別的多，pg在osd上分布并不是非常的均衡，經(jīng)常需要微調(diào)。

參考：

https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

https://github.com/ceph/ceph/pull/20196

https://docs.openstack.org/swif