優(yōu)點(diǎn)

1. 增加了column family萎胰，這樣有利于多個不相關(guān)的數(shù)據(jù)集存儲在同一個db中往果，因?yàn)椴煌琧olumn family的數(shù)據(jù)是存儲在不同的sst和memtable中使碾，所以一定程度上起到了隔離的作用草丧。
2. 采用了多線程同時進(jìn)行compaction的方法腋寨，優(yōu)化了compact的速度。
3. 增加了merge operator扼菠，優(yōu)化了modify的效率
4. 將flush和compaction分開不同的線程池摄杂，能有效的加快flush，防止stall循榆。
5. 增加了對write ahead log(WAL)的特殊管理機(jī)制析恢，這樣就能方便管理WAL文件，因?yàn)閃AL是binlog文件秧饮。
6. RocksDB典型的做法是Level 0-2不壓縮映挂，最后一層使用zlib(慢泽篮，壓縮比很高)，而其它各層采用snappy

rocksdb的文件類型

主要有以下幾種類型sst文件柑船，CURRENT文件帽撑，manifest文件，log文件鞍时，LOG文件和LOCK文件

• sst文件存儲的是落地的數(shù)據(jù);
• CURRENT文件存儲的是當(dāng)前最新的是哪個manifest文件;
• manifest文件存儲的是Version的變化;
• log文件是rocksdb的write ahead log亏拉，就是在寫db之前寫的數(shù)據(jù)日志文件;
• LOG文件是一些日志信息，是供調(diào)試用的;
• LOCK是打開db鎖逆巍，只允許同時有一個進(jìn)程打開db及塘。

配置信息(TODO)

ColumnFamilyOptions

這些option都是column family相關(guān)的，可以對不同的column family賦不同的值锐极。

• inplace_update_support: 字面含義是是否支持在原位置更新笙僚，如果支持的話，那么原來的數(shù)據(jù)就被擦除了灵再，所以snapshot和iterator保留當(dāng)時的數(shù)據(jù)的邏輯就沒法實(shí)現(xiàn)了
• num_levels: 記錄的是version的level的數(shù)目肋层，默認(rèn)是7，即0~6
• target_file_size_base: level1的sst文件的大小檬嘀，默認(rèn)為2MB
• target_file_size_multiplier: level1以上的sst文件大小槽驶，乘數(shù)因子默認(rèn)是1，即所有l(wèi)evel的文件大小都是2MB
  • level0的文件大小是由write_buffer_size決定的鸳兽，level1的文件大小是由target_file_size_base決定的掂铐，level2及以上，size = target_file_size_base * （target_file_size_multiplier ^ (L - 1)）
• max_bytes_for_level_base: level1的sst總的文件總和大小揍异，默認(rèn)是10MB
• max_bytes_for_level_multiplier: level2及以上的level的sst文件總和大小的乘數(shù)因子全陨，默認(rèn)是10,
  • level0的sst文件總和大小是level0_stop_writes_trigger * write_buffer_size，因?yàn)閘evel0的文件數(shù)目達(dá)到level0_stop_writes_trigger時候就會停止write衷掷。
  • level1及以上的文件總和大小是max_bytes_for_level_base * (max_bytes_for_level_multiplier ^ (L - 1))辱姨，默認(rèn)的level0是4MB * 24 = 96MB，level1是10MB戚嗅，level2是100MB雨涛，level3是1G，level4是10G懦胞。替久。

RocksDB Flush

Flush是指將memtable的數(shù)據(jù)導(dǎo)入到sst中，變成持久化存儲躏尉，就不怕數(shù)據(jù)丟失了蚯根。

觸發(fā)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的大小達(dá)到了max write buffer胀糜，如果是就將should_flush_置為true(CheckMemtableFull還有其他情況觸發(fā))颅拦，并會在WriteBatch的Handler里面調(diào)用CheckMemtableFull蒂誉，將當(dāng)前column family加入flush_scheduler;
   • CheckMemtableFull調(diào)用的FlushScheduler::ScheduleWork方法只是將cfd添加到checking_set_隊(duì)列中,并未真正地執(zhí)行Flush調(diào)度距帅；
