LevelDB读取
LevelDB读取
数据的读取
从 LevelDB 中读取数据其实并不复杂,memtable 和 imm 更像是两级缓存,它们在内存中提供了更快的访问速度,如果能直接从内存中的这两处直接获取到响应的值,那么它们一定是最新的数据。
LevelDB 总会将新的键值对写在最前面,并在数据压缩时删除历史数据。
数据的读取是按照 MemTable、Immutable MemTable 以及不同层级的 SSTable 的顺序进行的,前两者都是在内存中,后面不同层级的 SSTable 都是以 *.ldb
文件的形式持久存储在磁盘上,而正是因为有着不同层级的 SSTable,所以我们的数据库的名字叫做 LevelDB。
精简后的读操作方法的实现代码是这样的,方法的脉络非常清晰,作者相信这里也不需要过多的解释:
Status DBImpl::Get(const ReadOptions& options, const Slice& key, std::string* value) {
LookupKey lkey(key, versions_->LastSequence());
if (mem_->Get(lkey, value, NULL)) {
// Done
} else if (imm_ != NULL && imm_->Get(lkey, value, NULL)) {
// Done
} else {
versions_->current()->Get(options, lkey, value, NULL);
}
MaybeScheduleCompaction();
return Status::OK();
}
C++
当 LevelDB 在 memtable 和 imm 中查询到结果时,如果查询到了数据并不一定表示当前的值一定存在,它仍然需要判断 ValueType
来确定当前记录是否被删除。
多层级的 SSTable
当 LevelDB 在内存中没有找到对应的数据时,它才会到磁盘中多个层级的 SSTable 中进行查找,这个过程就稍微有一点复杂了,LevelDB 会在多个层级中逐级进行查找,并且不会跳过其中的任何层级;在查找的过程就涉及到一个非常重要的数据结构 FileMetaData
:
FileMetaData
中包含了整个文件的全部信息,其中包括键的最大值和最小值、允许查找的次数、文件被引用的次数、文件的大小以及文件号,因为所有的 SSTable
都是以固定的形式存储在同一目录下的,所以我们可以通过文件号轻松查找到对应的文件。
查找的顺序就是从低到高了,LevelDB 首先会在 Level0 中查找对应的键。但是,与其他层级不同,Level0 中多个 SSTable 的键的范围有重合部分的,在查找对应值的过程中,会依次查找 Level0 中固定的 4 个 SSTable。
但是当涉及到更高层级的 SSTable 时,因为同一层级的 SSTable 都是没有重叠部分的,所以我们在查找时可以利用已知的 SSTable 中的极值信息 smallest/largest
快速查找到对应的 SSTable,再判断当前的 SSTable 是否包含查询的 key,如果不存在,就继续查找下一个层级直到最后的一个层级 kNumLevels
(默认为 7 级)或者查询到了对应的值。
SSTable 的『合并』
既然 LevelDB 中的数据是通过多个层级的 SSTable 组织的,那么它是如何对不同层级中的 SSTable 进行合并和压缩的呢;与 Bigtable 论文中描述的两种 Compaction 几乎完全相同,LevelDB 对这两种压缩的方式都进行了实现。
无论是读操作还是写操作,在执行的过程中都可能调用 MaybeScheduleCompaction
来尝试对数据库中的 SSTable 进行合并,当合并的条件满足时,最终都会执行 BackgroundCompaction
方法在后台完成这个步骤。
这种合并分为两种情况,一种是 Minor Compaction,即内存中的数据超过了 memtable 大小的最大限制,改 memtable 被冻结为不可变的 imm,然后执行方法 CompactMemTable()
对内存表进行压缩。
void DBImpl::CompactMemTable() {
VersionEdit edit;
Version* base = versions_->current();
WriteLevel0Table(imm_, &edit, base);
versions_->LogAndApply(&edit, &mutex_);
DeleteObsoleteFiles();
}
C++
CompactMemTable
会执行 WriteLevel0Table
将当前的 imm 转换成一个 Level0 的 SSTable 文件,同时由于 Level0 层级的文件变多,可能会继续触发一个新的 Major Compaction,在这里我们就需要在这里选择需要压缩的合适的层级:
Status DBImpl::WriteLevel0Table(MemTable* mem, VersionEdit* edit, Version* base) {
FileMetaData meta;
meta.number = versions_->NewFileNumber();
Iterator* iter = mem->NewIterator();
BuildTable(dbname_, env_, options_, table_cache_, iter, &meta);
const Slice min_user_key = meta.smallest.user_key();
const Slice max_user_key = meta.largest.user_key();
int level = base->PickLevelForMemTableOutput(min_user_key, max_user_key);
edit->AddFile(level, meta.number, meta.file_size, meta.smallest, meta.largest);
return Status::OK();
}
C++
所有对当前 SSTable 数据的修改由一个统一的 VersionEdit
对象记录和管理,我们会在后面介绍这个对象的作用和实现,如果成功写入了就会返回这个文件的元数据 FileMetaData
,最后调用 VersionSet
的方法 LogAndApply
将文件中的全部变化如实记录下来,最后做一些数据的清理工作。
当然如果是 Major Compaction 就稍微有一些复杂了,不过整理后的 BackgroundCompaction
方法的逻辑非常清晰:
void DBImpl::BackgroundCompaction() {
if (imm_ != NULL) {
CompactMemTable();
return;
}
Compaction* c = versions_->PickCompaction();
CompactionState* compact = new CompactionState(c);
DoCompactionWork(compact);
CleanupCompaction(compact);
DeleteObsoleteFiles();
}
C++
我们从当前的 VersionSet
中找到需要压缩的文件信息,将它们打包存入一个 Compaction
对象,该对象需要选择两个层级的 SSTable,低层级的表很好选择,只需要选择大小超过限制的或者查询次数太多的 SSTable;当我们选择了低层级的一个 SSTable 后,就在更高的层级选择与该 SSTable 有重叠键的 SSTable 就可以了,通过 FileMetaData
中数据的帮助我们可以很快找到待压缩的全部数据。
查询次数太多的意思就是,当客户端调用多次
Get
方法时,如果这次Get
方法在某个层级的 SSTable 中找到了对应的键,那么就算做上一层级中包含该键的 SSTable 的一次查找,也就是这次查找由于不同层级键的覆盖范围造成了更多的耗时,每个 SSTable 在创建之后的allowed_seeks
都为 100 次,当allowed_seeks < 0
时就会触发该文件的与更高层级和合并,以减少以后查询的查找次数。
LevelDB 中的 DoCompactionWork
方法会对所有传入的 SSTable 中的键值使用归并排序进行合并,最后会在高高层级(图中为 Level2)中生成一个新的 SSTable。
这样下一次查询 17~40 之间的值时就可以减少一次对 SSTable 中数据的二分查找以及读取文件的时间,提升读写的性能。
存储 db 状态的 VersionSet
LevelDB 中的所有状态其实都是被一个 VersionSet
结构所存储的,一个 VersionSet
包含一组 Version
结构体,所有的 Version
包括历史版本都是通过双向链表连接起来的,但是只有一个版本是当前版本。
当 LevelDB 中的 SSTable 发生变动时,它会生成一个 VersionEdit
结构,最终执行 LogAndApply
方法:
Status VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu) {
Version* v = new Version(this);
Builder builder(this, current_);
builder.Apply(edit);
builder.SaveTo(v);
std::string new_manifest_file;
new_manifest_file = DescriptorFileName(dbname_, manifest_file_number_);
env_->NewWritableFile(new_manifest_file, &descriptor_file_);
std::string record;
edit->EncodeTo(&record);
descriptor_log_->AddRecord(record);
descriptor_file_->Sync();
SetCurrentFile(env_, dbname_, manifest_file_number_);
AppendVersion(v);
return Status::OK();
}
C++
该方法的主要工作是使用当前版本和 VersionEdit
创建一个新的版本对象,然后将 Version
的变更追加到 MANIFEST 日志中,并且改变数据库中全局当前版本信息。
MANIFEST 文件中记录了 LevelDB 中所有层级中的表、每一个 SSTable 的 Key 范围和其他重要的元数据,它以日志的格式存储,所有对文件的增删操作都会追加到这个日志中。
SSTable 的格式
SSTable 中其实存储的不只是数据,其中还保存了一些元数据、索引等信息,用于加速读写操作的速度,虽然在 Bigtable 的论文中并没有给出 SSTable 的数据格式,不过在 LevelDB 的实现中,我们可以发现 SSTable 是以这种格式存储数据的:
当 LevelDB 读取 SSTable 存在的 ldb
文件时,会先读取文件中的 Footer
信息。
整个 Footer
在文件中占用 48 个字节,我们能在其中拿到 MetaIndex 块和 Index 块的位置,再通过其中的索引继而找到对应值存在的位置。
TableBuilder::Rep
结构体中就包含了一个文件需要创建的全部信息,包括数据块、索引块等等:
struct TableBuilder::Rep {
WritableFile* file;
uint64_t offset;
BlockBuilder data_block;
BlockBuilder index_block;
std::string last_key;
int64_t num_entries;
bool closed;
FilterBlockBuilder* filter_block;
...
}
C++
到这里,我们就完成了对整个数据读取过程的解析了;对于读操作,我们可以理解为 LevelDB 在它内部的『多级缓存』中依次查找是否存在对应的键,如果存在就会直接返回,唯一与缓存不同可能就是,在数据『命中』后,它并不会把数据移动到更近的地方,而是会把数据移到更远的地方来减少下一次的访问时间,虽然这么听起来却是不可思议,不过仔细想一下确实是这样。