⚠

The web version only has simple instructions since chapter 04, while the full book has detailed explanations and background info.

0703: Multiple Levels

This step adds multiple SSTable levels:

type KV struct {
    // ...
    // main    SortedFile
    main    []SortedFile
}

type KVMetaData struct {
    Version  uint64
    // SSTable string
    SSTables []string
}

The query used to have 2 levels. Now only small changes are needed:

func (kv *KV) Seek(key []byte) (SortedKVIter, error) {
    levels := MergedSortedKV{&kv.mem}
    for i := range kv.main {
        levels = append(levels, &kv.main[i])
    }
    iter, err := levels.Seek(key)
    // ...
}

The last level SSTable must record deleted keys. Modify the SSTable format as follows:

[ key length | val length | deleted | key data | val data ]
    4bytes       4bytes      1byte
type SortedArray struct {
    keys    [][]byte
    vals    [][]byte
    deleted []bool      // added
}

KV.Compact() converts the log to an SSTable and inserts it into KV.main[0], instead of replacing the SSTable. Merging between SSTables will be implemented in the next step.

func (kv *KV) Compact() error

ⓘ

CodeCrafters.io has similar courses in many programming languages, including build your own Redis, SQLite, Docker, etc. It’s worth checking out.