LevelDB Compaction

Posted on

作用

LevelDB中将随机写在内存中缓存并进行排序(memtable)，从而将随机写转化成顺序写来提高数据的写入速度，在磁盘上它是以sstable的格式来持久化存储数据的。磁盘上的sstable文件是分层存储的，层级越高，容量就越大，存储的文件就越旧。随着数据的持续写入，memtable达到阈值之后会flush到level 0的sstable中，这个过程被称之为minor compaction，由于这一层级的文件是有memtable直接刷写下来的，所以sstable之间的key可能会存在重叠。

在查找一个key时，系统会先去memtable中查找，若未找到，则会按层级去sstable中查找。由于level 0中的sstable中的key是可能重叠的，所以在查找level0时可能要遍历多个sstable文件，这样会导致查询效率较低。所以当level 0中的文件数较多时，会出发major compaction，将该层的文件同下层合并。

level 0以上的文件是通过compaction来生成的，所以同一层的文件之间的key是不存在重叠的，但是该层的文件量也不能太大，否则会降低key的查找效率。同时，文件量太大也会造成major compaction的时候IO负载过高，影响系统的正常读写。所以LevelDB中会分多层来存储sstable文件，层级越高，容量越大，所存储的文件也越久。

综上，Compaction的机制如下：

  • 当memtable达到阈值时，会触发minor compaction，将memtable中的数据flush成sstable文件，防止占用过多内存
  • 当level 0中的文件数过多时，会触发major compaction，将该层的部分文件与上层合并，提高查询效率
  • 当level 0以上某层文件总量过大时，会触发major compaction，提高查询效率，同时避免之后参与compaction的数据量过大

流程

Compaction

Compaction最终是通过调用BackgroundCompaction来执行的，执行流程如下：

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
BackgroundCompaction() {
	if(imm_ != NULL) {
      	//minor compaction
		CompactMemtable() ;
		return ;
	}
	
    //major compaction
	if(is_manual) {
		ManualCompaction* m = manual_compaction_;
    	c = versions_->CompactRange(m->level, m->begin, m->end);
	} else {
		 c = versions_->PickCompaction();
	}

	if (c == NULL) {
    	// Nothing to do
  	} else if (!is_manual && c->IsTrivialMove()) {
      	//平移文件至下一层
	    c->edit()->DeleteFile(c->level(), f->number);
    	c->edit()->AddFile(c->level() + 1, f->number, f->file_size, f->smallest, f->largest);
    	status = versions_->LogAndApply(c->edit(), &mutex_);
  	} else {
  		DoCompactionWork(compact);
  	}
}

整体的流程图如下：

Minor Compaction

其中，CompactMemtable用以将memtable中的文件flush成sstable文件，它的流程如下：

1
2
3
4
5
6
7
8
CompactMemtable() {
	VersionEdit edit;
  	Version* base = versions_->current();
  	//将数据刷写至sstable中
  	Status s = WriteLevel0Table(imm_, &edit, base);
  	versions_->LogAndApply(&edit, &mutex_);
  	DeleteObsoleteFiles();
}

以上流程中，Version是系统用来管理系统中sstable文件的，每次进行compact后，都会新生成一个Version用来管理磁盘上sstable文件的状态，VersionEdit则代表此次compact中文件的变化情况，关于Version机制会在下节讨论。

在CompactMemtable中会调用WriteLevel0Table将memtable刷写至sstable中，机制如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
WriteLevel0Table(MemTable* mem, VersionEdit* edit, Version* base) {
	FileMetaData meta; 
	BuildTable(dbname_, env_, options_, table_cache_, iter, &meta);

	if(meta.file_size > 0) {
		if (base != NULL) {
			//为minor compact形成的sstfile选择合适的层级，memtable不一定是compact至level0中
			//如果level0中存在与此次compact key重叠的文件，则直接flush至level0
			//否则可以沉降至没有重叠区间的一个level，且沉降至该level后不会造成之后的大量compaction（与level+1层的重叠不能过多）
      		level = base->PickLevelForMemTableOutput(min_user_key, max_user_key);
    	}
    	//添加一个sstfile
    	edit->AddFile(level, meta.number, meta.file_size,
                meta.smallest, meta.largest);
	}
}

