DDIA閱讀紀錄(7) – 第三章：令人臉紅心跳的Storage and Retrieval – 軟人手札
source link: https://softman.blog/2021/06/03/ddia-7-storage-and-retrieval-intriguing-beginning/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
(本日進度：loc 1900 – 2032)
天啊，今天第一次開始讀第三章，只能說太精彩了。繼第二章走訪各data model的性質後，本章進一步深入到database engine的存取實作概念。雖然我現在才剛讀完一開頭一點點，但真的是讀到忍不住啊啊啊喔喔喔又喘又叫的，旁人看到搞不好以為我在讀的是官能小說。哼哼，誰說讀技術書籍不能高⬤的？
本章以一個「世界上最簡單的資料庫」開始，因為實在太精簡了，值得在這邊照抄一下：
#!/bin/bashdb_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，似乎相關應用還不少。
段落的最後作者指出這種資料庫的兩大限制：
- 由於整組hash map必須都在記憶體中，如果鍵值太多塞不下就不適用
- Range queries不佳，例如找出kitty00000 – kitty99999間所有鍵值會需要把整個hash map巡覽一遍
以此為引，下一個段落要開始講沒有這兩項限制的SSTables與LSM-Trees了。
太興奮了啊啊啊啊啊啊啊啊！！
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK