在某些场景, 特别是一次性删除大量的连续 key 的情况下, LevelDB 的 Seek() 操作将变得特别慢. 我在源码中打点, 简单分析了其出现的原因.
首先, LevelDB 对 Delete 操作处理, 是将被删除的 Key 做标记, 并在未来某个时间将真正的数据和这个标记从硬盘上删除. 在真正的删除之前, 标记本身也会排序(即 key-type)存储在 sst 文件中.
所以, 如果删除大量的连续 key, 那么这些 key 会聚集在一起, 存储在某个 sst 文件中. 当 Seek() 操作时, 会定位到这个 sst 文件头部, 然后开始扫描, 跳过所有标记, 直到找到非标记的 key. 显然, 跳过的 key 越多, 耗时就越长. 而一个 sst 可能存储几十万个 key 标记, 这样操作就是秒级别, 甚至是数秒级别! 而且 CPU 占用是 100%.
对应的源码在 db_iter.cc 中:
void DBIter::FindNextUserEntry(bool skipping, std::string* skip) {
// Loop until we hit an acceptable entry to yield
do {
ParsedInternalKey ikey;
if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
switch (ikey.type) {
case kTypeDeletion:
// Arrange to skip all upcoming entries for this key since
// they are hidden by this deletion.
SaveKey(ikey.user_key, skip);
skipping = true;
break;
case kTypeValue:
if (skipping &&
user_comparator_->Compare(ikey.user_key, *skip) <= 0) {
// Entry hidden
} else {
valid_ = true;
saved_key_.clear();
return;
}
break;
}
}
iter_->Next();
} while (iter_->Valid());
}
其中, case kTypeDeletion 分支就是跳过删除标记. 这个缺陷目前来看, 是无法解决的, 只能期待 compaction 把这些 obsoleted 的数据真正地从硬盘上删除.
另一种方案是重新设计数据结构, 把删除标记分开存储, 这样就可以快速的跳过, 而不用扫描遍历.
Loading ...