RocksDB原理学习笔记

2020-02-01  本文已影响0人  分裂四人组

优点

  1. 增加了column family，这样有利于多个不相关的数据集存储在同一个db中，因为不同column family的数据是存储在不同的sst和memtable中，所以一定程度上起到了隔离的作用。
  2. 采用了多线程同时进行compaction的方法，优化了compact的速度。
  3. 增加了merge operator，优化了modify的效率
  4. 将flush和compaction分开不同的线程池，能有效的加快flush，防止stall。
  5. 增加了对write ahead log(WAL)的特殊管理机制，这样就能方便管理WAL文件，因为WAL是binlog文件。
  6. RocksDB典型的做法是Level 0-2不压缩，最后一层使用zlib(慢，压缩比很高)，而其它各层采用snappy

rocksdb的文件类型

主要有以下几种类型sst文件，CURRENT文件，manifest文件，log文件，LOG文件和LOCK文件

配置信息(TODO)

ColumnFamilyOptions

这些option都是column family相关的，可以对不同的column family赋不同的值。

RocksDB Flush

Flush是指将memtable的数据导入到sst中，变成持久化存储，就不怕数据丢失了。

触发Flush的代码入口：

Status DBImpl::ScheduleFlushes(WriteContext* context) {
  autovector<ColumnFamilyData*> cfds;
  if (immutable_db_options_.atomic_flush) {
    SelectColumnFamiliesForAtomicFlush(&cfds);
    for (auto cfd : cfds) {
      cfd->Ref();
    }
    flush_scheduler_.Clear();
  } else {
    ColumnFamilyData* tmp_cfd;
    while ((tmp_cfd = flush_scheduler_.TakeNextColumnFamily()) != nullptr) {
      cfds.push_back(tmp_cfd);
    }
    MaybeFlushStatsCF(&cfds);
  }
  Status status;
  for (auto& cfd : cfds) {
    if (!cfd->mem()->IsEmpty()) {
      status = SwitchMemtable(cfd, context);
    }
    if (cfd->Unref()) {
      delete cfd;
      cfd = nullptr;
    }
    if (!status.ok()) {
      break;
    }
  }
  if (status.ok()) {
    if (immutable_db_options_.atomic_flush) {
      AssignAtomicFlushSeq(cfds);
    }
    FlushRequest flush_req;
    GenerateFlushRequest(cfds, &flush_req);
    SchedulePendingFlush(flush_req, FlushReason::kWriteBufferFull);
    MaybeScheduleFlushOrCompaction();
  }
  return status;
  1. 首先在memtable的add的时候，会检测是否memtable的大小达到了max write buffer，如果是就将should_flush_置为true(CheckMemtableFull还有其他情况触发)，并会在WriteBatch的Handler里面调用CheckMemtableFull，将当前column family加入flush_scheduler;
    • CheckMemtableFull调用的FlushScheduler::ScheduleWork方法只是将cfd添加到checking_set_队列中,并未真正地执行Flush调度；
  2. 在Write的时候，调用ScheduleFlushes，将需要flush的column family的memtable切换一个新的，同时将原来的memtable加入cfd的imm中;
    • 由于真正的Flush过程是在另一个线程完成的，所以这个地方并不会block写过程;
    • Write中调用PreprocessWrite做些预先处理的工作；
    • 如果发现checking_set_不为空，会调用DBImpl::ScheduleFlushes方法，然后调用SwitchMemtable切换新的memtable；DBImpl::SwitchMemtable执行流程：
      • 如果开启two_write_queues_: 等待没有并发的wal写入线程；
      • WriteRecoverableState在memtable中写入recoverable_state状态;
      • 如果开启enable_pipelined_write: 等待所有的memtable写入线程完毕；
      • 如果需要创建新的wal，则调用CreateWAL创建wal writer；
      • 调用cfd->ConstructNewMemtable，创建新的memtable;
      • cfd->imm()->Add(cfd->mem(), &context->memtables_to_free_)，将原来的memtable加入到imm中；
  3. 当mem切换imm切换成功，会触发MaybeScheduleFlushOrCompaction，尝试flush或者compaction;
    • 当然也有其他case触发flush/compaction： 如果这个column family data的imm数量大于min_write_buffer_number_to_merge，并启动一个新的线程调用BGWorkFlush;
    • BGWorkFlush->BackgroundCallFlush->BackgroundFlush->FlushJob
    • FlushJob::PickMemTable选择需要Flush的imm
      • 由于cfd中可能包含多个imm，从cfd获取一个可以进行flush的memtable的list：待合并、flush的imm结合;
      • 从memtable列表中获取第一个memtable，使用其edit结构来保存本次flush的元信息: 该次flush的版本信息通过第一个imm设定;
      • 调用version_set的NewFileNumber接口为新的文件生成一个filenumber（同时可以指定对应level的路径, level=0）
    • FlushJob::Run, 执行flush逻辑
      • WriteLevel0Table: 将imm写入level=0的sst文件中
        • 遍历待合并的Imm集合：
          • 待flush的数据：构造InternalIterator迭代器数组；
          • 待删除的数据：构造FragmentedRangeTombstoneIterator迭代器数组；
        • 基于InternalIterator构造NewMergingIterator归并迭代器，基于最小堆实现多路归并算法；
        • BuildTable:将数据写入sst中：
          • TableFileName： 构造flush的文件名；
          • NewWritableFile: 创建新的文件；
          • WritableFileWriter： 构造writer；
          • NewTableBuilder： 构建table builder；
          • CompactionIterator： 构建合并迭代器；
          • 遍历迭代器，调用BlockBasedTableBuilder.Add方法逐一添加k/v数据,中间可能触发flush；
        • 处理完成 之后如果output_file_directory不为空则同步该目录(output_file_directory_->Fsync())
        • 调用edit_->AddFile，将生成的文件添加到L0
        • 记录本次Flush的状态

RocksDB Compaction

Compaction的触发条件是两类：文件个数和文件大小。

Compaction的主要流程如下：

  1. 首先找score最高的level，如果level的score>1，则选择从这个level进行compaction
  2. 根据一定的策略，从level中选择一个sst文件进行compact，对于level0，由于sst文件之间(minkey,maxkey)有重叠，所以可能有多个。
  3. 从level中选出的文件，我们能计算出(minkey,maxkey)
  4. 从level+1中选出与(minkey,maxkey)有重叠的sst文件
  5. 多个sst文件进行归并排序，合并写出到sst文件
  6. 根据压缩策略，对写出的sst文件进行压缩
  7. 合并结束后，利用VersionEdit更新VersionSet，更新统计信息

触发Compaction的方式：

在ColumnFamilyData构造信息中会根据配置信息初始化，如下变量用于compaction的统计信息更新、并确定下一次compaction的判断：

std::unique_ptr<CompactionPicker> compaction_picker_;

CompactionPicker提供的主要接口有：

在RocksDB中，compaction的CompactionPicker实现有如下几种：

enum CompactionStyle : char {
  // level based compaction style
  kCompactionStyleLevel = 0x0,
  // Universal compaction style
  // Not supported in ROCKSDB_LITE.
  kCompactionStyleUniversal = 0x1,
  // FIFO compaction style
  // Not supported in ROCKSDB_LITE
  kCompactionStyleFIFO = 0x2,
  // Disable background compaction. Compaction jobs are submitted
  // via CompactFiles().
  // Not supported in ROCKSDB_LITE
  kCompactionStyleNone = 0x3,
};

Level Compaction

某个level的sst文件与level+1中存在重叠的sst文件进行合并，然后将合并后的文件写入到level+1层的过程。

在Level-Based的Compaction中，决定从一个level到下一个level进行合并的方法有(参考VersionStorageInfo::UpdateFilesByCompactionPri方法)：

Universal Compaction

相对于level compaction，Univeral compaction由于每一次合并的文件较多，相对于level compaction的多层合并，写放大较小，付出的代价是空间放大较大。

  • Univeral模式中，所有的sst文件都可能存在重叠的key范围。对于R1,R2,R3,...,Rn,每个R是一个sst文件，R1中包含了最新的数据，而Rn包含了最老的数据;
  • 合并的前提条件是sst文件数目大于level0_file_num_compaction_trigger，如果没有达到这个阀值，则不会触发合并。在满足前置条件的情况下，按优先级顺序触发以下合并。
  1. 如果空间放大超过一定的比例，则所有sst进行一次compaction，所谓的full compaction，通过参数max_size_amplification_percent控制。
  2. 如果前size(R1)小于size(R2)在一定比例，默认1%，则与R1与R2一起进行compaction，如果（R1+R2)*(100+ratio)%100<R3，则将R3也加入到compaction任务中，依次顺序加入sst文件
  3. 如果第1和第2种情况都没有compaction，则强制选择前N个文件进行合并。

FIFO Compaction

FIFO顾名思义就是先进先出，这种模式周期性地删除旧数据。在FIFO模式下，所有文件都在level0，当sst文件总大小超过阀值max_table_files_size，则删除最老的sst文件。

参考

上一篇 下一篇

猜你喜欢

热点阅读