這是一個技術(shù)創(chuàng)新的故事。

在現(xiàn)實業(yè)務(wù)的壓力和技術(shù)理想的感召下，帶著模糊的地圖，百度滄?！ご鎯?CFS 和 TafDB 兩個技術(shù)團隊啟程進入無人區(qū)，尋找解開「千億文件的情況下，文件存儲系統(tǒng)依然保持高性能」難題的鑰匙。

新架構(gòu)小試牛刀后帶來的驚喜還未持續(xù)多久，便被橫貫在面前的高山給阻擋，退回到起點還是繼續(xù)向前行……

如本文作者所言，對論文背后的故事進行講述，是為了能夠幫助讀者更好地理解這個創(chuàng)新結(jié)果本身，亦能為正在處于創(chuàng)新過程的讀者提供參考，愿大家早日找到那把鑰匙。

1. 引言

本文的主要目的是解讀百度滄?！ご鎯F隊發(fā)表于 EuroSys 2023 的論文《CFS: Scaling Metadata Service for Distributed File System via Pruned Scope of Critical Sections》，論文全文可以在 https://dl.acm.org/doi/10.1145/3552326.3587443 下載。

論文披露了百度智能云文件存儲 CFS 的元數(shù)據(jù)系統(tǒng)的核心設(shè)計，對?期困擾文件系統(tǒng)元數(shù)據(jù)領(lǐng)域的 POSIX 兼容性和高擴展性（特別是寫擴展性）難以兼顧的問題進行了解答。這是一個大規(guī)模分布式文件系統(tǒng)能否擴展到百億甚至千億級別文件數(shù)，同時保持高性能穩(wěn)定性的一個關(guān)鍵問題。

作為一種高度凝練的體裁，論文除了展示必要的分析過程，并不會告知讀者這些創(chuàng)新是如何被想到的。我們認為講清楚這次創(chuàng)新的整個過程，既有助于理解論文本身，也是對論文內(nèi)容的重要補充。基于這個考慮，我們將整篇文章按照以下結(jié)構(gòu)組織內(nèi)容:

• 首先，我們概括介紹了文件系統(tǒng)元數(shù)據(jù)問題產(chǎn)生的背景和業(yè)界對該問題的探索，并特別對本文著重解決的寫擴展性問題進行了定量分析；
• 然后，我們通過介紹 CFS 元數(shù)據(jù)架構(gòu)的演進歷史，向讀者展示了我們探索的過程以及對元數(shù)據(jù)問題本質(zhì)的思考，最終引出論文里介紹的系統(tǒng)架構(gòu)；
• 最后，我們詳細介紹了論文架構(gòu)的整體設(shè)計和其中關(guān)鍵的細節(jié)。

2. 背景

2.1. 文件系統(tǒng)的概念

文件系統(tǒng)的定義是一種采用樹形結(jié)構(gòu)存儲和組織計算機數(shù)據(jù)的方法，這個樹形結(jié)構(gòu)通常被稱為層級命名空間（Hierarchical Namespace）。如下圖所示，這種命名空間的特點是整個結(jié)構(gòu)像一棵倒掛的樹，非葉子結(jié)點只能是目錄。如果不考慮軟鏈接跟隨（follow symlinks）、硬鏈接（hardlink）的情況，從根節(jié)點（/）出發(fā)，每一個目錄項（目錄、文件、 軟鏈接等合法類型）都可以由一條唯一的路徑到達。

文件系統(tǒng)可以分為元數(shù)據(jù)（Metadata）和數(shù)據(jù)（Data）兩個部分。數(shù)據(jù)部分指的是一個文件具體存儲了哪些內(nèi)容，元數(shù)據(jù)部分是指層級命名空間樹形結(jié)構(gòu)本身。例如，如果我們要讀取 /a/b/file 這個文件的數(shù)據(jù)，元數(shù)據(jù)部分負責找到 /a/b/file 這個文件存儲在哪兒，數(shù)據(jù)部分則負責把文件的內(nèi)容讀出來。

文件系統(tǒng)主要有兩種 POSIX 和 HDFS 兩種實現(xiàn)?格:

• POSIX：全稱 Portable Operating System Interface，是 IEEE 制定的 UNIX 可移植操作系統(tǒng)兼容標準。該標準定義了一個文件系統(tǒng)相關(guān)的接口子集，是文件系統(tǒng)領(lǐng)域最基礎(chǔ)和權(quán)威的標準。POSIX 兼容文件系統(tǒng)就是指兼容該標準的文件系統(tǒng)；
• HDFS：源自 Hadoop 大數(shù)據(jù)生態(tài)，對 POSIX 標準做了一些比較實用的簡化和修改，主要是放棄了對 hardlink、隨機寫的支持，并增加了一些實用的遞歸操作。通常也將其歸類為 POSIX-like 文件系統(tǒng)，意思是和 POSIX 相似。

POSIX 和 HDFS ?格的文件系統(tǒng)不存在明顯的分界線，在實現(xiàn)技術(shù)上是互通的，實際使用時通過簡單的接口轉(zhuǎn)換也可以互現(xiàn)替換，當然這種轉(zhuǎn)換會以犧牲一定的兼容性為前提。論文描述的系統(tǒng)是 POSIX ?格的，但研究成果同樣適用于 HDFS ?格的系統(tǒng)，甚至文章里用于對比的 HopsFS 和 InifiniFS 均是 HDFS ?格的系統(tǒng)。

2.2. 文件系統(tǒng)元數(shù)據(jù)問題的抽象

在探索元數(shù)據(jù)問題的過程中，我們逐步建立了文件系統(tǒng)元數(shù)據(jù)問題的抽象，在此處先進行介紹，以方便展開后續(xù)的內(nèi)容。一個文件系統(tǒng)的元數(shù)據(jù)系統(tǒng)只要正確實現(xiàn)了這個抽象，就解決了 POSIX 兼容性問題的核心部分。

這個抽象是說，一個標準的 POSIX 文件系統(tǒng)層級命名空間要求實現(xiàn)以下語義：

• 寫操作的要求

關(guān)聯(lián)變更：所有操作均需要實現(xiàn)關(guān)聯(lián)變更（編號 1），即增刪目錄下的子項的同時更新父目錄必要的屬性信息。關(guān)聯(lián)變更需要原子完成，即 all-or-nothing，要么全部都發(fā)生變化，要么全部都不發(fā)生變化；

rename: rename 的作用是對目錄項進行重命名，這是整個文件系統(tǒng)里最復雜的操作，除了滿足關(guān)聯(lián)變更的要求外，還有很多其它復雜的要求，請自行參閱 POSIX 標準的定義。

• 讀操作的要求

• 點讀：包括路徑查找（lookup，編號 2）和 inode 獲取屬性（getattr，編號 3）兩種：

• 路徑查找：用于一級一級找到對應目錄項，單個 lookup 路徑查找操作的輸入是父目錄 inode + 子項的名稱，返回值是目錄項的 inode。inode 是一個文件系統(tǒng)中唯一標記一個目錄項的編號，通常是一個 64 位整數(shù)；

• 獲取屬性：獲取指定 inode 的屬性信息，屬性信息包括 size、nlinks、 ctime、mtime 等。

• 范圍讀：目錄遍歷（readdir，編號 4），獲取一個目錄下所有子項的列表，通過一系列的 readdir 調(diào)用，每次返回一部分子項，直到獲取到完全部子項。

對于上述的抽象，我們進一步做如下補充說明：

• 關(guān)聯(lián)變更的本質(zhì)是準確反映子項列表的變化