2. 在Write的時候锥债，調(diào)用ScheduleFlushes哮肚，將需要flush的column family的memtable切換一個新的允趟，同時將原來的memtable加入cfd的imm中;
   • 由于真正的Flush過程是在另一個線程完成的潮剪，所以這個地方并不會block寫過程;
   • Write中調(diào)用PreprocessWrite做些預(yù)先處理的工作抗碰；
   • 如果發(fā)現(xiàn)checking_set_不為空弧蝇，會調(diào)用DBImpl::ScheduleFlushes方法看疗，然后調(diào)用SwitchMemtable切換新的memtable两芳；DBImpl::SwitchMemtable執(zhí)行流程：
     • 如果開啟two_write_queues_: 等待沒有并發(fā)的wal寫入線程怖辆；
     • WriteRecoverableState在memtable中寫入recoverable_state狀態(tài);
     • 如果開啟enable_pipelined_write: 等待所有的memtable寫入線程完畢竖螃；
     • 如果需要創(chuàng)建新的wal斑鼻，則調(diào)用CreateWAL創(chuàng)建wal writer坚弱；
     • 調(diào)用cfd->ConstructNewMemtable荒叶，創(chuàng)建新的memtable;
     • cfd->imm()->Add(cfd->mem(), &context->memtables_to_free_)些楣，將原來的memtable加入到imm中愁茁；
3. 當(dāng)mem切換imm切換成功鹅很，會觸發(fā)MaybeScheduleFlushOrCompaction邮屁，嘗試flush或者compaction;
   • 當(dāng)然也有其他case觸發(fā)flush/compaction： 如果這個column family data的imm數(shù)量大于min_write_buffer_number_to_merge佑吝，并啟動一個新的線程調(diào)用BGWorkFlush;
   • BGWorkFlush->BackgroundCallFlush->BackgroundFlush->FlushJob
   • FlushJob::PickMemTable選擇需要Flush的imm
     • 由于cfd中可能包含多個imm芋忿，從cfd獲取一個可以進(jìn)行flush的memtable的list：待合并盗飒、flush的imm結(jié)合;
     • 從memtable列表中獲取第一個memtable逆趣，使用其edit結(jié)構(gòu)來保存本次flush的元信息: 該次flush的版本信息通過第一個imm設(shè)定;
     • 調(diào)用version_set的NewFileNumber接口為新的文件生成一個filenumber（同時可以指定對應(yīng)level的路徑, level=0）
   • FlushJob::Run, 執(zhí)行flush邏輯
     • WriteLevel0Table: 將imm寫入level=0的sst文件中
       • 遍歷待合并的Imm集合：
         • 待flush的數(shù)據(jù)：構(gòu)造InternalIterator迭代器數(shù)組宣渗；
         • 待刪除的數(shù)據(jù)：構(gòu)造FragmentedRangeTombstoneIterator迭代器數(shù)組痕囱；
       • 基于InternalIterator構(gòu)造NewMergingIterator歸并迭代器鞍恢，基于最小堆實(shí)現(xiàn)多路歸并算法弦悉；
       • BuildTable:將數(shù)據(jù)寫入sst中：
         • TableFileName： 構(gòu)造flush的文件名稽莉；
         • NewWritableFile: 創(chuàng)建新的文件污秆；
         • WritableFileWriter： 構(gòu)造writer良拼；
         • NewTableBuilder： 構(gòu)建table builder将饺；
         • CompactionIterator： 構(gòu)建合并迭代器刮吧；
         • 遍歷迭代器杀捻，調(diào)用BlockBasedTableBuilder.Add方法逐一添加k/v數(shù)據(jù),中間可能觸發(fā)flush仅仆；
       • 處理完成 之后如果output_file_directory不為空則同步該目錄(output_file_directory_->Fsync())
       • 調(diào)用edit_->AddFile墓拜，將生成的文件添加到L0
       • 記錄本次Flush的狀態(tài)

