CockroachDB 存储引擎RocksDB介绍(四)

在上一篇存储引擎介绍中,我们解析了CockroachDB(以下简称CRDB)底层集成的高性能存储引擎RocksDB如何通过WriteBatch实现数据写入的功能,以及如何高效地封装RocksDB的WriteBatch,通过减少CGO开销实现更加高性能的DBBatch操作。而在本篇我们将介绍RocksDB中的数据删除的相关内容,以及CockroachDB如何使用封装并使用RocksDB的删除接口。

TIPS:  

 以下内容基于CockroachDB v2.0.3版本,集成的RocksDB版本为v5.13.4。

Delete操作介绍

 

在RocksDB中,数据删除操作在处理逻辑上与数据写入操作类似,在底层也是通过WriteBatch以键值对的形式封装,提交,再通过WriteGroup并发处理机制写入MemTable当中,并最终随着MemTable持久化到SSTable文件中。具体地,跟数据删除相关的ValueType类型主要有:

  • kTypeDeletion:用于删除默认ColumnFamily(default)上的单个键值对。
  • kTypeColumnFamilyDeletion:用于删除默认ColumnFamily以外的其他ColumnFamily 上的单个键值对,与kTypeDeletion不同的是需要额外存储删除操作对应ColumnFamily的ID。
  • kTypeRangeDeletion:用于删除默认ColumnFamily(default)上的、指定起始和终止Key值的范围内的所有键值对。
  • kTypeColumnFamilyRangeDeletion:用于删除默认ColumnFamily以外的其他ColumnFamily 上的、指定起始和终止Key值的范围内的所有键值对,与kTypeRangeDeletion不同的是需要额外存储删除操作对应ColumnFamily的ID。
  • kTypeSingleDeletion:用于删除默认ColumnFamily(default)上的、单个键值对数据的特殊删除操作,只删除最新版本的键值对数据,适用于键值对Key值唯一的场景。
  • kTypeColumnFamilySingleDeletion:用于删除默认ColumnFamily以外的其他ColumnFamily 上的、单个键值对数据的特殊删除操作,需要额外存储删除操作对应ColumnFamily的ID。

出于场景与性能的考虑,当前CRDB目前涉及到的ValueType类型只有kTypeDeletion和kTypeRangeDeletion,以下将进一步地介绍这两种类型的删除操作。

kTypeDeletion

 

用于单个键值对的删除。ValueType类型为kTypeDeletion的键值对与普通数据的键值对一样,通过WriteBatch和MemTableInserter插入到MemTable当中,最终持久化到SSTable的数据块当中(默认SSTable文件格式为BlockBasedTable类型)。

在查找指定Key值对应Value值的时候:

  • 用户直接通过Get方法读取: 

    执行Get方法时会创建GetContext对象,缓存自上而下获取指定Key值对应的Value值时可能的多版本数据内容,例如kTypeMerge类型、需要合并的多版本数据。如果Get方法在上层查找到指定Key值对应的kTypeDeletion类型的数据版本,则停止向下查找的过程,返回Value值不存在的查找结果。
  • 用户通过迭代器DBIter读取: 

    迭代器DBIter会将同一个Key值的多版本数据按键值对的序列号大小读取并进行处理,如果读取到的相对于迭代器“当前序列号”为最新的数据版本为kTypeDeletion类型,则会跳过掉该Key值所对应的所有Value值,查找下一个Key值。
  • Compaction任务通过CompactionIterator迭代器读取: 

    Compaction任务用于合并多个SSTable文件中的多版本数据,减少文件数量并回收多余的存储空间。在没有快照、迭代器等因素锁定特定版本的数据的情况下,kTypeDeletion类型的数据与kTypeValue类型的普通数据一样,CompactionIterator根据序列号的大小,只保留最新版本的数据并作为迭代器的输出。

https://mmbiz.qpic.cn/mmbiz_png/xoB0BH4icmV4Ug3UOFJGBRDyWU8uJ2YjSxx24HAkUEco3PIq8I17oxutXFxIndvia1haicNricdyhpvEt22MYGhwEg/640?wx_fmt=png

CompactionIterator处理kTypeDeletion数据

kTypeDeletion类型的键值对数据,最终会通过Compaction任务回收,有三种情况:一是在多版本数据的合并中被过滤,二是在合并到LSM结构中最底层的SSTable文件的时候被删除,三是在该kTypeDeletion类型的Key值不包含于下层任意SSTable文件的Key值范围的时候,被判为不必要的内容而提早删除。

kTypeRangeDeletion

 

DeleteRange是RocksDB提供的一个范围删除的接口,用于删除指定startKey、endKey之间的键值数据。与kTypeDeletion类型的类似,在底层处理时以键值对的形式(ValueType为kTypeRangeDeletion,Key为startKey,Value为endKey),通过WriteBatch和MemTableInserter插入到MemTable当中。区别于kTypeDeletion类型数据和普通数据,范围删除的键值对单独存储在MemTable中额外的range_del_table_结构里。

