# 新興記憶儲存系統元件設計

## CH1 Traditional Architecture

北橋負責高速I/O

- I/O Divice
- **Block Device** （這門課重點）
bIO，HDD 之類的，資訊存在 fixed size block，比如說 HDD 的 sector，每個 block 都有 address。
- **Character Device**
鍵盤之類的，傳送或接收 stream of characters，沒有 block structure
- **其他**
也不是所有I/O都是上面那兩種，比如說時鐘，不會用 block 存資料，也不會一直傳 character

- I/O handling mechanisms：什麼時候搬資料
- **Interupt I/O**
I/O裝置: 欸我要傳/收資料了，CPU你先暫停手邊工作處理一下
適合回應慢的I/O裝置，資料準備好了(HDD讀資料、鍵盤輸入)，避免CPU一直卡著等它
但因為要CPU暫時放下原本工作，所以會有 context switch 的 overhead
- **Polling I/O**
CPU: ㄟ你有要傳嗎? 你呢? 你呢? ...

- Device Interaction Methods：怎麼搬資料
- **Programmed I/O (PIO)**：CPU 自行處理
- **Port-mapped I/O**：有專門的 I/O 位址空間，和記憶體位址分開，I/O 埠（port）用獨立的位址編號，需要額外指令操作去存取
- **Memory-mapped I/O**：I/O裝置直接映射到記憶體位址空間，讀寫 I/O 就跟存取一般記憶體一樣
- **Direct Memory Access (DMA)**：不靠CPU，直接用DMA控制器在I/O跟memory間搬資料

- 基本概念：常用的資料給他用比較貴的快快memory

### DRAM Technology

- DRAM Cell：1 個電晶體 + 1 個電容器
- capacitor：儲存電荷，表示 0 或 1
- transistor：控制是否允許存取電容器
- 讀寫
- Word line
- 連接一整排 cell 的「控制閘」(transistor gate)
- Bit line
- 垂直線，連接一整欄 cell 的「電容」，當 word line 開啟某一列 cell 以後，就可以用 bit line 讀寫各 bit，一次讀一整列
- 讀完以後電荷流失，需要再寫回去；或是過一段時間電荷也會自己流失，要refresh
- 一般來說 in-memeory 的 data copy 需要讀到CPU的register再寫回memory。但有比較新的研究是用 refresh 的機制，直接用 memory 自己的 buffer 移資料，省下資料傳輸的時間

### Advanced DRAM Organization

像上面的矩形陣列會有好幾個，可以一次讀很多

- DRAM 的讀寫流程大致可分為兩個步驟：
- 尋址 (Access Time)： 讀寫頭先找到資料所在的儲存單元。這個過程會花費較長的時間，因為需要先找到正確的列位址 (Row Address)，再找到正確的行位址 (Column Address)，把一整 row 的資料存進 Sense Amplifier 裡。
- 傳輸 (Transfer Time)： 把需要的資料從 Sense Amplifier 傳輸到Data Bus，但沒辦法一次傳整個 row
- Burst Mode：當需要一次讀同個 row 的連續資料的時候，正常是要 (尋址$\rightarrow$ 傳輸) * n 次，但 burst mode 可以先把這 row 的資料存著，靠晶片一段一段傳輸，就不需要一直尋址了

### Disk

#### HDD
- HDD
- **sector**：扇形上的實體區塊，是最小單位
- **Block**：在做 I/O 時的單位，通常不只一個 sector 的大小
- Disk latency = ++rotational delay++ + ++seek time++ + ++transfer time++
- **rotational delay**：disk 轉到指定 sector 需要的時間
- **Seek time**：把探頭(disk arm) 移動到指定 track 需要的時間，一個 block 可能表示多個 sector
- **Transfer time**：讀寫資料進表面的時間
- I/O performance heavily depends on workloads
- **Sequential Workload**: Large reads/writes (e.g., 100MB) to a number of contiguous sectors.
- **Random Workload**: Small reads/writes (e.g., 4KB) to random sector locations on the disk.
- **Track Skew**
- 如果不同磁軌區的編號都從在同一個角度，在讀橫跨磁軌的連續資料時，探頭讀完這軌，移到下一軌的時候，很有可能要讀的下一個sector已經轉走了，就要再等轉一圈，所以會把不同磁軌的起始位置偏移一下
像下圖右本來16應該要在23的位置，偏移一下比較不會錯過
 

- **Zone Bit Recording**
外圈比較長，所以分成不同 zone (下圖用不同顏色表示)，同一個 zone 裡各軌的 sector 數一樣，但外圈的 zone sector 比較多，這樣可以善用外圈空間
因為外圈轉比較快，所以在不同 zone 的時候要用不同的速率讀寫資料

- **Disk Caching**：Disk 內部會有一小塊記憶體用來 cache
- Read Caching：讀的時候可能會把一整個 track 都 cache 起來
- Write Caching
- ++Write-Through++：每次更新都寫回
- ++Write-Back++：要被踢出快取再一次寫回

- **Disk Scheduling**
- **FCFS**：First Come First Serve，照順序讀取，效能不佳
- **SSTF**：Shortest Seek Time First，每次選擇距離目前磁頭位置最近的請求，有 starvation 的問題
- **SCAN**：電梯演算法，磁頭固定往一個方向移動，沿途處理請求，直到磁碟的盡頭後，再反方向移動並處理請求
- **LOOK**：一樣是電梯演算法，但到最後一個請求時就回頭
- **SPTF**：Shortest Positioning Time First，跟 SSTF 很像，但 SSTF 只考慮 seek time（磁頭移動的時間，就磁軌遠近），SSTF 還考慮 rotation delay
e.g. 磁頭移到 A 軌可能比較快，但還要等那個 sector 轉過來，可能去找比較遠的 B 軌上的 sector b 還比較快
但因為硬體才知道實際磁軌分布，所以這在硬碟上實現，而不是 OS
這才是我們目前實際上使用的排程

#### Flash Memory

- Why Flash Memory
- 體積小
- 低功耗（不用轉磁碟）
- 特性
1. Write-once：不能覆蓋改值，要改值必須先抹除（erase 是設成 1）再重寫
2. Bulk-erasing：要刪區塊中的某個值，必須連帶把整個區塊抹掉
3. Limited erase cycle：抹除資料會損耗有限壽命

- SLC、MLC、TLC、QLC：表示每個單元可以表示 1、2、3、4 個 bit。（Multi Level Cell）

## CH2 Non-volatile Memory

- What is Memory？
- 可以直接被 CPU 定址（存取）的是 memory
- 不能直接被 CPU 定址，而且 persistent（資料可以永久儲存）的是 storage

- NVDIMM-N：用 DRAM 跟 Flash 兜出來的 NVM，斷電以後用電容供電把 資料存進 Flash

### Why NVM

- Limitation of Flash
- 讀寫壽命短
- 寫入比讀取慢很多（500μs~1ms）
- page-based access 跟 block-based erase，無法讓 CPU 直接定址（？？？）
- Out-place-update property: No write-in-place（？？？）
- Limitation of DRAM
- small cell density (10nm)
- 耗能，要 refresh
- 揮發性

### 不同種類的 NVM

1. **FRAM** (Ferroelectric RAM)
2. **MRAM** (Magnetoresistive RAM)
3. **PCM** (Phase-change Memory)
4. **ReRAM** (Resistive Random Access Memory)

#### FRAM

鐵電效應，跟鐵磁性無關，是指材料具有可以被外加電場反轉的電極性

FRAM 的 cell 類似 DRAM的電容，給電場來改變狀態，只是不需要電場來維持電極性

讀寫也類似，給一個電場，如果 cell 的電極跟電場相反，就會被反轉，並釋放電荷，產生比較多的電流

判斷是普通電流還是加料電流就能知道狀態（跟老師說的電阻無關）

讀取是破壞性的，跟 DRAM 一樣要寫回去

主要用在嵌入式系統


#### MRAM

寫：改變磁極方向
讀：跟永久磁鐵方向相反的話電阻比較大

主要用在人造衛星，因為可以抗輻射線，不然其他種類的容易被輻射（帶電粒子？）打到 bit flip

（不懂為什麼垂直比較好）

MLC 可以透過把每個 cell 的 free layer 分成 Hard bit、Soft bit，強電場會把兩個都改掉，弱電場只會改掉 Soft bit
（都可以分兩 part 了為什麼不直接切兩個 cell）


#### PCM

寫：高溫快冷卻會是亂亂態，中溫慢冷卻會是晶格態


#### ReRAM

反正就是可以改變每個 cell 的電阻值，甚至可以切成數十種狀態

可以用來加速 AI 的 MMV 運算（矩陣乘向量），原理是給 cell 陣列特定的電流改變狀態就等於相乘（？）


#### 比較

容量可以很大了，主要問題是 **Endurance**，DRAM 的讀寫次數可以到 10^15^，NVM 還比不上

所以目前 NVM 還是跟 DRAM 混用，用 memory controller 或 CPU，決定資料要放哪個 memory，把 DRAM 當作 buffer 或 cache，放需要常常讀取的資料，不更新的再寫入 NVM

- DRAM 壽命長
- NVM cell density 高，容量大


### Properties and Issue

NVM 的優缺點

#### 優點

- 相較於 DRAM
1. Non-volatility
2. Zero static power consumption
3. Small Form Factor（cell 比較小）
- 相較於 Flash
1. 快
2. 耐用（QLC: 100 v.s PCM: 10^9^）

#### 缺點

1. **Write Endurance**：壽命還是比不上 DRAM
2. **Data Retention**：SLC 問題不大，但 MLC、TLC、QLC 要在一個 cell 塞多種狀態，同樣的閾值電壓就要被切得愈細，會容易被干擾產生 error bit
3. **Security Concern**：因為非揮發性，所以記憶體被人家拔走可以還原目前電腦的狀態，有資安問題

### 應用 - 嵌入式系統

嵌入式系統不需要太大的 memory，且有低功耗需求，適合用 NVM

為了持續運作，有些嵌入式系統會用太陽能之類的，但不太穩定

