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

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

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

0x4979FC12mod256=18

0x4979FD12mod256=18

…

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

0x0Cmod12=0

0x18mod12=0

0x24mod12=0

…

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

n-1

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

n

–1))<pg_num)

return(hash&(2

n

–1));

else

return(hash&(2

n-1

-1));

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

0x0Dstable_mod12=5

0x15stable_mod12=5

0x1Dstable_mod12=5

…

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

└──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個PG（此時n=12，對應的掩碼為212-1=4095），則原來每個PG對應分裂成16個PG。仍以PGID為Y.D2的PG為例，通過簡單計算可以得到這15個新增PG的PGID分別為：Y.1D2

Y.2D2

…

Y.ED2

Y.FD2

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

./2/D/2/

…

./2/D/E/

./2/D/F/

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

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

可見，算法執行的結果取決于每個元素根據輸入（input）、隨機因子（r）和item_straw計算得到的簽長，而item_straw通過權重計算得到，偽代碼如下：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算法中，將所有元素按其權重進行逆序排列后逐個計算每個元素的item_straw，計算過程中不斷累積當前元素與前后元素的權重差值，以此作為計算下一個元素item_straw的基準。因此straw算法的最終結果不但取決于每個元素的自身權重，而且也與集合中所有其他元素的權重強相關，從而導致每次有元素加入集合或者被從集合中刪除時，都會引起不相干的數據遷移。出于兼容性考慮，Sage重新設計了一種針對原有straw算法進行修正的新算法，稱為straw2。straw2計算每個元素的簽長時僅使用自身權重，因此可以完美反映Sage的初衷（也因此避免了不相干的數據遷移），同時計算也更加簡單。其偽代碼如下：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的偽代碼可知，針對輸入和隨機因子執行哈希后，結果落在[0，65535]之間，因此x/65536必然小于1，對其取自然對數（ln(x/65536)）后結果為負值。進一步地，將其除以自身權重（weight）后，權重越大，結果越大（因為負得越少），從而體現出我們所期望的每個元素權重對于抽簽結果的正反饋作用。2.2CRUSH算法詳解CRUSH基于上述基本選擇算法完成數據映射，這個過程是受控的并且高度依賴于集群的拓撲描述——clustermap。不同的數據分布策略通過制定不同的placementrule來實現。placementrule實際上是一組包括最大副本數、故障（容災）級別等在內的自定義約束條件，例如針對圖2-1所示的集群，我們可以通過一條placementrule將互為鏡像的3個數據副本（這也是Ceph的默認數據備份策略）分別寫入位于不同機架的主機磁盤之上，以避免因為某個機架掉電而導致業務中斷。針對指定輸入x，CRUSH將輸出一個包含n個不同目標存儲對象（例如磁盤）的集合。CRUSH的計算過程中僅僅使用x、clustermap和placementrule作為哈希函數輸入，因此如果clustermap不發生變化（一般而言placementrule不會輕易變化），那么結果就是確定的；同時由于使用的哈希函數是偽隨機的，所以CRUSH選擇每個目標存儲對象的概率相對獨立（然而我們在后面將會看到，受控的副本策略改變了這種獨立性），從而可以保證數據在整個集群之間均勻分布。2.2.1集群的層級化描述——clustermapclustermap是Ceph集群拓撲結構的邏輯描述形式。考慮到生產環境中集群通常具有形如“數據中心→機架→主機→磁盤”（參考圖2-1）這樣的層級拓撲，所以clustermap使用樹這種數據結構來實現：每個葉子節點都是真實的最小物理存儲設備（例如磁盤），稱為device；所有中間節點統稱為bucket，每個bucket可以是一些devices的集合，也可以是低一級的buckets集合；根節點稱為root，是整個集群的入口。每個節點綁定一種類型，表示其在集群中所處的層級，也可以作為故障域，除此之外還包含一個集群唯一的數字標識。根節點與中間節點的數字標識都是負值，只有葉子節點，也就是device才擁有非負的數字標識，表明其是承載數據的真實設備。節點的權重屬性用于對CRUSH的選擇過程進行調整，使得數據分布更加合理。父節點權重是其所有孩子節點的權重之和。表2-2列舉了clustermap中一些常見的節點（層級）類型。表2-2clustermap常見的節點類型需要注意的是，這里并非強調每個Ceph集群都一定要劃分為如表2-2所示的11個層級，并且每種層級類型的名稱必須固定不變，而是層級可以根據實際情況進行裁剪，名稱也可以按照自身習慣進行修改。假定所有磁盤規格一致（這樣每個磁盤的權重一致），我們可以繪制圖2-1所示集群的clustermap，如圖2-2所示。圖2-2圖2-1所示集群的clustermap描述實現上，類似圖2-2中這種樹狀的層級關系在clustermap中可以通過一張二維映射表建立。<bucket,items>

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

select(replicas,type)

emit(void)

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

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

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

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

rootuniform0

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

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

（3）編輯CRUSHmap得到反編譯后的CRUSHmap之后，可以直接以文本形式打開和編輯。例如可以直接修改表2-3中的所有可調參數：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中各個選項含義如表2-5所示。表2-5CRUSHmap中ruleset相關選項及其具體含義因此上述placementrule表示“采用多副本數據備份策略，副本必須位于不同主機的磁盤之上”。（4）編譯CRUSHmap以文本形式編輯過的CRUSHmap，相應地需要經過編譯，才能被Ceph識別。執行如下命令：crushtool-c{decompiled-crush-map-filename}-o{compiled-crush-map-filename}

（5）模擬測試在新的CRUSHmap生效之前，可以先進行模擬測試，以驗證對應的修改是否符合預期。例如，可以使用如下命令打印輸入范圍為[0，9]、副本數為3、采用編號為0的ruleset的映射結果：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]

也可以僅統計結果分布概況（這里輸入變為[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