LSM Tree楔敌，即日志結(jié)構(gòu)合并樹(Log-StructuredMerge-Tree)。LSM tree 之所以有效是基于以下事實(shí)：磁盤或內(nèi)存的連續(xù)讀寫性能遠(yuǎn)高于隨機(jī)讀寫性能，有時候這種差距可以達(dá)到三個數(shù)量級之高呀页。這種現(xiàn)象不僅對傳統(tǒng)的機(jī)械硬盤成立蝇率，對 SSD 硬盤也同樣成立。如下圖：
LSM tree 是許多 key-value 型或日志型數(shù)據(jù)庫所依賴的核心數(shù)據(jù)結(jié)構(gòu)棺禾，例如 BigTable缀蹄、HBase、Cassandra膘婶、LevelDB缺前、SQLite、Scylla悬襟、RocksDB 等衅码。
LSM tree 在工作過程中盡可能避免隨機(jī)讀寫，充分發(fā)揮了磁盤連續(xù)讀寫的性能優(yōu)勢脊岳。
1逝段、LSM樹的核心思想
如上圖所示垛玻，LSM樹有以下三個重要組成部分：
1) MemTable
MemTable是在內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)，用于保存最近更新的數(shù)據(jù)奶躯，會按照Key有序地組織這些數(shù)據(jù)帚桩，LSM樹對于具體如何組織有序地組織數(shù)據(jù)并沒有明確的數(shù)據(jù)結(jié)構(gòu)定義，例如Hbase使跳躍表來保證內(nèi)存中key的有序巫糙。
因?yàn)閿?shù)據(jù)暫時保存在內(nèi)存中朗儒，內(nèi)存并不是可靠存儲，如果斷電會丟失數(shù)據(jù)参淹，因此通常會通過WAL(Write-ahead logging醉锄，預(yù)寫式日志)的方式來保證數(shù)據(jù)的可靠性。
2) Immutable MemTable
當(dāng) MemTable達(dá)到一定大小后浙值，會轉(zhuǎn)化成Immutable MemTable恳不。Immutable MemTable是將轉(zhuǎn)MemTable變?yōu)镾STable的一種中間狀態(tài)。寫操作由新的MemTable處理开呐，在轉(zhuǎn)存過程中不阻塞數(shù)據(jù)更新操作烟勋。
3) SSTable(Sorted String Table)
有序鍵值對集合，是LSM樹組在磁盤中的數(shù)據(jù)結(jié)構(gòu)筐付。為了加快SSTable的讀取卵惦，可以通過建立key的索引以及布隆過濾器來加快key的查找。
2瓦戚、寫入數(shù)據(jù)
LSM tree 的所有寫操作均為連續(xù)寫沮尿，因此效率非常高。但由于外部數(shù)據(jù)是無序到來的较解，如果無腦連續(xù)寫入到 segment畜疾，顯然是不能保證順序的。對此印衔，LSM tree 會在內(nèi)存中構(gòu)造一個有序數(shù)據(jù)結(jié)構(gòu)（就是 memtable）啡捶。每條新到達(dá)的數(shù)據(jù)都插入到該紅黑樹中，從而始終保持?jǐn)?shù)據(jù)有序奸焙。當(dāng)寫入的數(shù)據(jù)量達(dá)到一定閾值時瞎暑，將觸發(fā)紅黑樹的 flush 操作，把所有排好序的數(shù)據(jù)一次性寫入到硬盤中（該過程為連續(xù)寫）与帆，生成一個新的 segment了赌。而之后紅黑樹便從零開始下一輪積攢數(shù)據(jù)的過程。
3鲤桥、刪除數(shù)據(jù)
如果是在內(nèi)存中，刪除某塊數(shù)據(jù)通常是將它的引用指向 NULL渠概，那么這塊內(nèi)存就會被回收茶凳。但現(xiàn)在的情況是嫂拴，數(shù)據(jù)已經(jīng)存儲在硬盤中，要從一個 segment 文件中間抹除一段數(shù)據(jù)必須要覆寫其之后的所有內(nèi)容贮喧，這個成本非常高筒狠。LSM tree 所采用的做法是設(shè)計一個特殊的標(biāo)志位，稱為 tombstone（墓碑）箱沦，刪除一條數(shù)據(jù)就是把它的 value 置為墓碑辩恼，如下圖所示：
這個例子展示了刪除 segment 2 中的 dog 之后的效果。注意谓形，此時 segment 1 中仍然保留著 dog 的舊數(shù)據(jù)灶伊，如果我們查詢 dog，那么應(yīng)該返回空寒跳，而不是 52聘萨。因此，刪除操作的本質(zhì)是覆蓋寫童太，而不是清除一條數(shù)據(jù)米辐，這一點(diǎn)初看起來不太符合常識。墓碑會在 compact 操作中被清理掉书释，于是置為墓碑的數(shù)據(jù)在新的 segment 中將不復(fù)存在翘贮。
4、讀取/查詢數(shù)據(jù)
如何從 SSTable 中查詢一條特定的數(shù)據(jù)呢爆惧？一個最簡單直接的辦法是掃描所有的 segment狸页，直到找到所查詢的 key 為止。通常應(yīng)該從最新的 segment 掃描检激，依次到最老的 segment肴捉，這是因?yàn)樵绞亲罱臄?shù)據(jù)越可能被用戶查詢，把最近的數(shù)據(jù)優(yōu)先掃描能夠提高平均查詢速度叔收。
當(dāng)掃描某個特定的 segment 時齿穗，由于該 segment 內(nèi)部的數(shù)據(jù)是有序的，因此可以使用二分查找的方式饺律，在
的時間內(nèi)得到查詢結(jié)果窃页。但對于二分查找來說，要么一次性把數(shù)據(jù)全部讀入內(nèi)存复濒，要么在每次二分時都消耗一次磁盤 IO脖卖，當(dāng) segment 非常大時（這種情況在大數(shù)據(jù)場景下司空見慣），這兩種情況的代價都非常高巧颈。一個簡單的優(yōu)化策略是畦木，在內(nèi)存中維護(hù)一個稀疏索引（sparse index），其結(jié)構(gòu)如下圖：
稀疏索引是指將有序數(shù)據(jù)切分成（固定大小的）塊砸泛，僅對各個塊開頭的一條數(shù)據(jù)做索引十籍。與之相對的是全量索引（dense index）蛆封，即對全部數(shù)據(jù)編制索引，其中的任意一條數(shù)據(jù)發(fā)生增刪均需要更新索引勾栗。兩者相比惨篱，全量索引的查詢效率更高，達(dá)到了理論極限值
围俘，但寫入和刪除效率更低砸讳，因?yàn)槊看螖?shù)據(jù)增刪時均需要因?yàn)楦滤饕囊淮?IO 操作。通常的關(guān)系型數(shù)據(jù)庫界牡，例如 MySQL 等簿寂，其內(nèi)部采用 B tree 作為索引結(jié)構(gòu)，這便是一種全量索引欢揖。
有了稀疏索引之后陶耍，可以先在索引表中使用二分查找快速定位某個 key 位于哪一小塊數(shù)據(jù)中，然后僅從磁盤中讀取這一塊數(shù)據(jù)即可獲得最終查詢結(jié)果她混，此時加載的數(shù)據(jù)量僅僅是整個 segment 的一小部分烈钞，因此 IO 代價較小授药。以上圖為例随静，假設(shè)我們要查詢 dollar 所對應(yīng)的 value莺褒。首先在稀疏索引表中進(jìn)行二分查找闰非，定位到 dollar 應(yīng)該位于 dog 和 downgrade 之間植袍，對應(yīng)的 offset 為 17208~19504僚楞。之后去磁盤中讀取該范圍內(nèi)的全部數(shù)據(jù)岸裙，然后再次進(jìn)行二分查找即可找到結(jié)果建芙，或確定結(jié)果不存在来累。
稀疏索引極大地提高了查詢性能砚作，然而有一種極端情況卻會造成查詢性能驟降：當(dāng)要查詢的結(jié)果在 SSTable 中不存在時，我們將不得不依次掃描完所有的 segment嘹锁，這是最差的一種情況葫录。有一種稱為布隆過濾器（bloom filter）的數(shù)據(jù)結(jié)構(gòu)天然適合解決該問題。布隆過濾器是一種空間效率極高的算法领猾，能夠快速地檢測一條數(shù)據(jù)是否在數(shù)據(jù)集中存在米同。我們只需要在寫入每條數(shù)據(jù)之前先在布隆過濾器中登記一下，在查詢時即可斷定某條數(shù)據(jù)是否缺失摔竿。
布隆過濾器的內(nèi)部依賴于哈希算法面粮，當(dāng)檢測某一條數(shù)據(jù)是否見過時，有一定概率出現(xiàn)假陽性（False Positive）继低，但一定不會出現(xiàn)假陰性（False Negative）熬苍。也就是說，當(dāng)布隆過濾器認(rèn)為一條數(shù)據(jù)出現(xiàn)過袁翁，那么該條數(shù)據(jù)很可能出現(xiàn)過柴底；但如果布隆過濾器認(rèn)為一條數(shù)據(jù)沒出現(xiàn)過钱磅，那么該條數(shù)據(jù)一定沒出現(xiàn)過。這種特性剛好與此處的需求相契合似枕，即檢驗(yàn)?zāi)硹l數(shù)據(jù)是否缺失。
這里需要關(guān)注一個重點(diǎn)年柠，LSM樹(Log-Structured-Merge-Tree)正如它的名字一樣凿歼，LSM樹會將所有的數(shù)據(jù)插入、修改冗恨、刪除等操作記錄(注意是操作記錄)保存在內(nèi)存之中答憔，當(dāng)此類操作達(dá)到一定的數(shù)據(jù)量后，再批量地順序?qū)懭氲酱疟P當(dāng)中掀抹。這與B+樹不同虐拓，B+樹數(shù)據(jù)的更新會直接在原數(shù)據(jù)所在處修改對應(yīng)的值，但是LSM數(shù)的數(shù)據(jù)更新是日志式的傲武，當(dāng)一條數(shù)據(jù)更新是直接append一條更新記錄完成的蓉驹。這樣設(shè)計的目的就是為了順序?qū)懀粩嗟貙mmutable MemTable flush到持久化存儲即可揪利，而不用去修改之前的SSTable中的key态兴，保證了順序?qū)憽?/p>
因此當(dāng)MemTable達(dá)到一定大小flush到持久化存儲變成SSTable后，在不同的SSTable中疟位，可能存在相同Key的記錄瞻润，當(dāng)然最新的那條記錄才是準(zhǔn)確的。這樣設(shè)計的雖然大大提高了寫性能甜刻，但同時也會帶來一些問題：
1）冗余存儲绍撞，對于某個key，實(shí)際上除了最新的那條記錄外得院，其他的記錄都是冗余無用的傻铣，但是仍然占用了存儲空間。因此需要進(jìn)行Compact操作(合并多個SSTable)來清除冗余的記錄尿招。
2）讀取時需要從最新的倒著查詢矾柜，直到找到某個key的記錄。最壞情況需要查詢完所有的SSTable就谜，這里可以通過前面提到的索引/布隆過濾器來優(yōu)化查找速度怪蔑。
5、文件合并（Compaction）
隨著數(shù)據(jù)的不斷積累丧荐，SSTable 將會產(chǎn)生越來越多的 segment缆瓣，導(dǎo)致查詢時掃描文件的 IO 次數(shù)增多，效率降低虹统，因此需要有一種機(jī)制來控制 segment 的數(shù)量弓坞。對此隧甚，LSM tree 會定期執(zhí)行文件合并（compaction）操作，將多個 segment 合并成一個較大的 segment渡冻，隨后將舊的 segment 清理掉戚扳。由于每個 segment 內(nèi)部的數(shù)據(jù)都是有序的，合并過程類似于歸并排序族吻，效率很高帽借，只需要
的時間復(fù)雜度。
在上圖的示例中超歌，segment 1 和 2 中都存在 key 為 dog 的數(shù)據(jù)砍艾，這時應(yīng)該以最新的 segment 為準(zhǔn)，因此合并后的值取 84 而不是 52巍举，這實(shí)現(xiàn)了類似于字典/HashMap 中“覆蓋寫”的語義脆荷。
go-leveldb
go-leveldb是一個對leveldb的golang實(shí)現(xiàn)。
db, err := leveldb.OpenFile("path/to/db", nil)
// get
data, err := db.Get([]byte("key"), nil)
// 新增/修改
err = db.Put([]byte("key"), []byte("value"), nil)
// 刪除
err = db.Delete([]byte("key"), nil)
// 批量操作
batch := new(leveldb.Batch)
batch.Put([]byte("foo"), []byte("value"))
batch.Put([]byte("bar"), []byte("another value"))
batch.Delete([]byte("baz"))
err = db.Write(batch, nil)
// 使用布隆過濾器
o := &opt.Options{
Filter: filter.NewBloomFilter(10),
}
db, err := leveldb.OpenFile("path/to/db", o)
defer db.Close()
參考：https://zhuanlan.zhihu.com/p/181498475懊悯、 https://www.qtmuniao.com/2022/04/16/ddia-reading-chapter3-part1/
