# TierDB
> [minhsun-c/tierdb](https://github.com/minhsun-c/tierdb)
## Memtable
### 概述
Memtable 是 LSM-Tree 的記憶體寫入緩衝區。所有的寫入操作（`put`、`delete`）都先寫入 memtable，累積到一定大小後凍結（freeze），成為不可變的 immutable memtable，等待被 flush 到磁碟上成為 SST 檔案。
在 tierdb 中，memtable 的底層資料結構是 skiplist，所有的 key-value 資料在記憶體中始終保持排序。這使得 range scan 可以直接按序遍歷，也使得 flush 到 SST 時不需要額外排序。
### struct skiplist
Skiplist 是一種基於機率的有序資料結構，支援 $O(log n)$ 的平均插入與查找。
tierdb 的 skiplist 採用 intrusive design，靈感來自 Linux kernel 的 `list_head`。`struct skiplist` 本身不攜帶任何資料，而是嵌入到外部的資料結構中（`struct memtable_entry`），透過巨集 `container_of` 從 skiplist 節點指標反推出完整的 entry。
```c
struct skiplist {
struct skiplist **forward; // 各層的下一個節點指標陣列
uint32_t level; // 此節點參與的層數
};
```
每個 skiplist 有一個 sentinel（哨兵）節點作為根節點。sentinel 的 `level` 欄位代表整個 skiplist 的最大層數（由 `engine_options.max_level` 決定，上限為 `SKIPLIST_MAX_LEVEL = 16`）。sentinel 不存放資料，僅作為各層鏈結串列的頭節點。
插入新節點時，`random_level()` 以 50% 的機率決定是否升到下一層。當節點數量足夠多時，約 $1\over2$ 的節點僅具有一層指標，約 $1\over4$ 的節點具有兩層指標，約 $1\over8$ 具有三層，以此類推。層數越高的節點越稀疏，形成多層「快速通道」。
搜尋時從最高層開始，沿著高層指標跳過大量不需要檢查的節點，逐層下降直到找到目標。以上圖為例，搜尋 35 時，從 sentinel 的最高層直接跳到 26，再往下一層即可抵達 35，僅訪問 2 個節點。若採用一般的鏈結串列，則須從 10 開始逐一走訪全部 5 個節點才能到達 35。
Skiplist 無法得知儲存資料的型別、大小、數量等，因此所有的比較邏輯透過 `skiplist_cmp_fn` 函式指標委託給呼叫者。呼叫者在比較函式中用 `container_of` 取出外部結構體，再比較 key。
```c
typedef int (*skiplist_cmp_fn)(struct skiplist *a, struct skiplist *b);
```
### struct memtable_entry
```c
struct memtable_entry {
uint8_t *key; // key 的位元組陣列，由此 entry 持有
size_t key_len; // key 長度
uint8_t *value; // value 的位元組陣列，由此 entry 持有；tombstone 時為 NULL
size_t value_len; // value 長度；0 代表 tombstone（已刪除）
struct skiplist link; // 嵌入式 skiplist 節點
};
```
每個 entry 都擁有自己的 `key` 和 `value` 記憶體。插入時會 `malloc` + `memcpy` 一份副本，不持有呼叫者傳入的指標。當 entry 被銷毀時，`key`、`value`、skiplist 的 `forward` 陣列、以及 entry 本身都會被 `free`。
本資料庫系統透過邏輯刪除（Tombstone）機制來處理資料刪除：當 `value_len == 0` 且 `value` 為 `NULL` 時，代表該 `key` 已失效。Tombstone 會如同一般資料保留在 memtable 並寫入 SSTable，用以遮蔽更舊版本的同名 `key`。唯有在 compaction 階段，且確認系統內已無該 `key` 的舊版本時，Tombstone 才會被真正移除。
### struct memtable
```c
struct memtable {
struct skiplist sentinel; // skiplist 的哨兵節點
uint32_t size; // 目前儲存的 entry 數量
size_t approx_size; // 估算的 key + value 總位元組數
uint64_t id; // 由 engine 分配的單調遞增 ID
};
```
為了決定 `memtable` 的凍結時機，結構體內部會粗略計算目前的資料量。每次呼叫 `memtable_put` 皆會累加 `key_len + value_len`。遇到 key 覆寫時，系統不會扣除舊 value 的大小，而是直接累加新值。此設計為效能上的取捨（Trade-off）：精算空間差值的代價過高，而粗略估算已完全足夠讓 engine 判斷何時該凍結 memtable。
每個 memtable 都有一個唯一的 `id`，由 engine 的 `next_id` 計數器分配。mutable memtable 的 id 是 0，之後每次 freeze 產生新的 memtable 時遞增。這個 id 也用於生成 SST 檔名（`db_path/{id}.sst`）。
### 基本操作 - memtable_put
```c
int memtable_put(struct memtable *mt, const uint8_t *key, size_t key_len,
const uint8_t *value, size_t value_len);
```
memtable 的寫入流程會先以 `memtable_get` 查詢目標 key。若命中，為了節省重建 skiplist 節點的開銷，系統會原地替換 value（釋放舊值並寫入新值），而不更動 key 與節點結構；若未命中，則會建立全新的 `memtable_entry` 並將其插入 skiplist 中。操作完成後，無論是新增還是覆寫，系統均會統一將 `key_len + value_len` 累加至 `approx_size` 中，藉此追蹤目前的粗略資料量。
### 基本操作 - memtable_get
```c
struct memtable_entry *memtable_get(struct memtable *mt, const uint8_t *key, size_t key_len);
```
從 level 0 線性掃描，比較每個節點的 key。因為 skiplist 是排序的，遇到比目標 key 大的節點就提前返回 `NULL`。找到完全匹配的 key 就返回 entry 指標。
注意：`memtable_get` 會返回 tombstone entry（`value_len == 0`），呼叫者必須自行檢查。這是刻意的設計——engine 需要知道一個 key 是「不存在」還是「被刪除了」，這兩者的語意不同。如果 get 跳過 tombstone，engine 會繼續往更舊的 source（immutable memtable、SST）查找，最終找到被刪除之前的舊值，造成錯誤。
刪除操作就是 `memtable_put(mt, key, key_len, NULL, 0)`——插入一個 tombstone。沒有專門的 delete 函式在 memtable 層級。engine 層的 `engine_delete` 只是對 `engine_put` 的包裝。
### 基本操作 - freeze
Memtable 的凍結機制是由 engine 層統籌處理的。當 `approx_size` 達到 `engine_options.threshold` 所設定的上限（即 `memtable_is_full` 成立）時，engine 會將當前的 mutable memtable 移入 `imm_memtables` 陣列，並立刻建立一個新的 memtable 以接收後續寫入。被凍結的舊 memtable 雖不再允許寫入，但依然可以正常支援 get 與 scan 等唯讀操作。
## SSTable
### 概述
SSTable（Sorted String Table）是 LSM-Tree 的磁碟儲存單元。當 memtable 被凍結並 flush 到磁碟時，其中所有已排序的 key-value 資料會被寫成一個 SST 檔案。SST 一旦建立就不再修改（immutable），所有的更新和刪除都透過寫入新的 SST 來表達。
在 tierdb 中，SST 的磁碟格式由三層結構組成：Block、Meta Section、以及 Meta Offset。其中，Meta Offset 代表 Meta Section 距離檔案起始處的距離，同時也代表 Block 的資料總量。讀取時只需要載入 Meta Section 到記憶體，Block 則按需從磁碟讀取。
### Block
Block 是 SST 內部的基本儲存單元。每個 block 包含若干筆已排序的 key-value entry，大小受 `block_size`（預設 4096 bytes）限制。Block 在磁碟上以連續的二進位格式儲存，讀取時整個 block 會被載入記憶體並解碼。
#### Data Section
每筆 entry 的格式為： `[ key_len (2B) | key | value_len (2B) | value ]`
- `key_len` 和 `value_len` 均為 `uint16_t`，以 little-endian 儲存
- `value_len == 0` 代表 tombstone（已刪除的 key）
- key 和 value 為原始位元組，不做任何壓縮或編碼
範例：儲存 `key = "fruit"`, `value = "banana"`
| key_len | key | value_len | value |
|:-------:|:----:|:---------:|:-----:|
| 05 00 | 66 72 75 69 74 <br/> (f r u i t) | 06 00 | 62 61 6E 61 6E 61 <br/> (b a n a n a) |
#### offset section
每筆 entry 在 data section 中的起始偏移量（`uint16_t`），共 `n` 個。透過 `offsets[i]` 可以直接跳到第 `i` 筆 entry，用於 block 內的隨機存取和二分搜尋。
#### num_of_elements
entry 總數，`uint16_t`，位於 block 的最末端。解碼時從尾端開始讀取：先讀 `num_of_elements`，再往前讀 offset section，剩餘的就是 data section。
### Data Structure
與 Memtable 的設計理念相似，Block 在系統中亦區分為可變（Mutable）與不可變（Immutable）兩種狀態，分別對應 `struct block_builder` 與 `struct block`。當前的寫入操作會由 `block_builder` 處理；一旦容量達標，則會將其封裝為不可變的 `block` 以供讀取。
在執行寫入時，`block_builder_add` 會先預估加入新 entry 後的 Block 總大小（包含 Data Section、Offset Section 與 `num_of_elements`）。若預估大小超越了 `target_size` 上限，函數會回傳 `1`，提示外部機制該 Block 已滿，需進行封裝。然而此機制包含一個關鍵的例外處理：若當前 Block 為空（`n == 0`），為了確保每個 Block 至少包含一筆有效資料（避免單筆巨量資料導致無法寫入的死結），系統會無視 `target_size` 的限制，無條件接受這第一筆寫入。
```c
struct block_builder {
uint8_t *data; // data section 的緩衝區
size_t data_len; // 目前 data section 的長度
uint16_t *offsets; // offset 陣列
uint16_t n; // 已加入的 entry 數量
size_t target_size; // block 的最大編碼大小
};
```
```c
struct block {
uint8_t *data; // data section 的原始位元組
size_t data_len; // data section 的長度
uint16_t *offsets; // entry 偏移量陣列
uint16_t n; // entry 數量
};
```
### 編碼與解碼
**block_encode**：將 `struct block` 序列化為連續的位元組陣列。依序寫入 data section、offset section、num_of_elements。回傳的 buffer 由呼叫者負責 `free`。
**block_decode**：從原始位元組反序列化為 `struct block`。從尾端開始解析：先讀取最後 2 bytes 得到 `n`，再往前讀取 `n * sizeof(uint16_t)` 的 offset section，剩餘的就是 data section。`data` 和 `offsets` 各自 `malloc` 一份副本。
### Block Meta
`block_meta` 是每個 block 的輕量級索引，儲存在 SST 的 meta section 中。開啟 SST 時，所有的 `block_meta` 會被載入記憶體。讀取時透過 `first_key` 和 `last_key` 判斷目標 key 可能落在哪個 block，避免不必要的磁碟讀取。
```c
struct block_meta {
uint32_t offset; // block 在 SST 檔案中的起始偏移量
uint8_t *first_key; // 此 block 的第一個 key（heap-allocated）
uint16_t first_key_len; // first_key 的長度
uint8_t *last_key; // 此 block 的最後一個 key（heap-allocated）
uint16_t last_key_len; // last_key 的長度
};
```
每筆 block_meta 在 SST 檔案中的編碼為：
`[ offset (4B) | fk_len (2B) | first_key | lk_len (2B) | last_key ]`
所有欄位以 little-endian 儲存。meta section 是多筆 block_meta 依序排列，沒有額外的分隔符號。解碼時透過依序讀取 fk_len 和 lk_len 來確定每筆 meta 的邊界。
### SSTable
與 Memtable 的設計理念如出一轍，系統中的 SSTable 亦區分為負責建構的 **Mutable（可變）狀態**與供查詢的 **Immutable（不可變）狀態**，分別對應 `struct sst_builder` 與 `struct sst`。
所有的資料寫入操作皆交由 `sst_builder` 統籌。為了優化記憶體使用率，`sst_builder` 採用**串流寫入機制**：在記憶體中同一時間僅維護一個 Block 的資料（透過內部的 `block_builder`）；當該 Block 達到容量上限時，便會將其儲存至實體檔案（Flush），隨即重置並開啟下一個新的 Block 以接收後續寫入。直到所有寫入任務結束，才會將整個檔案封裝並實例化為 `struct sst` 供系統讀取。
基於上述職責差異，兩者在檔案描述子（File Descriptor）的權限設定上截然不同：`sst_builder` 負責增量追加資料，必須設定為 **「可寫入」** ；而封裝完成的 `sst` 僅供檢索，必須嚴格設定為 **「唯讀」** 。
以下為兩者的核心資料結構：
```c
struct sst {
int fd; // 唯讀的 file descriptor
struct block_meta *metas; // block meta 陣列，載入記憶體
uint32_t n_blocks; // block 數量
uint64_t id; // engine 分配的唯一 ID
size_t file_size; // 檔案總大小
uint32_t meta_offset; // meta section 的起始偏移量
};
```
```c
struct sst_builder {
struct block_builder bb; // 目前正在建構的 block
struct block_meta *metas; // 已完成的 block 的 meta 陣列
uint32_t n_blocks; // 已完成的 block 數量
uint32_t metas_cap; // metas 陣列的容量
size_t data_size; // 已寫入磁碟的 data section 總大小
size_t block_size; // 每個 block 的目標大小上限
uint8_t *first_key; // 目前 block 的第一個 key（heap-allocated）
uint16_t first_key_len; // first_key 的長度
uint8_t *last_key; // 目前 block 最近加入的 key（heap-allocated）
uint16_t last_key_len; // last_key 的長度
int fd; // 寫入用的 file descriptor
};
```
## Iterators
資料檢索是資料庫系統的核心操作。然而，資料在記憶體與磁碟中的實體儲存結構截然不同：在 TierDB 中，Memtable 底層採用 Skip List 來維持動態的有序性，而 SSTable 則是基於磁碟的連續 Block 結構。這導致了兩者在底層的走訪與搜尋邏輯完全不同。
為了解耦上層查詢邏輯與底層儲存實作，系統引入了 `struct iter` 作為統一的迭代器介面。透過函式指標（Function Pointers）機制，它將各式各樣的具體迭代器封裝在相同的抽象介面下：
```c
struct iter {
void *ctx;
int (*valid)(void *ctx);
const uint8_t *(*key)(void *ctx);
uint16_t (*key_len)(void *ctx);
const uint8_t *(*value)(void *ctx);
uint16_t (*value_len)(void *ctx);
int (*next)(void *ctx);
};
```
如下方的架構圖所示，使用者不再需要知道資料的實際來源，統一透過這套介面與底層互動。
### struct mt_iter
走訪單一個 memtable 的所有 entry，直接走 skiplist 的 level 0。
### struct sst_iter
由於單一 SSTable 檔案體積龐大，將其完整載入記憶體並不切實際。因此，`sst_iter` 採用了兩層式的迭代架構與 **延遲載入（Lazy Loading）** 機制。
在實作上，`sst_iter` 負責在全域層級跨越整個 SSTable，但內部實際上是委派 `block_iter` 來執行單一 Block 內的檢索。當目前的 `block_iter` 走訪至 Block 尾端時，`sst_iter` 會自動釋放當前記憶體，從磁碟讀取並載入下一個 Block，隨後重置 `block_iter`。這種設計成功將「跨 Block 切換的 I/O 成本」封裝在底層，對上層的合併邏輯提供了一致的迭代操作。
### struct iter
提供 `sst_iter_to_iter()`, `mt_iter_to_iter()` 分別將 `struct sst_iter` 和 `struct mt_iter` 轉換成統一格式的 `struct iter`。
### struct merge_iter
`merge_iter` 的核心任務是將多個獨立且有序的資料來源「合併」成單一的有序輸出。
此結構內部包含了一個 `struct iter` 的陣列。為了正確處理資料的更新與覆寫， tierdb 制定了一項規定：**「陣列索引值（Index）越小，代表資料版本越新」**。因此，資料源傳入陣列的標準順序必須為：
1. `iters[0]`: Mutable Memtable（包含最新寫入的資料）
2. `iters[1]`: Immutable Memtable（等待 flush 的資料）
3. `iters[..]`: Immutable Memtable（等待 flush 的資料）
4. `iters[m]`: Immutable Memtable（等待 flush 的資料）
5. `iters[..]`: SSTables（依新舊順序排開的磁碟資料）
**合併與覆寫機制**
每次呼叫 `merge_iter_next` 獲取下一筆資料時，系統會嚴格執行以下三個步驟：
1. **找最小 (`find_current`)**：掃描所有的 child iterator，找出當前全局最小的 Key。
2. **輸出**：將該最小 Key 所在的 Entry 作為本次的結果輸出。
3. **跳過重複與舊值 (`skip_dup`)**：若有多個 child iterator 同時持有該最小 Key，基於「Index 越小優先權越高」的規則，最新版本會勝出。同時，系統會將所有持有該 Key 的 child iterator 都往前推（Next），讓舊資料被邏輯覆蓋並丟棄。
### struct lsm_iter
作為架構中的最頂層介面，`lsm_iter` 封裝了底層的 `merge_iter`。其主要職責是在多路合併的基礎上，實作資料的過濾與邊界控制，確保最終輸出的資料流完全符合查詢語意。
具體包含兩項核心過濾機制：
1. **墓碑過濾 (Tombstone Skipping)**：在 LSM-Tree 中，刪除操作是以寫入長度為零（`value_len == 0`）的墓碑標記來完成。`lsm_iter` 會在輸出前攔截並自動跳過這些標記，確保呼叫端只會看見有效的實體資料。
2. **上限控制 (Upper Bound Enforcement)**：支援範圍查詢（Range Query）的提前終止。當迭代器掃描到的 Key 超越了設定的 Upper Bound 時，系統將自動標記為耗盡（Exhausted）並停止迭代。
這是一段為您精心撰寫的 Engine 說明與使用範例。您可以直接將這段內容接在您原本的 Markdown 文件最末端（也就是接在 `engine_scan` 說明的後面），讓整份 TierDB 的架構文件更加完整！
## Engine
`struct engine` 是 TierDB 的最上層控制器，負責統籌管理 LSM-Tree 所有的底層資源，對外提供簡單易用的資料庫操作介面（CRUD 與 Scan）。它隱藏了 Memtable 凍結、SSTable Flush 以及多路合併的複雜度，讓應用程式層只需要專注於寫入與讀取。
> CRUD 為 Create, Read, Update, Delete 的縮寫
Engine 內部維護了三個核心的資料容器集合：
1. **Mutable Memtable**：接收所有最新寫入的活躍表。
2. **Immutable Memtables**：已寫滿並被凍結的唯讀表陣列（依寫入時間由舊到新排列）。
3. **SSTables (L0)**：已儲存至磁碟的 SSTable 檔案陣列（依建立時間由新到舊排列）。
### 基本操作 - 寫入與凍結
所有的寫入操作（包含刪除，即寫入 Tombstone）都會直接送入當前的 Mutable Memtable。當單次寫入完成後，Engine 會檢查 Memtable 的粗略大小（`approx_size`）是否超越了 `engine_options.threshold` 上限。如果超過，則自動觸發 Freeze：將當前的 Memtable 移入 Immutable 陣列，並建立一個全新的 Memtable 來接收未來的寫入。
### 基本操作 - 讀取
`engine_get` 實作了極度嚴謹的「由新到舊」優先級檢索：
1. 先查 Mutable Memtable。
2. 再由新到舊掃描 Immutable Memtables。
3. 最後由新到舊掃描 SSTables。
為了將 I/O 降到最低，在掃描 SSTable 前，Engine 會先比對該 SSTable 的 `first_key` 與 `last_key`。如果目標 Key 不在此區間內，便直接跳過，省去載入 Block 與二分搜尋的開銷。
### 基本操作 - 寫入磁碟
當系統中的 Immutable Memtable 數量達到 `imm_cap` 上限時，Engine 必須將資料寫入磁碟。`engine_flush` 會抽出「最舊的」Immutable Memtable，利用 `sst_builder` 將其轉換為磁碟上的 SST 檔案，接著將該檔案註冊至 SSTables 陣列中，最後釋放原有的 Memtable 記憶體。
### Engine 使用範例
以下示範如何透過 Engine API 來操作 TierDB，涵蓋了初始化、寫入、讀取、範圍掃描以及資源釋放的完整生命週期：
```c
#include <stdio.h>
#include <string.h>
#include "engine.h"
int main(void) {
// ==========================================
// 1. Initialize engine options and open the database
// ==========================================
struct engine_options opts = {
.threshold = 4096 * 10, // Freeze memtable automatically when it reaches 40KB
.imm_cap = 5, // Keep a maximum of 5 immutable memtables
.max_level = 16, // Skiplist max level of 16
.block_size = 4096 // Target SSTable block size (4KB)
};
struct engine db;
// Store database files in the "./tierdb_data" directory
if (engine_open(&db, &opts, "./tierdb_data") < 0) {
printf("Failed to open the database!\n");
return -1;
}
// ==========================================
// 2. Write and delete data (Put & Delete)
// ==========================================
uint8_t *k1 = (uint8_t *)"apple";
uint8_t *v1 = (uint8_t *)"red";
engine_put(&db, k1, strlen((char*)k1), v1, strlen((char*)v1));
uint8_t *k2 = (uint8_t *)"banana";
uint8_t *v2 = (uint8_t *)"yellow";
engine_put(&db, k2, strlen((char*)k2), v2, strlen((char*)v2));
// A delete operation is essentially writing a Tombstone (value_len == 0)
engine_delete(&db, k2, strlen((char*)k2));
// ==========================================
// 3. Point lookup (Get)
// ==========================================
uint8_t val_buf[256];
size_t val_len;
// Query "apple" (Expected to succeed)
if (engine_get(&db, k1, strlen((char*)k1), val_buf, sizeof(val_buf), &val_len) == 0) {
if (val_len > 0) {
printf("Get apple: %.*s\n", (int)val_len, val_buf);
} else {
printf("apple has been deleted (Tombstone)\n");
}
}
// Query "banana" (Expected to read a Tombstone)
if (engine_get(&db, k2, strlen((char*)k2), val_buf, sizeof(val_buf), &val_len) == 0) {
if (val_len == 0) {
printf("Get banana: Data has been deleted!\n");
}
}
// ==========================================
// 4. Range Scan
// ==========================================
struct lsm_iter scan_iter;
uint8_t *lower = (uint8_t *)"a"; // Inclusive lower bound
uint8_t *upper = (uint8_t *)"z"; // Inclusive upper bound
printf("\n--- Start range scan [%s, %s] ---\n", lower, upper);
// engine_scan automatically handles the allocation and ordering of all underlying iterators
if (engine_scan(&db, lower, 1, upper, 1, &scan_iter) == 0) {
while (lsm_iter_is_valid(&scan_iter)) {
printf("Scan: Key=%.*s, Value=%.*s\n",
lsm_iter_key_len(&scan_iter), lsm_iter_key(&scan_iter),
lsm_iter_value_len(&scan_iter), lsm_iter_value(&scan_iter));
lsm_iter_next(&scan_iter);
}
// Scan complete, release iterator resources (including the large buffer allocated by the Engine)
lsm_iter_destroy(&scan_iter);
}
printf("--- Range scan complete ---\n");
// ==========================================
// 5. Close the database (Release memory resources)
// ==========================================
engine_close(&db);
return 0;
}
```
Sign in via Google
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Connect another wallet