# F2FS and BtrFS

## F2FS
F2FS 全名為 Flash-Friendly File System，由三星 (Samsung) 開發，期望藉由此項目取代傳統的如 JAFFS 等應用於快閃記憶體的檔案系統，在效能上也較 ext4 有更好的表現。

在一個行動裝置上，通常會有多個快閃晶片 (Flash Chips)，所以需要透過專門的硬體和軟體如 FTL (Flash Tramslation Layer) 將各種不同的快閃儲存裝置抽象並統一，且通常使用隨機寫入 (random write) 來存取，但會因此衍生一些問題如下：
- 頻繁地隨機寫入會造成嚴重的碎片化
- 對行動裝置來說，隨機寫入會造成較大的負擔
- 增加裝置的 I/O 延遲
- 減少裝置的生命週期 (life time)
因此，F2FS 為了解決這些問題，使用 1. Log-structured 2. COW (Copy on Write) 來解決這些問題。
### 結構
整個檔案系統在磁碟上，由小到大的單位依序是 segment, section, zone，segment 預設的大小為 2MB，並且將 volume 切成多個固定大小的區塊，並配置如下：
1. Superblock：不可變更的，用來儲存基礎的分割資訊，唯一不是以 segment 當作最小單位。
2. Check Point (CP)：用來保持文件的狀態，正常情況下，CP 必須在特定的時間儲存一致的狀態，並在突發事件例如斷電、作業系統崩潰後，該單位則成為恢復點 (recovery point)。
4. Segment Info Table (SIT)：用來儲存該 segment 的資訊，例如有多少可用的區塊 (valid blocks) 及 bitmap 用來儲存所有區塊 (block) 的狀態等，當需要清理 (cleaning) 時，可藉由此區塊快速的判斷。
5. Node Address Table (NAT)：用來儲存在主區域 (main area) 中，所有 node blocks 的地址。
6. Segment Summary Area (SSA)：用來儲存所有在主區域中各區塊的資訊如 parent inode number, node offset, data offset...。
7. Main Area：該區域為儲存裝置的主要資料儲存區，並且有兩種型態的節點 (node)
- node：該資料區塊的 inode 或是作為 indirect inode
- data：使用者儲存的資料或是目錄 (directory)


### 索引結構 (index structure)
主要可分為檔案結構 (file structure) 和目錄結構 (directory structure)。
- 檔案結構 (File Structure)：傳統的 LFS (Log-structured File System) 透過 inode 映射到對應的實體位址 (physical location)，但 F2FS
- 目錄結構 (Directory Structure)：為一個 4KB 大小的 dentry，由 bitmap, 兩個陣列紀錄 slot 和名稱。bitmap 用來記錄每一個 slot 是否有效；slot 紀錄 hash value、inode number、檔案長度、檔案類別等資訊。一個目錄結構會採用多層 hash table 的結構來管理。

### Multi-head Logging
該檔案系統使用 6 個 major log areas 標示 hot/cold 數據，一般的檔案系統會直接使用一大塊的 log areas 紀錄。實際上使用者可以自行決定要使用 2、4、6 種標示。如果使用 4 種，則會將 warm 和 cold 合併為一個標是；如果使用 2 種，則只會區分為 node 或是 data。

- direct node：和一般的定義相同，使用上會比 indirect node 更頻繁一些，因為該類型的 node 會直接接觸，所以會頻繁地更新資料，因此標示上為 Hot 和 Warm。
- indirect node：負責紀錄 directo node 的位址，只有在新增或是刪除節點的時候會更新，因此標示為 Cold。
- Main area 中目錄的 direct node 和 data block 都會被標示為 hot。
- 至於其他的 data block 只要符合下列其中一個條件，即可被標示為 Cold：
- 該 block 經過清理 (Cleaning) 移動過，可參考後續部分。
- 使用者可以自行定義該 block 為 Cold。
- 多媒體類型的資料也會被標示為 Cold，因為多媒體類型的資料通常寫入後不會頻繁地更新。