其中，需要注意的是，memtable不总是直接flush值level 0中的，如果level 0中没有文件与memtable的数据重合，则可以直接刷写至更高的层级，这样可以减少compaction的次数。但同时，如果某一层（level层）没有文件与memtable中的数据重合，但是下一层（level+1）中与memtable中重合的文件尺寸较大，也不能直接放入level中，否则的话会导致之后该文件compaction的时候设计到的数据量太大，影响系统的正常读写。

Major Compaction

Major Compaction的第一步是选择生成compaction的信息，根据compaction是否是手动触发的，具体机制又有不同，如下：

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
//根据手动compact时输入的level及key的范围生成compact信息
//compact信息中最重要的信息就是inputs，即参与compaction的sstfile
//其中inputs[0]中存储的是level层的文件
//inputs是与inputs[0]中的key存在交集的level+1层的文件
CompactRange(level, begin, end) {
	//获取第一层待compact的文件
	current_->GetOverlappingInputs(level, begin, end, &inputs);
  	if (inputs.empty()) {
   		return NULL;
  	}

  	Compaction* c = new Compaction(options_, level);
  	c->inputs_[0] = inputs;
  	//获取下一层被compact的文件
  	SetupOtherInputs(c);
}

PickCompaction() {
	//根据某层的总容量或者查找次数来触发compaction，其中容量触发的优先级更高
	const bool size_compaction = (current_->compaction_score_ >= 1);
  	const bool seek_compaction = (current_->file_to_compact_ != NULL);

  	if (size_compaction) {
  		level = current_->compaction_level_;
    	c = new Compaction(options_, level);

    // Pick the first file that comes after compact_pointer_[level]
    // compact_pointer_中记录的是每层上次compaction中最大的key，选择上次最大的key后的一个文件
    for (size_t i = 0; i < current_->files_[level].size(); i++) {
      FileMetaData* f = current_->files_[level][i];
      if (compact_pointer_[level].empty() ||
          icmp_.Compare(f->largest.Encode(), compact_pointer_[level]) > 0) {
        c->inputs_[0].push_back(f);
        break;
      }
    }
    if (c->inputs_[0].empty()) {
      // Wrap-around to the beginning of the key space
      //未选到文件的话，则选择第一个文件来进行compact
      c->inputs_[0].push_back(current_->files_[level][0]);
      }
  	} else if (seek_compaction) {
  		c->inputs_[0].push_back(current_->file_to_compact_)a
  	} else {
  		return NULL;
  	}
  	//根据inputs[0]来生成inputs[1]
  	SetupOtherInputs(c);
  	return c;
}

生成compaction信息后，便可开始compaction流程，如果level+1没有文件与待compaction的文件存在重叠，则可以考虑将文件直接下移，但是下移后也不能造成之后的compaction数据量过大，LevelDB这里是通过grandparent层级(level+2)的重叠数据量来判断的:

1
2
3
4
5
6
IsTrivialMove() {
	//如果level+2层存在与compact_range重合的数据较大，则不允许直接移动文件，否则之后会造成大量的compaction
	 return (num_input_files(0) == 1 && num_input_files(1) == 0 &&
          TotalFileSize(grandparents_) <=
            MaxGrandParentOverlapBytes(vset->options_));
}

