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

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

一致性hash的基本原理

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

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

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

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

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

crush算法的核心思想

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

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

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

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

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

總結

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

參考：

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

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

https://docs.openstack.org/swif