冥冥之中,接触到了不同于关系数据库的NoSQL Key-Value存储引擎RocksDB,懵懵懂懂、充满好奇,google一点,满眼皆是LSM-Tree,头晕眼花、若即若离,便有了这篇文章,一起与大家分享这趟探险之旅。

LSM-Tree(Log-Structured-Merge-Tree)

LSM从命名上看,容易望文生义成一个具体的数据结构,一个tree。但LSM并不是一个具体的数据结构,也不是一个tree。LSM是一个数据结构的概念,是一个数据结构的设计思想。实际上,要是给LSM的命名断句,Log和Structured这两个词是合并在一起的,LSM-Tree应该断句成Log-Structured、Merge、Tree三个词汇,这三个词汇分别对应以下三点LSM的关键性质:

  • 将数据形成Log-Structured:在将数据写入LSM内存结构之前,先记录log。这样LSM就可以将有易失性的内存看做永久性存储器。并且信任内存上的数据,等到内存容量达到threshold再集体写入磁盘。将数据形成Log-Structured,也是将整体存储结构转换成了“内存(in-memory)”存储结构。
  • 将所有磁盘上数据不组织成一个整体索引结构,而组织成有序的文件集:因为磁盘随机读写比顺序读写慢3个数量级,LSM尽量将磁盘读写转换成顺序读写。将磁盘上的数据组织成B树这样的一个整体索引结构,虽然查找很高效,但是面对随机读写,由于大量寻道导致其性能不佳。而LSM用了一种很有趣的方法,将所有数据不组织成一个整体索引结构,而组织成有序的文件集。每次LSM面对磁盘写,将数据写入一个或几个新生成的文件,顺序写入且不能修改其他文件,这样就将随机读写转换成了顺序读写。LSM将一次性集体写入的文件作为一个level,磁盘上划分多level,level与level之间互相隔离。这就形成了,以写入数据时间线形成的逻辑上、而非物理上的层级结构,这也就是为什么LSM被命名为”tree“,但不是“tree”。
  • 将数据按key排序,在合并不同file、level上的数据时类似merge-join:如果一直保持生成新的文件,不仅写入会造成冗余空间,而且也会大量降低读的性能。所以要高效的、周期性合并不同file、level。而如果数据是乱序的,根本做不到高效合并。所以LSM要将数据按key排序,在合并不同file、level上的数据时类似merge-join

很明显,LSM牺牲了一部分读的性能和增加了合并的开销,换取了高效的写性能。那LSM为什么要这么做?实际上,这就关系到对于磁盘写已经没有什么优化手段了,而对于磁盘读,不论硬件还是软件上都有优化的空间。通过多种优化后,读性能虽然仍是下降,但可以控制在可接受范围内。实际上,用于磁盘上的数据结构不同于用于内存上的数据结构,用于内存上的数据结构性能的瓶颈就在搜索复杂度,而用于磁盘上的数据结构性能的瓶颈在磁盘IO,甚至是磁盘IO的模式。

LSM近年来已被广泛使用起来,还有将B家族树和LSM结合起来使用的,像HBase、SQLite4、MongoDB、Cassandra、LevelDB,还有接下来的主角RocksDB,这些当家数据存储花旦,都或多或少支持、使用起LSM了。

RocksDB

RocksDB是Facebook在LevelDB基础上用C++写的Key-Value存储引擎。其Key和Value都是二进制流。并对闪存(flash)有更友好的优化。先来聊一聊RocksDB的整体结构,然后再聊一聊RocksDB中的一些有意思的抽象,最后聊一聊RocksDB内存上、磁盘上的具体结构。在RocksDB中,将内存结构中的数据写入磁盘结构叫做flush,而不同file、level之间merge叫做compaction。

Architecture

RocksDB如上文所说是基于LSM做存储。RocksDB在内存中的结构叫做memtable,用于形成Log-Structured的file叫做logfile,磁盘上的file结构叫做sstfile,用于记录对file更改的log叫做manifest。

Column-Family

为存储的数据逻辑分族,将不同family互相隔离,分开配置、存储。column family共享logfile,而不共享memtable和sstfile,这使得column family有以下两点特点:

  • 多个column family仍然能保持事务的原子性。
  • 单独增加、修改、删除一个column family内的数据性能提升。

Filter

RocksDB有一些奇思妙想的filter,这些filter根据特定条件生成,通过数据的key就可以判断数据是否确定或可能被特定条件排除掉。有些filter可以用来对读优化,有些也可以用来管理数据的生命周期等。

