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

首先，我們先回顧下一致性hash以及其在經典存儲系統中的應用。

一致性hash的基本原理

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

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

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

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

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

crush算法的核心思想

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

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

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

另外straw2抽簽算法也是支持異構的機型的，比如有的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為指數分布的λ，產生一個指數分布的隨機數，最后再比大小。

另外在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節點從集群中臨時剔除，通過調整osd weight也可以微調osd上的pg的分布。

總結

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

參考：

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

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

https://docs.openstack.org/swif