一、大幅度制約儲存介質吞吐量的原因

首先丟擲結論。無論任何儲存介質（不管是機械硬碟還是SSD，抑或是記憶體）的順序訪問速度都遠遠高出隨機訪問的速度。

二、傳統資料庫的實現機制

傳統資料庫，比如Mysql使用的b+樹索引，對讀友好。但容易造成隨機寫。比如新插入一個值到資料庫，首先我們要讀取b+樹，判斷新插入的值放在樹的什麼位置，其次在特定的位置寫入新值，並做一系列調整，分裂，使之滿足b+樹的特性。這不可避免的造成了磁碟的隨機訪問，大資料量的插入速度很慢。當然這也符合歷史發展趨勢，早起的IT行業，資料量和資料增長速度有限，只要擁有良好的查詢效能，即可滿足需求。

但隨著硬體效能的提升，業務形態的變化，現今的網際網路系統，往往面臨著資料的大量、高速產生。如何加快儲存速度，成了關鍵。於是LSM Tree應運而生。

三、LSM Tree的歷史由來

LSM Tree的最早概念，誕生於1996年google的“BigTable”論文。後世多種資料庫產品對LSM Tree的具體實現，都有一些小的差異。採用LSM Tree作為儲存結構的資料庫有，Google的LevelDB, Facebook的RockDB(RockDB來源於LevelDB), Cassandra,HBase等。

四、提高寫吞吐量的思路

既然順序寫比起隨機寫速度更快。那得想辦法將資料順序寫。

4.1 一種方式是資料來後，直接順序落盤

這擁有很高的寫速度。但是當我們想要查尋一個數據的時候，由於儲存下的資料本身是無序的（寫的值本身無法控制順序），無法使用任何演算法進行最佳化，只能挨個查詢，讀取速度是很慢的。

4.2 另一種方式，是保證落盤的資料是順序寫入的同時，還保證這些資料是有序的

而請求寫入的資料本身是無序且不可預測的，如何保證落盤的資料是有序的呢？這就需要利用記憶體訪問速度比硬碟快的原理。將寫入的請求，先在記憶體中快取起來，按一定的有序結構組織，達到一定量後，再寫入硬碟，從而使得硬碟順序寫入了有序的資料。提高資料的寫入速度同時，方便了後續基於有序資料的查詢(有序的資料結構，可以透過二分查詢等演算法進行進行快速查詢，具體查詢演算法，得看是哪種有序結構)

五、 LSM Tree結構圖

LSM tree即利用了上述第二種方式。具體結構圖如下：

5.1 寫入時，為什麼要先寫一份log

為了防止寫入的資料，在斷電時丟失。所以先順序寫一份log到硬碟，方便資料恢復。

5.2 什麼是MemTable

寫入資料的記憶體快取，MemTable中儲存的是有序的資料。什麼才是有序的資料結構？不同的實現可能不相同。LevelDB使用的是SkipList。Hbase使用的是B Tree。

5.3 什麼是ImmutableMemTable

MemTable中的資料隨時在增加，當其增加到一定量後，將其變為不可變資料，ImmutableMemTable。新生成一份MemTable用於後續的資料寫入。ImmutableMemTable中的資料，將被寫入到硬碟中的SSTable.

5.4 什麼是SSTable

SSTable 全稱Sorted String Table。實際上就是被寫入資料的有序儲存檔案，所以叫sorted.

SSTable檔案有DataBlock,IndexBlock,BitSet(不同的實現，有可能沒有)

DataBlock 一個SSTable包含多個數據塊，資料按KeyValue的形式有序組織。IndexBlock 記錄每個資料塊中最大的那個Key的OffsetBitSet 使用Bloom Filter來將一個Key對映到BitSet中

資料的有序組織、IndexBlock、BitSet。這些資料結構，都是為了提高資料讀取時的速度。那資料是如何進行讀取的呢？

5.5 如何進行資料讀取

讀取的大概流程如下

由於SSTable是順序建立，所以最新的SSTable中包含了最新的值。再查詢SSTable時，依次查詢最新的SSTable。

每一個SSTable的查詢流程如下

布隆表示式的原理是以極小的資料容量，去儲存大量資料存在的可能性。所以如果透過BitSet的布隆表示式查詢該Key存在時，只是一個理論存在可能，接下來要透過IndexBlock真正進行查詢。而如果布隆表示式在BitSet中沒有找到，那就是真的沒有，可以快速跳過，進入下一個SSTable查詢。布隆表示式的運用，能夠大大提高查詢效率。

5.6 如何進行資料的刪除和更新

為了保證資料的順序寫，所有SSTable都不會因為刪除和更新而在原資料所在位置進行更改。在更新時，僅僅插入一個最新的值去寫到新的SSTable中。在刪除時，依然是插入一個基於該Key的刪除標記，寫入最新的SSTable中。由於查詢某個Key是基於時間新鮮度，反向依次查詢SSTable，所以讀取某個Key始終讀的是最新的值。

5.7 SSTable的合併

隨著日積月累，SSTable的檔案數會增多，導致查詢時效能下降。同時由於資料的更新或刪除。讓老的SSTable中資料的有效性降低，太多的過期資料佔用SSTable，同樣會降低查詢效率。所以一般資料庫引擎，定期都會有一個SSTable的合併操作。移除過時資料，將多個小SSTable合併成大的SSTable。

5.8 最近讀取的SSTable IndexBlock快取

在大記憶體的條件下，部分資料庫還會將最近讀取的SSTable　索引，快取至記憶體。這進一步加速了查詢的過程。

六、參考文獻

www.benstopford.com/2015/02/14/… www.cnblogs.com/haippy/arch… blog.csdn.net/u014774781/… en.wikipedia.org/wiki/Log-st… www.igvita.com/2012/02/06/…