# 6-2 Ceph: A Scalable, High-Performance Distributed File System
:::info
**Ceph是一種分散式檔案系統**，具備良好的效能、可靠性和可擴展性，在Ceph中資料是由一種偽隨機函數**CRUSH來決定分佈在哪個物件儲存裝置**（OSD）上，從而達到將**資料層與meta data分離**，不像其它分散式檔案系統（如GFS），是master透過本地表記錄資料分佈，將資料複製、故障偵測、故障復原都下放到semi-autonomous、運行著特殊的本地物件檔案系統（specialized local object file system）的OSD。
:::

## Introduction
檔案系統效能是影響應用程式整體效能的關鍵因素。
* **傳統方式:** server export a file system hierarchy，客戶端將其映射成local name space，可擴展性很差。
存取介面是在block-level讀寫byte ranges。
* **較新的分散式模型:** 採用基於物件的儲存架構，傳統的硬碟被OSD(object storage device)取代。
存取介面是更大的named objects ，將更底層的block分配決定權交給設備本身，client通常和metadata server（MDS）互動來執行元資料操作（open、rename），但直接和OSD通訊來執行檔案I/O （read、、write）。
>一個OSD由CPU、網卡、底層磁碟或RAID及其本地快取組成。

但還是會遇到可擴展性的限制，因為沒有將元資料的操作分散到不同node，也沒有將device intelligence下放給OSD。

Ceph架構基於「PB級的儲存系統本質上是動態的」這個假設，因此:
1. 大型系統都是增量建置出來的
2. 節點故障是常態而非意外
3. 負載的品質和特性隨時間不斷變化

Ceph 以generating function取代了allocation table，從而實現了資料和元資料操作的解耦，元資料叢集採用了高度自適應的分散式架構，顯著提升了元資料存取的可擴展性。

## System Overview

系統主要有三個部分
**1. client:** 負責提供POSIX檔案系統介面給host或process。
**2. OSD cluster:** 儲存資料和元數據。
**3. metadata server cluster:** 管理命名空間（檔案名稱和目錄），協調security、consistency 和coherence。
>**consistency**是指replication file間的一致性; **coherency**是指緩存一致性。
>**safety**是指非預期事故或故障造成的損害; **security**是指惡意攻擊或未經授權的存取。

Ceph依賴底層三個特性(2.1~2.3)，目的是為了**減少MDS的負擔**(因為POSIX介面或傳統單體檔案系統的元資料管理壓力太大，不適合原封不動地遷移到分散式架構中)，解決擴展性的同時也取得了高效能、高可靠性和高可用性:
### 資料和元資料解耦
將檔案的資料儲存和元資料管理進行了最大程度的解耦，元資料操作（ open、rename等）由metadata server統一管理，client直接和OSD互動以執行檔案的I/O。
基於物件的檔案系統只是將很長的block list變成較短的物件清單object list， 而**Ceph是完全去掉了allocation list**(object list)，因為在CRASH中**檔案數據被劃分成可預測的named object**
>Ceph採用了CRUSH算法來動態計算數據應該存儲在集群中哪個位置，使得 Ceph不需要維護一個中心化的物件清單來追蹤每個數據塊的存儲位置>

Ceph在檔案層切入，MDS只負責管理元資料的操作，每個檔案條帶化之後儲存在多個OSD上，透過CRUSH的資料分佈函數將物件分配到儲存裝置上，讓其他工具都可以計算文件的所有對象的名字和位置，不需要詢問MDS。
>其它許多分散式檔案系統的切入點是在file層以下，如block/chunk，整個檔案實際上由若干個block/chunk這樣的小物件組成，但這種設計對元資料的管理有比較高的要求，也就是元資料層會制約整個系統的擴展性。

### 動態分散式元資料管理
典型檔案系統中元資料的操作可能會佔系統一半的負載。
Ceph 採用了一種基於**Dynamic Subtree Partitioning（動態子樹分割）** 的元資料集群架構，可以自適應地在不同MDS 之間自動均衡目錄樹(分發管理檔案系統目錄結構的任務)，從而進一步緩解單一MDS的壓力。

### 可靠、自動的分散式物件存儲
Ceph中資料遷移、replication、錯誤偵測、復原等功能都下放到了OSD cluster中，OSD cluster整體提供一個單一的邏輯物件倉庫，這種設計能充分利用OSD的資源，實現線性擴展。