Bloom-Filter

bloom filter就是一个能提高读性能的filter。通过算法可以生成一个key set对应的bloom filter。这个bloom filter可以判断出任意key可能存在或者肯定不存在key set中。每个sstfile在生成的时候,都会创建一个或多个对应的bloom filter,当在读数据的时候,可以快速判断出数据是否可能在sstfile中。在做range scan和prefix查找的时候,bloom filter也能帮上忙。

Time-To-Live(TTL)

RocksDB还支持为存入的数据设置上最长生命周期。RocksDB会为有TTL的数据创建一个filter。这种filter叫做compaction filter,当进行compaction的时候,生命周期结束的数据将会被排除。很明显,这个TTL不是绝对时间,RocksDB会在绝对时间过后的一段时间内删除数据。

Memtable

RocksDB在内存上的结构由memtable组成,具体默认使用SkipList,当然,外部也可以指定其他数据结构。不过,SkipList做为用多个线性结构模仿出层级结构的“树状“数据结构,能提供常数级顺序访问和对数级随机访问,并且在并发环境相对于其他树状数据结构,减轻了锁开销,运用在这里再合适不过了。

Flush

为了减小锁开销,将写入memtable和flush分离,RocksDB会使用多个memtable,并且把flush这件事抽象为task-pipeline,也就是job、job queue、worker抽象。将要flush的memtable先转换成immutable memtable,代表其不可写了,并将immutable memtable加入flush pipeline,等待后台线程去flush。而同时新的memtable生成取代immutable memtable等待数据写入。在将immutable memtable flush的过程中,值得一提的是会做inline-compaction,这是将immutbale memtable提前进行数据合并的优化,如果在这个memtable创建到flush的周期中,数据被加入然后删除,在这一步就可以compact掉,这对短生命周期的数据有很大的写优化。

SSTFile(SSTTable)

RocksDB在磁盘上的file结构sstfile由block作为基本单位组成,一个sstfile结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1: filter block]
[meta block 2: stats block]
[meta block 3: compression dictionary block]
...
[meta block K: future extended block]
[metaindex block]
[index block]
[Footer]
<end_of_file>

其中data block就是数据实体block,meta block为元数据block。metaindex block和index block分别是对meta block和data block的索引block。metaindex block和index block都以blockhandle结构作为指向所索引block的指针。blockhandle包含所索引block的offset和size。metaindex block将所索引的meta block的名字作为key。而index block将所索引的data block前一block的最大key值与所索引data block的最小key值的中间任意值作为key。

filter block记录的就是针对此sstfile生效的一系列filter。stats block也就是properties block,它以key-value形式记录了此sstfile的一些属性。sstfile组成的block有可能被压缩(compression),不同level也可能使用不同的compression方式。compression dictionary block记录了适用于compression此sstfile block的库。footer添加了一些字节填充,和记录了指向metaindex block、index block的blockhandle结构指针。这说明sstfile如果要遍历block,会逆序遍历,从footer开始。

Compaction

RocksDB会在后台多线程compact。RocksDB有两种compact style:

  • Universal Style Compaction:这种style去compact就如上文LSM所聊的,将磁盘上数据完全按照写入时间线去组织,只将相邻时间段内写入磁盘上的数据compact,很像在合并互不重叠(overlapping)的时间段。这种style可以compact出新的file或者level。很明显,不同时间段内的数据会有重叠的key,会有冗余空间。
  • Level Style Compaction:这种style去compact不会将磁盘上数据完全按照写入时间线去组织。而为了防止同一level多个file中相同key数据的冗余,这种style要保证同一level不存在有相同key的数据。若将Ln level中的file1 要compact到Ln+1level,要将Ln+1level中所有包含重叠file1数据key的文件一起compact,最后将这些file compact成Ln+1level中的一个新file。这种style还会造成一种效果,就是同一level的file按key值排序。虽然Level Style Compaction减少了冗余空间,但是,对于读数据来说,Universal Style Compaction更加遵守局部性,所以Level Style Compaction读性能更差一点。

