【LevelDB】文件挑选过程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

// 传入的 begin 和 end 是 InternalKey
void Version::GetOverlappingInputs(int level, const InternalKey* begin,
                                   const InternalKey* end,
                                   std::vector<FileMetaData*>* inputs) {
  assert(level >= 0);
  assert(level < config::kNumLevels);
  inputs->clear();
  Slice user_begin, user_end;
  if (begin != nullptr) {
    user_begin = begin->user_key();
  }
  if (end != nullptr) {
    user_end = end->user_key();
  }
  const Comparator* user_cmp = vset_->icmp_.user_comparator();
  for (size_t i = 0; i < files_[level].size();) {
    FileMetaData* f = files_[level][i++];
    const Slice file_start = f->smallest.user_key();
    const Slice file_limit = f->largest.user_key();
    if (begin != nullptr && user_cmp->Compare(file_limit, user_begin) < 0) {
      // file 最大值 file_limit 小于 user_begin，则必然不存在交集
      // "f" is completely before specified range; skip it
    } else if (end != nullptr && user_cmp->Compare(file_start, user_end) > 0) {
      // file 最小值 file_start 小于 user_end，则必然不存在交集
      // "f" is completely after specified range; skip it
    } else {
      // 当前文件和区间有交集，则将其加入 Compaction 中
      inputs->push_back(f);
      if (level == 0) {
        // 0 层需要特殊考虑，因为 0 层的文件自身也会互相产生交集
        // 具体就是 0 层需要修改 user_begin 和 user_end
        // 如果遇到一个 file_limit > user_end ，更新 user_end = file_limit 
        // 如果遇到一个 file_start < user_begin ，更新 user_begin = file_start
        // 然后从第一个文件根重新开始遍历，以最新的 [user_begin, user_end]
        // 这样不断扩充，因为 0 层文件很小，所以我们考虑直接暴力即可。
        // Level-0 files may overlap each other.  So check if the newly
        // added file has expanded the range.  If so, restart search.
        if (begin != nullptr && user_cmp->Compare(file_start, user_begin) < 0) {
          user_begin = file_start;
          inputs->clear();
          i = 0;
        } else if (end != nullptr &&
                   user_cmp->Compare(file_limit, user_end) > 0) {
          user_end = file_limit;
          inputs->clear();
          i = 0;
        }
      }
    }
  }

  // 最后 inputs 中就是与 [user_begin, user_end] 直接重叠或者间接重叠的所有文件
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

// l ==> low, u ==> up
// 从 compaction_files 中获取最大的文件 b1 ，然后在 level_files 中找到一个 b2 ，
// 满足 b1 中的最大值的 user_key 和 b2 中的最小值的 user_key 相等
// 如果找到这么一个 b2 ，那么就将其将入到 compaction_files 中，
// 然后以 compaction_files 中最大的文件来继续搜索
// 此时最大的文件已经更新了，更新为 b2 了
// 

// Extracts the largest file b1 from |compaction_files| and then searches for a
// b2 in |level_files| for which user_key(u1) = user_key(l2). If it finds such a
// file b2 (known as a boundary file) it adds it to |compaction_files| and then
// searches again using this new upper bound.
//
// If there are two blocks, b1=(l1, u1) and b2=(l2, u2) and
// user_key(u1) = user_key(l2), and if we compact b1 but not b2 then a
// subsequent get operation will yield an incorrect result because it will
// return the record from b2 in level i rather than from b1 because it searches
// level by level for records matching the supplied user key.
//
// parameters:
//   in     level_files:      List of files to search for boundary files.
//   in/out compaction_files: List of files to extend by adding boundary files.
// 注意，本函数是用来处理 level1-n 的，所以每个 SSTable 不存在交集
void AddBoundaryInputs(const InternalKeyComparator& icmp,
                       const std::vector<FileMetaData*>& level_files,
                       std::vector<FileMetaData*>* compaction_files) {
  InternalKey largest_key;

  // Quick return if compaction_files is empty.
  // 尝试找到最大的 key ，其实这里返回 false 当且仅当 compaction_files 为空
  if (!FindLargestKey(icmp, *compaction_files, &largest_key)) {
    return;
  }

  bool continue_searching = true;
  while (continue_searching) {
    // 找到当前的 level_files 中，一个文件中最小的 key 大于 larget_key ，而且其 user_key == largetst_key 的 user_key
    // 那么说明有重叠，如果不将这部分加入到合并区间内，那么之后这块的数据是过期数据
    //（具有相同的 user_key ，那么 internal_key 更大的 key 一定是 sequence_number 更小的，所以是国企数据）
    // 所以我们需要不停地将这部分找到，直到 smallest_boundary_file 为空，说明找不到了，那么就可以停止了
    FileMetaData* smallest_boundary_file =
        FindSmallestBoundaryFile(icmp, level_files, largest_key);

    // If a boundary file was found advance largest_key, otherwise we're done.
    if (smallest_boundary_file != NULL) {
      // 将这个文件加入 compaction_files
      compaction_files->push_back(smallest_boundary_file);
      // 然后这个文件的 largest 必然是新的 compaction_files 中最大的，将其设置为 largetst_key
      largest_key = smallest_boundary_file->largest;
    } else {
      // 否则没有，那么说明可以停止寻找了
      continue_searching = false;
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

void VersionSet::SetupOtherInputs(Compaction* c) {
  const int level = c->level(); 
  InternalKey smallest, largest;
  //level层边界文件文件查询
  AddBoundaryInputs(icmp_, current_->files_[level], &c->inputs_[0]);
  GetRange(c->inputs_[0], &smallest, &largest);
  //获取level+1层重叠文件
  current_->GetOverlappingInputs(level + 1, &smallest, &largest,
                                 &c->inputs_[1]); 

  // 获取文件集合边界[all_start, all_limit]
  InternalKey all_start, all_limit;
  GetRange2(c->inputs_[0], c->inputs_[1], &all_start, &all_limit);

  if (!c->inputs_[1].empty()) {
    std::vector<FileMetaData*> expanded0;
  //获取level层[all_start, all_limit]的重叠文件，若level为0会挑选出边界文件
    current_->GetOverlappingInputs(level, &all_start, &all_limit, &expanded0); 
  //level非0时挑选边界文件
    AddBoundaryInputs(icmp_, current_->files_[level], &expanded0); 

    const int64_t inputs0_size = TotalFileSize(c->inputs_[0]);
    const int64_t inputs1_size = TotalFileSize(c->inputs_[1]);
    const int64_t expanded0_size = TotalFileSize(expanded0);

  //文件集合总数小于25
    if (expanded0.size() > c->inputs_[0].size() &&
        inputs1_size + expanded0_size <
            ExpandedCompactionByteSizeLimit(options_)) {
      //获取level的文件边界[new_start, new_limit]
      InternalKey new_start, new_limit;
      GetRange(expanded0, &new_start, &new_limit);
      std::vector<FileMetaData*> expanded1;
      //获取level+1层[new_start, new_limit]重叠文件
      current_->GetOverlappingInputs(level + 1, &new_start, &new_limit,
                                     &expanded1);
      //若level+1层文件数不变，更新input0
      if (expanded1.size() == c->inputs_[1].size()) {
        smallest = new_start;
        largest = new_limit;
        c->inputs_[0] = expanded0;
        c->inputs_[1] = expanded1;
        GetRange2(c->inputs_[0], c->inputs_[1], &all_start, &all_limit);
      }
    }
  }

 //获取level+2层重叠文件
  if (level + 2 < config::kNumLevels) {
    current_->GetOverlappingInputs(level + 2, &all_start, &all_limit,
                                   &c->grandparents_);
  }

  //更新合并文件终止点
  compact_pointer_[level] = largest.Encode().ToString();
  c->edit_.SetCompactPointer(level, largest);
}