raft&bitcask 键值存储数据库
关于用 go 实现一个由 raft 分布式一致性协议和 bitcask 存储模型搭建的分布式键值存储数据库。
raft
raft 的实现来自于 MIT 6.824 课程实践 lab 的调整。主要集中于
- 内部调用方式上用 grpc 协议取代了该 lab 原有的 channel 模拟。
- 对于命令实现的调整。
命令应被传入当前的 leader 处，在这里由一个 subscriber 的机制来完成。该 subscriber 与应用处于同一层级，会接收到 raft 集群内部的命令但不会进行响应，只负责来记录 leader 的变更备应用使用。
只要命令通过 RPC 调用恰当的传入当前 leader，该 leader 确认后就会返回命令接受，立即开始日志同步，而调用该命令者则认为该命令已经被执行。但实际上，命令的真正执行时间，是 leader 确认半数节点接受命令后 apply 该日志时，则该日志所代表的命令会返回给真正的执行方开始执行。
当然，这边的执行方可以是任何实现了定义的 Command 接口的结构。
bitcask
bitcask 是真正的执行方。
bitcask 模型是一个经典的键值对存储模型。其使用日志形式管理键值对存储。
其核心在于追加写模式和 merge hint 过程。
- 追加写，不修改之前的内容保证了键值对结构的紧密排列和高效率。
- merge hint 过程，则保证了查找时的效率。
merge 即从前往后遍历之前的文件，只保留不被删除和覆盖的键值对一步步生成新的文件。而 hint 即 merge 过程生成的索引。其值存储的是真正的值所在的文件和偏移量。hint 文件会在下一次重启时起到恢复内存索引的作用。
在内存中，我们还是使用索引机制，索引与 hint 文件类似，不同点在于我们可以使用不同的方式构建索引，以实现快速查找。比如红黑树，b树等。
内部实现上我们还是围绕接口进行，如文件读写形式（传统 IO，mmap，iouring 等）和内存索引（Btree，HashMap）等。保证了可拓展性和模块化。
server
接着，我们需要划分宏观上的实现形式：即一个机器（或者说一个 provider ）拥有一个 raft client 和 bitcask。多个 provider 组成一个 cluster，内部使用 raft 完成通信。多个 cluster 组成一个 server ，对外由客户端使用一致性哈希在不同 cluster 间完成负载均衡。