[资料]了解LSM Tree
在学习 VictoriaMetrics时，作者的文章提到其存储类似于ClickHost的MergeTree，而MergeTree又和LSM-Tree(Log Structured Merge Tree)相似，于是借此机会了解了下LSM Tree是什么东西和使用场景，初步整理如下。
LSM Tree 是一种多层的数据结构，利用了磁盘顺序写要远快于随机写的特性，适用于数据插入和更新吞吐量大的场景。目前已经应用在Google BigTable, LevelDB, RocksDB，Cassandra，HBase等多个数据库中。
这里面有几个关键概念： （1）MemTable 新数据写入时会先写到内存中的MemTable中，并且是有序的（使用如红黑树、跳表等的数据结构）。 当MemTable达到一定大小时，会持久化到磁盘中转化为SSTables。
（2）Sorted String Tables （SSTables） 是按key排序的key-value字符串对。 为什么要排序？ LSM Tree中数据是顺序写的，即append-only。如果不对数据做排序，查询操作要做线性扫描，是O(n)的复杂度，这肯定是不能接受的。 但如果是排好序的数据，查询的复杂度就是O(logn)了。
磁盘中会有多个SStables，读数据时要分别从这多个SSTable中读取。
（3）Compaction 随着数据不断写入，磁盘中的SSTables会越来越多，其中还包含部分冗余的更新和删除（tombstone）数据。出于查询速率和磁盘利用率的考虑，需要对SSTables进行compation操作。 compaction是在后台执行的，将多余的数据移除掉，创建压缩后的SSTables。
随着SSTables的数量增加，读的耗时也会随之成正比的增加。为了解决这一问题，可以引入布隆过滤器来快速（O(1)的复杂度）地判断某个key是否在某个SSTable中；引入稀疏索引来帮助快速查找key的位置。
参考：
Comments