2023年9月14日星期四

Rocksdb源码笔记

重要流程

DBImpl::Get

  1. GetAndRefSuperVersion首先要获取super version，sv记录column family全局状态，有哪些memtable，有哪些sst等等。所以每次flush或者compaction之后都会更新sv
  2. 更新sv和读取sv可能发生冲突，所以用thread local机制来尽量避免锁
  3. 从super version读，读的顺序是mem(memtable), imm(immutable memtables), current(version sstables)
  4. MemTable::Get 先通过bloomfilter过滤 bloom_filter_->MayContain 然后MemTableRep::Get，如果是skiplist实现就是在skiplist里面找，还有hashskiplist，skiplist是比较均衡的选择
  5. MemTableListVersion::Get 顺着immutable memtable list查找。因为memtable是新写的数据所以总数据占比可能不高，命中率也可能不高
  6. Version::Get 遍历所有的sst files查找数据，遍历的过程l0顺序其它二分加上file indexer。处理每个sst文件是通过TableCache::Get，里面整合了各种读cache和读文件的过程
    1. 如果配置了row cache GetFromRowCache直接拿到kv值。cache key会用上sst file number做前缀，所以不会有update只有get失败时用insert填充
    2. BlockBasedTable::Get 封装了从block cache或者sst file读取的逻辑，这个talbe对应sst file number
    3. FullFilterKeyMayMatch 通过bloom filter快速过滤该sst file
    4. IndexIterator.seek(key) 在索引里寻找key对应的block(包含地址，大小等信息)
    5. BlockBasedTable::NewDataBlockIterator-> BlockBasedTable::MaybeReadBlockAndLoadToCache 从blockcache里面读取或者读sst file并放回block cache
    6. DataBlockIter.SeekForGet 读取block的实际内容
    7. DataBlockIter::SeekForGetImpl 通过hashmap寻找key对应的binary seek index位置，然后再通过这个位置读取block里面的data
    8. get_context->SaveValue 直接将Block中的数据地址赋给用户传进来的PinnableSlice*中(知名优化点)

DBImpl::WriteImpl

  1. WriteImpl 入口，write_thread_.JoinBatchGroup加入当前batch的线程组，抢主(cas队列头)，如果失败需要等待到下一个可运行状态(几种情况比较细节)
  2. WriteBatchInternal::InsertInto 如果出来的状态是并发写入memtable，则自己不是leader且leader已经将数据写入wal，可以将自己的数据写入memtable
  3. write_thread_.ExitAsBatchGroupFollower 判断自己是否是最后一个写入memtable的线程，如果是则需要做最后的处理设置last seq、选出下一个正在等待的线程中的leader继续做group commit逻辑
  4. PreprocessWrite 切换wal，memtable等等写前预处理，从这里开始都是leader的行为
  5. write_thread_.EnterAsBatchGroupLeader 初始化batch group leader信息，处理max_size相关逻辑，CreateMissingNewerLinks(newest_writer)将当前writer链表组成双向链表语义上得到了一个batch
  6. bool parallel 判断是否能并发写memtable，重要条件是所有batch里面没有merge操作
  7. WriteToWAL 写wal
  8. WriteBatchInternal::InsertInto 写memtable，根据是否能并发选择写入方式，两个分支在调用参数上稍有区别，并发就只写当前batch，非并发就leader写所以batch。顺序写分支要先write_thread_.LaunchParallelMemTableWriters(&write_group) 唤醒所有其它writer
  9. should_exit_batch_group = write_thread_.CompleteParallelMemTableWriter(&w) 判断自己是否最后一个写memtable的线程，如果是就调用write_thread_.ExitAsBatchGroupLeader设置下一轮的leader