RocksDB Compaction

• 通過minor compaction咳榜，內(nèi)存中的數(shù)據(jù)不斷地寫入的磁盤涌韩，保證有足夠的內(nèi)存來應(yīng)對新的寫入臣樱；
• 而通過major compaction雇毫，多層之間的SST文件的重復(fù)數(shù)據(jù)和無用的數(shù)據(jù)可以迅速減少桩盲，進(jìn)而減少sst文件占用的磁盤空間。

Compaction的觸發(fā)條件是兩類：文件個數(shù)和文件大小孝冒。

• 對于level0量承，觸發(fā)條件是:
  • sst文件個數(shù)撕捍，通過參數(shù)level0_file_num_compaction_trigger控制;
  • score通過sst文件數(shù)目與level0_file_num_compaction_trigger的比值得到。
• level1-levelN觸發(fā)條件是:
  • sst文件的大小狮腿，通過參數(shù)max_bytes_for_level_base和max_bytes_for_level_multiplier來控制每一層最大的容量;
  • score是本層當(dāng)前的總?cè)萘颗c能存放的最大容量的比值

Compaction的主要流程如下：

1. 首先找score最高的level缘厢，如果level的score>1，則選擇從這個level進(jìn)行compaction
2. 根據(jù)一定的策略夜畴，從level中選擇一個sst文件進(jìn)行compact，對于level0央碟，由于sst文件之間(minkey,maxkey)有重疊税灌，所以可能有多個均函。
3. 從level中選出的文件，我們能計算出(minkey,maxkey)
4. 從level+1中選出與(minkey,maxkey)有重疊的sst文件
5. 多個sst文件進(jìn)行歸并排序菱涤，合并寫出到sst文件
6. 根據(jù)壓縮策略苞也，對寫出的sst文件進(jìn)行壓縮
7. 合并結(jié)束后，利用VersionEdit更新VersionSet粘秆，更新統(tǒng)計信息

觸發(fā)Compaction的方式：

• DBImpl::RunManualCompaction： 手動觸發(fā)Compaction
  • 判斷觸發(fā)MannulCompaction條件如迟、變量;
    • 確保沒有非mannul compaction執(zhí)行，這樣的話mannual compaction可以執(zhí)行任意range的compaction攻走；
  • 調(diào)用BGWorkCompaction線程開啟調(diào)度;
• 自動Compaction:
  • DBImpl::MaybeScheduleFlushOrCompaction: 在每次觸發(fā)mem的flush的時昔搂，會判定是否進(jìn)行flush/compaction
  • DBImpl::BackgroundCallFlush: 包含了mem的flush逛裤、compaction的判定執(zhí)行邏輯；
  • DBImpl::MaybeScheduleFlushOrCompaction
    • 調(diào)用BGWorkCompaction線程開啟調(diào)度
