# MemTable ## ImmutableMemtableOptions - **`memtable_prefix_bloom_bits`**：`uint32_t`，布隆过滤器大小 - 等于 `write_buffer_size * memtable_prefix_bloom_size_ratio` - 虽然叫 prefix，也涵盖了 key 整体的 filter - 默认 0， 表示不启用 memtable 的过滤器 - **`memtable_whole_key_filtering`**：`bool`，来自 `AdvancedColumnFamilyOptions` - 布隆过滤器是否包含了 whole keys（相对于 key prefixs） ，默认 false - **`arena_block_size`**: `size_t`，来自 `AdvancedColumnFamilyOptions` - **`memtable_huge_page_size`**：`size_t`， 来自 `AdvancedColumnFamilyOptions` - 配置大于 0 表示启用，会先从 huge page 中分配内存（包含 arena 和 bloom filter） - 默认为 0 不启用，从 malloc 分配内存。 <br> - **`protection_bytes_per_key`**：来自 `AdvancedColumnFamilyOptions` - 每 KV 额外存储 checksum，防止内存损坏，默认不启用 - **`inplace_update_*`**: inplace update 相关配置，默认不启用 - 启用后无法保证快照语义。见 `AdvancedColumnFamilyOptions::inplace_update_support` 的说明。 ## MemTable 关键成员 - **`id_`**：cf 内自增的 id - **`table_`**：`unique_ptr<MemTableRep>`，存储普通 KV 数据 - **`range_del_table_`**：`unique_ptr<MemTableRep>`，存储 range deletions - **`bloom_filter_`**：`unique_ptr<DynamicBloom>`，布隆过滤器，可能为空 - **`first_seqno_`**：`atomic<SequenceNumber>`, 第一个 Insert 的 KV 的 seqnum - **`earliest_seqno_`**：`atomic<SequenceNumber>`，创建时 DB 的 seqnum - 等于 `kMaxSequenceNumber` 表示未设置 - 设置后，insert 到此 memtable 的数据保证大于等于它 - **`write_buffer_size_`**: `atomic<size_t>`，memtable 大小，当没配置过滤器时可动态更改 - **`arena_`**: `ConcurrentArena`，给数据、过滤器分配内存。 - **`flush_state_`**：`atomic<FlushStateEnum>` - 三个枚举值： - `FLUSH_NOT_REQUESTED`：不需要 flush - `FLUSH_REQUESTED`：需要 flush - `FLUSH_SCHEDULED`：已经放入 FlushScheduler - **`fragmented_range_tombstone_list_`**：`unique_ptr<FragmentedRangeTombstoneList>` - [Fragment memtable range tombstone in the write path](https://github.com/facebook/rocksdb/pull/10380/) - 变成 immutable 时生成，用于加速 range tombstones 的查询 - **`cached_range_tombstone_`**： - [Cache fragmented range tombstone list for mutable memtables](https://github.com/facebook/rocksdb/pull/10547) - **`mem_next_logfile_number_`**：`uint64_t` ^ce1bad - 当 memtable 冻结时（SwitchMemtable中），创建的新 WAL。 - 当 memtable flush 后，编号小于它的 WAL 就不要 recover 了。 - 比当前 memtable 新的数据只会写入到大于等于 `mem_next_logfile_number_` 的 WAL 中 ## BatchPostProcess() - 仅用于并行写 Memtable 时，每个 writer / batch 累积自己的写入计数到 `MemTablePostProcessInfo`，batch 写完后将计数一次性纳入到 Memtable 的计数中 - 内部会 `UpdateFlushState()` 检查和更新 flush 状态 ## ShouldFlushNow() - 检查 memtable 是否应该 flush。 - **Flush 条件**： - `num_range_deletes_` 大于 `memtable_max_range_deletions_`选项限制 - 选项来自 `ColumnFamilyOptions`，默认为0，表示无限制 - [#11358](https://github.com/facebook/rocksdb/pull/11358) - 已分配的内存大于阈值 - 这个阈值略大于 `write_buffer_size`，因为 arena 会多分配 - [ ] 分析 heuristic way： > flush when arena has allocated its last and the last is "almost full" ## UpdateFlushState() - 通过 `ShouldFlushNow()` 判断是否需要 Flush，如果需要，则将 `flush_state_` 设置为 `FLUSH_REQUESTED` - 调用时机： - 非并行写 Memtable 时，每次 Add 写入时调用 - 并行写 Memtable 时，每个 batch 写完后通过 `BatchPostProcess`调用 ## ShouldScheduleFlush() - 返回 true 如果 `flush_state_` 为 `FLUSH_REQUESTED` ## MarkFlushScheduled() - CAS 将 `flush_state_` 从 `FLUSH_REQUESTED` 变为 `FLUSH_SCHEDULED`，返回是否成功。 ------- # MemTableInserter - 继承了 `WriteBatch::Handler` ，用于遍历 WriteBatch，插入到 Memtable 中。 ## 核心成员 - **`mem_post_info_map_`**：`Map<Memtable*, MemTablePostProcessInfo>` - 缓存插入过程中每个 Memtable 的计数（`data_size`，`num_entries`，`num_deleted`等） - 插入完成后，统一处理。 - **`cf_mems_`**: `ColumnFamilyMemTables*`，来自 DBImpl，用于获取各个 cf 当前的 memtable - **`flush_scheduler_`**: `FlushScheduler*`，来自 DBImpl - **`trim_history_scheduler_`**：`TrimHistoryScheduler *`，来自 DBImpl ## PostProcess() - 当 `concurrent_memtable_writes`为 true 时，batch insert 完后调用 - 针对 `mem_post_info_map_`中的每个 memtable 调用 `Memtable::BatchPostProcess` - 累积计数 - 检查是否需要 flush ## CheckMemtableFull() - 检查当前 cf 的 memtable，每次写入（put/delete）时调用。 - memtable 是否需要 flush： - 调用 `Memtable::ShouldScheduleFlush()` - 如果需要，将当前 cf 加入到 `flush_scheduler_`队列 - 检查 memtable list 是否超过 `max_write_buffer_size_to_maintain` - transaction 相关，参数默认为0，表示不检查 [#5022](https://github.com/facebook/rocksdb/pull/5022) - 超过后，将当前 cf 加入到 `trim_history_scheduler_`队列 --- # MemTableListVersion - 某一时刻的 immutable memtables 列表。 - 该类非线程安全。需要外部进行同步控制（例如通过 db mutex 或者在 write thread 内操作）。 ## 关键成员 - **`memlist_`**：`std::list<MemTable*>`，没有 flush 的 immutable memtables - ==新==加入的在链表头部 - **`memlist_history_`**：`std::list<Memtable*>`，已经 flush 的 memtables，额外保留它们用于事务检测写冲突。 - 新加入的在链表头部 ## Remove() - 从 `memlist_` 中删除一个 memtable - 从链表移除，将 memtable 标记为 Flushed（`m->MarkFlushed()`) - 如果需要维护 history（事务需要），则放入 `memlist_history_`，否则进行 Unref - Unref 为 0 则放其入待删除列表 ## Add() - 往 `memlist_` （前面）添加一个 memtable ------ # MemtableList - 存储了对所有 immutable memtables 的引用。 - 如果有多个，可以并行 flush，但写入 manifest 时需要 FIFO 有序（recover需要）。 - 除了部分原子变量，该类非线程安全（需要 db mutex 保护或者在 write thread 内操作）。 - 与 MemTableListVersion 的关系： - MemTableListVersion 相当于 Version - MemtableList 相当于 VersionSet（多版本） ## 关键成员 - **`current_`**： `MemTableListVersion *`，最新版本的 memtable list - **`imm_flush_needed`**：`atomic<bool>`，是否需要 flush - **`imm_trim_needed`**：`atomic<bool>`，是否需要 trim history - **`num_flush_not_started`**：`int`，还没有开始 flush 的 memtables 数量 - **`commit_in_progress_`**： `bool`，是否正在提交 flush 的结果 - **`flush_requested_`**：`bool`，标记，外部请求对 memtable 进行 flush - **`current_memory_usage_`**：`size_t`，当前的内存使用量 ## IsFlushPending() - 返回 true，如果有 memtable 需要 flush，但还没开始。 - 条件（需要同时满足）： - `flush_requested_`为 true - `num_flush_not_started_ > 0` - `num_flush_not_started_ > min_write_buffer_number_to_merge` ## IsFlushPendingOrRunning() - 是否有 memtable 需要被 flush 或者正在 flush ## PickMemtablesToFlush() ^b51817 - 入参： - **`max_memtable_id`**: `uint64_t`，只挑选小于此 ID 的 memtables - 从 `current_->memlist_`的末尾开启遍历挑选，满足以下条件 - id 小于等于 `max_memtable_id` - memtable 的 `flush_in_progress_`标志为 false（即没有正在被 flush） - 避免挑选不连续的 memtables（比如两个链表元素中间有个不满足条件的，就停止挑选） - 被挑选的 memtable 会设置其 `flush_in_progress_`标志为 true - 每次调用都会选择最旧的还没 flush 的 memtable。 ## InstallNewVersion() - 修改 memtable list 的前置操作，多版本下的写时拷贝。 - 从当前 `current_` 克隆创建新的 MemTableListVersion，设置为新的 `current_` - 如果 `current_` 的引用为 1， 则表示只有自己持有，不需要拷贝 ## Add() - 入参：`Memtable *m` - 将一个 memtable 加入到 immutable list - 操作流程 1. `InstallNewVersion()`克隆 `current_` 2. 将 m 加入到 `current_->memlist_` 3. 将 m 表示为 immutable： `m->MarkImmutable()` 4. `num_flush_not_started_` 加 1，如果是 从 0 加到 1，标记 `imm_flush_needed` 为 true ## RemoveMemTablesOrRestoreFlags() - flush 完写入到 MANIFEST 后调用 - 操作的 memtables 范围：`memlist_`末尾的 `batch_count` 个（对应提交的范围） - 根据提交操作返回的 status 做不同的操作： - 如果 status 是 ok 的：从 `memlist_` 中移除这些 memtables - 否则：恢复它们的 `flush_completed_` 等标记，以便可以再次 flush ## TryInstallMemtableFlushResults() ^d8e92e - flush 成功后提交给 manifest，并删除被 flush 的 imm - 有可能其他线程也在提交，此时就会直接返回成功。 - 入参： - **`mems`**: `vector<Memtable*> &`，flush 成功的 memtables - **`file_number`**：`uint64_t`，flush 生成的 SST 文件编号 - 函数进入时已经持有 db mutex，中间`LogAndApply`内会释放后再重新获取。 - 执行流程： 1. 依次设置各个 `mems`的 `flush_completed_` 标记和 `flie_number_`字段 - 即使因为冲突自己没提交成功，其他线程看到这些状态也能代替提交 2. 检查和设置 `commit_in_progress_` 标记 - 如果之前为 true，则表示已经有其他线程在 commit，直接返回。 3. 从 `current_->memlist_`末尾（从旧到新）提交已经 flush 完成的 memtable - 如果有 memtable 的 `flush_completed_` 为 false，则退出（由其他线程提交） - 必须从旧到新==有序提交== - 调用 `VersionSet::LogAndApply()` 提交给 Manifest 4. 提交后调用 `RemoveMemTablesOrRestoreFlags()`，成功则删除 memtables，否则取消相关标记，重试 flush。 ## InstallMemtableAtomicFlushResults() --- # WriteBufferManager - 用于实现多 CF，多 DB 整体的内存使用限制。 - 可以通过 `DBOptions::write_buffer_manager` 为多个 DB 实例指定同一个 manager。 - 默认：一个 DB 一个 WriteBufferManager - `db/db_impl/db_impl_open.cc` SanitizeOptions 函数中创建 - 创建时的关联配置：`DBOptions::db_write_buffer_size` - 默认为 0 ，表示内存无限制。 ------- # TODO - [ ] inplace_update_support - [x] SwitchMemtable - leader writer 调用 `DBImpl::PreprocessWrite()` 时 - [ ] https://github.com/facebook/rocksdb/pull/6146 - memtable 的释放是否在后台，内存占用是否可能增加，内存统计是否能看到这部分内存 - [ ] Memtable merge - [ ] hint_per_batch - [x] skyline: https://rocksdb.org/blog/2018/11/21/delete-range.html - [ ] trim history 的调用时机，flush job中是否会调用 - [ ] mempurge - https://github.com/facebook/rocksdb/pull/8454 (prototype) - https://github.com/facebook/rocksdb/pull/8628 - https://github.com/facebook/rocksdb/pull/8656