Compaction

  1. 需要关注的几件事，是否要compact，选择哪些文件compact以及怎样compact
  2. DBImpl::MaybeScheduleFlushOrCompaction 后台自动compaction的入口
  3. LevelCompactionPicker::NeedsCompaction 是否需要compaction，会逐层判断分数是否>1，分数计算在VersionStorageInfo::ComputeCompactionScore
    1. 对于L0，文件个数/level0_file_num_compaction_trigger得到一个分数，total_size/level_max_bytes_[base_level_]得到另一个分数取最大值
    2. 其它level，level_bytes_no_compacting/MaxBytesForLevel(level) 计算分数
    3. MaxBytesForLevel可以来自配置也可能动态算的，动态算法是先到数据量最大一层，然后按乘数因子递减
  4. DBImpl::BackgroundCompaction->LevelCompactionBuilder::PickCompaction 选择需要compact的文件
    1. SetupInitialFiles->PickFileToCompact 先选择startlevel和targetlevel，之前已经根据分数倒排序所以直接拿最上面那层做start，targe直接+1，PickFileToCompact 选择要compaction的文件，首先startlevel根据文件大小倒排然后选最大的，会用ExpandInputsToCleanCut把range overlap的都选进来，但在level compaction似乎没什么用，然后选择合适range空间的output files，GetOverlappingInputs，同样也会ExpandInputsToCleanCut也没啥用。选好后会跳过正在compact的文件。
    2. GetOverlappingL0Files 如果start level是L0逻辑会有区别，需要比较所有文件
    3. SetupOtherInputsIfNeeded->SetupOtherInputs 如果是L0，start在上面一步变化了，output也要相应变化
    4. GetCompaction最终返回一个Compaction对象
  5. CompactionJob::Prepare->GenSubcompactionBoundaries 需要并发的compact会被抽象成sub compactions，这里会解析生成sub compaction以及对应的边界
    1. 原理https://github.com/facebook/rocksdb/wiki/Subcompaction
    2. Compaction::ShouldFormSubcompactions满足条件才做sub compaction，leveled情况下L0的compaction或者kRoundRobin选文件或者手动状况下满足条件
    3. 遍历所有level所有file，生成对应的anchor，一个文件128archor，代表一个范围。然后排序去重
    4. 然后计算sub compaction并把所有的archor平均分，并保存在boundaries_里面
    5. 然后Prepare里面会生成sub compaction的列表sub_compact_states
  6. CompactionJob::Run 遍历sub compaction都放到线程池里面启动多线程compaction其中当前线程会分担sub_compact_states[0]，执行的函数是ProcessKeyValueCompaction。执行完之后应该直接生成sst file没有合并这一步
    1. 实际上每次BackgroundCompaction一般是从start选一个文件output选多个文件，然后多次BackgroundCompaction形成并行关系，满足sub compaction条件之后可以进一步文件内部并行
  7. ProcessKeyValueCompaction 取出subcompaction的kv放到一个迭代器里面(此时会构造堆结构)
    1. VersionSet::MakeInputIterator 对L0每个文件建立一个TableCache::NewIterator对其它层整层建立LevelIterator
    2. NewCompactionMergingIterator 建立堆排序iterator
    3. CompactionIterator->c_iter->SeekToFirst 构建需要使用的iterator
    4. while (status.ok() && !cfd->IsDropped() && c_iter->Valid()) 开始迭代输出
  8. SubcompactionState::AddToOutput 输出到文件
    1. open_file_func 没有builder的情况下新建table builder
    2. BlockBasedTableBuilder::Add 添加数据，flush的时候会创建index block
    3. CompactionJob::FinishCompactionOutputFile->BlockBasedTableBuilder::Finish 写各种index filter block完成文件

DeleteRange

  1. 参考https://rocksdb.org/blog/2018/11/21/delete-range.html
  2. 如果没有delete range，要用delete来做需要seek start, iterate and compare很慢。而且做scan的时候如果tombstone很多要一个个过没法快速跳过会很慢
  3. 基本的解决思路是写入的时候写入range tombstone，在memtable里面是range tombstone，在sst file里面有一个range deletetion block，读的时候通过在range合并之后的天际线里面二分查找快速判断是否删除，如果删除可直接返回
  4. range deletion block存储格式见https://github.com/facebook/rocksdb/wiki/Rocksdb-BlockBasedTable-Format 末尾
  5. compaction或者flush的时候会清理过时的tombstone, tombstone到达sst最底层时可清除因为它就像个罩子来判断它下面层次的数据是否被删除
  6. DB::DeleteRange->DeleteRangeCF->DeleteImpl->MemTable::Add 会选择range_del_table_插入数据
  7. DeleteImpl->CheckMemtableFull 如果memtable满就flush这个带着tombstone的table
  8. ProcessKeyValueCompaction compaction过程迭代inputs
    1. CompactionRangeDelAggregator::AddTombstones 收集input里面的tombstones
    2. 如果是merge操作 MergeHelper::MergeUntil->ForwardRangeDelIterator::ShouldDelete 合并的时候判断key能否从range tombstone里面删除。如果当前key没有快照引用，或者版本比tombstone里面高，tombstone里面都可以删除
    3. 如果是put操作可以直接删除
    4. 没删掉的tombstone通过builder->Finish写入文件

