文章目录
- 1. 基本介绍
- 2. 两种接口使用及简单性能对比
- 3. DeleteRange 的基本实现
- 3.1 写流程的实现
- 3.2 读流程的实现 -- skyline算法
以下涉及到的代码都是基于rocksdb 6.4.0版本进行描述的
1. 基本介绍
DeleteRange
接口的设计是为了代替传统的删除一个区间[start,end) 内的key-value的接口
Slice start, end;
// set start and end
auto it = db->NewIterator(ReadOptions());
for (it->Seek(start); cmp->Compare(it->key(), end) < 0; it->Next()) {
db->Delete(WriteOptions(), it->key());
} 但是这样的实现会有一些问题，它的删除逻辑是先使用迭代器查找，再进行Delete(本质上还是写，将一个Delete type的key写入)，而且这个过程也不是原子操作。所以，这样的接口实现对与写性能要求比较高的场景会严重降低系统性能。
同时删除一段区间内的key 这样的操在很多系统中都很常见，很多数据库系统都会在多主键的基础上构建其schema，这一些主键拥有相同的公共前缀，用来加速查找和压缩存储数据。所以删除操作在存储引擎这里就是删除一段区间内的key。
像MyRocks作为一种MySQL的存储引擎，其内部会用每一个key的前四个字节标识其所属的表或者索引，当删除一个表或者一个索引的时候，在存储引擎这里就是删除一段区间。
同时还有Cassandra的Rockssandra的存储引擎，Marketplace使用的Rocksdb都是这样的实现，那么
DeleteRange
接口的推出就是自然而然了，需要保证写性能的同时不能降低读性能。
Slice start, end;
// set start and end
db->DeleteRange(WriteOptions(), start, end); 2. 两种接口使用及简单性能对比
在介绍实现原理之前，我们可以先看看怎么使用，以及使用之后相比于传统的删除接口的性能差异有多少
基本接口使用
#include <iostream>
#include <string>
#include <rocksdb/db.h>
#include <rocksdb/iterator.h>
#include <rocksdb/table.h>
#include <rocksdb/options.h>
#include <rocksdb/env.h>
#include <ctime>
using namespace std;
//生成随机key
static string rand_key(unsigned long long key_range) {
char buff[30];
unsigned long long n = 1;
for (int i =1; i <= 4; ++i) {
n *= (unsigned long long ) rand();
}
sprintf(buff, "%llu", n % key_range);
string k(buff);
return k;
}
int main() {
rocksdb::DB *db;
rocksdb::Options option;
option.create_if_missing = true;
option.compression = rocksdb::CompressionType::kNoCompression;
//创建db
rocksdb::Status s = rocksdb::DB::Open(option, "./iterator_db", &db);
if (!s.ok()) {
cout << "Open failed with " << s.ToString() << endl;
exit(1);
}
rocksdb::DestroyDB("./iterator_db", option);
//写入
for(int i = 0; i < 5; i ++) {
rocksdb::Status s = db->Put(rocksdb::WriteOptions(),
rand_key(9), string(10, 'a' + (i % 26)) );
if (!s.ok()) {
cout << "Put failed with " << s.ToString() << endl;
exit(1);
}
}
//先遍历一遍写入的key-value
cout << "after put , seek all keys :" << endl;
rocksdb::ReadOptions read_option;
auto it=db->NewIterator(read_option);
for (it->SeekToFirst(); it->Valid(); it->Next()) {
cout << it->key().ToString() << " " << it->value().ToString() << endl;
}
//删除从[2,5)之间的key
rocksdb::Slice start("2");
rocksdb::Slice end("5");
s = db->DeleteRange(rocksdb::WriteOptions(),db->DefaultColumnFamily(), start.ToString(), end.ToString());
assert(s.ok());
//遍历删除之后的key-value
cout << "after DeleteRange from 2-5 , seek all keys :" << endl;
it = db->NewIterator(read_option);
for (it->SeekToFirst(); it->Valid(); it->Next()) {
cout << it->key().ToString() << " " << it->value().ToString() << endl;
}
db->Close();
delete db;
return 0;
} 输出如下:
after put , seek all keys :
3 cccccccccc
4 dddddddddd
7 bbbbbbbbbb
8 eeeeeeeeee
after DeleteRange from 2-5 , seek all keys :
7 bbbbbbbbbb
8 eeeeeeeeee 我们接下来看看两个接口的性能差异：
在代码deleteRange 逻辑前后增加时间戳，打印一下消耗时间
string start("1000");
string end("5000");
ts = clock();
for(it ->Seek(start); it->Valid() && it->key().ToString() < end; it->Next()) {
db->Delete(rocksdb::WriteOptions(), it->key());
}
//s = db->DeleteRange(rocksdb::WriteOptions(),db->DefaultColumnFamily(), start.ToString(), end.ToString());
assert(s.ok());
cout << "Old Delete Range use " << clock() - ts << endl; 两者最后的时间差异对比如下:
DeleteRange use 30us
Old Delete Range use 193519us 当然我这个测试并不严谨，仅仅是删除4000个key，且没有读写混合。但是对照组只有这两个接口，其他的环境，基本配置，写入的数据量都是一样的，且反复跑了多次，其实是能够说明这个接口效率的提升的。
社区有更加严谨的benchmark测试
3. DeleteRange 的基本实现
3.1 写流程的实现
之前我们描述Rocksdb 事务的基本实现中，有说过Rocksdb事务的写实现是通过writebach的方式，同样为了保证DeleteRange的一致性，会将其通过
WriteBatch
保存其
range tombstone
（即删除的key的区间），然后按照writebatch的写流程进行写入，WriteBatch的写入可以参考 图3.1。
- 为了保证读性能，写memtable的过程会为该
range tombstone
range tombstone
Not Found
- 写入SST的时候，sst为其同样预留了一段专门的存储区域
range tombstone block
，这个block属于元数据的block。也是为了在读请求下发到sst的时候能够从sst中的指定区域判断key是否在deleterange 的范围内部。
参考 图3.2
- compaction或者flush的时候会清除掉过时的tombstone数据（当该sst携带的tombstone到达最LSM tree最底层的时候认为存储的tombstone已经过时，此时会将其清除掉；或者当前的key之前的版本没有snapshot引用，则同样可以被清除）
图3.1 writebatch 写入
图3.2 writebach写入memtable和sst，为tombstone生成独立的memtable
最终在SST中的存储格式为一个单独的range tombstone block，关于sst文件详细格式可以看考sst文件详细格式,这里借用官方的图来描述
蓝色区域数据MetaBlock，而range tombestone 作为其中的一个元数据区域进行存储。
写入tombestoe的具体代码实现如下:
- 通过DeleteRange接口，调用到DeleteRangeCF --> DeleteImpl --> mm->add ，通过memtable 的add函数将range tombstone加入自己的memtable（默认还是通过skiplit 实现的管理结构），关于rocksdb的跳表的实现可以参考
inlineskiplist.h
InlineSkipList<Comparator>::Insert
函数。
Memtable 的add函数内部实现如下:
bool MemTable::Add(SequenceNumber s, ValueType type,
const Slice& key, /* user key */
const Slice& value, bool allow_concurrent,
MemTablePostProcessInfo* post_process_info, void** hint) {
......
//根据传入的valueType分配对应的memtable，这里就是为range delete分配属于它的memtable
//我们默认的memtable 的管理数据结构是跳表
std::unique_ptr<MemTableRep>& table =
type == kTypeRangeDeletion ? range_del_table_ : table_;
KeyHandle handle = table->Allocate(encoded_len, &buf);
......
//通过在如下函数中调用跳表的insert函数将其插入到table之中(这个版本6.4.6默认开启并发写memtable)
bool res = (hint == nullptr)
? table->InsertKeyConcurrently(handle)
: table->InsertKeyWithHintConcurrently(handle, hint);
if (UNLIKELY(!res)) {
return res;
}
} -
写入到memtable之后，会到DeleteImpl之中调用CheckMemtableFull函数，尝试flush range tomstone的 memtable。此时也就进入range tombstone的第二阶段，写入sst文件，并参与compaction。
我们直接进入到compaction真正进行计算并写入到sst文件的核心函数
ProcessKeyValueCompaction
- 所以该函数针对range tombstone的处理就是一开始就需要先收集之前sst文件的range tombstone数据。通过构建通用的迭代器MakeInputIterator的过程中调用CompactionRangeDelAggregator::AddTombstones函数来完成compaction时访问range tombstone的迭代器构建。
void CompactionJob::ProcessKeyValueCompaction(SubcompactionState* sub_compact) {
......
CompactionRangeDelAggregator range_del_agg(&cfd->internal_comparator(),
existing_snapshots_);
// 通过迭代器，添加tombstones,构建好的key 底层迭代器就是一个最小堆，这个函数内部还会完成针对所有key的最小堆的构建。
std::unique_ptr<InternalIterator> input(versions_->MakeInputIterator(
sub_compact->compaction, &range_del_agg, env_options_for_read_)); -
后续compaction的过程中，调用c_iter->SeekToFirst(); 以及c_iter->Next()，控制迭代器的移动。同时，内部实现会处理Range tombstone。他们都会调用同一个函数CompactionIterator::NextFromInput() ，当一个internal key处理完成之后需要从内部重新调整此时参与compation的key数据(遍历的方式)，能够删除的需要清除，能够合并的需要合并。
这里针对NextFromInput函数中处理 Range tombstone的部分主要有两个地方
- 处理的key的type是merge的时候，需要将当前key的历史seq都进行合并，合并的时候也会处理range tombstone
- 当key的type是 新的Put的时候，则同样可以清除之前所有的tombstone
第一个逻辑我们需要进入函数MergeUntil，根据合并后的结果调用range_del_agg->ShouldDelete函数，确认当前key是否能从range tombstone删除。合并操作会将当前internal key对应的历史版本进行合并，包括put/delete
a. 如果这个时候当前key之前的版本没有被快照引用，那么对于deleterange来说就可以删除掉了。
b. 如果当前key是put,且当前internal key的低版本key在tombstone中，那么低版本的key也能够被tomestone跳过
//MergeUntil 函数清理range_del_agg
const Slice val = iter->value();
const Slice* val_ptr;
if (kTypeValue == ikey.type &&
(range_del_agg == nullptr ||
!range_del_agg->ShouldDelete(
ikey, RangeDelPositioningMode::kForwardTraversal))) {
val_ptr = &val;
} else {
val_ptr = nullptr;
}
// 详细的清理过程如下,默认是Forward的方式进行遍历
bool ForwardRangeDelIterator::ShouldDelete(const ParsedInternalKey& parsed) {
// Move active iterators that end before parsed.
//如果迭代器中已经保存的key比当前解析的key版本还低，即tombstone保存的key版本低。
while (!active_iters_.empty() &&
icmp_->Compare((*active_iters_.top())->end_key(), parsed) <= 0) {
TruncatedRangeDelIterator* iter = PopActiveIter();//从binary_heap维护的迭代器中移除顶部的元素，并重构内部的二分堆
do {
iter->Next();
} while (iter->Valid() && icmp_->Compare(iter->end_key(), parsed) <= 0);
PushIter(iter, parsed);
assert(active_iters_.size() == active_seqnums_.size());
}
// Move inactive iterators that start before parsed.
while (!inactive_iters_.empty() &&
icmp_->Compare(inactive_iters_.top()->start_key(), parsed) <= 0) {
TruncatedRangeDelIterator* iter = PopInactiveIter();
while (iter->Valid() && icmp_->Compare(iter->end_key(), parsed) <= 0) {
iter->Next();
}
PushIter(iter, parsed);
assert(active_iters_.size() == active_seqnums_.size());
}
return active_seqnums_.empty()
? false
: (*active_seqnums_.begin())->seq() > parsed.sequence;
} 第二个逻辑则就比较简单了，当前key是put的时候，可以直接将当前key之前所有的tombstone都清除掉
// 1. new user key -OR-
// 2. different snapshot stripe
bool should_delete = range_del_agg_->ShouldDelete(
key_, RangeDelPositioningMode::kForwardTraversal);
if (should_delete) {
++iter_stats_.num_record_drop_hidden;
++iter_stats_.num_record_drop_range_del;
input_->Next();
} else {
valid_ = true;
} - 接下来回到
ProcessKeyValueCompaction
逻辑中，c_iter->SeekToFirst(); 以及c_iter->Next()的逻辑是将能够删除的tombstone清理掉，实际上还有一些场景无法清理。
比如：ikey1(internal key1) 是range delete,但是之前的版本中有snapshot引用，则此时无法清理掉该tombstone
此时需要将该key写入到tombstone对应的sst metadata 区域,进行固化
// ProcessKeyValueCompaction 函数之中
while (status.ok() && !cfd->IsDropped() && c_iter->Valid()) {
// Invariant: c_iter.status() is guaranteed to be OK if c_iter->Valid()
// returns true.
const Slice& key = c_iter->key();
const Slice& value = c_iter->value();
......
sub_compact->builder->Add(key, value); //内部写入tombstone对应的builder之中 当compaction中builder添加的key+value size大小超过了Max_output_size的时候则会触发一次FinishCompactionOutputFile，通过这个函数进一步进行range tombstonde的固化逻辑，最终通过builder->Finish()函数写入tombstonde的block之中
// ProcessKeyValueCompaction函数之中
if (sub_compact->compaction->output_level() != 0 &&
sub_compact->current_output_file_size >=
sub_compact->compaction->max_output_file_size()) {
// (1) this key terminates the file. For historical reasons, the iterator
// status before advancing will be given to FinishCompactionOutputFile().
input_status = input->status();
output_file_ended = true; //标记可以进行ouput到文件里了
}
if (output_file_ended) {
const Slice* next_key = nullptr;
if (c_iter->Valid()) {
next_key = &c_iter->key();
}
CompactionIterationStats range_del_out_stats;
//此时可以将累计的key+value固化到对应的sst结构中
status =
FinishCompactionOutputFile(input_status, sub_compact, &range_del_agg,
&range_del_out_stats, next_key);
} builder->Finish()函数实现:
Status BlockBasedTableBuilder::Finish() {
Rep* r = rep_;
assert(r->state != Rep::State::kClosed);
bool empty_data_block = r->data_block.empty();
.......
WriteRangeDelBlock(&meta_index_builder);
} 最终，需要被清理的range tombstone被清理了。无法被清理的，则会被写入到下一个sst文件中的tombstone block之中，等待之后的清理。
3.2 读流程的实现 – skyline算法
Rocksdb的读流程，拿到一个读请求，如果是同一个事务内部的读，则会先从该事务对应的writebatch中读；如果是非事务，则读的顺序是memtable，immutable memtable ，table cache，SSTs。
如之前我们通过迭代器访问db中的数据时，本身逻辑就是完整的读流程。而且实际的生产环境中，通过迭代器进行访问居多，因为迭代器提供了不同方式的访问逻辑。
为了提升读性能，快速定位到一个key是否在range tombstone区间之中，这里针对迭代器进行了优化。在memtable,immu,table cache, sst的 range tombstone的路径之上构造一个skyline，skyline能够提供包含所有路径中的tombstone的全集，而且是有序的，这样只需要通过高效的二分查找来确定一个key是否在range tombstone之间。构建过程如 图3.2.1