Ceph之RADOS設(shè)計(jì)原理與實(shí)現(xiàn)

Ceph之RADOS設(shè)計(jì)原理與實(shí)現(xiàn)目錄TOC\h\h第1章一生萬物——RADOS導(dǎo)論\h1.1RADOS概述\h1.2存儲池與PG\h1.3對象演進(jìn)與排序\h1.4stable_mod與客戶端尋址\h1.5PG分裂與集群擴(kuò)容\h1.6總結(jié)和展望\h第2章計(jì)算尋址之美與數(shù)據(jù)平衡之殤——CRUSH\h2.1抽簽算法\h2.2CRUSH算法詳解\h2.2.1集群的層級化描述——clustermap\h2.2.2數(shù)據(jù)分布策略——placementrule\h2.3調(diào)制CRUSH\h2.3.1編輯CRUSHmap\h2.3.2定制CRUSH規(guī)則\h2.4數(shù)據(jù)重平衡\h2.4.1reweight\h2.4.2weight-set\h2.4.3upmap\h2.4.4balancer\h2.5總結(jié)和展望\h第3章集群的大腦——Monitor\h3.1集群表OSDMap\h3.2集群管理\h3.2.1OSD管理\h3.2.2存儲池管理\h3.2.3告警管理\h3.3總結(jié)和展望\h第4章存儲的基石——OSD\h4.1OSD概述\h4.1.1集群管理\h4.1.2網(wǎng)絡(luò)通信\h4.1.3公共服務(wù)\h4.2OSD上電\h4.3故障檢測\h4.4空間管理\h4.5總結(jié)和展望\h第5章高效本地對象存儲引擎——BlueStore\h5.1設(shè)計(jì)原理\h5.2磁盤數(shù)據(jù)結(jié)構(gòu)\h5.2.1PG\h5.2.2對象\h5.3緩存機(jī)制\h5.3.1概述\h5.3.2實(shí)現(xiàn)\h5.4磁盤空間管理\h5.4.1概述\h5.4.2BitmapFreelistManager\h5.4.3BitmapAllocator\h5.5BlueFS\h5.5.1概述\h5.5.2磁盤數(shù)據(jù)結(jié)構(gòu)\h5.5.3塊設(shè)備\h5.6實(shí)現(xiàn)原理\h5.6.1mkfs\h5.6.2mount\h5.6.3read\h5.6.4write\h5.7使用指南\h5.7.1部署B(yǎng)lueStore\h5.7.2配置參數(shù)\h5.8總結(jié)和展望\h第6章移動(dòng)的對象載體——PG\h6.1基本概念與術(shù)語\h6.2讀寫流程\h6.2.1消息接收與分發(fā)\h6.2.2do_request\h6.2.3do_op\h6.2.4execute_ctx\h6.3狀態(tài)遷移\h6.3.1狀態(tài)機(jī)概述\h6.3.2創(chuàng)建PG\h6.3.3Peering\h6.4總結(jié)和展望\h第7章在線數(shù)據(jù)恢復(fù)——Recovery和Backfill\h7.1Recovery\h7.1.1資源預(yù)留\h7.1.2對象修復(fù)\h7.1.3增量Recovery和異步Recovery\h7.2Backfill\h7.3總結(jié)和展望\h第8章數(shù)據(jù)正確性與一致性的守護(hù)者——Scrub\h8.1Scrub的指導(dǎo)思想\h8.2Scrub流程詳解\h8.2.1資源預(yù)留\h8.2.2范圍界定\h8.2.3對象掃描\h8.2.4副本比對\h8.2.5統(tǒng)計(jì)更新與自動(dòng)修復(fù)\h8.3Scrub搶占\h8.4總結(jié)和展望\h第9章基于dmClock的分布式流控策略\h9.1概述\h9.2dmClock基本原理\h9.2.1mClock\h9.2.2dmClock\h9.3dmClock算法實(shí)現(xiàn)\h9.3.1I/O請求入隊(duì)\h9.3.2I/O請求出隊(duì)\h9.3.3實(shí)例分析\h9.4在Ceph中的應(yīng)用實(shí)踐\h9.4.1client的界定\h9.4.2支持帶寬限制\h9.4.3存儲卷的QoS\h9.4.4集群流控策略\h9.5總結(jié)和展望\h第10章糾刪碼原理與實(shí)踐\h10.1RAID技術(shù)概述\h10.2RS-RAID和Jerasure\h10.2.1計(jì)算校驗(yàn)和\h10.2.2數(shù)據(jù)恢復(fù)\h10.2.3算術(shù)運(yùn)算\h10.2.4缺陷與改進(jìn)\h10.2.5Jerasure\h10.3糾刪碼在Ceph中的應(yīng)用\h10.3.1術(shù)語\h10.3.2新寫\h10.3.3讀\h10.3.4覆蓋寫\h10.3.5日志\h10.3.6Scrub\h10.4總結(jié)和展望第1章