藍色是 CPU 在運作的時候會耗電，耗太多就沒電，工作就被迫中斷，如果用 DRAM 就需要從頭來，甚至永遠無法完成，但 NVM 就可以接續做

#### Inconsistency Issue with NVM

斷電以後，資料本身不會消失，但 CPU register 會消失，所以會忘記執行到哪裡，復電後用舊資料重跑 code 就會出問題

##### checkpoint

其中一個解法是設 **checkpoint**，在某些地方保存狀態，掉電之後可以從這恢復


##### task

另一種是把程式拆成許多短小的 task，盡量讓它在掉電前能做完
而 task 要是 atomic，掉電就重做，以及要確保重做不會資料不一致

#### Constraint

- **Atomicity Constraint**
就算資料沒有不一致，但有可能是外部資訊在斷電的時候更新了，復電之後程式就會沒更新到
所以 Atomicity Constraint 要求一個 task 必須要麼完全執行完，要麼完全不算數

- **Timeliness Constraint**
Task 必須在一定的「時間內」完成，否則就失去意義

- **Reactivity constraint**
要頻繁做

- **Asynchronous burst constraint**
事件來了就要馬上做

小電容充電快放電快、大電容相反，適用情況不同

一個可以跟根據不同任務需求動態配置供電的平台

## CH3 Flash memory & Management

一種 non-volitle storage，隨身碟、SD 卡、SSD... 都是

### 分類

- **NOR flash**：貴，每個 cell 都各自連到 Source，可以 bitwise 的讀寫，所以可以支援在 storage 的 execute in place
但因為每個 cell 都比較大，所以同體積的話，容量比 NAND 小
e.g. switch 的遊戲卡
- **NAND flash**：便宜，需以 page（word）為單位讀取（為啥？？）（該 bit 是否導通取決於該 word 上的 gate）

以下講的都是 NAND

### 構造

- **Chip**：每個 flash 通常會有 4~8 個 chip，Each chip has its own controller and works independently.
- **Plane**：A chip contains 2 or 4 plane. Unit of multi-operation.
同一個 Plane 內的兩個 Block 不行同時寫入。
- **Block**：The basic unit for an ++erase++ operation.
(32768 blocks for one plane)
- **Wordline**：The basic unit for a ++write++ operation.
一條 Wordline = 一個 Page
(96 wordlines for one block)
- **Cell**：The basic storage unit.


黃色的 spare area 用來存 ECC（Error Correction Code）、LPN (page number)


### 特性

- **Write-once property**（Page）
雖然可以對 page 讀寫，但只能寫入，不能更新。要更新要 erase 再重寫
- **Bulk erasing**（block）
要 erase 要整個 block 一起 erase

也就是說，要更新 page 的值需要整個 block 都 erase 重寫

以下根據物理特性講解為什麼 flash 會有這樣的性質

### Cell

#### SLC（Single Level Cell）

一個 Cell 存 1 bit，有負電荷 $\rightarrow$ 難導通 $\rightarrow$ 0


#### MLC（Multi Level Cell）

把電壓切更細，區分多種狀態


#### SLC v.s. MLC

SLC 讀寫比較快（狀態少？）、壽命長
MLC 容量大


##### Hybrid Architecture

結合 SLC 的高速與 MLC 的低成本
頻繁寫入的 hot data 放 SLC 區塊，cold data 放 MLC

- **Heterogeneous hybrid**：真的放了 SLC + MLC 晶片
物理異質、速度快、成本高
- **Homogeneous hybrid**：用 MLC 假裝成 SLC，只讀最高與最低的狀態
邏輯異質、速度中、成本低

##### Revived Blocks

達到壽命：永久壞了，或是 Bit Error Rate （寫入的資料與讀出來的不一樣，這邊的 rate 應該不是時間上的，而是說一個 page 裡錯誤 bit 的比例）超過 ECC 能處理的範圍

在 Homogeneous hybrid SSD 架構中，達到壽命的 MLC 可以當成 SLC 繼續使用，延長壽命

把壞掉的 MLC（DATA）移到 FREE，用來替換壞掉的 SLC（BUFF）

### Cell Operation

#### Program

指的是往 floating gate（FG）中加入電子，使導通的閾值提高的操作


因為 FG 中的電子數量是一個機率分布，而且每個 cell 的品質也不一樣，不能確定要多少給多少電子才能使 cell 跑到下一個 state，所以需要 **ISPP**（Incremental Step Pulse Programming），逐步給一些電子，確認狀態、給一些電子，確認狀態

#### Read

給一個中間值的電壓，看有沒有導通就知道當前狀態了，如果是 MLC 就需要給多次電壓確認狀態，給一個中間電壓可以確認是 erase、P1 或是 P2、P3，再給一次就可以確認到底是哪個（二分搜）

#### Pass-through

因為各 word 的 同 bit 是串聯的，所以除了指定 wordline 的電壓要給中間值，其他 wordline 都應該要給高電壓讓 cell 導通，才能讀到指定 wordline 的狀態

#### Erase

在 substrate（基板），施加反向高電壓，利用 Fowler–Nordheim Tunneling（穿隧效應），把電子抽出浮動閘

因為同個 block 的所有 cell 都共用一個 substrate（製程物理限制）所以要 erase 就會整個 block 都 erase

（而 NOR flash 因為每個 cell 都有獨立接線，所以可以對特定 cell 施加電壓避免電子被抽走，屏蔽不該 erase 的 cell，達到指定 cell erase $\rightarrow$ 指定 cell 讀寫）

由於每次抹除都會造成氧化層劣化，一個 block 通常只能抹除數千次（SLC 約 10^5^ 次，TLC 約 10^3^ 次）

### Flash Memory Reliablity

As NAND flash scales up and stores more bits per cell, the reliability and endurance of flash memory decrease.


用高溫烤模擬時間考驗


#### Error Types

- **Read errors**：++Continuously read++ a given block.
- **Program interference errors**：Extra electrons injection when ++programming neighbor cells++
- **Retention errors**：Charge stored in the memory cells can leak away ++over time++
- **Erase errors**：擦不乾淨

##### Read Error

當頻繁讀取某 cell 時，附近的 cell（尤其是同一頁或隔壁頁）會被反覆施壓，
這些 V_pass 雖然比 program 電壓低，但長期下來仍可能導致閾值電壓偏移


##### Program Interference Errors

對 cell 高壓寫入（Program）的時候電場會影響到附近 cell，尤其是對精細的多 bit cell（MLC/TLC）特別嚴重

主要是會讓鄰居 cell 多電子（閾值電壓升高），所以對本來就多電子的01、00影響較小，所以可以用一些軟體的方式讓儲存的資料比較多是 01、00，減少 Program Interference Errors

##### Retention errors

電子隨時間漏掉，所以對 01、00 影響比較大
在 MLC 中，因為一個 cell 表示兩個 bit，所以一個 wordline 控制的是兩個 Page，分成 LSB Page、MSB Page
（Least Significant Bit、Most Significant Bit，但不知道為什麼這邊 LSB 是左邊的bit）

從下圖可以看到， LSB page 比較不容易受 Retention errors 影響，所以 archive system 把資料搞成 11 10 比較不會衰退錯誤

###### Optimal Read Reference Voltage (OPT)

既然閾值電壓會偏移，那 V_read 也可以一起偏移修正


###### Flash Correct-and-Refresh (FCR)

Flash Correct-and-Refresh 是一種讓控制器定期用 ECC 檢查並重寫資料的機制，目的是防止資料因漏電（retention loss）變成不可修復錯誤，以「少量寫入」換取「長期可靠性」。

顧名思義分成兩步：Correct（糾錯） + Refresh（重寫）

1. 把一個 page 的資料讀出來
2. ECC correction，如果發現錯誤的 bit 數接近 ECC 能 handle 的上限，那就觸發 Refresh
3. Refresh：寫入新資料，有兩種方式：
- **reprogramming**：直接 In-place program 成正確資料（ISPP），比較有效率，但有 Program Interference Errors 的風險，而且如果 Cell 不是電子流失的 Retention errors，而是獲得電子的 Program Interference Errors，那就沒辦法用 program 注入電子更正了
- **remapping**：直接把整個 block 的資料都搬到新的 block，雖然 cost 高，沒效率（為了一個 page 搬整個 block），但是最安全，避免重複寫入老化 block

有些步驟有改進版作法

- ++Adaptive-rate FCR++：第 2. 步可以是控制器根據多項參數決定 refresh 速度
- ECC 修正錯誤次數
- block 使用年限（P/E 次數）
- 溫度（高溫 → 漏電快 → 要更頻繁 refresh）
- 資料重要性（metadata 比一般 data 更常 refresh）
- ++Hybrid reprogramming/remapping-based FCR++：第 3. 步可以混用，控制器根據 block 健康狀況來決定要 reprogram 還是 remap

##### Erase errors

製程導致的缺陷或是 P/E 對氧化層的磨耗，導致電子被困在氧化層，無法擦除乾淨

從下圖可以看到，拉長 erase 時間沒用，多 erase 幾次比較有效


### Flash Translation Layer

因為 Flash 有一些麻煩的限制跟特性

- 無法覆寫（只能先擦再寫）
- 擦除單位大（Block），寫入單位小（Page）
- Block 有壽命限制（P/E 次數有限）
- 寫入干擾、retention 問題，需要均勻使用與管理錯誤

所以不讓作業系統直接存取 flash，而是用 **Flash Translation Layer** 包起來

FTL 負責：

- **Address Mapping**：把主機的邏輯地址（LBA）轉換成 Flash 的實體地址（Physical Block/Page）
- **Garbage Collection**：回收被舊資料佔用但已無效的 block
- **Wear Leveling**：平衡各 block 擦寫次數，防止局部過度老化
- **Bad Block 管理**：偵測並避開壞掉的 block
- **Error Management**：與 ECC、FCR 協同工作以確保資料可靠性


#### Address Mapping

OS 會有一個 Address Translation Table（in main-memory）把 Logic block address 轉成實體的 page address

而這邊需要關注的點是，因為要更新 page 的值需要整個 block erase 重寫，所以該如何設計並維護 ATT

##### Page-Level

