第 3 / 12 部 待錄

儲存與檢索

《Designing Data-Intensive Applications（DDIA）》Podcast 準備稿：儲存與檢索

書名： 設計資料密集型應用 Designing Data-Intensive Applications（The Big Ideas Behind Reliable, Scalable, and Maintainable Systems） 作者： Martin Kleppmann 系列： 啃一本大書（恩普拉氏） 公開標題建議： 啃一本大書｜DDIA．LSM-Tree vs B-Tree：資料庫引擎的世紀對決 (3/12) 涵蓋範圍： 第4章 儲存與檢索（雜湊索引、SSTable／LSM-Tree、B-Tree、OLTP vs OLAP、列式儲存）

背景速覽

上一集談「資料用什麼模型表示」，這集往下鑽一層：這些資料在磁碟上到底怎麼存、怎麼找回來。這是 DDIA 裡技術密度最高、也最讓工程師「功力升級」的一章。核心對決是兩大 OLTP 索引結構——LSM-Tree（日誌結構）vs B-Tree（原地更新）；後半段切到 OLAP，講資料倉儲為什麼需要完全不同的引擎，以及列式儲存的魔法。這章是面試最愛問、也最能拉開工程師段位的一章。

一句話重點

資料庫的讀寫效能不是玄學，而是由索引結構的取捨決定的：LSM-Tree 把隨機寫變成循序寫、寫得快但讀要查多層，B-Tree 原地覆寫、讀得穩但每筆至少寫兩次；而當你從「按鍵取少量記錄」（OLTP）切換到「掃描海量記錄做聚合」（OLAP）時，連儲存的方向都要從「按列」翻轉成「按欄」——沒有萬用引擎，只有對的工作負載配對的引擎。

值得討論的重點

1. 從「兩行 Bash 的資料庫」開始，理解索引的本質取捨

Kleppmann 的招牌教法：最簡單的資料庫就是 db_set（把鍵值附加到檔尾）＋ db_get（掃整個檔案找最新值）。寫入超快（append），但讀取是 O(n)，資料一多就慢成狗。於是我們需要索引——一種從主資料衍生的額外結構。但這裡有個貫穿全章的鐵律：

精心選的索引加速讀取，但每個索引都拖慢寫入。 所以資料庫不會幫你索引所有欄位，要你自己根據查詢模式手動選。

這個「讀寫取捨」就是整章的主旋律。

2. LSM-Tree：把隨機寫變成循序寫的魔法

雜湊索引（Bitcask）簡單但兩個硬傷：雜湊表必須放進記憶體、範圍查詢爛。解法是要求段檔案按鍵排序——這就是 SSTable。好處有三：合併像 mergesort 一樣高效、不用在記憶體存所有鍵（只要稀疏索引）、能區塊壓縮。

運作方式：寫入先進記憶體的排序結構（memtable），滿了就刷成 SSTable 檔案，背景持續合併壓縮。這就是 LSM-Tree（Log-Structured Merge-Tree）——LevelDB、RocksDB、Cassandra、HBase 全是這一派。配合 Bloom filter（快速判斷某鍵「一定不存在」，省下無謂的磁碟讀）效能更好。

3. B-Tree：統治關聯式資料庫四十年的老將

B-Tree（1970 年問世）跟 SSTable 一樣按鍵排序，但設計哲學相反——它把資料庫切成固定大小的頁面（page，通常 4KB），原地覆寫（overwrite in place）。分支因子常達數百，所以一棵 4 層 B-Tree 就能存 256TB。

關鍵差異在這裡：B-Tree 原地改，所以頁面分裂時若崩潰會壞索引，得靠 WAL（write-ahead log） 保命；多執行緒存取要用 latch（輕量鎖）。而 LSM-Tree 是追加式的、段檔不可變，所以並行與崩潰恢復天生簡單。

4. 世紀對決：一句話記住誰快

經驗法則：LSM-Tree 寫得快，B-Tree 讀得快。

  • LSM-Tree 優勢：寫入放大低（B-Tree 每筆至少寫兩次：WAL ＋ 頁面，且改幾個 byte 也要寫整頁）、循序寫吞吐高、壓縮率好檔案小。對 SSD 尤其友善（SSD 寫入次數有限）。
  • LSM-Tree 劣勢：壓縮過程會干擾正常讀寫，造成高百分位延遲不穩；高寫入下壓縮可能跟不上、磁碟爆掉。B-Tree 延遲更可預測，且每個鍵只在一處、利於強交易語意（用鎖實作隔離）。

這不是「誰比較好」，是「你的工作負載偏讀還偏寫、要穩定延遲還是要高吞吐」。

5. OLTP vs OLAP：連儲存方向都要翻轉

後半章是另一個世界。OLTP（交易處理）：按鍵取少量記錄、低延遲、終端使用者。OLAP（分析）：掃描海量記錄做聚合、給分析師。兩者差太多，所以企業把資料抽到獨立的資料倉儲（透過 ETL），用星型架構（事實表居中、維度表環繞）組織。

而 OLAP 的殺手鐧是列式儲存（column-oriented storage）：不把一列的所有欄位存一起，而是把一個欄位的所有值存一起。因為分析查詢通常只碰一張寬表的 4–5 個欄位——列式儲存讓你只讀用到的欄位，I/O 大降。再配合點陣圖編碼、遊程編碼、向量化處理（SIMD），分析查詢快上數量級。

注意事項

