RocksDB 的 MVCC 與交易是怎麼運作的——從一個會遞增的數字講起

看完這篇你會知道：RocksDB 怎麼讓多個 read 在 write 持續進行時仍然看到一致的資料，snapshot、WriteBatch 的原子性、SuperVersion 的引用計數、悲觀與樂觀交易的衝突偵測，全部歸結到同一件事——比較兩個 sequence number 誰大。這篇從零講起，不假設你已經懂 MVCC。

一個 read 正在進行，write 也沒停——這個場景要解決什麼問題

RocksDB 是個嵌入式 key-value store，同一時間常常有多個 read 在跑，也同時有 write 在進行。最直覺的做法是拿一把鎖：每次 read 或 write 都要先鎖住整個 db。這樣做問題很明顯——只要有一個 write 在跑，所有其他 read 都要排隊等它放手，read 之間互相打架不打緊，跟 write 打架就是全面停擺。另一個直覺做法是每次 read 開始前把整份資料複製一份，這樣 read 永遠看自己的副本，不用跟任何人搶。但複製的代價跟資料庫大小成正比，write 稍微密集一點，複製就跟不上。

這個問題在讀多寫少的場景特別尖銳。假設一個服務的 read 遠比 write 頻繁，用大鎖的做法等於讓絕大多數請求陪著少數 write 一起排隊；用複製的做法則是讓每一次 write 都拖著一整份資料一起搬。兩種代價都跟資料庫實際大小或並發數綁死，規模一大就撐不住。

RocksDB 選的路徑不鎖也不複製。它從最底層的儲存格式開始動手：每一筆寫進 memtable 或 SST 檔案的東西，不是單純的 (key, value)，而是一個三元組——「What actually gets into the memtable and SST files on disk is a triplet of (user_key, sequence_number, value_type)」。同一個 user_key 被寫入多次，不會覆蓋掉舊版本，而是各自留一筆記錄，用 sequence_number 區分先後。

同一個 key 的多個版本疊在一起——鎖不掉、也不用鎖

三元組帶來一個立即的問題：既然舊版本不會被覆蓋，memtable 裡同一個 user_key 就可能同時存在好幾筆記錄。RocksDB 用 skip list 存 memtable，排序規則是先比 user_key（遞增），同一個 user_key 之內再比 sequence_number（遞減）——「when two keys share the same user key, the one with the larger sequence number comes first」。最新版本永遠排在最前面，這件事本身不需要鎖：skip list 的併發插入靠原子指標操作完成，不是傳統的排他鎖。

skip list 被選中不是巧合。B-tree 之類的結構做原地更新，插入新版本會牽動整個 page 的排列，通常得對 page 加鎖；skip list 的每個節點只靠幾個 forward 指標串起來，插入新節點只要把前後指標接上，不需要移動既有節點，也不需要碰既有節點的鎖。這讓「同一個 key 疊多個版本」這件事幾乎沒有額外代價——多出來的只是多一個節點，排序規則保證新節點永遠插在正確位置。

但排序解決不了「read 應該看見哪一個版本」這個問題。如果一個 read 在 dog 的 b 版本（seqnum 5）寫入之後才啟動，它理所當然該看見 b；但如果它是在 b 寫入之前就啟動、只是還沒讀到這個 key，它該看見的是舊的 a，而不能被半途冒出來的 b 影響。鎖解決不了這件事，因為問題根本不是「誰先誰後搶到鎖」，是「這個 read 應該凍結在哪一個時間點」。這正是 RocksDB 引入 sequence number 比較的原因。

快照不是複製資料，是記一個數字

RocksDB 內部維護兩個關鍵的 sequence number：一個是最近配出去的號碼，另一個是「已發布」給 read 看的號碼。每個 read 查詢開始時，會記下當下的已發布 sequence number，之後所有的比較都拿這個數字當上限。原文用 dog 這個 key 舉的例子最直接：「The reader R, when it sees dog,b with the sequence number 5, will skip over it, as it is allowed to see only keys with a sequence number of 4 or below.」reader 只被允許看到 sequence number 4 或更低的版本，seqnum 5 的 b 直接跳過，改看排在它後面、seqnum 較小的 a。

