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基本思路也是这样，细节还需要研究

存储格式

  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算法更简单一点外，似乎没有很大程度优化空间

    参考链接


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