## Client Operation
Ceph client提供一個檔案系統介面給應用程式。client可以透過連結的方式使用，也可以透過FUSE（一個用戶態檔案系統介面）掛載成檔案系統，每個client都有自己的檔案和buffer cache、獨立的核心page。

### File I/O and Capabilities
當client需要open一個檔案時，收到要求的MDS會遍歷檔案系統，將檔案名稱轉換為inode，同時可能會傳回capability(規定可以執行那些操作)或security key等。 Ceph中檔案都是條帶（stripe）化的，每個檔案對應一組條帶對象，物件名字由inode number 和 stripe number組成，透過CRUSH可以知道每個條帶物件對應的OSD，Ceph中允許某個條帶物件或位元組範圍不存在，即檔案中可以有hole。

### Client Synchronization
POSIX語意明確定義
1. 寫後立即能讀到。
2. 寫入操作是原子的。
當MDS發現檔案被多個client並發讀寫的時候，就會收回所有client的buffer capability，強制client執行同步的讀寫操作，這樣單一OSD的並發操作的順序完全由OSD自己決定，極大簡化了設計。不過當寫跨物件邊界(多個物件)時，client就需要向這些受影響的物件加上取得鎖。

從上面可知同步I/O對效能影響很大，會增加延遲，特別是讀取或寫入的資料小時，至少要一次OSD來回。所以Ceph實現一個對POSIX I/O 介面的高效能運算擴展，像是*O_LAZY*表示寬松的coherency ，另外，應用程式可以自行管理一致性，例如保證不同client寫檔案的不同區域，這樣每個client都可以使用cache了，client還可以呼叫*lazyio_propagate*保證自己的寫反映到檔案上，*lazyio_synchronize*保證後續讀取反映最新的寫內容（類似於atomic_release和atomic_require）。

### Namespace Operations
client與MDS的所有namespace相關操作（readdir/ stat/ unlink/chmod等）都是同步的，不提供明確的加鎖及callback（因為對HPC場景無用且開銷大）。
為了降低這些同步namespace操作的延遲，Ceph對常見場景做了最佳化，例如一次readdir在Ceph 中只需要一次MDS 請求，會載入整個目錄的inode，如果readdir之後有一個或多個stat（ls -l），這樣stat就會直接返回剛剛載入的內容，犧牲了一致性（假設之間有更新），但換來了效能。

Ceph不像其它一些系統那樣（如早期的NFS）會長時間（如30秒）緩存元數據，這樣對coherency的衝擊太大，所以Ceph對這些影響性能的介面進行了擴展，如對一個被多個客戶端開啟進行寫入操作的檔案進行stat操作，MDS會撤回所有的write capability，立即停止更新操作，然後從所有的writer收集最新的size和mtime資訊，stat傳回最大的那個值，再重新授予capability，保證獲得正確的文件大小和修改時間，而不需要這種保證的應用可以呼叫statlite。

## Dynamically Distributed Metadata
檔案系統的workload中元資料操作經常佔據了檔案系統多達一半的負載，且都在關鍵路上，因此MDS 叢集對於系統的整體效能非常關鍵。
Ceph中檔案和目錄的元資料都很小，幾乎只包含目錄項目（檔案名稱）和inode（80B），與傳統檔案系統不同的是，Ceph中不需要記錄block分配表（編碼到條帶物件名字中，使用CRUSH定位），物件名稱是根據inode number 建構出來的，然後利用CRUSH分散到不同OSD上，簡化了metadata負載，讓MDS能有效率地管理非常龐大的文件集。

### Metadata Storage
**MDS叢集的目標是用記憶體快取提供大部分的請求**，但metadata的更新必須寫入到磁碟，以確保資料的safety。
每個MDS都有自己的journal，以streaming的方式將更新的元資料快速寫到OSD，這些journal後續會合併到MDS的長期儲存中（也由OSD負責），當它最終將journal entries 寫到磁碟之前，有些更新就已經標記為過期了
>目前未實現MDS恢復過程，但當MDS 發生故障時，其他節點會快速的掃描journal，恢復失敗的節點中記憶體快取（為了快速恢復）的內容，進而恢復文件系統狀態，有兩種好處:
>1. 以一種高效的（順序的）方式將更新流式傳輸到磁盤。
>2. 避免了大量的重複寫入（re-write）負載，使磁碟上的長期儲存佈局可以針對讀做優化，如inode直接嵌入目錄中，這樣一次讀取操作就可以把整個目錄的inode拿到。