直覺上，ATT 紀錄的內容會是 page to page

`LBA: (blockID, pageID)`

當 page 值需要更新的時候，可以直接把值寫入一個新的空白 page，並更新 ATT，再把舊的 page 標記為 invalid，給 GC 去回收，這樣就不用每次寫入 page 都要 erase 整個 block

但是這樣 ATT 要記錄的 entry 個數 = page 數，很佔空間
1TB 的硬碟需要 1GB 的 memory 來轉換位址，誇張


##### Block-Level

ATT 只記錄 virtual block address（**VBA**） 對應到的 PBA

`VBA: LBA`

而 VBA = LBA / #page

舉例來說，給定 LBA 為 1011

1. 算出這 address 屬於哪個 virtual block：VBA = LBA / 8 = 126
2. 根據 ATT 找出這虛擬 block 對應到哪個真實 block： n
3. 算出這 LBA 是這 block 的第幾個 page：LBA % 8 = 3
4. ok，所以 1011 對應到的是第 n 個 block 的第 3 個 page

這樣一來 ATT 的 entry 數就只需要 block 數這麼多，省了超多倍

而當 page 的 data 要更新的時候，直接把整個 block 的非空 page 寫入新的空白 block，並更新 ATT，map 到新的 block，整個舊的 block 留給 GC

由此可見 Block-Level mapping 雖然省空間，但更新一個 page 就要寫一整個 block（Write Amplification：實際寫入的物理資料量是寫入資料量的多倍），更新開銷大


##### NFTL Type1 (Block-level)

為了解決 Block-level mapping 的 WA 問題，NFTL Type1 的 block 會有一個 pointer 指向下一個 block，形成 block chain

當要 ++更新++ / ++讀取++ page data 的時候，就沿著 block chain 找到 ++第一個 free page++ / ++最後一個 used page++，不需要寫入整個 block

但缺點是，只有某個 page 是 hot data 的時候，會一直找新的 block，占用到很多空白 block，那些 block 的空間使用率就很低，
而且這樣到時候 GC 要回收的時候要 erase 很多空白 page 很多的 block，平白消耗壽命


##### NFTL Type2 (Block-level)

類似 Type 1 但不會一直延伸下去，而是用每個 Primary Block 都有一個 Replacement Block 來存更新的資料，

ATT 裡多用 4 個 bytes 放 Primary Block 跟 Replacement Block，每個 PB 都有專屬的 RB，當寫入時發現 Primary Block 有資料了就寫到 Replacement Block 中第一個 Free 的 page，讀取則是需要遍歷 RB 看 spare area 中的 LBA 是不是自己要找的那個 page。遍歷完都沒有的話再去看 PB


##### FAST (Hybrid)

結合 block-level 跟 page-level

寫入資料是寫到 ++block-level++ 的 **data blocks**，
更新資料是寫到 ++page-level++ 的 **log blocks**

就像 Type 2，只是 read 的時候不用遍歷 Replacement Block，而是把 LBA 跟 log Blocks 的對應關係放在另一個 page-level 的 table，而且每個 data block 共用同一個 log block

log block 寫滿再 **merge** 回去，有兩種情況

- **Switch Merge**：Log block 含有該 Data block 的所有 pages（即該 block 全部被更新）
很快，直接把 Log block 改名成新的 Data block，舊的 Data block erase 掉
- **Partial Merge**：Log block 只更新了部分 pages
把 Data block 未更新的 pages + Log block 的新 pages，複製成新的 block


##### DFTL (page-level)

原本的 page-level 做法要在 memory 存放所有 LPN 跟 PPN 的對應關係，太大了

Demand-based FTL，把這個 page-level 的 map 放在 flash 裡，要轉址的時候，再用 memory 裡的 block-level 去找對應的 map

並且還能 cache

分為幾個元件

- **Traslation Blocks**：存放 translation pages，紀錄 LPN:PPN 的對應關係，++放在 flash 裡++
- **Data Blocks**：就 flash 的 blocks，裡面放 pages，紀錄 Data
- **Global Translation Directory (GTD)**：放在 memory 裡，Block-Level 的對應關係，紀錄要去哪裡找 translation block（以便找 data block）
- **Cached Mapping Table (CMT)**：把 translation page 快取到這 memory 中的 table，有在 CMT 找到的話就可以跳過 GTD $\rightarrow$ Translation page $\rightarrow$ Data page

也就是說步驟如下：

1. memory 查 CMT 快取，有的話直接跳 4.
2. 沒有的話，去 GTD (memory) 看要去 flash 的哪裡找 Translation page
3. 查 Translation page 看要去哪裡找 Data page
4. 在 Data page 取資料

下圖為 CMT 沒找到且滿了的情況，(2) ~ (6) 是在把舊快取資料 write-back（更新需要複製整個 block 並更新 GTD）

##### FTL Comparison


#### Garbage Collection

##### Why need GC

當更新操作累積後：

- 舊版本的 pages 會變成 invalid pages
- 有效與無效 pages 混雜在同一個 block 中
- 該 block 就無法直接 erase
- 需靠 GC 來移開有效資料並 erase 釋放空間

##### Typical GC Procedure

1. ++選擇一個 victim block++：通常挑 invalid page 比例高的 block（回收效率高）
2. ++移動有效 pages++：把 live pages 複製到一個新的 free block
3. ++更新 mapping table++：將搬移後的新位置更新到 FTL 的對應表（例如 LPN:PPN）
4. ++擦除 victim block++：執行 block erase（把所有 bits 重設為 1）
5. ++釋放該 block++：供未來寫入使用

##### Strategies of victim block selection

有很多種，這邊介紹幾個

| 策略 | 主要依據 | 優點 | 缺點 | 複雜度 |
| ------------ | ------------------- | ----- | ----------------- | --- |
| **Random** | 無 | 實作最簡單 | 效率最差 | ★ |
| **FIFO** (RR) | block 分配順序 | 穩定、簡單 | 無法適應實際 invalid 狀況 | ★ |
| **Greedy** | invalid page 比例 | 效率高 | 磨損不均 | ★★ |
| **Cost-Benefit** (CB) | invalid ratio + age | 高效且均勻 | 複雜度高 | ★★★ |

而 CB 綜合評估 invalid ration 跟 age 的公式有好幾個，常見的是：

$\text{CostBenefit}_b = \frac{\text {Benefit}}{\text {cost}} = \frac{1-\mu_b}{2\mu_b} \times \text{age}_b$

- $\mu_b$：block $b$ 中的 valid page ratio
- $\text{age}_b$：block 自上次擦除以來的時間
- $2$：讀舊 page + 寫入新 page = 扣兩分

總之，當 block 的 ++有效資料比例低++ 且 ++很久沒清理++ $\rightarrow$ 優先被選中

##### Design Issues and Discussion

- **Scalability**: GC 本身所需維護的資訊（block age 之類的）要少，這樣在超大 flash 中才好用
- **Flexibility**: GC 策略應該要能適應性，能夠根據不同的工作負載或儲存環境自我調整行為
- Shifting access patterns：有時大量順序寫入（像錄影）、有時隨機更新（像資料庫、metadata）
- Heterogeneous storage media：混用不同型態 NAND 的 flash（e.g. SLC + MLC）

##### Wear-leveling

flash 擦除有壽命限制，所以 GC 要避免一直擦同一個 block

###### Dynamic Wear Leveling

選擦寫次數少的 free block 來寫
缺點是 cold block 不會被 GC free 所以不參與擦寫

###### Static Wear Leveling

把 cold data 移到磨損較多的 block，自然就會比較少 erase 它

###### Dual Pool Wear Leveling

將所有 block 分為 ++Hot Pool++、++Cold Pool++ 各自內部進行 wear leveling

當 hot block 的平均擦寫次數與 cold block 差距過大，從 cold pool 中挑出擦寫次數最低的 block 加入 hot pool，重新平衡兩個 pool 的壽命


###### Block Erase Table (BET)

在大容量 Flash 裡，如果要為每個 block 都維護一個 erase counter佔用太多 memory

因此，BET 用 bit array 方式壓縮紀錄：
每一個 bit 不對應一個 block，而是對應一組（例如 2^k^）個連續 blocks
並只記得「這組 blocks 是否有人已經被擦過」，而不是「擦了幾次」

- **BET**：一個 bit array（每個 bit 代表一群 blocks）
- **e_cnt**：自 BET reset 以來，所有 blocks 的總擦除次數（global counter）
- **f_cnt**：BET 中值為 1 的 bit 數（代表有多少區域被擦過至少一次）
- **T**：閾值，用來判斷擦寫是否「過度不平均」

每次要 erase 時，e_cnt += 1、BET 對應的 bit = 1
如果 e_cnt / f_cnt > T $\Rightarrow$ 擦寫不平均，找 BET 為 0 的 block 來擦，e_cnt += 1
如果已經沒有 BET 為 0 的 block $\Rightarrow$ 全部 reset 歸零


###### Progressive Wear Leveling

一開始不太做 WL，之後慢慢增加


###### Error-Rate-Aware Wear Leveling

因為每個 block 的物理性質不一樣，有的可能就先天超耐磨（CNM），只看 P/E cycles 不一定能正確表示其壽命，所以不如直接看 Bit Error Rate

## CH4 Next-generation Hard Disk Drive

便宜容量大，好用繼續用，但想提高單位容量


**Conventional Magnetic Recording Technology**

有兩種傳統的技術，垂直的 cell 比較小


但想繼續提升單位容量的話，縮小 cell 有極限，太小會有 superparamagnetic effect，總之就是顆粒太小會抵抗不了干擾之類的

**New Magnetic Recording Technologies**

有一些新技術可以提升容量，但目前主流是 PMR


**New Track Layout**

用改 track layout 的做法來提高單位容量相對簡單，因為符合目前主流架構，製程什麼的不用大改


### Shingled Magnetic Recording (SMR)

把 track 之間重疊，增加密度
（至於圓周方向的偏移，GPT 說是什麼補償磁頭磁場形狀與控制精度，母災）
因為 read head 比 write head 小，所以可以對細細的地方讀就好，不用改什麼
只是要寫的時候，因為會覆蓋後面軌道，所以後面的軌道也要一起順序寫入，覆寫下去

