LSM Tree/MemTable/SSTable基本原理
時光飛逝，截至今天具滴，2018的進(jìn)度條已經(jīng)毫不留情的燃燒掉了8.5%。
2017接觸了很多新事物，也實(shí)踐和落地了一些有意思的技術(shù)毙籽、產(chǎn)品和框架。要想走得快毡庆，一個人走坑赡，要想走得遠(yuǎn)，得學(xué)會多回頭看么抗，多總結(jié)毅否。這也是接下來一系列文章的初衷。當(dāng)然蝇刀，前提是自己能夠堅持寫下去螟加，??
是為記。
背景
2017年吞琐，做調(diào)用鏈服務(wù)的時候捆探，為了存儲整個系統(tǒng)的調(diào)用事件數(shù)據(jù)，遇到了一個存儲上的問題：數(shù)據(jù)每天的寫入量大概在10億級別站粟，也就是1.1w rps(record per second), 加上高峰期流量波動和系統(tǒng)冗余黍图，我們把及格線定為3w rps。這是一個典型的寫多讀少的場景奴烙，自然直接放棄了關(guān)系型數(shù)據(jù)庫助被；同時考慮到寫入的時序特性剖张，選型基本鎖定到基于LSM Tree為存儲引擎的數(shù)據(jù)庫上。挑戰(zhàn)依然在恰起，但是基于LSM Tree的數(shù)據(jù)庫一大把（HBase, Cassandra, RockDB, LevelDB, SQLite...）修械，解決問題無非是時間問題。
我們先嘗試了ssdb检盼，號稱可以替代redis, 一些指標(biāo)上快過redis. 結(jié)果被坑得體無完膚：
- key不支持過期（2017.04）肯污；
- 寫入性能壓測只有2w qps，如果數(shù)據(jù)記錄增大吨枉，性能迅速下降蹦渣；
- 翻了下代碼實(shí)現(xiàn)，雖然很失望貌亭，但是感覺因此避開了一個定時炸彈而慶幸??
在同事推薦下柬唯，我們嘗試了Cassandra. 雖然國內(nèi)用得不多，但是在《微服務(wù)架構(gòu)》中圃庭，看到了奈飛（Netflix）的大規(guī)模使用案例锄奢，信心還是有的。實(shí)際壓測結(jié)果：單節(jié)點(diǎn)寫入性能在8w qps剧腻，超出預(yù)期拘央。此外，系統(tǒng)上線后书在，同事花了大量時間調(diào)優(yōu)參數(shù)灰伟，目前線上的單節(jié)點(diǎn)性能應(yīng)該遠(yuǎn)超8w qps.
基本概念
LSM Tree (Log-structured merge-tree) ：這個名稱挺容易讓人困惑的，因?yàn)槟憧慈魏我粋€介紹LSM Tree的文章很難直接將之與樹對應(yīng)起來儒旬。事實(shí)上栏账，它只是一種分層的組織數(shù)據(jù)的結(jié)構(gòu)，具體到實(shí)際實(shí)現(xiàn)上栈源，就是一些按照邏輯分層的有序文件挡爵。
MemTable: LSM Tree的樹節(jié)點(diǎn)可以分為兩種，保存在內(nèi)存中的稱之為MemTable, 保存在磁盤上的稱之為SSTable. 嚴(yán)格講甚垦，MemTable與SSTable還有很多細(xì)節(jié)區(qū)別茶鹃，這里不展開討論。
基本原理
- 寫操作直接作用于MemTable, 因此寫入性能接近寫內(nèi)存制轰。
- 每層SSTable文件到達(dá)一定條件后前计，進(jìn)行合并操作胞谭，然后放置到更高層垃杖。合并操作在實(shí)現(xiàn)上一般是策略驅(qū)動、可插件化的丈屹。比如Cassandra的合并策略可以選擇
SizeTieredCompactionStrategy或LeveledCompactionStrategy.
- Level 0可以認(rèn)為是MemTable的
文件映射內(nèi)存, 因此每個Level 0的SSTable之間的key range可能會有重疊调俘。其他Level的SSTable key range不存在重疊伶棒。 - Level 0的寫入是簡單的
創(chuàng)建-->順序?qū)?/code>流程，因此理論上彩库，寫磁盤的速度可以接近磁盤的理論速度肤无。
- SSTable合并類似于簡單的歸并排序：根據(jù)key值確定要merge的文件，然后進(jìn)行合并骇钦。因此宛渐，合并一個文件到更高層，可能會需要寫多個文件眯搭。存在一定程度的寫放大窥翩。是非常昂貴的I/O操作行為。Cassandra除了提供策略進(jìn)行合并文件的選擇鳞仙，還提供了合并時I/O的限制寇蚊，以期減少合并操作對上層業(yè)務(wù)的影響。
- 讀操作優(yōu)先判斷key是否在MemTable, 如果不在的話棍好，則把覆蓋該key range的所有SSTable都查找一遍仗岸。簡單，但是低效借笙。因此扒怖，在工程實(shí)現(xiàn)上，一般會為SSTable加入索引——布隆過濾器（Bloom Filter）提澎。它有一個特性：如果bloom說一個key不存在姚垃，就一定不存在，而當(dāng)bloom說一個key存在于這個文件盼忌，可能是不存在的积糯。實(shí)現(xiàn)層面上，布隆過濾器就是
key--比特位的映射谦纱。理想情況下看成，當(dāng)然是一個key對應(yīng)一個比特實(shí)現(xiàn)全映射，但是太消耗內(nèi)存跨嘉。因此川慌，一般通過控制假陽性概率來節(jié)約內(nèi)存，代價是犧牲了一定的讀性能祠乃。對于我們的應(yīng)用場景梦重，我們將該概率從0.99降低到0.8，布隆過濾器的內(nèi)存消耗從2GB+下降到了300MB亮瓷，數(shù)據(jù)讀取速度有所降低琴拧，但在感知層面可忽略。
Q&A
-
基于LSM Tree存儲引擎的數(shù)據(jù)適用于哪些場景嘱支？
(key or key-range), 且key/key-range整體大致有序蚓胸。
-
LSM Tree自從Google BigTable問世后挣饥，如此牛x, 為什么沒有替代B Tree呀？
LSM Tree本質(zhì)上也是一種二分查找的思想沛膳，只是這種二分局限在key的大致有序這個假設(shè)上扔枫，并充分利用了磁盤順序?qū)懙男阅埽瞧者m性一般锹安。B Tree對于寫多讀少的場景短荐，大部分代價開銷在Tree的維護(hù)上，但是具有更強(qiáng)的普適性叹哭。
-
看起來搓侄，你們已經(jīng)將Cassandra玩得很溜了，你們線上用了多大集群支持當(dāng)前業(yè)務(wù)话速？
其實(shí)……還可以吧讶踪，主要是隊(duì)友給力。還有就是國外有獨(dú)角獸奈飛領(lǐng)頭泊交，遇到問題其實(shí)還是容易解決的乳讥。我們目前線上用了3*(4 core, 16G), 系統(tǒng)冗余還很大。最近奈飛出了一篇關(guān)于Cassandra優(yōu)化的深度博文廓俭，如果有對Cassandra有興趣云石，可以閱讀Scaling Time Series Data Storage.
擴(kuò)展閱讀
同步自我的博客 LSM Tree/MemTable/SSTable基本原理
