使用Rust编写一个KV数据库-三

发表于 更新于 分类于

本项目内容来自于PingCAP的talent-plan中Rust部分内容。

建立线程安全的KvsEngine

建立多线程数据库的关键在于实现线程安全的KvsEngine。我们期望KvsEngine能够像线程安全的容器一样，可以安全地被多线程共用。要实现这一目标，需要对原trait及实现进行修改。

从trait层面，我们希望KvsEngine具有以下特征：

  1. 实现线程级Clone与Send
  2. 具有immutable的方法

首先，我们需要线程级的Clone，保证在多线程访问时，KvsEngine的实体只有一个，同时可以安全地被多线程进行修改。最简单的方式是使用Arc包裹整个KvsEngine，但为了更细粒度的控制，我们可以将Arc放在结构体内部，并针对具体需求进行修改。

由于我们需要在启用线程时转移对KvsEngine的控制，所以实现Send也是必须的。

为了高性能的进行并发，必须控制对共享资源锁的粒度最小。在高层次上，我们对需要修改的内容上锁，而不需要修改的部分严格声明immutable。这就是为什么方法是immutable的（immutable的Mutex仍然可以修改内部数据）。

读写分离

线程安全的最简单方法就是给整个实体上锁：但这开销未免太大，相较于顺序执行，只有对外IO部分并发。我们必须分解出存在资源竞争的部分，对其单独上锁，对其他内容允许无锁的并发访问。

数据库具有三个基本方法：get、set、rm 和一个压缩算法compact。我们逐个分析可能发生资源竞争的地方。

  • get方法看似没有资源竞争，其实也有。这是因为在带缓存的IO中，读取数据必定涉及到移动游标，而这个游标是包裹在BufReader中的，我们检查Seek的相关签名，可以看到seek需要&mut self。因此在get中，加锁的最低粒度为文件句柄。

  • set方法的基本内容是：将Command写入本地存储，将CommandPos写入内存。这就涉及到两个基本写入操作。写入Command由唯一的writer句柄执行，我们直接为其加锁，写入时首先获取锁即可，这方面没有什么困惑。接下来还有CommandPos，这涉及index_map，同样是必须上锁的对象。

  • rm方法实质上是向文件写入一个指令，同时检测可压缩量。需要为writer加锁。

  • compact算法涉及新建文件，包含大量写入操作。

可以看到，一些方法包含大量写入操作，而一些方法几乎不涉及写入操作。

在get中，涉及缓冲区光标的移动。实际上，我们完全可以负担得起在内存中保留大量句柄的开销，而且句柄缓冲区光标的区别不会影响实际存储的数据，因此我们应该令每个线程占有自己的读文件句柄，以此忽略这部分的资源竞争，获得并发性能提升。

我们可以将方法分为两大类：需要锁的set、rm、compact和不需要锁的get。我们假定get操作具有最高的频率，set与rm具有中等频率，compact频率最低。当操作后三者时，设计锁结构；对于前者，设计无锁算法，以此通过读写分离获得并发带来的最大性能提升。