為了不要太大的 WA，所以把 tracks 分成 zone ，有 track 要更新的話，只有 zone 內後續 track 要順序寫入（中斷點的概念），變成有點像 flash memory 的 block 一樣，要整區覆寫

但要整區覆寫的話， WA 還是很大，所以可以改用 out-place update，就是不原地更新，而是複製到別的地方，之後再 merge，就像 FTL 的 log-block。並把原來的標成 invalid。那這樣資料跑來跑去就需要維護 ++address mapping++，也需要 ++GC++ 把 invalid 的區塊釋放


**Persistent Cache**

Persistent 表示 non-volatile，可以是 HDD 本身（CMR）、flash、或其他 NVM

總之就是因為 SMR 是 ++append-only++，只能順序寫入，所以搞一個可以隨機寫入的 write buffer，要更新資料都寫在 Persistent Cache，Cache 要滿了（++Lazy Cleaning++）或是 disk 閒置時（++Aggressive Cleaning++）再把 cache 內的資料寫回 SMR zone
（那不就是 FTL 的 log block ?）

常見做法是在把 SMR 外面幾個 track（轉速快、讀寫快）當作 Persistent Cache，透過維護 **extent map** 來支援隨機寫入


實驗觀察，SMR 因為都是 write append，所以反而還比 CMR 穩定，只是 Persistent Cache 滿了就需要大量時間來寫回 SMR zone，而且久到有點嚴重

 

如果是讀讀寫寫，因為 Persistent Cache 在外圈，所以讀內圈會比較花時間
（OD：outer diameter 就外圈的意思）


### Who Should Take Care of SMR

3 models

- **Host-Managed (HM)**：主機（OS/FS/Driver）完全負責 zone 管理，主機必須嚴格依序寫入每個 zone，寫入模式明確、I/O latency 可預測，但是軟體修改成本高。
- **Host-Aware (HA)**：主機「知道」底層是 SMR，但不一定要順序寫，可以自由寫入，磁碟 firmware 會幫忙整理（會變慢）。但若遵守 sequential zone write，效能會比較穩定。折衷方案，效能與相容性平衡。少見
- **Drive-Managed (DM)**：全部交給硬碟內部 firmware 處理，主機不知道底層是 SMR，對主機完全透明，不需任何軟體修改。但因此效能不可預測，尤其在 random write 下效能不穩定

接著介紹了這三種 model 的研究的 case study，但我就懶得細讀了

- **DM-SMR: SMaRT**
SMaRT 之於 HDD 就像 FTL 之於 Flash，總之就是把 SMR 包起來，讓主機當 CMR 操作
操作單位是 Track（zone 太大），就像 FTL 的 Block，一樣就是 address mapping、GC 那些
- **HA-SMR: VPC**
比較沒什麼特別的，Persisten Cache 之類的，把順序寫的資料直接寫入，隨機寫的資料先快取
- **HM-SMR: HiSMRfs**
HM-SMR 會比較需要大改，All of layers must be SMR compatible，而且下層不能因為排程之類的改動 host 決定好的 I/O 順序
還有一些 Meta data 之類的，之後 file system 會再講吧

## CH5 Zoned Namespace Storage Drives

### Peripheral Communication

電腦跟周邊裝置的通訊


- **Common Peripheral Interface**
- **USB (Universal Serial Bus)**：幾乎可以連接任何裝置，從鍵盤、滑鼠到外接硬碟和 Webcam
- **HDMI (High-Definition Multimedia Interface)**：影、音訊號同時傳，用於多媒體應用
- **PCI (Peripheral Component Interconnect)** and **PCIe (PCI Express)**：用來連接高速的內部週邊，如顯示卡 (Graphics cards)、網卡 (Network cards) 以及儲存控制器 (Storage controllers)，是++系統的骨幹++

#### PCI

Parallel bus architecture，資料同時透過多條並行的線路傳輸

所有的裝置共享同一條頻寬（如圖右側所示，裝置並聯在 Bus 上）。當裝置變多時，訊號干擾和時序同步會變得非常困難，限制了速度提升

#### PCIe (PCI Express)

Serial architecture，PCIe 改用點對點 (Point-to-Point) 的序列傳輸（如圖左側所示，每個裝置透過 Switch 獨立連線）

雖然單一通道看起來是一次傳一個 bit，但因為沒有並行訊號干擾的問題，頻率可以拉得非常高，且每個裝置享有獨立頻寬，不會被搶佔

PCIe 透過增加「通道」數量來倍增頻寬，常見規格有 x1, x4, x8, x16。x16 通常用於顯卡


（挺酷，為了加速反而是從 Parallel 改成 Serial，但不太懂他們的架構）

而 **SATA** 接口則是因為 PCIe 通道珍貴，而 HDD 又不需要那麼高速，所以設計出 SATA 通道來用。一條 PCIe 通道可以拉出 4~6 個 SATA 接口

### NVMe (NVM Express)

PCIe 是物理傳輸通道，NVMe 則是專為 SSD 設計的邏輯介面標準，可以想成是 OS 用來操作 SSD 的 API（而 FTL 則是這 API 背後的實作）

| 層級 | HDD | SSD |
| --- | --- | --- |
| **Protocol** | AHCI | NVMe |
| **Interface** | SATA | PCIe |

AHCI 是為了單執行緒的機械手臂設計的；NVMe 是為了多核心 CPU 與多通道 Flash 的高並發設計的

- **NVMe 1.4**：
- 引入 **HMB** (Host Memory Buffer)：
允許 SSD 借用電腦主機的一小塊 DRAM 來 Cache，讓沒有內建 DRAM 的便宜 SSD 也能有不錯的效能
- 增強 Multi-path I/O 和錯誤處理
- **NVMe 1.4b**：
- 引入 **Zoned Namespaces (ZNS)**，進一步提升資料中心和企業級應用的效率
- **Unpredictable latency**：因為 SSD 有 GC 機制進行額外擦寫，所以會有非預期的延遲，有些少量操作會面臨大量延遲 (**Tail Latency**)

- **Multi-streamed SSD**：將不同性質的資料「分流 (Stream)」，來減少傳統 SSD 的 WA 問題。
主機端根據資料的更新頻率或用途，將資料分成不同的 "Streams"，並標上 StreamID，SSD 內部的 FTL 接收到指令後，根據 StreamID 將資料寫入對應的物理區塊

- **Open-channel SSD (OCSSD)**：用主機軟體管 SSD
把原本寫在 SSD firmware 裡的 FTL 核心邏輯全都移到 Host 的 software 裡，讓主機自行管理 SSD，主機可以直接看到底層物理結構，以此達到最高效率，且因由主機決定何時 GC，所以解決了 Unpredictable latency

### ZNS

OCSSD 給主機的負擔太重，所以後來的 ZNS (Zoned Namespaces) 採取了折衷方案：
- 保留好處： 像 OCSSD 一樣讓主機決定資料放置 (Data Placement)。
- 解決壞處： 把底層的物理細節 (如壞塊管理、ECC) 藏回去 SSD 內部，只暴露標準化的 "Zone" 介面

#### ZNS 的核心目標

將 SSD 的「物理限制」標準化，變成「邏輯規則」告訴主機，透過將資料分 Zone 管理，降低 WA，提升平行度，並簡化 GC

- 傳統 SSD (Block Interface)： 假裝自己是可以隨便亂寫的磁碟，結果內部 FTL 忙著做垃圾回收 (GC) 來擦屁股，導致效能忽快忽慢。
- ZNS SSD (Zoned Interface)： 誠實地告訴主機：「我的物理特性就是只能順序寫入，請你配合我。」


#### ZNS 運作機制

ZNS 將整個 LBA 空間切割成多個固定大小的區域 Zones

- **Sequential Write Constraint**
- 每個 Zone 都有一個 **Write Pointer**
- HOST 寫入資料時，必須從 WP 的位置開始寫，寫完後 WP 會自動往後移
- HOST 不能像傳統 SSD 那樣隨機覆寫 Zone 中間的資料，若要重寫，必須先 **Reset** 整個 Zone，讓 WP 回到起點
（跟 HDD 的 SMR 很像）
- 因此在單一個 Zone 內部，LBA 的順序必須高度對應到底層 PBA 的物理寫入順序
- ZNS 分成兩種寫入方式
- **Regular Write**：傳統的 Write 指令，必須精確指定 LBA
如果一次送多個指令，無法保證它們到達 SSD 的順序，可能會導致寫入位置錯誤（不在 WP 上），因此一次只能送一個指令。這會嚴重拖慢速度
- **Zone Append**：
主機不指定 LBA，只說「我要寫到 Zone X」
SSD 接到指令後，自己決定把它放在該 Zone 的當前 WP 位置，寫完後再回傳「我把它存在哪裡」給主機。
因此允許多個寫入指令同時發送，大幅提升並行效能

#### Smart Data Placement

只要主機端應用程式（軟體）利用 ZNS 的特性，聰明地安排資料寫入位置，
硬體（SSD）就可以少做很多事（GC、搬移），最終實現容量更大、壽命更長、且速度極其穩定的儲存系統

- **Reduced Write Amplification**
因為主機保證是順序寫入，SSD 內部不再會有「資料碎片」，所以不須 GC。當一個 Zone 要被回收時，主機可以直接下令 Reset，完全不需要 SSD 內部做搬移資料的 GC
- **Minimal Garbage Collection**：因為資料沒有混在一起，當 File A 被刪除時，整區 (Zone) 都是無效資料，直接 Reset 即可，不需要搬移資料，GC 負擔趨近於零
- **Reduced Tail Latency**
因為沒有了不可控的內部 GC，讀寫的回應時間變得非常穩定且可預測
- **More Capacity**
傳統 SSD 需要預留很大一塊空間 (Over-provisioning, OP) 來做 GC 緩衝 (通常佔 7~28%)。ZNS 不需要這塊空間，所以這些容量都可以釋放給使用者

 

#### Zone status

