LevelDB Seek() 特别慢的场景

在某些场景, 特别是一次性删除大量的连续 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 的数据真正地从硬盘上删除.

另一种方案是重新设计数据结构, 把删除标记分开存储, 这样就可以快速的跳过, 而不用扫描遍历.