前言
新的KV数据库层出不穷，我们经常听说的KV数据库如RocksDb、Hbase等都是基于日志结构的存储引擎。最近我在看《数据密集型应用系统设计》，里面有一章专门在讲日志结构的存储引擎的演进过程，纯看理论不过瘾，所以我决定根据书里的理论动手自己实现一个KV数据库。同时，为了能顺便学习Rust，所以我使用了Rust来实现数据库。
除了参考《数据密集型应用系统设计》，我还参考了《pingcap/talent-plan》中使用Rust实现KV数据库的源码，恰好它的实现就是基于哈希索引和日志压缩的原理，跟书中的描述不谋而合。通过实现一个迷你数据库来学习和理解数据库的原理是一种学以致用的方式，能够帮助我们更加深入理解数据库原理。闲话不多说，开始正文。
最简单的数据库
在上正菜之前先来一道甜点，你知道最简单的数据库只需要几行代码吗？只需要两行，一行读取，一行写入。
#!/bin/bashdb_set(){echo$1,$2database}db_get(){grep^$1,database
sed-es/^$1,//
tail-n1}可以尝试保存脚本，然后在shell中试一下。
~sourcedb.sh~db_setkey1value1~db_setkey2value2~db_setkey1value1~db_setkey1value2~db_getkey1value2~catdatabasekey1,value1key2,value2key1,value1key1,value2是不是很神奇，其实原理很简单，set的操作是将数据追加到文件末尾，get的操作是先grep找到所有key的数据，然后再取最后一条数据（tail-n1）作为结果。仔细思考一下，这个数据库逻辑是正确的，而且还是持久化的。
这个数据库原理虽然简单，但是其中set使用日志追加的方式写入数据却是很多数据库的常用方式，因为日志追加性能非常好。相对的，get的方式性能就比较差了，需要从头到尾扫描整个文件，查询的开销是O(n)。
为了提高读取的性能，我们需要用到索引，基本的思路就是通过保存额外的元数据，根据这些元数据作为路标来快速定位到想要的数据。但是天下没有免费的午餐，维护索引需要在写入的时候额外写入其他数据，这会影响写入的性能。这里就涉及到存储系统中重要的权衡设计：适当的索引可以加速读取，但是每个索引都会减慢写入的速度。下面我们就给我们简单的数据库加上最简单的索引方式：哈希索引。
基于哈希索引的数据库
回想一下我们经常使用HashMap数据结构，哈希索引就是基于内存的HashMap来实现的，不同的是我们在内存里面使用HashMap的时候value都是直接存储原始数据的，对于数据库来说，如果你把所有的原始数据都直接存储到内存的话，这是不现实的。那怎么办呢？想想我们在编程里面常用的指针，是不是得到启发了？我们可以在内存里面保存原始数据的“指针”，即文件的字节偏移量和数据的长度。指针的占用量很小，这样我们完全可以把整个数据库的key的索引都放到内存里面，读取的时候直接找到key在文件中的偏移量，直接去磁盘读取数据。
借用书中的图示
-w这个哈希索引的原理听起来很简单，但是这可是在生产中被实际使用过的Bitcask数据库的核心原理。只要保证所有key都能放到内存里面，Bitcask就能提供高性能的读写，因为它的索引结构简单，写入也是内存操作，可以说索引的代价可以忽略不计，而读取只需要一次内存寻址，在有文件系统缓存时甚至不需要IO操作。在某些场景中这个数据库可以完爆其他所有数据库。
了解了基本原理之后，下面开始实操环节。
数据命令
首先定义一下我们数据库的基本功能：
set：保存KVget：获取数据rm：删除数据如果基于日志追加来做，我们的存储结构要怎么设计呢？肯定不能按照前面的简单数据库那样搞，因为光把数据存进去不能支持删除数据的功能。回想一下MySQL的RedoLog，我们可以得到一些启发。如果我们不记录原始数据，而是记录数据命令呢？例如，我们按照下面的格式来记录数据。
set:key1,value1set:key2,value2set:key1,value1rm:key1因为写入的操作只有两个：set和rm，所以我们可以定义两个数据命令，每次都把这些数据命令记录到日志里面，这样读取的时候读取到的就是数据命令，假设我们现在读取key2，实际上从磁盘读取到的数据是：set:key2,value2，这样我们就知道key2现在的最新值是value2，当读取key1的时候，从磁盘读取到的数据是rm:key1，那么意味着key1已经被删除了。
在Rust中数据命令的定义如下：
pubenumCommand{Set{key:String,value:String},Remove{key:String},}数据写入
接下来定义我们的数据库对象，成员变量只有三个，一个读取器、一个写入器、一个索引。
pubstructKvStore{reader:BufReaderWithPosFile,writer:BufWriterWithPosFile,index:HashMapString,CommandPos,}structCommandPos{pos:u64,len:u64,}BufReaderWithPos：带有寻址读取功能的读取器BufWriterWithPos：带有寻址写入功能的写入器CommandPos：记录命令的起始位置和长度那么写入操作具体要做什么呢？看一下的代码注释
pubfnset(mutself,key:String,value:String)-Result(){//构造一个写入命令letcmd=Command::set(key,value);//获取当前写入句柄的位置letpos=self.writer.pos;//通过serde把set命令序列化成json写入到文件中serde_json::to_writer(mutself.writer,cmd)?;//文件刷盘持久化self.writer.flush()?;ifletCommand::Set{key,..}=cmd{//记录写入命令的开始位置和长度letcmd_pos=CommandPos{pos,len:self.writer.pos-pos};//把当前key的最新命令位置记录到索引里面self.index.insert(key,cmd_pos);}Ok(())}删除操作也是类似的：
pubfnremove(mutself,key:String)-Result(){ifself.index.contains_key(key){//构造删除命令letcmd=Command::remove(key);//写入到文件serde_json::to_writer(mutself.writer,cmd)?;self.writer.flush()?;ifletCommand::Remove{key}=cmd{//从索引中删除key，这样就读取不到了。self.index.remove(key).expect(keynotfound);}Ok(())}else{Err(KvsError::KeyNotFound)}}数据读取
数据读取主要是从索引里面获取命令位置，然后从磁盘读取命令返回结果。
pubfnget(mutself,key:String)-ResultOptionString{//从索引中读取key的命令位置，如果读取不到说明key不存在ifletSome(cmd_pos)=self.index.get(key){letreader=mutself.reader;//把读取器游标设置到命令的起始位置reader.seek(SeekFrom::Start(cmd_pos.pos))?;//指定读取的长度letcmd_reader=reader.take(cmd_pos.len);//读取命令ifletCommand::Set{value,..}=serde_json::from_reader(cmd_reader)?{Ok(Some(value))}else{Err(KvsError::UnexpectedCommandType)}}else{Ok(None)}}数据加载
数据库每次启动都需要从文件中命令回放一遍，然后构建出内存索引才能开始使用。
fnload(reader:mutBufReaderWithPosFile,index:mutHashMapString,CommandPos)-Result(){//设置文件游标到0，从开始遍历到文件末尾letmutpos=reader.seek(SeekFrom::Start(0))?;letmutstream=Deserializer::from_reader(reader).into_iter::Command();//遍历命令whileletSome(cmd)=stream.next(){letnew_pos=stream.byte_offset()asu64;matchcmd?{//如果是set命令就插入到索引中Command::Set{key,..}={index.insert(key,CommandPos{pos,len:new_pos-pos});},//如果是rm命令就从索引中删除keyCommand::Remove{key}={index.remove(key);}}pos=new_pos;}Ok(())}至此，一个简单的基于哈希索引的数据库就完成了。完整代码可以参考：log_base
日志文件压缩
上面我们实现的数据库有一个明细的缺陷：如果使用时间很长的情况下，日志文件会非常大，可能把磁盘用光了。所以要想办法对日志文件进行压缩，可以发现对于相同的key在日志文件中会重复保存，而且实际上我们只会使用最新的命令。这部分没用的命令是可以删除掉的。因此，一个简单的日志压缩方式就是把重复的key删除掉只保留每个key最近的更新。
-w压缩日志文件实现会比较复杂，核心思路就是要将日志进行分段处理，当日志大小超过某个阈值时，新建一个日志用于写入，然后再新建一个日志将之前的全部日志遍历一遍进行压缩，最后将原始日志删除。由于加入了分段日志的设计，所以现在要寻找一个key在磁盘的位置，需要增加一个维度：日志文件的序号。即命令位置的数据结构需要新增一个gen字段用于标识文件的序号。
structCommandPos{gen:u64,pos:u64,len:u64,}数据库的成员对象也需要修改，具体见注释。
pubstructKvStore{//记录日志文件的目录path:PathBuf,//从单个读取器修改为多个日志读取器的集合，key是日志文件的序号readers:HashMapu64,BufReaderWithPosFile,writer:BufWriterWithPosFile,index:HashMapString,CommandPos,//记录当前写入的文件序号，压缩时写入的文件序号会自增切换到新的文件上current_gen:u64,//记录当前未压缩的命令大小un