DBImpl::IngestExternalFiles

  1. 参考https://github.com/facebook/rocksdb/wiki/Creating-and-Ingesting-SST-files
  2. ReserveFileNumbersBeforeIngestion 获取下一个可用文件号
  3. ExternalSstFileIngestionJob::Prepare 将待导入文件拷贝/移动到db内部的sst文件中，导入前会判断如果多个文件是否有范围重叠
  4. WriteThread::EnterUnbatched 停写
  5. ExternalSstFileIngestionJob::NeedsFlush 判断是否要flush memtable，逻辑在ColumnFamilyData::RangesOverlapWithMemtables应该是简单的范围比较而不是遍历每个key。然后flush，DBImpl::FlushMemTable
  6. ExternalSstFileIngestionJob::Run 实际ingest逻辑
    1. CheckLevelForIngestedBehindFile 如果有ingest_behind标志，直接尝试放最后一层，如果有key重叠返回失败
    2. AssignLevelAndSeqnoForIngestedFile 从L0往下看每层首先CompactionPicker::RangeOverlapWithCompaction是否和本层正在进行的compaction output的范围冲突，Version::OverlapWithLevelIterator，IngestedFileFitInLevel(两个类似)再检查每个sst file是否有冲突
    3. AssignGlobalSeqnoForIngestedFile 为ingest_file获取global seq no
    4. edit_.AddFile 更新文件元信息到VersionEdit
  7. write_thread_.ExitUnbatched 恢复写入

Version相关

  1. 数据库lsn记录在last_sequence_，在DBImpl::WriteImpl每次写都会增加
  2. DBImpl::GetImpl读取的时候会使用seq构造LookupKey去读，seq来源GetLastPublishedSequence，LookupKey的构造类似于user_key + sequence + type
  3. 这个lookupkey有三种使用方法memtable_key(全部内容)，internal_key(去掉长度描述)，user_key(再去掉sequence和type只留下外部传入的key)
  4. 在memtable里面iterate的时候根据internal_key来寻找第user_key相同internal_key大于等于的key
  5. TableCache::GetFromRowCache row cache在查找的时候会用row_cache_key去查找，row_cache_key的构成是fd_number+seq_no(正常情况可能是0)+user_key。这就清楚了为什么不用update row cache了，其实还是和sst file关联的

性能优化

FileIndexer

  1. 大体思路是上一层确定了key在某个文件的范围，但是又不在这个文件中的时候可以利用这个信息加快下一层的查找。
  2. 可以做一个文件相对位置的索引，上一层的每个文件的start和end对应下一层的文件和位置

减少一次Get过程中的内存拷贝

  1. 问题是之前的版本数据从sst读取之后需要一次copy给返回给用户的变量，那明显的解法是直接返回sst读取之后内存块里面对应的地址
  2. 带来的问题是DataBlockIter本来是填充block cache之后就释放，如果返回地址给读接口，可能读接口拿到值引用时空指针
  3. 解决方案是引入了Cleanable接口，然后DataBlockIter的clean委托给PinnableSlice(Get使用的结构)，等Get使用完了以后一起释放

降低Statistics代价

  1. 使用CoreLocalArray数据结构保证数据不会跨cpu访问

写wal优化

  1. 多线程写wal的时候会有竞争，所以比较好的方式是一个线程收集所有线程的写请求batch写，写完之后通知其他线程继续，可以恢复成多线程写各自的memtable
  2. 这里的线程协调有个很微妙的性能点，leveldb使用在MutexLock里面pthread_cond_wait的方式来让其他线程等待，这样会导致context switch比较重。注意虽然pthread_mutex_lock使用futex有spinlock快速返回的逻辑，但是pthread_cond_wait没有。所以这里需要自定义比较精细的wait逻辑disruptor里面其实也需要
  3. 代码实现在WriteThread::AwaitState，首先busy loop并使用asm volatile("pause")避免cpu流水线重排，如果条件不满足再进入short wait，使用yield，还不行就进入long wait，使用cond.wait()

二分查找cache miss问题

kDataBlockBinaryAndHash

  1. 参考https://rocksdb.org/blog/2018/08/23/data-block-hash-index.html
  2. 简单说就是加个hashmap索引key信息的相对位置

阿里x-engine的解法

  1. 参考https://zhuanlan.zhihu.com/p/114681578
  2. 如果用有序数组存key,value-address,在二分查找过程中要反复跳地址，只要跳动的长度大于cache line的长度就无法使用上次缓存就会cache miss
  3. 解决办法是用两层的b+ tree，b+ tree内节点只存放key所以很紧凑，寻址过程可以充分利用缓存。两层是实践选择

