LSM-tree

语言: CN / TW / HK

LSM-tree

十年前,谷歌发表了 “BigTable” 的论文,论文中很多很酷的方面之一就是它所使用的文件组织方式,这个方法更一般的名字叫 Log Structured-Merge Tree。

LSM(Log Structured Merge Tree)是当前被用在许多产品的文件结构策略:HBase, Cassandra, LevelDB, SQLite,clickhouse,tdengine,甚至在mangodb3.0中也带了一个可选的LSM引擎(Wired Tiger 实现的)。

磁盘操作

我们知道磁盘随机操作慢,顺序读写快;

img

上图很好的说明了这一点,他们展现了一些反直觉的事实,顺序读写磁盘(不管是SATA还是SSD)快于随机读写主存,而且快至少三个数量级。这说明我们要避免随机读写,最好设计成顺序读写。

现在我们发现,如果我们对写操作的吞吐量敏感,我们最好怎么做?

一个好的办法是简单的将数据添加到文件。这个策略经常被使用在日志或者堆文件,因为他们是完全顺序的,所以可以提供非常好的写操作性能,大约等于磁盘的理论速度,也就是200~300 MB/s。

这说明日志仅仅适用于一些简单的场景:1. 数据是被整体访问,像大部分数据库的WAL(write-ahead log) 2. 知道明确的offset,比如在Kafka、Rocketmq中。

  1. 二分查找: 将文件数据有序保存,使用二分查找来完成特定key的查找。
  2. 哈希:用哈希将数据分割为不同的bucket
  3. B+树:使用B+树 或者 ISAM 等方法,可以减少外部文件的读取
  4. 外部文件: 将数据保存为日志,并创建一个hash或者查找树映射相应的文件。

cassandra—一致性hash rowkey+ CacheService(缓存管理)

Kafka/rocketmq—offset定位

clickhouse—洗漱索引(类似跳跃表zset)

msyql—b+树

Hbase---提前分配sstable地址存放在外部文件中,类似hash槽? 好像也是跳表

所有的方法都可以有效的提高了读操作的性能(最少提供了O(log(n)) ),但是,却丢失了日志文件超好的写性能。上面这些方法,都强加了总体的结构信息在数据上,数据被按照特定的方式放置,所以可以很快的找到特定的数据,但是却对写操作不友善,让写操作性能下降。

更糟糕的是,当我们需要更新hash或者B+树的结构时,需要同时更新文件系统中特定的部分,这就是上面说的比较慢的随机读写操作。这种随机的操作要尽量减少

LSM-Tree

LSM-Tree里面,核心的数据结构就是SSTable,全称是Sorted String Table.

SSTable是一种拥有持久化,有序且不可变的的键值存储结构,它的key和value都是任意的字节数组,并且了提供了按指定key查找和指定范围的key区间迭代遍历的功能。SSTable内部包含了一系列可配置大小的Block块,典型的大小是64KB,关于这些Block块的index存储在SSTable的尾部,用于帮助快速查找特定的Block。当一个SSTable被打开的时候,index会被加载到内存,然后根据key在内存index里面进行一个二分查找,查到该key对应的磁盘的offset之后,然后去磁盘把响应的块数据读取出来。当然如果内存足够大的话,可以直接把SSTable直接通过MMap的技术映射到内存中,从而提供更快的查找。

img

在LSM-Tree里,SSTable有一份在内存里面,其他的多级在磁盘上,如下图是一份完整的LSM-Tree图示:

img

我们总结下在在LSM-Tree里面如何写数据的?

1,当收到一个写请求时,会先把该条数据记录在WAL Log里面,用作故障恢复。

2,当写完WAL Log后,会把该条数据写入内存的SSTable里面,也称Memtable。注意为了维持有序性在内存里面可以采用红黑树或者跳跃表相关的数据结构。(原理有点类似redis hset跳跃表--ckickhouse稀疏索引)

3,当Memtable超过一定的大小后,会在内存里面冻结,变成不可变的Memtable,同时为了不阻塞写操作需要新生成一个Memtable继续提供服务。

4,把内存里面不可变的Memtable给dump到到硬盘上的SSTable层中,此步骤也称为Minor Compaction,这里需要注意在L0层的SSTable是没有进行合并的,所以这里的key range在多个SSTable中可能会出现重叠,在层数大于0层之后的SSTable,不存在重叠key。