一方面，關(guān)系到元數(shù)據(jù)的一致性。例如，刪除目錄的時候需要判斷目錄是否非空，這在很多系統(tǒng)里會維護一個字段來記錄，如果這個字段的信息滯后了，就有誤判的可能性。當一個非空目錄被誤判為空目錄，目錄本身會被刪除，目錄下的子項殘留了下來。這些殘留的子項是所謂的孤兒節(jié)點，無法通過路徑查找訪問到；

另外一方面，關(guān)系到緩存的正確性和效率。為了優(yōu)化文件系統(tǒng)元數(shù)據(jù)的性能，客戶端通常會緩存 lookup 和 readdir 操作的結(jié)果，然后再次訪問的時候可以通過獲取父目錄的屬性信息，快速判斷父目錄是否被修改，從而確認緩存是否有效。如果沒有這個機制，操作要么無條件重新執(zhí)行保證數(shù)據(jù)正確，要么容忍可能存在的信息滯后。這個緩存機制對大目錄的 readdir 效果尤其重要，可以節(jié)省重復執(zhí)行大目錄的 readdir 帶來的大量 I/O 開銷。

• 讀操作隱含的兩種索引需求

• <父目錄 inode, 子項名稱> 索引：這個索引需要支持點讀和范圍讀，分別對應 lookup 和 readdir。需要特別說明的是，POSIX 對 readdir 并沒有規(guī)定需要按照字母序返回結(jié)果，只需要實現(xiàn)不重復、不遺漏返回即可，這種情況下范圍讀中的 “子項名稱” 參數(shù)可以是某種系統(tǒng)內(nèi)部的游標（marker）；

• <inode> 索引：這個索引只需要支持點讀，對應 getattr 請求獲取屬性信息。

2.3. 分布式文件系統(tǒng)的元數(shù)據(jù)服務(wù)

二十多年前，隨著 GFS、HDFS 等分布式文件系統(tǒng)的興起，元數(shù)據(jù)和數(shù)據(jù)分離的架構(gòu)逐漸成為分布式文件系統(tǒng)領(lǐng)域的主流共識。這種架構(gòu)將整個系統(tǒng)分成負責元數(shù)據(jù)的元數(shù)據(jù)服務(wù)（Metadata Service）和負責數(shù)據(jù)的數(shù)據(jù)服務(wù)（Data Service）兩個部分。

對于數(shù)據(jù)服務(wù)，由于不同文件的數(shù)據(jù)相互獨立，同一文件的不同部分也很容易條帶化和分塊處理，天然具備并行處理的條件，因此較容易擴展到很大的規(guī)模。但對于元數(shù)據(jù)服務(wù)，層級命名空間的目錄結(jié)構(gòu)帶來了很強的父子依賴關(guān)系，并行處理并不是件容易的事情。

我們通常通過以下指標來綜合衡量一個元數(shù)據(jù)服務(wù)實現(xiàn)的優(yōu)劣：

• 擴展性：衡量一個實現(xiàn)可以擴展到多大的規(guī)模，實際上可以細分為兩個指標：

規(guī)模擴展性：指的是系統(tǒng)可以存儲多少目錄項，數(shù)億、百億，還是千億。因為文件占比是最高的，通常也將這個指標稱為系統(tǒng)支持的文件數(shù)；

性能擴展性：通過增加節(jié)點，系統(tǒng)的元數(shù)據(jù)讀寫 OPS 能夠分別擴展到什么量級，以及讀寫 OPS 和節(jié)點規(guī)模是否呈現(xiàn)線性關(guān)系。

• 延時：衡量單個請求需要花費多?時間才能完成處理；
• 均衡性：衡量系統(tǒng)是否有能力疏散熱點，讓不同節(jié)點的處理壓力大致均衡。

針對擴展性和均衡性，需要特別指出的是，盡管很多實現(xiàn)認為自己具備非常好的擴展性，但是根據(jù)木桶原理，擴展性的短板是由表現(xiàn)最差的那個節(jié)點決定的。因此，如果一個系統(tǒng)的均衡性沒做好，擴展性的實際表現(xiàn)不會特別好。

元數(shù)據(jù)服務(wù)的架構(gòu)發(fā)展在業(yè)界經(jīng)歷了三個階段：

階段一：單點元數(shù)據(jù)架構(gòu)

早期分布式文件系統(tǒng)存儲的單個文件都比較大，文件數(shù)量不會超過數(shù)億，單點的元數(shù)據(jù)服務(wù)完全可以滿足需求。GFS、HDFS 等系統(tǒng)是這個階段的代表。

這個單點只是邏輯上的，物理上元數(shù)據(jù)服務(wù)仍然會有多個備節(jié)點，在故障時候自動切換以保證服務(wù)連續(xù)性。這個階段的系統(tǒng)很明顯沒有擴展性和均衡性可言，但是延時性能是比較好的。

階段二：（耦合式）分布式元數(shù)據(jù)架構(gòu)

隨著 AI 等新型負載的流行，現(xiàn)代文件系統(tǒng)里存儲的文件越來越小，文件數(shù)量數(shù)卻越來越多。單個文件系統(tǒng)的文件大小可能只有數(shù)十 KB，文件數(shù)卻高達數(shù)十億。單點架構(gòu)的極限是存儲和處理數(shù)億文件，已經(jīng)不能適應時代的需求，因此，可擴展的多節(jié)點分布式元數(shù)據(jù)服務(wù)成為必選項。HDFS Federation、Lustre DNE1/DNE2、CephFS、BeeGFS 等系統(tǒng)都是這一階段發(fā)展起來的。

這個階段的分布式元數(shù)據(jù)服務(wù)是在單點架構(gòu)上的橫向擴展，每個節(jié)點同時負責數(shù)據(jù)存儲和文件系統(tǒng)語義的處理。為了和后來的分離式架構(gòu)做區(qū)分，本文將這種架構(gòu)稱為耦合式架構(gòu)。

耦合式架構(gòu)系統(tǒng)普遍采用子樹分片或 Hash 分片的方式來將整個層級命名空間分布到不同的節(jié)點上，能夠大致均勻地在數(shù)據(jù)量上打散元數(shù)據(jù)，但是元數(shù)據(jù)在創(chuàng)建時就確定了其物理位置，不能動態(tài)負載均衡，無法很好的解決數(shù)據(jù)熱點問題。

盡管有很多研究提出了各種負載動態(tài)均衡的方案，某些開源系統(tǒng)代碼上也支持該能力，但并沒有實際落地生產(chǎn)的案例。歸根到底，是因為元數(shù)據(jù)架構(gòu)同時耦合了數(shù)據(jù)存儲和處理邏輯，動態(tài)遷移的過程既要完成數(shù)據(jù)的搬遷，又要保證處理過程不中斷或者中斷時間極短（數(shù)秒鐘），工程實現(xiàn)的難度極大。

當一個操作需要多個節(jié)點參與時，如何保證元數(shù)據(jù)的一致性是一個比較難的問題，實現(xiàn)上要么需要引入復雜容易出錯的多節(jié)點參與的分布式鎖機制（Lustre DNE2、 BeeGFS、CephFS），要么放松對 POSIX 或 HDFS 語義的完整支持（HDFS Federation）。前者在沖突時開銷較大使得系統(tǒng)的寫擴展性存在瓶頸（后文會有定量分析），后者需要業(yè)務(wù)改造以感知底層的數(shù)據(jù)分布。

引入分布式鎖的目的是為了正確實現(xiàn)關(guān)聯(lián)變更。關(guān)聯(lián)變更里最核心的一個要求就是原子性。當需要變更的數(shù)據(jù)分散在多個節(jié)點時，分布式鎖可以保證變更同時生效或者同時不生效。當然，實現(xiàn)一個能正確容忍各種異常的分布式鎖機制也是一個有一定難度的技術(shù)活兒，由于和本文關(guān)系不大不再展開。

