摘要：下圖是的代碼段，我喜歡叫它攪拌攪拌再攪拌得出一個隨機數(shù)如果看到這里你已經(jīng)被攪暈了，那讓我再簡單梳理下選擇一個時做的事情給出一個，作為的輸入。，，得出一個隨機數(shù)重點是隨機數(shù)，不是。對于所有的用他們的權(quán)重乘以每個對應(yīng)的隨機數(shù)，得到乘積。

前言

前文回顧：《開源社區(qū)的明星項目—Ceph談》、《史上最全的Ceph構(gòu)件及組件分析》、

關(guān)于Ceph主題，這一節(jié)將詳細(xì)介紹Ceph ?CRUSH。

Ceph CRUSH

CRUSH算法通過計算數(shù)據(jù)存儲位置來確定如何存儲和檢索數(shù)據(jù)。CRUSH使Ceph客戶機能夠直接與OSDs通信，而不是通過集中的服務(wù)器或代理。通過算法確定的數(shù)據(jù)存儲和檢索方法，Ceph避免了單點故障、性能瓶頸和對其可伸縮性的物理限制。

CRUSH需要集群的映射，并使用CRUSH映射在OSDs中偽隨機存儲和檢索數(shù)據(jù)，數(shù)據(jù)在集群中均勻分布。

CRUSH映射包含一個osd列表、一個用于將設(shè)備聚合到物理位置的“bucket”列表，以及一個規(guī)則列表，這些規(guī)則告訴CRUSH應(yīng)該如何復(fù)制Ceph集群池中的數(shù)據(jù)。通過反映安裝的底層物理組織，CRUSH可以建?！獜亩鉀Q——相關(guān)設(shè)備故障的潛在來源。典型的資源包括物理接近性、共享電源和共享網(wǎng)絡(luò)。通過將這些信息編碼到集群映射中，CRUSH放置策略可以跨不同的故障域分離對象副本，同時仍然保持所需的分布。例如，為了解決并發(fā)故障的可能性，可能需要確保數(shù)據(jù)副本位于使用不同貨架、機架、電源、控制器和／或物理位置的設(shè)備上。

當(dāng)您創(chuàng)建一個配置文件并使用Ceph －deploy部署Ceph時，Ceph將生成一個默認(rèn)的map。默認(rèn)的CRUSH map 是工作的。然而，當(dāng)您部署大型數(shù)據(jù)集群時，您應(yīng)該考慮開發(fā)一個定制CRUSH map，因為它將幫助您管理Ceph集群，提高性能并確保數(shù)據(jù)安全。

CRUSH map可以幫助你更快地識別錯誤。例如，如果一個特定機架中的所有OSDs同時下降，故障可能是由網(wǎng)絡(luò)交換機或機架的電源引起的，而不是OSDs本身。當(dāng)與失敗主機關(guān)聯(lián)的放置組處于降級狀態(tài)時，自定義CRUSH map還可以幫助您確定Ceph存儲冗余數(shù)據(jù)副本的物理位置。

CRUSH WRITE

那么一個object是如何保存到磁盤上呢？

1．1．1 邏輯層

Ceph為了保存一個對象，對上構(gòu)建了一個邏輯層，也就是池（pool），用于保存對象，這個池的翻譯很好的解釋了pool的特征，如果把pool比喻成一個中國象棋棋盤，那么保存一個對象的過程就類似于把一粒芝麻放置到棋盤上。

Pool再一次進(jìn)行了細(xì)分，即將一個pool劃分為若干的PG（歸置組Placement Group），這類似于棋盤上的方格，所有的方格構(gòu)成了整個棋盤，也就是說所有的PG構(gòu)成了一個pool。

現(xiàn)在需要解決的問題是，對象怎么知道要保存到哪個PG上，假定這里我們的pool名叫rbd，共有256個PG，給每個PG編個號分別叫做0x0， 0x1， ．．．0xF， 0x10， 0x11．．． 0xFE， 0xFF。

要解決這個問題，我們先看看我們擁有什么，1，不同的對象名。2，不同的PG編號。這里就可以引入Ceph的計算方法了： HASH。

