◄ prev contents next ►

⚠

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

0704: Merge Levels

LSM-Tree Parameters

In the previous step, the log was turned into the top-level SSTable. Now implement the merge operation from 0700. Add 2 parameters:

type KVOptions struct {
    Dirpath string
    // LSM-Tree
    LogShreshold int
    GrowthFactor float32
}

LogShreshold is the max key count in the log. When exceeded, convert to an SSTable.
GrowthFactor is the size ratio (key count) between the next level and the current level.

Merge SSTables

The KV.Compact() function uses these 2 parameters to decide when to merge SSTables:

func (kv *KV) Compact() error {
    if kv.mem.Size() >= kv.Options.LogShreshold {
        if err := kv.compactLog(); err != nil {
            return err
        }
    }
    for i := 0; i < len(kv.main)-1; i++ {
        if kv.shouldMerge(i) {
            if err := kv.compactSSTable(i); err != nil {
                return err
            }
            i--
            continue
        }
    }
    return nil
}

KV.compactLog() is the previous step’s KV.Compact().
KV.shouldMerge() decides whether to merge level i with i+1 using exponential growth rule.
KV.compactSSTable() merges 2 adjacent SSTables and replaces the originals.

Note that the last level must drop deleted keys. You can wrap the input iterator:

type NoDeletedSortedKV struct {
    SortedKV
}

func (kv NoDeletedSortedKV) Iter() (iter SortedKVIter, err error) {
    if iter, err = kv.SortedKV.Iter(); err != nil {
        return nil, err
    }
    return NoDeletedIter{iter}, nil
}

func (kv *KV) compactSSTable(level int) error {
    // ...
    file := SortedFile{FileName: filename}
    m := SortedKV(MergedSortedKV{&kv.main[level], &kv.main[level+1]})
    if len(kv.main) == level+2 {
        m = NoDeletedSortedKV{m}
    }
    err := file.CreateFromSorted(m)
    // ...
}

To make the DB practical, KV.Compact() should be auto-triggered on update, which is a future step.

ⓘ

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

◄ prev contents next ►