LSM Tree (Log-structured merge-tree)_(log-structured-merge-tree)

基本概念

LSM Tree (Log-structured merge-tree) ：这个名称挺容易让人困惑的，因为你看任何一个介绍LSM Tree的文章很难直接将之与树对应起来。事实上，它只是一种分层的组织数据的结构，具体到实际实现上，就是一些按照逻辑分层的有序文件。

MemTable: LSM Tree的树节点可以分为两种，保存在内存中的称之为MemTable, 保存在磁盘上的称之为SSTable. 严格讲，MemTable与SSTable还有很多细节区别，这里不展开讨论。

基本原理

• 写操作直接作用于MemTable, 因此写入性能接近写内存。
• 每层SSTable文件到达一定条件后，进行合并操作，然后放置到更高层。合并操作在实现上一般是策略驱动、可插件化的。比如Cassandra的合并策略可以选择SizeTieredCompactionStrategy或LeveledCompactionStrategy.

• Level 0可以认为是MemTable的文件映射内存, 因此每个Level 0的SSTable之间的key range可能会有重叠。其他Level的SSTable key range不存在重叠。
• Level 0的写入是简单的创建-->顺序写流程，因此理论上，写磁盘的速度可以接近磁盘的理论速度。

• SSTable合并类似于简单的归并排序：根据key值确定要merge的文件，然后进行合并。因此，合并一个文件到更高层，可能会需要写多个文件。存在一定程度的写放大。是非常昂贵的I/O操作行为。Cassandra除了提供策略进行合并文件的选择，还提供了合并时I/O的限制，以期减少合并操作对上层业务的影响。

读操作优先判断key是否在MemTable, 如果不在的话，则把覆盖该key range的所有SSTable都查找一遍。简单，但是低效。因此，在工程实现上，一般会为SSTable加入索引——布隆过滤器（Bloom Filter）。它有一个特性：如果bloom说一个key不存在，就一定不存在，而当bloom说一个key存在于这个文件，可能是不存在的。实现层面上，布隆过滤器就是key--比特位的映射。理想情况下，当然是一个key对应一个比特实现全映射，但是太消耗内存。因此，一般通过控制假阳性概率来节约内存，代价是牺牲了一定的读性能。对于我们的应用场景，我们将该概率从0.99降低到0.8，布隆过滤器的内存消耗从2GB+下降到了300MB，数据读取速度有所降低，但在感知层面可忽略。