5,当每层的磁盘上的SSTable的体积超过一定的大小或者个数,也会周期的进行合并。此步骤也称为Major Compaction,这个阶段会真正 的清除掉被标记删除掉的数据以及多版本数据的合并,避免浪费空间,注意由于SSTable都是有序的,我们可以直接采用merge sort进行高效合并。

接着我们总结下在LSM-Tree里面如何读数据的?

1,当收到一个读请求的时候,会直接先在内存里面查询,如果查询到就返回。

2,如果没有查询到就会依次下沉,知道把所有的Level层查询一遍得到最终结果。

那么如果运气不好,我们需要扫描秒所有的分层,那么我们就需要优化:

1,压缩

SSTable 是可以启用压缩功能的,并且这种压缩不是将整个 SSTable 一起压缩,而是根据 locality 将数据分组,每个组分别压缩,这样的好处当读取数据的时候,我们不需要解压缩整个文件而是解压缩部分 Group 就可以读取。

2,缓存

因为SSTable在写入磁盘后,除了Compaction之外,是不会变化的,所以我可以将Scan的Block进行缓存,从而提高检索的效率

3,索引,Bloom filters

正常情况下,一个读操作是需要读取所有的 SSTable 将结果合并后返回的,但是对于某些 key 而言,有些 SSTable 是根本不包含对应数据的,因此,我们可以对每一个 SSTable 添加 Bloom Filter,因为布隆过滤器在判断一个SSTable不存在某个key的时候,那么就一定不会存在,利用这个特性可以减少不必要的磁盘扫描。

4,合并

这个在前面的写入流程中已经介绍过,通过定期合并瘦身, 可以有效的清除无效数据,缩短读取路径,提高磁盘利用空间。但Compaction操作是非常消耗CPU和磁盘IO的,尤其是在业务高峰期,如果发生了Major Compaction,则会降低整个系统的吞吐量,这也是一些NoSQL数据库,比如Hbase里面常常会禁用Major Compaction,并在凌晨业务低峰期进行合并的原因。

快速随机写

一旦将SSTable放在磁盘上,它实际上是不变的,因为插入或删除将需要对文件进行大量的I / O重写。话虽这么说,对于静态索引来说,这是一个很好的解决方案:读入索引,您总是只需要一个磁盘,或者只是memmap将整个文件存储到内存中。随机读取既快速又容易。

随机写入会变得更加困难和昂贵,也就是说,除非整个表都在内存中,否则我们将回到简单的指针操作。事实证明,这是Google BigTable着手解决的问题:对数以字节计的数据集进行快速读/写访问,并在其下提供SSTables支持。他们是如何做到的呢?

我们想保留SSTables给我们的快速读取访问权限,但我们也想支持快速随机写入。事实证明,我们已经拥有所有必要的片段:当SSTable处于内存中时(我们称其为MemTable),随机写入会很快,如果表是不可变的,那么从磁盘上读取SSTable也会很快。现在让我们介绍以下约定:

img

  1. 磁盘SSTable索引始终加载到内存中
  2. 所有写入均直接进入MemTable索引
  3. 先读取检查MemTable,然后读取SSTable索引
  4. 定期将MemTable作为SSTable刷新到磁盘
  5. 磁盘上的SSTable会定期“折叠在一起”

我们在这里做了什么?写操作总是在内存中完成,因此总是很快。一旦MemTable达到一定大小,就将其作为不可变对象刷新到磁盘SSTable。但是,我们将所有SSTable索引保留在内存中,这意味着对于任何读取,我们都可以先检查MemTable,然后遍历SSTable索引的序列以查找我们的数据。

Cassandra读写操作

cassandra一般都是根据rowkey来进行读写操作的(hadoop类似),所以这个查询最主要的就是通过rowkey找到对应数据的位置。

根据LSM-tree结构,我们需要找到rowkey对应的sstable的位置,并载入内存,然后根据sstable的数据结构二分查找,找到对应的数据,前文我们知道sstable一般是可能使用红黑树来保存数据,数据是有序的,即时间复杂度为logN;

所以,我们需要很快的根据rowkey找到sstable并载入内存。

在cassandra中,于是就有了keycache的概念,用于记录了sstable中rowkey对应的data.db文件中的位置,并且存储在内存中,减少一次IO来加快通过rowkey的检索速度。

在cassandra运行中,cache的总体管理和控制主要由CacheService管理

public final AutoSavingCache<KeyCacheKey, RowIndexEntry> keyCache;

而一组sstable就会对应在内存中映射出一个SSTableReader对象进行对应SSTable的控制。

