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

一致性hash的基本原理

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

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

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

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

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

crush算法的核心思想

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

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

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

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

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

總結(jié)

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