因為 SSD 內部的 SRAM/DRAM 緩衝區（用來暫存寫入資料）是有限的，SSD 無法同時開啟所有 Zone 進行寫入。因此，ZNS 定義了這些狀態，讓 Host 與 SSD 協調「現在到底哪幾個 Zone 是活躍的」

- **Empty**：全空，WP 在起點
- **Implicit Open**：Host 寫了資料，但沒特別下令要鎖定開啟這 Zone。如果有太多 Zone 同時處於 Open 狀態，導致 SSD 資源不足時，SSD 可能會優先把 Implicit Open 的 Zone 關掉以回收資源
- **Explicit Open**：Zone 被 Host 用明確的指令標記為 open，表示接下來要寫入它。除非 Host 下令或被寫滿，否則它會一直佔用 Open Resources
- **Full**：寫滿了
- **Closed**：雖然裡面還有資料要讀，但暫時不寫了，釋放資源
- **Read Only**
- **Offline**：壞掉，不可讀寫


#### ZNS Parallelism

- **Small zone**：Small GC overhead but low internal parallelism.
- **Large zone**：High GC overhead but high internal parallelism.

（？？）

#### Linux Kernel Support

Linux 並沒有為 NVMe ZNS 重新發明一套全新的子系統，而是加料並沿用了之前為 SMR HDD (疊瓦式磁記錄硬碟) 所開發的架構 (ZBC、ZAC)

Linux Kernel 將 ZNS SSD 和 SMR HDD 統一抽象化為 「Zoned Block Device」，上層應用程式可以用一套相同的 API 來控制不同種類的硬體

Linux 提供了三條路徑讓使用者使用 ZNS SSD，既可以「向下相容」舊系統 (透過 dm-zoned)，又可以讓新應用程式完整使用到 ZNS 的效益

- **傳統相容模式 (Legacy Path)**
- **對象**：不懂 ZNS 的傳統檔案系統 (如 ext4, xfs) 或舊應用程式
- **關鍵元件**：**Device Mapper (dm-zoned)**
- **運作**：dm-zoned 是一個中間層，它把 ZNS SSD「偽裝」成一個普通的、可以隨機寫入的區塊裝置。它在內部處理 Zone 的重置和寫入指標管理。雖然方便，但會損失部分 ZNS 的效能優勢（因為中間層又有 overhead）

- **支援 ZNS 的檔案系統 (File System Path)**
- **對象**：經過修改、原生支援 Zone 的檔案系統。
- **關鍵元件**：
- **f2fs** (Flash-Friendly File System)：這是目前對 ZNS 支援度最好的檔案系統之一。它知道如何將檔案寫入對齊到 Zone WP，並處理垃圾回收
- **zonefs**： 這是一個特殊的檔案系統。它不是用來存一般檔案的，而是把每個 Zone 映射成一個檔案。例如 zone0 檔案就對應到底層的 Zone 0。這讓應用程式可以用簡單的 open/write/read 系統呼叫來直接操作 Zone，而不需要處理複雜的 ioctl

- **直接裝置存取 (Direct Device Access / Passthrough)**
- **對象**：高效能資料庫 (如 RocksDB/ZenFS) 或客製化儲存應用
- **運作**： 繞過檔案系統，直接對 `/dev/nvme0n1` 進行操作
- **介面**： 使用 `ioctl()` 系統呼叫直接發送管理指令


#### Application case: LSM-Tree & ZenFS

##### LSM-Tree

Log-structured Merge-tree，一種資料結構，RocksDB (一個高效能 Key-Value 資料庫) 會用到它，而其運作原理非常適合用 ZNS

- 寫入流程：
- **MemTable**：資料先寫入記憶體中的緩衝區
- **Immutable MemTable**：寫滿後變成不可變狀態
- **Flush to SSTable**：記憶體資料被「順序」寫入到磁碟，變成 SSTable (Sorted String Table) 檔案
- Compaction (壓縮)：
- 隨著時間推移，愈來愈多 SSTable 被創建，系統會把 Level 0 的 SSTable 合併、排序後寫入 Level 1
- 關鍵點：這個過程會不斷產生新的檔案，並刪除舊的檔案
- 與 ZNS 的關聯：
- **順序寫入**：SSTable 的產生過程本來就是順序寫入，完全符合 ZNS 的 Sequential Write Constraint。
- **整批刪除**：Compaction 完成後，舊的 SSTable 會被刪除。如果一個 Zone 剛好只存一個 SSTable，刪除檔案等於 Reset Zone，完全不需要 GC！


##### ZenFS

雖然 LSM-Tree 很適合 ZNS，但如果中間隔著一個傳統檔案系統（如 ext4），ext4 會把順序的 SSTable 切碎亂塞進 SSD 的各個角落，破壞了順序性。

因此，Western Digital 開發了 ZenFS，一個專為 ZNS 打造的檔案系統後端

- **Zone 的分類管理**：ZenFS 將 SSD 上的 Zone 分為兩大類，實現了我們剛學過的 Smart Data Placement
- **Journal Zones**：日誌區，存放 WAL (Write-Ahead Log) 和 Superblock，這些資料需要極高的寫入可靠性
- **Data Zones**：資料區，存放 Extents (也就是 RocksDB 的 SSTables)，使用 ++Zone Append++ 指令來寫入，這意味著 ZenFS 可以 ++同時發送多個寫入請求++ (High Queue Depth)，由 SSD 決定最終位置
- **ZoneFS 優勢**
- 傳統路徑： `RocksDB -> ext4 -> Block Layer -> FTL -> Flash`
經過層層轉換，順序寫入變成隨機寫入，觸發大量 GC
- ZenFS 路徑： `RocksDB -> ZenFS -> Zone Append -> Flash Zone`
資料直接對齊物理 Zone，寫入放大接近 1，GC 近乎 0

## CH6 File Systems and Storage Class Memory

- **File**: 就是一串 byte 陣列 (linear array of bytes)，每個檔案都有一個獨一無二的編號，稱為 inode (index node) number
- **Directory**: 目錄其實也是一種特殊的檔案。它的內容是一張清單，記錄了「檔名」對應到「inode number」的關係
- **Directory Tree**: 檔案系統呈現階層狀結構，根目錄為 /
- **Metadata**: 檔案系統的主要任務除了存資料，還要存 Metadata。Metadata 包含檔案名稱、權限、擁有者、Timestamps 和檔案大小等

### File System

檔案系統是作業系統用來管理資料儲存與檢索的一種機制/結構

它的核心任務與組成可以拆解為以下三點：

1. **儲存檔案**
檔案系統的主要任務是儲存兩類資訊 ：
- Data: 使用者實際的檔案內容
- Metadata: 關於資料的資料，包括檔名、擁有權 、存取權限、時間戳記以及檔案大小等
2. **組織檔案**
檔案系統不只是把資料丟進硬碟，它還負責組織，透過 Directory 來管理檔案，目錄本身也是一種特殊的檔案，內容是一張對照表，記錄了「檔名」與「Inode number」的對應關係
3. **操作檔案**
File system 提供標準的操作介面，讓使用者或程式可以對資料進行操作，而不需要去管底層硬碟的 Sector 是怎麼寫入的
這些介面包括：Creating、Reading/writing、Renaming、Removing、Mounting 等

### Virtual File System (VFS)

現代 OS 有同時支援多個 file system 的需求，而不是寫死特定的 FS，所以需要 VFS，一個位於 Application 和具體 File System (如 Ext4) 之間的中間層，它讓 Linux 能夠同時支援多種檔案系統，並將 System Call 標準化，讓使用者可以不用管後面的檔案系統跟硬體

 

VFS 不只是一個 API wrapper，它本身包含了大量的核心邏輯與功能實作，負責執行很多所有檔案系統都通用的邏輯

- Caches Metadata
- Caches data
- Access Control
- Path Lookup
- File Handle Management

VFS 它不是一個薄薄的轉接層，而是一個功能強大的中間層，它把所有檔案系統都需要用到的功能 (快取、權限、路徑解析) 統一實作在 Kernel 裡，這樣底層的 Ext4、Fat32 開發者就不用重複造輪子，只需要專注在「如何把資料存到硬碟上」就好

#### VFS Abstraction

- **Superblock**: FS-global data，位於最開頭第一個 block，存放用來++描述整個檔案系統的全域資訊++，例如：Block size 是多少？Inode 總共有多少個？檔案系統類型是什麼？
- **i-node**: index node，記錄一個檔案的 metadata (權限、大小、資料區塊位置等)
- **d-entry**: directory entry，++name++ to ++i-node++ mapping
- **file object**: pointer to ++dentry++ and ++cursor++ (file offset，紀錄這檔案目前讀到哪邊)，代表一個 ++被 Process 打開的檔案++

Superblock and i-nodes 由 file system developer 實作

### Extended File System (Ext)

Ext 是 Linux 上的主流 file system 家族

- **Ext2**: second extended file system
- 單一檔案大小上限: 16 GB ~ 2 TB
- 檔案系統總容量上限: 2 TB ~ 32 TB
- 適用場景: 推薦用於 Flash drives 或 USB drives，因為可以減少寫入次數，延長壽命
- **Ext3**: 加入 journaling 功能，data 直接寫入 data 區塊，metadata 記錄在 journal 區塊，等 data 寫好再更新，讓系統在不正常關機後，能快速恢復檔案
- **Ext4**: 支援超大容量，並引入許多提升效能的機制
- 單一檔案大小上限: 16 TB
- 檔案系統總容量上限: 1 EB

#### File System View

開機後先去 MBR 找 superblock 的位址獲取檔案系統資訊，以及 root 的 inode number


#### File System Organization

Metadata (superblock、i-bmap、d-bitmap、inode table) 都記錄在前面的地方，後面都放 data


Inodes 是用來記錄 metadata 的資料結構，當創建一個新檔案時，檔案系統必須分配一個 Inode 給這個檔案，跟 data block 一樣，都是一種需要分配的有限資源，所以需要記錄使用情況，而 Ext 系列中為了省空間，用的是 bitmap，每單位都只用 1 bit 來記錄是否空閒