所以在SSTableReader中就会有相应的指针指向keycache

private InstrumentingCache<KeyCacheKey, RowIndexEntry> keyCache;

B+Tree VS LSM-Tree

传统关系型数据采用的底层数据结构是B+树,那么同样是面向磁盘存储的数据结构LSM-Tree相比B+树有什么异同之处呢?

LSM-Tree的设计思路是,将数据拆分为几百M大小的Segments,并是顺序写入。(一个sstable一般是64KB)

B+Tree则是将数据拆分为固定大小的Block或Page, 一般是4KB大小,和磁盘一个扇区的大小对应,Page是读写的最小单位。

在数据的更新和删除方面,B+Tree可以做到原地更新和删除,这种方式对数据库事务支持更加友好,因为一个key只会出现一个Page页里面,但由于LSM-Tree只能追加写,并且在L0层key的rang会重叠,所以对事务支持较弱,只能在Segment Compaction的时候进行真正地更新和删除。

因此LSM-Tree的优点是支持高吞吐的写(可认为是O(1)),这个特点在分布式系统上更为看重,当然针对读取普通的LSM-Tree结构,读取是O(N)的复杂度,在使用索引或者缓存优化后的也可以达到O(logN)的复杂度。

而B+tree的优点是支持高效的读(稳定的OlogN),但是在大规模的写请求下(复杂度O(LogN)),效率会变得比较低,因为随着insert的操作,为了维护B+树结构,节点会不断的分裂和合并。操作磁盘的随机读写概率会变大,故导致性能降低。

还有一点需要提到的是基于LSM-Tree分层存储能够做到写的高吞吐,带来的副作用是整个系统必须频繁的进行compaction,写入量越大,Compaction的过程越频繁。而compaction是一个compare & merge的过程,非常消耗CPU和存储IO,在高吞吐的写入情形下,大量的compaction操作占用大量系统资源,必然带来整个系统性能断崖式下跌,对应用系统产生巨大影响,当然我们可以禁用自动Major Compaction,在每天系统低峰期定期触发合并,来避免这个问题。

MergeTree

MergeTree引擎族是ClickHouse强大功能的基础。MergeTree这个名词是在我们耳熟能详的LSM Tree之上做减法而来——去掉了MemTable和Log。也就是说,向MergeTree引擎族的表插入数据时,数据会不经过缓冲而直接写到磁盘。官方文档中有如下的描述:

MergeTree is not an LSM tree because it doesn’t contain "memtable" and "log": inserted data is written directly to the filesystem. This makes it suitable only to INSERT data in batches, not by individual row and not very frequently – about once per second is ok, but a thousand times a second is not. We did it this way for simplicity’s sake, and because we are already inserting data in batches in our applications.

但是在最近的ClickHouse新版本中,上述情况发生了巨大的改变。社区通过#8290#10697两个PR实现了名为Polymorphic Parts的特性,使得MergeTree引擎能够更好地处理频繁的小批量写入,但同时也标志着MergeTree的内核开始向真正的LSM Tree靠拢。

Wide/Compact Part Storage

先来创建一张测试表,并写入两批次数据。


  1. CREATE TABLE test.test_event_log (
  2. event_time DateTime,
  3. user_id UInt64,
  4. event_type String,
  5. site_id UInt64
  6. ) ENGINE = MergeTree()
  7. PARTITION BY toYYYYMMDD(event_time)
  8. ORDER BY (user_id,site_id)
  9. SETTINGS index_granularity = 8192;
  10. INSERT INTO test.test_event_log VALUES
  11. ('2020-09-14 12:00:00',12345678,'appStart',16789),
  12. ('2020-09-14 12:00:01',12345679,'appStart',26789);
  13. INSERT INTO test.test_event_log VALUES
  14. ('2020-09-14 13:00:00',22345678,'openGoodsDetail',16789),
  15. ('2020-09-14 13:00:01',22345679,'buyNow',26789);

利用tree命令观察该表的数据目录,可以发现形成了两个part目录,每个part目录中都存在每一列的数据文件(bin)和索引标记文件(mrk2),老生常谈了。


  1. ├── 20200914_1_1_0
  2. │ ├── checksums.txt
  3. │ ├── columns.txt
  4. │ ├── count.txt
  5. │ ├── event_time.bin
  6. │ ├── event_time.mrk2
  7. │ ├── event_type.bin
  8. │ ├── event_type.mrk2
  9. │ ├── minmax_event_time.idx
  10. │ ├── partition.dat
  11. │ ├── primary.idx
  12. │ ├── site_id.bin
  13. │ ├── site_id.mrk2
  14. │ ├── user_id.bin
  15. │ └── user_id.mrk2
  16. ├── 20200914_2_2_0
  17. │ ├── ......