一生萬物——RADOS導(dǎo)論Ceph誕生于10年前，本來的意圖是為大型超級計(jì)算機(jī)打造一個(gè)高可靠、高可擴(kuò)展和高性能的分布式文件系統(tǒng)。在漫長的演進(jìn)過程中，Ceph基于計(jì)算分布數(shù)據(jù)、完全去中心化的設(shè)計(jì)理念，經(jīng)受住了時(shí)間考驗(yàn)，逐漸成長為大數(shù)據(jù)時(shí)代最具生命力與參考價(jià)值的開源統(tǒng)一存儲系統(tǒng)。Ceph的特點(diǎn)亦即其優(yōu)點(diǎn)如下：1）Ceph是軟件定義存儲。Ceph可以運(yùn)行在幾乎所有主流Linux發(fā)行版（例如CentOS和Ubuntu）和其他類UNIX操作系統(tǒng)（例如FreeBSD）之上。2016年，社區(qū)成功地將Ceph從x86架構(gòu)移植到ARM架構(gòu)，表明Ceph開始進(jìn)軍移動(dòng)通信、低功耗等前沿領(lǐng)域。因此，Ceph的應(yīng)用場景覆蓋當(dāng)前主流的軟硬件平臺。2）Ceph是分布式存儲。分布式基因使其可以輕易管理成百上千個(gè)節(jié)點(diǎn)、PB級及以上存儲容量的大規(guī)模集群，基于計(jì)算尋址則讓Ceph客戶端可以直接與服務(wù)端的任意節(jié)點(diǎn)通信，從而避免因?yàn)榇嬖谠L問熱點(diǎn)而產(chǎn)生性能瓶頸。實(shí)際上，在沒有網(wǎng)絡(luò)傳輸限制的前提下，Ceph可以實(shí)現(xiàn)我們夢寐以求的、性能與集群規(guī)模呈線性擴(kuò)展的優(yōu)秀特性。3）Ceph是統(tǒng)一存儲。Ceph既支持傳統(tǒng)的塊、文件存儲協(xié)議，例如SAN和NAS，也支持新興的對象存儲協(xié)議，例如S3和Swift，這使得Ceph在理論上可以滿足當(dāng)前一切主流的存儲需求。此外，良好的架構(gòu)設(shè)計(jì)使得Ceph可以輕易地拓展至需要存儲的任何領(lǐng)域。上述特點(diǎn)使得只要存在存儲需求，Ceph就能找到用武之地。因此，誠如Ceph社區(qū)所言：Ceph是存儲的未來！為了盡可能地拓展“觸角”，Ceph在架構(gòu)上采用存儲應(yīng)用與存儲服務(wù)完全分離的模式（即Client/Server模式），并基于RADOS（ReliableAutonomicDistributedObjectStore）——一種可靠、高度自治的分布式對象存儲系統(tǒng)，對外提供高性能和可輕松擴(kuò)展的存儲服務(wù)。毋庸置疑，RADOS是Ceph的核心組件。理論上，基于RADOS及其派生的librados標(biāo)準(zhǔn)庫可以開發(fā)任意類型的存儲應(yīng)用，典型的如Ceph的三大核心應(yīng)用——RBD（RadosBlockDevice）、RGW（RadosGateWay）和CephFS，如圖1-1所示。圖1-1Ceph的三大核心應(yīng)用作為全書的開始，本章簡要介紹包括OSD、Monitor、存儲池、PG、對象在內(nèi)的基本概念，旨在為讀者建立一個(gè)對RADOS的初步印象。但是作為一個(gè)分布式存儲系統(tǒng)的核心組件，RADOS的龐大和復(fù)雜在所難免，因此本章的介紹不免存在掛一漏萬之嫌。好在序幕剛剛開啟，如果存在某些當(dāng)前無法理解的細(xì)節(jié)，讀者大可不必灰心，我們將在后續(xù)章節(jié)逐一解答。1.1RADOS概述當(dāng)存儲容量達(dá)到PB級別或者更高規(guī)模時(shí)，對應(yīng)的存儲系統(tǒng)必然一直處于變化之中：隨著存儲需求的增長，會(huì)不斷有新設(shè)備被加入進(jìn)來；老設(shè)備因?yàn)楣收隙粩嗟乇惶蕴?；任何時(shí)候都有大量數(shù)據(jù)寫入、更新或者刪除；持續(xù)不斷的數(shù)據(jù)恢復(fù)，或者出于負(fù)載均衡而自動(dòng)觸發(fā)的數(shù)據(jù)遷移行為等。如果再考慮用戶不斷提升的數(shù)據(jù)可靠性和近乎無止境的性能訴求，那么任何基于中心控制器和查表法設(shè)計(jì)的傳統(tǒng)存儲都難免力不從心。Ceph基于RADOS，可提供可靠、高性能和全分布式的存儲服務(wù)?；谟?jì)算實(shí)時(shí)分布數(shù)據(jù)，允許自定義故障域，再加上任意類型的應(yīng)用程序數(shù)據(jù)都被抽象為對象這個(gè)同時(shí)具備安全和強(qiáng)一致性語義的抽象數(shù)據(jù)類型，從而，RADOS可輕松地在大規(guī)模異構(gòu)存儲集群中實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)與負(fù)載均衡。簡言之，一個(gè)RADOS集群由大量OSD（ObjectStoreDevice，對象存儲設(shè)備）和少數(shù)幾個(gè)Monitor組成。OSD是個(gè)抽象概念，一般對應(yīng)一個(gè)本地塊設(shè)備（如一塊磁盤或者一個(gè)RAID組等），在其工作周期內(nèi)會(huì)占用一些CPU、內(nèi)存、網(wǎng)絡(luò)等物理資源，并依賴某個(gè)具體的本地對象存儲引擎，來訪問位于塊設(shè)備上的數(shù)據(jù)?；诟呖煽吭O(shè)計(jì)的Monitor團(tuán)體（quorum，本質(zhì)上也是一個(gè)集群）則負(fù)責(zé)維護(hù)和分發(fā)集群的關(guān)鍵元數(shù)據(jù)，同時(shí)也是客戶端與RADOS集群建立連接的橋梁——客戶端通過咨詢Monitor獲得集群的關(guān)鍵元數(shù)據(jù)之后，就可以通過約定的方式（例如RBD、RGW、CephFS等）來訪問RADOS集群，如圖1-2所示。為了去中心化、免除單點(diǎn)故障，RADOS使用一張緊湊的集群表對集群拓?fù)浣Y(jié)構(gòu)和數(shù)據(jù)映射規(guī)則進(jìn)行描述。任何時(shí)刻，任何持有該表的合法客戶端都可以獨(dú)立地與位于任意位置的OSD直接通信。當(dāng)集群拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)，RADOS確保這些變化能夠及時(shí)地被Monitor捕獲，并通過集群表高效傳遞至所有受影響的OSD和客戶端，以保證對外提供不中斷的業(yè)務(wù)訪問。由于數(shù)據(jù)復(fù)制、故障檢測和數(shù)據(jù)恢復(fù)都由每個(gè)OSD自動(dòng)進(jìn)行，因此即便存儲容量上升至PB級別或者以上，系統(tǒng)也不會(huì)存在明顯的調(diào)度和處理瓶頸。圖1-2一個(gè)典型的RADOS集群RADOS取得高可擴(kuò)展性的關(guān)鍵在于徹底拋棄了傳統(tǒng)存儲系統(tǒng)中諸如中心控制器、網(wǎng)關(guān)等概念，另辟蹊徑地以基于可擴(kuò)展哈希的受控副本分布算法——CRUSH（ControlledReplicationUnderScalableHashing）取而代之，作為銜接客戶端和OSD的橋梁，使得客戶端可以直接與OSD通信，從而得以徹底免除需要查表的煩瑣操作。進(jìn)一步地，由于CRUSH包含了獲取集群當(dāng)前數(shù)據(jù)分布形態(tài)所需的全部信息，所以O(shè)SD之間通過交互即可智能地完成諸如故障、擴(kuò)容等引起的數(shù)據(jù)重新分布，而無須中心控制器進(jìn)行指導(dǎo)和干預(yù)。集群表屏蔽了實(shí)際集群可能呈現(xiàn)的紛繁蕪雜的細(xì)節(jié)，使得客戶端可以將整個(gè)RADOS集群當(dāng)作一個(gè)單一的“對象”來處理。當(dāng)然，在生產(chǎn)環(huán)境中，由于集群本身可能具有復(fù)雜的拓?fù)浣Y(jié)構(gòu)，以及隨著時(shí)間的推移，不可避免地趨于異構(gòu)化，為了最大化資源利用率，我們還必須對集群資源合理地分割和重組。1.2存儲池與PG為了實(shí)現(xiàn)存儲資源按需配置，RADOS對集群中的OSD進(jìn)行池化管理。資源池（對存儲系統(tǒng)而言，具體則是存儲池）實(shí)際上是個(gè)虛擬概念，表示一組約束條件，例如可以針對存儲池設(shè)計(jì)一組CRUSH規(guī)則，限制其只能使用某些規(guī)格相同的OSD，或者盡量將所有數(shù)據(jù)副本分布在物理上隔離的、不同的故障域；也可以針對不同用途的存儲池指定不同的副本策略，例如若存儲池承載的存儲應(yīng)用對時(shí)延敏感，則采用多副本備份策略；反之，如果存儲的是一些對時(shí)延不敏感的數(shù)據(jù)（例如備份數(shù)據(jù)），為提升空間利用率則采用糾刪碼備份策略；甚至可以為每個(gè)存儲池分別指定獨(dú)立的Scrub、壓縮、校驗(yàn)策略等。為了實(shí)現(xiàn)不同存儲池之間的策略隔離，RADOS并不是將任何應(yīng)用程序數(shù)據(jù)一步到位地寫入OSD的本地存儲設(shè)備，而是引入了一個(gè)中間結(jié)構(gòu)，稱為PG（PlacementGroup），執(zhí)行兩次映射，如圖1-3所示。圖1-3應(yīng)用程序數(shù)據(jù)通過兩次映射到達(dá)OSD的本地存儲設(shè)備第一次映射是靜態(tài)的，負(fù)責(zé)將任意類型的客戶端數(shù)據(jù)按照固定大小進(jìn)行切割、編號后，作為偽隨機(jī)哈希函數(shù)輸入，均勻映射至每個(gè)PG，以實(shí)現(xiàn)負(fù)載均衡策略；第二次映射實(shí)現(xiàn)PG到OSD的映射，仍然采用偽隨機(jī)哈希函數(shù)（以保證PG在OSD之間分布的均勻性），但是其輸入除了全局唯一的PG身份標(biāo)識之外，還引入了集群拓?fù)洌⑶沂褂肅RUSH規(guī)則對映射過程進(jìn)行調(diào)整，以幫助PG在不同OSD之間靈活遷移，進(jìn)而實(shí)現(xiàn)數(shù)據(jù)可靠性、自動(dòng)平衡等高級特性。最終，存儲池以PG作為基本單位進(jìn)行管理。為了維持扁平尋址空間，實(shí)際上要求PG擁有一個(gè)全集群唯一的身份標(biāo)識——PGID。由于集群所有存儲池都由Monitor統(tǒng)一管理，所以Monitor可以為每個(gè)存儲池分配一個(gè)集群內(nèi)唯一的存儲池標(biāo)識。基于此，我們只需要為存儲池中的每個(gè)PG再分配一個(gè)存儲池內(nèi)唯一的編號即可。假定某個(gè)存儲池的標(biāo)識為1，創(chuàng)建此存儲池時(shí)指定了256個(gè)PG，那么容易理解對應(yīng)的PGID可以寫成1.0，1.1，…，1.255這樣的形式。1.3對象演進(jìn)與排序與Linux“一切皆文件”的設(shè)計(jì)理念類似，Ceph將任意類型的客戶端數(shù)據(jù)都抽象為對象這個(gè)小巧而精致的概念。文件伴隨文件系統(tǒng)一同誕生，是計(jì)算機(jī)科學(xué)中最基本和最經(jīng)典的概念之一。為了增強(qiáng)（人機(jī)之間的）可交互性，一般而言文件對外支持使用基于UTF-8編碼方式的字符串進(jìn)行命名，作為其唯一身份標(biāo)志。這意味著在最初的文件系統(tǒng)設(shè)計(jì)中，所有文件都共享一個(gè)扁平的全局命名空間（namespace）。信息技術(shù)的飛速發(fā)展使得數(shù)據(jù)（信息）呈井噴式增長，因此，與傳統(tǒng)文件系統(tǒng)不同，現(xiàn)代文件系統(tǒng)普遍采用面向管理海量數(shù)據(jù)（文件）的設(shè)計(jì)——例如XFS，這是一個(gè)64位文件系統(tǒng)，64位意味著XFS理論上可以存儲和管理多達(dá)264個(gè)文件。而被譽(yù)為最后一個(gè)文件系統(tǒng)的ZFS則更進(jìn)一步地采用面向128位尋址空間的設(shè)計(jì)（注：這表明單個(gè)ZFS文件系統(tǒng)可以管理的存儲空間為2128，但是因?yàn)閆FS仍然采用64位的inode設(shè)計(jì)，所以單個(gè)ZFS文件系統(tǒng)能夠存儲的最大文件數(shù)量仍然與XFS相同。）。正如ZFS的創(chuàng)造者所言：理論上，單個(gè)ZFS所能管理的存儲容量“即便窮盡這個(gè)地球上的每粒沙子來制造存儲設(shè)備也無法企及”。出于查找效率考慮，面向管理海量文件而生的現(xiàn)代文件系統(tǒng)不可能繼續(xù)采取全局唯一的扁平命名空間，而必須采用更高效的組織方式。參考人類社會(huì)族譜、各類社會(huì)組織機(jī)構(gòu)等，一個(gè)自然的想法是轉(zhuǎn)而使用樹這種非線性數(shù)據(jù)結(jié)構(gòu)對文件系統(tǒng)中所有文件進(jìn)行描述：樹中每個(gè)葉子節(jié)點(diǎn)表示一個(gè)文件，每個(gè)中間節(jié)點(diǎn)則起到了隔離和保護(hù)其轄下所有文件、特別是每個(gè)文件名作用域的作用，因此這些中間節(jié)點(diǎn)又被形象地稱為文件夾（或者目錄）。這樣，即便使用數(shù)據(jù)結(jié)構(gòu)中最常見的平衡二叉樹來管理單個(gè)64位文件系統(tǒng)中的所有文件（注：指理論上限，即264。），樹的高度（或者層級）也不超過64，也就是查找任何文件都可以經(jīng)過至多64次比較得到。與文件類似，Ceph也使用字符串對對象進(jìn)行標(biāo)識，使用命名空間對每個(gè)對象歸屬的作用域進(jìn)行限制和隔離。除此之外，因?yàn)閷ο螅ū仨毻ㄟ^PG間接地）歸屬于某個(gè)存儲池，因此對象還必須記憶其歸屬的存儲池標(biāo)識。作為文件系統(tǒng)中最經(jīng)典的數(shù)據(jù)備份機(jī)制，快照和克隆對所有存儲系統(tǒng)而言幾乎都是必備功能。在將一切客戶端數(shù)據(jù)對象化之后，很容易理解Ceph的快照和克隆功能，其實(shí)現(xiàn)粒度也應(yīng)當(dāng)是對象級的。因此，為了區(qū)分原始對象和由其產(chǎn)生的一眾克隆對象，必須通過向?qū)ο笾刑砑尤治ㄒ坏目煺諛?biāo)識（snap-id）加以解決。進(jìn)一步，在宣布支持糾刪碼這種數(shù)據(jù)備份機(jī)制后，Ceph的數(shù)據(jù)強(qiáng)一致性設(shè)計(jì)必然要求其支持對象粒度的數(shù)據(jù)回滾功能，為此還必須能夠區(qū)分某個(gè)糾刪碼對象的當(dāng)前版本和由其衍生的一眾歷史版本。類似地，這通過向?qū)ο笾刑砑臃制瑯?biāo)識（shard-id）和對象版本號（generation）加以解決。至此，我們已經(jīng)得到了基于對象名、命名空間、對象歸屬的存儲池標(biāo)識、快照標(biāo)識、分片標(biāo)識和版本號區(qū)分集群中各種對象的方法，基于這些特征值構(gòu)造的數(shù)據(jù)結(jié)構(gòu)也被稱為對象標(biāo)識（object-id），其在集群內(nèi)唯一定義一個(gè)Ceph對象。事實(shí)上，無論是Ceph引以為傲的自動(dòng)數(shù)據(jù)恢復(fù)和平衡功能，還是用于守護(hù)數(shù)據(jù)正確性與一致性的Scrub機(jī)制，都無不隱式地依賴于“可以通過某種手段不重復(fù)地遍歷PG中所有對象”這個(gè)前提，這實(shí)際上要求能夠?qū)G中的每個(gè)對象進(jìn)行嚴(yán)格排序。一個(gè)比較直觀的方法是簡單地將對象標(biāo)識中所有特征值按照一定順序拼接起來，形成一個(gè)囊括對象所有特征信息的字符串。這樣，直接通過字符串比較（容易理解，每個(gè)這種類型的字符串都唯一對應(yīng)一個(gè)對象），我們即可實(shí)現(xiàn)對象排序。然而不幸的是，一些典型應(yīng)用，例如RBD，為了保證對象的唯一性，一般都會(huì)傾向于使用較長的對象名（例如rbd_data.75b86e238e1f29.0000000000000050），因此如果直接采用上面這種方式，其效率實(shí)際上是十分低下的。一個(gè)改進(jìn)的方向是與存儲池標(biāo)識類似，要求每個(gè)對象也直接采用集群內(nèi)唯一的數(shù)字標(biāo)識?？紤]到Ceph本身是個(gè)分布式存儲系統(tǒng)，這個(gè)數(shù)字標(biāo)識只能由客戶端在創(chuàng)建每個(gè)對象時(shí)統(tǒng)一向Monitor申請。顯然，這樣做效率只會(huì)更低。那么，是否還有其他代價(jià)較小的方法能產(chǎn)生這個(gè)數(shù)字標(biāo)識呢？答案是哈希。哈希是一種在密碼學(xué)中被廣泛使用的非對稱數(shù)學(xué)變換手段。大部分情況下，針對不同輸入，哈希都能夠得到不同輸出，而使用不同輸入得到相同輸出的現(xiàn)象稱為哈希沖突。產(chǎn)生哈希沖突的概率一是取決于算法本身，二是取決于輸出長度?？紤]到目前廣泛使用的幾種哈希算法都經(jīng)過大量工程實(shí)踐驗(yàn)證，其算法本身的質(zhì)量毋庸置疑，因此采用典型哈希算法（例如MD5、SHA）產(chǎn)生沖突的概率主要受輸出長度影響。舉例來說，如果輸出長度為16位，則原始輸入經(jīng)過哈希后至多產(chǎn)生65536種不同的結(jié)果（輸出）；如果輸出長度增加到32位，則將產(chǎn)生超過40億種不同的結(jié)果。顯然，在保證算法不變的前提下，增加輸出長度可以不同程度地降低產(chǎn)生沖突的概率。當(dāng)然，隨著輸出長度的增加，所需的存儲空間也將相應(yīng)增加，加之沖突的發(fā)生理論上不可避免，因此一般而言輸出長度也不是越大越好?？紤]到Ceph當(dāng)前的實(shí)現(xiàn)中，我們總是以PG為單位進(jìn)行數(shù)據(jù)遷移、Scrub等，因此實(shí)際上僅需要能夠針對單個(gè)PG中的全部對象進(jìn)行排序即可。以標(biāo)稱容量為1TB的磁盤為例，按照每個(gè)OSD承載100個(gè)PG并且每個(gè)對象大小固定為4MB進(jìn)行估算，平均每個(gè)PG存儲的對象數(shù)量約為2621個(gè)。因此，在相當(dāng)長的一段時(shí)間內(nèi)（注：參考摩爾定律，假定磁盤容量每年翻一番，按照前面的估算，2621×29=1341952，即要到9年之后，單個(gè)PG能夠存儲的對象數(shù)量才能達(dá)到百萬級別。），我們認(rèn)為每個(gè)PG能夠存儲的最大對象數(shù)量大約在百萬至千萬級別。進(jìn)一步地，綜合考慮內(nèi)存消耗（這個(gè)哈希結(jié)果需要作為對象標(biāo)識的一部分常駐內(nèi)存）和比較效率（我們引入這個(gè)數(shù)值的初衷就是為了對對象排序進(jìn)行加速），采用32位的哈希輸出是一個(gè)比較合理的選擇。確定了哈希輸出長度后，反過來我們需要決策哪些對象特征值適合充當(dāng)哈希輸入。最差的做法當(dāng)然是直接使用對象的全部特征值?？紤]到快照、糾刪碼數(shù)據(jù)回滾并不是常見操作，因此與之相關(guān)的快照標(biāo)識、分片標(biāo)識、版本號這類特征值在大部分情況下都是無效值，可以排除在外。進(jìn)一步地，由于PG不能在存儲池之間共享，即某個(gè)PG中的所有對象都只能歸屬于同一個(gè)存儲池，所以在計(jì)算哈希時(shí)，存儲池標(biāo)識也是無效輸入，同樣需要予以剔除。綜上，我們認(rèn)為使用命名空間加上對象名作為哈希輸入是合適的。包含此32位哈希值之后的對象標(biāo)識如表1-1所示。表1-1對象標(biāo)識注：\h/bob/hash/evahash.html基于對象的特征值可以定義對象排序所依賴的比較算法如下：·比較兩個(gè)對象的分片標(biāo)識·比較兩個(gè)對象的存儲池標(biāo)識·比較兩個(gè)對象的32位哈希值·比較兩個(gè)對象的命名空間·比較兩個(gè)對象的鍵·比較兩個(gè)對象的對象名·比較兩個(gè)對象的快照標(biāo)識·比較兩個(gè)對象的版本號·判定兩個(gè)對象相等進(jìn)一步地，基于上述排序算法可以對PG中的所有對象執(zhí)行快速排序，這是實(shí)現(xiàn)Backfill、Scrub等復(fù)雜功能的理論基礎(chǔ)。1.4stable_mod與客戶端尋址Ceph通過C/S模式實(shí)現(xiàn)外部應(yīng)用程序與RADOS集群之間的交互。任何時(shí)候，應(yīng)用程序通過客戶端訪問集群時(shí)，首先由其客戶端負(fù)責(zé)生成一個(gè)字符串形式的對象名，然后基于對象名計(jì)算得出一個(gè)32位哈希值。針對此哈希值，通過簡單的數(shù)學(xué)運(yùn)算，例如對存儲池的PG數(shù)（pg_num）取模，可以得到一個(gè)PG在存儲池內(nèi)部的編號，加上對象本身已經(jīng)記錄了其歸屬存儲池的唯一標(biāo)識，最終可以找到負(fù)責(zé)承載該對象的PG。假定標(biāo)識為1的存儲池中的某個(gè)對象，經(jīng)過計(jì)算后32位哈希值為0x4979FA12，并且該存儲池的pg_num為256，則由：0x4979FA12mod256=18

