Overview
Week1：Mini-LSM
Memtable
tasks
- 基于现有的无锁 SkipList，实现 memtable 的 get 和 put 接口；
- 为 LsmStorageInner 实现 get、put 和 delete 接口，只需考虑将请求分派到当前 memtable；
- 当 memtable 大小达到阈值时，需冻结成 immutable memtable，并创建新的 memtable；
- 当有 memtable 和多个 immutable memtable 存在时，完善 LsmStorageInner 的 get 接口；
Questions
为什么 memtable 不提供 delete API？
memtable 的 delete 没有意义。在 LSM 的查找过程中，需要查找 memtable->immemtable->sst，因此，delete 无法减少后续对 immemtable 和 sst 的查找，反而 delete 后，在后续的 get 操作时可能错误地取得一个过期数据；
是否可以使用其他数据结构作为 LSM 中的 memtable？使用跳跃列表的优点/缺点是什么？
（1）可以使用红黑树，B+ 树替代；
（2）优点：平均查询时间较低，为 O(logn)；范围查询时间较低，为 O(logn)；缺点：平均插入时间较高，为 O(logn)；依赖随机化策略，因此性能可能退化成 O(n)；需要额外的空间存储结点指针；（n 为 memtable 中的 kv 对数量）
为什么我们需要
state和state_lock的组合？我们可以只使用state.read()和state.write()吗？多个线程在 append 数据时同时触发 freeze，需要使用 state_lock 同步 state 状态的修改，否则将出现未达到阈值的新建立的 memtable 被错误 freeze；
为什么存储和查询 memtables 的顺序很重要？如果一个 key 出现在多个 memtables 中，你应该返回哪个版本给用户？
在 LSM 中，所有操作都是 append 的，因此只有最近的操作结果是有效的；
返回最新的 memtable 中的结果；
memtable 的内存布局是否高效/是否具有良好的数据局部性？ （想想
Byte是如何实现并存储在skiplist 中的……）有哪些可能的优化可以让 memtable 更加高效？并不具备好的数据局部性，因为 memtable 中的 k 或者 v 只是存储指针，而它们之间的顺序也仅是通过链表连接，随机 IO 比较多；
预先分配大片连续空间以供 memtable 使用；
在本教程中使用
parking_lot锁。它的读写锁是公平锁吗？如果有一个写入器等待现有读取器停止，那么尝试获取锁的读取器可能会发生什么情况？是公平锁；等待时间最长的将获得锁。
冻结 memtable 后，是否有可能某些线程仍然保留旧的 LSM 状态并写入这些不可变的 memtable？您的解决方案如何防止这种情况发生？
不会；通过 state.write() 锁；
Merge Iterator
tasks
- 实现 memtable 迭代器，包含：
key,value,next和is_valid函数；为 memtable 实现 scan 接口，返回值即 memtable 迭代器； - 实现 merge 迭代器，通过多个 memtable 的迭代器进行构建，较新的 memtable 中的数据将覆盖较旧的 memtable 中的相同键数据；
- 继续向上封装 LsmIterator 和 FusedIterator；（LsmIterator 在调用 next 时，需要跳过 value 为空的迭代器）
- 实现 LSM 的 scan 接口，当前仅需考虑 memtable 和 immemtable；
Block
Note
Block 编码格式
1 | ---------------------------------------------------------------------------------------------------- |
1 | ----------------------------------------------------------------------- |
tasks
实现 SST 块编码，块解码和块迭代器；
- 实现 SST 中最小单元 Block 的构造器和编解码；
- 实现 Block 迭代器，在创建时可以定位第一个 key 或者指定 key，指定 key 时将使用间接索引 offset 进行二分查找快速定位；
Questions
在块中寻找密钥的时间复杂度是多少?
O(logn)；
当您在实现中查找不存在的键时，光标会停在哪里？
num_of_elements 处；
Block 的 kv 对数量是多少？
block.offsets.len()；
Block 可以包含重复 key 吗？
可以，在二分查找指定重复 key 时，光标将达到该 key 首次出现的位置；
如果用户添加大于目标块大小的 key 会发生什么？
如果该 key 是块的第一个键，则被允许，且该块仅包含这一个 kv 对；如果不是块的第一个键，则无法添加；
考虑 LSM 引擎构建在对象存储服务 (S3) 上的情况。您将如何优化/更改块格式和参数以使其适合此类服务？
增大目标块大小至 MB 级，以减少对象存储的访问次数；
SST
Note
SST 编码格式
1 | ------------------------------------------------------------------------------------------------------------------------------------------------------- |
tasks
- 实现 SST 构建器，SST 元数据编解码；
- 实现 SST 迭代器，且可定位指定 key（在 SST 层面基于 Block 的 first key 进行二分查找，再在 Block 内部进行二分 seek）；
- 实现块缓存（每个 SST 独立维护各自的 block cache）；
Questions
在 SST 中查找 key 的时间复杂度是多少？
O(log(m) + log(n))；其中 m 是 SST 中的 block 数量，n 是 block 内部 key 的数量；
当您在实现中查找不存在的 key 时，光标会停在哪里？
第一个大于该 key 的位置；
是否可以（或有必要）对 SST 文件进行就地更新？
没必要，原地更新成本太大，所在 block 的读写放大，以及如果 value 长度改变了，后续的 Meta Section 信息需要大量修改；
SST 通常很大（即 256MB）。在这种情况下，复制/扩展
Vec的成本将是巨大的。您的实现是否提前为 SST 构建器分配了足够的空间？你是如何实施的？在构建 SST 时，根据 estimated_size() 预分配容量；
是否可以在 LSM 引擎中存储列式数据（即包含 100 个整数列的表）？当前的 SST 格式仍然是一个不错的选择吗？
考虑 LSM 引擎构建在对象存储服务（即 S3）上的情况。您将如何优化/更改 SST 格式/参数和块缓存以使其适合此类服务？
块存储可以不再局限内存，亦可以包括本地 SSD；
Read Path
tasks
- 实现
TwoMergeIterator<X, Y>，其中 X 和 Y 分别是内存中 memtable 的合并迭代器和磁盘中 SST 的合并迭代器；简单使用一个标志来标记当前需要读取哪个迭代器（每次TwoMergeIterator.next()后需要保证 X 和 Y 的迭代器头部 value 不为空，再通过比较 X 和 Y 的首个 key 的大小决定标记值）； - 有了 SST 后，修改 Mini-LSM 的 scan 接口；（对每个 memtable 做 scan，对每个 SST 做 seek_to_key，再将 memtable 的合并迭代器和 SST 的合并迭代器合并成 TwoMergeIterator）
- 接着修改 Mini-LSM 的 get 接口；（依次对 memtable 做 get，再对每个 SST 做 seek_to_key，多个 SST 迭代器合并，check 合并迭代器的队首元素）
Write Path
tasks
- 将 memtable 刷新到 SST；（当 imm_memtabls 数量达到阈值时，后台 flush 线程通过 SsTableBuilder 将最早的 imm_memtable 刷新成一个 SST）
- Flush Trigger；
- Filter the SSTs；（每个 SST 有 first_key 和 last_key 信息，因此在 get 和 scan 时，可以检查是否在 first_key~last_key 范围内，从而过滤不可能的 SST，减轻读放大）
Questions
如果用户两次请求删除某个密钥会发生什么？
存在两条 “key: EMPTY” 记录；
SST Optimizations
Note
有了布隆过滤器后，SST 编码格式
1 | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
tasks
- 布隆过滤器；（每个 SST 有一个独有的布隆过滤器，创建 SST 的同时，根据 SST 中的所有 key 来确定布隆过滤器所需 hash 函数个数、总位数以及各个位置的 bit 值，作为只读过滤器）
- 在 get 路径上使用布隆过滤器，减轻 SST 的读放大；（在 key_with_sst 的基础上，查询只读过滤器，如果一定不存在，则可以跳过该 SST 的读取）
- 使用前缀编码节省 block 的磁盘存储成本；（block 的 first_key 作为标杆，后续每个 key 使用
key_overlap_len (u16) | rest_key_len (u16) | key (rest_key_len)进行压缩，如某个 block 中第一个 key 为mini-something，该 block 中另一个 key 为5|3|LSM，则解码后为mini-LSM）
Questions
布隆过滤器如何帮助 SST 过滤过程？它可以告诉您有关密钥的哪些信息？ （可能不存在/可能存在/必须存在/必须不存在）
通过多个哈希函数，将 key 映射到多个 bit，并将这些 bit 置为 1；后续在判断 SST 中是否可能存在某个 key 时，检查查询 key 对应的 bit 位置是否全为 1，如果全为 1，则 可能存在，否则，必定不存在；
考虑我们需要一个向后迭代器的情况。我们的密钥压缩会影响向后迭代器吗？
不会，按需解码即可；
您可以在扫描时使用布隆过滤器吗？
理论上可以，但需要对扫描范围的所有 key 进行判断，且只要范围内有一个 key 存在，也将需要读取对应 SST，因此得不偿失；
对相邻键而不是块中的第一个键进行键前缀编码可能有什么优点/缺点？
优点：因为相邻键公共前缀长度往往更大，因此大概率可以节省更多的磁盘空间；
缺点：频繁点查时需要从 block 的第一个 key 开始读起，以解码中间位置的真实 key 值，将导致点查时间成本过高；范围查询接近第一个键前缀编码，但也会有些微时间性能损失。
Week 2：Compaction + Persistence
Overview
Compaction Implementation
将 L0 SSTs 合并到一个 sorted run （每个 SST 都不包含重叠的 key 范围，且依次按照它们的首 key 有序）中；（从 L1 开始往下，每一层可以理解成是一个 sorted run）
tasks
- 实现 force_full_compaction，定期对 L0 和 L1 进行 full compaction，压缩后的 sorted run 加入 L1 层；（从 L0 和 L1 的合并迭代器中创建有序压缩后的 SST 磁盘文件->获取 LsmState 快照->从 LsmState 快照中删除压缩前的 L0 和 L1 SST 内存结构->向 LsmState 快照中添加压缩后的 SST 内存结构->使用 LsmState 快照更新 LsmState->删除压缩前的 L0 和 L1 的 SST 磁盘文件）
- 由于从 L1 开始往下都是 sorted run，因此对于它们无需使用基于堆的 MergeIterator，仅需使用一个串联迭代器进行简化；
- 有了 L1 层后，完善 LSM 的 scan 和 get 接口；
Questions
读/写/空间放大的定义是什么？
读放大系数：对磁盘发起的实际读取数据量 / 上层应用实际需要的数据量；
写放大系数：对磁盘发起的总写入数据量 / 上层应用发起的总写入数据量；
空间放大系数：磁盘的总占用空间 / 上层应用逻辑视图的总数据量；
有哪些方法可以准确计算读/写/空间放大，以及估计它们的方法是什么？
读/写放大往往可以较为准确地进行估计，参考上面的两种系数定义；
空间放大不好估计，因为对于存储引擎来说，无法探测上层应用实际使用的数据量大小，一个简易的估计方式是：在稳定的工作负载模式下，用户的新增数据量和删除数据量应该接近，即用户实际使用的数据量从某时开始不再发生变化，因此，最后一层的 SST 包含用户数据在某个时刻的快照。因此，空间放大可以简易估计为 磁盘的总占用空间 / 最后一层SST所占用的空间；
即使用户请求删除密钥也会占用一些存储空间，这是否正确？
正确，由于 LSM 引擎不原地更新，因此 delete 操作必须记录下来；在后续进行 compaction 时，可以不再进行保存；
使用/填充块缓存进行压缩是个好主意吗？或者压缩时完全绕过块缓存更好？
不是一个好主意；完全绕过更好。
压缩完成后，先前进行压缩的 SST 将被删除，因此对应的块缓存将不再被使用，压缩过程中填充块缓存将变得没有意义。当然，在这个过程中使用原有块缓存可以一定程度上加速压缩的速度，或许一个好的方式是压缩过程中使用完的块缓存直接从内存中主动删除，腾出宝贵的缓存空间。
系统中拥有
struct ConcatIterator<I: StorageIterator>是否有意义？有意义；从 L1 往下都是 sorted run，因此，无需使用基于堆的 MergeIterator 对整层 SST 进行合并，从而加快从迭代器中读取和 seek key 的速度；
Simple Leveled Compaction
实现经典的分级压缩算法并使用压缩模拟器来查看其工作效果如何；
tasks
- 实现简单的分级压缩：当 L0 层的 SST 数量达到阈值，将 L0 和 L1 进行压缩并加入 L1 层；L(n+1) / L(n) 小于某一阈值时，将 L(n) 和 L(n+1) 层进行合并并加入 L(n+1) 层；
- 现在有了 L2… 等层，需要进一步完善 LSM 的 get 和 scan 接口；（注意：从 L1 开始往下，它们各自都是 sorted run，因此每一层可以使用 SstConcatIterator 创建串联迭代器）
Questions
分级压缩的估计写入放大是多少？
分级压缩的估计读取放大是多少？
仅当用户请求删除某个密钥并且该密钥已在最底层进行压缩时，该密钥才会从 LSM 树中清除，这是否正确？
正确；如果在较高层压缩时面对 delete 操作直接将 key 清除，在后续底层的压缩过程中，可能出现旧值覆盖原本 delete 操作的情况；
定期对 LSM 树进行完全压缩是一个好的策略吗？为什么或为什么不呢？
不好；全量压缩非常耗费 CPU 和 IO 资源，影响存储引擎的服务质量；
积极选择一些旧文件/关卡进行压缩，即使它们不违反层级放大器也会是一个不错的选择，是吗？
是的，可以进一步减少空间放大和读放大；
如果存储设备能够实现可持续的1GB/s写入吞吐量，并且LSM树的写入放大为10倍，那么用户可以从LSM键值接口获得多少吞吐量？
十分之一的吞吐；
如果L2中有SST文件，可以直接合并L1和L3吗？它仍然产生正确的结果吗？
不可以；如果将合并后的结果加入 L1 层，则会导致 L3 的旧值可能覆盖 L2 的较新值，如果合并后的结果加入 L3 层，可能导致 L2 的旧值覆盖 L1 的较新值；
到目前为止，我们假设我们的 SST 文件使用单调递增的 id 作为文件名。可以用吗
<level>_<begin_key>_<end_key>.sst作为 SST 文件名？这可能存在哪些潜在问题？对于 L0 层的 SST，可能会有同名情况，以及在从磁盘文件恢复 LsmState 时，无法判断哪个文件是最新的。
Tiered/Universal Compaction
实现 RocksDB 通用压缩算法并了解其优缺点；
Leveled Compaction
实现 RocksDB 分级压缩算法。该压缩算法还支持部分压缩，以减少峰值空间使用；
Manifest
把 LSM 状态存储在磁盘上并从该状态中恢复；
Write-Ahead Log (WAL)
用户请求将被路由到 memtable 和 WAL，以便所有操作都将被持久化；
Write Batch and Checksums
为所有存储格式实现批量写入 API（为第 3 周的 MVCC 做准备）和校验和；