当写入特别频繁时,短时间内生成的part目录过多,后台的merger线程合并不过来,就会出现Too many parts的异常,所以官方才会建议不要执行超过一秒钟一次的写入操作。

TDengine优化点:

​ TDengine根据时间和设备对存储做了优化,导致读写速度快:

1.每个设备的数据是独立的,每个设备一张表,根据设备号查询不会去查其他设备的数据;

2.再按时间将每个设备的大表分成小表,再将小表按时间分成块,块内数据都是按时间有序,所以可以顺序写,按时间二分查找的读

以上两个原因导致TDengine在按时间、设备的查询会很快,但如果查询不是时间、设备作为筛选条件,效率也会低 。而且TDengine的这两种存储上的优化,尤其是按设备分表,并不适合其他场景,和hadoop没有可比性。

初步比较TDengine和InfluxDB:

InfluxDB不会将不同设备的数据分开,TDengine按设备分表是为了保证每个块内的数据都是按时间有序的。

如果TDengine不按设备分表,设备A在19:00、19:01产生两条数据,设备B在19:00产生数据,因为网络延迟等,导致设备B的这条数据比设备A的两条数据晚到TDengine,则存储的数据就是:设备A19:00数据、设备A19:01数据、设备B19:00数据,无法保证按时间有序。

TDengine假定了数据一定能按设备分表,如果这个假设不成立呢?

什么是时序数据

什么是时序数据。时序数据是基于时间的一系列的数据。在有时间的坐标中将这些数据点连成线,往过去看可以做成多纬度报表,揭示其趋势性、规律性、异常性;往未来看可以做大数据分析,机器学习,实现预测和预警。

时序数据库就是存放时序数据的数据库,并且需要支持时序数据的快速写入、持久化、多纬度的聚合查询等基本功能。

对比传统数据库仅仅记录了数据的当前值,时序数据库则记录了所有的历史数据。同时时序数据的查询也总是会带上时间作为过滤条件。

以物联网为例,智能设备在运行时需上报各种状态,包括亮度,音量,状态,温度,湿度等等,并且需要把每时每刻监控的数据记录下来,用来做大数据分析。

大量的设备会产生大量的数据,都是以T为单位。如果只是存储下来不查询也还好(虽然已经是不小的成本),

但如果需要快速查询“今天下午两点在后有哪些灯泡是亮着的”这样的多纬度分组聚合查询,那么时序数据库会是一个很好的选择。

时序数据库遇到的挑战

很多人可能认为在传统关系型数据库上加上时间戳一列就能作为时序数据库。数据量少的时候确实也没问题,但少量数据是展现的纬度有限,细节少,可置信低,更加不能用来做大数据分析。很明显时序数据库是为了解决海量数据场景而设计的。

可以看到时序数据库需要解决以下几个问题

l 时序数据的写入:如何支持每秒钟上千万上亿数据点的写入。

l 时序数据的读取:又如何支持在秒级对上亿数据的分组聚合运算。

l 成本敏感:由海量数据存储带来的是成本问题。如何更低成本的存储这些数据,将成为时序数据库需要解决的重中之重。

这些问题不是用一篇文章就能含盖的,同时每个问题都可以从多个角度去优化解决。在这里只从数据存储这个角度来尝试回答如何解决大数据量的写入和读取。

数据的存储

单机存储

如果只是存储起来,直接写成日志就行。但因为后续还要快速的查询,所以需要考虑存储的结构。

传统数据库存储采用的都是B tree,这是由于其在查询和顺序插入时有利于减少寻道次数的组织形式。我们知道磁盘寻道时间是非常慢的,一般在10ms左右。磁盘的随机读写慢就慢在寻道上面。对于随机写入B tree会消耗大量的时间在磁盘寻道上,导致速度很慢。我们知道SSD具有更快的寻道时间,但并没有从根本上解决这个问题。

对于90%以上场景都是写入的时序数据库,B tree很明显是不合适的。

业界主流都是采用LSM tree替换B tree,比如Hbase, Cassandra等nosql中。这里我们详细介绍一下。

LSM tree包括内存里的数据结构和磁盘上的文件两部分。分别对应Hbase里的MemStore和HLog;对应Cassandra里的MemTable和sstable。

