OceanBase的memtable設計成key為主鍵，value為行操作鏈表的目的是什麼？

01-14

Oceanbase的內存B+樹中的每個元素對應MemTable中的一行操作，key為行主鍵，value為行操作鏈表的指針。每行的操作按照時間順序構成一個行操作鏈表，
請問這樣設計的目的是什麼？是為了lock-free嗎？有相關的論文介紹這種思想嗎？

謝邀

當時算是參考了一點bigtable存儲多版本數據的方式吧，但是其實論文中也沒很明確的講。在陽老師的帶領下，大家自己發揮了一下創造力。

與cockroach tidb直接把rocksdb當黑盒用的方式不同，oceanbase將mvcc的邏輯做到了memtable中，只在memtable中存儲多版本數據，compaction時丟棄多版本只存最後一個版本。

以前多版本是正序串聯的，後來支持sql以後的版本，因為不會再有+1這樣的值了(數據都是執行完表達式再存儲了)，所以每行多次的修改按照倒序串聯起來更方便，讀最近的版本效率更高。

相比cockroach tidb的每個版本存為一行的做法，ob的方式數據膨脹較小，範圍查詢效率高，且沒有回收舊版本數據的代價。代價是不支持長事務或大事務，memtable凍結時要殺掉正在運行中的事務(這裡會稍微等一下下，不會直接殺)。我離開ob團隊的時候還存在這個局限，不知道後來有沒有解掉。

當然上述問題是有解的，只不過在互聯網場景下，大部分都是短小事務，影響並不大。正好最近在菊廠也在思考這個問題。如果限制一下事務大小，在提交時一次性寫日誌，在凍結時把活躍事務遷移的未提交數據和鎖到新memtable，即可避免凍結時殺掉事務；在此基礎上，如果compaction時允許將未提交事務的數據和鎖持久化到sstable(這個做法需要配合額外的事務狀態表)，那麼還可以支持長事務了。

這是MVCC多版本並發控制的一種實現方式，寫不阻塞讀，並且讀可以讀到一個快照版本。實現MVCC可以有多種方法，下面我解釋一下幾種可能的實現方法，並分析一下各方法的優劣

B+tree是索引，可以通過一行的key，索引到其value，索引還可以是其它的，比如Rocksdb和MemSQL用的是skiplist，還可以是Hashtable，還有一些新的數據結構微軟Hekaton用的bw-tree，HyPer用的adaptive radix tree等。B+tree是非常合適的，對範圍查詢和點查詢都不錯，對於CPU Cache非常友好，可以做到很高的性能，至於用skiplist的資料庫，看了一他們選擇這個的理由，文檔里基本都是說因為實現起來比較簡單，B+tree實現起來太複雜了。不過OceanBase的前輩們把內存B+tree實現的非常好，可以看到實力非常強，不需要因為某些東西簡單而去選擇用那個東西。

下面說一下幾種實現方法，主要說的是MVCC，就不說B+tree了

1. 完整數據直接存Row里，新版本在前

讀的時候，有一個snapshot version，比如是7，就需要找到第一個小於7的版本，v=6的那個數據

優點：如果更新不頻繁，大部分查詢所需的數據版本都是最新的，通過索引找到某一行，直接通過指針就可以找到所需數據。通過指針就是一次內存的隨機訪問，100ns，當然還有其它處理數據的開銷

缺點：更新數據的時候，需要申請一塊新的內存空間存儲數據，由於它需要被放鏈表首位置，索引就需要指向它，因此需要更新一下索引的指針，使其指向新的數據

2. 完整數據直接存Row里，老版本在前

優點：更新的時候，直接插到鏈表的最後就好了，不需要再更新索引的指針

缺點：查詢的時候，可能需要順著鏈表找很多結點才能找到所需版本的數據，而每一次都是一次內存隨機訪問，需要(n*100)ns

3. 更新數據存在Node里，然後通過Row指向Node，定期做壓縮

優點：更新的時候，直接插入Row的指針指向的第一個位置就好了，而且不需要像第1種方法那樣更新索引。另一個優點是，由於只存儲增量數據，能節省很多內存，尤其是當一個表的列數非常多的時候

缺點：查詢的時候，就算是需要查詢最新的版本，也可能需要遍歷多個node才能得到完整的數據。不過當更新過多時，可以通過壓縮，將多個更新合併成完整數據，存到一個新的node中，一定程度上緩解這個問題

4. 數據存到一塊連續的內存中

前面幾種方法都是，當插入一行新的數據時，申請一塊內存，存數據，或者存更新node，這會導致做scan的時候比較慢。因為做scan的時候，需要通過索引中的指針才能找到數據，做scan是先對索引進行scan，再找到相應的數據，而每一次內存隨機訪問是100ns，也就是每秒掃描的數據量不可能超過1s/100ns=1000萬

所以可以申請一塊大內存，類似一個存struct的數組，然後把每一行存到這個數組裡，定長數據直接存，變長數據用指針，對於小字元串，可以做一個優化，將字元串分成2部分，前面小的一部分可以直接存數據里，然後通過指針指向另一部分

至於多版本和增量數據，可以按照前面幾種方法做選擇

做點查詢的時候，通過索引查，做scan的時候，看查詢的數據情況，當數據量大時，直接scan數組是更快的，數據量小時，仍然通過索引做範圍查找

優點：一些情況下，scan的性能更高

缺點：由於是原地更改row里的數據，讀寫的時候都需要加鎖（latch），更新多的時候，對讀不友好

這些方法都很好，每一個都有適合自己的場景，需要根據資料庫的定位做選擇

當然，MVCC裡面還有很多其它東西需要管理，如具體的並發控制演算法，垃圾回收等，可以參考下面的論文

參考文獻

[1]An Empirical Evaluation of In-Memory Multi-Version Concurrency Control

http://www.comp.nus.edu.sg/~yingjun/papers/vldb2017.pdf

[2]Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems

https://db.in.tum.de/~muehlbau/papers/mvcc.pdf

[3]High-Performance Concurrency Control Mechanisms for Main-Memory Databases

http://vldb.org/pvldb/vol5/p298_per-akelarson_vldb2012.pdf

比較自然的做法，我們的實現也大同小異。memtable自身要支持讀寫不互相block（否則性能極差，特別是高頻寫、range讀），每行key -&> {value-version2, value-version1 ...}實現了一個簡單的MVCC。行內容有兩種排放，一種是放增量，在讀的時候由多個版本的value拼湊出該行；另外一種是每次寫的時候拼接好，行的完整內容放在最新版本的value裡面，後一種做法新版本會引用舊版本，速度快也不費內存。個人認為第二種做法較好，同一個value反覆更改的場景並不多。