我們知道此對象由存儲池內(nèi)編號為18的PG負(fù)責(zé)承載，并且其完整的PGID為1.18。一般而言，將某個(gè)對象映射至PG時(shí)，我們并不會(huì)使用全部的32位哈希值，因此會(huì)出現(xiàn)不同對象被映射至同一個(gè)PG的現(xiàn)象。我們很容易驗(yàn)證該存儲池內(nèi)哈希值如下的其他對象，通過模運(yùn)算同樣會(huì)被映射至PGID為1.18的PG之上。0x4979FB12mod256=18

0x4979FC12mod256=18

0x4979FD12mod256=18

…

可見，針對上面這個(gè)例子，我們僅僅使用了這個(gè)“全精度”32位哈希值的后8位。因此，如果pg_num可以寫成2n的形式（例如這里256可以寫成28，即是2的整數(shù)次冪），則每個(gè)對象執(zhí)行PG映射時(shí)，其32位哈希值中僅有低n位是有意義的。進(jìn)一步地，我們很容易驗(yàn)證此時(shí)歸屬于同一個(gè)PG的對象，其32位哈希值中低n位都是相同的?；诖耍覀儗?n-1稱為pg_num的掩碼，其中n為掩碼的位數(shù)。相反，如果pg_num不是2的整數(shù)次冪，即無法寫成2n的形式，仍然假定此時(shí)其最高位為n（從1開始計(jì)數(shù)），則此時(shí)普通的取模操作無法保證“歸屬于某個(gè)PG的所有對象的低n位都相同”這個(gè)特性。例如，假定pg_num為12，此時(shí)n=4，容易驗(yàn)證如下輸入經(jīng)過模運(yùn)算后結(jié)果一致，但是它們只有低2位是相同的。0x00mod12=0

0x0Cmod12=0

0x18mod12=0

0x24mod12=0

…

