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了。

太興奮了啊啊啊啊啊啊啊啊!!

對「DDIA閱讀紀錄(7) – 第三章:令人臉紅心跳的Storage and Retrieval」的一則回應

James Tien 發表迴響 取消回覆

Please log in using one of these methods to post your comment:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.