### 清理 (Cleaning)
用來整理破碎化、無效的區段 (segment) 的機制，每次清理會以 section 為最小單位來做清理。總共會分成兩種方法來做清理，分別是前景 (front-ground) 和背景 (back-ground)，前景只會在沒有足夠的空間時才會使用；背景則是會定期實施。可分為下列三步驟：
1. Victim Selection，選擇要清理的 section。
- greedy：前景 (front-ground) 時使用的方法，假設有 10 個 sections，在這十個 sections 中找出 valid blocks 最少的 section，代表該 section 的使用率 (utilization) 最低。
- cost-benefit：背景 (back-ground) 時使用的方法，以使用率和 age 來當作標準，age 為最近一次該 block 修改的時間，而該資訊會記錄在 SIT 中，此外也可以藉由 hot/cold 的標示迅速獲得。
2. valid block identification and migration：辨識有效的 block 並整合進其他 section 中。
- 前景使用的方法：檔案系統會使用一組 bitmap 來記錄每個 segment 的是否為有效的 (valid)，且該 bitmap 會放置在 SIT 中，因此只要掃瞄 SIT 即可得知每個 segment 內部的情況，在掃描完 bitmap 後，直接將 valid block 搬移至其他 section 中閒置的位置。如此即可空出一條完整的 secton 可寫入。(搬移的同時也會處理 parent node block 和其他相關的訊息)
- 背景使用的方法：檔案系統本身不會親自執行搬移的動作，而是將 valid block 推到 page cache 中，並且標示為 dirty，kernel 會在下次發生 cache misses 時，首先將 dirty block 移入檔案系統中。
3. post-cleaning process：在步驟 2. 之後會將 section 標記為 candicate (pre-free)，但還不能夠被使用，經過 CP 運作後，才會標記為 free 並且被使用。這個步驟主要是為了避免斷電或是系統崩潰之類的事情發生。

## Adaptive Logging
該部分主要探討檔案系統如何將資訊寫入至檔案系統中。主要有兩種策略如下：
- normal logging：block 被寫入到完整乾淨的 segment 中，並且以循序寫入 (sequential write) 的方式寫入，不論系統提出任何隨機寫入 (random write) 的要求。所以當空間耗盡時，就會一直發生清理 (cleaning)。
- threaded logging：將資料寫入到非完整的 segment 的空閒的 block 中，但因為採用隨機寫入 (random write) 所以效能表現較差。
F2FS 會實作上樹兩種機制，並且動態的改變策略，以目前擁有 k 個乾淨的 section 作為判斷標準，k 為預先設定好的閥值，通常為所有 section 數目中的 5%。

## BtrFS
由 Oracle 公司在 2017 年研發，原本是打算由此檔案系統替換掉 Linux 中 ext 系列的檔案系統，但由於設計問題，一直沒有長期支持的版本 (LTS)。
- page, block：block 為 4KB 的大小，並且是連續空間。
- Extent：許多檔案系統也會用到該概念，在磁碟上一塊連續的空間，並且對齊 page，所以長度為 page 的倍數，因為檔案系統通常是連續分配的，用此制度可以大幅的減少管理檔案空間的開銷，例如在 ext3 上，每增加一個 1GB 的檔案需要 256KB 大小的空間存放 block 管理。
- Copy-on-Write (COW)：此機制也是常用的方法，一般檔案系統在複製的時候會直接使用額外的空間存放複製的內容。但此機制是將此區域設為 read-only，當有 process 試著寫入時，才會配置一塊空間並複製內容供該 process 使用。

### 設計
1. COW friendly B-trees：使用 B-tree 結構，並且遵守下列三個特性
- top-down update procedure：由上至下更新。
- remove leaf-chaining：將不必要的節點清除。
- 使用計數器 (counter) 來管理空間：紀錄有多少個節點指向自己，可參考複製的說明和範例。樹根皆為 1，因為檔案系統會由一個 root 指向各樹的 root。
- 加入：可參考下圖解說，圖(a)為基本的 B-tree 結構範例，當要插入一個新的資料 19 時，並不會直接寫入到該寫入的 node 中，而是先複製一塊一樣的資料，並且複製一塊新的父節點，在寫入資料後，之後再將新的父節點的鏈結 (link) 連至新的節點。可對照至 top-down update procedure。


- 刪除：可參考下圖解說，圖(a)為一基本的 B-tree 結構範例，當要刪除一個新的資料時，操作和寫入類似，會有一個新的父節點，複製一塊一樣的子節點，並且在新的節點上刪除後再鏈結。

- 複製：可參考下圖解說，當有一父節點 p，並且新創建一節點 Q 複製節點 p。新舊復節點會同時連結同一節點一段時間，主要是為了避免發生斷電或是系統崩潰，造成無法恢復。此外這部分還增加了 ref-counter，也就是前面提到的計數器，主要是用來記錄被多少個節點指向自己。

