982
“寫優化”的數據結構(3)：small-splittable-tree
作者：一工
如果你感到buffered b-tree 或者 x–y tree還是有點複雜，這裏還有簡單的。
如果不走tree-like派係，那就走短、平、快的small-splittable-tree的路子，甚至可以玩small-splittable-list。
短就是每個tree單元要小。
平就是tree高度要低。
快就是分裂起來要快(compaction)。
這裏的tree可以是b-tree或其他的tree結構都沒問題，但在分裂起來，一定要快，不能hang住寫線程。
如果你嫌tree結構有高度，還是複雜，那可以來簡單的small-splittable-list，也就是所有數據插入完畢，最終是個順序的list，這個list由多個segment構成，任何兩個segment之間不會有區間重疊。
write
——–
每個segment反映到磁盤就是一個文件，比如1.SSL。
這個SSL文件由2部分組成：header和blocks。
header記錄區間信息，比如: <pivot1, blockid1> … <pivotn, blockidn>，用於數據歸屬block查找。
block裏存放的是key-value數據(追加寫），每個block大小是固定的（比如256KB)，當block滿了，就分裂成2個block，當一個SSL裏的block都滿了（個數等於 SSL-size/block-size)，則對這個SSL進行分裂，這個分裂過程也是很快的，沒有數據merge過程。
read
——
首先根據key定位到你屬於哪個SSL，然後根據header定位到你屬於哪個block，這樣就搞定了。
small-splittable-list基本就是在往AOF靠攏，但是讀起來是很快的。
這種數據結構的缺點就是page cache利用率不高，共享部分太少了，如果是tree，從root到某些inner-node的路徑是可共享的，隻好做記錄級緩存了，kernel幫不了你。
小結
做“寫優化”的數據結構讀不一定慢的。
比如在寫的過程中，你已經走了root-node1-node2…-nodex這條path，可認為它已在page cache裏，當你讀的時候，root無需從磁盤讀取，node1也無需從磁盤，這樣“讀”就揩“寫”的油。反過來，“寫”也可以揩”讀“的油，所以即使在讀寫混合的時候，仍可互利。
如果node大小為4MB（leaf節點可設置的更大些），一個高度為6的tree就是TB級了，這樣leaf節點是很少被touch到的，所以在page cache裏的基本都是inner node，很爽了 
如果你“嫌棄”page cache的機製，可以嚐試自己的cache + Direct IO (cascadb用的AIO）這條路。
期待更多的引擎來嚐試下buffered tree!
BTW:大塊寫在SSD上的好處就是Write amplification（https://en.wikipedia.org/wiki/Write_amplification）的降低。
最後更新：2017-04-03 07:57:05