因此需要針對普通的取模操作加以改進(jìn)，以保證針對不同輸入，當(dāng)計(jì)算結(jié)果相等時(shí)，維持“輸入具有盡可能多的、相同的低位”這個(gè)相對有規(guī)律的特性。一種改進(jìn)的方案是使用掩碼來替代取模操作。例如仍然假定pg_num對應(yīng)的最高位為n，則其掩碼為2n-1，需要將某個(gè)對象映射至PG時(shí)，直接執(zhí)行hash&(2n-1)即可。但是這個(gè)改進(jìn)方案仍然存在一個(gè)潛在問題：如果pg_num不是2的整數(shù)次冪，那么直接采用這種方式進(jìn)行映射會(huì)產(chǎn)生空穴，即將某些對象映射到一些實(shí)際上并不存在的PG上，如圖1-4所示。這里pg_num為12，n=4，可見執(zhí)行hash&(24-1)會(huì)產(chǎn)生0～15共計(jì)16種不同的結(jié)果。但是實(shí)際上編號為12～15的PG并不存在。圖1-4使用掩碼方式進(jìn)行對象至PG映射因此需要進(jìn)一步對上述改進(jìn)方案進(jìn)行修正。由n為pg_num的最高位，必然有：pg_num≥2

n-1

即[0，2n-1]內(nèi)的PG必然都是存在的。于是可以通過hash&(2n-1-1)將那些實(shí)際上并不存在的PG重新映射到[0，2n-1]區(qū)間，如圖1-5所示。修正后的效果等同于將這些空穴通過平移的方式重定向到前半個(gè)對稱區(qū)間。圖1-5使用修正后的掩碼方式對圖1-4中的映射結(jié)果進(jìn)行校正這樣，退而求其次，如果pg_num不是2的整數(shù)次冪，我們只能保證相對每個(gè)PG而言，映射至該P(yáng)G的所有對象，其哈希值低n-1位都是相同的。改進(jìn)后的映射方法稱為stable_mod，其邏輯如下：if((hash&(2

n

–1))<pg_num)

return(hash&(2

n

–1));

else

return(hash&(2

n-1

-1));

仍然以pg_num等于12為例，可以驗(yàn)證：如果采用stable_mod方式，在保證結(jié)果相等的前提下，如下輸入的低n-1=3位都是相同的。0x05stable_mod12=5

0x0Dstable_mod12=5

0x15stable_mod12=5

0x1Dstable_mod12=5

…

綜上，無論pg_num是否為2的整數(shù)次冪，采用stable_mod都可以產(chǎn)生一個(gè)相對有規(guī)律的對象到PG的映射結(jié)果，這是PG分裂的一個(gè)重要理論基礎(chǔ)。1.5PG分裂與集群擴(kuò)容為了節(jié)省成本，初期規(guī)劃的Ceph集群容量一般而言都會(huì)偏保守，無法應(yīng)對隨著時(shí)間推移而呈爆炸式增長的數(shù)據(jù)存儲需求，因此集群擴(kuò)容成為一種常見操作。對Ceph而言，需要關(guān)注的一個(gè)問題是擴(kuò)容前后負(fù)載在所有OSD之間的重新均衡，即如何能讓新加入的OSD立即參與負(fù)荷分擔(dān)，從而實(shí)現(xiàn)集群性能與規(guī)模呈線性擴(kuò)展這一優(yōu)雅特性。通常情況下，這是通過PG自動(dòng)遷移和重平衡來實(shí)現(xiàn)的。然而遺憾的是，存儲池中的PG數(shù)量并不會(huì)隨著集群規(guī)模增大而自動(dòng)增加，這在某些場景下往往會(huì)導(dǎo)致潛在的性能瓶頸。為此，Ceph提供了一種手動(dòng)增加存儲池中PG數(shù)量的機(jī)制。當(dāng)存儲池中的PG數(shù)增加后，新的PG會(huì)被隨機(jī)、均勻地映射至歸屬于該存儲池的所有OSD之上。又由圖1-3可知，執(zhí)行對象至PG的映射時(shí)，此時(shí)作為stable_mod輸入之一的pg_num已經(jīng)發(fā)生了變化，所以會(huì)出現(xiàn)某些對象也被隨之映射至新PG的現(xiàn)象。因而需要搶在客戶端訪問之前，將這部分對象轉(zhuǎn)移至新創(chuàng)建的PG之中。顯然，為了避免造成長時(shí)間的業(yè)務(wù)停頓，我們應(yīng)該盡可能減少對象移動(dòng)。為此我們需要先研究對象在PG之間分布的特點(diǎn)，以便以最高效的方式產(chǎn)生新的PG和轉(zhuǎn)移對象。假定某個(gè)存儲池老的pg_num為24，新的pg_num為26，以存儲池中某個(gè)老PG（假定其PGID=Y.X，其中X=0bX3X2X1X0）為例，容易驗(yàn)證其中所有對象的哈希值都可以分成如圖1-6所示的4種類型（按前面的分析，分裂前后，對象哈希值中只有低6位有效，圖中只展示這6位）。圖1-64種類型對象哈希值依次針對這4種類型的對象PG（Y.X）使用新的pg_num（24->26）再次執(zhí)行stable_mod，結(jié)果如表1-2所示。表1-2使用新的pg_num重新執(zhí)行stable_mod的結(jié)果可見，由于存儲池的pg_num發(fā)生了變化，僅有第1種類型（X5X4=00）的對象使用stable_mod方法仍然能夠映射至老的PG之上，其他3種類型的對象則并無實(shí)際PG對應(yīng)。為此，我們需要?jiǎng)?chuàng)建3個(gè)新的PG來分別轉(zhuǎn)移部分來自老PG中的對象。參考表1-2，容易驗(yàn)證這3個(gè)新的PG在存儲池中的編號可以通過(m×16)+X(m=1，2，3)得到，同時(shí)由于（概率上）每種類型的對象數(shù)量相等，因此完成對象轉(zhuǎn)移之后每個(gè)PG承載的數(shù)據(jù)仍然可以保持均衡。針對所有老的PG重復(fù)上述過程，最終可以將存儲池中的PG數(shù)量調(diào)整為原來的4倍。又因?yàn)樵谡{(diào)整PG數(shù)量的過程中，我們總是基于老PG（稱為祖先PG）產(chǎn)生新的孩子PG，并且新的孩子PG中最初的對象全部來源于老PG，所以這個(gè)過程被形象地稱為PG分裂。在FileStore的實(shí)現(xiàn)中，由于PG對應(yīng)一個(gè)文件目錄，其下的對象全部使用文件保存，所以出于索引效率和PG分裂考慮，F(xiàn)ileStore對目錄下的文件進(jìn)行分層管理。采用stable_mod執(zhí)行對象至PG的映射后，由于歸屬于同一個(gè)PG的所有對象，總是可以保證它們的哈希值至少低n-1位是相同的，所以一個(gè)自然的想法是使用對象哈希值逆序之后作為目錄分層的依據(jù)。例如，假定某個(gè)對象的32位哈希值為0xA4CEE0D2，則其可能的一個(gè)目錄層次為./2/D/0/E/E/C/4/A/0xA4CEE0D2，這樣我們最終可以得到一個(gè)符合常規(guī)的、樹形的目錄結(jié)構(gòu)。仍然假定某個(gè)PG歸屬的存儲池分裂之前共有256個(gè)PG（此時(shí)n=8，對應(yīng)的掩碼為28-1=255），PG對應(yīng)的PGID為Y.D2，則某個(gè)時(shí)刻其一個(gè)可能的目錄結(jié)構(gòu)如下：.

└──2

└──D

├──0

│├──0x324140D2

│└──0x78AF30D2

├──1

│└──0x9898A1D2

├──2

│├──0x1578A2D2

│└──0x787AE2D2

├──3

│├──0x789713D2

│└──0x8976E3D2

├──4

│└──0x123174D2

├──5

│└──0xAA3CE5D2

├──6

│├──0x6873F6D2

│└──0xFABE36D2

├──7

│└──0xA675F7D2

├──8

│├──0x9786A8D2

│└──0x990028D2

├──9

│└──0x787329D2

├──A

│└──0x67812AD2

├──B

│└──0x7760FBD2

├──C

│└──0x798ADCD2

├──D

│└──0x787ABDD2

├──E

│├──0x014ACED2

│└──0x123EEED2

└──F

├──0x018BCFD2

└──0xBCC34FD2

如果分裂為4096個(gè)PG（此時(shí)n=12，對應(yīng)的掩碼為212-1=4095），則原來每個(gè)PG對應(yīng)分裂成16個(gè)PG。仍以PGID為Y.D2的PG為例，通過簡單計(jì)算可以得到這15個(gè)新增PG的PGID分別為：Y.1D2

Y.2D2

…

Y.ED2

Y.FD2

可見這些新的PG對應(yīng)的對象分別存儲于老PG的如下目錄之下。./2/D/1/

./2/D/2/

…

./2/D/E/

./2/D/F/

此時(shí)可以不用移動(dòng)對象（即文件），而是直接修改文件夾的歸屬，即可完成對象在新老PG之間的遷移。引入PG分裂機(jī)制之后，如果仍然直接使用PGID作為CRUSH輸入，據(jù)此計(jì)算新增孩子PG在OSD之間的映射結(jié)果，由于此時(shí)每個(gè)PG的PGID都不相同，必然觸發(fā)大量新增孩子PG在OSD之間遷移?？紤]到分裂之前PG在OSD之間的分布已經(jīng)趨于均衡，更好的辦法是讓同一個(gè)祖先誕生的所有孩子PG與其保持相同的副本分布，這樣當(dāng)分裂完成之后，整個(gè)集群的PG分布仍然是均衡的。為此，每個(gè)存儲池除了記錄當(dāng)前的PG數(shù)量之外，為了應(yīng)對PG分裂，還需要額外記錄分裂之前祖先PG的數(shù)量，后者稱為PGP（PlacementGroupPlacement）數(shù)量（pgp_num）。最終，利用CRUSH執(zhí)行PG映射時(shí)，我們不是直接使用PGID，而是轉(zhuǎn)而使用其在存儲池內(nèi)的唯一編號先針對pgp_num執(zhí)行stable_mod，再與存儲池標(biāo)識一起哈希之后作為CRUSH的特征輸入，即可保證每個(gè)孩子PG與其祖先產(chǎn)生相同的CRUSH計(jì)算結(jié)果（因?yàn)榇藭r(shí)祖先和孩子PG產(chǎn)生的CRUSH特征輸入都相同），進(jìn)而保證兩者產(chǎn)生相同的副本分布。Luminous將默認(rèn)的本地對象存儲引擎切換為BlueStore，此時(shí)同一個(gè)OSD下所有對象都共享一個(gè)扁平尋址空間，所以PG分裂時(shí)，甚至不存在上述對象在（新老）文件夾之間轉(zhuǎn)移的過程，因而更加高效。1.6總結(jié)和展望作為Ceph的服務(wù)端，RADOS集群負(fù)責(zé)提供可信賴、可擴(kuò)展和高性能的分布式對象存儲服務(wù)。串行化和安全性解耦的設(shè)計(jì)理念使得RADOS可在客戶端對故障零感知的情況下仍然提供強(qiáng)一致性語義?；诜植际礁呖煽繖C(jī)制構(gòu)建的小型Monitor集群負(fù)責(zé)維護(hù)集群表的權(quán)威副本（mastercopy）。進(jìn)一步地，通過集群表傳播CRUSH，RADOS保證所有OSD和應(yīng)用程序客戶端都能清楚地了解集群當(dāng)前的數(shù)據(jù)分布形態(tài)。一方面，這使得RADOS免受類似傳統(tǒng)存儲需要通過查表才能準(zhǔn)確定位某個(gè)具體對象的困擾；另一方面，也使得RADOS能夠在線處理諸如數(shù)據(jù)復(fù)制、一致性管理、故障恢復(fù)等復(fù)雜任務(wù)，同時(shí)仍然對外提供強(qiáng)一致性的讀寫服務(wù)。上述一切，再加上精心設(shè)計(jì)的、可擴(kuò)展的故障檢測機(jī)制和“漣漪式”集群表傳播機(jī)制，使得在生產(chǎn)環(huán)境中構(gòu)建超大規(guī)模的RADOS集群成為可能。如前所述，當(dāng)集群存儲規(guī)模上升至PB級別或者以上，其拓?fù)浣Y(jié)構(gòu)必然是異構(gòu)的。同時(shí)，由于集群中存在成千上萬個(gè)本地存儲設(shè)備，故障必然成為常態(tài)。以PG為粒度、高度并行的數(shù)據(jù)恢復(fù)機(jī)制使得RADOS無論是從短暫性的掉電，還是永久性的硬件損壞之中恢復(fù)都異常迅速和高效，從而大大降低了數(shù)據(jù)丟失風(fēng)險(xiǎn)?！奥仿湫捱h(yuǎn)兮，吾將上下而求索。”新的征程已在前方展開，接下來，讓我們首先接觸一下Ceph兩大核心設(shè)計(jì)之一的CRUSH，領(lǐng)略計(jì)算尋址之美。第2章

