rocksdb compaction,rocksdb 部署方案

它既有助于阅读又有助于写作。新的写入总是将数据插入到memtable中，读取过程首先查询memtable，因为memtable中的数据较新。一旦memtable满了，它就变成不可变的，并被新的memtable所取代。后台线程会将内存表的内容刷新到SST文件中，然后销毁掉磁盘的内存表。Memtable默认使用SkipList实现。也可以选择HashLinkList和HashSkipL。

ist、Vector用来加速某些查询。

SkipList MemTable

读写、随机访问和顺序扫描提供了总体良好的性能还提供了其他 memtable 实现目前不支持的一些其他有用功能例如并发插入和带Hit插入

HashSkipList MemTable

HashSkipList将数据组织在哈希表中每一个哈希桶都是一个有序的SkipListkey是原始key通过Options.prefix_extractor截取的前缀key。主要用于减少查询时的比较次数。一般与PlainTable SST格式配合使用将数据存储在 RAMFS 中。

基于哈希的 memtables 的最大限制是跨多个前缀进行扫描需要复制和排序非常慢且内存成本高。

触发 Memtable 刷新落盘的场景

写入后 Memtable 大小超过ColumnFamilyOptions::write_buffer_size所有列族的Memtable用量超过 DBOptions::db_write_buffer_size 或者 write_buffer_manager发出刷新信号。最大的MemTable将会flushedWAL文件大小超过 DBOptions::max_total_wal_size Block Cache

RocksDB 在内存中缓存数据以供读取的地方。一个Cache对象可以被同一个进程中的多个RocksDB实例共享用户可以控制整体的缓存容量。

块缓存存储未压缩的块。用户可以选择设置存储压缩块的二级块缓存。读取将首先从未压缩的块缓存中获取数据块然后是压缩的块缓存。如果使用 Direct-IO压缩块缓存可以替代 OS 页面缓存。

Block Cache有两种缓存实现分别是 LRUCache 和 ClockCache。两种类型的缓存都使用分片以减轻锁争用。容量平均分配给每个分片分片不共享容量。默认情况下每个缓存最多会被分成 64 个分片每个分片的容量不小于 512k 字节。

LRUCache 默认的缓存实现。使用容量为8MB的基于LRU的缓存。缓存的每个分片都维护自己的LRU列表和自己的哈希表以供查找。通过每个分片的互斥锁实现同步查找与插入都需要对分片加锁。

极少数情况下在块上进行读或迭代的并且固定的块总大小超过限制缓存的大小可能会大于容量。如果主机没有足够的内存这可能会导致意外的 OOM 错误从而导致数据库崩溃

ClockCache ClockCache 实现了 CLOCK 算法。时钟缓存的每个分片都维护一个缓存条目的循环列表。时钟句柄在循环列表上运行寻找要驱逐的未固定条目但如果自上次扫描以来已使用过也给每个条目第二次机会留在缓存中。

ClockCache 还不稳定不建议使用

Write Buffer Manager

Write Buffer Manager 用于控制多个列族或者多个数据库实例的内存表总使用量。

使用方式用户创建一个write buffer manager对象并将对象传递到需要控制内存的列族或数据库实例中。

有两种限制方式

1、限制 memtables 的总内存用量

触发其中一个条件将会在实例的列族上触发flush操作

如果活跃的 memtables 使用超过阈值的90%总内存超过限制活跃的 mamtables 使用也超过阈值的 50% 时。

2、memtable 的内存占用转移到 block cache

大多数情况下block cache中实际使用的block远小于block cache中缓存的所以当用户启用该功能时block cache容量将覆盖block cache和memtable两者的内存使用量。

如果用户同时开启 cache_index_and_filter_blocks那么RocksDB的三大内存区域index and filter cache memtables block cache内存占用都在block cache中。

SST文件格式

BlockBasedTable 是 SSTable 的默认表格式。

<beginning_of_file>[data block 1][data block 2]...[data block N][meta block 1: filter block]                  (see section: filter Meta Block)[meta block 2: index block][meta block 3: compression dictionary block]  (see section: compression dictionary Meta Block)[meta block 4: range deletion block]          (see section: range deletion Meta Block)[meta block 5: stats block]                   (see section: properties Meta Block)...[meta block K: future extended block]  (we may add more meta blocks in the future)[metaindex block][Footer]                               (fixed size; starts at file_size - sizeof(Footer))<end_of_file>

数据块 DataBlock键值对序列按照根据排序规则顺序排列划分为一系列数据块data block。这些块在文件开头一个接一个排列每个数据块可选择性压缩。

元数据块 MetaBlock紧接着数据块的是一堆元数据块meta block元数据块包括过滤块filter block、索引块index block、压缩字典块compression dictionary block、范围删除块range deletion block、属性块properties block。

元索引3块 MetaIndexBlock 元索引块包含一个映射表指向每个meta blockkey是meta block的名称value是指向该meta block的指针指针通过offset、size指向数据块。

页脚 Footer文件末尾是固定长度的页脚。包括指向metaindex block的指针指向index block的指针以及一个magic number。

Meta Block的具体种类 索引块 Index Block

