0601: Build SSTables

SSTable Format

In this step, we persist the sorted in-memory array to a file. This file is initially created by flushing the in-memory data structure (mirroring the log). Later, whenever the log reaches a size limit, it is merged with the old file into a new file, then replace the old one.

In an LSM-Tree, the on-disk data structure is usually called an SSTable (sorted string table). An SSTable is just some implementation details; even with the same data structure, different on-disk formats can be used. We adopt the following format:

[ n keys | offset1 | offset2 | ... | offsetn | KV1 | KV2 | ... | KVn ]
  8bytes   8bytes

First comes an array that records the offset of each key in the file. The array size (n) is stored at the beginning. This array is used for binary search and iteration. Each KV is stored in the following format:

[ key length | val length | key data | val data ]
    4bytes       4bytes

Constructing an SSTable

The initial SSTable is created by flushing the in-memory data structure (MemTable). When building an SSTable, input data is fed through an iterator, so the code does not depend on the specific data type.

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
}

This iterator is an interface and matches the existing KVIterator. Using an interface also makes it more testable; see the test cases for details.

The input interface also provides the number of keys. With this, we know the size of the offset array and therefore the offset of the first KV. We can write both the offset array and the KV data in a single pass. To write at a specific position, use WriteAt():

func (fp *os.File) WriteAt(b []byte, offset int64) (n int, err error)