計(jì)算尋址之美與數(shù)據(jù)平衡之殤——CRUSH大部分存儲系統(tǒng)將數(shù)據(jù)寫入后端存儲設(shè)備之后，很少會(huì)在設(shè)備之間再次移動(dòng)數(shù)據(jù)。這就存在一個(gè)潛在問題：即使一個(gè)數(shù)據(jù)分布已經(jīng)趨于完美均衡的系統(tǒng)，隨著時(shí)間推移，新的空閑設(shè)備不斷加入，老的故障設(shè)備不斷退出，數(shù)據(jù)也會(huì)重新變得不均衡。這種情況在大型分布式存儲系統(tǒng)中尤為常見。一種可行的解決方案是將數(shù)據(jù)以足夠小的粒度打散，然后完全隨機(jī)地分布至所有存儲設(shè)備。這樣，從概率上而言，如果系統(tǒng)運(yùn)行的時(shí)間足夠長，所有設(shè)備的空間使用率將會(huì)趨于均衡。當(dāng)新設(shè)備加入后，數(shù)據(jù)會(huì)隨機(jī)地從不同的老設(shè)備遷移過來；當(dāng)老設(shè)備因?yàn)楣收贤顺龊?，其原有?shù)據(jù)會(huì)隨機(jī)遷出至其他正常設(shè)備。整個(gè)系統(tǒng)一直處于動(dòng)態(tài)平衡之中，從而能夠適應(yīng)任何類型的負(fù)載和拓?fù)浣Y(jié)構(gòu)變化。進(jìn)一步地，由于任何數(shù)據(jù)（可以是文件、塊設(shè)備等）都被打散成多個(gè)碎片，然后寫入不同的底層存儲設(shè)備，從而使得在大型分布式存儲系統(tǒng)中獲得盡可能高的I/O并發(fā)和匯聚帶寬成為可能。一般而言，使用哈希函數(shù)可以達(dá)到上述目的。但是在實(shí)際應(yīng)用中還需要解決兩個(gè)問題：一是如果系統(tǒng)中存儲設(shè)備數(shù)量發(fā)生變化，如何最小化數(shù)據(jù)遷移量，從而使得系統(tǒng)盡快恢復(fù)平衡；二是在大型（PB級及以上）分布式存儲系統(tǒng)中，數(shù)據(jù)一般包含多個(gè)備份，如何合理地分布這些備份，從而盡可能地使得數(shù)據(jù)具有較高的可靠性。因此，需要對普通哈希函數(shù)加以擴(kuò)展，使之能夠解決上述問題，Ceph稱之為CRUSH。顧名思義，CRUSH是一種基于哈希的數(shù)據(jù)分布算法。以數(shù)據(jù)唯一標(biāo)識符、集群當(dāng)前的拓?fù)浣Y(jié)構(gòu)以及數(shù)據(jù)備份策略作為CRUSH輸入，可以隨時(shí)隨地通過計(jì)算獲取數(shù)據(jù)所在的底層存儲設(shè)備（例如磁盤）位置并直接與其通信，從而避免查表操作，實(shí)現(xiàn)去中心化和高度并發(fā)。CRUSH同時(shí)支持多種數(shù)據(jù)備份策略，例如鏡像、RAID及其衍生的糾刪碼等，并受控地將數(shù)據(jù)的多個(gè)備份映射到集群不同故障域中的底層存儲設(shè)備之上，從而保證數(shù)據(jù)可靠性。上述特點(diǎn)使得CRUSH特別適用于對可擴(kuò)展性、性能以及可靠性都有極高要求的大型分布式存儲系統(tǒng)。本章按照如下思路組織：首先，介紹CRUSH需要解決的問題，由此引出CRUSH最重要的基本選擇算法——straw及其改進(jìn)版本straw2；其次，完成基本算法分析后，介紹如何將其進(jìn)一步拓展至具有復(fù)雜拓?fù)浣Y(jié)構(gòu)的真實(shí)集群，為了實(shí)現(xiàn)上述目標(biāo)，首先介紹集群拓?fù)浣Y(jié)構(gòu)和數(shù)據(jù)分布規(guī)則的具體描述形式，然后以此為基礎(chǔ)介紹CRUSH的完整實(shí)現(xiàn)；再次，生產(chǎn)環(huán)境中集群拓?fù)浣Y(jié)構(gòu)千變?nèi)f化，CRUSH配置相對復(fù)雜，我們結(jié)合一些實(shí)際案例，分析如何針對CRUSH進(jìn)行深度定制，以滿足形式各異的數(shù)據(jù)分布需求；最后，由于CRUSH在執(zhí)行多副本映射時(shí)存在一些缺陷，如果集群規(guī)模較小或者異構(gòu)化，容易出現(xiàn)數(shù)據(jù)分布不均衡的問題，為此，我們針對一些可行的解決方案進(jìn)行了探討。2.1抽簽算法Ceph在設(shè)計(jì)之初被定位成用于管理大型分級存儲網(wǎng)絡(luò)的分布式文件系統(tǒng)。網(wǎng)絡(luò)中的不同層級具有不同的故障容忍程度，因此也稱為故障域。圖2-1展示了一個(gè)具有3個(gè)層級（機(jī)架、主機(jī)、磁盤）的Ceph集群。圖2-1具有3個(gè)層級的Ceph集群在圖2-1中，單個(gè)主機(jī)包含多個(gè)磁盤，每個(gè)機(jī)架包含多個(gè)主機(jī)，并采用獨(dú)立的供電和網(wǎng)絡(luò)交換系統(tǒng)，從而可以將整個(gè)集群以機(jī)架為單位劃分為若干故障域。為了實(shí)現(xiàn)高可靠性，實(shí)際上要求數(shù)據(jù)的多個(gè)副本分布在不同機(jī)架的主機(jī)磁盤之上。因此，CRUSH首先應(yīng)該是一種基于層級的深度優(yōu)先遍歷算法。此外，上述層級結(jié)構(gòu)中，每個(gè)層級的結(jié)構(gòu)特征也存在差異，一般而言，越處于頂層的其結(jié)構(gòu)變化的可能性越小，反之越處于底層的則其結(jié)構(gòu)變化越頻繁。例如，大多數(shù)情況下一個(gè)Ceph集群自始至終只對應(yīng)一個(gè)數(shù)據(jù)中心，但是主機(jī)或者磁盤數(shù)量隨時(shí)間流逝則可能一直處于變化之中。因此，從這個(gè)角度而言，CRUSH還應(yīng)該允許針對不同的層級按照其特點(diǎn)設(shè)置不同的選擇算法，從而實(shí)現(xiàn)全局和動(dòng)態(tài)最優(yōu)。在CRUSH的最初實(shí)現(xiàn)中，Sage一共設(shè)計(jì)了4種不同的基本選擇算法，這些算法是實(shí)現(xiàn)其他更復(fù)雜算法的基礎(chǔ)，它們各自的優(yōu)缺點(diǎn)如表2-1所示。表2-1CRUSH基本選擇算法對比由表2-1可見，unique算法執(zhí)行效率最高，但是抵御結(jié)構(gòu)變化的能力最差；straw算法執(zhí)行效率較低，但是抵御結(jié)構(gòu)變化的能力最好；list和tree算法執(zhí)行效率和抵御結(jié)構(gòu)變化的能力介于unique與straw之間。如果綜合考慮呈爆炸式增長的存儲空間需求（導(dǎo)致需要添加元素）、在大型分布式存儲系統(tǒng)中某些部件故障是常態(tài)（導(dǎo)致需要?jiǎng)h除元素），以及愈發(fā)嚴(yán)苛的數(shù)據(jù)可靠性需求（導(dǎo)致需要將數(shù)據(jù)副本存儲在更高級別的故障域中，例如不同的數(shù)據(jù)中心），那么針對任何層級采用straw算法都是一個(gè)不錯(cuò)的選擇。事實(shí)上，這也是CRUSH算法的現(xiàn)狀，在大多數(shù)將Ceph用于生產(chǎn)環(huán)境的案例中，除了straw算法之外，其他3種算法基本上形同虛設(shè)，因此我們將重點(diǎn)放在分析straw算法上。顧名思義，straw算法將所有元素比作吸管，針對指定輸入，為每個(gè)元素隨機(jī)地計(jì)算一個(gè)長度，最后從中選擇長度最長的那個(gè)元素（吸管）作為輸出。這個(gè)過程被形象地稱為抽簽（draw），元素的長度稱為簽長。顯然straw算法的關(guān)鍵在于如何計(jì)算簽長。理論上，如果所有元素構(gòu)成完全一致，那么只需要將指定輸入和元素自身唯一編號作為哈希輸入即可計(jì)算出對應(yīng)元素的簽長。因此，如果樣本容量足夠大，那么最終所有元素被選擇的概率都是相等的，從而保證數(shù)據(jù)在不同元素之間均勻分布。然而實(shí)際上，前期規(guī)劃得再好的集群，其包含的存儲設(shè)備隨著時(shí)間的推移也會(huì)逐漸趨于異構(gòu)化，例如，由于批次不同而導(dǎo)致的磁盤容量差異。顯然，通常情況下，我們不應(yīng)該對所有設(shè)備一視同仁，而是需要在CRUSH算法中引入一個(gè)額外的參數(shù)，稱為權(quán)重，來體現(xiàn)設(shè)備之間的差異，讓權(quán)重大（對應(yīng)容量大）的設(shè)備分擔(dān)更多的數(shù)據(jù)，權(quán)重?。▽?yīng)容量小）的設(shè)備分擔(dān)更少的數(shù)據(jù)，從而使得數(shù)據(jù)在異構(gòu)存儲網(wǎng)絡(luò)中也能合理地分布。將上述理論應(yīng)用于straw算法，則可以通過使用權(quán)重對簽長的計(jì)算過程進(jìn)行調(diào)整來實(shí)現(xiàn)，即我們總是傾向于讓權(quán)重大的元素有較大的概率獲得更大的簽長，從而在每次抽簽中更容易勝出。因此，引入權(quán)重之后straw算法的執(zhí)行結(jié)果將取決于3個(gè)因素：固定輸入、元素編號和元素權(quán)重。這其中，元素編號起的是隨機(jī)種子的作用，所以針對固定輸入，straw算法實(shí)際上只受元素權(quán)重的影響。進(jìn)一步地，如果每個(gè)元素的簽長只與自身權(quán)重相關(guān)，則可以證明此時(shí)straw算法對于添加元素和刪除元素的處理都是最優(yōu)的。我們以添加元素為例進(jìn)行論證。1）假定當(dāng)前集合中一共包含n個(gè)元素：(e1，e2，…，en)2）向集合中添加新元素en+1：(e1，e2，…，en，en+1)3）針對任意輸入x，加入en+1之前，分別計(jì)算每個(gè)元素簽長并假定其中最大值為dmax：(d1，d2，…，dn)4）因?yàn)樾略豦n+1的簽長計(jì)算只與自身編號及自身權(quán)重相關(guān)，所以可以使用x獨(dú)立計(jì)算其簽長（同時(shí)其他元素的簽長不受en+1加入的影響），假定為dn+1；5）又因?yàn)閟traw算法總是選擇最大的簽長作為最終結(jié)果，所以：如果dn+1>dmax，那么x將被重新映射至新元素en+1；反之，對x的已有映射結(jié)果無任何影響?？梢?，添加一個(gè)元素，straw算法會(huì)隨機(jī)地將一些原有元素中的數(shù)據(jù)重新映射至新加入的元素之中。同理，刪除一個(gè)元素，straw算法會(huì)將該元素中全部數(shù)據(jù)隨機(jī)地重新映射至其他元素之中。因此無論添加或者刪除元素，都不會(huì)導(dǎo)致數(shù)據(jù)在除被添加或者刪除之外的兩個(gè)元素（即不相干的元素）之間進(jìn)行遷移。理論上straw算法是非常完美的，然而在straw算法實(shí)現(xiàn)整整8年之后，由于Ceph應(yīng)用日益廣泛，不斷有用戶向社區(qū)反饋，每次集群有新的OSD加入或者舊的OSD刪除時(shí)，總會(huì)觸發(fā)不相干的數(shù)據(jù)遷移，這迫使Sage對straw算法重新進(jìn)行審視。原straw算法偽代碼如下：max_x=-1