綜合來說，這個階段的系統(tǒng)一定程度上解決了規(guī)模擴展性的問題，能夠存儲幾十億文件，延時指標在請求不跨節(jié)點的時候是比較好的，但是寫擴展性和均衡性表現(xiàn)不是很好。

階段三:分離式元數(shù)據(jù)架構(gòu)

計算機領(lǐng)域有一條經(jīng)典的方法論:

Any problem in computer science can be solved by another layer of indirection. 

計算機科學領(lǐng)域的任何問題都可以通過增加一個間接的中間層來解決。

這個方法論具體的做法是將復雜系統(tǒng)進行分層，每一層次專注于解決一個領(lǐng)域的問題做到極致，最后疊加不同層次實現(xiàn)完整的功能。這在計算機領(lǐng)域是屢試不爽的套路。經(jīng)典的 OSI 7 層網(wǎng)絡(luò)模型，近年來在大數(shù)據(jù)和數(shù)據(jù)庫領(lǐng)域流行的存儲計算分離架構(gòu)，都是最好的佐證。

2017 年，HopsFS、ADLS 兩個工作將類似的想法引入到分布式文件系統(tǒng)元數(shù)據(jù)領(lǐng)域，在這之后出現(xiàn)的重要系統(tǒng)和研究工作幾乎都是基于此思路的。該思路將元數(shù)據(jù)服務(wù)從架構(gòu)上分成兩層：

• 數(shù)據(jù)庫層：這一層負責數(shù)據(jù)存儲，通常采用 NewSQL 或分布式 KV 系統(tǒng)（以下統(tǒng)稱 Table 系統(tǒng)），實現(xiàn)數(shù)據(jù)的持久化的同時提供分布式事務(wù)能力；
• 元數(shù)據(jù)代理層：這一層對外提供 POSIX 或 HDFS 接口，對內(nèi)將層級命名空間的數(shù)據(jù)轉(zhuǎn)換成 Table 系統(tǒng)中的記錄，處理時利用事務(wù)保證操作的正確性。

分層思路讓整個系統(tǒng)的設(shè)計變得非常簡潔。原來耦合式架構(gòu)里同一個節(jié)點既負責數(shù)據(jù)存儲還負責文件語義，兩者揉雜在一起剪不斷理還亂。分層之后，數(shù)據(jù)存儲的部分首先被從元數(shù)據(jù)節(jié)點里剝離了出去，元數(shù)據(jù)節(jié)點只剩下處理邏輯，變得更專注。

Table 系統(tǒng)提供的 SQL 或者 KV 接口易用性和通用性非常好，和存儲交互的邏輯表達起來也很容易。最重要的是，Table 系統(tǒng)提供了事務(wù)。事務(wù)是計算機領(lǐng)域最強大和最有用的能力之一，ACID 配合合適的隔離級別，（幾乎）所有的復雜的一致性問題都可以基于這個能力來簡潔地解決，文件系統(tǒng)語義要求的一致性當然也不例外。

除了架構(gòu)變得更簡潔外，分離式架構(gòu)借助 Table 系統(tǒng)諸多成熟的能力，還解決了之前架構(gòu)難以解決的規(guī)模擴展性和均衡性的問題：

• 規(guī)模擴展性：Table 系統(tǒng)具有非常好的規(guī)模擴展性，可以存儲海量的數(shù)據(jù)，例如，在對象存儲服務(wù)上，百度智能云的 TafDB 已經(jīng)存儲了萬億條數(shù)據(jù)，這個規(guī)模還在不斷增?。通過將文件系統(tǒng)元數(shù)據(jù)以合適的格式編碼存儲到這類系統(tǒng)中，可以滿足元數(shù)據(jù)服務(wù)對百億、千億文件的存儲需求；
• 均衡性：文件系統(tǒng)的元數(shù)據(jù)編碼到 Table 系統(tǒng)之后，維護層級關(guān)系變成了多條記錄同時變更時的原子性和一致性問題，這是事務(wù)可以保證的。剝離了文件系統(tǒng)語義之后， 數(shù)據(jù)本身并沒有特殊之處，Table 系統(tǒng)可以使用數(shù)據(jù)分片分裂、合并、均衡機制進行熱點的疏散，這些機制非常平凡和成熟，產(chǎn)生的服務(wù)中斷時間可以控制在秒級。

分離式架構(gòu)沒有在更早的時間點出現(xiàn)是有其歷史原因的。

事務(wù)?期只能在單機上良好運作，直到 2012 年 Spanner 橫空出世，才讓人們明白了怎么去組合利用 Paxos/Raft 這類分布式共識算法、Percolator 事務(wù)機制來構(gòu)建一個強大的分布式事務(wù)系統(tǒng)。這之后從 Spanner 衍生的各種開源或閉源的 Table 系統(tǒng)就雨后春筍般繁榮了起來，一定規(guī)模的技術(shù)公司都有能力研發(fā)這類系統(tǒng)。分離式元數(shù)據(jù)架構(gòu)出現(xiàn)的時間點，剛好吻合這類系統(tǒng)初步成熟并在各類場景開始落地的時間，幾乎是水到渠成。

遺憾的是，分離式架構(gòu)同樣沒有解決寫擴展性的問題，寫延時的表現(xiàn)甚至比耦合式架構(gòu)更差：

• 事務(wù)在架構(gòu)里的實質(zhì)作用其實也是一種分布式鎖，并沒有解決其它分布式鎖機制的缺陷，當一個寫操作需要多節(jié)點參與時，無論是吞吐還是延時的表現(xiàn)都會比較差；
• 分離式架構(gòu)處理請求時，需要先經(jīng)過元數(shù)據(jù)代理層，再到數(shù)據(jù)庫層，比耦合式架構(gòu)的處理路徑要更?，因此天然在性能上，特別是延時指標上更具劣勢。讀請求可以通過客戶端直接讀數(shù)據(jù)庫層的方法來進行優(yōu)化，但寫請求就沒有辦法這么處理了。

2.4. 為什么元數(shù)據(jù)服務(wù)需要分布式鎖

前文我們一直在強調(diào)通過分布式鎖來保證一致性，這個一致性就是指關(guān)聯(lián)變更的正確性。在這一章節(jié)，為了讓大家更好地理解這個問題，我們再補充說明一下分布式鎖是怎么實現(xiàn)這個保證的。以分離式架構(gòu)創(chuàng)建文件 create file "/A/f2" 為例，需要經(jīng)過以下步驟：

1. 創(chuàng)建操作發(fā)送到元數(shù)據(jù)代理；
2. 讀取 A 目錄的屬性并對 A 加鎖，在這一階段實際上還會去檢查目錄是否存在、用戶是否有權(quán)限創(chuàng)建等；
3. 插入 f2 文件的記錄；
4. 更新 A 目錄的屬性，主要是 mtime/ctime/links/size 等屬性。這個階段變更還沒有提交，客戶端不可?；
5. 解鎖并提交這次變更，這次提交如果涉及到多個元數(shù)據(jù)分片，需要采用 2PC 提交（two phase-commit）來保證變更同時生效；

操作 2 – 5 需要在鎖的保護下進行，如果沒有鎖的保護，會很容易出現(xiàn)并發(fā)問題。如下圖所示，系統(tǒng)使用 children 字段表示該目錄下有多少個有效的子目錄或文件，這個字段可以在刪除目錄的時候快速判斷目錄是否為空。當沒有鎖保護的時候，并發(fā)的操作 create file "/A/f2" 和 create file "/A/f3" 分別讀到 A.children=0，各自 +1 并更新，最后得到的 children 字段數(shù)據(jù)是錯誤的 1。

