LSM實作熱資料讀寫和range查詢加速

LSM-tree 上的讀路徑，從出生就帶着鐐铐。因為 CoW 的使用，讀一條記錄實際上需要把這條記錄所有的增量碎片都找到。因為橫跨記憶體和磁盤兩種媒體和有階層化的存儲，這些碎片可能藏在各種犄角旮旯裡面。更慘的是，如果是讀一個範圍内的記錄，俗稱 range scan，因為 LSM-tree 的每一層的 key range 是交疊的，那麼一個 range 内的資料就很有可能會落在所有的層次上，為了把他們都找到，我們就需要每層都去讀，這個工作量也不小。

為了解決這個問題，目前的 LSM-tree 引擎把各種經典技術都用上了：各種索引、各種 cache。但是為了提高索引和 cache 的效率，讓他們一直發揮比較好的作用，難度不小。以

富貴論壇

cache 為例，X-Engine 中使用了兩種經典的 cache，一種是 row cache，緩存記錄級别的熱資料，一種是 block cache，緩存資料塊級别的熱資料。Row cache 可以加速點查詢，block cache 可以加速 range scan，一切看上去都是很完美的芭蕾舞。然而，當 compaction 被大王叫來巡山的時候，危險就發生了。因為 compaction 會重新組織資料塊裡面的内容，幹掉一些老的 block，生成一些新的 block，傳統的 cache 替換政策對老的 block 做的通路統計會失效，而新的 block 它不認識，沒統計資訊。此外，compaction 還會移動資料。這兩點加起來，隻要 compaction 巡了一次山，cache 裡面緩存的記錄就有很大可能出現大面積失效，導緻原本可以命中 cache 的查詢，不得不去通路磁盤，造成嚴重的延遲尖刺。