max_item=-1

foreachitem:

x=hash(input,r)

x=x*item_straw

ifx>max_x:

max_x=x

max_item=item

returnmax_item

可見，算法執(zhí)行的結(jié)果取決于每個(gè)元素根據(jù)輸入（input）、隨機(jī)因子（r）和item_straw計(jì)算得到的簽長，而item_straw通過權(quán)重計(jì)算得到，偽代碼如下：reverse=rearrangeallweightsinreverseorder

straw=-1

weight_diff_prev_total=0

foreachitem:

item_straw=straw*0x10000

weight_diff_prev=(reverse[current_item]–reverse[prev_item])*items_remain

weight_diff_prev_total+=weight_diff_prev

weight_diff_next=(reverse[next_item]–reverse[current_item])*items_remain

scale=weight_diff_prev_total/(weight_diff_prev_total+weight_diff_next)

straw*=pow(1/scale,1/items_remain)

原straw算法中，將所有元素按其權(quán)重進(jìn)行逆序排列后逐個(gè)計(jì)算每個(gè)元素的item_straw，計(jì)算過程中不斷累積當(dāng)前元素與前后元素的權(quán)重差值，以此作為計(jì)算下一個(gè)元素item_straw的基準(zhǔn)。因此straw算法的最終結(jié)果不但取決于每個(gè)元素的自身權(quán)重，而且也與集合中所有其他元素的權(quán)重強(qiáng)相關(guān)，從而導(dǎo)致每次有元素加入集合或者被從集合中刪除時(shí)，都會(huì)引起不相干的數(shù)據(jù)遷移。出于兼容性考慮，Sage重新設(shè)計(jì)了一種針對原有straw算法進(jìn)行修正的新算法，稱為straw2。straw2計(jì)算每個(gè)元素的簽長時(shí)僅使用自身權(quán)重，因此可以完美反映Sage的初衷（也因此避免了不相干的數(shù)據(jù)遷移），同時(shí)計(jì)算也更加簡單。其偽代碼如下：max_x=-1

max_item=-1

foreachitem:

x=hash(input,r)

x=ln(x/65536)/weight

ifx>max_x:

max_x=x

max_item=item

returnmax_item

分析straw2的偽代碼可知，針對輸入和隨機(jī)因子執(zhí)行哈希后，結(jié)果落在[0，65535]之間，因此x/65536必然小于1，對其取自然對數(shù)（ln(x/65536)）后結(jié)果為負(fù)值。進(jìn)一步地，將其除以自身權(quán)重（weight）后，權(quán)重越大，結(jié)果越大（因?yàn)樨?fù)得越少），從而體現(xiàn)出我們所期望的每個(gè)元素權(quán)重對于抽簽結(jié)果的正反饋?zhàn)饔谩?.2CRUSH算法詳解CRUSH基于上述基本選擇算法完成數(shù)據(jù)映射，這個(gè)過程是受控的并且高度依賴于集群的拓?fù)涿枋觥猚lustermap。不同的數(shù)據(jù)分布策略通過制定不同的placementrule來實(shí)現(xiàn)。placementrule實(shí)際上是一組包括最大副本數(shù)、故障（容災(zāi)）級別等在內(nèi)的自定義約束條件，例如針對圖2-1所示的集群，我們可以通過一條placementrule將互為鏡像的3個(gè)數(shù)據(jù)副本（這也是Ceph的默認(rèn)數(shù)據(jù)備份策略）分別寫入位于不同機(jī)架的主機(jī)磁盤之上，以避免因?yàn)槟硞€(gè)機(jī)架掉電而導(dǎo)致業(yè)務(wù)中斷。針對指定輸入x，CRUSH將輸出一個(gè)包含n個(gè)不同目標(biāo)存儲對象（例如磁盤）的集合。CRUSH的計(jì)算過程中僅僅使用x、clustermap和placementrule作為哈希函數(shù)輸入，因此如果clustermap不發(fā)生變化（一般而言placementrule不會(huì)輕易變化），那么結(jié)果就是確定的；同時(shí)由于使用的哈希函數(shù)是偽隨機(jī)的，所以CRUSH選擇每個(gè)目標(biāo)存儲對象的概率相對獨(dú)立（然而我們在后面將會(huì)看到，受控的副本策略改變了這種獨(dú)立性），從而可以保證數(shù)據(jù)在整個(gè)集群之間均勻分布。2.2.1集群的層級化描述——clustermapclustermap是Ceph集群拓?fù)浣Y(jié)構(gòu)的邏輯描述形式?？紤]到生產(chǎn)環(huán)境中集群通常具有形如“數(shù)據(jù)中心→機(jī)架→主機(jī)→磁盤”（參考圖2-1）這樣的層級拓?fù)?，所以clustermap使用樹這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)：每個(gè)葉子節(jié)點(diǎn)都是真實(shí)的最小物理存儲設(shè)備（例如磁盤），稱為device；所有中間節(jié)點(diǎn)統(tǒng)稱為bucket，每個(gè)bucket可以是一些devices的集合，也可以是低一級的buckets集合；根節(jié)點(diǎn)稱為root，是整個(gè)集群的入口。每個(gè)節(jié)點(diǎn)綁定一種類型，表示其在集群中所處的層級，也可以作為故障域，除此之外還包含一個(gè)集群唯一的數(shù)字標(biāo)識。根節(jié)點(diǎn)與中間節(jié)點(diǎn)的數(shù)字標(biāo)識都是負(fù)值，只有葉子節(jié)點(diǎn)，也就是device才擁有非負(fù)的數(shù)字標(biāo)識，表明其是承載數(shù)據(jù)的真實(shí)設(shè)備。節(jié)點(diǎn)的權(quán)重屬性用于對CRUSH的選擇過程進(jìn)行調(diào)整，使得數(shù)據(jù)分布更加合理。父節(jié)點(diǎn)權(quán)重是其所有孩子節(jié)點(diǎn)的權(quán)重之和。表2-2列舉了clustermap中一些常見的節(jié)點(diǎn)（層級）類型。表2-2clustermap常見的節(jié)點(diǎn)類型需要注意的是，這里并非強(qiáng)調(diào)每個(gè)Ceph集群都一定要?jiǎng)澐譃槿绫?-2所示的11個(gè)層級，并且每種層級類型的名稱必須固定不變，而是層級可以根據(jù)實(shí)際情況進(jìn)行裁剪，名稱也可以按照自身習(xí)慣進(jìn)行修改。假定所有磁盤規(guī)格一致（這樣每個(gè)磁盤的權(quán)重一致），我們可以繪制圖2-1所示集群的clustermap，如圖2-2所示。圖2-2圖2-1所示集群的clustermap描述實(shí)現(xiàn)上，類似圖2-2中這種樹狀的層級關(guān)系在clustermap中可以通過一張二維映射表建立。<bucket,items>