這個錯誤會導致后續(xù)刪除目錄操作誤判目錄為空，使一些文件成為孤兒節(jié)點。例如，在這個例子結(jié)束之后，用戶先執(zhí)行 delete file "/A/f2"，再執(zhí)行 delete directory "/A"，這時看到 children=0 認為目錄是空的，就可以把 A 目錄刪除掉了。此時，f3 文件還存在，但卻再也無法通過 /A/f3 路徑訪問到了!

實際系統(tǒng)的并發(fā)情況遠比上述的例子要復雜得多，但從上述的例子，我們可以簡單了解到為什么分布式文件系統(tǒng)的元數(shù)據(jù)操作需要分布式鎖來保護。

2.5. 對分布式鎖性能影響的定量分析

在回答了為什么元數(shù)據(jù)服務(wù)需要分布式鎖之后，我們在本章節(jié)進一步展示分布式鎖對寫性能的影響。這里直接引用論文里對 HopsFS 創(chuàng)建文件操作做的定量分析，分析結(jié)果同樣適用于其它系統(tǒng)。

在 Peak throughput 這個圖里，我們構(gòu)造了鎖沖突比例從 0% 到 100% 的負載，觀察系統(tǒng)的 OPS 和客戶端數(shù)量的關(guān)系。在沒有沖突的情況下（沖突比例 0%），OPS 幾乎隨著客戶端數(shù)量線性增?，但是當沖突比例越來越高時，OPS 有顯著的下降，當沖突比例達到 100% 時，整個曲線變得很平，說明系統(tǒng)的性能已經(jīng)完全喪失了擴展性。

在 Latency breakdown 這張圖里，我們進一步分解了 HopsFS 的執(zhí)行時間，可以發(fā)現(xiàn)，當沖突比例為 50% 和 100% 的時候，鎖沖突在整個操作中的占比高達 83.18% 和 93.86%。

上述的實驗表明，鎖沖突是影響系統(tǒng)擴展性和操作延時的關(guān)鍵。

另外，我們可以看到一個有意思的結(jié)果，那就是即使在無沖突的情況下，鎖在整個操作里的耗時占比也達到了 52.9%。這是因為系統(tǒng)并不知道何時會發(fā)生沖突，因此需要始終以最壞的情況來預防。如果能降低甚至消除這部分延時，就可以極大的降低系統(tǒng)的延時。事實上，無論是耦合式架構(gòu)，還是分離式架構(gòu)，很多系統(tǒng)都會通過一些數(shù)據(jù)的放置策略，讓一個子樹或者一個目錄的數(shù)據(jù)盡可能分布到一個分片上，以方便做鎖沖突的優(yōu)化。

3. CFS 元數(shù)據(jù)架構(gòu)的演進歷史

論文披露的 CFS 元數(shù)據(jù)架構(gòu)在內(nèi)部的代號是 Namespace 2.0，即第二代架構(gòu)。第二代架構(gòu)對第一代架構(gòu)存在明顯的繼承關(guān)系，正是因為我們分析清楚了第一代架構(gòu)的局限性，才使得第二代架構(gòu)的設(shè)計成為可能。

在正式介紹 Namespace 2.0 的架構(gòu)之前，讓我們先花一些時間講一講 CFS 元數(shù)據(jù)服務(wù)是怎么一步步演進到今天這個架構(gòu)的，這個對理解整篇論文是有幫助的。

3.1. Namespace 1.0: 分離式架構(gòu)上的微創(chuàng)新

當 2017 年我們開始設(shè)計 CFS 時，最重要的一個設(shè)計目標就是系統(tǒng)應該具備支撐海量文件的能力，這個海量的量級要遠超傳統(tǒng)系統(tǒng)的量級。云上的文件系統(tǒng)是多租戶的，租戶數(shù)量疊加單個租戶的規(guī)模，就會導致整個集群的文件數(shù)量爆炸式增?。例如，一個用戶 10 億文件，100 個租戶就是 1000 億文件。即使一開始的數(shù)據(jù)規(guī)模沒有那么大，但作為面向未來三五年甚至更久的設(shè)計，必須具備一定的前瞻性，為未來架構(gòu)上的擴展留足余地。

我們一開始就將單點架構(gòu)排除在外。面對大量的租戶，單點架構(gòu)會導致需要非常多的小集群，帶來巨大的運維復雜度。另外，隨著單個文件系統(tǒng)規(guī)模的擴大，單機的能力上限、熱點數(shù)據(jù)這些問題遲早會遇到。這些因素會導致單點架構(gòu)無法走很遠，那就不如在一開始就朝著真正的分布式的方向努力。

在調(diào)研的時候，我們注意到 HopsFS、ADLS 這兩篇論文的工作，經(jīng)過研判之后認為這兩個工作代表的分離式元數(shù)據(jù)架構(gòu)是未來整個領(lǐng)域的發(fā)展趨勢。當時我們已經(jīng)看到這個架構(gòu)在寫延時和寫擴展性方面的劣勢，但我們認為這不過是一朵烏云，汽?剛發(fā)明出來的時候還跑不過??呢，驅(qū)散這朵烏云不過是時間問題。

在百度智能云內(nèi)部，后來以 “滄海” 品牌命名的新一代存儲體系當時正在建設(shè)中。這套體系以 brpc + braft 為基石，通過組件化的方式實現(xiàn)各類易運維、高性能、超大規(guī)模的分布式存儲服務(wù)。這個體系的元數(shù)據(jù)底座 TafDB 是一個類 Spanner 的系統(tǒng)，幾乎和 CFS 同時啟動研發(fā)。

綜合這些因素，由 TafDB 提供海量數(shù)據(jù)存儲能力和分布式事務(wù)，CFS 自己實現(xiàn)文件語義層這條技術(shù)路線在原理上確定了下來。在 TafDB 就緒之前，CFS 基于 MySQL 開始前期的研發(fā)工作。

確定技術(shù)路線之后，我們針對 CFS 的目標業(yè)務(wù)場景，做了一些設(shè)計上的調(diào)整：

1）文件屬性分離

這個調(diào)整是說將文件屬性（file attributes）從元數(shù)據(jù)服務(wù)中剝離出來，和文件數(shù)據(jù)（file data）一起放到數(shù)據(jù)服務(wù)（Data Service）中進行處理。主要的考慮和性能有關(guān)系：

• 讀性能的考慮：在 2.2 章節(jié)我們指出，屬性部分只需要滿足 inode 索引的點讀即可，TafDB 作為一種全局有序的存儲系統(tǒng)，點讀的處理性能要比全局無序的數(shù)據(jù)服務(wù)要低；
• 寫性能的考慮：在修改文件數(shù)據(jù)的時候，POSIX 要求修改 ctime、mtime 等屬性，追加寫還伴隨著文件大?。╢ile size）的更新，這會在數(shù)據(jù)寫數(shù)據(jù)路徑上引入頻繁的元數(shù)據(jù)更新操作。類 Spanner 系統(tǒng)的寫 OPS 上限大約為百萬級別，不可能都消耗在文件數(shù)據(jù)修改操作上，因此，整個系統(tǒng)的寫性能將比這個數(shù)字更低，不能滿足業(yè)務(wù)的需求。

這個調(diào)整讓整個系統(tǒng)的文件屬性操作的擴展能力變得非常好，后來 Namespace 2.0 沿用了該設(shè)計。讀者可以在論文實驗部分可以找到對該設(shè)計收益的定量分析。

2）讀寫分離

另外一個調(diào)整是將元數(shù)據(jù)讀寫路徑做了分開處理。對于讀請求，我們繞過了元數(shù)據(jù)代理層直接訪問 TafDB，這樣可以縮短讀延時，同時少了元數(shù)據(jù)代理層的轉(zhuǎn)發(fā)開銷之后 OPS 也有一定提升。對于寫請求，則將每個文件系統(tǒng)（CFS 支持多租戶，一套系統(tǒng)中存在很多文件系統(tǒng)實例）的寫請求收斂到一個單點進行處理，這么做的原因詳述如下。