- 清除：可參考下圖解說，當執行完複製或是相關行為後，會將複製的副本節點刪除，這時會先將該節點的父節點的計數器 (ref-counter) 標示為 0，並且一步步地往下更新各節點的計數器，並且最後在(c)步驟將計數器歸零的節點刪除。

透過這些行為可對應上述的三個特性。

## 特性
該檔案系統的 superblock 會在固定的硬碟位址，並且指向 樹根 (root)。BtrFS 可視為由多個 B-tree 組成的森林結構。
- subvolume：該結構負責保存用戶可見的文件和目錄的訊息，同時該結構也是一個 B-tree。該結構可以達成 Snapshot (藉由 COW 機制)。藉由 subvolume，可以將整個檔案系統切割成多個 subvolume，再整合成一個森林來進行管理，可參考下圖。

- snapshot：將現在目前的結構，包含連結關係等記錄起來，但不對結構做任何事，在需要進行復原 (recovery) 時，可藉由最新的 snapshot 來進行復原。
- checksum：檔案系統也會進行一致性檢查。
- shadow：基於 COW 的複製服務，並不會直接配置一塊位置並且進行複製，而是在有資料變更時才複製。
---

## F2FS
Flash-friendly file system
專門為 NAND flash 設計的檔案系統

一個 mobile device 上通常會有多個 flash chips ，所以需要透過專門的硬體 (controller) 和軟體 FTL (Flash Translation Layer) 將各種不同的 flash storage 來抽象並統一。通常會使用 random write 來存取，但會衍生一些問題如下：
- 頻繁地 random wrtie 會造成嚴重的碎片化
- 對 mobile device 來說，random write 負擔較大。
- 增加 I/O latency
- 減少裝置的 lifetime

因此可以透過 1. Log-structured FS 2. COW (Copy on write) 機制來解決。

:::info
快閃記憶體有兩種型別，NOR 和 NAND，NOR 常用在 BIOS ROM 裡面。而 NAND 則是用在常見的 SSD, SDcard ... 產品上，此外又有顆粒分別如 TLC, MLC, QLC 等

block access, 最基本的存取單位，讀取或寫入可以以 block 為 offset
抹除的話則是以 "頁" 為單位。
:::

### feature
1. 一種快閃記憶體檔案系統
2. 採用 log structured file system approach 實作，也有盡量避免一些在既有 log structured FS 的問題如 snowball effect of wandering tree, high cleaning overhead。^[2]^
3. 缺點: erase-before-write requirement,

