前面幾天我們談了 Data Model，為你的數據系統挑個合適 Data Model 後，接下來就要談談怎麼儲存與檢索了，資料庫 (database) 就做這 2 件事，給它資料後它儲存，之後還要能檢索資料，

每個 Data Model 都有對應之資料庫，它們會實做不同的儲存引擎 (storage engine)，我們有幸活在這個年代，現在不太需要動手實做資料庫了，但我們得知道它們的原理，否則我們無法選合適的資料庫，首先我們來聊聊 2 個類似的儲存引擎，log-structured 和 page-oriented 。

資料庫的原力：Data Structure

首先用 Bash 來建立個簡單的資料庫，

#!/bin/bash
db_set () {
	echo "$1,$2" >> database
}

db_get () {
	grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

我們有 2 個在簡單不過的 function，給 db_set key 及 value，它會用逗號組合起來後 append (附加) 到檔案中 (CSV-like 格式)， db_get 則是找到符合 key 的最新資料 (用 tail -n 1)，我們新增幾個 JSON 來舉例：

$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}' 

$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'

$ db_get 42 
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}

在新增一次 key 為 42 的資料，db_get 取到的是最近一次新增的資料，

$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}' 

$ db_get 42
    {"name":"San Francisco","attractions":["Exploratorium"]}

$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}

db_set 有非常好的 performance，因為夠簡單、有效率，許多資料庫內部實做時稱 append-only log，

但 db_get 就不是這麼有效率了，如果你的 database 筆數非常大，你得需要 O(n) 的時間才能找到指定的 key，若多一倍資料，你得多花一倍的時間，為了有效率的查找資料，我們得建立另一個不同的 data structure：index 。

index 的概念是替我們的主要增加額外 meta data，不同的方式會建立不同的 index，index 影響的層面只有查詢，你無法用 index 加速寫入，因為你很難打敗 append-only log，另外任何 index 都會提高寫入資料的時間，因為額外的 meta data 也需要更新，這裡依舊需要工程師選擇適合的欄位建立 index。

這裡的 log 不是指系統執行時產生的，而是 append-only 且有序的記錄，它不用一定要讓工程師看得懂，通常是 binary 字串或者是某些程式語言讀的格式。

Hash Index

讓我們用 key-value 資料來開始學學第一個 Index 吧，key-value 資料很像許多程式語言有的 dictionary 型態，也是 Hash map 的實做方式，我們也可以用相同的概念為我們在硬碟的資料建立 index，延用前面提到的範例，我們在記憶體中建立一個 hash map 存我們 database 的資料是從哪個 byte offset (偏移)開始，如下圖所示：

這聽起來很簡單對吧！？但這真的是一個非常有效的辦法。

壓實 (compaction)

再來要談談怎麼避免硬碟爆掉，我們知道 append-only log 是很有效的方式，但總不能無止盡的 append 吧！

一個好的解決方案就是我們指定每個 segment log 的大小，當達到該容量時，我們可以對該 log 做 compaction (壓實) ，compaction 後該 log 只會有最新的 key value，如下圖：

若 segment log 不大，一次做多個也 OK，

當然在 compaction 期間並不會對查詢有任何影響，當 compaction 完成後，只要把查詢 request 切到新的 segment log 去就好了，舊的 log 就可刪除了。

每個 segment log 都有自己的 hash map index，查詢時，會依序從最新的 hashmap 找資料，其他實務上該注意的地方還有：

• 刪除資料 (Deleting records)

  當你想要刪除資料時，並不會真的找到所有有該 key 的 segment log 裡刪掉該筆檔案，我們會另外新增一個刪除用的檔案 (稱 tombstone)，當查詢或 compaction 時，會去忽略該筆被刪除的資料。

• 故障恢復 (Crash recovery)

  當資料庫重啟時，理論上在記憶體中的 hash map 會全部消失，所以我們需要重建毎個 segment log 的 hash map，有些資料庫也會把 hash map 的 index 資料寫到硬碟中。

• 部份寫入 (Partially written records)

  不幸的當資料庫掛掉時，有些正在寫的 log 會寫不完全，有些資料庫會有 檢查點 (checksums) 機制，讓資料庫能略過爛掉的資料。

• 並發控制 (Concurrent control)

  寫入時需要嚴格控制寫入時的順序，所以通常只會有一個執行緒執行寫入動作，除了 append 以外，log 是不可變的，所以查詢就可以並發多個執行緒一起作業。

當然，hash map index 也是有幾個限制：

• hash map 必須存在記憶體中，我們不能期望維護存在硬碟的 hash map 會快到哪裡去，會有太多的隨機訪問存取 I/O。
• 範圍查詢非常沒效率，舉例來說，你無法簡單的找 st0001~st0009 的所有資料，在 hash index 下，你只能一次次的獨立找。

明天會介紹 SSTables 跟 LSM-Tree 是怎麼突破這些限制的。