儲存引擎:LSM-tree、B-tree,與欄式儲存

上一篇選好了資料模型,這篇往最底層鑽:資料庫到底怎麼把資料放上磁碟、又怎麼找回來? DDIA 這章從一個兩行 bash 的「全世界最簡單資料庫」開場——db_set 就是往檔案尾巴 append 一行,db_get 就是 grep 全檔取最後一筆。寫入快到極致(順序附加),讀取慢到絕望(O(n) 全掃)。而全章、甚至所有儲存引擎,都在回答同一道題:為了讓「讀」快一點,你願意讓「寫」付出多少整理成本? 索引就是這道取捨的名字——它用寫入時的額外功夫,買讀取時的速度;索引不是免費的,這章告訴你那筆帳到底怎麼付。

兩大流派:事後整理的 LSM,就地更新的 B-tree

把「怎麼付整理費」這個問題推到底,世界上的儲存引擎其實只有兩大流派:

LSM-tree(log-structured):寫入先進記憶體的 memtable,滿了整批順序刷成一個不可變的 SSTable 檔,永不回頭改——舊值靠背景的 compaction 合併清掉。寫入永遠是磁碟最愛的順序 append,所以寫得飛快;代價是讀一個 key 可能要從新到舊翻好幾層(bloom filter 幫你快速跳過沒有的)。B-tree:資料放在固定大小(如 4KB)page 組成的樹,寫入是找到那個 page 就地覆寫;讀取沿樹走三四層就到,又快又穩。代價是就地更新是隨機 I/O、而且為了防「改到一半當機」,每次都得先寫一筆 WAL。同一筆整理費,LSM 選擇欠著之後付(compaction),B-tree 選擇當場付(隨機寫 + WAL)

兩派的取捨可以壓成一句:LSM 把磁碟當 log 用、寫入極快,但欠下的整理債要用 compaction 慢慢還(還會放大寫入量);B-tree 每筆寫當場歸位、讀取路徑短而穩定,是幾十年來關聯式資料庫的骨架。你其實兩邊都早就見過:Redis 的 AOF 就是純 append 的 log、Kafka 的 partition 就是一條只增不減的 log(它「磁碟為王」的秘密正是順序寫),而你每天下的 SQL 背後,那顆索引幾乎就是一棵 B-tree。

OLTP vs OLAP:同一份資料,兩種擺法

第二個大主題,是「讀的形狀」不同,連資料該怎麼橫著擺還是直著擺都不同。交易型(OLTP)的讀寫是「取少數幾筆的完整資料」——查一張訂單、改一個會員;分析型(OLAP)是「掃過幾億筆、但每筆只要兩三個欄位」——算上季每天的營收總和。用同一種擺法伺候兩種讀法,注定有一邊很痛:

列式把一筆資料的所有欄位連續擺——查一張訂單讀一處全拿,OLTP 超快;但分析只要 amount 一欄時,你被迫把每列的全部欄位都掃進來。欄式反過來,把同一欄的值連續擺——掃十億筆只讀那一串,I/O 直接省一個數量級,而且同型別的值相鄰、壓縮率極高(一串重複的日期壓到不像話)。這就是為什麼分析世界全是欄式:數倉、Spark 生態的 Parquet,都是這個擺法。資料庫與資料倉儲的分家,根子上就是「讀的形狀不同 → 擺法只能二選一」

所以「為什麼不能直接在 Production DB 上跑分析」這個 DE 日常問題,答案在儲存層就寫死了:不是 DBA 小氣,是列式擺法天生伺候不了掃全表的讀法(反之亦然)。把資料從 OLTP 搬去欄式的倉儲再分析——這正是分層資料架構、整個資料工程管線存在的底層理由。

反思

「append-only 討好磁碟」是貫穿現代資料系統的一條暗線

讀完這章我才把散落各處的點連成線:LSM 的 SSTable、B-tree 的 WAL、Redis 的 AOF、Kafka 的 partition log——全都是同一招:順序 append。 磁碟(連 SSD 都是)天生痛恨隨機寫、熱愛順序寫,所以幾十年來的儲存設計,骨子裡都在做同一件事:把隨機的寫入需求,改寫成順序的 log。 連最「就地更新」的 B-tree,都得靠一條 append-only 的 WAL 才敢動手。認出這條暗線之後,我看任何新儲存系統的第一個問題都變成:它在哪裡把隨機寫變成了順序寫? 幾乎每次都問得到答案——這就是好原理的力量,一條線串起十個工具。

選引擎,是選「整理費付在哪個時間點」

LSM vs B-tree 吵了很多年誰快,但這章給我最乾淨的理解是:兩邊付的是同一筆「為了讀而整理」的費用,差別只在付款時間。 B-tree 當場付清(每筆寫就地歸位、隨機 I/O + WAL),所以讀取路徑永遠短而穩;LSM 先賒帳(寫入只管 append),把整理債留給背景的 compaction 慢慢還——寫入尖峰時很爽,但債會利滾利(寫入放大),還債的 compaction 還可能跟前台搶 I/O。沒有比較快,只有把成本搬到你比較付得起的時刻。 這把尺我現在到處用:寫多讀少、能容忍讀取偶爾抖動 → LSM 系(Cassandra、RocksDB);讀寫均衡、要穩定的查詢延遲 → B-tree 系(關聯式)。選型吵架時把問題翻譯成「你想什麼時候付整理費」,爭論通常就結束了。

OLTP / OLAP 分家教我:沒有一種擺法能伺候所有讀法

欄式儲存那一節,替我把 DE 這行的「存在理由」講到了根上。同一份訂單資料,交易系統要「一次一筆、整筆拿」,分析要「十億筆、只挑兩欄」——讀的形狀不同,最佳的物理擺法就是不同的,而一份資料同時只能有一種擺法。 所以才需要把資料從 OLTP 複製出來、轉成欄式、餵給分析——ETL、數倉、Medallion、乃至之後 DDIA 第三部的「衍生資料」,全是這個物理限制的下游後果。這也讓我對「一個系統通吃 OLTP + OLAP」的宣傳保持清醒:它不是不可能,但底下一定藏著「兩份擺法、自動同步」之類的機制,而那個同步就是新的複雜度。資料工程的很多工作,本質上就是在替同一份資料維護「第二種擺法」——想通這點,你會更清楚自己每天在做的事,到底在解哪道物理題。