InlineSkipList

  1. 参考RocksDB 源码分析 – InlineSkipList
  2. 节点的指针和key存在一起，上面n层节点指针的位置分别在数组对应的-n,-(n-1),...-1的位置，因为skiplist常用操作是从上层节点一个一个往下找，所以变成了顺序而且局部的内存访问
  3. Splice主要是记录上次insert时候每层的range，如果是顺序插入就可以利用上次的range迅速缩小范围
  4. 并发比较普通，每一层独立做CAS

并发相关

ThreadLocalPtr

  1. 参考https://zhuanlan.zhihu.com/p/398409455
  2. 每个线程一个ThreadData，里面有个vector存储多个thread local数据对象。ThreadData组成链表方便一起处理
  3. ThreadLocalPtr::StaticMeta是个singleton，所有的ThreadLocalPtr都指向它

LRU Cache

  1. LRUCache最外层实体 LRUCacheShard缓存分片 LRUHandle基本存储元素封装k，v
  2. LRUCacheShard::Lookup 读链路，加锁(本分片锁)，ref+1设置hit，没有传统lru的移动位置操作。lookup之后要调用Release
  3. LRUCacheShard::Insert 写链路，参数可带优先级，加分片锁，先看是否需要释放如果需要就先从尾部删除，然后插入table，然后从顺着优先级往下看哪里有空间就插到对应的head上。
  4. LRUCacheShard::LRU_Remove 删除，变化指针以及三个优先级的容量
  5. LRUCacheShard::Release get使用结束以后需要调用release接口，引用计数-1，然后判断引用计数是否=0，=0且容量不足就删除这个节点，=0有容量会调用LRU_Insert插回去。>0就什么都不做
  6. 所以lru的逻辑就是lookup过的item(hit)，在引用变0的时候如果容量够有一次机会从高优先级区开始重新插入，而优先级的逻辑就是低优先级插到队列中间偏后的位置，淘汰的比较快一些
  7. 总结来看是一个比较标准的带分片和优先级的lru实现

Clock Cache

  1. LRU Cache的问题是每次读会导致重新插入，锁竞争激烈
  2. 大致逻辑是，分片，每个分片一个环形队列，释放空间时循环扫描如果entry上次扫描之后又被置了访问标记就清理标记继续，否则就干掉entry。这应该是rocksdb某个版本的实现
  3. 这个简单算法的问题是如果整体访问很多都被置了标志就退化成fifo了，解决方案是Two-Handed Clock，有两个指针，一个负责周期性扫描清理标记，另一个负责看被清理的标记是否又被置位如果置位说明访问频繁，否则可以干掉，扫描速度也可以自调整
  4. Rocksdb的HyperClockCache基本思路也是这样，细节还需要研究

MultiGet为啥快

  1. https://github.com/facebook/rocksdb/wiki/MultiGet-Performance
  2. 少了很多虚函数调用
  3. block index和filter都放在lru里面会有锁竞争，批量访问同一个sst file的key就免了这些竞争，不过clock的方式就没有这问题？
  4. 每次访问sst会访问bloom filter会带来cache miss，batch操作可以用pipeline的方式隐藏cache miss latency，这个技巧比较高端
  5. 单次请求多个访问同一个sst file可以通过io uring的接口io并行访问，多个请求就比较难这样做