如果不是直接平移，则调用DoCompactionWork来修改sstable，机制如下：

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
//根据输入在高层生成新的sstfile
DoCompactionWork() {
	//对所有传入的sstfile中的键值使用归并排序合并
	Iterator* input = versions_->MakeInputIterator(compact->compaction);
	input->SeekToFirst();
	//遍历所有key
	for ( input->Valid() ) {
		bool drop = false;
		 if (!ParseInternalKey(key, &ikey)) {
      		// Do not hide error keys
     		current_user_key.clear();
      		has_current_user_key = false;
     		last_sequence_for_key = kMaxSequenceNumber;
    	} else {
    		if (!has_current_user_key ||
          user_comparator()->Compare(ikey.user_key,
                                     Slice(current_user_key)) != 0) {
        //这个user_key是第一次出现
        current_user_key.assign(ikey.user_key.data(), ikey.user_key.size());
        has_current_user_key = true;
        last_sequence_for_key = kMaxSequenceNumber;
      	}

      	if (last_sequence_for_key <= compact->smallest_snapshot) {
        // last_sequence_for_key比快照中的key还旧，需要删除
        drop = true;    // rule A
      } else if (ikey.type == kTypeDeletion &&
                 ikey.sequence <= compact->smallest_snapshot &&
                 compact->compaction->IsBaseLevelForKey(ikey.user_key)) {
       			// 一个被标记为删除的key满足如下所有条件，才可删除：
        		// (1) 更高层不会出现该key
        		// (2) 更低层的key的sequence number更小
        		// (3) 符合如上规则A
        		drop = true;
      		}

      		last_sequence_for_key = ikey.sequence;
    	}

	 	//如果该key不需要删除，则写入新的sstfile中
	 	if(!drop) {
	 		//如果当前output file为空则打开一个output file

	 		if (compact->builder->NumEntries() == 0) {
        		compact->current_output()->smallest.DecodeFrom(key);
     		}
      		compact->current_output()->largest.DecodeFrom(key);
      		compact->builder->Add(key, input->value());

      		//如果当前output file过大，则关闭它
	 	}
	 	input->Next();
	 }
}

其中，LogAndApply是根据VersionEdit来生成新的version，并将新生成的version数据append到manifest中来进行持久化存储，这部分会在下节展开。

Version

Version机制作用简要概括如下：

  • 维护sstfile的索引信息，包括每层由哪些文件，每个文件的key range等
  • 根据sstfile信息，生成compaction相关的信息
  • 在每次compaction后，将元数据持久化至manifest中，供DB启动或恢复时加载
  • 维护版本信息，在此基础之上生成快照

Version机制涉及到数据结构主要有三个：Version，VersionEdit，VersionSet，其中每个Version都记录了当前sstfile的索引信息，每次compaction后都会生成一个新的version，而这次compaction的文件变化情况就是用VersionEdit来记录的，简单来说就是：

1
version0 + versionedit = version1

此外，为了支持快照及MVCC，老的version不会马上就删除，而是通过VersionSet来管理，VersionSet中所有的version是通过双向链表来连接的，这样可以方便地查找各个version对应的数据，简单来说就是：

1
versionset = version0 + version1 + ... + currentversion

如下所示：

VersionEdit

VersionEdit的主要结构如下，它记录了一次compaction后sstfile的变化信息，包括新增哪些文件、删除哪些文件、某个level参与compaction的最大key是什么：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//一个VersionEdit总是与一次compaction相关
class VersionEdit {
  //要删除的文件集合
  typedef std::set< std::pair<int, uint64_t> > DeletedFileSet;
  //要新增的文件集合
  std::vector< std::pair<int, FileMetaData> > new_files_;
  //记录此次compaction时，某层参与的最大key，下次compaction时会选择该key的后一个文件来进行compaction
  std::vector< std::pair<int, InternalKey> > compact_pointers_;

  void SetCompactPointer(int level, const InternalKey& key) {};

  void AddFile(int level, uint64_t file,
               uint64_t file_size,
               const InternalKey& smallest,
               const InternalKey& largest) {} ;
   
  void DeleteFile(int level, uint64_t file) {};
};

Version

LevelDB是通过version来记录数据库是有哪些sst文件组成的，每次compaction后都会生成新的version，version是LevelDB实现快照和MVCC的基础，它的主要结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Version {
	VersionSet* vset_; 
	//更旧的版本
	Version* next_;
	//更新的版本
	Version* prev_;
	//该version的引用数，初始为1，读取或者创建快照都会增加引用数
	int refs_;

	//当前sst文件的索引信息
	std::vector<FileMetaData*> files_[config::kNumLevels];
};

