0601: 构造 SSTable

SSTable 格式

这一步将内存中的排序数组保存到文件里，这个文件最初是由内存数据结构（对应 log）转移过去的。之后 log 大小达到一个上限，就合并成一个新文件，替换老文件。

LSM-Tree 里具体的数据结构一般叫做 SSTable（sorted string table），因为它们实现的是可以 seek 和按顺序遍历的数据结构，它可以是数组或是树，不是字面意思上的一堆按顺序储存的 string。 SSTable 只是一些实现细节，即使是同样的数据结构，落到硬盘上可以采用不同的格式。我们采用下面的格式：

[ n个key | 偏移量1 | 偏移量2 | ... | 偏移量n | KV1 | KV2 | ... | KVn ]
  8bytes   8bytes

首先是一个数组，记录了每个 key 在文件中的偏移量（offset），这个数组的大小放在开头。通过这个数组来做二分查找、遍历。 KV 按以下格式储存：

[ key 长度 | val 长度 | key 数据 | val 数据 ]
   4bytes     4bytes

写入 SSTable

最初的那个 SSTable 是从内存数据结构（MemTable）转移过去的，构造 SSTable 时，数据可以通过 iterator 来输入，这样不用依赖具体的数据结构。

type SortedFile struct {
    FileName string
    fp       *os.File
}

func (file *SortedFile) CreateFromSorted(kv SortedKV) error

type SortedKV interface {
    Size() int
    Iter() (SortedKVIter, error)
}
type SortedKVIter interface {
    Valid() bool
    Key() []byte
    Val() []byte
    Next() error
    Prev() error
}

这个 iterator 当然是一个 interface，并且恰好匹配已有的 KVIterator。使用 interface 还方便单独测试这个模块，具体请看测试用例。