Status DBImpl::MakeRoomForWrite(bool force){ mutex_.AssertHeld(); bool allow_delay = !force; Status s; while (true) { if (!bg_error_.ok()) { // ... 中间跳过了很多 case } else { // Attempt to switch to a new memtable and trigger compaction of old // 尝试创建一个新的 memtable,并且将 旧数据进行压实 assert(versions_->PrevLogNumber() == 0);
// Save the contents of the memtable as a new Table VersionEdit edit; Version* base = versions_->current(); base->Ref(); Status s = WriteLevel0Table(imm_, &edit, base); // 内存的数据往 level0 写,最近的数据嘛 base->Unref();
if (s.ok() && shutting_down_.load(std::memory_order_acquire)) { s = Status::IOError("Deleting DB during memtable compaction"); } // .... }
删除值
和之前处理逻辑一样,我们增加一个特殊的值,append 到 log 中,标记此值已死亡。
读取数据
为了方便在 SSTable 中查询数据。Index Table 被放置于每一个 SSTable 的尾端,一般是 sparse index [稀疏索引],我们载入这个块的时候,讲 Index Table 载入内存,提供查询的能力。
当我们查找某个 Key,比如 Dollar 这个值势必在 dog 和 downgrade 之间,因此我们只需要扫描 17208 到 19504 但是如果数据没有的情况下,我们可能会扫描全表,因此我们加入 bloom filter 来帮助我们快速确认是否某个值根本不存在。
// Unlock while reading from files and memtables { mutex_.Unlock(); // First look in the memtable, then in the immutable memtable (if any). // 这里我们先去 mem 中获取也就是内存中的 LookupKey lkey(key, snapshot); if (mem->Get(lkey, value, &s)) { // Done // 然后尝试从 imm,也就是即将持久化的内存对象中找 } elseif (imm != nullptr && imm->Get(lkey, value, &s)) { // Done } else {
// Search level-0 in order from newest to oldest. // 从 Level-0 开始的逆序查找,因为大部分时候,Level-0 能找到,局部性原则嘛 std::vector<FileMetaData*> tmp; tmp.reserve(files_[0].size()); for (uint32_t i = 0; i < files_[0].size(); i++) { FileMetaData* f = files_[0][i]; if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 && ucmp->Compare(user_key, f->largest.user_key()) <= 0) { tmp.push_back(f); } } if (!tmp.empty()) { std::sort(tmp.begin(), tmp.end(), NewestFirst); for (uint32_t i = 0; i < tmp.size(); i++) { if (!(*func)(arg, 0, tmp[i])) { return; } } }
// Search other levels. 查找其他的层级 for (int level = 1; level < config::kNumLevels; level++) { size_t num_files = files_[level].size(); if (num_files == 0) continue;
// 二分查找 INdex uint32_t index = FindFile(vset_->icmp_, files_[level], internal_key); if (index < num_files) { FileMetaData* f = files_[level][index]; if (ucmp->Compare(user_key, f->smallest.user_key()) < 0) { // All of "f" is past any data for user_key } else { if (!(*func)(arg, level, f)) { return; } } } } }