snapshot API 把這個機制包成一個顯式物件：「A snapshot is just the published sequence number recorded when db.snapshot() is called - reads through the snapshot skip keys with higher sequence numbers.」snapshot 不是複製任何東西，就是記錄呼叫當下的那個數字。之後不管透過這個 snapshot 讀幾次、讀哪個 key，比較邏輯都一樣：seqnum 大於 snapshot 記錄值的版本一律跳過。

這兩個數字系統性地分工：一個記錄「目前配到哪個號」，另一個記錄「目前公開給 read 看到哪個號」。寫入的當下，配號動作先發生；號碼真正讓 read 看得到，是發布動作，兩者可以不同時發生——WriteBatch 的原子性正是利用了這個時間差，後面會講到。read 或 snapshot 要做的事，永遠只是記下當下已發布的那個數字，再拿它跟每個版本的 seqnum 比大小。compaction 也會尊重還活著的 snapshot：一份 snapshot 只要還活著，它記下的那個 seqnum 就還有 read 可能拿來當上限比對，compaction 想清掉某個舊版本之前，得先確認沒有任何還沒釋放的 snapshot 需要它——不然某個 read 半路發現自己要比對的版本已經被清空，語義就從「跳過」變成「查無此版本」，完全不是一回事。

下面這個 widget 用 dog 這個 key（原文的例子）加一個示範用的第二個 key，讓你自己拖動快照捕捉到的 sequence number，看哪個版本會被判定可見、哪個被跳過。

三個地方把「比較 seqnum」用出實際效果——skip list、WriteBatch、SuperVersion

把同一個比較動作放到三個不同的地方，就組成了 RocksDB 併發控制的骨架。第一個是剛才講過的 skip list 排序：同 key 內 seqnum 遞減排列，讓最新版本永遠排最前面，read 只要沿著 skip list 往下找，遇到第一個 seqnum ≤ 快照上限的版本就是答案。用虛擬碼寫出來大概是這樣：

// memtable skip list 排序規則：先比 user_key（遞增），
// 同一個 user_key 內再比 sequence_number（遞減）
(dog, seq=5, put, b)      // 排前面 —— 較新
(dog, seq=2, put, a)      // 排後面 —— 較舊

// 一個快照記到 seqnum 4 的 read，沿著這條 skip list 往下找 dog，
// 遇到的第一筆 seq=5 大於 4，跳過；下一筆 seq=2 符合，就是答案

這段虛擬碼想強調的是一個容易被忽略的細節：排序規則本身不做任何「決定要不要顯示」的判斷，它只負責把版本排好隊；真正決定顯示與否的，是 read 走訪這條隊伍時各自帶著的那個 seqnum 上限。把排序跟過濾拆成兩個獨立的步驟，skip list 不需要知道任何一個 read 現在在哪個時間點，插入新版本也不需要通知任何正在進行中的 read——這正是為什麼寫入跟讀取可以完全不互相阻塞。

第二個是 WriteBatch 的原子性。一個 batch 裡有多筆寫入時，RocksDB 不是一筆一筆各自配號、各自公開，而是整批一次配好一段連續的 seqnum，全部寫進 memtable 之後才一次性發布：「When the batch is applied to the database (the db.write call), sequence numbers for all keys are allocated atomically by incrementing the sequence number by 3 (the number of keys in the batch) and then publishing that number only after all three keys are inserted into the memtable.」關鍵在發布這一步——已發布的 sequence number 是任何 read 用來判斷可見性的唯一依據，只要這個數字還沒往前推，不管 memtable 裡實際上是不是已經寫了半批，read 都看不到。等三筆全部就位，數字一次跳過去，三筆同時對所有 read 可見。原子性不是靠鎖住 read，是靠「可見性只認發布後的那個數字」這個規則本身。