對于對象名分別為bar和foo的兩個對象，對他們的對象名進(jìn)行計算即：

HASH（‘bar’） ＝ 0x3E0A4162

HASH（‘foo’） ＝ 0x7FE391A0

HASH（‘bar’） ＝ 0x3E0A4162

對對象名進(jìn)行HASH后，得到了一串十六進(jìn)制輸出值，也就是說通過HASH我們將一個對象名轉(zhuǎn)化成了一串?dāng)?shù)字，那么上面的第一行和第三行是一樣的有什么意義？意義就是對于一個同樣的對象名，計算出來的結(jié)果永遠(yuǎn)都是一樣的，但是HASH算法的確將對象名計算得出了一個隨機數(shù)。

有了這個輸出，我們使用小學(xué)就會的方法：求余數(shù)！用隨機數(shù)除以PG的總數(shù)256，得到的余數(shù)一定會落在［0x0， 0xFF］之間，也就是這256個PG中的某一個：

0x3E0A4162 ％ 0xFF ＝＝＝＞ 0x62

0x7FE391A0 ％ 0xFF ＝＝＝＞ 0xA0

于是乎，對象bar保存到編號為0x62的PG中，對象foo保存到編號為0xA0的PG中。對象bar永遠(yuǎn)都會保存到PG 0x62中！對象foo永遠(yuǎn)都會保存到PG 0xA0中！

這里給出更Ceph一點的說明，實際上在Ceph中，存在著多個pool，每個pool里面存在著若干的PG，如果兩個pool里面的PG編號相同，Ceph怎么區(qū)分呢？ 于是乎，Ceph對每個pool進(jìn)行了編號，比如剛剛的rbd池，給予編號0，再建一個pool就給予編號1，那么在Ceph里，PG的實際編號是由pool＿id＋．＋PG＿id組成的，也就是說，剛剛的bar對象會保存在0．62這個PG里，foo這個對象會保存在0．A0這個PG里。其他池里的PG名稱可能為1．12f， 2．a(chǎn)a1，10．a(chǎn)a1等。

1．1．2 物理層

理解了剛剛的邏輯層，我們再看一下Ceph里的物理層，對下，也就是我們?nèi)舾傻姆?wù)器上的磁盤，通常，Ceph將一個磁盤看作一個OSD（實際上，OSD是管理一個磁盤的程序），于是物理層由若干的OSD組成，我們的最終目標(biāo)是將對象保存到磁盤上，在邏輯層里，對象是保存到PG里面的，那么現(xiàn)在的任務(wù)就是打通PG和OSD之間的隧道。PG相當(dāng)于一堆余數(shù)相同的對象的組合，PG把這一部分對象打了個包，現(xiàn)在我們需要把很多的包平均的安放在各個OSD上，這就是CRUSH算法所要做的事情：CRUSH計算PG－＞OSD的映射關(guān)系。

加上剛剛的對象映射到PG的方法，我們將開篇的兩步表示成如下的兩個計算公式：

池ID ＋ HASH（‘對象名’） ％ pg＿num ＝＝＝＞ PG＿ID

CRUSH（PG＿ID） ＝＝＝＞ OSD

使用HASH代替CRUSH？

在討論CRUSH算法之前，我們來做一點思考，可以發(fā)現(xiàn)，上面兩個計算公式有點類似，為何我們不把

CRUSH（PG＿ID） ＝＝＝＞ OSD
改為

HASH（PG＿ID） ％OSD＿num ＝＝＝＞ OSD

我可以如下幾個由此假設(shè)帶來的副作用：

如果掛掉一個OSD，OSD＿num－1，于是所有的PG ％ OSD＿num的余數(shù)都會變化，也就是說這個PG保存的磁盤發(fā)生了變化，對這最簡單的解釋就是，這個PG上的數(shù)據(jù)要從一個磁盤全部遷移到另一個磁盤上去，一個優(yōu)秀的存儲架構(gòu)應(yīng)當(dāng)在磁盤損壞時使得數(shù)據(jù)遷移量降到最低，CRUSH可以做到。

如果保存多個副本，我們希望得到多個OSD結(jié)果的輸出，HASH只能獲得一個，但是CRUSH可以獲得任意多個。