樹中每個(gè)節(jié)點(diǎn)都是一個(gè)bucket（device也被抽象成為一種bucket類型），每個(gè)bucket都只保存自身所有直接孩子的編號。當(dāng)bucket類型為device（對應(yīng)圖2-2中的osd）時(shí)，容易知道，此時(shí)其對應(yīng)的items列表為空，表明bucket實(shí)際上是葉子節(jié)點(diǎn)。2.2.2數(shù)據(jù)分布策略——placementrule使用clustermap建立對應(yīng)集群的拓?fù)浣Y(jié)構(gòu)描述之后，可以定義placementrule來完成數(shù)據(jù)映射。每條placementrule可以包含多個(gè)操作，這些操作有以下3種類型。1）take：從clustermap選擇指定編號的bucket（即某個(gè)特定bucket），并以此作為后續(xù)步驟的輸入。例如，系統(tǒng)默認(rèn)的placementrule總是以clustermap中的root節(jié)點(diǎn)作為輸入開始執(zhí)行的。2）select：從輸入的bucket中隨機(jī)選擇指定類型和數(shù)量的條目（items）。Ceph當(dāng)前支持兩種備份策略，多副本和糾刪碼，相應(yīng)的有兩種select算法，firstn和indep。實(shí)現(xiàn)上兩者都是采用深度優(yōu)先遍歷算法，并無顯著不同，主要區(qū)別在于糾刪碼要求結(jié)果是有序的，因此，如果無法得到滿足指定數(shù)量（例如4）的輸出，那么firstn會(huì)返回形如[1，2，4]這樣的結(jié)果，而indep會(huì)返回形如[1，2，CRUSH_ITEM_NONE，4]這樣的結(jié)果，即indep總是返回要求數(shù)量的條目，如果對應(yīng)的條目不存在（即選不出來），則使用空穴進(jìn)行填充。select執(zhí)行過程中，如果選中的條目故障、過載或者與其他之前已經(jīng)被選中的條目沖突，都會(huì)觸發(fā)select重新執(zhí)行，因此需要指定最大嘗試次數(shù)，防止select陷入死循環(huán)。3）emit：輸出選擇結(jié)果。可見，placementrule中真正起決定性作用的是select操作。為了簡化placementrule配置，select操作也支持故障域模式。以firstn為例，如果為故障域模式，那么firstn將返回指定數(shù)量的葉子設(shè)備，并保證這些葉子設(shè)備位于不同的、指定類型的故障域之下。因此，在故障域模式下，一條最簡單的placementrule可以只包含如下3個(gè)操作：take(root)

select(replicas,type)

emit(void)

上述select操作中的type為想要設(shè)置的故障域類型，例如設(shè)置為rack，則select將保證選出的所有副本都位于不同機(jī)架的主機(jī)磁盤之上；也可以設(shè)置為host，那么select只保證選出的所有副本都位于不同主機(jī)的磁盤之上。圖2-3以firstn為例，展示了select從指定的bucket當(dāng)中查找指定數(shù)量條目的過程。圖2-3中幾個(gè)關(guān)鍵處理步驟補(bǔ)充說明如下：1）如何從bucket下選擇一個(gè)條目（item）？構(gòu)建集群的clustermap時(shí)，通過分析每種類型的bucket特點(diǎn)，可以為其指定一種合適的選擇算法（例如straw2），用于從對應(yīng)的bucket中選擇一個(gè)條目。因此從bucket選擇條目的過程實(shí)際上就是執(zhí)行設(shè)定的選擇算法。這個(gè)選擇算法的執(zhí)行結(jié)果取決于兩個(gè)因素：一是輸入對象的特征標(biāo)識符x，二是隨機(jī)因子r（r實(shí)際上是哈希函數(shù)的種子）。因?yàn)閤固定不變，所以如果選擇失敗，那么在后續(xù)重試的過程中需要對r進(jìn)行調(diào)整，以盡可能輸出不同的結(jié)果。目前r由待選擇的副本編號和當(dāng)前的嘗試次數(shù)共同決定。為了防止陷入死循環(huán)，需要對選擇每個(gè)副本過程中的嘗試次數(shù)進(jìn)行限制，這個(gè)限制稱為全局嘗試次數(shù)（choose_total_tries）；同時(shí)由于在故障域模式下會(huì)產(chǎn)生遞歸調(diào)用，所以還需要限制產(chǎn)生遞歸調(diào)用時(shí)作為下一級輸入的全局嘗試次數(shù)。由于這個(gè)限制會(huì)導(dǎo)致遞歸調(diào)用時(shí)的全局嘗試次數(shù)成倍增長，實(shí)現(xiàn)上采用一個(gè)布爾變量（chooseleaf_descend_once）進(jìn)行控制，如果為真，則在產(chǎn)生遞歸調(diào)用時(shí)下一級被調(diào)用者至多重試一次，反之則下一級被調(diào)用者不進(jìn)行重試，由調(diào)用者自身重試。為了降低沖突概率（如前，每次盡量使用不同的隨機(jī)因子r可以減少?zèng)_突概率），也可以使用當(dāng)前的重試次數(shù)（或者其2N-1倍，這里的N由chooseleaf_vary_r參數(shù)決定）對遞歸調(diào)用時(shí)的隨機(jī)因子r再次進(jìn)行調(diào)整，這樣產(chǎn)生遞歸調(diào)用時(shí)，其初始隨機(jī)因子r將取決于待選擇的副本編號和調(diào)用者傳入的隨機(jī)因子（稱為parent_r）。圖2-3基于firstn的select執(zhí)行過程值得一提的是，Jewel版本之前，故障域模式下作為遞歸調(diào)用時(shí)所使用的副本編號是固定的，例如調(diào)用者當(dāng)前正在選擇第2個(gè)副本，那么執(zhí)行遞歸調(diào)用時(shí)的起始副本編號也將是2。按照上面的分析，副本編號會(huì)作為輸入?yún)?shù)之一對遞歸調(diào)用時(shí)的初始隨機(jī)因子r產(chǎn)生影響，有的用戶反饋，這在OSD失效時(shí)會(huì)觸發(fā)不必要的數(shù)據(jù)（PG）遷移，因此在Jewel版本之后，故障域模式下會(huì)對遞歸調(diào)用的起始副本獨(dú)立編號（這個(gè)操作受chooseleaf_stable控制），以進(jìn)一步降低兩次調(diào)用之間的相關(guān)性。由于選擇的過程是執(zhí)行深度優(yōu)先遍歷，在老的CRUSH實(shí)現(xiàn)中，如果對應(yīng)集群的層次較多，并且在中間某個(gè)層次的bucket下由于沖突而選擇條目失敗，那么可以在當(dāng)前的bucket下直接進(jìn)行重試，而不用每次回歸到初始輸入的bucket之下重新開始重試，這樣可以稍微提升算法的執(zhí)行效率，此時(shí)同樣需要對這個(gè)局部重試過程中的重試次數(shù)進(jìn)行限制，稱為局部重試次數(shù)（choose_local_retries）。此外，由于進(jìn)入這種模式的直接原因是bucket自帶選擇算法沖突概率較高（即使用不同的r作為輸入反復(fù)選中同一個(gè)條目），所以針對這種模式還設(shè)計(jì)了一種后備選擇算法。這種后備選擇算法的基本原理是：將對應(yīng)bucket下的所有條目進(jìn)行隨機(jī)重排，只要輸入x不變，那么隨著r變化，算法會(huì)不停地記錄前面已經(jīng)被選擇過的條目，并從本次選擇的候選條目中排除，從而能夠有效地降低沖突概率，保證最終能夠成功選中一個(gè)不再?zèng)_突的條目。切換至后備選擇算法需要沖突次數(shù)達(dá)到某個(gè)閾值，其主要由當(dāng)前bucket的規(guī)模決定（原實(shí)現(xiàn)中要求沖突次數(shù)至少大于當(dāng)前bucket下條目數(shù)的一半）。當(dāng)然切換至后備選擇算法時(shí)，也可以再次限制啟用后備選擇算法進(jìn)行重試的次數(shù)（choose_local_fallback_retries）。上述過程因?yàn)閷φ麄€(gè)CRUSH的執(zhí)行過程進(jìn)行了大量人工干預(yù)從而嚴(yán)重?fù)p傷了CRUSH的偽隨機(jī)性（即公平性），所以會(huì)導(dǎo)致嚴(yán)重的數(shù)據(jù)均衡問題，因此在Ceph的第一個(gè)正式發(fā)行版Argonaut之后即被廢棄，不再建議啟用。表2-3匯總了如上分析的、所有影響CRUSH執(zhí)行的可調(diào)參數(shù)（表中的默認(rèn)值和最優(yōu)值針對Jewel版本而言）。表2-3CRUSH可調(diào)參數(shù)2）沖突沖突指選中的條目已經(jīng)存在于輸出條目列表之中。3）OSD過載（或失效）雖然哈希以及由哈希派生出來的CRUSH算法從理論上能夠保證數(shù)據(jù)在所有磁盤之間均勻分布，但是實(shí)際上，以下因素：·集群規(guī)模較小，集群整體容量有限，導(dǎo)致集群PG總數(shù)有限，亦即CRUSH輸入的樣本容量不夠?！RUSH本身的缺陷。CRUSH的基本選擇算法中，以straw2為例，每次選擇都是計(jì)算單個(gè)條目被選中的獨(dú)立概率，但是CRUSH所要求的副本策略使得針對同一個(gè)輸入、多個(gè)副本之間的選擇變成了計(jì)算條件概率（我們需要保證副本位于不同故障域中的OSD之上），所以從原理上CRUSH就無法處理好多副本模式下的副本均勻分布問題。都會(huì)導(dǎo)致在真實(shí)的Ceph集群、特別是異構(gòu)集群中，出現(xiàn)大量磁盤數(shù)據(jù)分布懸殊（這里指每個(gè)磁盤已用空間所占的百分比）的情況，因此需要對CRUSH計(jì)算結(jié)果進(jìn)行人工調(diào)整。這個(gè)調(diào)整同樣是基于權(quán)重進(jìn)行的，即針對每個(gè)葉子設(shè)備（OSD），除了由其基于容量計(jì)算得來的真實(shí)權(quán)重（weight）之外，Ceph還為其設(shè)置了一個(gè)額外的權(quán)重，稱為reweight。算法正常選中一個(gè)OSD后，最后還將基于此reweight對該OSD進(jìn)行一次過載測試，如果測試失敗，則仍將拒絕選擇該條目，這個(gè)過程如圖2-4所示。圖2-4過載測試由圖2-4可見，對應(yīng)OSD的reweight調(diào)整得越高，那么通過測試的概率越高（例如手動(dòng)設(shè)置某個(gè)OSD的reweight為0x10000，那么通過測試的概率是100%），反之則通過測試的概率越低。因此實(shí)際應(yīng)用中，通過降低過載OSD或者（和）增加低負(fù)載OSD的reweight，都可以觸發(fā)數(shù)據(jù)在OSD之間重新分布，從而使得數(shù)據(jù)分布更加合理。引入過載測試的另一個(gè)好處在于可以對OSD暫時(shí)失效和OSD被永久刪除的場景進(jìn)行區(qū)分。區(qū)分這兩者的意義在于：如果OSD暫時(shí)失效（例如對應(yīng)的磁盤被拔出超過一定時(shí)間，Ceph會(huì)將其設(shè)置為out），可以通過將其reweight調(diào)整為0，從而利用過載測試將其從候選條目中淘汰，進(jìn)而將其承載的數(shù)據(jù)遷移至其他OSD，這樣后續(xù)該OSD正常回歸時(shí)，將其reweight重新調(diào)整為0x10000即可將原來歸屬于該OSD的數(shù)據(jù)再次遷回，而遷回過程中只需要同步該OSD離線期間產(chǎn)生的新數(shù)據(jù)即可，亦即只需要進(jìn)行增量同步；相反，如果是刪除OSD，此時(shí)會(huì)同步將其從對應(yīng)的bucket條目中刪除，這樣即便該OSD后續(xù)被重新添加回集群，由于其在clustermap中的唯一編號可能已經(jīng)發(fā)生了變化，所以也可能承載與之前完全不同的數(shù)據(jù)。初始時(shí)，Ceph將每個(gè)OSD的reweight都設(shè)置為0x10000，因此上述過載測試對CRUSH的最終選擇結(jié)果不會(huì)產(chǎn)生任何影響。2.3調(diào)制CRUSH按照Ceph的設(shè)計(jì)，任何涉及客戶端進(jìn)行對象尋址的場景都需要基于CRUSH進(jìn)行計(jì)算，所以提升CRUSH的計(jì)算效率具有重要意義。調(diào)制CRUSH即針對表2-3中的參數(shù)進(jìn)行調(diào)整，使得CRUSH正常工作的同時(shí)花費(fèi)盡可能小的計(jì)算代價(jià)，以提升性能。需要注意的是，為了使得調(diào)整后的參數(shù)正常生效，需要保證客戶端與RADOS集群的Ceph版本嚴(yán)格一致。調(diào)制CRUSH最簡單的辦法是使用現(xiàn)成的、預(yù)先經(jīng)過驗(yàn)證的模板（profile），命令如下：cephosdcrushtunables{profile}