索引块用于查找包含指定key的数据块。是一种基于二分搜索的数据结构。一个文件可能包含一个索引块也可能包含一组分区索引块这取决于使用配置。即存在全局索引与分区索引两种索引方式。

过滤器块 Filter Block

全局过滤器、分区过滤器都是通过用布隆过滤器实现

全局过滤器 Full Filter: 在此过滤器中整个 SST 文件只有一个过滤器块。分区过滤器 Partitioned Filter: Full Filter 被分成多个子过滤器块在这些块的顶层有一个索引块用于将key映射到相应的子过滤器块。

压缩字典块 Compression Dictionary Block

包含用于在压缩/解压缩每个块之前准备压缩库的字典。

范围删除块 Range Deletion Block

范围删除块包含文件中key与序列号中的删除范围。在读请求下发到sst的时候能够从sst中的指定区域判断key是否在deleterange 的范围内部存在则直接返回NotFound。memtable中也有一块区域实现同样的功能。

compaction或者flush的时候会清除掉过时的tombstone数据。

属性块 Properties Block

包含属性信息。

统计块格式

 [prop1] 每个property都是一个键值对     [prop2] ... [propN]

属性信息保证顺序且没有重复默认情况下包含了以下信息

 data size               // data block总大小 index size              // index block总大小 filter size             // filter block总大小 raw key size            // 所有key的原始大小 raw value size          // 所有value的原始大小 number of entries number of data blocks

优化

RocksDB优化的演变进程

优化写放大 Log-Structure Merge Tree空间放大 compaction操作减少compaction带来的cpu负载优化lsm控制压缩频率粒度cpu、ssd资源平衡拆分存储使用远程存储hdfs、s3、oss

写放大

RocksDB早起专注于通过节省闪存的擦除周期来减小写入放大。写放大主要出现在两个层面

1、SSD本身引入的写入放大放大范围在1.1~3

2、存储和数据库软件也会产生写放大有时会高达100eg当100bytes的变更导致4kB/8KB/16KB的page被写出

Leveled Compaction通常会带来10-30之间的写入放大在大多数情况下比B-trees要低但对于写敏感的应用来说还是太高。

所以有了Tiered Compaction牺牲了读性能将写放大减小到4-10之间。数据写入速率高的场景使用Tiered Compaction这类压缩策略减少写入放大

写入速率偏低的场景使用Leveled Compaction这类策略减少空间使用和提高读取效率。

写放大对写入速率的影响

空间放大

后续对大多数程序的观察可知闪存的写入周期与写入开销都没有受到约束IO负载远低于SSD能提供的能力。

空间的利用率变得比写放大更重要因此开始对磁盘空间进行优化。

得益于LSM-trees结构的非碎片化数据布局其对于磁盘空间优化也能起到有效作用。可以通过减少LSM-trees中的脏数据delete/overwrite来优化Leveled-Compaction。

因此有了新的数据压缩策略

Dynamic Leveled Compaction每一层的数据大小根据上一层的实际大小动态调整实现比Leveled Compaction更好更稳定的空间效率

右下图测试数据所示Leveled Compaction使用25.6%的空间而Dynamic Leveled Compaction策略只需要12.4%。

极端情况下Leveled Compaction的磁盘使用会高达90%而Dynamic Leveled Compaction依旧能保持在相对稳定的范围。

恒定2MB/s写入速率下两种压缩策略的空间使用与数据大小

CPU利用率

减少CPU负载可以提高少数受CPU限制的应用性能。更重要的是减少CPU开销能够节省硬件成本。

早期降低CPU开销的方式包括引入前缀布隆过滤器、在索引查询之前应用布隆过滤器、优化布隆过滤器

适应新的硬件技术

SSD与SSD相关的架构改进可能会影响RocksDB。例如open-channel SSDsmulti-stream和SSDZNS都承诺改善查询延迟并节省闪存擦除周期。

由于大部分使用RocksDB的软件受限于磁盘空间而不是擦除周期和延迟这种新技术变更只会对小部分使用RocksDB的软件有性能提升。

让RocksDB直接适应新的硬件技术将会对RocksDB的一致性体验带来挑战。目前社区对存储计算这方面还没有研究与优化规划。

Disaggregated (remote) storag 远程存储是目前的优先事项。目前的优化都是预设闪存在本机环境然而现在的网络已经允许支撑更多的远程I/。

因此对越来越多的程序来说支持远程存储的RocksDB性能变得越来越重要。使用远程存储可以按需配置能更容易重复利用CPU与SSD资源。

目前针对分离存储的优化有整合&并行化I/O来优化I/O延迟、将QoS需求传递到底层系统、报告分析信息

Storage Class MemorySCM存储级内存即既具有memory的优势又兼顾了storage的特点。目前有几种应用设想

SCM做为内存拓展涉及到如何设计贴合两种存储的数据结构SCM做为db主要存储将SCM应用于WAL

Rocksdb在大型系统上的使用优化 键-值接口

几乎所有存储工作负载都可以由具有KV API的数据存储提供服务。KV 接口是通用的。

键和值都是由可变长的字节数组构成应用程序负责解析和解释键和值可以自由选择将哪些信息打包到key value中包括编码方案。