• BGWorkCompaction的執(zhí)行邏輯：可以發(fā)現(xiàn)不論是手動拍霜、自動觸發(fā)的模式道偷，的最終都會調(diào)用Compaction線程進(jìn)行處理：
  • DBImpl::BackgroundCallCompaction
  • DBImpl::BackgroundCompaction(真正的執(zhí)行邏輯，這個函數(shù)巨長)
    • 如果是mannul compaction:
      • 調(diào)用EnoughRoomForCompaction判定是否有足夠的Compaction空間剃执，沒有空間的話直接返回CompactionTooLarge異常；
    • 如果是auto compaction:
      • 調(diào)用PickCompactionFromQueue，從queue選擇需要執(zhí)行的cfd示血，如果為空，直接返回黔姜；
      • 調(diào)用EnoughRoomForCompaction判定是否有足夠的Compaction空間纳寂，沒有空間的話爷肝，更新統(tǒng)計信息不返回異常；
    • 在進(jìn)行完準(zhǔn)備工作之后杏愤，判定需要合并的compcation(c)不為空的話，
      • 如果c為deletion_compaction：
        • 刪除c執(zhí)行的fd和edit信息；
        • 調(diào)用VersionSet::LogAndApply進(jìn)行更新manifest操作；
        • 調(diào)用DBImpl::InstallSuperVersionAndScheduleWork更新SuperVersion把将；
      • 如果c為IsTrivialMove:
        • 類似于上述操作漫拭，先進(jìn)性fileMeta變更膳叨；
        • 然后調(diào)用VersionSet::LogAndApply進(jìn)行更新manifest操作复唤；
        • 再調(diào)用DBImpl::InstallSuperVersionAndScheduleWork更新SuperVersion；
      • 如果c是BottomCompaction（最開始引入是為了universal-compaction，后來也對level-compaction進(jìn)行適配掺出，主要用于長時間(long running)合并摩泪，以避免同short-live上層合并邏輯的沖突）:
        • 調(diào)用DBImpl::BGWorkBottomCompaction執(zhí)行；
      • 否則驼侠，執(zhí)行通用Compaction邏輯：
        • 構(gòu)造并提交CompactionJob昔馋；
          • Prepare:
            • 構(gòu)造邊界值和統(tǒng)計信息；
          • Run:
            • 構(gòu)造合并迭代器妥粟；
          • Install:
            • 調(diào)用VersionSet::LogAndApply變更edit/fileMeta信息;

在ColumnFamilyData構(gòu)造信息中會根據(jù)配置信息初始化审丘，如下變量用于compaction的統(tǒng)計信息更新、并確定下一次compaction的判斷：

std::unique_ptr<CompactionPicker> compaction_picker_;

CompactionPicker提供的主要接口有：

• NeedsCompaction: 是否進(jìn)行合并勾给；
• MaxOutputLevel: 最大output level滩报；
• PickCompaction: 根據(jù)level和inputs文件產(chǎn)生新的compaction；
• CompactRange: 根據(jù)在指定level的[begin,end]信息構(gòu)造compaction信息播急；

在RocksDB中脓钾，compaction的CompactionPicker實(shí)現(xiàn)有如下幾種：

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文件進(jìn)行合并，然后將合并后的文件寫入到level+1層的過程桩警。

• 通過判斷每個level的score是否大于1可训，確定level是否需要compact
  • 默認(rèn)是選擇文件size較大，包含delete記錄較多的sst文件捶枢，這種文件盡快合并有利于縮小空間握截。
  • 每次會從level中選取一個sst文件與下層compact，但由于level0中可能會有多個sst文件存在重疊的范圍烂叔，因此一次compaction可能有多個level0的sst文件參與谨胞。

在Level-Based的Compaction中，決定從一個level到下一個level進(jìn)行合并的方法有(參考VersionStorageInfo::UpdateFilesByCompactionPri方法)：

• kByCompensatedSize: 根據(jù)sst文件的compensated_file_size補(bǔ)償文件大小排序選擇蒜鸡；
  • compensated_file_size大致可以理解為：file_meta->fd.GetFileSize() + (file_meta->num_deletions * 2 - file_meta->num_entries) * average_value_size * kDeletionWeightOnCompaction胯努，同文件大小與刪除文件數(shù)量有關(guān)系（參考VersionStorageInfo::ComputeCompensatedSizes）；
• kOldestLargestSeqFirst: 根據(jù)sst文件的largest_seqno序列號排序選擇(大者優(yōu)先)逢防；
• kOldestSmallestSeqFirst: 根據(jù)sst文件的smallest_seqno序列號排序選擇(小者優(yōu)先)康聂；
• kMinOverlappingRatio: 根據(jù)sst文件的overlapping大小/file_size排序；

Universal Compaction

相對于level compaction胞四，Univeral compaction由于每一次合并的文件較多，相對于level compaction的多層合并伶椿，寫放大較小辜伟，付出的代價是空間放大較大氓侧。