LSM tree操作流程如下:

\1. 数据写入和更新时首先写入位于内存里的数据结构。为了避免数据丢失也会先写到WAL文件中。

\2. 内存里的数据结构会定时或者达到固定大小会刷到磁盘。这些磁盘上的文件不会被修改。

\3. 随着磁盘上积累的文件越来越多,会定时的进行合并操作,消除冗余数据,减少文件数量。

img

p4-Hbase LSM tree结构介绍(注1)

可以看到LSM tree核心思想就是通过内存写和后续磁盘的顺序写入获得更高的写入性能,避免了随机写入。但同时也牺牲了读取性能,因为同一个key的值可能存在于多个HFile中。为了获取更好的读取性能,可以通过bloom filter和compaction得到,这里限于篇幅就不详细展开。

分布式存储

时序数据库面向的是海量数据的写入存储读取,单机是无法解决问题的。所以需要采用多机存储,也就是分布式存储。

分布式存储首先要考虑的是如何将数据分布到多台机器上面,也就是 分片(sharding)问题。下面我们就时序数据库分片问题展开介绍。分片问题由分片方法的选择和分片的设计组成。

分片方法

时序数据库的分片方法和其他分布式系统是相通的。

哈希分片:这种方法实现简单,均衡性较好,但是集群不易扩展。

一致性哈希:这种方案均衡性好,集群扩展容易,只是实现复杂。代表有Amazon的DynamoDB和开源的Cassandra。

范围划分:通常配合全局有序,复杂度在于合并和分裂。代表有Hbase。

分片设计

分片设计简单来说就是以什么做分片,这是非常有技巧的,会直接影响写入读取的性能。

结合时序数据库的特点,根据metric+tags分片是比较好的一种方式,因为往往会按照一个时间范围查询,这样相同metric和tags的数据会分配到一台机器上连续存放,顺序的磁盘读取是很快的。再结合上面讲到的单机存储内容,可以做到快速查询。

进一步我们考虑时序数据时间范围很长的情况,需要根据时间范围再将分成几段,分别存储到不同的机器上,这样对于大范围时序数据就可以支持并发查询,优化查询速度。

如下图,第一行和第三行都是同样的tag(sensor=95D8-7913;city=上海),所以分配到同样的分片,而第五行虽然也是同样的tag,但是根据时间范围再分段,被分到了不同的分片。第二、四、六行属于同样的tag(sensor=F3CC-20F3;city=北京)也是一样的道理。

img

p5-时序数据分片说明

优秀的时序数据库

InfluxDB:

非常优秀的时序数据库,但只有单机版是免费开源的,集群版本是要收费的。从单机版本中可以一窥其存储方案:在单机上InfluxDB采取类似于LSM tree的存储结构TSM;而分片的方案InfluxDB先通过+(事实上还要加上retentionPolicy)确定ShardGroup,再通过+的hash code确定到具体的Shard。

这里timestamp默认情况下是7天对齐,也就是说7天的时序数据会在一个Shard中。

img

p6-Influxdb TSM结构图(注2)

Kairosdb:

底层使用Cassandra作为分布式存储引擎,如上文提到单机上采用的是LSM tree。

Cassandra有两级索引:partition key和clustering key。其中partition key是其分片ID,使用的是一致性哈希;而clustering key在一个partition key中保证有序。

Kairosdb利用Cassandra的特性,将++<数据类型>+作为partition key,数据点时间在timestamp上的偏移作为clustering key,其有序性方便做基于时间范围的查询。

partition key中的timestamp是3周对齐的,也就是说21天的时序数据会在一个clustering key下。3周的毫秒数是18亿正好小于Cassandra每行列数20亿的限制。

OpenTsdb:

底层使用Hbase作为其分布式存储引擎,采用的也是LSM tree。

Hbase采用范围划分的分片方式。使用row key做分片,保证其全局有序。每个row key下可以有多个column family。每个column family下可以有多个column。

img

上图是OpenTsdb的row key组织方式。不同于别的时序数据库,由于Hbase的row key全局有序,所以增加了可选的salt以达到更好的数据分布,避免热点产生。再由与timestamp间的偏移和数据类型组成column qualifier。

他的timestamp是小时对齐的,也就是说一个row key下最多存储一个小时的数据。并且需要将构成row key的metric和tags都转成对应的uid来减少存储空间,避免Hfile索引太大。下图是真实的row key示例。

img

p7-open tsdb的row key示例(注3)

分享到: