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

前言

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

關于Ceph主題，這一節將詳細介紹Ceph ?CRUSH。

Ceph CRUSH

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

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

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

當您創建一個配置文件并使用Ceph －deploy部署Ceph時，Ceph將生成一個默認的map。默認的CRUSH map 是工作的。然而，當您部署大型數據集群時，您應該考慮開發一個定制CRUSH map，因為它將幫助您管理Ceph集群，提高性能并確保數據安全。

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

CRUSH WRITE

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

1．1．1 邏輯層

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

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

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

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

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

HASH（‘bar’） ＝ 0x3E0A4162

HASH（‘foo’） ＝ 0x7FE391A0

HASH（‘bar’） ＝ 0x3E0A4162

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

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

0x3E0A4162 ％ 0xFF ＝＝＝＞ 0x62

0x7FE391A0 ％ 0xFF ＝＝＝＞ 0xA0

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

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

1．1．2 物理層

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

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

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

CRUSH（PG＿ID） ＝＝＝＞ OSD

使用HASH代替CRUSH？

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

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

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

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

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

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

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

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

引入CRUSH算法

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

首先來看我們要做什么：

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

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

再來看我們有了什么：

互不相同的PG＿ID。

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

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

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

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

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

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

pick up high＿osd＿straw

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

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

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

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

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

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

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

－對于所有的OSD用他們的權重乘以每個OSD＿ID對應的隨機數，得到乘積。

－選出乘積最大的OSD。

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

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

當然實際選擇過程還要稍微復雜一點，我這里只是用最簡單的方法來解釋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的隨機值，乘以OSD的weight，再取一個最大的得到第二個OSD，依此得到第三個OSD，如果在此過程中，選中了相同的OSD，那么將r再加一，生成一組隨機值，再選一次，直到選中三個OSD為止。

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

locator ＝object＿name

obj＿hash ＝hash（locator）

pg ＝obj＿hash ％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．append（chosen）

returnresult

CRUSH READ

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

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

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

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

針對這個PG lD執行CRUSH 查找得到主OSO 和輔助OSO ，最后寫數據。

CRUSH 層級結構

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

CRUSH WEIGHTS

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

CRUSH RECOVERY

在故障域內任何組件發生故障之后，在Ceph 將該OSD 標記為down 和out 并初始化恢

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

當一個新主機或磁盤添加到Ceph 集群中時，CRUSH 開始執行再平衡操作，在這個過程中，CRUSH 從現有的主機／磁盤上移動數據到新的主機／磁盤。再平衡保證所有磁盤

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

啟迪云－高級開發工程師 ?侯玉彬

互動區

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