? ? ? ? ? ? ?CRUSH（Controlled Replication Under Scalable Hashing）是一種基于偽隨機(jī)控制數(shù)據(jù)分布、復(fù)制的算法。Ceph是為大規(guī)模分布式存儲(chǔ)系統(tǒng)（PB級(jí)的數(shù)據(jù)和成百上千臺(tái)存儲(chǔ)設(shè)備）而設(shè)計(jì)的，在大規(guī)模的存儲(chǔ)系統(tǒng)里，必須考慮數(shù)據(jù)的平衡分布和負(fù)載（提高資源利用率）、最大化系統(tǒng)的性能，以及系統(tǒng)的擴(kuò)展和硬件容錯(cuò)等。CRUSH就是為解決以上問(wèn)題而設(shè)計(jì)的。在Ceph集群里，CRUSH只需要一個(gè)簡(jiǎn)潔而層次清晰的設(shè)備描述，包括存儲(chǔ)集群和副本放置策略，就可以有效地把數(shù)據(jù)對(duì)象映射到存儲(chǔ)設(shè)備上，且這個(gè)過(guò)程是完全分布式的，在集群系統(tǒng)中的任何一方都可以獨(dú)立計(jì)算任何對(duì)象的位置；另外，大型系統(tǒng)存儲(chǔ)結(jié)構(gòu)是動(dòng)態(tài)變化的（存儲(chǔ)節(jié)點(diǎn)的擴(kuò)展或者縮容、硬件故障等），CRUSH能夠處理存儲(chǔ)設(shè)備的變更（添加或刪除），并最小化由于存儲(chǔ)設(shè)備的變更而導(dǎo)致的數(shù)據(jù)遷移。
CRUSH基本原理
? ? ? ? ?眾所周知，存儲(chǔ)設(shè)備具有吞吐量限制，它影響讀寫(xiě)性能和可擴(kuò)展性能。所以，存儲(chǔ)系統(tǒng)通常都支持條帶化以增加存儲(chǔ)系統(tǒng)的吞吐量并提升性能，數(shù)據(jù)條帶化最常見(jiàn)的方式是做RAID。與ceph的條帶化最相似的是RAID 0或者是“帶區(qū)卷”。Ceph條帶化提供了類似于RAID 0的吞吐量，N路RAID鏡像的可靠性以及更快速的恢復(fù)能力。
? ? ? ? ?在磁盤(pán)陣列中，數(shù)據(jù)是以條帶（stripe）的方式貫穿在磁盤(pán)陣列所有硬盤(pán)中的。這種數(shù)據(jù)的分配方式可以彌補(bǔ)OS讀取數(shù)據(jù)量跟不上的不足。
1. 將條帶單元（stripe unit）從陣列的第一個(gè)硬盤(pán)到最后一個(gè)硬盤(pán)收集起來(lái)，就可以稱為條帶（stripe）。有的時(shí)候，條帶單元也被稱為交錯(cuò)深度。在光纖技術(shù)中，一個(gè)條帶單元被叫作段。
2.數(shù)據(jù)在陣列中的硬盤(pán)上是以條帶的形式分布的，條帶化是指數(shù)據(jù)在陣列中所有硬盤(pán)中的存儲(chǔ)過(guò)程。文件中的數(shù)據(jù)被分割成小塊的數(shù)據(jù)段在陣列中的硬盤(pán)上順序的存儲(chǔ)，這個(gè)最小數(shù)據(jù)塊就叫做條帶單元。
? ? ? ? 決定Ceph條帶化數(shù)據(jù)的3個(gè)因素：
◎ 對(duì)象大?。禾幱诜植际郊褐械膶?duì)象擁有一個(gè)最大可配置的尺寸（例如，2MB、4MB等），對(duì)象大小應(yīng)該足夠大以適應(yīng)大量的條帶單元。
?◎?條帶寬度：條帶有一個(gè)可以配置的單元大小，Ceph Client端將數(shù)據(jù)寫(xiě)入對(duì)象分成相同大小的條帶單元，除了最后一個(gè)條帶之外；每個(gè)條帶寬度，應(yīng)用是對(duì)象大小的一小部分，這樣使得一個(gè)對(duì)象可以包含多個(gè)條帶單元。
?◎?條帶總量：Ceph客戶端寫(xiě)入一系列的條帶單元到一系列的對(duì)象，這就決定了條帶的總量，這些對(duì)象被稱為對(duì)象集，當(dāng)Ceph客戶端寫(xiě)入的對(duì)象集合中的最后一個(gè)對(duì)象之后，它將會(huì)返回到對(duì)象集合中的第一個(gè)對(duì)象處。
Object與PG
? ? ? ? ?Ceph條帶化之后，將獲得N個(gè)帶有唯一oid（即object的id）。Object id 是進(jìn)行線性映射生成的，即由file的元數(shù)據(jù)、Ceph條帶化產(chǎn)生的object的序號(hào)連綴而成。此時(shí)object需要映射到PG中，該映射包括兩部分。
? ? ? ? ? 1.由Ceph集群指定的靜態(tài)Hash函數(shù)計(jì)算Object的oid，獲取到其Hash值。
? ? ? ? ? 2.將該Hash值與mask進(jìn)行操作，從而獲得PG IＤ
? ? ? ? ? 根據(jù)PADOS的設(shè)計(jì)，假定集群中設(shè)定的PG總數(shù)為M（M一般為2的整數(shù)冪），則mask的值為M-1。由此，Hash值計(jì)算之后，進(jìn)行按位與操作是想從所有PG中近似均勻地隨機(jī)選擇?；谠撛硪约案怕收摰南嚓P(guān)原理，當(dāng)用于數(shù)量龐大的Object以及PG時(shí)，獲得到的PG ID是近似均勻的。
? ? ? ? ?計(jì)算PG的ID示例如下：
? ? ? ? ? 1.Client輸入pool ID和對(duì)象ID（如pool='liverpool'，object-id='john'）。
? ? ? ? ? 2.CRUSH獲得對(duì)象ID并對(duì)其Hash運(yùn)算。
? ? ? ? ? 3.CRUSH計(jì)算OSD個(gè)數(shù)，Hash取模獲得PG的ID（如0x58）。
? ? ? ? ? 4.CRUSH獲得已命名pool的ID（如liverpool=4）。
? ? ? ? ? 5.CRUSH預(yù)先考慮到pool ID相同的PG ID（如4.0x58）。
PG與OSD
? ? ? ? ?由PG映射到數(shù)據(jù)存儲(chǔ)的實(shí)際單元OSD中，該映射是由CRUSH算法來(lái)確定的，將PG ID作為該算法的輸入，獲得到包含N個(gè)OSD的集合，集合中第一個(gè)OSD被作為主OSD，其他的OSD則依次作為從OSD。N為該P(yáng)G所在POOL下的副本數(shù)目，在生產(chǎn)環(huán)境N一般為3；OSD集合中的OSD將共同存儲(chǔ)和維護(hù)該P(yáng)G下的Object。需要注意的是，CRUSH算法的結(jié)果不是絕對(duì)不變的，而是受其他因素的影響。其影響因素主要有以下兩個(gè)。
? ? ? ? ?一是當(dāng)前系統(tǒng)狀態(tài)。也就是上文邏輯結(jié)構(gòu)中曾經(jīng)提及的Cluster Map（集群映射）。當(dāng)系統(tǒng)中的OSD狀態(tài)、數(shù)量發(fā)生變化 時(shí)，Cluster Map可能發(fā)生變化，而這種變化將會(huì)影響到PG到OSD之間的映射。
? ? ? ? ? 二是存儲(chǔ)策略配置。這里的策略主要與安全相關(guān)。利用策略配置，系統(tǒng)管理員可以指定承載同一個(gè)PG的3個(gè)OSD分別位于數(shù)據(jù)中心的不同服務(wù)器乃至機(jī)架上，從而進(jìn)一步改善存儲(chǔ)的可靠性。
? ? ? ? ?因此，只有在Cluster Map和存儲(chǔ)策略都不發(fā)生變化的時(shí)候，PG和OSD之間的映射關(guān)系才是固定不變的。在實(shí)際使用中，策略一經(jīng)配置通常不會(huì)改變。而系統(tǒng)狀態(tài)的改變或者是因?yàn)樵O(shè)備損壞，或者是因?yàn)榇鎯?chǔ)集群規(guī)模擴(kuò)大。好在Ceph本身提供了對(duì)于這種變化的自動(dòng)化支持，因而，即便PG與OSD之間的映射關(guān)系發(fā)生了變化，并不會(huì)對(duì)應(yīng)用造成困擾。事實(shí)上，Ceph正是需要有目的的利用這種動(dòng)態(tài)映射關(guān)系。正是利用了CRUSH的動(dòng)態(tài)特性，Ceph才可以將一個(gè)PG根據(jù)需要?jiǎng)討B(tài)遷移到不同的OSD組合上，從而自動(dòng)化地實(shí)現(xiàn)高可靠性、數(shù)據(jù)分布re-blancing等特性。
? ? ? ? 之所以在此次映射中使用CRUSH算法，而不是其他Hash算法，原因之一是CRUSH具有上述可配置特性，可以根據(jù)管理員的配置參數(shù)決定OSD的物理位置映射策略；另一方面是因?yàn)镃RUSH具有特殊的“穩(wěn)定性”，也就是當(dāng)系統(tǒng)中加入新的OSD導(dǎo)致系統(tǒng)規(guī)模增大時(shí)，大部分PG與OSD之間的映射關(guān)系不會(huì)發(fā)生改變，只是少部分PG的映射關(guān)系會(huì)發(fā)生變化并引發(fā)數(shù)據(jù)遷移。這種可配置性和穩(wěn)定性都不是普通Hash算法所能提供的。因此，CRUSH算法的設(shè)計(jì)也是Ceph的核心內(nèi)容之一。
PG與Pool
? ? ? ? ? Ceph存儲(chǔ)系統(tǒng)支持“池”（pool）的概念，這是存儲(chǔ)對(duì)象的邏輯分區(qū)。
? ? ? ? ? Ceph Client端從Ceph mon端檢索Cluster Map，寫(xiě)入對(duì)象到pool。Pool的副本數(shù)目，Crush規(guī)則和PG數(shù)目決定了Ceph將數(shù)據(jù)存儲(chǔ)的位置，如圖：
? ? ? ? ? ? Pool至少需要設(shè)定以下參數(shù)：
? ? ? ? ? ? ? ? ? ? ◎ ?對(duì)象的所有權(quán)/訪問(wèn)權(quán)
? ? ? ? ? ? ? ? ? ? ◎? PG數(shù)目
? ? ? ? ? ? ? ? ? ? ◎? 該P(yáng)ool使用的CRUSH規(guī)則
? ? ? ? ? ? ? ? ? ? ◎? ?對(duì)象副本的數(shù)目
CRUSH關(guān)系分析
? ? ? ? ? 從本質(zhì)上講，CRUSH算法是通過(guò)存儲(chǔ)設(shè)備的權(quán)重來(lái)計(jì)算數(shù)據(jù)對(duì)象的分布的。在計(jì)算過(guò)程中，通過(guò)Cluster Map（集群映射）、Data Distribution Policy（數(shù)據(jù)分布策略）和給出的一個(gè)隨機(jī)數(shù)共同決定數(shù)據(jù)對(duì)象的最終位置。
Cluster Map
? ? ? ? Cluster Map記錄所有可用的存儲(chǔ)資源及相互之間的空間層次結(jié)構(gòu)（集群中有多少個(gè)機(jī)架、機(jī)架上有多少服務(wù)器、每個(gè)機(jī)器上有多少磁盤(pán)等信息）。所謂的Map，顧名思義，就是類似于我們生活中的地圖。在Ceph存儲(chǔ)里，數(shù)據(jù)的索引都是通過(guò)各種不同的Map來(lái)實(shí)現(xiàn)的。另一方面，Map使得Ceph集群存儲(chǔ)設(shè)備在物理層作了一層防護(hù)。例如，在多副本結(jié)構(gòu)上，通過(guò)設(shè)備合理的Map（故障域設(shè)置為Host級(jí)），可以保證在某一服務(wù)器死機(jī)的情況下，有其他副本保留在正常的存儲(chǔ)節(jié)點(diǎn)上，能夠繼續(xù)提供服務(wù)，實(shí)現(xiàn)存儲(chǔ)的高可用。設(shè)置更高的故障域級(jí)別（如Rack、Row等）能保證整機(jī)柜或同一排機(jī)柜在掉電情況下數(shù)據(jù)的可用性和完整性。
1.Cluster Map的分層結(jié)構(gòu)
? ? ? ? ?Cluster Map由Device和Bucket構(gòu)成。它們都有自己的ID和權(quán)重值，并且形成一個(gè)以Device為葉子節(jié)點(diǎn)、Bucket為軀干的樹(shù)狀結(jié)果。
? ? ? ? ? ? Bucket擁有不同的類型，如Host、Row、Rack、Room等，通常我們默認(rèn)把機(jī)架類型定義為Rack，主機(jī)類型定義為Host，數(shù)據(jù)中心（IDC機(jī)房）定義為Data Center。Bucket的類型都是虛擬結(jié)構(gòu)，可以根據(jù)自己的喜好設(shè)計(jì)合適的類型。Device節(jié)點(diǎn)的權(quán)重值代表了存儲(chǔ)設(shè)備的容量與性能。其中，磁盤(pán)容量是權(quán)重大小的關(guān)鍵因素。
? ? ? ? ? OSD的權(quán)重值越高，對(duì)應(yīng)磁盤(pán)會(huì)被分配寫(xiě)入更多的數(shù)據(jù)?？傮w來(lái)看，數(shù)據(jù)會(huì)被均勻?qū)懭敕植加诩核写疟P(pán)，從而提高整體性能和可靠性。無(wú)論磁盤(pán)的規(guī)格容量，總能夠均勻使用。
? ? ? ? ? 關(guān)于OSD權(quán)重值的大小值的配比，官方默認(rèn)值設(shè)置為1TB容量的硬盤(pán)，對(duì)應(yīng)權(quán)重值為1.可以在/etc/init.d/ceph原碼里查看相關(guān)的內(nèi)容。
2.恢復(fù)與動(dòng)態(tài)平衡
? ? ? ? ? 在默認(rèn)設(shè)置下，當(dāng)集群里有組件出現(xiàn)故障時(shí)（主要是OSD，也可能是磁盤(pán)或者網(wǎng)絡(luò)等），Ceph會(huì)把OSD標(biāo)記為down，如果在300s內(nèi)未能回復(fù)，集群就會(huì)開(kāi)始進(jìn)行恢復(fù)狀態(tài)。這個(gè)“300s”可以通過(guò)"mon osd down ourt interval“配置選項(xiàng)修改等待時(shí)間。PG（Placement Groups）是Ceph數(shù)據(jù)管理（包括復(fù)制、修復(fù)等動(dòng)作）單元。當(dāng)客戶端把讀寫(xiě)請(qǐng)求（對(duì)象單元）推送到Ceph時(shí)，通過(guò)CRUSH提供的Hash算法把對(duì)象映射到PG。PG在CRUSH策略的影響下，最終會(huì)被映射到OSD上。
Data Distribution Policy
? ? ? ? ? ? ?Data Distribution Policy由Placement Rules組成。Rule決定了每個(gè)數(shù)據(jù)對(duì)象有多少個(gè)副本，這些副本存儲(chǔ)的限制條件（比如3個(gè)副本放在不同的機(jī)架中）。一個(gè)典型的rule如下所示：
rule replicated_ruleset ? ? {? ##rule名字
? ? ? ruleset 0? ? ? ? ? ? ? ? ? ? #rule的ID
? ? ? type replicated? ? ? ? ##類型為副本模式，另外一種模式為糾刪碼（EC）
? ? ? min_size 1? ? ? ? ? ? ? ##如果存儲(chǔ)池的副本數(shù)大于這個(gè)值，此rule不會(huì)應(yīng)用
? ? ? max_size 10 ? ? ? ? ? ##如果存儲(chǔ)池的副本數(shù)大于這個(gè)值，此rule不會(huì)應(yīng)用
? ? ? step take default ? ?##以default root 為入口
? ? ? step chooseleaf firstn 0 type host ? ##隔離城為host級(jí)，即不同副本在不同的主機(jī)上
? ? ? step emit ? ? ? ? ? ? ? ? ##提交}
根據(jù)實(shí)際的設(shè)備環(huán)境，可以定制符合自己需求的Rule。
CRUSH中的偽隨機(jī)
? ? ? ? ? ? CRUSH(x) -> (osd1,osd2……osd N)
? ? ? ? ? CRUSH使用了多參數(shù)的Hash函數(shù)在Hash之后，映射都是按既定規(guī)則選擇的，這使得從x到OSD的集合是確定的和獨(dú)立的。CRUSH只使用Cluster Map、Placement Rules、X。CRUSH是偽隨機(jī)算法，相似輸入的結(jié)果之間沒(méi)有相關(guān)性。
? ? ? ? ? ? PGP是PG的邏輯承載體，是CRUSH算法不可缺少的部分。在Ceph集群里，增加PG數(shù)量，PG到OSD的映射關(guān)系就會(huì)發(fā)生變化，但此時(shí)存儲(chǔ)在PG里的數(shù)據(jù)并興地發(fā)生遷移，只有當(dāng)PGP的數(shù)量也增加時(shí)，數(shù)據(jù)遷移才會(huì)真正開(kāi)始。關(guān)于PG和PGP的關(guān)系，假如把PG比作參加宴會(huì)的人，那么PGP就是人坐的椅子，如果人員增加時(shí)，人的座位排序就會(huì)發(fā)生變化，只有增加椅子時(shí)，真正的座位排序變更才會(huì)落實(shí)。因此，人和椅子的數(shù)量一般都保持一致。所以，在ceph里，通常把PGP和PG設(shè)置成一致的。
查看PG映射OSD的集合，即PG具體分配到OSD的歸屬。
ceph pg dump | grep ^22\. | awk '{print $1 "\t" $17}'
? ? ? ? ? ?在Ceph集群里，當(dāng)有數(shù)據(jù)對(duì)象要寫(xiě)入集群時(shí)，需要進(jìn)行兩次映射，第一次從object-->PG，第2次是PG-->OSD set 。每一次的映射都是與其他對(duì)象無(wú)相關(guān)的，這充分體現(xiàn)了CRUSH的獨(dú)立性（充分分散）和確定性（可確定的存儲(chǔ)位置）。
