簡(jiǎn)介
Log Structured Merge Tree社痛，下面簡(jiǎn)稱 LSM仔雷。
2006年，Google 發(fā)表了 BigTable 的論文渐白。這篇論文提到 BigTable 單機(jī)上所使用的數(shù)據(jù)結(jié)構(gòu)就是 LSM。
目前逞频，LSM 被很多存儲(chǔ)產(chǎn)品作為存儲(chǔ)結(jié)構(gòu)纯衍，比如 Apache HBase, Apache Cassandra, MongoDB 的 Wired Tiger 存儲(chǔ)引擎, LevelDB 存儲(chǔ)引擎, RocksDB 存儲(chǔ)引擎等。
簡(jiǎn)單地說(shuō)苗胀，LSM 的設(shè)計(jì)目標(biāo)是提供比傳統(tǒng)的 B+ 樹更好的寫性能襟诸。LSM 通過(guò)將磁盤的隨機(jī)寫轉(zhuǎn)化為順序?qū)憗?lái)提高寫性能 ，而付出的代價(jià)就是犧牲部分讀性能基协、寫放大（B+樹同樣有寫放大的問(wèn)題）歌亲。
LSM 相比 B+ 樹能提高寫性能的本質(zhì)原因是：外存——無(wú)論磁盤還是 SSD，其隨機(jī)讀寫都要慢于順序讀寫堡掏。
優(yōu)化寫性能
如果我們對(duì)寫性能特別敏感应结，我們最好怎么做？—— Append Only：所有寫操作都是將數(shù)據(jù)添加到文件末尾泉唁。這樣做的寫性能是最好的鹅龄，大約等于磁盤的理論速度（200 ~ 300 MB/s）。但是 Append Only 的方式帶來(lái)的問(wèn)題是：
- 讀操作不方便亭畜。
- 很難支持范圍操作扮休。
- 需要垃圾回收（合并過(guò)期數(shù)據(jù)）。
所以拴鸵，純粹的 Append Only 方式只能適用于一些簡(jiǎn)單的場(chǎng)景：
優(yōu)化讀性能
如果我們對(duì)讀性能特別敏感八堡，一般我們有兩種方式：
- 有序存儲(chǔ)樟凄，比如 B+ 樹，SkipList 等兄渺。
- Hash 存儲(chǔ) —— 不支持范圍操作缝龄，適用范圍有限。
讀寫性能的權(quán)衡
如何獲得（接近） Append Only 的寫性能挂谍，而又能擁有不錯(cuò)的讀性能呢叔壤？
以 LevelDB 為代表的 LSM 存儲(chǔ)引擎給出了一個(gè)參考答案。注意口叙，LevelDB 實(shí)現(xiàn)的是優(yōu)化后的 LSM炼绘，原始的 LSM 可以參考論文。下面的討論主要以 LevelDB 為例子妄田。
LevelDB 的寫操作主要由兩步組成：
- 寫日志并持久化（Append Only）俺亮。
- Apply 到內(nèi)存中的 memtable（SkipList）。
所以形庭，LevelDB 的寫速度非城Υ牵快。
memtable 寫“滿”后萨醒，會(huì)轉(zhuǎn)換為 immutable memtable斟珊，然后被后臺(tái)線程 compaction 成按 Key 有序存儲(chǔ)的 sst 文件（順序?qū)懀Ｓ捎?sst 文件會(huì)有多個(gè)富纸，所以 LevelDB 的讀操作可能會(huì)有多次磁盤 IO（LevelDB 通過(guò) table cache囤踩、block cache 和 bloom filter 等優(yōu)化措施來(lái)減少讀操作的磁盤 IO 次數(shù)）。
總結(jié)
基于 LSM 數(shù)據(jù)結(jié)構(gòu)的 LevelDB 的適用場(chǎng)景：
- 寫請(qǐng)求多晓褪。
- 寫性能（吞吐+延遲）要求高堵漱。