每個目錄的內容會分散到相同的OSD，每個MDS都有自己的inode範圍，另外有一個全域的anchor table保存對應多個hardlink的inode， 盡量優化單一link的場景。

### Dynamic Subtree Partitioning
primary-copy 快取策略使得對任一份metadata，只有一個權威的MDS 負責管理快取一致性和更新順序化。
dynamic subtree partitioning是一個Ceph的一個創新: **MDS之間基於目錄樹的負載平衡**，在節點之間自適應地以層級（hierarchically ）分發快取的元資料（cached metadata）。

每個MDS 都會使用指數時間衰退的計數器（counters with an exponential time decay），測量directory hierarchy內的元資料熱度（popularity ）。
每次操作時，受影響的inode 以及它向上直到根目錄的所有祖先節點上的計數器都會增加。**最終呈現給MDS 的就是一棵能反映最近一段時間負載分佈的權重樹（weighted tree）**，這樣MDS之間就可以方便遷移目錄樹了。
shared long-term storage和carefully constructed namespace locks使得這種元資料遷移只需將記憶體快取中的部分內容轉移到新的權威，而對coherence lock 或客戶端capability 影響最小。遷移過程中新MDS會把資料都寫進journal，之後新增修改會寫進新舊兩個MDS的journal，直到遷移完成。
遷移過程中inode的內容會分為三組：
* security（owner, mode）
* file（size, mtime）
* immutable(inode number, ctime, layout）

其中security和file locks在遷移過程中可能會改變，需要加鎖，是受獨立的狀態機管理的，每個狀態機有不同的狀態集合和狀態轉移。例如在遍歷樹進行security check時需要owner和mode，但是這個兩個字段變化非常少，因此需要的狀態就只有幾個，而file lock 反映的是類型更廣泛的客戶端端存取模式，很有可能修改。
>security基本上不變，但file則很可能有修改。

### Traffic Control
Ceph 利用元資料的熱度資訊在必要時做熱點的分散，在通常情況下，這不需要額外的開銷，也不會破壞directory locality。
針對特別熱門的目錄，Ceph可以有特殊處理：
1. 讀特別熱(被大量讀取)的目錄可以分散到多個MDS節點，以減少負擔。
2. 寫入特別熱(被大量寫入)的目錄可以按filename hash後分散到多個節點上，用犧牲目錄locality換來負載的均衡分佈。

這些內容都可以由MDS回傳給client，也就是每個MDS的回應裡都有更新之後的權威訊息，以及相關的inode及其祖先是否被複製到其他節點訊息，這使得client可以了解到元資料的分割資訊。

## Distributed Object Storage
從client和MDS的角度看Ceph的整個OSD叢集是一個整體（一個single logical object store and namespace），所有replication、資料遷移、容錯復原等機制都下放到Reliable Atuonomic Distributed Object Store（RADOS）的資料儲存層。

### Data Distribution with CRUSH
>[CRUSH論文整理](https://hackmd.io/@11220CS542600/HyxrKSzM0)

為避免不平衡或負載不對稱，採用以下的資料分佈策略：
1. 隨機分散新數據。
2. 隨機遷移一部分現有資料到新設備。
3. 將被移除的設備上的數據均勻地分散到其他設備上。

物件到OSD 的映射分兩步驟：
1. 物件到PG：用簡單的hash
2. PG到OSD列表：用CRUSH

>Ceph先將物件依hash分成若干個placement group（PG），接著再透過CRUSH將PG分配給OSD，PG與OSD的數量比例大概是100:1，**CRUSH只需要知道pg和OSD map就可以定義一個物件**，好處如下:
>1. client和工具可以自行計算PG所在的OSD，不需要透過MDS。
>2. 保證了整個叢集儲存負載的平衡。
>3. OSD map更新頻率非常低，每次更新只會影響到非常少量的PG。
>
>**因此CRUSH同時解決data distribution和data location的問題**。

CRUSH在執行時會根據placement rule將PG對應到OSD，cluster map也維護了down和inactive的設備列表，以及一個epoch number，每次OSD cluster map都變化，epoch 都會加1。所有的OSD請求都會帶有client的map epoch，因此所有的參與者都可以就目前的資料分佈達成一致共識。

### Replication
**RADOS使用了primary-copy的一個變種來做replication**，資料以PG為單位複製。
* 寫入請球
client將寫入請求傳送給物件的PG對應的OSD清單中第一個狀態正常的（non-failed）primary OSD，OSD會為寫的物件和PG分配新version，隨後轉寄寫入請求給其它參與replication的OSD，當所有replica都執行完修改回覆primary後，primary再執行修改並回覆client。
* 讀取請求
均由primary處理（可用Paxos/Raft）。

>簡化了副本同步或序列化對客戶端複雜度的影響，還將複製消耗的頻寬從客戶端側移動到OSD 叢集內部網路。

### Data Safety
在分散式系統中，為什麼資料要寫到共享儲存本質上?
1. 客戶端希望它們的更新對其他客戶端可見，代表系統越快越好，也就是寫入越快生效越好。
2. 客戶端希望它們寫的資料已經非常可靠地做了副本，並flush到了磁碟上，能夠承受掉電或其他故障。


RADOS分離了同步與safety，目的是同時服務需要低延遲和高安全性的應用，client因此在收到請求成功之後，仍然要本地快取寫過的數據，直到知道提交成功。

### Failure Detection
對於那些會導致OSD 失聯的故障，RADOS使用主動監控（active monitoring），**讓共享PG 的OSD互相監控彼此**，短時間無回應的OSD會被標記為down，它的primary也會讓給其它OSD，長時間標記為down的OSD會被標記為out，其它OSD會接管它的PG。
用monitor集群負責收集failure reports信息，過濾掉transient或系統性的問題（例如網路分裂），以及管理OSD map，OSD map的變化會先發給受影響的OSD，然後在相互間的反應中傳播開。

### Recovery and Cluster Updates
**OSD 為每個物件維護了一個版本號碼和每個PG最近改動的日誌**，當一個active OSD收到一個更新的cluster map，它會遍歷本地所有的PG，計算CRUSH mapping，確定每個OSD是該作為primary OSD還是replica OSD。
* 如果一個PG 的OSD 成員清單變了:
對於replicated PG，它需要向primary OSD 提供它自己目前的PG 版本號。如果一個OSD 是PG 的primary OSD，它需要收集目前（以及之前的）replica OSD 的PG 版本資訊。
* 如果primary OSD 缺少了PG:
最近的更新為了確定正確的（最近的）PG 內容，它需要從PG 對應的當前或前一個OSD那裡獲取最近的PG改動的log，只有當primary OSD確定了正確的PG 狀態，並且將它共享給其他副本後，開始接受到這個PG內的物件的I/O操作，OSD就可以獨立從它們的peer取得它們遺失的或是過期的物件。

故障恢復完全是由每個OSD 驅動的，因此一個OSD故障受影響的那些PG（很可能）會在不同OSD 上並行恢復。

### Object Storage with EBOFS
OSD的本機檔案系統稱為Extent and B-tree based Object File System（EBOFS)，**完全在用戶態實現，直接操縱裸露的區塊設備**，使得我們可以自己定義低層的對象存儲接口和更新語義，將update serialization（為了同步）和磁碟提交（為了安全性）分離開來。
支援同步與提交的分離、多個物件的原子事務等特性。
>許多分散式儲存系統使用ext3這種檔案系統，為什麼OSD不用?
>ext3對於object workload的介面和效能都很差。

大部分核心檔案系統都是惰性地（lazily）將更新flush 到磁碟，但**EBOFS是主動地調度磁碟寫操作**，如果後面的更新會覆蓋前面的更新，那麼前面的pending更新可能會在flush之前就被取消了，使得我們的低層磁碟調度器有一個更長的I/O 隊列，可以提高調度的效率。

**EBOFS的核心設計是一個健壯的、靈活的、功能完整的B-Tree 服務，用於定位物件在磁碟中的位置、管理區塊分配、對PG進行索引。**
<!-- ## 6. Performance and Scalability Evaluation

## 7. Experiences

## 8. Related Work

## 9. Future Work -->
1. MDS 故障復原和幾個POSIX 呼叫還沒實現。
2. 在同一目錄或檔案進行大量存取時只會對元資料進行複製，不會對資料進行複製。
3. 按類型聚合流量。
4. 其他最佳化。
## Conclusions
Ceph沒有使用allocation lists，而是透過Crush最大化資料和元資料管理的分離，允許client計算而不是尋找物件的位置，從而達到高擴展性、高效能和高可靠性。
## Reference
[筆記] https://kairen-archived.github.io/2015/11/19/ceph/introduction/
[筆記] https://fuzhe1989.github.io/2021/03/28/ceph-a-scalable-high-performance-distributed-file-system/
[翻譯] https://arthurchiao.art/blog/ceph-osdi-zh/