如果增加OSD的數(shù)量，OSD＿num增大了，同樣會導(dǎo)致PG在OSD之間的胡亂遷移，但是CRUSH可以保證數(shù)據(jù)向新增機器均勻的擴散。

所以HASH只適用于一對一的映射關(guān)系計算，并且兩個映射組合（對象名和PG總數(shù)）不能變化，因此這里的假設(shè)不適用于PG－＞OSD的映射計算。因此，這里開始引入CRUSH算法。

引入CRUSH算法

千呼萬喚始出來，終于開始講CRUSH算法了，如果直接講Sage的博士論文或者crush．c的代碼的話，可能會十分苦澀難懂，所以我決定嘗試大話一把CRUSH，希望能讓沒有接觸過CRUSH的同學(xué)也能對其有所理解。

首先來看我們要做什么：

把已有的PG＿ID映射到OSD上，有了映射關(guān)系就可以把一個PG保存到一個磁盤上。

如果我們想保存三個副本，可以把一個PG映射到三個不同的OSD上，這三個OSD上保存著一模一樣的PG內(nèi)容。

再來看我們有了什么：

互不相同的PG＿ID。

如果給OSD也編個號，那么就有了互不相同的OSD＿ID。

每個OSD最大的不同的就是它們的容量，即4T還是800G的容量，我們將每個OSD的容量又稱為OSD的權(quán)重（weight），規(guī)定4T權(quán)重為4，800G為0．8，也就是以T為單位的值。

現(xiàn)在問題轉(zhuǎn)化為：如何將PG＿ID映射到有各自權(quán)重的OSD上。這里我直接使用CRUSH里面采取的Straw算法，翻譯過來就是抽簽，說白了就是挑個最長的簽，這里的簽指的是OSD的權(quán)重。

那么問題就來了，總不至于每次都挑容量最大的OSD吧，這不分分鐘都把數(shù)據(jù)存滿那個最大的OSD了嗎？是的，所以在挑之前先把這些OSD搓一搓，這里直接介紹CRUSH的方法，如下圖（可忽視代碼直接看文字）：

CRUSH＿HASH（ PG＿ID， OSD＿ID， r ） ＝＝＝＞ draw

（ draw ＆0xffff ） ＊ osd＿weight ＝＝＝＞ osd＿straw

pick up high＿osd＿straw

第一行，我們姑且把r當(dāng)做一個常數(shù)，第一行實際上就做了搓一搓的事情：將PG＿ID， OSD＿ID和r一起當(dāng)做CRUSH＿HASH的輸入，求出一個十六進(jìn)制輸出，這和HASH（對象名）完全類似，只是多了兩個輸入。所以需要強調(diào)的是，對于相同的三個輸入，計算得出的draw的值是一定相同的。

這個draw到底有啥用？其實，CRUSH希望得到一個隨機數(shù)，也就是這里的draw，然后拿這個隨機數(shù)去乘以O(shè)SD的權(quán)重，這樣把隨機數(shù)和OSD的權(quán)重搓在一起，就得到了每個OSD的實際簽長，而且每個簽都不一樣長（極大概率），就很容易從中挑一個最長的。

說白了，CRUSH希望隨機挑一個OSD出來，但是還要滿足權(quán)重越大的OSD被挑中的概率越大，為了達(dá)到隨機的目的，它在挑之前讓每個OSD都拿著自己的權(quán)重乘以一個隨機數(shù)，再取乘積最大的那個。那么這里我們再定個小目標(biāo)：挑個一億次！從宏觀來看，同樣是乘以一個隨機數(shù)，在樣本容量足夠大之后，這個隨機數(shù)對挑中的結(jié)果不再有影響，起決定性影響的是OSD的權(quán)重，也就是說，OSD的權(quán)重越大，宏觀來看被挑中的概率越大。

這里再說明下CRUSH造出來的隨機數(shù)draw，前文可知，對于常量輸入，一定會得到一樣的輸出，所以這并不是真正的隨機，所以說，CRUSH是一個偽隨機算法。下圖是CRUSH＿HASH的代碼段，我喜歡叫它攪拌攪拌再攪拌得出一個隨機數(shù)：

