Mini-LSM Week1 Day3 Day4

(Updated: )
KV
,

要点解析

没啥好说的,就是按照任务要求,编码Block,SST,解码Block,SST,并且对外提供Iteartor

数据编码都使用定长编码,方便编码解码
Data Block

1
2
3
4
5
6
7
8
9
10
11
12
----------------------------------------------------------------------------------------------------
|             Data Section             |              Offset Section             |      Extra      |
----------------------------------------------------------------------------------------------------
| Entry #1 | Entry #2 | ... | Entry #N | Offset #1 | Offset #2 | ... | Offset #N | num_of_elements |
----------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------
|                           Entry #1                            | ... |
-----------------------------------------------------------------------
| key_len (2B) | key (keylen) | value_len (2B) | value (varlen) | ... |
-----------------------------------------------------------------------

SST: Meta Section数据编码由用户定义

1
2
3
4
5
6
7
8
9
-------------------------------------------------------------------------------------------
|         Block Section         |          Meta Section         |          Extra          |
-------------------------------------------------------------------------------------------
| data block | ... | data block |            metadata           | meta block offset (u32) |
-------------------------------------------------------------------------------------------
// Meta Section自定义布局如下
// Entrys + num of entry
// Entry: offset(u32) + first key len(u16) + first key + last key len(u16) + last key

需要注意的点:

  • 第三方库bytes::{Buf,BufMut}提供了方便的数据编码解码函数,如何put_u16,get_u16等,不要自己手动编解码。
  • 在有序列表/数组中查找第一个符合条件的idx时,rust标准库提供的partition_point非常方便

思考

  • 在块中查找键的时间复杂度是多少？
    • O(log n) ; n 是键值的数量, 使用二分查找
  • 在你的实现中，当你查找一个不存在的键时，游标停在哪里？
    • 第一个比该键大的位置,当然也可能是末尾
  • 所以 Block 只是原始数据的向量和偏移量的向量。我们能否将它们更改为 Byte 和 Arc<[u16]>，并将所有迭代器接口更改为返回 Byte 而不是 &[u8]？（假设我们使用 Byte::slice 返回块的切片而不复制。）优缺点是什么？
    • 现有实现非常方便序列化到磁盘,并且可以有效减少数据拷贝
    • 改成Byte尚且能理解，有利于跨线程管理和异步IO,但是没必要
    • 改成Arc<[u16]>太难绷了, 这也要用智能指针吗??
  • 在你的实现中，写入块中的数字的字节序是什么？
    • CPU默认字节序
  • 你的实现是否容易受到恶意构建的块的影响？如果用户故意构造一个无效的块，是否会有无效的内存访问或 OOM？
  • 一个块可以包含重复的键吗？
    • 不能,一个块对应一个SST的一部分,SST内部的KV是唯一的
  • 如果用户添加一个大于目标块大小的键会发生什么？
    • 如果是目标块的第一个Key,会被保存到目标块;否则会拒绝服务
  • 考虑 LSM 引擎构建在对象存储服务（S3）上的情况。你将如何优化/更改块格式和参数以使其适合此类服务？
    • S3特性: 高延迟(10-100ms), 按Get/Put计费, 带宽有成本
    • 适当加大块大小, 减少Get请求的次数, 摊销延迟
  • 在 SST 中查找键的时间复杂度是多少？
    • O(1) / O(logn) : 首先查找固定数量的BlockMeta,确定Key在哪个块;如果不存在,时间复杂度为O(1);如果存在,在块中二分查找,时间复杂度为O(logn)
  • 在你的实现中，当你查找一个不存在的键时，游标停在哪里？
    • 第一个大于等于该键的位置(也可能是末尾)
  • 是否可能（或必要）对 SST 文件进行原地更新？
    • 没有必要: 由于SST有序,以及新旧KV的长度不一定一致,更新一对KV可能导致后续的数据全部需要重新写入,对应的索引也需要重新写入
  • SST 通常很大（例如 256MB）。在这种情况下，复制/扩展 Vec 的成本将很高。你的实现是否为 SST 构建器预先分配了足够的空间？你是如何实现的？
    • 目前没有预留,后续可以优化: 根据Block和BlockMeta的方法estimated_size来获取大小并手动预留容量
  • 查看 moka 块缓存，为什么它返回 Arc<Error> 而不是原始的 Error？
    • 为了在并发环境下高效地共享错误
  • 使用块缓存是否保证内存中最多有固定数量的块？例如，如果你有一个 4GB 的 moka 块缓存和 4KB 的块大小，内存中是否会有超过 4GB/4KB 数量的块同时存在？
    • 不能,因为moka并发写入时可能会短暂超过限制,随后异步/延后淘汰写回
    • 不会,因为除了块开销外,moka内部的哈希结构和指针等都有内存开销
  • 是否可以在 LSM 引擎中存储列式数据（即 100 个整数列的表）？当前的 SST 格式仍然是一个好的选择吗？
    • 可以存,但是效率不高; 因为目前的磁盘结构是依次顺序存储输入的KV,因此一个Key实际上对应一行,做聚合查询某一列时效率很低,读取放大严重
    • 如果Mini-LSM加入Column Family功能并且使用Key + 列号当主键, 当前的存储格式依旧可用
  • 考虑 LSM 引擎构建在对象存储服务（即 S3）上的情况。你将如何优化/更改 SST 格式/参数/块格式和块缓存以使其适合此类服务？
    • S3存储与本地磁盘存储的对比 S3-VS-LocalSSD
    • 利用 S3 Multipart Upload 分段并行上传，单次 GET 用 Range Read 取需要的 block
    • 增大块尺寸到64KB-256KB,SST尺寸到256MB-1GB: S3按调用次数+网络带宽等计费, 如果SST文件过小，合并时需要访问的文件很多，那么费用会很高
    • 增加Index Block + Bloom Filter: 显然全量加载SST带来的网络带宽挤占,以及内核波动是不可接受的, 肯定是分段读取；添加Bloom Filter用于过滤,减少查询次数; 添加Index Block用于快速定位; 这两者最好只读取一次,随后全量驻留内存
    • 使用二级索引: 如果SST尺寸达1GB,那么Index Block尺寸也会多达10+MB,这时需要引入二级索引,用于索引Index Block且常驻内存来减少开销