⚠️ 「LSM 寫快、B-Tree 讀快」是經驗法則，不是定律。 Kleppmann 自己強調：基準測試結果常常不一致、對工作負載細節極度敏感。一定要用你自己的真實資料測。 別在節目裡（或工作裡）把這條經驗法則講成鐵律——它是「思考的起點」，不是「結論」。

⚠️ 列式儲存不是「另一種資料庫」，是「另一種存放方向」。 容易被誤解成 OLAP 專屬的黑科技。其實它的核心假設很樸素：每個欄位檔案裡的列要以相同順序排列，這樣取第 k 列就是從每個欄位檔取第 k 個。而且寫入很麻煩（不能像 B-Tree 原地改壓縮欄位），解法又是借 LSM-tree 的思路（寫進記憶體、批次合併）——整章你會發現 LSM 的思想無所不在。

⚠️ 記憶體資料庫快的原因，常被講錯。 Redis 之類快，不是因為「不用讀磁碟」（OS 的檔案快取早就在做這件事），而是因為省去了「把記憶體結構編碼成磁碟格式」的開銷。這個細節值得澄清，否則聽眾會以為「記憶體資料庫＝把資料放 RAM 就好」。

專家補充

💡 這一章是「工程師段位分水嶺」。 能講清楚「為什麼 Cassandra 寫很快但讀要查多層」「為什麼 MySQL InnoDB 用 B+Tree」的人，跟只會「裝個資料庫連上去用」的人，是兩個段位。建議節目把這章當成整季的「硬核高峰」來經營——聽懂這一集，後面講複製、分片時會輕鬆很多，因為那些都建立在「資料怎麼存」之上。

💡 「寫入放大（write amplification）」是 SSD 時代的關鍵字。 一筆邏輯寫入，實際在磁碟上造成幾倍的物理寫入？B-Tree 因為 WAL ＋ 整頁覆寫，放大嚴重；LSM 雖然壓縮也重寫，但循序寫壓縮過的 SSTable 通常更省。在 SSD 上這直接關係到硬碟壽命——這也是為什麼近年很多新資料庫（CockroachDB、TiKV 底層的 RocksDB）選 LSM 系。

💡 資料立方體（data cube）是「預先計算」哲學的極端案例。 把聚合值按維度先算好，查詢飛快，但喪失彈性（無法回答沒預先算的問題）。這個「把工作從讀取時搬到寫入時」的取捨，是 DDIA 最後一章（衍生資料的「寫入路徑 vs 讀取路徑」）的伏筆——索引、快取、物化視圖本質上都在做同一件事。

💡 B-Tree 的 copy-on-write 變體（如 LMDB）值得一提：它不原地覆寫，而是把改過的頁面寫到新位置、建新的父頁面指過去。這其實是在向 LSM 的「不可變」思想靠攏——兩派並非壁壘分明，而是在互相借點子。

討論問題

🎙️ 開場鉤子：「為什麼 Cassandra 的寫入快到誇張，但讀取有時候慢吞吞？為什麼 MySQL 反過來？這不是廠商行銷，是兩種索引結構從骨子裡就做了相反的取捨——今天我們把這個取捨拆開來看。」

🎙️ 自問自答：「為什麼資料庫不乾脆把所有欄位都建索引、讓查詢都飛快？」用全章鐵律回答：因為每個索引都是寫入的稅，索引越多寫越慢——讀寫永遠在拔河，沒有免費的午餐。

🎙️ 帶走的一題：「下次你選資料庫時，先問自己一句——我這個系統是寫多還是讀多？要的是穩定的延遲還是爆量的吞吐？答案會直接告訴你該往 LSM 還是 B-Tree 那一邊靠。」

更大範圍關聯

  • 這章是後面所有章節的地基：複製（第5集）傳的是什麼？是 replication log——本質就是儲存層的變更流。串流處理（第11集）的 CDC，靠的是解析資料庫的 WAL。你不懂「資料怎麼存」，就看不懂「資料怎麼在機器間流動」。 所以這一集投資越多，後面回報越大。
  • 與 Alex Xu 面試書的分工：面試常問「為什麼選這個資料庫」，DDIA 這章給你的是引擎層的彈藥——你能講出「因為這是寫密集的時序資料，LSM 系的寫入放大低、循序寫吞吐高」，而不是「因為大家都用 Cassandra」。（見 [軟體工程領域切分藍圖] §5「軟體架構演進」）
  • 思想連線：列式儲存源自 Google 的 Dremel（後來的 BigQuery、Parquet），LSM-Tree 源自 Google 的 Bigtable 論文——這一章幾乎是「Google 基礎設施論文的科普版」，把那些改變產業的論文，翻譯成工程師聽得懂的取捨語言。

錄製建議

  • 建議時長：約 25–28 分鐘（這是技術最重的一集，值得多給時間）。配比：索引本質取捨＋雜湊索引約 5 分；LSM-Tree 約 7 分；B-Tree 約 5 分；世紀對決（誰快、為什麼）約 5 分；OLTP/OLAP ＋列式儲存約 6 分。
  • 討論策略：一定要從「兩行 Bash 資料庫」開場——這是 Kleppmann 最天才的教法，把抽象的索引概念變得超具體。中段 LSM vs B-Tree 用「寫快 vs 讀快」這個鉤子串起所有細節。OLAP 那段用「為什麼分析查詢要把儲存方向翻 90 度」當切換點，畫面感很強。
  • 這集硬核，建議節奏放慢、多用比喻（memtable 像「緩衝區」、Bloom filter 像「門口的保全先擋掉不存在的訪客」、列式儲存像「把 Excel 直著存」）。聽眾撐過這一集，整季就穩了。