如果看到這里你已經(jīng)被攪暈了，那讓我再簡單梳理下PG選擇一個OSD時做的事情：

－給出一個PG＿ID，作為CRUSH＿HASH的輸入。

－CRUSH＿HASH（PG＿ID， OSD＿ID， r） 得出一個隨機數(shù)（重點是隨機數(shù)，不是HASH）。

－對于所有的OSD用他們的權(quán)重乘以每個OSD＿ID對應(yīng)的隨機數(shù)，得到乘積。

－選出乘積最大的OSD。

－這個PG就會保存到這個OSD上。

現(xiàn)在趁熱打鐵，解決一個PG映射到多個OSD的問題，還記得那個常量r嗎？我們把r＋1，再求一遍隨機數(shù)，再去乘以每個OSD的權(quán)重，再去選出乘積最大的OSD，如果和之前的OSD編號不一樣，那么就選中它，如果和之前的OSD編號一樣的話，那么再把r＋2，再次選一次，直到選出我們需要的三個不一樣編號的OSD為止！

當(dāng)然實際選擇過程還要稍微復(fù)雜一點，我這里只是用最簡單的方法來解釋CRUSH在選擇OSD的時候所做的事情。

下面我們來舉個例子，假定我們有6個OSD，需要從中選出三個副本：

osd＿id

weight

CRUSH＿HASH

（CRUSH＿HASH ＆ 0xffff）＊ weight

osd．0

4

0xC35E90CB

0x2432C

osd．1

4

0xA67DE680

0x39A00

osd．2

4

0xF9B1B224

0x2C890

osd．3

4

0x42454470

0x111C0

osd．4

4

0xE950E2F9

0x38BE4

osd．5

4

0x8A844538

0x114E0

這是r ＝ 0的情況，這時候，我們選出（CRUSH＿HASH ＆ 0xFFFF） ＊ weight的值最大的一個，也就是osd．1的0x39A00，這就是我們選出的第一個OSD。

然后，我們再讓r ＝ 1，再生成一組CRUSH＿HASH的隨機值，乘以O(shè)SD的weight，再取一個最大的得到第二個OSD，依此得到第三個OSD，如果在此過程中，選中了相同的OSD，那么將r再加一，生成一組隨機值，再選一次，直到選中三個OSD為止。

下面是偽代碼object到osd的偽代碼

locator ＝object＿name

obj＿h(yuǎn)ash ＝hash（locator）

pg ＝obj＿h(yuǎn)ash ％num＿pg

OSDs＿for＿pg ＝crush（pg） ?＃ returns a list of OSDs

primary ＝osds＿for＿pg［0］

replicas ＝osds＿for＿pg［1：］

defcrush（pg）：

all＿osds＝［＇osd．0＇，＇osd．1＇，＇osd．2＇，．．．］

result＝［］

＃ size is the number of copies； primary＋replicas

whilelen（result）＜size：

r＝hash（pg）

chosen＝all＿osds［r％len（all＿osds）］

ifchoseninresult：

＃ OSD can be picked only once

continue

result．a(chǎn)ppend（chosen）

returnresult

CRUSH READ

對于Ceph 集群的一次讀寫操作，客戶端首先聯(lián)系Ceph 的momtor 并獲取一個集群

map 副本。集群map 幫助客戶端獲取Ceph 集群的狀態(tài)和配置信息。使用對象和池名IID將數(shù)據(jù)轉(zhuǎn)換為對象。然后將對象和PG （ placement groups ，歸置組）數(shù)一起經(jīng)過散列來生成其在Ceph 池巾最終存放的那一個PG 。然后前面計算好的PG 經(jīng)過CRUSH 查找來確定存儲或獲取數(shù)據(jù)所需的主OSO 的位置計算完準(zhǔn)確的OSD 10 之后，客戶端直接聯(lián)系這個OSO 來存儲數(shù)據(jù)。所有這些計算操作都由客戶端來執(zhí)行，因此它不會影響集群的性能。

