冥冥之中,接触到了不同于关系数据库的 NoSQL Key-Value 存储引擎 RocksDB,懵懵懂懂、充满好奇,google 一点,满眼皆是 LSM-Tree,头晕眼花、若即若离,便有了这篇文章,一起与大家分享这趟探险之旅。
LSM 从命名上看,容易望文生义成一个具体的数据结构,一个 tree。但 LSM 并不是一个具体的数据结构,也不是一个 tree。LSM 是一个数据结构的概念,是一个数据结构的设计思想。实际上,要是给 LSM 的命名断句,Log 和 Structured 这两个词是合并在一起的,LSM-Tree 应该断句成 Log-Structured、Merge、Tree 三个词汇,这三个词汇分别对应以下三点 LSM 的关键性质:
很明显,LSM 牺牲了一部分读的性能和增加了合并的开销,换取了高效的写性能。那 LSM 为什么要这么做?实际上,这就关系到对于磁盘写已经没有什么优化手段了,而对于磁盘读,不论硬件还是软件上都有优化的空间。通过多种优化后,读性能虽然仍是下降,但可以控制在可接受范围内。实际上,用于磁盘上的数据结构不同于用于内存上的数据结构,用于内存上的数据结构性能的瓶颈就在搜索复杂度,而用于磁盘上的数据结构性能的瓶颈在磁盘 IO,甚至是磁盘 IO 的模式。
LSM 近年来已被广泛使用起来,还有将 B 家族树和 LSM 结合起来使用的,像 HBase、SQLite4、MongoDB、Cassandra、LevelDB,还有接下来的主角 RocksDB,这些当家数据存储花旦,都或多或少支持、使用起 LSM 了。
RocksDB 是 Facebook 在 LevelDB 基础上用 C++ 写的 Key-Value 存储引擎。其 Key 和 Value 都是二进制流。并对闪存 (flash) 有更友好的优化。先来聊一聊 RocksDB 的整体结构,然后再聊一聊 RocksDB 中的一些有意思的抽象,最后聊一聊 RocksDB 内存上、磁盘上的具体结构。在 RocksDB 中,将内存结构中的数据写入磁盘结构叫做 flush,而不同 file、level 之间 merge 叫做 compaction。
RocksDB 如上文所说是基于 LSM 做存储。RocksDB 在内存中的结构叫做 memtable,用于形成 Log-Structured 的 file 叫做 logfile,磁盘上的 file 结构叫做 sstfile,用于记录对 file 更改的 log 叫做 manifest。
为存储的数据逻辑分族,将不同 family 互相隔离,分开配置、存储。column family 共享 logfile,而不共享 memtable 和 sstfile,这使得 column family 有以下两点特点:
RocksDB 有一些奇思妙想的 filter,这些 filter 根据特定条件生成,通过数据的 key 就可以判断数据是否确定或可能被特定条件排除掉。有些 filter 可以用来对读优化,有些也可以用来管理数据的生命周期等。
bloom filter 就是一个能提高读性能的 filter。通过算法可以生成一个 key set 对应的 bloom filter。这个 bloom filter 可以判断出任意 key 可能存在或者肯定不存在 key set 中。每个 sstfile 在生成的时候,都会创建一个或多个对应的 bloom filter,当在读数据的时候,可以快速判断出数据是否可能在 sstfile 中。在做 range scan 和 prefix 查找的时候,bloom filter 也能帮上忙。
RocksDB 还支持为存入的数据设置上最长生命周期。RocksDB 会为有 TTL 的数据创建一个 filter。这种 filter 叫做 compaction filter,当进行 compaction 的时候,生命周期结束的数据将会被排除。很明显,这个 TTL 不是绝对时间,RocksDB 会在绝对时间过后的一段时间内删除数据。
RocksDB 在内存上的结构由 memtable 组成,具体默认使用 SkipList,当然,外部也可以指定其他数据结构。不过,SkipList 做为用多个线性结构模仿出层级结构的 "树状" 数据结构,能提供常数级顺序访问和对数级随机访问,并且在并发环境相对于其他树状数据结构,减轻了锁开销,运用在这里再合适不过了。
为了减小锁开销,将写入 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 掉,这对短生命周期的数据有很大的写优化。
RocksDB 在磁盘上的 file 结构 sstfile 由 block 作为基本单位组成,一个 sstfile 结构如下:
- <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 开始。
RocksDB 会在后台多线程 compact。RocksDB 有两种 compact style:
也就说,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 可以选择:
如果 RocksDB 使用的是 Level Style Compaction,那么还可以在查找数据时做更多优化。Level Style Compaction 保证同一 level 不存在有相同 key 的数据,且 file 按 key 值排序。首先,对于有序结构搜索,可以使用二分查找。其次,如果在某一 level 中都查找不到 key,那么在下一 level 中查找的时候,可以用查找到的最后一个 file 的 key 范围排除下一 level 的很多 file,比如如下结构:
- 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 的指针,加快查找速度。
因为文件系统的操作不能保证原子性,所以 RocksDB 对 file 的更改也会记录 log,就记录在 manifest 里。实际上,可以将 manifest 看做,记录的是 RocksDB 的状态。manifest 记录的内容就成了 RocksDB 按时间排序的一系列状态,如果,将每个状态看做 RocksDB 某个时间点的快照,manifest 就是 RocksDB 的动图 GIF。
没有 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 结构, 推荐这篇文章 。
以下是使用 RocksDB 的一些建议:
本篇聊了很多 RocksDB 的设计思想。然而毕竟大多数工程师都是面向应用,不会去搞个存储引擎。这里就总结几条从 LSM、RocksDB 等存储引擎中学到的有关读写 IO 的技巧,理解了大有裨益。
来源: http://www.tuicool.com/articles/7ju2UfI