DDIA閱讀紀錄(7) – 第三章：令人臉紅心跳的Storage and Retrieval

(本日進度：loc 1900 – 2032)

天啊，今天第一次開始讀第三章，只能說太精彩了。繼第二章走訪各data model的性質後，本章進一步深入到database engine的存取實作概念。雖然我現在才剛讀完一開頭一點點，但真的是讀到忍不住啊啊啊喔喔喔又喘又叫的，旁人看到搞不好以為我在讀的是官能小說。哼哼，誰說讀技術書籍不能高⬤的？

本章以一個「世界上最簡單的資料庫」開始，因為實在太精簡了，值得在這邊照抄一下：

#!/bin/bash

db_set () {
    echo "$1, $2" >> database
}

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

這種append-only的讀寫策略很顯然寫入非常有效率，但讀取會是一場災難。從這裡，作者進一步帶出hash indexes的概念：透過一個在記憶體中的hash map去儲存從key到file offset的map來解決讀取效率問題，同時指出任何index都會增加寫入的overhead，這也是為什麼幾乎所有資料庫都不會預設index。這讓我想起以前年少不懂事，曾經搞出過index file比實際資料還龐大的烏龍。

由於是append-only，那代表任何對已存key的更新或刪除事實上是透過在檔案尾端新增一筆相同key的紀錄來完成。雖然概念上簡單，但書中指出這在實作上其實有很多挑戰，例如空間使用效率上需實作compaction來把所有相同key的records合為1個，以及把一個資料庫檔案切成多個"segment"等等。

既然有了這組map，那這代表我們可以直接in-place覆寫檔案來實作update嗎？作者在這裡回顧了上面的極簡資料庫，指出這種append-only的log structure其實出乎意料地有效，因為它是一種sequential operation，這在過去磁盤為主的硬碟尤其重要；上面提到的compaction若造成segment merge，也會是sequential operation。

實作以上hash indexes的代表性key-value store為Bitcask，稍微看了一下它的repo，似乎相關應用還不少。

段落的最後作者指出這種資料庫的兩大限制：

1. 由於整組hash map必須都在記憶體中，如果鍵值太多塞不下就不適用
2. Range queries不佳，例如找出kitty00000 – kitty99999間所有鍵值會需要把整個hash map巡覽一遍

以此為引，下一個段落要開始講沒有這兩項限制的SSTables與LSM-Trees了。

…

太興奮了啊啊啊啊啊啊啊啊！！