一旦數(shù)據(jù)被寫入主OSO ，主OSO 所在節(jié)點將執(zhí)行CRUSH 查找操作并計算輔助歸置組和lOSD 的位置來實現(xiàn)數(shù)據(jù)復(fù)制，進(jìn)而實現(xiàn)高可用性。參考下面的例子來了解CRUSH 查找和對象王IJ OSO 的映射。

首先，基于池10 將對象名稱和集群PG 數(shù)應(yīng)用散列函數(shù)可以得到一個PG 10 。接下來，

針對這個PG lD執(zhí)行CRUSH 查找得到主OSO 和輔助OSO ，最后寫數(shù)據(jù)。

CRUSH 層級結(jié)構(gòu)

CRUSH 是完全了解所有基礎(chǔ)設(shè)施并支持用戶自定義配置的，它維護(hù)你所有基礎(chǔ)設(shè)施組件的一個嵌套層次結(jié)構(gòu)。CRUSH 設(shè)備列表通常包括磁盤、節(jié)點、機架（ rack） 、行（ row） 、開關(guān)、電源電路、房間、數(shù)據(jù)中心等。這些組件稱為故障域或CRUSH bucketo CRUSH map包含一系列可用bucket ，這些bucket 表明了設(shè)備的具體物理位置。它還包拆一系列的規(guī)則告訴CRUSH 如何為不同的Ceph 池復(fù)制數(shù)據(jù)。從下圖可以看到CRUSH 是如何看待你的基礎(chǔ)設(shè)施的。

CRUSH WEIGHTS

CRUSH算法為每個設(shè)備分配一個權(quán)重值，其目標(biāo)是逼近I／O請求的均勻概率分布。作為最佳實踐，我們建議使用相同類型和大小的設(shè)備創(chuàng)建池，并分配相同的相對權(quán)重。由于這并不總是實用的，您可以合并不同大小的設(shè)備，并使用相對權(quán)重，以便Ceph將更多的數(shù)據(jù)分配給較大的驅(qū)動器，而將更少的數(shù)據(jù)分配給較小的驅(qū)動器。

CRUSH RECOVERY

在故障域內(nèi)任何組件發(fā)生故障之后，在Ceph 將該OSD 標(biāo)記為down 和out 并初始化恢

復(fù)操作前，默認(rèn)情況下Ceph 會等待300 秒。這個值可以在Ceph 集群的配置文件中通過參數(shù)mon osd down out interval 進(jìn)行修改。在恢復(fù)操作期間，Ceph 開始重新組織發(fā)生故障的節(jié)點上受影響的數(shù)據(jù)。CRUSH 會復(fù)制數(shù)據(jù)到多個磁盤，這些復(fù)制的數(shù)據(jù)在恢復(fù)的時候使用。在恢復(fù)期間CRUSH 試圖移動盡量少的數(shù)據(jù)來構(gòu)建一個新的集群布局，這樣即使一些組件出現(xiàn)故障也能確保Ceph 的容錯性。

當(dāng)一個新主機或磁盤添加到Ceph 集群中時，CRUSH 開始執(zhí)行再平衡操作，在這個過程中，CRUSH 從現(xiàn)有的主機／磁盤上移動數(shù)據(jù)到新的主機／磁盤。再平衡保證所有磁盤

能闖勻使用，以此提升集群性能和保持集群健康。例如，如果一個Ceph 集群包含2000 個OSO ，這時一個新的系統(tǒng)添加20 個新的OSD ，這樣就只有1％ 的數(shù)據(jù)會在再平衡期間移動，并且所有現(xiàn)有的OSD 是并行地移動數(shù)據(jù)，使其迅速完成這個操作。然而，對于利用率高的Ceph 集群，建議先將新添加的OSD的權(quán)重設(shè)為0 ，再逐漸增加權(quán)重到依據(jù)磁盤容量確定的更高的權(quán)重值。通過這種方式，新的OSD 將減少Ceph 集群再平衡時的負(fù)載并避免性能下降。

啟迪云－高級開發(fā)工程師 ?侯玉彬

互動區(qū)

＊ 你對以上內(nèi)容有什么看法？你最關(guān)注云計算哪個趨勢？如果你還有想了解的技術(shù)話題，歡迎留言分享。