继续继续...

转眼都开学啦...

Building Blocks 2

building blocks里讲了一些关于Log structure storage的东西，这也是用于在硬盘上持久化KvStore要用的结构。我们边做project边看吧

Project 2

这次要Create a persistent key/value store that can be accessed from the command line，意思就是要写硬盘啦。我们给project2起个名字吧：KVS2.0

Bitcask

我们会使用Building Blocks 2中讲过的Bitcask，这是一种日志型key-value存储模型。Bitcask的核心思想就是把key对应的具体的值存到硬盘上，在写内存的同时维护一个硬盘上的log file（类似RocksDB中的WAL），这样就可以把数据持久化啦。

ref: https://cloud.tencent.com/developer/article/1083737

      https://blog.csdn.net/chdhust/article/details/77801890

根据Bitcask的思想，那我们的KVS2.0就这样设计：

KVS2.0要支持以下几种操作（和之前的project1差不多）：

• Set <KEY> <VALUE>
  • 对于不存在的新记录，向log file中存record（注意维护idx++），并在index中存储<key, idx>
  • 对于已存在的新纪录，向log file中存record（还是idx++，旧的先不动），并在index中更新<key, idx>
  • 一个写操作需要进行 一次顺序的磁盘写入 和 一次内存操作。

• Get <KEY>
  • 先在idex中key对应的idx，然后在log file中找idx对应的value，返回

• Rm <KEY>
  • 删掉index中的<key, idx>键值对。Log file不动

• Replay
  • 刚重启程序时index是空的，需要根据log file重建内存中的index

• compaction：删除log file中无用的块
  • 定期将所有older data file中的数据扫描一遍并生成新的data file（没有包括active data file 是因为它还在不停写入），这里的merge其实就是将对同一个key的多个操作以只保留最新一个的原则进行删除。

另外Bitcask还支持一些特性，但现在我们暂(tou)时(lan)先不实现啦：

• 当一个log file过大时，另外建立一个新的log file
• Hint file

Error handeling in rust

因为磁盘io是可能存在错误的（比如硬盘被人跺了一脚），所以这次我们还要考虑rust中的error handeling。

Rust工程的文件结构

project 2和project 1的文件结构很像，唯一不同点就是多了一个error.rs，用于错误处理。

刚上来写好像有种无从下手的感觉....我们不妨先分析一下Brain大神的样例。

BufReader和BufWriter

首先来看最核心的KvStore的结构。它被定义在kv.rs中。之前我们提到要记录log file，假设我们就用一个简单的文本文件作为log（用别的格式比如json也可以，反正原理是一样的），那么它的格式应该是这样的：

idx "key":"val"

比如
232 "qq": "mahuateng"
233 "zzz": "qaqaqaq"
234 "llc": "nbnbnbnbnbnb"
235 "hfut": "nb666"

其中idx是一个递增的计数器。那么如果我们要在rust中做到能随时定位这个文本文件中的每一行（即每个record），就需要如下信息：

该行在文件中的起始位置
该行在文件中的结束位置
该行记录的长度
该行记录的idx

Rust提供了std::io，这是一个进行io操作的库。为了方便进行文件读写操作，可以定义 BufReaderWithPos 和 BufWriterWithPos 两个结构体：

struct BufReaderWithPos<R: Read + Seek> {     //BufReaderWithPos可以同时作用在Read和Seek两种trait上
    reader: BufReader<R>,                     //读缓冲区
    pos: u64,                                 //当前读位置的指针
}
BufReaderWithPos实现了read和seek函数。
new时会用给定的文件（File）初始化BufReader。seek时将文件定位到指定的位置。


struct BufWriterWithPos<W: Write + Seek> {    //BufWriterWithPos可以同时作用在Write和Seek两种trait上
    writer: BufWriter<W>,                     //写缓冲区
    pos: u64,                                 //当前写位置的指针
}
BufReaderWithPos实现了write，seek，flush函数。
new时会用给定的文件（File）初始化BufWriter。

 这样我们就有了对文件进行读写的工具。

KvStore

接下来看最主要的struct：KvStore。里面的成员变量如下：

pub struct KvStore {
    // directory for the log and other data
    path: PathBuf,

    // map generation number to the file reader
    // 一条记录的idx->它在log file中的位置，用于读记录
    readers: HashMap<u64, BufReaderWithPos<File>>,

    // writer of the current log
    // 用于写记录
    writer: BufWriterWithPos<File>,

    current_gen: u64,

    // 
    index: BTreeMap<String, CommandPos>,

    // the number of bytes representing "stale" commands that could be deleted during a compaction
    uncompacted: u64,
}

这里我们重点关注这两个HashMap。

1