TafDB 提供的隔離級別是快照隔離級別（Snapshot Isolation），但文件系統(tǒng)場景實際需要串行化快照隔離級別（Serializable Snapshot Isolation）來避免孤兒節(jié)點問題。在下圖的例子中，rmdir "/a" 和 create "/a/b" 操作并發(fā)了，在操作開始后，他們讀到的是事務(wù)開始前的快照數(shù)據(jù)，同時看到 /a 目錄存在，然后都操作成功了，這就導致 b 成為一個不可達的孤兒節(jié)點。

通過在父目錄的記錄上制造寫沖突可以規(guī)避該問題，代價是讓事務(wù)的沖突變得更頻繁。我們前文對鎖的代價進行過定量分析，這在 TafDB 這種采用樂觀鎖模型的系統(tǒng)中代價更為高昂，因為這類系統(tǒng)判斷事務(wù)沖突是在提交前的最后一刻，在這之前因沖突回退的事務(wù)已經(jīng)完成了絕大部分的操作，包括多輪 RPC 和落盤開銷。

這些代價對于寫性能的影響極大，容易導致大量不可控的?尾甚至整個系統(tǒng)雪崩。這個問題在短期內(nèi)沒有特別好的解決思路。同時，根據(jù)公司內(nèi)的經(jīng)驗，單點架構(gòu)的寫性能如果優(yōu)化好可以達到 5 萬 OPS 左右，我們認為這個性能短期內(nèi)是夠用的。因此，我們決定將每個文件系統(tǒng)的寫請求收縮到一個單點進行處理，寫擴展性和寫延時的問題留到以后再去解決。

經(jīng)過上面的調(diào)整之后，Namespace 1.0 順利的完成了研發(fā)并落地，大概的架構(gòu)如下圖所示。在這個架構(gòu)里，所有文件相關(guān)的操作均由分布式的 FileStore 負責，其它的元數(shù)據(jù)讀操作直接由客戶端 ClientLib 發(fā)給 TafDB 處理，寫操作經(jīng)過 Namespace 進行處理，Namespace 是一個 Multi-Raft 的實現(xiàn)，每個 Raft 復制組負責一個文件系統(tǒng)。

CFS 元數(shù)據(jù)架構(gòu) Namespace 1.0

系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)如下圖所示。其中 TafDB 中的數(shù)據(jù)存儲在一張大表中，以 <parent_inode, name> 為 primary key，負責實現(xiàn) lookup 和 readdir，以 <inode> 為 secondary key，負責實現(xiàn)目錄的 getattr。

3.2. Namespace 1.X: 1.0 基礎(chǔ)上不太成功的探索

1.0 上線之后，CFS 順利承接了一些元數(shù)據(jù)讀性能要求較高的業(yè)務(wù)。以一個內(nèi)部業(yè)務(wù)為例，遷移到 CFS 之前采用了某開源解決方案，高峰期數(shù)十萬 getattr OPS 導致元數(shù)據(jù)節(jié)點 CPU 打滿，請求大量?尾甚至失敗，系統(tǒng)?雨飄搖，徘徊在崩潰的邊緣。CFS 很輕松地接下了該業(yè)務(wù)，整個過程波瀾不驚。后來我們分析這個案例，認為主要的收益來自文件屬性的分離，這個優(yōu)化使得文件的 getattr 直接由 FileStore 處理，將 getattr 打散得非常充分。

但是寫的性能始終是一個痛點，我們基于 1.0 的架構(gòu)做了大量的實驗和分析，嘗試提升單機的性能。在這個過程中比較成功的優(yōu)化包括:

• 處理流程精簡：我們分析了每一類寫請求的全流程，從內(nèi)核到 TafDB，將一些重復的條件檢查進行了精簡，將可以合并的操作進行了合并；
• 引入緩存：由于每個文件系統(tǒng)的元數(shù)據(jù)寫都是單點，Namespace 模塊任何時刻看到的數(shù)據(jù)都是最新的，具備引入緩存的條件，緩存命中情況下事務(wù)中的大部分讀請求都可以被優(yōu)化掉；
• 事務(wù)沖突預處理：在 TafDB 中出現(xiàn)事務(wù)沖突的代價比較大，我們將事務(wù)沖突的處理上提到 CFS 這一層，Namespace 模塊在執(zhí)行事務(wù)前分析其中存在的沖突點，按照每個沖突點進行排隊，從而讓下發(fā)到 TafDB 的請求無事務(wù)沖突。

通過這些優(yōu)化，我們讓寫延時和 OPS 分別提升了一倍多。但和單點架構(gòu)、耦合式架構(gòu)相比，這些優(yōu)化不能抵消處理路徑變?帶來的開銷，寫性能指標上仍然存在不小的差距。另外，如果我們想要將處理能力擴展到多個節(jié)點，原來所做的緩存、事務(wù)沖突預處理機制在一定程度上會失效，處理延時和單機 OPS 將再度惡化。

到 2019 年年中的時候，事情變得有點兒讓人絕望，我們失望的發(fā)現(xiàn)，在幾乎窮舉了所有可能和不可能的方案和思路后，擺在我們面前的似乎只有一條路線可走，即回到耦合式架構(gòu)，基于 TafDB 做二次開發(fā)，在盡可能保留 TafDB 的優(yōu)點的前提下實現(xiàn)文件系統(tǒng)語義。

我們曾經(jīng)篤信分離式架構(gòu)是未來發(fā)展的大趨勢，盡管存在一些顯而易?的問題，但汽?剛出來的時候也跑不過??，解決這些問題不過是遲早的事情。然而，至少在 POSIX 領(lǐng)域，看起來這輛新的汽?終究不是汽?，不過是更好一點兒的自行?。

3.3. Namespace 2.0: 柳暗花明又一村

不管我們怎么看好分離式架構(gòu)，現(xiàn)實的問題終歸還是要解決的。CFS 和 TafDB 兩個團隊決定最后坐下來一起再努力一把，要是不行就真散伙兒了。

在數(shù)學和物理史上，很多新的理論都是從拆除舊理論的基石開始的，典型的例子有非歐幾何、相對論。當然，和大師們相比，我們的工作微不足道，這里只是借用比喻一下 。

我們決定放下所有的先驗知識和成?，去尋找整個文件系統(tǒng)元數(shù)據(jù)大廈最底層的磚頭，從那些磚頭開始討論。

很快，我們發(fā)現(xiàn)現(xiàn)有的幾乎所有工作，都是從如何滿足 POSIX 標準的那一堆接口開始的，但這些接口本身也是有內(nèi)部結(jié)構(gòu)和邏輯的，還不是最底層的磚頭。

通過提煉 POSIX 接口背后的本質(zhì)要求，我們建立了 2.2 章節(jié)描述的抽象模型，并將每種操作用極其簡單的偽代碼寫了出來。

從這個抽象模型出發(fā)，我們推導出一組極其簡單的結(jié)論：

• 影響元數(shù)據(jù)服務(wù)擴展性的根源是更新父目錄屬性時產(chǎn)生的沖突，這是關(guān)聯(lián)變更的一部分；
• 這些變更本質(zhì)上只是一些數(shù)學運算，分為兩種。一種是加減運算，針對 links、 children、size 等屬性（如前文，children 不是標準屬性，是為了便于維護目錄下的子項數(shù)量），每次創(chuàng)建刪除子項都需要準確更新。另外一種賦值操作，針對 ctime、 atime、mtime 等屬性，每次創(chuàng)建刪除子項的時候用新值覆蓋掉舊值；
• 以上兩條對所有修改操作均成立，rename 的要求會更復雜的額外要求。

