Storage engines: B-trees and LSM trees

// Put appends to the log and to the memtable. It never reads from disk.
func (l *LSM) Put(key uint64) {
  l.c.UserBytes += EntrySize
  l.write(rec{key: key})
}

// Delete writes a tombstone. The old value stays on disk until compaction drops both.
func (l *LSM) Delete(key uint64) {
  l.c.UserBytes += KeySize
  l.write(rec{key: key, tomb: true})
}

func (l *LSM) write(r rec) {
  l.seq++
  r.seq = l.seq
  l.c.WALBytes += WALHeader + r.size() - 8
  if old, ok := l.mem[r.key]; ok {
    l.memBytes -= old.size() // a newer version replaces it in memory
  }
  l.mem[r.key] = r
  l.memBytes += r.size()
  if l.memBytes >= l.cfg.MemtableBytes {
    l.flush()
  }
}

// flush writes the memtable as one sorted SSTable, then compacts if a trigger fires.
func (l *LSM) flush() {
  if len(l.mem) == 0 {
    return
  }
  recs := slices.SortedFunc(maps.Values(l.mem), func(a, b rec) int { return cmp.Compare(a.key, b.key) })
  clear(l.mem)
  l.memBytes = 0
  t := l.newTable(recs)
  l.c.DataBytes += t.bytes
  if l.cfg.Compaction == Tiered {
    l.runs = slices.Insert(l.runs, 0, t)
    l.compactTiered()
    return
  }
  l.l0 = append(l.l0, t)
  l.compactLeveled()
}

// probe looks for key in one SSTable. The filter is in memory; only a "maybe" costs a block read.
func (l *LSM) probe(t *table, key uint64) (rec, bool) {
  if key < t.min || key > t.max {
    return rec{}, false // the key range, kept in memory, rules the table out
  }
  l.c.Probes++
  if t.filter != nil && !t.filter.mayContain(key) {
    return rec{}, false
  }
  i, found := slices.BinarySearchFunc(t.recs, key, func(r rec, k uint64) int { return cmp.Compare(r.key, k) })
  l.readBlock(t, t.block(min(i, len(t.recs)-1)))
  if !found {
    return rec{}, false // a false positive: one block read for nothing
  }
  return t.recs[i], true
}

// Get checks the memtable, then each sorted run from newest to oldest, and stops at the first
// version it finds. A tombstone means the key was deleted.
func (l *LSM) Get(key uint64) bool {
  if r, ok := l.mem[key]; ok {
    return !r.tomb
  }
  if l.cfg.Compaction == Tiered {
    return l.getTiered(key)
  }
  for i := len(l.l0) - 1; i >= 0; i-- {
    if r, ok := l.probe(l.l0[i], key); ok {
      return !r.tomb
    }
  }
  for lv := 1; lv < len(l.levels); lv++ {
    files := l.levels[lv]
    j := sort.Search(len(files), func(j int) bool { return files[j].max >= key })
    if j < len(files) {
      if r, ok := l.probe(files[j], key); ok {
        return !r.tomb
      }
    }
  }
  return false
}

// compactLeveled runs until no trigger fires: L0 has too many files, or a level is over its target.
func (l *LSM) compactLeveled() {
  for {
    if len(l.l0) >= l.cfg.L0Trigger {
      l.compactL0()
      continue
    }
    lv := 0
    for i := 1; i < len(l.levels); i++ {
      if levelBytes(l.levels[i]) > l.target(i) {
        lv = i
        break
      }
    }
    if lv == 0 {
      return
    }
    l.compactLevel(lv)
  }
}

// compactL0 merges every L0 file with the L1 files whose key ranges they meet.
func (l *LSM) compactL0() {
  in := l.l0
  l.l0 = nil
  lo, hi := in[0].min, in[0].max
  for _, f := range in {
    lo, hi = min(lo, f.min), max(hi, f.max)
  }
  over, rest := overlap(l.levels[1], lo, hi)
  if len(over) == 0 && disjoint(in) {
    l.levels[1] = byMin(append(rest, in...)) // a trivial move: no byte is rewritten
    return
  }
  l.levels[1] = byMin(append(rest, l.merge(append(over, in...), 1)...))
}

// compactLevel pushes one file of level lv into lv+1, taking files in key order, round robin.
func (l *LSM) compactLevel(lv int) {
  l.ensure(lv + 1)
  files := l.levels[lv]
  i := sort.Search(len(files), func(i int) bool { return files[i].min > l.ptr[lv] })
  if i == len(files) {
    i = 0
  }
  f := files[i]
  l.ptr[lv] = f.max
  l.levels[lv] = slices.Delete(slices.Clone(files), i, i+1)
  over, rest := overlap(l.levels[lv+1], f.min, f.max)
  if len(over) == 0 {
    l.levels[lv+1] = byMin(append(rest, f))
    return
  }
  l.levels[lv+1] = byMin(append(rest, l.merge(append(over, f), lv+1)...))
}