KV引擎到關係型資料庫存儲引擎之間的距離

02-01

前一段, 本人不知天高地厚, 認為自己造出了很厲害的輪子, 大有秒天秒地秒空氣的意思. 在受到許多質疑後, 我心情就很低落, 明明是好主意, 怎麼就沒人明白呢? 所以, 我陷入了民科般的狂熱中去了. 但我終究不是民科, 我會認真看書籍論文去學習的. 至於丟臉嘛, 常有的事情, :-D.

作為一個傻吊, 我來分享一下, 這幾天學到的.

由於我根本不關心關係型資料庫是怎麼使用的, 或者是怎麼解析SQL語句的, 我直接從<DATABASE SYSTEMS: The Complete Book>的Database System Implementation章節看起.

假使要實現ACID中的A, 就必須要上日誌, 這個一般人都能想到. 在正統的資料庫書籍中, 分為3種模式.

undo log
redo log
undo/redo log

undo log指的是每次變動資料庫之前, 先把原有的值備份, 如果操作過程中crash了, undo log就會缺乏對這次操作的結尾(commit log), 說明失敗, 那麼順著undo log把原先的值回寫一遍就好了.

redo log是leveldb採用的方式, 當log寫入新值成功後, 才開始操作.

undo/redo log是二者混合.

但這書還有別的一些油管視頻都在暗示一個觀點, 資料庫操作和log是交叉進行的, 所以順序很重要. 這個假設導致許多不必要的複雜性.

繼續拿leveldb舉例, log和數據操作是完全分開的, 不存在著說修改memtable的時候, log還要寫的情況. 來一個write batch, log一寫, 然後就是批量插入memtable, 如果滿了, flush進硬碟. 大部頭這麼寫, 估計是延續了資料庫上古時期資源緊張時的設定吧.

leveldb之所以不能成為MySQL之類的存儲引擎就是缺乏了transaction的支持. 我對數據結構比較感興趣, 就形而上學, 認為transaction不就是多個操作像一個原子操作嘛, leveldb的write batch和snapshot就差不多了啊, 我levi-db支持這個就差不多了吧. 但其實transaction是一個非常複雜的概念, 只是有非常簡單的描述.

Facebook的RocksDB小組專門為了MyRocks(MySQL的RocksDB-based引擎)出了視頻介紹, https://www.youtube.com/watch?v=tMeon8FHF3I(油管, 請翻).

訂票問題:

"tickets"的num(餘量)為1,

兩個人同時從兩台訂票終端發起訂票任務, "--tickets". 在合理的資料庫中, 只可能有一個人訂票成功.

對於這個問題, 你把leveldb的介面玩出花都沒辦法解決. A訂票終端Get tickets, 發現有票, Put tickets 0. B終端也觀測到Get tickets = 1, Put tickets 0. 這樣, 儘管餘量只有一張, 但卻有兩個成功的訂單. 無論是使用snapshot還是write batch都沒有任何幫助, 你們可以思維實驗來試試.

最簡單的方法就是: "序列化"

每個訂票終端操作時獨佔整個資料庫, A訂票終端完成任務後, 無論成敗, 才能讓B訂票終端操作. 這無疑是個噩夢. 我一開始有疑問, Redis不就是單線程的么, 也跑得很歡啊. 這充分體現了我對於SQL業務模型的不了解. 每個transaction完全有可能要等待用戶的反饋, 所以CPU單核性能再高, 也是沒有任何意義的. 一個資料庫必須要支持transaction的並發, 才能叫做可用.

並發解決可用性問題, 同時還有正確性的問題. 在並發執行transaction的時候, 我們不應該得到反直覺的結果, 這就很像多線程了. 這些transaction各個步驟的執行順序安排, 叫做schedule. 我花了一個下午看了油管印度小哥的視頻集, 看得頭昏腦漲, 不是為了掌握理論原理, 沒什麼必要看. 因為不可能有人允許"read uncommitted"這種隔離等級. 那些視頻深入探討了如果不做任何干預, schedule會怎樣, https://www.youtube.com/playlist?list=PLbKVlnc3OmnwG-2-EeoheUZxBHwJhRaZ-.