下面這個 widget 把這個過程拆成兩個狀態，你可以按按鈕看它們怎麼切換。

第三個是 SuperVersion。RocksDB 把「一個 read 應該看到哪些 memtable 跟哪些 SST」打包成一個結構，程式碼大致是：

struct SuperVersion {
  active_memtable: ReferenceCounter<Memtable>,          // memtable accepting writes
  immutable_memtables: Vec<ReferenceCounter<Memtable>>, // memtables ready to be flushed or just flushed
  ssts: ReferenceCounter<SstLevels>,                    // on-disk SSTs, each reference-counted individually
}

三個成分各自都用引用計數保護：一個正在接受寫入的 active memtable、一批正等著或剛 flush 完的 immutable memtables、一份磁碟上各自獨立計數的 SST 檔案。「When a read starts, it acquires a reference to the structure. The reference is released only after the read is done.」read 開始時對整個 SuperVersion 拿一份引用，結束才放，flush 或 compaction 想回收某個舊 memtable 或舊 SST，只要還有 read 在持有引用，就不能真的釋放底層記憶體。這跟前面提到的 snapshot 邏輯是同一件事的兩個層面：snapshot 靠 seqnum 攔住「不該被過濾掉的版本」，SuperVersion 的引用計數則攔住「不該被回收的整塊記憶體或檔案」——一個管邏輯上的可見性，一個管實體資源的生命週期，兩者合起來才讓 read 全程不用鎖任何東西。

交易怎麼用同一套機制判斷衝突——悲觀鎖 key，樂觀鎖 commit 那一刻

把 sequence number 比較這件事往上疊一層，就是交易的衝突偵測。RocksDB 提供兩種交易：悲觀（pessimistic）跟樂觀（optimistic），差別在「什麼時候發現衝突」。兩種交易解決的是同一個問題——一群並發的操作，怎麼知道自己有沒有跟別人打架，差別只在於這件事什麼時候被發現：悲觀交易假設打架很常見，先把手伸出去擋；樂觀交易假設打架很少見，先讓大家各自做完，最後再核對一次。

悲觀交易在寫入當下就鎖 key。鎖存在一個 per-DB 的 map 裡，把 key 對應到持有它的 transaction id：「If another transaction tries to update one of the locked keys concurrently, the conflicting transaction T2 blocks until T1 commits or rolls back.」拿到鎖之後，悲觀交易還要再檢查一次快照有效性：「After T1 acquires a lock on key a, it checks whether the key was updated after the snapshot was set」——確認的內容是「whether there is a version of the key in the database with a sequence number higher than the snapshot sequence number」。鎖負責擋住未來的衝突寫入，seqnum 比較負責檢查過去有沒有已經發生的衝突——兩件事分開做，但底層檢查的動作是同一種比較。

樂觀交易的做法更輕量。它不追蹤每個 key 各自的鎖，而是把 key 雜湊進一組預先配置好的 mutex：「the lock manager hashes keys into 1M pre-allocated mutexes (yes, 1M is a lot - it trades off memory for reduced contention)」——一百萬個 mutex，用記憶體換低碰撞率。這個數字反映了一個具體的取捨：mutex 越多，不同 key 雜湊撞在同一個 mutex 上的機率越低，但每個 mutex 都要佔一份常駐記憶體，等於為「幾乎不會全部用滿」的容量先付一筆固定成本。換來的是不用維護一個會隨交易數量長大的鎖表——鎖表本身在高並發下也會變成熱點，把它換成固定大小、雜湊分散的 mutex 陣列，等於把熱點打散了。真正的衝突偵測延後到 commit 那一刻才做：交易記下每個讀過或寫過的 key 當時的 seqnum，commit 時重新比對一次，「If it contains a key with a sequence number larger than the recorded one, it means another transaction already committed the same key」——結果就是「the commit fails」。記錄的 seqnum 被超過，代表有別人搶先了，commit 直接失敗，交易要重來。