也就说,Universal Style Compaction重读轻空间,Level Style Compaction重空间轻读。RocksDB将后者作为default style,关于这两种style如何选择(pick)level、file去compact,这里就不整体叙述了,基本是file、level的数量或大小达到一个ratio的threshold就会triger compact,关于Universal Style的选择在这里关于Level Style的选择在这里。挑个有趣的聊下,Level Style如何pick file去compact?RocksDB还不能提供一个universal策略去pick,不过以下几个option可以选择:

  • 优先选择key分布范围集中的file去compact:file中数据key如果分布集中,就会有更少的重叠file在下一level,就会有更少的compact开销。用kOldestSmallestSeqFirst设置优先compactkey分布范围集中的file。
  • 优先选择冷数据file去compact:经常修改的热数据如果经常compact,只会浪费开销。设想下,刚刚插入的一组数据,马上又删除,如果插入后就进行compact,本应该删除的数据又占了两倍的冗余空间。用kOldestLargestSeqFirst设置优先compact冷数据file。
  • 优先选择被删除数据多的file去compact:被删除的数据如果早被compact的话,可以减少冗余空间,用kByCompensatedSize设置优先compact被删除数据多的file。

SSTFile-Indexing

如果RocksDB使用的是Level Style Compaction,那么还可以在查找数据时做更多优化。Level Style Compaction保证同一level不存在有相同key的数据,且file按key值排序。首先,对于有序结构搜索,可以使用二分查找。其次,如果在某一level中都查找不到key,那么在下一level中查找的时候,可以用查找到的最后一个file的key范围排除下一level的很多file,比如如下结构:

1
2
3
4
5
6
7
8
                                         file 1                                file 2
+----------+ +----------+
level 1: | 100, 200 | | 300, 400 |
+----------+ +----------+
file 1 file 2 file 3 file 4 file 5 file 6 file 7
+--------+ +--------+ +---------+ +----------+ +----------+ +----------+ +----------+
level 2: | 40, 50 | | 60, 70 | | 95, 110 | | 150, 160 | | 210, 230 | | 290, 300 | | 310, 320 |
+--------+ +--------+ +---------+ +----------+ +----------+ +----------+ +----------+

如果要查找80,在level 1中file1没有查找到,那么在level2中可以排除file3以后的file。这种排除和level结构有点像区间树。基于此思想,在level compact的时候,可以为file添加一系列指向下一level file的指针,加快查找速度。

Manifest

因为文件系统的操作不能保证原子性,所以RocksDB对file的更改也会记录log,就记录在manifest里。实际上,可以将manifest看做,记录的是RocksDB的状态。manifest记录的内容就成了RocksDB按时间排序的一系列状态,如果,将每个状态看做RocksDB某个时间点的快照,manifest就是RocksDB的动图GIF。

Cache

没有cache的存储引擎是不完整的,RocksDB有两种cache,block cache和table cache。先来聊聊block cache。block cache缓存的单位就是sstfile的data block,这种cache有两种算法,经典的LRU和clock,任由你选择。除了data block,用于索引和提高读性能的index block和filter block更是重点缓存对象,但RocksDB并不会把这俩放在block cache中,RocksDB会单独照顾好这俩,基本不用外部操心。而table cache缓存的是sstfile的file descriptor,实际上,操作系统通过file descriptor用引用计数的方式来管理file结构体和其背后的资源。也就是说,table cache缓存的是操作系统用来操作sstfile的file结构体和其背后资源,更多关于file descriptor结构,推荐这篇文章

Tips

以下是使用RocksDB的一些建议:

  • RocksDB线程模型是单句柄对多线程。
  • Get、Put、Delete等操作不需要操心数据同步问题,而Iterator和WriteBatch需要同步控制。
  • WriteBatch类似于事务,提供将一个或多个数据库操作抽象为单位的能力,此单位是原子性的,但并不会互相隔离从而并发控制,也不会检测出异常并恢复。

本篇聊了很多RocksDB的设计思想。然而毕竟大多数工程师都是面向应用,不会去搞个存储引擎。这里就总结几条从LSM、RocksDB等存储引擎中学到的有关读写IO的技巧,理解了大有裨益。

  • 相对于计算、内存读取,磁盘IO慢不知多少数量级。
  • 相对于执行一次磁盘IO,磁盘IO的数据量多少不重要,也就说开始、结束一次磁盘IO更费时。尽量集中对磁盘进行IO。
  • 相对于磁盘随机读写,磁盘顺序读写快上3个数量级。
  • 读写分离,减少并发锁的性能开销。

引用

LSM:https://www.zhihu.com/question/19887265

LSM论文:http://www.cs.umb.edu/~poneil/lsmtree.pdf

RocksDB Blog:http://rocksdb.org/blog/

RocksDB Wiki:https://github.com/facebook/rocksdb/wiki