有一定編程經(jīng)驗的同學應該可以發(fā)現(xiàn)第二條的抽象要求可以用原子變量操作來表達！傳統(tǒng)的實現(xiàn)為了這幾個原子變量操作的正確性，將沖突范圍至少擴大到整個父目錄記錄，這是很不精細的做法，類似于給整個操作上了 mutex 鎖來保護臨界區(qū)（critical section）。

在編程上優(yōu)化這類的問題的路線，就是嘗試縮小臨界區(qū)范圍，采用開銷更小的保護方式來替代 mutex，如果能優(yōu)化到僅僅依賴原子變量操作就能保證正確性就最好了。這實際上就是我們接下來采用的優(yōu)化思路，論文標題對此有比較精準的概括。

計算機領(lǐng)域經(jīng)常會看到一些知識或經(jīng)驗逐漸變成大家的常識，但當時這些知識或經(jīng)驗產(chǎn)生的過程卻是經(jīng)過一些波折的。

我們總共花了一個季度來討論和設(shè)計 Namespace 2.0，上面這幾個關(guān)鍵點現(xiàn)在看來已經(jīng)成為我們的常識，但在當時耗費了我們一個多月的時間來推導。方案設(shè)計完成之后，接下來的工作異常順利。在已有系統(tǒng)的基礎(chǔ)上，我們又花了一個季度做了 demo 版本進行方案驗證和性能評估。demo 版本其實和后來的正式版本差別很小，這使得正式開發(fā)和測試的周期比較短，到 2020 年 Q1 末的時候 Namespace 2.0 就開始在線上小流量了。此后陸陸續(xù)續(xù)上線了一些優(yōu)化，但整體架構(gòu)直到現(xiàn)在都沒有大的變化。

4. 實現(xiàn)思路

Namepace 2.0 的指導思路是不斷縮小寫操作的臨界區(qū)范圍并最終實現(xiàn)無鎖化。上圖給了一個簡單的示意圖，在 Namespace 1.0 中通過鎖保護的關(guān)聯(lián)變更，在 Namespace 2.0 僅通過原子操作就滿足，并發(fā)的操作不再需要串行執(zhí)行。

為了實現(xiàn)這一點，我們采用了一系列技術(shù)的組合：

第一步，通過合適的數(shù)據(jù)布局，將沖突范圍縮小到單個分片

系統(tǒng)的首要目標是將 TafDB 的元數(shù)據(jù)請求的執(zhí)行范圍從跨分片降低到單個分片，這樣才可能讓去除分布式鎖成為可能，否則會有一致性問題，這個在背景部分我們已經(jīng)論證過。這個目標督促我們重新思考數(shù)據(jù)布局。

首先，Namespace 1.0 將文件屬性由文件存儲單獨負責的做法，已經(jīng)被驗證能夠提供更好的文件屬性操作性能，Namespace 2.0 繼續(xù)沿用此設(shè)計。

其次，我們觀察到，任何一個目錄項的元數(shù)據(jù)需要同時滿足兩類索引的需求，天然就是兩個部分，一部分用于 getattr，保存的是屬性信息，另外一部分用于 lookup 和 readdir，保存的是和父目錄有關(guān)的索引信息。后者是關(guān)聯(lián)變更的一部分，關(guān)聯(lián)變更的剩余部分和父目錄屬性有關(guān)系。通過調(diào)整數(shù)據(jù)布局，將整個關(guān)聯(lián)變更涉及的數(shù)據(jù)耦合到一個分片上，可以起到讓事務(wù)沖突聚焦到單個分片的效果。這個調(diào)整其實意味著 “屬性分開存儲” 這一規(guī)則擴展到了包括文件在內(nèi)的所有類型的目錄項。

最后，我們將原來事務(wù)保護的整個操作，拆解成兩個 TafDB 單分片操作的組合（目錄的情況），或一個 FileStore 操作 + 一個 TafDB 單分片操作的組合（文件的情況），配合通過精心排列的順序，使得這兩個操作只需要滿足分別滿足原子性即可保證執(zhí)行效果，不再需要一把大鎖來保護整個范圍。

第二步，將單分片操作的沖突范圍縮小到字段級別，并實現(xiàn)無鎖化

在沖突縮小到單分片之后，如果不經(jīng)過任何優(yōu)化，單個目錄下的操作仍然需要串行執(zhí)行。TafDB 通過對存儲引擎進行擴展，引入單分片原語（single-shard atomic primitive）的技術(shù)，將原來的行沖突縮小成具體字段的原子操作，并能對并發(fā)的操作自動合并。

第三步，精簡元數(shù)據(jù)代理層，進一步縮短執(zhí)行路徑

在上述優(yōu)化后，除了非常復雜的 rename 操作，元數(shù)據(jù)代理層（Namespace 1.0 的 Namespace 模塊）的作用僅剩實現(xiàn) POSIX 接口并轉(zhuǎn)發(fā)請求，我們將這一層的能力直接整合到客戶端中，只保留復雜 rename 的處理，重新命名為 Renamer。

5. 整體架構(gòu)

CFS 元數(shù)據(jù)架構(gòu) Namespace 2.0

根據(jù)上述的實現(xiàn)思路，整個系統(tǒng)架構(gòu)上分成四個部分:

• Namespace 存儲層（TafDB）：TafDB 負責存儲層級命名空間里除文件屬性外的其它部分；
• 文件存儲層（FileStore）：這一層是一個以平坦方式組織的塊存儲層，塊是文件數(shù)據(jù)的基本單位。文件屬性和文件數(shù)據(jù)一起存儲在該系統(tǒng)里。對于文件屬性而言，這是一個不支持范圍讀、只支持點讀的 KV 系統(tǒng)；
• Rename 服務(wù)（Renamer）：Multi-Raft 架構(gòu)，每個文件系統(tǒng)由一個 Raft 復制組提供對復雜 rename，即所謂 Normal Path rename 的支持；
• 客戶端庫（ClientLib）：客戶端負責接收具體的請求，拆解成上述模塊的內(nèi)部請求。ClientLib 提供必要的接口，以方便接入 Linux VFS 層，目前支持 FUSE、Samba、NFS-Ganesha。

從上面的架構(gòu)圖可以看出，CFS 中不再存在傳統(tǒng)分布式文件系統(tǒng)的 MDS 或 NameNode 角色，所有的功能全部打散到其它模塊。

這個設(shè)計在維持分離式架構(gòu)優(yōu)點的同時，解決了其存在的全部缺點，在擴展性、延時、均衡性等方面都達到了比較好的狀態(tài)。

我們認為，這個新的思路給分離式架構(gòu)這輛汽?換上了新的引擎，讓這輛汽?在各方面的表現(xiàn)全面超越了??。

6. 實現(xiàn)細節(jié)

6.1. 元數(shù)據(jù)組織和分片

和 InfiniFS 類似，CFS 將每一個目錄項的記錄拆解成兩部分，分別是 inode id record 和 attributes record。這個分解是進一步縮減沖突域的基礎(chǔ)。

TafDB 使用一張 inode_table 表來存儲所有的數(shù)據(jù)，表的主鍵為 <kID, kStr>。這張表里實際上存儲了混合存儲的兩類數(shù)據(jù)，包括所有的 inode id record 和目錄的 attributes record。FileStore 負責存儲文件的 attributes record。整體如下圖一樣組織：

對于 inode id record，<kID, kStr> 中的 kID 部分代表父目錄的 inode，kStr 代表子項的名字。這種記錄是為了滿足 lookup 和 readdir 的需求，除了 inode 和 type，其它字段都是無效的。

