一、OceanBase的memtable設(shè)計成key為主鍵，value為行操作鏈表的目的

這是MVCC多版本并發(fā)控制的一種實現(xiàn)方式，寫不阻塞讀，并且讀可以讀到一個快照版本。實現(xiàn)MVCC可以有多種方法，下面我解釋一下幾種可能的實現(xiàn)方法，并分析一下各方法的優(yōu)劣

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

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

1. 完整數(shù)據(jù)直接存Row里，新版本在前

讀的時候，有一個snapshot version，比如是7，就需要找到名列前茅個小于7的版本，v=6的那個數(shù)據(jù)

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

缺點：更新數(shù)據(jù)的時候，需要申請一塊新的內(nèi)存空間存儲數(shù)據(jù)，由于它需要被放鏈表首位置，索引就需要指向它，因此需要更新一下索引的指針，使其指向新的數(shù)據(jù)。

2. 完整數(shù)據(jù)直接存Row里，老版本在前

優(yōu)點：更新的時候，直接插到鏈表的最后就好了，不需要再更新索引的指針

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

3. 更新數(shù)據(jù)存在Node里，然后通過Row指向Node，定期做壓縮

優(yōu)點：更新的時候，直接插入Row的指針指向的名列前茅個位置就好了，而且不需要像第1種方法那樣更新索引。另一個優(yōu)點是，由于只存儲增量數(shù)據(jù)，能節(jié)省很多內(nèi)存，尤其是當(dāng)一個表的列數(shù)非常多的時候

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

4. 數(shù)據(jù)存到一塊連續(xù)的內(nèi)存中

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

所以可以申請一塊大內(nèi)存，類似一個存struct的數(shù)組，然后把每一行存到這個數(shù)組里，定長數(shù)據(jù)直接存，變長數(shù)據(jù)用指針，對于小字符串，可以做一個優(yōu)化，將字符串分成2部分，前面小的一部分可以直接存數(shù)據(jù)里，然后通過指針指向另一部分

至于多版本和增量數(shù)據(jù)，可以按照前面幾種方法做選擇

做點查詢的時候，通過索引查，做scan的時候，看查詢的數(shù)據(jù)情況，當(dāng)數(shù)據(jù)量大時，直接scan數(shù)組是更快的，數(shù)據(jù)量小時，仍然通過索引做范圍查找

優(yōu)點：一些情況下，scan的性能更高

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

延伸閱讀：

二、網(wǎng)絡(luò)附加存儲(NAS)

NAS指Network Area Storage，即網(wǎng)絡(luò)附加存儲。它一般是將本地的存儲空間共享給其他主機使用，一般通過C/S架構(gòu)實現(xiàn)通信。它實現(xiàn)的是文件級別的共享，計算機通常將共享的設(shè)別識別為一個文件系統(tǒng)，其文件服務(wù)器會管理鎖以實現(xiàn)并發(fā)訪問。網(wǎng)絡(luò)文件系統(tǒng)，以文件模塊的形式進行共享，工作在應(yīng)用層上，常見的NAS有NFS和CIFS(FTP)。