之前零零散散寫過幾篇和 LSM-Tree、LevelDB 有關(guān)的文章树枫。之后也看了一些代碼和論文直焙，筆記也做了一些，但大都比較零亂砂轻、隨意奔誓，沒花功夫整理。
這次打算將之前的文章和之后的筆記一起整理一下搔涝，成為一個系列文章——本文是本系列文章的第一篇厨喂。
LSM-Tree
Log Structured Merge Tree，簡稱 LSM-Tree庄呈。2006年蜕煌，Google 發(fā)表了 BigTable 的論文。這篇論文提到 BigTable 單機(jī)上所使用的數(shù)據(jù)結(jié)構(gòu)就是 LSM-Tree抒痒。
很多存儲產(chǎn)品使用 LSM-Tree 作為數(shù)據(jù)結(jié)構(gòu)幌绍，比如 Apache HBase颁褂，Apache Cassandra故响，MongoDB 的 Wired Tiger 存儲引擎，LevelDB 存儲引擎颁独，RocksDB 存儲引擎等彩届。
簡單地說，LSM-Tree 的設(shè)計(jì)目標(biāo)是提供比傳統(tǒng)的 B-Tree/B+Tree 更好的寫性能誓酒。LSM-Tree 通過將磁盤的隨機(jī)寫轉(zhuǎn)化為順序?qū)憗硖岣邔懶阅?樟蠕，而付出的代價(jià)就是犧牲部分讀性能贮聂、寫放大（B-Tree/B+Tree 同樣有寫放大的問題）。
如何優(yōu)化寫性能
如果我們對寫性能特別敏感寨辩，我們最好怎么做吓懈？—— Append only：所有寫操作都是將數(shù)據(jù)添加到文件末尾。這樣順序?qū)懙男阅苁亲詈玫拿夷蠹s等于磁盤的理論速度（無論是 SSD 還是 HDD耻警，順序?qū)懶阅芏家黠@由于隨機(jī)寫性能）。但是 append only 的方式會帶來一些問題：
- 不支持有序遍歷甸怕。
- 需要垃圾回收（清理過期數(shù)據(jù)）甘穿。
所以，純粹的 append only 方式只能適用于一些簡單的場景：
如何優(yōu)化讀性能
如果我們對讀性能特別敏感武契，一般我們有兩種方式：
- 有序存儲募判，比如 B-Tree/B+Tree。但是 B-Tree/B+Tree 會導(dǎo)致隨機(jī)寫咒唆。
- 哈希存儲 —— 不支持有序遍歷兰伤，適用范圍有限。
讀寫性能的權(quán)衡
如何獲得接近 append only 的寫性能钧排，而又能擁有不錯的讀性能呢敦腔？以 LevelDB/RocksDB 為代表的 LSM-Tree 存儲引擎給出了一個參考答案。原始的 LSM-Tree 可以參考論文恨溜。下面的討論主要以 LevelDB 為例子符衔。
LevelDB 的寫操作（Put/Delete/Write）主要由兩步組成：
- 寫日志（WAL，順序?qū)懀?/li>
- 寫 MemTable（內(nèi)存中的 SkipList）糟袁。
所以判族，正常情況下，LevelDB 的寫速度非诚畲鳎快形帮。
內(nèi)存中的 MemTable 寫滿后，會轉(zhuǎn)換為 Immutable MemTable周叮，然后被后臺線程 compact 成按 key 有序存儲的 SSTable（順序?qū)懀?br>
SSTable 按照數(shù)據(jù)從新到舊被組織成多個層次（上層新下層舊）辩撑，點(diǎn)查詢（Get）的時(shí)候從上往下一層層查找，所以 LevelDB 的讀操作可能會有多次磁盤 IO（LevelDB 通過 table cache仿耽、block cache 和 bloom filter 等優(yōu)化措施來減少讀操作的 I/O 次數(shù)）合冀。
后臺線程的定期 compaction 負(fù)責(zé)回收過期數(shù)據(jù)和維護(hù)每一層數(shù)據(jù)的有序性。在數(shù)據(jù)局部有序的基礎(chǔ)上项贺，LevelDB 實(shí)現(xiàn)了數(shù)據(jù)的（全局）有序遍歷君躺。
LevelDB 接口使用
LevelDB 提供的接口很簡單峭判，請參考官網(wǎng)文檔。
LevelDB 整體架構(gòu)
上圖簡單展示了 LevelDB 的整體架構(gòu)棕叫。
- MemTable：內(nèi)存數(shù)據(jù)結(jié)構(gòu)林螃，具體實(shí)現(xiàn)是 SkipList。 接受用戶的讀寫請求俺泣，新的數(shù)據(jù)會先在這里寫入治宣。
- Immutable MemTable：當(dāng) MemTable 的大小達(dá)到設(shè)定的閾值后，會被轉(zhuǎn)換成 Immutable MemTable砌滞，只接受讀操作侮邀，不再接受寫操作，然后由后臺線程 flush 到磁盤上 —— 這個過程稱為 minor compaction贝润。
- Log：數(shù)據(jù)寫入 MemTable 之前會先寫日志绊茧，用于防止宕機(jī)導(dǎo)致 MemTable 的數(shù)據(jù)丟失。一個日志文件對應(yīng)到一個 MemTable打掘。
- SSTable：Sorted String Table华畏。分為 level-0 到 level-n 多層，每一層包含多個 SSTable尊蚁，文件內(nèi)數(shù)據(jù)有序亡笑。除了 level-0 之外，每一層內(nèi)部的 SSTable 的 key 范圍都不相交横朋。
- Manifest：Manifest 文件中記錄 SSTable 在不同 level 的信息仑乌，包括每一層由哪些 SSTable，每個 SSTable 的文件大小琴锭、最大 key晰甚、最小 key 等信息。
- Current：重啟時(shí)决帖，LevelDB 會重新生成 Manifest厕九，所以 Manifest 文件可能同時(shí)存在多個，Current 記錄的是當(dāng)前使用的 Manifest 文件名地回。
- TableCache：TableCache 用于緩存 SSTable 的文件描述符扁远、索引和 filter。
- BlockCache：SSTable 的數(shù)據(jù)是被組織成一個個 block刻像。BlockCache 用于緩存這些 block（解壓后）的數(shù)據(jù)畅买。