- **i-bmap**: 用來追蹤 Inode Table 裡的每一個 Inode 是否已經被分配出去
一個 Block (4KB) 的 i-bmap 就可以管理 32,768 (4KB * 8 bit) 個檔案的 Inode 狀態
- **d-bmap**: 用來追蹤 Data Region 裡的每一個 Block 是否存有資料

雖然用 bitmap 來管理的話，要尋找空閒空間需要遍歷 bitmap，不如用 queue 的 O(1) 來的快速，但是很省空間，而且 bitmap 可以用 bit mask 快速找到連續的空閒空間，避免同一個 file 的 data block 太過破碎，增加讀寫的 overhead (要寫入檔案的時候不會只分配一個 data block 而是會直接一次給 8 個連續的 data block)


分配到 inode 以後，File system 紀錄的是 inode number，那要怎麼去找到對應的 inode 內容存在哪一個 sector 中呢？

舉 inode number = 32 為例

1. 找到這 inode number 在 Inode Table 中的第幾 block

$\text{iaddr} = \frac{\text{inumber} \times \text{sizeof(inode)}}{\text{blocksize}}$

$\text{iaddr} = \frac{32 \times 256}{4096} = \frac{8192}{4096} = 2$

$\Rightarrow$ 32 在 inode table 中的 第 2 個 block
2. 加上 Inode Table Start Address，得到硬碟上的絕對位置

$\text{Sector} = \frac{(\text{iaddr} \times \text{blocksize}) + \text{InodeStartAddr}}{\text{sectorsize}}$

$\text{Sector} = \frac{(2 \times 4\text{ KB}) + \text{12 KB}}{\text{512 B}} = 40$

$\Rightarrow$ 32 所在的 block 在第 40 個 sector

::: spoiler AI 釋疑

有一些困惑的地方，以下是 AI 的解答

- Q: 為什麼要第一步把位址轉成 block id，第二步再轉回位址？

$\text{Sector} = \frac{(\frac{\text{inumber} \times \text{sizeof(inode)}}{\text{blocksize}} \times \text{blocksize}) + \text{InodeStartAddr}}{\text{sectorsize}}$

而不是直接獲取位址

$\text{Sector} = \frac{(\text{inumber} \times \text{sizeof(inode)}) + \text{InodeStartAddr}}{\text{sectorsize}}$

AI: 第一個除法是強除法，目的是去除 offset，得到 inode 所在的 block 的位址，因為 OS 的讀取單位是 block

- Q: 為什麼得到 block 的 address 之後，還要 / sectorsize 得到是第幾個 sector？
AI: 因為 HDD 是用 Sector Index 在做讀取

- Q: 上面得到的是 inode 所在 block 的第一個 sector，怎麼沒繼續計算 block 內的 offset？

AI: 那是搬完整個 block 進 RAM 以後，CPU 要做的事

:::

#### Inode

Ext3/Ext4 中 Inode 的 size 為 256 Byte (0.5 sector)，記錄的資料大概是這些


值得注意的是，inode 中不含 file name，因為 inode 是底層資訊，不需要使用者取的檔案名稱

其中 block 的部分記錄指向 data block 的 pointer，讀檔時會依序遍歷這些 pointer 指向的 data block，再拼起來就是要讀的檔案

但一個 pointer 4 Byte，60 Byte 可以記錄 15 個 pointer也就是 15 個 block，也是 15 * 4 = 60 KB，顯然不夠用

所以這裡的 pointer 可以指向其他紀錄 pointer 的 block，一個 block 可以放 4KB / 4 = 1024 個 pointer，這樣一來，inode 中的一個 pointer 就可以指向 1024 * 4KB = 4MB 的空間，總共是 15 * 4 = 60 MB

但這樣還是不夠，所以可以延伸到四層，最多支援 4TB 的檔案
（很像 memory translation 的多層 page table，根據實際情況動態增長大小）
- **Direct Pointer**: points to a data block explicitly.
- **Indirect Pointer**: points to an indirect block that holds (multiple) pointers to data blocks.
- **Double Indirect Pointer**: points to pointers to indirect blocks.
- **Triple Indirect Pointer**: points to pointers to pointers to indirect blocks. 其實是四層哦


#### Directory

那 file name 怎麼對應到 inode number 呢？靠的就是 Directory

Directory 本身也是一個 file，它也會對應到一個 inode，只是它的 data block 紀錄的會是下面這樣 inum : filename 的對應關係


**reclen**: record length，因為每個檔名的長度不一樣，所以 directory 中每個 entry 的大小都不一樣，所以需要 reclen 來記錄這個 entry 的大小，當遍歷 directory 時，讀完一個條目後會 + reclen 移到下一個 entry

刪除檔案時，不會直接去 disk 清除 data block（所以才能檔案救援），而是把 i-bmap、d-bmap 對應的 bit 歸零，並移除 directory 中對應的 entry，讓使用者 access 不到檔案對應的 data block
而要移除 directory 中對應的 entry 不會把後面所有的 entry 往前搬，而是透過增加上一個 entry 的 reclen，使其覆蓋要刪掉的 entry 來達成

### File System Interface

File system interface includes:
- Creating files
- Reading/writing files
- Renaming files
- Getting information about files
- Removing files
- Managing directories
- Linking files/directories
- Mounting/unmounting a file system

使用者透過 system call interface (C 中是 libc) 呼叫 system call， system call 會再去呼叫 FS interface 去操作檔案，而 FS Interface 就由 FS 來實作


#### Creating Files

（UNIX OS）

The system call `open()` is to create or open a file


開起來的那個檔案的 inode 會被記錄在一個所有 process 共用的 open file table 裡面
（ref 是有幾個 子 process 在讀寫這檔案）

每個 process 都有個 pointer array 用來指向 open file table 中的 entry，`open()` 成功的話會回傳一個 file descriptor (fd)，就是該檔案在這個 pointer array 中的 index


而開檔案的 fd 會從 3 開始，因為前 3 個有人用了

stdin: 0
stdout: 1
stderr: 2


##### 為什麼這個架構要這樣設計

我們有2個需求

- 不同 process 開同一個檔案，需要各自紀錄彼此讀到哪，不能讓 process A 的讀取進度影響到process B
$\Rightarrow$ 每個 process都需要有各自的讀檔記錄
- 透過 `fork()` 產生的 子 process 需要跟 父 process 共享同樣的讀檔進度
$\Rightarrow$ 這個讀檔記錄要抽出來，不能放在 process 的 memory 裡，不然父子 process 會不同步

$\Rightarrow$ Open File Table，且父子行程會共享同一個 Open File Table entry

#### See the metadata

`stat()` or `fstat()` calls can be used to see each file's metadata


#### Links

File systems allow links to create multiple names (aliases) for the same file

- **Hard Link**: 在 Directory 中新增一個 entry，把另一個 name 也對應到同樣的 inode number
- 限制：通常不能跨越不同的檔案系統 (因為 Inode Number 在不同分割區是獨立的)
- **Symbolic/Soft Link**: 創建一個新的 Inode，有自己的 Data Block，只是裡面存的是目標檔案的 path，就像 windows 中的捷徑一樣
- 優點：可以跨越不同的檔案系統 (因為只是記路徑)


### Log-structured File System (LFS)

又稱作 Journaling Flash Filesystem，是為了寫快擦慢的 flash 開發的 FS，能夠比較符合 SSD 的特性 e.g. JFFS2

這裡介紹的是JFFS2 (Journaling Flash File System version 2)

#### Data and Metadata

傳統的 file system 把 meta data 跟 data 分開存（Ext 把 inode 記錄在 inode table 裡、data 放在 data blocks

在 LFS 中，所有的東西都被打包成一種變動長度的結構，稱為 Node

LFS Node 的內容 = \[ ++Header++ + ++Metadata++ + ++Data Payload++ ]

* Header: 標記這是屬於哪個檔案 (Inode Number)、這是該檔案的第幾個版本
* Metadata: 類似傳統 Inode 的內容 (UID, GID, mtime, mode)
* Data Payload: 檔案的一部分實際內容 (Data)


#### Write

每次寫檔不會去修改之前的內容，而是直接在 flash 的最後空白處寫入一個新的 node (包含 metadata)

講白了就是 **Append-Only**

- **write buffering**：為了提升效率，會把寫入 request 先 buffer 在 memory 裡，形成一個 in-memory segment 再一次寫入 disk

但因為 metadata 跟 data 放在一起 write append，也就是說 inode 的位置不固定，所以無法像 Ext 一樣，直接從 inode number 算出 inode 的位址，因此 LFS 需要一個 map 統一紀錄 inode number 對應的 inode 現在存去哪了，這就是 **imap**

但因為 imap 也需要更新。所以也是一樣會在資料更新後，寫在最後面的位置，因此位置也不固定，所以需要再有一個固定位址的 Checkpoint Region (CR)，來指向當前的 imap，而 CR 不會每次 imap 更新都刷新，而是固定時間刷新 (30秒)，反正就算它指到舊 imap，因為 LFS 都是 sequential write，所以發現是舊的就再往後找就好了
（至於為什麼 CR 就可以原地刷新，不用 write append ... 可能因為更新頻率低吧）


#### Directory

一個普通檔案，存 (name, inode number)，讀檔時去根據 file name 取到 inode number 再去 imap 找檔案的 inode

**CR** (找 imap) $\rightarrow$ **imap** (找 Dir Inode) $\rightarrow$ **Dir Inode** (讀 Dir Data) $\rightarrow$ **Dir Data** (找 Name 對應的 File Inode Number) $\rightarrow$ **imap** (找 File Inode Address) $\rightarrow$ **File Inode** (讀 File Data)

因為通常有多層路徑，所以 **Dir Inode** $\rightarrow$ **Dir Data** 會跑多次，一層層路徑找下去

#### Garbage Collection

由於 LFS 永遠採取 Append-Only 的策略，這意味著當修改一個檔案時，舊的 Data Blocks 仍然佔用著硬碟空間，但已經變成了無效的 Garbage，因此需要 GC

（感覺 LFS 就是把 FTL 的工作往上拉到 file system）

##### How to clean

LFS 不是一個一個 Block 去回收，而是以 Segment (區段) 為單位進行「壓縮與搬運」