### Design of F2FS
1. Flash-freindly on-disk layout
- segments, sections, zones
- 將 volume 切割成多個 fixed-size segements
- superblock: not changable, 基礎的分割 (partition) info
- checkpoint: 保持文件的狀態，正常無被破壞的 CP 必須在給定的時間儲存一致的 F2FS 狀態，並在突發事件如斷電等之後，該 CP 則成為 recovery point。使用兩個 segment，一個為 Last stable, 一個為 intermediate
- segment info table
- node address table
- segment summary area: 儲存所有區塊的資訊例如 parent inode number, node/data offset 等
- main area: 有兩種 type: data/node, 同一個 section 不會同時有 data 和 node。也就是說最小單位是 section。
- 示範如何完成 search "file":
1. NAT 會告知 root inode 位置
2. 在 root inode block 找名為 "file" 的 data block 和 inode number
3. 透過 NAT 找到該 inode number 的 physical 位址
4. 讀取該區塊得到 inode 的位址
5. 在 "file" 的 inode 重複 3,4 來找到要找的東西
3. Cost-effective index structure
- file structure: 傳統的 LFS 透過 inode 映射到 physical location，但 F2FS 透過 node 來擴展，node 總共有三種型態 inode (包含 file's metadata(file name, file size...)), direct node(包含data 的 block address), indirect node 包含另一個 node 的 address。使用 pointer-based 來實作 direct/indirect node，所以比起 LFS ，在加入一個 data 到 file(8MB-4GB or bigger than 4GB)，F2FS 都只需要更新一個 pointer。
- Directory structure: 一個 4KB 的 dentry 由 bitmap, two arrays of slots, names in pairs 組成。bitmap 代表每一個 slot 是否有效，slot 紀錄 hash value, inode number, len of file, file type。一個 directory 會建立 multi-level hash tables 來管理。 dentry 算是很重要的一個結構，會放進 cache 裡面當作快取，詳細的可以參考 ＶＦＳ 的一些實作。

4. Multi-head logging
用 6 major log areas 去分離 hot/cold 數據。如果使用 6 個來紀錄，則可依照表 1 去紀錄，如果用 4 個(user 可以自己決定要用多少個) 會將 cold 和 warm 合併起來。如果只使用 2 個來紀錄，則一個紀錄 node 另一個紀錄 data。傳統的 LFS 只使用一個 log area 來紀錄。

- direct node: 比 indirect node 更熱一點，因為他會頻繁地更新。
- indirect node: 紀錄 node IDs (可參考前面)，只有在新增或刪除的時候會更動。
- directory's direct node and data blocks 都被認為 hot。和常規 data block 相比，這兩者的寫入明顯比較頻繁(畢竟是目錄使用的)。
- data blocks 只要符合下列三者即可被認為是 cold:
- data blocks moved by cleanning: 可以參考 4. ，預設再經過 clenning 操作後，會維持一段時間。
- data blocks labeled "cold" by the user: 算是 F2FS 支援的操作。比較特別一點
- multimedia file data: 基本上很少會一直更動這類型的檔案，所以 F2FS 預設他為 cold。
最後在和 FTL 的配合上也有一些考慮，不過這邊就先跳過吧＝＝

4. Cleaning
用來整理 分散、無效的區段的 process。以 section 為單位來做清理。
有兩種整理的方法，front-ground 和 back-ground， front 只有在沒有足夠的 section 時才會出現。back 則會定期實施。3 steps:
1. victim selection: 在非空的 sections 中找尋目標 (section)
- greedy: 假設有 10 個 sections，在這十個中找擁有最少有用 block 的 section。所以 overhead 為該 section 中 valid block 的時間。在 F2FS 的 front-ground 使用這種方法。簡單來說就是以 utilization 來當作選擇的標準。
- cost-benefit: 以 utilization 和 age 來當作標準，應用在 back-ground 。 age 可以從 SIT 根據最後修改時間獲得，此外也可以藉由這個機制將資料標示為 hot / cold data。
2. valid block identification and migration: 挑選 section 後，要整理該 section 中的 block。
- F2FS 會使用一組 bitmap 來記錄每個 segment 的 valid 狀況 (放置在 SIT 內)，所以只要掃過該 SIT 即可。F2FS 在掃描整個 bitmap 後 (也會掃描 parent node block，parent node 通常是 valid)，會將 valid block 搬移至其他的 section，這樣就空出一整條完整的 section 。
- back-ground 的方法(有點神奇)，他不親自搬移 blocks，而是將 block 推到 page cache 並且標示為 dirty (也就是會被 page cache 淘汰，藉由 kernel 的機制)，等下次 page cache 不夠空間需要清除時，會將該 block 移動回去 FS。僅會在閒置時使用。
3. post-cleaning process: 在步驟2. 之後會將該 section 標記為 candicate (pre-free)，經過 CP 之後才會變成 free section。是為了避免斷電之類的事情。

5. Adaptive logging: 寫入的方式
傳統的 LFS 有兩種 policy 如下。
- normal logging: block 被寫入到 clean segment 中，並且以 sequential write 的方式寫入，不論提出任何 random 的要求。所以當 free space 耗盡的時候，就會一直發生 cleaning。
- threaded logging: 將 block 寫入到 hole (invalid, obsolete space) 到現有的 dirty segment 中。但因為是 random write，所以會降低 performance。
- F2FS 會實作上述兩種機制，並且動態的改變 policy，以 k clean section 當作判斷依據(k 為 pre-defined，通常為 5% of total sections)。 thread logging 有可能會造成不良的隨機寫入，但有 paper 證明在 flash 上不會有這問題。

7. `fsync` acceleration with roll-forward recovery
實作一個 CP 機制來確保一致性，會在下列程序後啟動 (triger) 1. 所有的 dirty node/page 都從 cache flush 到 Storage 中。2. 暫停所有寫入的活動如 create mkdir 之類的。3. 所有 FS 的 metadata 如 NAT SIT SSA 都被寫入到該寫入的位置。4. 完成上述後，才會開始建立 CP pack 並寫入下列資訊到 CP area 中
- header and footer: 會放在 pack 的頭尾，用來記錄版本號，每次更新都會疊加上去
- NAT and SIT bitmaps: 代表組成目前這個 pack 的 NAT SIT blocks
- NAT and SIT journals: 包含一些些最近更新的 NAT SIT 的 entry，避免頻繁地更新 NAT SIT。
- Summary blocks of active segments: 由 memory 中 SSA blocks 組成，在未來會 flush 到 SSA area。
- orphan blocks: 紀錄 orphan inode 的資訊。 orphan inode (會發生在有兩個 process 同時使用同一個 file ，其中一個 process 刪除該檔案，則該檔案會被標記為 orphan block)。



:::info
（不確定的解釋）
multi-level hashtable 感覺上有點像是 TST 但又不是，主要是藉由多層，每一層都會有對應得一個 block ，每一個 block 再往下去找。
但在 dentry 中並沒有提到如何處理 collision 的問題，也沒有提到說切割多大才算是好的切割方法。
:::

### Conclusion
目前主流的硬碟形式應該幾乎都是 SSD ，但既有的檔案系統設計對於 SSD 存取來說不是那麼友善。詳細的特徵可能要留到 Flash File System 解說。

### ref
1. wiki [link](https://zh.wikipedia.org/wiki/F2FS)
2. https://lwn.net/Articles/518718/
3. introduce to F2FS from samsung [link](https://www.linuxsecrets.com/elinux-wiki/images/1/12/Elc2013_Hwang.pdf)
4. original paper [link](https://www.usenix.org/conference/fast15/technical-sessions/presentation/lee)
5. http://linux.vbird.org/linux_basic/0230filesystem.php#harddisk

## Btrfs
由 oracle 在 2007　研發，預計是要替換掉 Linux 中 ext 系列的檔案系統。
一些基礎的設定:
- page, block: 4KB 連續空間。是通用的 size 在 Intel 架構上，在其他架構上可能可以更大，但就為了簡單來描述。
- Extent: 在 disk 上一塊連續的空間，對齊 page，所以長度為 page 的倍數。可以翻成"範圍"，因為檔案系統通常是連續分配的，所以用這個可以大幅減少管理檔案空間的開銷。(在一般的 ext 3上，每增加一個 1GB 的檔案就需要 256K 大小的空間存放 block 去管理)
- Copy-on-Write(COW): COW 傳統上會將資料即時寫回原始位置，但這個 COW 是將資料新建一個版本寫在其他位置，否則斷電或是系統崩潰，原始的版本也會受到汙染。

(這p 用的基本上是 b-5 tree)
### Design
1. COW friendly B-trees: 使用 B-tree 但維持下列三個特性
- top-down update procedure
- remove leaf-chaining
- use lazy reference-counting for space management: 因為 COW 的關係，所以會讓整個 tree 變成 DAG (有向無環圖)，因此用 ref-count 來記錄有多少個 pointer 指向自身 node。ref-counter 會額外放在 extent-tree，這樣更改的時候就不需要更改到 node 本身。


2. checkpoint:
3. BtrFS:
superblock 會在固定的 disk location，然後指向 root tree。
BtrFS 可以視為由 B-trees 組成的，解決了部分 ext 系列文件系統中的既有問題
- subvolume: subvolume 負責保存用戶可見的文件和目錄的訊息，同時該結構也是一個 b-tree。該結構可以達成 Snapshot (因為COW特性)。subvolume 達成了可以將整個 FS 切割成多個 subvolume ，再合起來變成一個 forest 來進行檔案系統的管理。
- Extent allocation tree:


:::info
Snapshot: 快照
假設對資料庫某一瞬間執行快照，可以保存該瞬間的檔案系統。

shadow:
Shadowing is a technique used by file systems like WAFL [D. Hitz et al. 1994] and
ZFS [V. Henson et al. 2003] to ensure atomic update to persistent data-structures.
It is a powerful mechanism that has been used to implement snapshots, crashrecovery, write-batching, and RAID. The basic scheme is to look at the file system
as a large tree made up of fixed-sized pages. Shadowing means that to update
an on-disk page, the entire page is read into memory, modified, and later written
to disk at an alternate location. When a page is shadowed its location on disk
changes, this creates a need to update (and shadow) the immediate ancestor of the
page with the new address. Shadowing propagates up to the file system root.
:::
###
### ref
[群暉系統的 btrfs](https://kknews.cc/zh-tw/news/jlzjl5y.html)
[synology introduction](https://www.synology.com/zh-tw/dsm/Btrfs)
[wiki](https://en.wikipedia.org/wiki/Btrfs)
[original paper](https://dl.acm.org/doi/abs/10.1145/2501620.2501623)
[shadowing and clone]()
[LWN.net The Btrfs FS](https://lwn.net/Articles/576276/)