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

前言

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

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

Ceph CRUSH

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

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

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

當(dāng)您創(chuàng)建一個(gè)配置文件并使用Ceph －deploy部署Ceph時(shí)，Ceph將生成一個(gè)默認(rèn)的map。默認(rèn)的CRUSH map 是工作的。然而，當(dāng)您部署大型數(shù)據(jù)集群時(shí)，您應(yīng)該考慮開(kāi)發(fā)一個(gè)定制CRUSH map，因?yàn)樗鼘椭芾鞢eph集群，提高性能并確保數(shù)據(jù)安全。

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

CRUSH WRITE

那么一個(gè)object是如何保存到磁盤(pán)上呢？

1．1．1 邏輯層

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

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

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

要解決這個(gè)問(wèn)題，我們先看看我們擁有什么，1，不同的對(duì)象名。2，不同的PG編號(hào)。這里就可以引入Ceph的計(jì)算方法了： HASH。

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

HASH（‘bar’） ＝ 0x3E0A4162

HASH（‘foo’） ＝ 0x7FE391A0

HASH（‘bar’） ＝ 0x3E0A4162

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

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

0x3E0A4162 ％ 0xFF ＝＝＝＞ 0x62

0x7FE391A0 ％ 0xFF ＝＝＝＞ 0xA0

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

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

1．1．2 物理層

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

加上剛剛的對(duì)象映射到PG的方法，我們將開(kāi)篇的兩步表示成如下的兩個(gè)計(jì)算公式：

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

CRUSH（PG＿ID） ＝＝＝＞ OSD

使用HASH代替CRUSH？

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

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

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

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

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

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

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

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

引入CRUSH算法

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

首先來(lái)看我們要做什么：

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

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

再來(lái)看我們有了什么：

互不相同的PG＿ID。

如果給OSD也編個(gè)號(hào)，那么就有了互不相同的OSD＿ID。

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

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

那么問(wèn)題就來(lái)了，總不至于每次都挑容量最大的OSD吧，這不分分鐘都把數(shù)據(jù)存滿那個(gè)最大的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)做一個(gè)常數(shù)，第一行實(shí)際上就做了搓一搓的事情：將PG＿ID， OSD＿ID和r一起當(dāng)做CRUSH＿HASH的輸入，求出一個(gè)十六進(jìn)制輸出，這和HASH（對(duì)象名）完全類(lèi)似，只是多了兩個(gè)輸入。所以需要強(qiáng)調(diào)的是，對(duì)于相同的三個(gè)輸入，計(jì)算得出的draw的值是一定相同的。

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

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

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

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

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

－CRUSH＿HASH（PG＿ID， OSD＿ID， r） 得出一個(gè)隨機(jī)數(shù)（重點(diǎn)是隨機(jī)數(shù)，不是HASH）。

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

－選出乘積最大的OSD。

－這個(gè)PG就會(huì)保存到這個(gè)OSD上。

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

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

下面我們來(lái)舉個(gè)例子，假定我們有6個(gè)OSD，需要從中選出三個(gè)副本：

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的情況，這時(shí)候，我們選出（CRUSH＿HASH ＆ 0xFFFF） ＊ weight的值最大的一個(gè)，也就是osd．1的0x39A00，這就是我們選出的第一個(gè)OSD。

然后，我們?cè)僮宺 ＝ 1，再生成一組CRUSH＿HASH的隨機(jī)值，乘以O(shè)SD的weight，再取一個(gè)最大的得到第二個(gè)OSD，依此得到第三個(gè)OSD，如果在此過(guò)程中，選中了相同的OSD，那么將r再加一，生成一組隨機(jī)值，再選一次，直到選中三個(gè)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

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

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

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

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

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

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

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

CRUSH WEIGHTS

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

CRUSH RECOVERY

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

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

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

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

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

互動(dòng)區(qū)

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