https://mmbiz.qpic.cn/mmbiz_png/xoB0BH4icmV4MnP1dia7sABN95dkxrNdVibIq7uakZnicDMJjbAzuXqYR2AWpruOZ5YslNVJRLhdtYzAWYZqic90KHw/640?wx_fmt=png

kTypeRangeDeletion类型键值对编码

  • 在执行Flush任务持久化MemTable的时候,DeleteRange键值对将区别于普通数据,以元数据的形式存储在RangeDelBlock中,同时更新SSTable元数据中的Key值范围和seqnumber值范围。

https://mmbiz.qpic.cn/mmbiz_png/xoB0BH4icmV4MnP1dia7sABN95dkxrNdVibcH2pgqQCxAodQCmvbhp4U6blRdHkQfpI1pC1EIfSpqpC73sP4Z7QKw/640?wx_fmt=png
 

BlockBasedTable文件格式

  • 在查找指定Key值对应Value值的时候,每次Get方法调用或是DBIter迭代器在内部都会新建一个range_del_agg聚合器,用于在查找数据的过程中缓存范围删除的信息。具体地,如果数据查询过程中需要读取某个SSTable文件里的数据,则在打开该SSTable文件时会将可能存在的RangeDelBlock加载进入BlockCache当中。该文件的TableReader调用Get方法获取SSTable中指定key值对应value值之前(或是构造TableIterator迭代器的时候),RocksDB会获取先前在BlockCache中缓存的RangeDelBlock块,解析出一批范围删除的元信息,加载到range_del_agg聚合器。而在TableReader执行Get方法(或是遍历迭代器的时候),通过range_del_agg聚合器能够查找出指定key值是否被“范围删除”。若是,则过滤掉查找到的结果。否则正常输出查找内容。
  • 在执行Compaction任务的时候,所有的SSTable输入文件将会构造用于遍历文件数据的Table迭代器,组成特殊迭代器CompactionIterator,过程中DeleteRange元数据会添加到range_del_agg聚合器当中。CompactionIterator根据range_del_agg聚合器过滤掉被删除的键值对数据。同时在Compaction任务结束的时候,所有的SSTable输出文件会根据当前文件数据的Key值范围[lower_bound, upper_bound)逐一对重叠的DeleteRange元数据{[StartKey, EndKey)}进行裁剪,得到{[max{StartKey, lower_bound}, min{EndKey, upper_bound})},持久化到自己的RangeDelBlock中。

CRDB的数据删除

 

上面已经提到,CRDB中数据删除操作跟数据写入操作一致,最终都是在RocksDB层通过WriteBatch实现。在CRDB层基本都是通过DBBatch来操作底层存储引擎,通过Clear方法删除单个键值对,通过ClearRange方法进行范围删除,通过ClearIterRange方法遍历迭代器内指定范围内的键值对并依次删除。

特别地,在Range Rebalance、表删除、表清空、Raft日志大量清理等场景下,涉及比较大范围的存储空间,需要尽早回收,而单纯依赖RocksDB自身的后台Compaction任务无法及时回收空间。最极端的情况是一些存储在LSM最底层的静态Range数据需要范围删除的元信息数据,从最顶层一直“传递”到最底层触发对应Compaction,才能回收空间。因此CRDB在调用ClearRange方法以后,会向运行在每个Store上的后台Compactor定时器,建议一次范围Compaction任务(以键值对记录在存储引擎中防止任务丢失)。

考虑到范围Compaction是一个比较重的操作,很可能阻塞L0层到L1层的Compaction任务导致RocksDB进入Stall状态影响存储引擎整体的性能,CRDB对于ClearRange方法的调用场景进行了必要的评估,在小数据量的场景使用ClearIterRange方法替代。同时CRDB对于范围Compaction任务根据从RocksDB获取到的各层文件的元信息(主要涉及文件Key值范围),对缓存任务列表中的任务进行评估、聚合与规模约束。

https://mmbiz.qpic.cn/mmbiz_png/xoB0BH4icmV4Ug3UOFJGBRDyWU8uJ2YjS21jlmQqt4MNuRyVLgDJ7JYPjWMA57YwnDbJfM6qg6kVib9VzD4hMz1w/640?wx_fmt=png

Admin界面定制化图表 – 节点2退役时Range迁移触发大量SuggestionCompaction任务

结  语

本文主要介绍了RocksDB中删除数据相关的接口和细节实现,主要涉及kTypeDeletion和kTypeRangeDeletion类型的删除操作。在第二章介绍了CRDB在CGO友好的DBBatch基础上,在合适的场景调用Clear、ClearRange和ClearIterRange方法,操作底层存储引擎进行数据管理,删除不必要的数据。

参考资料:

https://github.com/facebook/rocksdb  
https://github.com/cockroachdb/cockroach  
http://catkang.github.io/2017/01/17/leveldb-data.html  
https://github.com/cockroachdb/cockroach/issues/24029
 

https://www.cockroachlabs.com/docs/stable/admin-ui-custom-chart-debug-page.html#available-metrics