KV 接口的另一个好处就是便携性键值系统之间的数据迁移更为容易。

然而KV 接口会限制某些程序的性能。例如在RocksDB之外构建并发控制很难有高效的性能特别是需要支持两阶段提交的场景在提交事务之前需要持久化一些数据因此RocksDB提供了事务支持。

版本与时间戳

数据的版本控制非常重要。版本信息是RocksDB中的第一物件以便正确支持多版本并发控制MVCC、时间点读取等特性。

RocksDB也需要支持对不同版本的高效访问。

目前RocksDB内部使用56位序列号识别不同版本的键值对。序列号由RocksDB生成每次客户端写入时递增因此所有数据都按逻辑顺序排列。

RocksDB允许应用程序对数据库进行快照RocksDB保证快照时存在的所有键值对将持续存在直至程序明确释放快照因此具有相同key的多个键值对可以共存由它们的序列号区分。

这种版本控制方式也有局限性无法满足许多程序的要求。

因为没有API指定时间点RocksDB不支持创建过去的快照。并且支持时间点读取效率低下每个RocksDB实例维护自己的序列号也只能在每个实例的基础上获取快照。导致多数据分片的程序版本控制复杂度增高。提供跨分片一致性读取的数据版本基本上是不可能的。

应用程序可以通过在key/value中编码写入时间错解决局限性。不过这种方式会导致性能下降key中编码会牺牲 点查寻的性能key变大

value中编码会牺牲会牺牲同一key乱序写入的性能并使旧版本key读取复杂化解码value比较时间戳。让应用程序指定时间戳的方式可以更好解决这些限制应用程序可以在key/value之外用全局时间戳标记数据。

资源管理

对于大型的分布式数据服务常常将数据划为多个分片分布在多个节点存储。一个单独的 RocksDB 实例用于为每个分片提供服务。

这意味着主机上将运行许多 RocksDB 实例。这些实例可以全部运行在一个单一的地址空间中也可以每个都运行在自己的地址空间中。

一、RocksDB需要对资源进行有效管理以保证它们被有效应用。在单进程模式下运行时需要具备全局资源限制能力资源包括

内存用于write buffer、block cache压缩I/O带宽线程用于压缩磁盘资源文件删除率RocksDB 允许应用程序为每种类型的资源创建一个或多个资源控制器支持RocksDB实例之间的优先级排序以确保资源优先用于最需要它的实例。

二、多实例的使用方式下不限制地使用非线程池化的线程会出现问题。线程过多会增加CPU负载的概率导致过多的上下文切换开销并使调试变得极其困难并且会增加I/O负载。RocksDB最好使用可以轻松限制大小和资源使用量的线程池。

三、每个分片只有本地信息当 RocksDB 实例在单独的进程中运行时全局资源管理更具挑战性有两种应对策略

使用保守的资源策略例如降低压缩频率这种策略的缺点是全局资源可能没有被充分利用

实例之间共享资源使用信息并相应地进行调整以尝试更全局地优化资源使用。这种需要做更多的工作来改进 RocksDB 中主机范围的资源管理

WAL处理

传统数据库倾向于在每次写入操作时强制写入预写日志 (WAL) 以确保持久性。而大规模分布式存储系统通常为了性能和可用性而复制数据并且它们具有各种一致性保证。

因此提供选项来调整WAL同步行为以满足不同应用程序的需求是很有帮助的。

具体来说RocksDB引入了差异化的 WAL 操作模式(1) 同步 WAL 写入 (2) 缓冲 WAL 写入 (3) 无 WAL 写入。对于缓冲的 WAL 处理WAL 会在后台以低优先级定期写入磁盘以免影响 RocksDB 的流量延迟

限制文件删除速度

RocksDB 通常通过文件系统与底层存储设备交互文件系统对是闪存SSD是有感知的。ssd上文件的删除可能会触发SSD的内部垃圾收集导致大量数据移动并对 IO 延迟产生负面影响。

引入了文件删除速率限制以防止同时删除多个文件压缩过程中

数据格式兼容

磁盘上的数据在不同软件版本之间保持向后和向前兼容非常重要。

配置管理

RocksDB 是高度可配置的因此应用程序可以针对其工作负载进行优化。然而配置管理是一个挑战

早期的配置继承自LevelD大量配置与代码耦合。RocksDB对其配置方式进行了调整与更新。

QA

Q: MemTable为什么用跳表不用平衡树

A: 1. 跳表实现比树简洁; 2. 空间占用小除了数据外其他都是指针; 3. 数据有序利于范围查询。

Q: MySQL 为什么用B trees不用跳表

A: 1、B树的页天生就与磁盘块对应对磁盘更友好而跳表基于链表实现数据物理分布比较分散对I/O不友好

2、跳表无法实现聚集索引和覆盖索引 3、数据分散无法利用磁盘预读对磁盘缓存不友好

。总之就是跳表设计简单不贴合磁盘特性适合内存使用。

参考文档

Evolution of Development Priorities in Key-value Stores Serving Large-scale Applications: The RocksDB Experience

RocksDB Wiki