KV数据库引擎开发

KV数据库引擎开发.md

原始(Instinct)

• WAL
• 每一次读取时, 扫描整个 wal

问题:

• wal 无序, 只能顺序扫描
• 数据存在多个版本, 所以必须扫描完整个 wal 文件
• 数据多版本, 浪费空间
• 无法利用局部性原理

写缓冲

缓冲多次写操作, 合并同一个 key 多次操作, 便可减少写 IO.

问题:

• 操作返回时还未持久化
• key, value 持久化先后顺序不确定, 需要进行数据修复

读Cache

启动时加载全部 key 到 cache, 写时维护 key cache

问题:

• 加载全部 key 会很慢, 虽然只加载一次
• 内存占用可能过多

Compact

1. 消除多数据版本, 只保留一个版本
2. 数据有序组织, 利用局部性原理

问题:

• Compaction 本身消耗资源(读, 写)

Cache摘要

考虑内存占用问题, 内存中只保留 key 的摘要(crc32, hash). 因为摘要有可能冲突, 所以采用开放链式结构.

问题:

• 写入时, 如果摘要有冲突, 需要读出摘要对应的所有 key, 比较后才能知道 key 本身是否有冲突, 以决定替换链表中的节点或是新增节点
• 似乎就是 B+ 树, 不断地加索引层级, 但只有叶子节点才是真正的最终数据

wal 拆分

按 range 拆分 key wal, 否则每一次都 compact 全量 key, 成本太高.

问题:

• 拆分过程中, 将产生重叠的文件, 需要维护文件的新旧关系

wal 异步分裂

如果分裂操作是同步的, 将阻塞正常请求. 在分裂过程,

1. 将目标文件设置为只读
2. 将数据写到统一的文件 key.wal
3. 分裂完毕
4. 停止 key.wal 写, 锁定新的目标文件, 将 key.wal 中的内容转存到新目标文件
5. 删除 key.wal
6. 解锁新目标文件

异步 compact

因为在写流程中做 compact 会拖慢写操作, 所以, 异步地进行 compaction.

问题:

• compaction 过程, 数据需要写入到某个地方(buffer)
• 因此, 读取过程, 需要同时读取 buffer
• 如果写 buffer 满了, 需要阻塞写操作, 等待 compaction 完成
• 异步任务中断之后, 重启时需要进行清理

写缓冲和批量提交

在并发写的场景下, 是可以用写缓冲模式的, 主动阻塞每一个写线程, 收集到多个写请求之后, 批量提交. 但如果是单线程写, 只能要求请求者自己缓冲多个请求(也即 Batch 接口).

在将 log(raft log, binlog) 分离之后, 数据库不依赖使用场景即可做缓冲, 因为丢失的数据可以从 log 中回补.

给操作分配序列号, 多个目标(资源)单独确认自己的持久化进度, 引入单点确认整体的持久化进度.

Shadow, Proxy, Delegate

因为某种原因, 在操作目标前, 先通过一个代理, 对代理的操作, 即认为是对目标的操作. 例如, 目标当前正在做 compaction, 无法写入, 因此先将数据写入代理. 等目标就绪后, 代理再将之前缓冲的操作, 依次应用到目标身上.

读取时, 要么全部通过代理, 要么先获取目标的写锁之后(禁止目标变更状态), 判断目标的状态, 然后决定是否去读代理.

Batch 框架

1. 收到请求时, 分配序号
2. 将请求者放入等待队列
3. 将请求发给多个处理者
4. 处理者处理完毕后, 回调
5. 检查等待队列, 通知完成

Compaction IO 优化

compaction 生成新文件时, 采用 buffer io 模式, 最后再调用 fsync().

读优化: 锁粒度

• 全局锁: 读写锁
• 每个资源一把锁: 排他锁

Multi Versions, Commit Point

这是一个总的原则, 然后粒度不断地细化.

第一步: 序列化

数据库最初是序列化操作的, 每一个读和写操作排队.

• 读操作进行的时候, 写必须等待. 反之亦然
• 读操作进行的时候, 其它的读也必须等待

第二步: 读写锁

读和写虽然排队, 但, 读和读之间可以并发进行. 性能有了进一步的提高.

• 读操作进行的时候, 写必须等待. 反之亦然
• 读操作进行的时候, 其它的读可以并发进行

第三步: 读写并发(Multi Versions, Commit Point)

读可以并发, 写虽然不可以并发, 但读和写之间可以并发. 只需要它们操作不同的版本, 然后通过一个 Commit Point 来切换.

• 读可以并发进行
• 写序列化
• 读写可以同时进行

同时读写一个文件

打开同一个文件两次, 获得两个 fd, 一个用于写, 一个用于读. 记录写的偏移, 确保读不超过该偏移, 这样读就不会读到不完整的记录.

好处:

• 读和写可以并发进行
• 未来可以创建多个读 fd, 并发读

并发 fsync 并无益处

系统的 fsync 资源是唯一的, 即使用户多线程/多线程调用 fsync, 依然会被内核排队处理.

所以, 对于数据库系统来说, 提高写性能的唯一路径就是做写 Batch.

限制体积与限制条数

例如 cache, 除了限制占用内存的大小, 还可能需要限制数据条数.

转存 Buffer

在目标进行变更的过程中, 新的数据暂时存在 Buffer 中. 当目标变更完毕后, 需要将 Buffer 转存到目标中. 如果转存过程是一个原子操作, 那么就要加锁, 锁住 Buffer.

Tombstone 触发 compaction

使用 tombstone 技术的系统, 即使 tombstone 保存在内存中, 当出现大量的连续的 tombstone 时(例如10w级别), 扫描一次可能也要数毫秒, 而且空耗大量的 CPU.

把数据和删除标记, 分开存储. 当删除标记达到一定程度时, 必须真正地将数据清除.