2.2.2 CRUSH 算法因子
上述介紹可以看出，CRUSH算法在 Ceph存儲系統的資料尋址中占有核心地位，Ceph存儲系統通過 CRUSH 算法規則來控制資料的分布政策，Ceph存儲系統的 CRUSH算法能夠控制對象檔案在存儲叢集中随機均勻地分布。
CRUSH算法包含兩個關鍵輸入因子：階層化的 ClusterMap以及資料分布政策PlacementRules。
1. 階層化的 ClusterMap
階層化的 ClusterMap 反映了存儲系統層級的實體拓撲結構。
Ceph存儲叢集通過 ClusterMap定義了 OSD守護程序的靜态拓撲關系（層級資訊），使得CRUSH算法在選擇OSD時具備了主機、機架、機房等資訊的感覺能力。通過 ClusterMap規則定義，Ceph 存儲系統允許資料副本可以分布在不同的主機、不同的機架，甚至不同的機房中，提高了資料存儲的安全性。
ClusterMap由裝置（device）和桶（bucket）組成，device是最基本的儲存設備，也就是 OSD，通常 1個 OSD對應 1 個磁盤儲存設備，bucket 表示存放裝置的容器，可以包含多個裝置或子類型的 bucket。
儲存設備（device）的權重由管理者設定，以控制裝置負責存儲的相對資料量，device的權重值越高，對應的磁盤就會被配置設定寫入更多的資料。大型存儲系統中的儲存設備（磁盤）通常存在容量大小不等或者性能高低不一的情況，系統管理者可以依據儲存設備的使用率 和負載來設定權重，随機資料分布算法，以此控制資料的最終分布，實作存儲系統裝置的 資料量均衡，進而平衡存儲系統的I/O 負載，最終提高存儲叢集整體的性能和可靠性。
桶的權重是它所包含的所有元素（device及 bucket）權重的總和。Bucket可以包含很多種類型，例如，Host 就代表一個主機節點，可以包含多個 device；Rack 代表機架，包含多個 host節點。Ceph中預設有 OSD、host、Chassis、Rack、row、PDU、Pod、Room、Datacenter、Region、root，共計11個層級（同時也允許使用者定義自己新的類型），它們含義如下。
OSD 磁盤裝置，對應 OSD守護程序
host 包含若幹個 OSD的主機
Chassis 包含若幹個刀片伺服器的機箱
Rack 包含若幹個主機的機架
row 包含若幹個主機的一排機櫃
PDU 為機櫃配置設定的電源插排
Pod 一個資料中心中的機房單間
Room 含若幹個機櫃和主機的機房
Datacenter 包含若幹機房的資料中心
Region 包含若幹資料中心的區域
root bucket分層結構的根
通常 OSD、host、Rack 層級較為常用。下面舉例說明 bucket的用法。
| host test1{ | // 類型host，名字為 test1 | |
| id -2 | //bucket的 ID，⼀般為負值 | |
| #weight 3.000 | // 權重，預設為⼦ item 的權重之和 | |
| algstraw | //bucket随機選擇的算法 | |
| hash 0 | //bucket随機選擇的算法使⽤的 hash函數 | |
| // 這⾥ 0代表使⽤ hash 函數 jenkins1 | ||
| itemosd.1 weight | 1.000 | //item1: osd.1 和權重 |
| itemosd.2 weight | ||
| itemosd.3 weight } |
host test2{id -3
# weight 3.00algstrawhash 0
item osd.3 weight 1.000item osd.4 weight 1.000itemosd.5 weight 1.000
rootdefault{ //root的類型為bucket，名字為 defaultid -1 //ID号
# weight 6.000algstraw
item test1 weight 3.000itemtest2 weight 3.000
根據上面 ClusterMap的文法定義，圖 2-2 給出了比較直覺的層級化的樹形結構。
如圖2-2所示，Ceph的 ClusterMap是一個由 bucket和 device 共同組成的樹形存儲層次結構，葉子節點是device（也就是OSD），其他的節點稱為bucket節點，這些bucket都是邏輯上的概念，是對實體結構的抽象（如對資料中心的抽象、機房的抽象、機架的抽象、主機的抽象等），樹形結構隻有一個最終的根節點，稱為root節點，root也是一個抽象的邏輯概念。
圖 2-2Ceph的CusterMap層級結構
在上面的 ClusterMap中，有一個 root類型的 bucket，名字為 default；root下面有兩個 host類型的bucket，名字分别為 test1和 test2，其下分别各有3個 OSD裝置，每個 device的權重都為 1.000，說明它們的容量大小都相同。host 的權重為子裝置之和，即test1與test2 的權重均為3.000，它是自動計算的，不需要設定；同理，root 的權重為6.000。
2. 資料分布政策 PlacementRules
PlacementRules決定了一個 PG的對象（副本或糾删碼政策）如何選擇 OSD，通過這些自定義的規則，使用者可以設定副本在叢集中的分布。Ceph 存儲系統的PlacementRules 定義格式如下。
take(a)choose
choose firstn {num} type {bucket-type}chooseleaffirstn{num} type{bucket-type}
If{num}== 0，choose pool-num-replicasbuckets (all-available).
If {num} > 0 && <pool-num-replicas，choose that many buckets.
If {num} < 0，it means pool-num-replicas- |{num}|.
Emit
PlacementRules 的執行流程如下。
（1） take操作選擇一個 bucket，一般是root類型的 bucket。
（2） choose 操作有不同的選擇方式，其輸入都是上一步的輸出。
a）choosefirstn 深度優先選擇出 num個類型為 bucket-type的子 bucket。b）chooseleaf先選擇出 num個類型為bucket-type的子 bucket，然後遞歸到葉子節
點，選擇一個OSD 裝置。
i. 如果 num為 0，num就為 Pool 設定的副本數；
ii. 如果 num大于 0，小于Pool 的副本數，那麼就選出 num個；
iii. 如果 num小于 0，就選出 Pool 的副本數減去 num 的絕對值。
（3） emit輸出結果。
由上述流程可以看出，PlacementRules主要定義以下 3個關鍵操作。
（1）從 CRUSHMap中的哪個節點開始查找；
（2）使用哪個節點作為故障隔離域；
（3）定位副本的搜尋模式（廣度優先或深度優先）。
3. 示例
（1）3 個副本分布在 1個 row 下的 3個 cabinet 中。
在圖2-3中，最下面的長方形圖例代表一台主機，裡面的圓柱形圖例代表OSD， cabinet圖例代表一個機櫃，row圖例代表一排機櫃，頂端的 root是根節點，可以把它了解成一個資料中心。
圖 2-3 Ceph資料分布示意(CusterMap)
自頂而下來看，頂層是一個 rootbucket，每個 root下有 4個 row類型 bucket，每個 row下面有 4個 cabinet，每個cabinet下有若幹個 OSD裝置（圖中有 4個 host，每個host有若幹個 OSD裝置，但是在本 CRUSHMap中并沒有設定host這一級别的 bucket，而是直接把4個host上的所有OSD裝置定義為一個cabinet）。
該場景下，PlacementRules定義如下。
rulereplicated_ruleset {
ruleset 0 //ruleset的編号ID
typereplicated //類型 replicated或者erasurecode
min_size 1 //副本數最⼩值
max_size 10 //副本數最⼤值
step take root //選擇⼀個rootbucket，做下⼀步的輸⼊
step choose firstn 1type row //選擇⼀個 row，同⼀排
stepchoosefirstn3typecabinet //選擇3個cabinet，3副本分别在不同的cabinet
stepchoosefirstn1typeosd //在上⼀步輸出的3個cabinet中，分别選擇⼀個OSD
stepemit
根據上面的 ClusterMap和 PlacementRules 定義，選擇算法的執行過程如下。1）選中 rootbucket作為下一個步驟的輸入；
2） 從 root類型的 bucket中選擇 1個 row類的子 bucket，其選擇的算法在 root的定義中設定，一般設定為 straw算法；
3）從上一步的輸出row中，選擇 3個 cabinet，其選擇的算法在 row中定義；4）從上一步輸出的3個 cabinet中，分别選出一個 OSD，并輸出。
最終實作效果為可選擇出3個OSD 裝置，分布在1個row上的 3個 cabinet中。
（2） 主副本分布在 SSD 上，其他副本分布在 HDD上。
如圖 2-4所示的 ClusterMap定義了 2個 root類型的 bucket，一個是名為SSD的root類型的 bucket，其 OSD存儲媒體都是SSD固态硬碟，它包含 2個 host，每個host上的儲存設備都是 SSD固态硬碟；另一個是名為 HDD的 root類型的bucket，其 OSD存儲媒體都是 HDD硬碟，它有 2個 host，每個host上的裝置都是 HDD硬碟。
圖 2-4Ceph資料分布示意(CusterMap)
rule ssd-primary {
ruleset 0
type replicatedmin_size 1
max_size10
step take ssd //選擇SSD這個rootbucket為輸⼊step chooseleaf firstn 1 type host //選擇⼀個host，并遞歸選擇葉⼦節點 OSDstep emit //輸出結果
step take hdd //選擇HDD這個rootbucket為輸⼊
step chooseleaf firstn -1 type host //選擇總副本數減⼀個host
//并分别遞歸選擇⼀個葉⼦節點OSD
step emit //輸出結果
根據上面的 ClusterMap和 PlacementRules 定義，選擇算法的執行過程如下。1）首先 take操作選擇 ssd為 root類型的 bucket；
2） 在 SSD的 root中先選擇一個 host，然後以該 host 為輸入，遞歸至葉子節點，選擇一個 OSD裝置；
3）輸出選擇的裝置，也就是SSD裝置；
4）選擇 HDD作為 root的輸入；
5） 選擇2個host（副本數減1，預設3副本），并分别遞歸選擇一個OSD裝置，最終選出 2個 HDD裝置；
6）輸出最終結果。
最終實作效果為輸出 3個裝置，一個是 SSD類型的磁盤，另外兩個是 HDD磁盤。通過上述規則，就可以把PG的主副本存儲在SSD類型的 OSD上，其他副本分布在HDD類型的磁盤上。