其中一个很重要的成员是引用数。。在一次compaction后，需要删除的sst文件并不会立马删除，因为此时可能会有读请求或者快照仍需要查找旧的文件来获取数据，这都是通过引用计数来控制的。一个version在生成时默认引用数为1，引用数变为0的时候便可以删除，当读请求释放或者该version不是最新版本时，refs_都会减1。总的来说，LevelDB的MVCC和快照机制是由一下几个部分组成：

  • sst文件是不可变的，在compaction的时候也不影响read
  • 每个key在内部存储时都会带上SequenceNumber，打快照时只需记录对应的SequenceNumber即可
  • version通过引用计数来保证资源的有效性，防止write影响read或者影响快照

VersionSet

VersionSet管理系统当前所有version，并负责这些元数据的持久化，其中最重要的方法就是LogAndApply，在每次version发生变化时该方法都会被调用，根据VersionEdit生成一个最新的Version，并 插入链表头部，持久化存储在manifest中，如下：

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
58
LogAndApply(VersionEdit* edit, port::Mutex* mu) {
	Version* v = new Version(this);
  	{
    	Builder builder(this, current_);
    	//将edit生效，记录在builder中
    	builder.Apply(edit);
    	//生成新的version
    	builder.SaveTo(v);
  	}
  	Finalize(v);

  	//创建新的manifest文件
  	if (descriptor_log_ == NULL) {
    // No reason to unlock *mu here since we only hit this path in the
    // first call to LogAndApply (when opening the database).
    assert(descriptor_file_ == NULL);
    new_manifest_file = DescriptorFileName(dbname_, manifest_file_number_);
    edit->SetNextFile(next_file_number_);
    s = env_->NewWritableFile(new_manifest_file, &descriptor_file_);
    if (s.ok()) {
      descriptor_log_ = new log::Writer(descriptor_file_);
      s = WriteSnapshot(descriptor_log_);
    }
  }

  //写入manifest时候，可以释放锁，让其他写入线程能进去队列排队
  {
    mu->Unlock();

    // Write new record to MANIFEST log
    //将变化写入manifest中
    if (s.ok()) {
      std::string record;
      edit->EncodeTo(&record);
      s = descriptor_log_->AddRecord(record);
      if (s.ok()) {
        s = descriptor_file_->Sync();
      }
      if (!s.ok()) {
        Log(options_->info_log, "MANIFEST write: %s\n", s.ToString().c_str());
      }
    }

    // If we just created a new descriptor file, install it by writing a
    // new CURRENT file that points to it.
    //将current文件指向最新的manifest文件
    if (s.ok() && !new_manifest_file.empty()) {
      s = SetCurrentFile(env_, dbname_, manifest_file_number_);
    }

    mu->Lock();
  }

  if(s.ok()) {
  	//将版本v插入头部，使current_指向该版本
  	AppendVersion(v);
  }
}

触发机制

LevelDB中总共有以下几种情况会出发compaction：

  • memtable达到阈值时会出发minor compaction
  • 手动触发：系统提供结构供用户指定key range及level来出发compaction，默认情况下，手动触发的compaction比自动触发的高
  • 文件数触发：由于level 0中的文件间key range可能存在重叠，所以需要严格控制该层的文件数，该层的文件数大于阈值的时候并发触发major compaction
  • 容量触发：level 0之上的文件需要严格控制容量，提高查询效率和避免过大的数据参与compaction，所以当level 0上某层的总数据量超过阈值时，便会触发major compaction
  • seek触发：系统在查找Key时会记录查找次数，由于每次查找都会消耗额外的IO，当查找次数过多时，对应的IO消耗会大于一次compaction所带来的IO，此时系统会触发compaction来降低某些key的查找次数

Reference

庖丁解LevelDB之版本控制

浅析 Bigtable 和 LevelDB 的实现

leveldb之Version VersionEdit and VersionSet