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

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

数据结构

日志结构的数据库最早来源于LFS的论文The Design and Implementation of a Log-Structured File System，这篇论文本身是关于文件系统结构的研究，后来基于此发展出了LSM等日志结构的数据库。

日志结构（Log-Structure）的核心是以日志形式存储数据，将数据的写入、删除等操作作为表项添加到日志末尾。其特点是大量的顺序写入，利用了硬盘对于顺序写的速度优势。

数据维护

日志结构的一个核心问题是数据维护。在日志末尾记录操作是纯粹的消耗空间，如果不清理此前记录的表项，势必导致存储用尽。此外，在维护日志的同时，先前记录的表项随着数据更新可能会废弃，我们希望清理这些废弃表项来获取可用空间。

使用朴素的思想清理数据：直接读取需要清理的部分到内存中，在读取日志的同时新读取的数据会自然覆盖无用数据。当读取完毕后将新数据存储回硬盘中。

内存中的数据

一般来说，键是一个较短的字符串，而值是一个较长的字符串。例如使用KV数据库存储图片，键是图片名，值是图片的Base64编码。因此，整个数据库的所有键信息都存储在内存中。

内存中的主要数据结构为：保存键到表项位置的映射。可以使用HashMap实现这一映射。表项位置包括两点：日志结构位置，偏移量，表项长度。通过这两个信息，可以直接通过键获取日志文件中的值。

除此之外，内存中还存放着能访问文件句柄的映射。借助Rust中的BufReader，我们可以在每次读取之后保存文件中指针的位置，提高读写性能。

数据库操作

数据库内核需要支持最基本的三个操作：

• set
  • 生成日志表项
  • 写入日志表项到日志尾
  • 生成表项位置
  • 将表项位置记录到内存
• get
  • 通过键查询表项位置
  • 通过表项位置获取表项内容
• rm
  • 生成日志表项
  • 写入日志表项到日志尾

统计可压缩量

压缩算法需要以可压缩空间尾参考运行。为了设计压缩策略，我们首先要在数据库操作的同时统计有多少空间可以压缩。

在基本操作中，统计压缩量的算法如下：

• set
  插入时查找内存中是否已存在该键，若已存在，则其对应的旧表项可压缩，计入压缩量。
• rm
  删除时获取旧表项，该表项可以压缩，计入压缩量。同时，当旧set表项不存在时，这个删除表项本身也可以被压缩。

注意到执行压缩算法时，是执行日志并将内存中结果写回新日志，因此写回内容必为set表项，所有的rm表项本身都是会被压缩的。

对客户端执行的set rm指令或其他操作中的插入都需要执行上述算法。

压缩算法

在我们的程序中，使用朴素的压缩算法：设置阈值，当uncompacted统计量到达一定数值时，新建log文件作为写入文件，依据我们的key_map逐个从reader_map中反序列化并写入内容到新文件，同时直接删除所有的旧文件。

在未来的开发中，我们希望构建更为智能，节约计算成本，多线程的压缩算法，但是在version 0.1.0中，最重要的是成功实现一个算法。

程序开发

序列化与反序列化

一开始我准备使用RON（Rust Object Notation）作为存储格式，但是由于ron中的Deserializer没有实现基于缓存的流式读取，当读取整个文件时必须直接将所有内容缓存到内存中，因此使用了较为成熟的JSON。

程序结构

│  Cargo.lock
│  Cargo.toml
│   
├─src
│      command.rs
│      error.rs
│      io.rs
│      lib.rs
│      main.rs
│      store.rs
│      tools.rs
│
└─tests
        tests.rs

• store.rs
  开发的核心为KvStore结构体，它实现了数据库内核所需要具备的功能。以此为基础，使用了clap解析命令，编写基本的可执行程序作为演示。
• io.rs
  为了显式的确定指针在文件中的位置，使用带偏移量的BufReader与BufWriter编写程序。
• command.rs
  定义了set与rm的指令以及表项位置结构体。
• error.rs
KvError定义了可能遇到的错误，实现了From<io::Error>与From<serde_json::Error>。
• tools.rs工具库

程序发布

完成了上述内容的KvStore即为0.1.0版本，我将代码开源在Github仓库中，有兴趣可以阅读。