存储格式

  1.  sst文件格式 https://github.com/facebook/rocksdb/wiki/Rocksdb-BlockBasedTable-Format
  2. key的存储做了delta压缩，每隔k个key会有一个kv不做delta压缩被称作restart point这个被用来辅助binary search
  3. kv实际存下来shared_bytes:unshared_bytes:value_length:key_delta:value

    和hbase性能比较

    1. hbase get需要寻址region，当然结果可以被缓存
    2. leveled compaction对比类似universal compaction，以及rocksdb的file indexer
    3. hbase hfile是多层index block+data block，rocksdb是block meta block + block(index part+data part) meta block一般常驻内存
    4. block mem 内查找过程 hbase看起来是线性查找，rocksdb是binary+hash辅助
    5. block cache hbase一般存索引节点，rocksdb除了block meta还可以存 data block
    6. rocksdb有row cache
    7. flush 简单ab table vs 多列族导致复杂slab分配
    8. blockcache clockwise vs dumb lru
    9. memtable 超级优化vs ConcurrentNavigableMap
    10. 参考https://bbs.huaweicloud.com/blogs/192853

    问题

    block cache什么时候更新的？

    因为是block级别的所以应该不会被更新，只会随着compaction之类的动作被重置

    row cache什么时候更新的？

    不用更新，查询的时候sst file no会在条件里面

    redis足够快了吗？

    本质说就是一个单线程hashmap get操作，expireIfNeeded->dictHashKey->dictGetVal核心链路就是这样，除了可以干掉expire，让hash算法更简单一点外，似乎没有很大程度优化空间

    speedb

    性能点

    1. 写放大系数降低80%，重写了lsm tree https://www.linkedin.com/pulse/speedb-dramatically-improves-rocksdb-response-times-performance/，这一条似乎缺乏其他资料印证
    2. 读稳定性和p99提升，p99稳定大约是rocksdb的1/4，底层算法提升，compaction动态自适应调整，根据workload调整flush和compaction
    3. speedb认为rocksb读延迟高不是因为lsm tree，而是compaction相关缺乏资源管理

    优化细节

    1. snapshot-optimization https://docs.speedb.io/speedb-features/snapshot-optimization 缓存snapshot，减少获取snapshot锁冲突
    2. Write Flow optimization https://docs.speedb.io/speedb-features/write-flow
      1. rocksdb写wal是append只能单线程，memtable switch会block，写流程中还有其他不少需要全局锁的地方
      2. spdb改变了写流程，独立一个线程处理memtable switch,flush request到memtable,wal switch等等,这个线程用两个container(memtable?不确定)切换。
      3. 多个write batch组成一个batch group，以group级别刷wal，可以多个group并发刷wal
      4. 主要的优化点是db锁变成读写锁，写wal和memtable变成并行，写wal是计算文件位置再写，可以并行。memtable和wal切换都不会有db锁不会block整个流程
      5. 新流程带来的一个复杂度代价是写memtalbe失败需要rollback wal写
      6. 该优化带来近两倍的写吞吐，但个人理解并不能降低cpu使用率
    3. Global Delayed write https://docs.speedb.io/speedb-features/global-delayed-write, 把WriteController从per db变成全局，做全局的流量分配。这个知道就好
    4. Proactive Flushing https://docs.speedb.io/speedb-features/proactive-flushing flush行为不再是被动发生在write调用的时候，判断依据不再是年龄而不顾数据多少
    5. Sorted Hash Memtable https://docs.speedb.io/speedb-features/sorted-hash-memtable 要并发写，fast read，又要能scan，默认数据结构中只有skiplist，shorted hash map的结构是一个concurrent hashmap+一个list，这个list分成无序和多个有序的vector部分，读很简单hash o(1)，写同时写hashmap和无序list，后台线程整理无序list成有序vectors，整理发生在无序size超过10000或者发生scan的时候。不得不说这种根据场景打破常规做法的数据结构比较牛逼。写提升155%，随机读提升50%
    6. Paired Bloom Filter https://docs.speedb.io/speedb-features/paired-bloom-filter
      1. 原始的bloom filter局部性很差，对于一个positive key查询会有k(函数数量)次cache miss
      2. blocked bloom filter是个改进，会把内存划分成blocks，每个block大小等于cache line size(512b)，对于每个key先拿一个函数映射到一个block，再拿k个函数在block内做原始bloom filter。这个是rocksdb的默认实现方式
      3. 但问题是随着key的位数增长，fpr增加得比较多，核心原因是每个block的key的数量差异很大
      4. 解决方式是通过pair来减少key的数量差异，先做block映射，然后把block分片成很多batch，一个batch 128 block，然后通过batch内通过block key的数量排序block首尾匹配成64个pair，key的前k/2个函数映射到一个block，后k/2映射到paired block,block在batch中的位置需要额外几位来存
      5. Ribbon filter比较省内存，但是耗4-6倍cpu，所以看场景
      6. 随机读比默认算法吞吐翻倍
    7. Range Delete Improvement https://docs.speedb.io/enhancements/remove-single-delete-elements-during-memtable-flush 原来的实现delete range的key还是会flush到sst，这个变更在flush过程中会过滤，一个比较细节的提升
    8. Dynamic Delayed Writes https://docs.speedb.io/enhancements/dynamic-delayed-writes 更精细的delayed write rate计算方式让变化更线性
    9. Reduce switch memtable latency https://docs.speedb.io/enhancements/reduce-switch-memtable-latency 提前准备用于switch的memtable，在切换的时候更平滑，但是要付出额外内存的代价


    参考链接


    发帖者 时间： 没有评论:
    订阅： 博文 (Atom)