1. **Read**: 系統將 $M$ 個舊的 Segments (裡面混雜著有效資料與垃圾) 讀入記憶體
2. **Identify**: 判斷 Block 是 Live / Dead
3. **Compact**: 將那些 live Blocks 挑出來，緊密地排列寫入到 $N$ 個新的 Segments 中 (其中 $N < M$)
4. **Free**: 原本那 $M$ 個舊 Segments 的空間就可以被標記為 Free，拿來重複使用

至於要怎麼做到 2.，LFS 在每個 Segment 的開頭加入了一個 Segment Summary Block (SS) ，它記錄了這個 Segment 裡每一個 Data Block 屬於的 Inode Number、Offset，再去 imap 找 inode，跟這 offset 的最新位址比對看有沒有一樣就好

##### When to clean

GC 是一個很耗資源的動作，所以通常會在以下時機觸發
- **Periodically**: 定時執行
- **Idle time**: 當系統不忙的時候偷偷做
- **Disk full**: 被迫執行，這時候系統效能會顯著下降

##### Which to clean

LFS 會根據資料的「熱度」來決定清理順序
- **Hot Segment**
- 定義: 裡面的資料經常被覆寫
- 特徵: 既然常被覆寫，代表裡面的資料很快就會變成垃圾
- 策略: **Clean Later**，因為如果太早清，剛搬完的資料可能下一秒就被使用者改掉了，浪費力氣，等久一點，讓它們自然死光再清最划算
- **Cold Segment**
- 定義: 裡面的資料很少變動 (Few overwritten)
- 特徵: 裡面的垃圾比較少，大部分是穩定的死資料
- 策略: **Clean Sooner**，雖然回收的空間可能不多，但如果不主動清，它們永遠佔在那裡

#### Crash Recovery

兩種 crash

##### 更新 CR 的時候 crash

Checkpoint Region (CR) 是整個檔案系統的入口，萬一我們在每 30 秒更新一次 CR 的時候，剛好寫到一半斷電了，那唯一的入口壞了，整個檔案系統豈不是毀了？

解法：雙份備份 + Timestamp

- **雙份 CR**: 硬碟的最開頭和最尾端各有一個 CR，LFS 會 交替寫入這兩個位置，如果寫 CR1 時當機，CR2 還是好的（雖然是 30 秒前的舊版，但至少能開機）
- **Timestamp**: It first writes a **header (with a timestamp)**, then the **body of CR**, and then an **end marker (with a timestamp)**，檢查 header 跟 end marker 的 timestamp 有沒有一樣就知道上次有沒有正常寫完了

##### 寫入 segment 的時候 crash

既然 CR 是 30 秒才更新一次，那如果在第 29 秒寫入了一個新檔案然後當機，這 29 秒內的資料是不是就丟了？（因為 CR 還指著 29 秒前的舊 imap）

- **Roll-Forwarding**: 因為所有資料都是按時間順序寫在 Log 末端的，如果發現 CR 指的地方後面還有完整寫入的 segment，就順藤摸瓜找回來

### Metadata Journaling

The sequence of metadata journaling:
1. **Data Write**: Write data to final location
2. **Journal Metadata Write**: Write the begin block (TxB) and metadata (I[v2], B[v2]) to log
3. **Journal Commit**: Write the transaction commit block (TxE)
4. **Checkpoint Metadata**: Write the contents of metadata update to their final locations within the file system
5. **Free**: Mark the transaction free in the journal superblock

要確定 1.、2. 都完成才能 3. 繼續

類似先前 Ext3 那的 full journaling，但只 journal metadata，好像是說不保證檔案不會壞，但至少 metadata 不會因為 crash 壞掉，保護 FS 的完整性

### Filesystem in Userspace (FUSE)

先前講的 file system 都是在 kernel 裡，但 FUSE 允許開發者在 User Space 編寫檔案系統程式碼，這意味著你可以用 Python, Java, C++ 寫一個普通的程式，讓作業系統把它當作一個隨身碟或硬碟掛載起來

- **File System in Kernel-space**
- Very **difficult** to build
- Need careful use of synchronization primitives
- Only C language supported
- Standard C libraries not available
- Need root privilege
- **File System in User-space (using FUSE!)**
- Framework to implement user-space file system
- **Easy** to write: Avoid awful coding in kernel
- Easy to test: Run like a normal user program
- Easy to integrate libraries: Can easily deploy libraries
- Trade performance for flexibility

總之 FUSE 就是比較好開發，只是效能較差

原理是 FUSE 在 Kernel 裡留了一個小小的模組，負責把 VFS 的指令「轉發」給 User Space 的程式


## CH7 Distributed File System

### Network File System

#### Client-Server Model


- **Client**
- Issues system calls to the client-side file system to access files on the server
- Caches retrieved blocks in memory for future use
- **Server**
- Accesses data blocks in the server-side file system (i.e., file server).
- Caches and buffers reads/writes in memory


### NFSv2: A Stateless File Protocol

An open protocol that specifies the exact message formats for client-server communication

Current Standard: NFSv4 supports larger-scale protocol

But we focus on **NFSv2**: simplicity and fast crash recovery

#### Fast Crash Recovery: Statelessness

NFSv2 is for simplicity and fast crash recovery，因此採用 stateless 的設計

- Stateless
- Server 不會記錄任何關於 Client 操作的狀態或歷史紀錄
- Client 發出的每一個 Protocol Request 都必須包含完成該操作所需的所有資訊
- Server 處理完請求後，就會立即「忘記」該請求，不會保留記憶
- 優勢
- ++Server Crash++
如果 Server 當機後重啟，因為它本來就不保存 Client 的狀態 (例如開啟的檔案描述符 fd)，Client 只需要重新發送請求即可，Server 不需要進行複雜的狀態重建
- ++Client Crash++
如果 Client 當機，Server 也不會殘留任何無用的資源 (例如開了檔案沒關)，因為 Server 從未追蹤 Client 是否開啟了檔案

#### File Handler

由於 NFS 是 Stateless 的，Server 不會維護傳統作業系統中的 File Descriptor (fd) 對應表，取而代之的是，NFS 使用 File Handle 來識別檔案

- **File Handle**：用來唯一識別一個檔案或目錄的識別碼，通常包含以下元件，組成一個 encoded string
- **Volume Identifier**： 指定 File System
- **Inode Number**： 指定該檔案系統中的特定檔案或目錄
- **Generation Number**： 用於 Inode 重複使用時的辨識

在傳統的 Unix/Linux 檔案系統中，當一個檔案被刪除後，它原本佔用的 Inode Number 會被釋放，並可能分配給未來新建立的檔案使用

由於 NFS 是 Stateless 的，Server 不知道 Client 手上的 File Handle 是否其實是指向舊檔案的，所以需要 ++Generation Number++，用來比對 inode number 是否指向的是同一個檔案，簡單來說就是 Inode 的「版本號」

然後 client 要讀寫檔案就是會把 system calls 轉成 protocol messages 發送，
Server 再回應 protocol messages



#### Handling Server Failures

中間掉封包，或是 server 掛掉怎麼辦？

無所謂，client 偵測到 Request Timeout 就直接重送原本的 request 就好，因為大多數的 NFSv2 請求都是 Idempotent（執行幾次結果都一樣）的

比如說

- `LOOKUP`：無論查詢幾次，回傳的 File Handle 都是一樣的
- `READ`：無論讀取幾次，讀到的資料都是一樣的
- `WRITE`：NFS 的寫入是指定絕對偏移量（Offset）和數據，所以將同樣的數據寫入同樣的位置多次，結果還是一樣

但不是所有做都是 Idempotent，比如說 `MKDIR`
對於這類 not idempotent 操作，Server 必須讓重試的請求失敗（Fail the retry）

（但 server stateless 要怎麼知道這 request 是 retry 的？？）

#### Client-side Caching / Buffering

Read / Write 都會 buffer，但就會導致 cache 未更新的問題

- **Stale Cache**
- 描述：read 的 cache 版本過舊
- 解法：Client 在使用快取前，會先發送 `GETATTR` 請求給伺服器，檢查檔案的「最後修改時間」，確認檔案是否已被更動過
- **Update Visibility**
- 描述：write 沒寫到 server 那，就算其他 client 用 `GETATTR` 檢查過了，也拿步道最新版
- 解法：**Flush-on-close**，關檔的時候要寫回 server（？有解跟沒解一樣）

#### Server-side Caching / Buffering

server 利用 memory 來 cache 讀取與寫入的請求，以提升系統效能

但對於 write 要注意的是，必須在真的寫入硬碟後才能回覆 Client 說「寫入成功」，不然如果 server 斷電或 crash，兩邊資料就不一致了

要提升 write performance 可以採用：

- **Battery-backed Memory**
- 使用有電池供電的記憶體，即使斷電，資料也不會流失
- 伺服器只要寫入到這種記憶體就可以立刻回覆 Client 成功，既安全又快速
- **Log-structured Approach**
- sequential write 比較快

### Google File System (GFS)

#### Design Considerations and Assumptions

GFS 是基於 Google 特定的工作負載與環境所設計，與傳統檔案系統有不同的假設：

- ++硬體故障是常態++，系統由數千個不可靠的廉價硬體組成，Component failures 是常態而非例外
- ++檔案巨大++，數 GB 的大檔案非常普遍
- ++Append-heavy++，Random writes 很少見，絕大多數是 Append
- Read 多為 ++streaming reads++，很少有 small random reads
- 重視持續的高頻寬 (++High Bandwidth++) 勝過低延遲 (Low Latency)

#### GFS Architecture

GFS cluster 包含三個主要元件：

