# Log-Structured File Systems (LFS)
> 了解 F2FS 之前，一些 LFS 的筆記

## Background
大部分的 I/O 都是 random，對於 random read，我們現在有足夠大的 page cache 可以把大部分的 read 都 cache，但 random write 卻沒有很好的方案。

## Concept

Log-structured file system: 像 append log 一樣 sequentailly 的寫入 disk 最後面，不會對先前已經寫入的資料做修改。

把一堆 file system change 先 buffer 起來存在 file cache，再集結成一個 disk write operation 寫入 disk。所有需要用來管理 file system 的資訊都可以這樣操作。

## Design

### Write

現在來講講一些重要的 data structure。

在談 LFS 怎麼寫入資料前，先了解一下 *segment :*

- *******segment*******

LFS 把 disk 切割成固定大小的 *segment* (常見 512 KB or 1 MB)，剛剛前面有提到 LFS 會先 buffer 要進行的 file system change，而 memory buffer 滿了之後，便會以 *segment* 為 log 的單位大小寫入 disk。

和許多 filesystem 一樣，每個 file 有自己的 inode，存有這個 file 的 metadata + 這個 file 的前十個 block 的 disk address，對於超過十個 block 的 file，inode 會有 indirect block 的 address。

- *********inode map*********

不過在 UNIX FFS 裡面，inode 在 disk 上的位置是固定的，而在 LFS 則不是，他是像log 一樣被寫入的。這樣要怎麼知道每個 inode 在哪裡呢？LFS 維護了一個叫 *inode map* 的 structure。

*inode map* 和 log 一樣寫入，所以每個 segment 會有一個 *inode map*。

### Read

現在問題又來了，我們要怎麼找到 *inode map* 呢 ?

- *****************checkpoint region*****************

假如我們把 LFS 的 data structure 存在的位置分為 log (每次寫入的位置)、fixed，如果這個用來找 *inode map* 的位置也存在 log，那我們不就又要想辦法找它了 ? 所以想當然 *checkpoint region* 在 disk 上的位置是 fixed 的 !

不過因為 *inode map* 的容量不大，基本上我們可以把它 cache 在 memory 中 (在 mount 的時候) ! 所以基本上想要 access *inode map* 是不需要 disk access 的～

:::warning
:bulb: So far 我們可以成功獲得 *inode map* 的資訊了，那怎麼利用 *segment* 中的 *inode map* 去找到我們要的 inode 呢 ?
:::

每個 file 有個 inode number，假如今天要 locate 的 file inode number 為 i，就會先從 memory 中找到所有有 i 這個 index 的 *inode map*，這樣就可以找到所有 *segment* 中這個 file 的 inode 了 !

### Segment Cleaning

LFS 刪除舊資料的方法稱為 ***segment cleaning***，大致上分為三步

1. 把 M 個 segment 讀入 memory
2. identify live data (還在使用的，非過期的 data)
3. 把 live data copy 到 N 個 clean segment (空的，可以被寫入 data 的 segment)

M ≥ N，而原本那 M 個 segment 就會被標記成 clean

LFS 用了 data structure *segment summary block* 來判斷現在的 block 是不是 live

- *********************segment summary block*********************

每個 segment 有一個 *segment summary block* (特殊情況下會有多個)，用來記錄在這個 segment 中每個 block 的 file inode、在它屬於的 file 中的 offset、block address 等等。

這些資訊除了在 copy 有用之外，可以根據它的 file inode 或 indirect block 去看 block pointer 是不是還指到這個 block，進而知道它是 live or dead。


> 待補