題外話: 國人真的是太少分享了, Youtube上優秀的CS相關視頻/公開課一大把, 都是免費的. 中國求知的人卻不得不支付高昂的知識費用. 學好英語起碼可以省10W以上的學費!

解決方案1:

大名鼎鼎的2PL(2 Phase Lock),

CS的概念多, 但很多本質上還挺簡單的. 2PL說白了就是加鎖, 這個在多線程已經用爛的概念, 在資料庫就叫做2PL了... CS的人真的很喜歡新瓶裝舊酒啊. 所以面試的時候, 如果被問成傻逼, 我告訴你, 不要慌, 很可能很多高深的名詞, 你學了發現, 哇, 就是那麼回事兒. 我曾經因為沒做過LeetCode被問easy難度的題目, 做不出來, 馬路邊哭了五分鐘, 深感智商不如人. 我之後做了LeetCode發現, 這玩意兒熟能生巧罷了.

言歸正傳, 2PL的兩個階段, 一個是加鎖階段, 一個是解鎖階段, 細分還能是Basic 2PL, Strict 2PL, 嚴謹(英文單詞忘了)2PL, 保守(英文單詞又忘了)2PL. 但這些都是bull shit... 你只要知道這裡加鎖就是了.

回到訂票問題,

A訂票終端有可能修改tickets, 獲得了tickets的寫鎖, 得到數目為1, 自減, 寫會0.

B訂票終端在查詢tickets發現A已經獲得了tickets的寫鎖, 只能等待. 等待結束後, 發現num為0, 自減不成功, 返回或者abort(如果有別的操作的話).

就這麼簡單, 這個叫悲觀CC. 另外會導致死鎖也確實挺讓人悲觀的.

解決方案2:

時間戳.

每條記錄分別記錄最近讀寫的時間戳, 發現衝突, 就放棄, 規則叫做Thomas Write Rule. 這個自己去wiki就明白了.

這叫樂觀CC(OCC).

我剛剛描述的是Basic T/O, 這是樂觀CC的一種實現.

OCC還能指基於read/write set最後validation的演算法.

一個名詞可以有兩種意思.

很多教材還有大篇幅講述什麼rollback, save point怎麼做, 怎麼schedule才能recoverable. 我覺得都是架構複雜的鍋, 沒什麼必要.

我看了RocksDB的TransactionDB的實現, 啥transaction啊, 就是很簡單, 一個lockmap加write batch. 就跟上面log和資料庫操作要交叉會導致系統複雜一樣, leveldb/rocksdb有了memtable, 根本沒必要太費心去解決不存在的問題.

MVCC意味著什麼?

如果有人說一個資料庫存儲引擎是MVCC的, 那他話肯定沒說完. MVCC+2PL, 或者MVCC+OCC才是嚴謹的說法.

大概就是在沒有需要等待語義的衝突的時候, 我修改是創建新版本, 讀取時查詢合適的版本, 多線程CAS演算法也是類似精神.

大概就是這些了. 藉助一些人的鞭策, 我去了解了一些資料庫基礎概念, 在這裡讓各位peer review一下. 我個人認為leveldb式API加transaction manager就可以當MySQL的存儲引擎了, 是這樣嗎? 我看了看MySQL的storage的API跟我想的差不多. 還有個upsacledb的, 這個作者寫了mysql-upsacledb(cruppstahl/upscaledb-mysql), 整體API設計就是這樣. 這幾天還有什麼別的, 就是思考了下原來levi-db的不足, 比如是表級鎖, 這個已經早就被淘汰了.

接下來, 我就要弄MySQL on levi-db.

各位有什麼書籍或者論文推薦嗎? 謝謝幫助! 謝謝!