1. 單一 **Master**（maybe single point of failure）
- **管理 Metadata**：負責維護所有檔案系統的 Metadata，包含 Namespace、存取控制、檔案到 Chunk 的對應、以及 Chunk 的位置
- **系統管理**：控制 Chunk 的 Placement、 Replication、Rebalancing 與 Garbage Collection
- **Heartbeats**：週期性與 Chunkserver 溝通以發送指令並收集狀態
2. 多個 **Chunkservers**
- **儲存數據**：檔案被分割成固定大小的 Chunks (通常為 64 MB)，儲存在 Chunkserver 的本機磁碟上
- **可靠性**：每個 Chunk 預設會有 3 個 Replicas (副本) 存放在不同的 Chunkservers 上
- **識別**：透過 64-bit 的 Chunk Handle 來識別
3. 多個 **Clients**
- **互動模式**：Client ++與 Master 交換 Metadata++，但直接 ++與 Chunkservers 傳輸 data++
- **No Data Caching**：Client 不會快取檔案內容，避免了維護快取一致性的開銷 (與 NFS 不同)，而且 streaming of large files 本來就不太需要快取檔案重用

Each of these is typically a commodity Linux machine running a user-level server process


#### Read

Client 將 file name、offset 轉成 chunk index，先向 Master 發送 request 詢問 Chunk 的位置，然後直接聯繫「最近」的 Chunkserver 讀取 data

#### Write

If a write exceeds the chunk boundary, the client must break it down into multiple mutation operations

為了維護 replica 一致性，GFS 將控制流與資料流分開：

- **Lease**：Master 發放 Lease 給其中一個 Replica 成為 Primary (timeout of 60 seconds)
- **Order**：Primary 負責決定所有 Mutation 的執行順序 (自己先執行，然後轉發給所有的 Secondaries 要求它們依同樣順序執行)
- **Data Flow**：Client 將 data 推送到所有的 Replicas
- **Commit**：當所有 Replicas 都收到數據後，Primary 通知所有 Secondary 依序執行寫入

流程：


#### Record Appends

在 Google 的 workload 中，常常有數百個 Client 同時將數據 append 到同一個檔案的尾端

如果使用一般的寫入方式（Client 指定寫入的 Offset），當多個 Client 同時寫入時，若沒有複雜的鎖定機制，數據會互相覆蓋或交錯，導致不可預期的結果

因此 GFS 提供 **Record Append** 這種 Atomic Operation，Client 不需要指定 Offset，只需提供數據，由 server 決定寫入的位置（很像 ZFS 的那個）

流程：

1. 傳送數據： Client 將數據推送到該 Chunk 的所有 Replicas 。
2. 發送請求： Client 向 Primary 發送 Record Append 請求 。
3. Primary 判斷與執行：
檢查空間： Primary 檢查目前的 Chunk 剩餘空間是否足夠寫入這筆 Record。
- 情況 A：空間足夠
1. Primary 決定寫入的 Offset。
2. Primary 將數據寫入自己的 Replica。
3. Primary 通知所有 Secondary Replicas 在「完全相同的 Offset」寫入數據 。
4. 回覆 Client 成功。
- 情況 B：空間不足 (Padding)
1. Primary 會將 Chunk 剩餘的空間填滿（Padding），使其達到 Chunk 的邊界 。
2. 通知所有 Secondaries 也做 Padding。
3. 回覆 Client 「操作失敗，請在下一個 Chunk 重試」（Client 隨後會請求下一個 Chunk 並重新執行 Append）

If a record append fails at ++any++ replica, C must retry but may result in ++inconsistency++: The GFS **application** must cope with it

#### Relaxed Consistency

Relaxed Consistency（寬鬆一致性）是 Google File System (GFS) 為了在由不可靠硬體組成的大規模系統中保持高效能與高可用性，而採用的一種非傳統一致性模型

相較於傳統 POSIX 檔案系統嚴格的一致性，GFS 允許在特定情況下出現數據不精確的狀態，並要求應用程式自行處理

##### Terminology

為了描述 File Region 的狀態，GFS 定義了以下幾個術語：

- **Consistent**：無論 Client 從哪個 Replica 讀取數據，看到的內容都是一樣的 。
- **Defined**：區域是 Consistent 的，並且單一 Client 能夠看到它所寫入的完整數據
（簡單說：寫入成功且數據完整，沒有混雜其他人的數據）
- **Undefined**：區域是 Consistent 的（大家看到的都一樣），但數據可能不完全反映任何單一 Client 的寫入內容
（發生原因：並發寫入時，數據交錯混合）
- **Inconsistent**：不同的 Client 在同一時間從不同的 Replica 可能看到不同的數據
（發生原因：寫入操作失敗，導致部分 Replica 更新了，部分沒有）

## CH8 Key-value Store

### Key-value database

- A type of non-relational database.
- A simple key-value method to store data
- Unique key an arbitrary large data field
- Individual or combinations of keys to retrieve associated values
- Important: **Key management** (Index)

Relational Table (Row-based)


KV-stores (column-based)


### Distributed Architecture

Master 它不存實際的 Data，只存 Metadata，通過 Hash Function，將 Key 映射到不同的 Nodes
它維護一張 Mapping Table，記錄 "++Key 的範圍++" 對應到 "++哪台 Node++"


**iterative query**：Client 自己找 node

**recursive query**：Master 幫忙轉發

### DBMS Layers

database management system

- Query Optimization：決定「怎麼查最快」（例如要用哪個 Index）
- Access Methods：負責管理資料在磁碟上的組織方式（例如 B+ Tree, Hash Index, ISAM, LSM Tree）
- Buffer/Disk Space：負責實際的 I/O 和快取管理

我們的接下來要討論的是 Access Methods，有各種資料結構可以用（Hash table, Binary Tree, B^+^-Tree）


### Indexed Sequential Access Method (ISAM)

static 的（那幹嘛不用 array 就好）

- **Non-Leaf Pages** (Index Levels)：包含 Root 和中間節點。這些頁面在建立索引時生成，之後 「**永遠不會被修改**」
- **Leaf Pages** (Data Levels)：實際存放資料 (Key-Value pairs) 的地方，所有的 Insert、Delete 都只發生在這裡

類似 Binary Search Tree


如果有 leaf page 滿了的話，會直接新增 page 接上去，變成 page 的 linked list


### LevelDB and LSM Tree

LevelDB is an ++open source on-disk key-value store++ written by Google fellows

#### LSM Tree

Log-Structured Merge Tree，不太像資料結構的 tree，比較像是一種分層的儲存結構

由兩個主要的樹狀結構組成
1. $C_0$ Tree (Memory Component)：
- 位於 記憶體 (RAM) 中
- 負責接收所有的寫入請求，速度極快
2. $C_1$ Tree (Disk Component)：
- 位於 磁碟 (Disk) 中
- 資料是唯讀且排序過的，容量大但寫入慢

總之就是不改之前寫入的舊資料，直接 append 新的資料（Log-Structured），讀的時候會先讀到新資料（有點 stack 的味道）

至於舊資料等新資料被沉澱到下層的時會被合併刪除


#### LevelDB

而 LevelDB 則是 LSM Tree 的具體實作 (其他還有 RocksDB, BigTable, HBase, Cassandra...)

由以下元件組成：

- **Write Ahead Log**
- WAL，位於 disk
- 資料寫入 memtable 前會先 Append 存入這裡，避免 memtable 因斷電遺失資料
- **Memtable**
- 這就是 LSM 的 $C_0$ 層
- 通常是一個 SkipList (跳躍表)，駐留在記憶體中
- 負責接收所有新的 Put 和 Delete 請求
- **Immutable Memtable**
- 當 Memtable 寫滿了（例如達到 4MB），它會變成 Immutable (唯讀)，同時系統會開啟一個新的 Memtable 接收新寫入
- 這是一個過渡狀態，準備由背景執行緒 Flush 到磁碟
- **SSTable** (file)
- Sorted String Table， LSM 的 $C_1...C_k$ 層
- 磁碟上的檔案，一旦寫入就不可修改 (Immutable)
- 內部的 Key 是排序好的，方便快速搜尋
- **Manifest file**
- 這是 LevelDB 的「地圖」。它記錄了每一層 (Level) 有哪些 SSTable 檔案，以及每個檔案的 Key Range (最小到最大 Key)


##### Put/delete

LevelDB 的寫入是 Append-only 的，非常快

1. 寫入 Log (磁碟循序寫入)
2. 寫入 Memtable (記憶體操作)

在 LevelDB 中，沒有真正的刪除。當呼叫 `Delete(Key)`，它其實是寫入一條新的紀錄，標記為 "Delete Marker" (通常稱為 Tombstone 墓碑)。舊的資料還在磁碟深處，直到 Compaction 發生時相遇才會真正被消滅

##### Get

這就是 LevelDB 的代價：Read Amplification。為了找一個 Key，你可能要翻遍所有層級。

搜尋路徑：
1. 查 Memtable (最新)
2. 查 Immutable Memtable
3. 查 Level 0 SSTs (可能有多個重疊檔案)
4. 查 Level 1 SSTs -> Level 2 -> ... -> Level k

優化：為了避免讀太慢，LevelDB 大量依賴 Bloom Filter 。Bloom Filter 可以快速告訴你「這個 Key 絕對不在 這個 SSTable 裡」，讓你跳過不必要的磁碟讀取。

##### Compaction

Compaction 是 LevelDB 的心臟，負責維持 LSM Tree 的形狀，防止讀取效能隨著檔案變多而崩潰。
- **Minor Compaction**
- 觸發條件：Memtable 滿了 (>4MB)
- 動作：將 Immutable Memtable 直接 Dump 成一個 Level 0 SSTable 檔案
- 特性：非常快，只涉及記憶體到磁碟的 I/O
- 關鍵細節：Level 0 是唯一允許 SSTable 之間 Key Range 重疊 的層級 (因為它們直接來自時間序不同的 Memtable)。這導致讀取 L0 很慢 (最壞情況要讀所有 L0 檔案)
- **Major Compaction**
- 觸發條件：
- Level 0 檔案太多 (超過 8 個)
- 某一層 Level $i$ 的總大小超過限制 ($10^i$ MB)
- 動作：
- 從 Level $i$ 挑選一個檔案
- 找出 Level $i+1$ 中所有與之 Key Range 重疊 (Overlapping) 的檔案
- 進行 Merge Sort (因為 SST 都是已排序的，這步很快)
- 將合併結果寫成新的 Level $i+1$ 檔案。刪除舊的檔案 (包含被覆蓋的舊值和 Tombstone)