LSM Tree/MemTable/SSTable基本原理

时光飞逝，截至今天，2018的进度条已经毫不留情的燃烧掉了8.5%。

2017接触了很多新事物，也实践和落地了一些有意思的技术、产品和框架。要想走得快，一个人走，要想走得远，得学会多回头看，多总结。这也是接下来一系列文章的初衷。当然，前提是自己能够坚持写下去，😶

是为记。

背景

2017年，做调用链服务的时候，为了存储整个系统的调用事件数据，遇到了一个存储上的问题：数据每天的写入量大概在10亿级别，也就是1.1w rps(record per second), 加上高峰期流量波动和系统冗余，我们把及格线定为3w rps。这是一个典型的写多读少的场景，自然直接放弃了关系型数据库；同时考虑到写入的时序特性，选型基本锁定到基于LSM Tree为存储引擎的数据库上。挑战依然在，但是基于LSM Tree的数据库一大把（HBase, Cassandra, RockDB, LevelDB, SQLite...），解决问题无非是时间问题。

我们先尝试了ssdb，号称可以替代redis, 一些指标上快过redis. 结果被坑得体无完肤：

1. key不支持过期（2017.04）；
2. 写入性能压测只有2w qps，如果数据记录增大，性能迅速下降；
3. 翻了下代码实现，虽然很失望，但是感觉因此避开了一个定时炸弹而庆幸😝

在同事推荐下，我们尝试了Cassandra. 虽然国内用得不多，但是在《微服务架构》中，看到了奈飞（Netflix）的大规模使用案例，信心还是有的。实际压测结果：单节点写入性能在8w qps，超出预期。此外，系统上线后，同事花了大量时间调优参数，目前线上的单节点性能应该远超8w qps.

基本概念

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

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

基本原理

image

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

image

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

image

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

image

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

Q&A

• 基于LSM Tree存储引擎的数据适用于哪些场景？

  (key or key-range), 且key/key-range整体大致有序。

• LSM Tree自从Google BigTable问世后，如此牛x, 为什么没有替代B Tree呀？

  LSM Tree本质上也是一种二分查找的思想，只是这种二分局限在key的大致有序这个假设上，并充分利用了磁盘顺序写的性能，但是普适性一般。B Tree对于写多读少的场景，大部分代价开销在Tree的维护上，但是具有更强的普适性。

• 看起来，你们已经将Cassandra玩得很溜了，你们线上用了多大集群支持当前业务？

  其实……还可以吧，主要是队友给力。还有就是国外有独角兽奈飞领头，遇到问题其实还是容易解决的。我们目前线上用了3*(4 core, 16G), 系统冗余还很大。最近奈飞出了一篇关于Cassandra优化的深度博文，如果有对Cassandra有兴趣，可以阅读Scaling Time Series Data Storage.

扩展阅读

• LSM Tree
• RockDB Leveled Compaction
• Cassandra MemtableSSTable

同步自我的博客 LSM Tree/MemTable/SSTable基本原理