樂觀交易有個具體的代價：它的驗證只查 memtable，不像悲觀交易會查整棵樹。「Optimistic transactions limit validation to memtables (pessimistic transactions check the whole tree). If the memtable is flushed mid-transaction, there is nothing left to validate against, so the commit fails.」如果交易進行到一半，memtable 剛好被 flush 到 SST 去，用來比對的那個 seqnum 記錄就消失了，commit 只能直接判失敗——不是真的偵測到衝突，是驗證對象不見了。兩種交易在負載形狀不同的情境下互有勝負：原文的測試裡，key 爭用激烈時「the throughput of optimistic transactions stays flat, while pessimistic transactions queue on the shared key's lock」，樂觀交易吞吐量維持平穩，悲觀交易則因為排隊等同一把鎖而下滑。

四種隔離等級的邊界，跟一個很少人用得到的 range lock

把 seqnum 比較機制套進標準的隔離等級詞彙，邊界在哪裡就很清楚。四個等級排下來，真正在變的不是「有沒有用 seqnum」——所有等級用的都是同一套比較機制，變的是比較的時機跟比較的範圍有多寬：Read Committed 每次 get 都重新記一次當下已發布的 seqnum；Snapshot Isolation 整個交易共用同一個；Serializable 想逼近的則是「連還沒發生的寫入都要考慮進去」，而這正是單純比較 seqnum 做不到的地方——phantom read 之所以是個洞，是因為它牽涉到一個當下根本不存在、還沒有 seqnum 可比的 key。

range scan 的 phantom read 有個專門的解法：range lock，鎖住的不是單一 key，是一整段 key range，插入這段範圍內的新 key 也會被擋下。但這個功能目前的處境有點尷尬：「It was contributed in 2020, but it's not documented anywhere on the RocksDB wiki and not exposed through the C or Java APIs, so the feature is usable only from C++.」2020 年就進了程式庫，六年後 wiki 上還是找不到說明，C 跟 Java binding 也沒補上，能摸到它的只有直接用 C++ API 的使用者。對大多數只用 get／put 的應用來說，這個限制不痛不癢——用不到 range lock，也就碰不到它的文件洞。但只要應用邏輯裡有「先掃一段 key range 再決定要不要插入」這種模式，像唯一性檢查或排隊之類的場景，Serializable 那個逼近就撐不住，這時候唯一能補上的機制卻卡在只有 C++ binding 摸得到的位置。

真正在生產環境直接用 RocksDB 交易的專案不多。原文作者自己的觀察是：「MyRocks... and ArangoDB are the only large projects I'm aware of that rely on RocksDB transactions.」——這是他自己知道的範圍，不是窮舉。分散式資料庫大多不用：「RocksDB-native transactions are node-local... and with a distributed database you have to coordinate transactions across multiple nodes.」TiDB、YugabyteDB、CockroachDB 都自己蓋了一層交易協調，原因很直接——RocksDB 原生交易只管單一節點內的衝突，分散式系統要跨節點協調，這件事 RocksDB 本身管不到，得在它之上另起一層。這也說明「交易」在 RocksDB 裡的定位比較像是給單機應用用的便利功能，不是給分散式系統當地基：它解決的是同一份 seqnum 序列內部的衝突，一旦協調對象跨過單一行程、單一磁碟，seqnum 比較這個原語本身就不夠用了，分散式系統需要的是跨節點的時鐘或共識協議，那是完全不同的另一層機制。

Take-away：RocksDB 沒有為 MVCC、快照、交易分別設計三套機制——它只有一個會遞增的 sequence number，snapshot 是記下它、WriteBatch 的原子性是延遲發布它、悲觀交易是鎖了 key 之後比它、樂觀交易是 commit 時重新比它。學會這一個數字怎麼被比較，上面所有名詞都只是它的應用場景。