對于目錄的 attributes record，kID 就是目錄自己的 inode，kStr 是保留字符串 /_ATTR。其它字段存放的是各個屬性字段，inode 字段在這里留空沒有實際作用。

inode_table 整體上按 <kID, kStr> 有序存儲所有數(shù)據(jù)，分片規(guī)則是按照 kID 來的。TafDB 做了一個特殊的保證，即分片無論如何分裂和合并，同一個 kID 的數(shù)據(jù)始終存儲在同一個分片上。這意味著同一個目錄的關(guān)聯(lián)變更涉及到的數(shù)據(jù)都在一個分片進行處理，CFS 實現(xiàn)了目錄級別的 range partition。所有分片的分裂和合并操作都是 TafDB 自動進行的，不需要 CFS 關(guān)注和人工干預。

需要指出的是，我們認為目前的設(shè)計沒有必要繼續(xù)探索單目錄多分片，以往的耦合式系統(tǒng)里存在此類設(shè)計的根本原因是因為一個節(jié)點上的熱點無法精確疏散，熱點會影響同節(jié)點上的其它目錄的操作，多個熱點間也會互相影響，只能通過分散目錄壓力的方式來緩解問題。但我們的架構(gòu)不存在此問題，理由如下:

• TafDB 極端情況下可以分裂到單個目錄獨占整個分片，單個分片獨占整個機器，單目錄的處理能力和單點架構(gòu)相當。這個粒度足夠小，處理能力足夠強；
• 文件屬性分離到 FileStore 之后，單分片不需要處理占比最高的文件屬性操作，壓力遠小于傳統(tǒng)的設(shè)計。

6.2. 縮減分布式鎖開銷

6.2.1. 優(yōu)化跨組件的協(xié)同開銷

將元數(shù)據(jù)分散到 TafDB 和 FileStore 兩個組件存儲之后，首先要保證的是兩個系統(tǒng)的對外一致性。我們通過精心排列的執(zhí)行順序來解決這個問題：

• 對于所有的創(chuàng)建操作，先創(chuàng)建 FileStore file attribuets record，后創(chuàng)建 TafDB inode id record；
• 對于所有的刪除操作，先刪除 TafDB inode id record，再刪除 FileStore file attribuets record；

以 create、unlink、rename 為例，具體的執(zhí)行過程如下：

文件系統(tǒng)在對文件操作之前都會經(jīng)歷從特定目錄開始 lookup 的過程，只有 inode id record 存在對應的文件才會被看到，因此，只需要保證 file attributes record 比 inode id record 更早產(chǎn)生更晚消亡，就可以保證無效數(shù)據(jù)不會被用戶看到，從外部視角觀察，一致性沒有被打破。圖示給出的操作順序可以達到這個效果，唯一的副作用是操作失敗可能殘留垃圾，這可以通過垃圾回收來解決。

這個方法可以推廣到 TafDB 內(nèi)部的情況，對于 inode id record 和 attribuets record 均存儲在 TafDB 的目錄也同樣適用。當然，具體的操作執(zhí)行順序需要考慮 POSIX 的兼容性要求，可能和文件不完全一致，在此不做詳細展開。

6.2.2. 優(yōu)化 TafDB 內(nèi)部的跨分片開銷

在 TafDB 這樣的系統(tǒng)中，如果一個事務(wù)涉及到多個分片，必然需要 2PC 事務(wù)提交機制來保證 ACID。我們采用的數(shù)據(jù)布局，讓目錄的 attribuets record 和其子項的 inode id record 都在一個分片內(nèi)，使得這些必要的修改操作可以從傳統(tǒng)的跨分片事務(wù)簡化到單分片事務(wù)。在接下來的章節(jié)我們將介紹這個簡化技術(shù)。經(jīng)過這一次裁剪之后，CFS 中除了 Normal Path rename，所有的 TafDB 操作均是高度優(yōu)化的單分片事務(wù)。

6.3. 縮減單分片鎖

6.3.1. 單分片原語

關(guān)聯(lián)變更涉及到多條記錄，在執(zhí)行過程中還存在 read-and-modify 模式，特別的，對父目錄屬性的修改就需要先讀出舊值再更新。一個樸素的實現(xiàn)方式會包含多輪條件檢查、讀和寫操作，效率肯定是不高的。為了解決這個問題，我們提出了單分片原語（single-shard atomic primitive）的概念。

每一種原語實現(xiàn)了一個定制的單分片事務(wù)，這個事務(wù)原子地完成所需要的所有讀、寫和條件檢查，保證執(zhí)行過程是 all-or-nothing 的，只有全部條件檢查為真，才會執(zhí)行成功，否則不會對分片數(shù)據(jù)做任何修改。原語作為一種特殊的單分片事務(wù)，高度優(yōu)化后的執(zhí)行代價和寫一條 WAL 日志相當。

我們歸納了所有的 POSIX 操作，最后總結(jié)出三種原語，如下表所示，表中同時標注了每種原語的使用范圍、類 SQL 形式的接口描述和簡要的執(zhí)行過程：

論文里給了 create、unlink、同目錄文件 rename 偽代碼作為示例解釋了原語是如何工作的。在這里我們可以看一下其中 create 的例子。

create 的第一個步驟是在 FileStore 中創(chuàng)建文件，第二個步驟就是 instert_with_update 原語，主要完成了以下工作:

• WHERE 做了兩個條件檢查，kID=@parent_id, kStr="/_ATTR", type=dir 這幾個條件聯(lián)合檢查 kID、kStr、type 是否符合指定的值。當檢查通過時意味著 inode 為 @parent_id 的 attribuets record 在 TafDB 中存在，且類型為目錄；
• SET 對符合 WHERE 條件的記錄更新屬性，具體的就是更新 children、size、mtime 等字段；
• INSERT 插入 inode id record 記錄，主鍵是 kID=@parent_id, kStr=@name，主要的字段是 inode；

在文章里原語是以類 SQL 的形式表達的，這只是為了表達的方便，實際 TafDB 提供的是 KV 層接口。相比于標準的接口，原語強化了條件檢查的能力，同時在語句執(zhí)行出錯時能夠返回更精細的出錯條件，CFS 負責將這些條件轉(zhuǎn)譯成 POSIX 錯誤碼。根據(jù)我們的經(jīng)驗，即使使用的 Table 系統(tǒng)本身不支持這樣的擴展，進行二次開發(fā)所需的工作量也很小，和耦合式元數(shù)據(jù)服務(wù)相比，工作量和實現(xiàn)難度更是要低好幾個數(shù)量級。

最后，我們總結(jié)一下原語的優(yōu)勢：

• 極大地降低了和 TafDB 的通信開銷，交互輪次減到一次；
• 將很多的關(guān)聯(lián)操作壓縮到一次處理，降低了整體的處理損耗，并存在進一步優(yōu)化的空間；
• 簡化了元數(shù)據(jù)服務(wù)的設(shè)計，不同的 POSIX 操作可以被 3 種原語概括，傳統(tǒng)的實現(xiàn)則需要實現(xiàn)所有的 POSIX 接口。

6.3.2. 沖突合并

如果沿用標準的實現(xiàn)，上述的原語仍然在父目錄屬性更新的時候?qū)е屡抨?。前文我們分析過，這里沖突的本質(zhì)其實是對屬性的更新操作，本質(zhì)上是一些原子變量操作。根據(jù)這一點，我們進一步實現(xiàn)了兩個增強機制用于弱化及合并處理事務(wù)沖突。

第一個機制是 delta apply，針對 links、children、size 這些數(shù)字屬性。它們在變更的時候會加減增量，和原子變量加減一樣，順序并不重要，只要保證最終的疊加結(jié)果是對的。delta apply 就實現(xiàn)了這種合并加減效果。