一些系統(tǒng)已經(jīng)預(yù)先定義好的模板（截至Luminous版本）如表2-4所示。表2-4系統(tǒng)自定義的CRUSH可調(diào)參數(shù)模板當(dāng)然在一些特定的場景（例如集群比較大同時(shí)每個(gè)主機(jī)中的磁盤數(shù)量都比較少）中，可能使用上述模板仍然無法使得CRUSH正常工作，那么就需要手動(dòng)進(jìn)行參數(shù)調(diào)整。2.3.1編輯CRUSHmap為了方便將CRUSH的計(jì)算過程作為一個(gè)相對獨(dú)立的整體進(jìn)行管理（因?yàn)閮?nèi)核客戶端也需要用到），Ceph將集群的clustermap和所有的placementrule合并成一張CRUSHmap，因此基于CRUSHmap可以獨(dú)立實(shí)施數(shù)據(jù)備份及分布策略。一般而言，通過CLI（Command-LineInterface，命令行接口）即可方便地在線修改CRUSH的各項(xiàng)配置。當(dāng)然也可以通過直接編輯CRUSHmap實(shí)現(xiàn)，步驟如下：（1）獲取CRUSHmap大部分情況下集群創(chuàng)建成功后，對應(yīng)的CRUSHmap已經(jīng)由系統(tǒng)自動(dòng)生成，可以通過如下命令獲?。篶ephosdgetcrushmap-o{compiled-crushmap-filename}

上述命令將輸出集群的CRUSHmap至指定文件。當(dāng)然出于測試或者其他目的，也可以手動(dòng)創(chuàng)建CRUSHmap，命令如下：crushtool-o{compiled-crushmap-filename}--build--num_osdsNlayer1...

其中，--num_osds{N}layer1...將N個(gè)OSD從0開始編號，然后在指定的層級之間平均分布，每個(gè)層級（layer）需要采用形如<name，algorithm，size>（其中size指每種類型的bucket下包含條目的個(gè)數(shù)）的三元組進(jìn)行描述，并按照從低（靠近葉子節(jié)點(diǎn)）到高（靠近根節(jié)點(diǎn)）的順序進(jìn)行排列。例如，可以用如下命令生成圖2-2所示集群的CRUSHmap（osd->host->rack->root）：crushtool-omycrushmap--build--num_osds27hoststraw23rackstraw23\

rootuniform0

需要注意的是，上述兩種方式輸出的CRUSHmap都是經(jīng)過編譯的，需要經(jīng)過反編譯之后才能以文本的方式被編輯。（2）反編譯CRUSHmap執(zhí)行命令：crushtool-d{compiled-crushmap-filename}-o{decompiled-crushmap-filename}

即可將步驟（1）中輸出的CRUSHmap轉(zhuǎn)化為可直接編輯的文本形式。例如：crushtool-dmycrushmap-omycrushmap.txt

（3）編輯CRUSHmap得到反編譯后的CRUSHmap之后，可以直接以文本形式打開和編輯。例如可以直接修改表2-3中的所有可調(diào)參數(shù)：vimycrushmap.txt

#begincrushmap

tunablechoose_local_tries0

tunablechoose_local_fallback_tries0

tunablechoose_total_tries50

tunablechooseleaf_descend_once1

tunablechooseleaf_vary_r1

tunablestraw_calc_version1

也可以修改placementrule：vimycrushmap.txt

#rules

rulereplicated_ruleset{

ruleset0

typereplicated

min_size1

max_size10

steptakeroot

stepchooseleaffirstn0typehost

stepemit

}

上述placementrule中各個(gè)選項(xiàng)含義如表2-5所示。表2-5CRUSHmap中ruleset相關(guān)選項(xiàng)及其具體含義因此上述placementrule表示“采用多副本數(shù)據(jù)備份策略，副本必須位于不同主機(jī)的磁盤之上”。（4）編譯CRUSHmap以文本形式編輯過的CRUSHmap，相應(yīng)地需要經(jīng)過編譯，才能被Ceph識別。執(zhí)行如下命令：crushtool-c{decompiled-crush-map-filename}-o{compiled-crush-map-filename}

（5）模擬測試在新的CRUSHmap生效之前，可以先進(jìn)行模擬測試，以驗(yàn)證對應(yīng)的修改是否符合預(yù)期。例如，可以使用如下命令打印輸入范圍為[0，9]、副本數(shù)為3、采用編號為0的ruleset的映射結(jié)果：crushtool-imycrushmap--test--min-x0--max-x9--num-rep3--ruleset0\

--show_mappings

CRUSHrule0x0[19,11,3]

CRUSHrule0x1[15,7,21]

CRUSHrule0x2[26,5,14]

CRUSHrule0x3[8,25,13]

CRUSHrule0x4[5,13,21]

CRUSHrule0x5[7,25,16]

CRUSHrule0x6[17,25,8]

CRUSHrule0x7[13,4,25]

CRUSHrule0x8[18,5,15]

CRUSHrule0x9[26,3,16]

也可以僅統(tǒng)計(jì)結(jié)果分布概況（這里輸入變?yōu)閇0，100000]）：crushtool-imycrushmap--test--min-x0--max-x100000--num-rep3\

--ruleset0--show_utilization

rule0(replicated_ruleset),x=0..100000,numrep=3..3

rule0(replicated_ruleset)num_rep3resultsize==3:100001/100001

device0:stored:11243expected:11111.2

device1:stored:11064expected:11111.2

device2:stored:11270expected:11111.2

device3:stored:11154expected:11111.2

device4:stored:11050expected:11111.2

device5:stored:11211expected:11111.2

device6:stored:10848expected:11111.2

device7:stored:10958expected:11111.2

device8:stored:11203expected:11111.2

device9:st