• Univeral模式中，所有的sst文件都可能存在重疊的key范圍导狡。對于R1,R2,R3,...,Rn,每個R是一個sst文件约巷，R1中包含了最新的數(shù)據(jù)，而Rn包含了最老的數(shù)據(jù);
• 合并的前提條件是sst文件數(shù)目大于level0_file_num_compaction_trigger旱捧，如果沒有達(dá)到這個閥值独郎，則不會觸發(fā)合并。在滿足前置條件的情況下枚赡，按優(yōu)先級順序觸發(fā)以下合并氓癌。

1. 如果空間放大超過一定的比例，則所有sst進(jìn)行一次compaction贫橙，所謂的full compaction贪婉，通過參數(shù)max_size_amplification_percent控制。
2. 如果前size(R1)小于size(R2)在一定比例卢肃，默認(rèn)1%疲迂，則與R1與R2一起進(jìn)行compaction，如果（R1+R2)*(100+ratio)%100<R3莫湘，則將R3也加入到compaction任務(wù)中尤蒿，依次順序加入sst文件
3. 如果第1和第2種情況都沒有compaction，則強(qiáng)制選擇前N個文件進(jìn)行合并幅垮。

FIFO Compaction

FIFO顧名思義就是先進(jìn)先出腰池，這種模式周期性地刪除舊數(shù)據(jù)。在FIFO模式下军洼，所有文件都在level0巩螃，當(dāng)sst文件總大小超過閥值max_table_files_size，則刪除最老的sst文件匕争。

參考

• RocksDB簡介：http://www.reibang.com/p/8d09a7190dda
• RocksDB Version管理概述: https://www.cnblogs.com/coguin/p/11405082.html
• https://segmentfault.com/a/1190000018967058
• 這里講了memtable并發(fā)寫入的過程避乏，利用了InlineSkipList，它是支持多讀多寫的甘桑，節(jié)點(diǎn)插入的時候會使用 每層CAS 判斷節(jié)點(diǎn)的 next域是否發(fā)生了改變拍皮，這個 CAS 操作使用默認(rèn)的memory_order_seq_cst:
  • http://mysql.taobao.org/monthly/2017/07/05/
• RocksDB線程管理: http://www.reibang.com/p/abf15e5e306b
• 知乎RocksDB學(xué)習(xí)好文章: https://www.zhihu.com/question/270732348/answer/356254676
• RocksDB系列文章: https://www.cnblogs.com/cchust/category/895428.html
• RocksDB Flush: http://www.reibang.com/p/38a38134491b
• MemTable存儲結(jié)構(gòu):
  • https://github.com/facebook/rocksdb/wiki/MemTable
  • http://www.reibang.com/p/9e385682ed4e
• RocksDB BlockBasedTable:
  • http://www.reibang.com/p/9b5ade5212ab
  • https://github.com/facebook/rocksdb/wiki/Rocksdb-BlockBasedTable-Format
• RocksDB PrefixSeek:
  • http://www.reibang.com/p/9848a376d41d
• RocksDB Manifest:
  • http://www.reibang.com/p/d1b38ce0d966
  • http://www.reibang.com/p/fea863a775af
• RocksDB BloomFilter:
  • http://www.reibang.com/p/b534dc48bb59
• RocksDB Compaction:
  • https://github.com/facebook/rocksdb/wiki/Leveled-Compaction
  • http://www.reibang.com/p/99cc0df8ed21
  • https://www.cnblogs.com/svan/p/7047251.html
  • https://www.cnblogs.com/cchust/p/6007486.html
• RocksDB 筆記: http://www.reibang.com/p/0d4bea498a91
• RocksDB 寫入流程:
  • https://yq.aliyun.com/articles/409102?spm=a2c4e.11153959.teamhomeleft.1.8WKxt7
  • https://cloud.tencent.com/developer/article/1143439
• RocksDB CuckooTable: 針對點(diǎn)差進(jìn)行優(yōu)化了的format格式
  • https://github.com/facebook/rocksdb/wiki/CuckooTable-Format
• RocksDB SnapShot:
  • https://zhuanlan.zhihu.com/p/35195328