第二個機制是 last-writer-win，針對權(quán)限、mtime、ctime 這些單純的覆蓋操作，我們簡單的保留最后一個賦值操作的結(jié)果。

原語通過檢查 SET 語句涉及的是加減運算（如 children+=1）還是賦值運算（如 mtime=@now）就可以自動決定運用 delta apply 還是 last-writer-win。這個檢測完全不需要感知文件系統(tǒng)的語義，具有通用性，實際上可以推廣到任何只是部分字段原子變量操作的場景，實現(xiàn)比寫寫沖突更小范圍的沖突。

6.4. 移除元數(shù)據(jù)代理層

將 Normal Path rename 之外的所有操作均拆解成了原語的組合之后，這些操作之間只有落到單個分片上時才可能會產(chǎn)生沖突，分離式架構(gòu)里的元數(shù)據(jù)代理層存在的唯一價值變成了接口翻譯，串聯(lián)起各個環(huán)節(jié)來實現(xiàn) POSIX 接口，但這一點完全可以由客戶端來承擔，因此我們做了一個大膽的決定，將這一層功能完全集成到客戶端來實現(xiàn)。

6.5. 強一致 Rename

rename 是一個文件系統(tǒng)里最復雜的操作，最壞的情況下，涉及到 6 個元數(shù)據(jù)對象，包括 4 個 attributes record，2 個 inode id records。根據(jù)我們的線上統(tǒng)計，99% 的 rename 都發(fā)生在同一個目錄內(nèi)文件間，這種 case 涉及到的變更都在一個 TafDB 分片內(nèi)，可以采用前文提及的方法優(yōu)化。因此，我們將 rename 分為 Fast Path 和 Normal Path 兩種。

Fast Path 的 rename 基于 insert_and_delete_with_update 原語實現(xiàn)，只處理同一個目錄內(nèi)的文件 rename，剩下的其它類型均為 Normal Path。Normal Path 由 Renamer 進行處理，Renamer 是每個文件系統(tǒng)一個 Raft 復制組，負責對 Normal Path rename 操作進行沖突檢測。只有通過沖突檢測的請求會發(fā)往 TafDB 繼續(xù)處理使用 2PC 事務(wù)進行處理，這個檢測可以保證發(fā)出去的請求不會導致孤兒或環(huán)。

Normal Path rename 和其它操作并發(fā)的正確性基于兩個方面保證:

• 其它操作都不會改變子項的歸屬，頂多導致看到的信息不是最新的，但不會對成環(huán)或孤兒的判斷產(chǎn)生實際影響。在處理 Normal Path rename 的 2PC 事務(wù)中，我們會對可能誤判的情況進行進一步的檢查，如果出現(xiàn)變化則進行回退重試，整個處理過程和樂觀鎖機制類似；
• 1PC 事務(wù)只是對普通 2PC 事務(wù)的高度優(yōu)化，ACID 和事務(wù)隔離級別的保證沒有被破壞，因此并發(fā)的 1PC、2PC 事務(wù)進一步由 TafDB 進行沖突處理，保證執(zhí)行的結(jié)果符合隔離性和正確性承諾。

整個機制的正確性可以通過 TLA+ 之類的形式化驗證手段證明。

6.6 垃圾回收

當 ClientLib 出現(xiàn)網(wǎng)絡(luò)分區(qū)或者進程崩潰的時候，沒有做完的操作會導致 TafDB 或 FileStore 中殘留垃圾。系統(tǒng)通過兩種機制進行處理這些垃圾：

• 周期對賬：周期性地在 TafDB 和 FileStore 之間進行對賬，回收垃圾數(shù)據(jù)；
• 按需處理：當 getattr、readdir 在執(zhí)行的時候發(fā)現(xiàn)某些 attributes record 無法找到時可以?上發(fā)起一次垃圾回收，回收對應的 inode id record。

7. 實驗

論文里將 CFS 和 HopsFS、InfiniFS 進行了詳細的對比。測試結(jié)果顯示，在 50 節(jié)點規(guī)模的測試中，與 HopsFS 和 InfiniFS 相比，CFS 各操作的吞吐量提高至 1.76 – 75.82 倍和 1.22 – 4.10 倍，并將它們的平均延遲分別最高降低了 91.71% 和 54.54%。在競爭較高和目錄較大的情況下，CFS 的吞吐量優(yōu)勢則會進一步擴大一個數(shù)量級。

想了解完整測試結(jié)果的讀者可以閱讀論文原文的實驗部分，在這里就不再贅述。

8. 總結(jié)

本文介紹了百度智能云文件存儲 CFS 的元數(shù)據(jù)系統(tǒng)的核心設(shè)計，對?期困擾文件系統(tǒng)元數(shù)據(jù)領(lǐng)域的 POSIX 兼容性和高擴展性（特別是寫擴展性）難以兼顧的問題，進行了解答。這是一個大規(guī)模分布式文件系統(tǒng)能否擴展到千億級別文件數(shù)，同時保持高性能穩(wěn)定性的一個關(guān)鍵問題。

分離式元數(shù)據(jù)架構(gòu)是近年來文件系統(tǒng)元數(shù)據(jù)領(lǐng)域的發(fā)展趨勢，業(yè)界有潛力存儲千億文件的系統(tǒng)均是基于這種架構(gòu)實現(xiàn)的。這類架構(gòu)采用類似 “存算分離” 的思想，將元數(shù)據(jù)服務(wù)分為兩層，分別是負責存儲數(shù)據(jù)的數(shù)據(jù)庫層，和偏計算邏輯、負責實現(xiàn)文件系統(tǒng)語義的元數(shù)據(jù)代理層。但這種架構(gòu)并沒有解決寫擴展性較差、寫延時偏高的問題。

文件存儲 CFS 進一步發(fā)展了分離式元數(shù)據(jù)架構(gòu)，通過精心設(shè)計數(shù)據(jù)布局，讓元數(shù)據(jù)的不同部分以更科學的方式在系統(tǒng)里打散和聚合。打散是為了提高數(shù)據(jù)處理的并行度，聚合則讓相互依賴的數(shù)據(jù)避免多輪交互能夠被一次就處理完。在這個數(shù)據(jù)布局的基礎(chǔ)上，CFS 不斷修剪元數(shù)據(jù)寫操作臨界區(qū)的范圍，最終實現(xiàn)了無鎖化，解決了分離式元數(shù)據(jù)架構(gòu)寫擴展性較差、寫延時偏高的問題。

CFS 的這套設(shè)計已經(jīng)在生產(chǎn)環(huán)境中穩(wěn)定運行了超過 3 年時間，為云上蓬勃發(fā)展的的大數(shù)據(jù)、AI、容器、生命科學等場景的業(yè)務(wù)提供了有力支撐。

需要指出的是，CFS 的創(chuàng)新和整個百度滄海存儲技術(shù)體系的大力支持是分不開的。合抱之木，生于毫末；九層之臺，起于累土。正是因為前人和其它團隊做了很多扎實的工作，我們才可以對一些不成熟、非常規(guī)的想法快速地進行驗證和試錯，并在驗證完全之后迅速落地生產(chǎn)環(huán)境。在百度內(nèi)部，這樣的例子還有很多。

在研發(fā) CFS 元數(shù)據(jù)系統(tǒng)的過程中，我們得到的另外一個收獲是懷疑精神，技術(shù)上沒有什么權(quán)威是不可挑戰(zhàn)的，多問一句 “從來如此便對嗎” 沒什么壞處。

最后，再次感謝 CFS 論文的合作方中國科學技術(shù)大學先進數(shù)據(jù)系統(tǒng)實驗室 （Advanced Data Systems Laboratory, ADSL）的老師和同學們，這篇論文的面世離不開你們的共同努力。