LSM Tree/MemTable/SSTable基本原理

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还有很多细节区别,这里不展开讨论。

基本原理

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

  • 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加入索引。可以是一个key-offset索引(类似于kafka的index文件),也可以是布隆过滤器(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.

扩展阅读