pebble Documentation

Technical Documentation: cockroachdb/pebble

ℹ️ Provenance: Multi-Tier Ingestion · CodeWiki Reference

Overview (`README.md`) Copy Section

Pebble [](https://github.com/cockroachdb/pebble/actions/workflows/ci.yaml) [](https://godoc.org/github.com/cockroachdb/pebble) ^{_{[Coverage](https://storage.googleapis.com/crl-codecover-public/pebble/index.html)}}

[Nightly benchmarks](https://cockroachdb.github.io/pebble/)

Pebble is a LevelDB/RocksDB inspired key-value store focused on
performance and internal usage by CockroachDB. Pebble inherits the
RocksDB file formats and a few extensions such as range deletion
tombstones, table-level bloom filters, and updates to the MANIFEST
format.

Pebble intentionally does not aspire to include every feature in RocksDB and
specifically targets the use case and feature set needed by CockroachDB:

• Block-based tables
• Checkpoints
• Indexed batches
• Iterator options (lower/upper bound, table filter)
• Level-based compaction
• Manual compaction
• Merge operator
• Prefix bloom filters
• Prefix iteration
• Range deletion tombstones
• Reverse iteration
• SSTable ingestion
• Single delete
• Snapshots
• Table-level bloom filters

RocksDB has a large number of features that are not implemented in
Pebble:

• Backups
• Column families
• Delete files in range
• FIFO compaction style
• Forward iterator / tailing iterator
• Hash table format
• Memtable bloom filter
• Persistent cache
• Pin iterator key / value
• Plain table format
• SSTable ingest-behind
• Sub-compactions
• Transactions
• Universal compaction style

WARNING: Pebble may silently corrupt data or behave incorrectly if
used with a RocksDB database that uses a feature Pebble doesn't
support. Caveat emptor!

Production Ready Copy Chapter

Pebble was introduced as an alternative storage engine to RocksDB in
CockroachDB v20.1 (released May 2020) and was used in production
successfully at that time. Pebble was made the default storage engine
in CockroachDB v20.2 (released Nov 2020). Pebble is being used in
production by users of CockroachDB at scale and is considered stable
and production ready.

Advantages Copy Chapter

Pebble offers several improvements over RocksDB:

• Faster reverse iteration via backwards links in the memtable's
  skiplist.
• Faster commit pipeline that achieves better concurrency.
• Seamless merged iteration of indexed batches. The mutations in the
  batch conceptually occupy another memtable level.
• L0 sublevels and flush splitting for concurrent compactions out of L0 and
  reduced read-amplification during heavy write load.
• Faster LSM edits in LSMs with large numbers of sstables through use of a
  copy-on-write B-tree to hold file metadata.
• Delete-only compactions that drop whole sstables that fall within the bounds
  of a range deletion.
• Block-property collectors and filters that enable iterators to skip tables,
  index blocks and data blocks that are irrelevant, according to user-defined
  properties over key-value pairs.
• Range keys API, allowing KV pairs defined over a range of keyspace with
  user-defined semantics and interleaved during iteration.
• Smaller, more approachable code base.

See the Pebble vs RocksDB: Implementation
Differences doc for more details on implementation
differences.

RocksDB Compatibility Copy Chapter

Pebble v1 strives for forward compatibility with RocksDB 6.2.1 (the latest
version of RocksDB used by CockroachDB). Forward compatibility means that a DB
generated by RocksDB 6.2.1 can be upgraded for use by Pebble. Pebble versions in
the v1 series may open DBs generated by RocksDB 6.2.1. Since its introduction,
Pebble has adopted various backwards-incompatible format changes that are gated
behind new 'format major versions'. Pebble v2 and newer does not support
opening DBs generated by RocksDB. DBs generated by RocksDB may only be used with
recent versions of Pebble after migrating them through format major version
upgrades using previous versions of Pebble. See the below section of format
major versions.

Even the RocksDB-compatible versions of Pebble only provide compatibility with
the subset of functionality and configuration used by CockroachDB. The scope of
RocksDB functionality and configuration is too large to adequately test and
document all the incompatibilities. The list below contains known
incompatibilities.

• Pebble's use of WAL recycling is only compatible with RocksDB's
  kTolerateCorruptedTailRecords WAL recovery mode. Older versions of
  RocksDB would automatically map incompatible WAL recovery modes to
  kTolerateCorruptedTailRecords. New versions of RocksDB will
  disable WAL recycling.
• Column families. Pebble does not support column families, nor does
  it attempt to detect their usage when opening a DB that may contain
  them.
• Hash table format. Pebble does not support the hash table sstable
  format.
• Plain table format. Pebble does not support the plain table sstable
  format.
• SSTable format version 3 and 4. Pebble does not support version 3
  and version 4 format sstables. The sstable format version is
  controlled by the BlockBasedTableOptions::format_version option.
  See #97.

Format major versions Copy Chapter

Over time Pebble has introduced new physical file formats. Backwards
incompatible changes are made through the introduction of 'format major
versions'. By default, when Pebble opens a database, it defaults to the lowest
supported version. In v1, this is FormatMostCompatible, which is
bi-directionally compatible with RocksDB 6.2.1 (with the caveats described
above).

Databases created by RocksDB or Pebble versions v1 and earlier must be upgraded
to a compatible format major version before running newer Pebble versions. Newer
Pebble versions will refuse to open databases in no longer supported formats.

To opt into new formats, a user may set FormatMajorVersion on the
Options
supplied to
Open, or
upgrade the format major version at runtime using
DB.RatchetFormatMajorVersion.
Format major version upgrades are permanent; There is no option to
return to an earlier format.

The table below outlines the history of format major versions, along with what
range of Pebble versions support that format.

Upgrading to a format major version with 'Background' in the migration
column may trigger background activity to rewrite physical file
formats, typically through compactions. Upgrading to a format major
version with 'Blocking' in the migration column will block until a
migration is complete. The database may continue to serve reads and
writes if upgrading a live database through
RatchetFormatMajorVersion, but the method call will not return until
the migration is complete.

Upgrading existing stores can be performed via the RatchetFormatMajorVersion
method. If the database does not use a custom comparer, merger, or block
property collectors, the pebble tool can also be used, at the latest version
that supports the format. For example:

# WARNING: only use if no custom comparer/merger/property collector are necessary.
go run github.com/cockroachdb/pebble/cmd/[email protected] db upgrade <db-dir>

For reference, the table below lists the range of supported Pebble format major
versions for CockroachDB releases.

Pedigree Copy Chapter

Pebble is based on the incomplete Go version of LevelDB:

https://github.com/golang/leveldb

The Go version of LevelDB is based on the C++ original:

https://github.com/google/leveldb

Optimizations and inspiration were drawn from RocksDB:

https://github.com/facebook/rocksdb

Getting Started Copy Chapter

Example Code Copy Section

package main

import (
	"fmt"
	"log"

	"github.com/cockroachdb/pebble"
)

func main() {
	db, err := pebble.Open("demo", &pebble.Options{})
	if err != nil {
		log.Fatal(err)
	}
	key := []byte("hello")
	if err := db.Set(key, []byte("world"), pebble.Sync); err != nil {
		log.Fatal(err)
	}
	value, closer, err := db.Get(key)
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("%s %s\n", key, value)
	if err := closer.Close(); err != nil {
		log.Fatal(err)
	}
	if err := db.Close(); err != nil {
		log.Fatal(err)
	}
}

Overview (`internal/arenaskl/README.md`) Copy Section

arenaskl

Fast, lock-free, arena-based Skiplist implementation in Go that supports iteration
in both directions.

Advantages Copy Chapter

Arenaskl offers several advantages over other skiplist implementations:

• High performance that linearly scales with the number of cores. This is
  achieved by allocating from a fixed-size arena and by avoiding locks.
• Iterators that can be allocated on the stack and easily cloned by value.
• Simple-to-use and low overhead model for detecting and handling race conditions
  with other threads.
• Support for iterating in reverse (i.e. previous links).

Limitations Copy Chapter

The advantages come at a cost that prevents arenaskl from being a general-purpose
skiplist implementation:

• The size of the arena sets a hard upper bound on the combined size of skiplist
  nodes, keys, and values. This limit includes even the size of deleted nodes,
  keys, and values.
• Deletion is not supported. Instead, higher-level code is expected to
  add deletion tombstones and needs to process those tombstones
  appropriately.

Pedigree Copy Chapter

This code is based on Andy Kimball's arenaskl code:

https://github.com/andy-kimball/arenaskl

The arenaskl code is based on the skiplist found in Badger, a Go-based
KV store:

https://github.com/dgraph-io/badger/tree/master/skl

The skiplist in Badger is itself based on a C++ skiplist built for
Facebook's RocksDB:

https://github.com/facebook/rocksdb/tree/master/memtable

Benchmarks Copy Chapter

The benchmarks consist of a mix of reads and writes executed in parallel. The
fraction of reads is indicated in the run name: "frac_X" indicates a run where
X percent of the operations are reads.

The results are much better than skiplist and slist.

name                  time/op
ReadWrite/frac_0-8     470ns ±11%
ReadWrite/frac_10-8    462ns ± 3%
ReadWrite/frac_20-8    436ns ± 2%
ReadWrite/frac_30-8    410ns ± 2%
ReadWrite/frac_40-8    385ns ± 2%
ReadWrite/frac_50-8    360ns ± 4%
ReadWrite/frac_60-8    386ns ± 1%
ReadWrite/frac_70-8    352ns ± 2%
ReadWrite/frac_80-8    306ns ± 3%
ReadWrite/frac_90-8    253ns ± 4%
ReadWrite/frac_100-8  28.1ns ± 2%

Note that the above numbers are for concurrent operations using 8x
parallelism. The same benchmarks without concurrency (use these
numbers when comparing vs batchskl):

name                time/op
ReadWrite/frac_0    1.53µs ± 1%
ReadWrite/frac_10   1.46µs ± 2%
ReadWrite/frac_20   1.39µs ± 3%
ReadWrite/frac_30   1.28µs ± 3%
ReadWrite/frac_40   1.21µs ± 2%
ReadWrite/frac_50   1.11µs ± 3%
ReadWrite/frac_60   1.23µs ±17%
ReadWrite/frac_70   1.16µs ± 4%
ReadWrite/frac_80    959ns ± 3%
ReadWrite/frac_90    738ns ± 5%
ReadWrite/frac_100  81.9ns ± 2%

Forward and backward iteration are also fast:

name                time/op
IterNext            3.97ns ± 5%
IterPrev            3.88ns ± 3%

Overview (`internal/batchskl/README.md`) Copy Section

batchskl

Fast, non-concurrent skiplist implementation in Go that supports
forward and backward iteration.

Limitations Copy Chapter

• The interface is tailored for use in indexing pebble batches. Keys
  and values are stored outside of the skiplist making the skiplist
  awkward for general purpose use.
• Deletion is not supported. Instead, higher-level code is expected to
  add deletion tombstones and needs to process those tombstones
  appropriately.

Pedigree Copy Chapter

This code is based on Andy Kimball's arenaskl code.

The arenaskl code is based on the skiplist found in Badger, a Go-based
KV store:

https://github.com/dgraph-io/badger/tree/master/skl

The skiplist in Badger is itself based on a C++ skiplist built for
Facebook's RocksDB:

https://github.com/facebook/rocksdb/tree/master/memtable

Benchmarks Copy Chapter

The benchmarks consist of a mix of reads and writes executed in parallel. The
fraction of reads is indicated in the run name: "frac_X" indicates a run where
X percent of the operations are reads.

name                  time/op
ReadWrite/frac_0      1.03µs ± 2%
ReadWrite/frac_10     1.32µs ± 1%
ReadWrite/frac_20     1.26µs ± 1%
ReadWrite/frac_30     1.18µs ± 1%
ReadWrite/frac_40     1.09µs ± 1%
ReadWrite/frac_50      987ns ± 2%
ReadWrite/frac_60     1.07µs ± 1%
ReadWrite/frac_70      909ns ± 1%
ReadWrite/frac_80      693ns ± 2%
ReadWrite/frac_90      599ns ± 2%
ReadWrite/frac_100    45.3ns ± 3%

Forward and backward iteration are also fast:

name                  time/op
IterNext              4.49ns ± 3%
IterPrev              4.48ns ± 3%

Overview (`vfs/atomicfs/README.md`) Copy Section

Here’s a walkthrough of how this “atomic marker” system works, what files it
creates, and what to watch out for on Linux vs. Windows.

1. What is a “marker”? Copy Chapter

A marker is simply a file whose name encodes a string value and a
monotonically increasing counter. By always creating a new file for the next
value (and then deleting the old one), the code ensures that at any point
on-disk there is exactly one visible marker file whose name tells you “the
current value is X, at iteration N.”

Filenames have the pattern:

marker.<markerName>.<iteration>.<value>

• <markerName> is an arbitrary identifier you chose.
• `` is a zero-padded, 6-digit decimal.
• <value> is the new state you’re storing.

For example, if your marker is named foo, you might see files like:

marker.foo.000001.alpha
marker.foo.000002.beta

2. High-level API Copy Chapter

ReadMarker(fs, dir, markerName) Copy Section

• Lists all files in dir.
• Picks out those beginning with marker. and matching your markerName.
• Returns the highest-iteration file’s value (e.g. "beta").

LocateMarker(fs, dir, markerName) Copy Section

• Same as ReadMarker, but also opens dir for later syncing.
• Returns a *Marker object plus the current value.

3. Core logic: parsing and scanning Copy Chapter

func scanForMarker(fs vfs.FS, ls []string, markerName string) (scannedState, error)

• Iterates over filenames in ls.
• Calls parseMarkerFilename, which:
  1. Strips the marker. prefix.
  2. Splits off the name, the iteration (parsed via strconv.ParseUint), and the value.
• Keeps track of:
  • state.filename: the newest marker file seen so far.
  • state.iter: that file’s iteration number.
  • state.value: that file’s embedded value.
  • state.obsolete: a list of older marker files.

4. The `Marker` object Copy Chapter

Once you have a *Marker, you can do two things:

Move(newValue string) Copy Section

1. Increment the internal iter counter.
2. Build a filename marker.<name>..<newValue>.
3. Create that file via fs.Create(...).
4. Close it, then delete the old marker.* file.
5. Call dirFD.Sync() to flush the directory metadata.

If deletion of the old file fails, it’s remembered in an obsoleteFiles slice
for later cleanup.

RemoveObsolete() Copy Section

Loops over any filenames in obsoleteFiles and tries to remove them. Stops at
first error (leaving the remaining entries in obsoleteFiles).

5. Examples of files created Copy Chapter

Imagine we start with an empty directory and markerName = "task":

$ ls
# (empty)

// First LocateMarker → no existing files, iter=0, value=""
marker, _, err := LocateMarker(fs, "/path", "task")

// Move to "started":
marker.Move("started")
$ ls /path
marker.task.000001.started

// Move to "halfway":
marker.Move("halfway")
$ ls /path
marker.task.000002.halfway

// If RemoveObsolete hasn’t run yet, you might still see the old:
marker.RemoveObsolete()
$ ls /path
marker.task.000002.halfway

And if your value strings contain dots or special chars, they simply go into the
filename (so avoid /).

6. Linux vs. Windows quirks Copy Chapter

1. Path separators & case-sensitivity

• On Linux, files named marker.Task.000001.foo and marker.task.000001.foo are
  distinct.
• On Windows, filenames are case-insensitive, so your marker names should avoid
  differing only by letter case.

2. Directory sync (dirFD.Sync())

• Linux: opening a directory and fsync-ing its file descriptor reliably flushes the new/removed filenames to disk.
• Windows: the equivalent “flush directory metadata” is more limited. In some cases you may see the new file appear immediately but metadata not fully durable until later; and deleting a file that’s still in use can fail.

3. Deleting open files

• Linux lets you unlink (remove) a file even while a process still has it open; the file truly goes away only after all handles close.
• Windows generally refuses to delete an open file handle, so if another process still has the old marker open, the Remove call will error. That error is caught and the old filename pushed into obsoleteFiles.

4. Maximum filename length

• Windows MAX_PATH (260 chars) may be hit if your <value> is long; Linux allows up to around 255 bytes per component. Keep your values short.

Summary Copy Section

• Naming scheme: marker.<name>.<6-digit-iter>.<value>
• Read/Locate: scan the directory, pick the highest iter.
• Move: create new marker file, delete old, sync.
• Cleanup: RemoveObsolete() for any leftovers.
• Linux vs. Windows: watch case sensitivity, directory‐sync semantics, and
  open‐file deletion behavior.

This pattern guarantees that at most one marker file is “current,” and that any
failure mid‐move leaves you either at the old value or the new one—never a
corrupted state.

Overview (`internal/mkbench/testdata/README.md`) Copy Section

testdata

The files in this directory serve as test fixtures, used for validating that
the mkbench command produces the expected output when reading and writing
various Pebble benchmark data.

The data was generated by downloading a sample of existing raw benchmark log
data from the
pebble-benchmarks
S3 bucket. The data was trimmed so as to reduce the amount of data checked into
version control, with something akin to:

for _file in $(find "$DOWNLOADED_DATA" -name '*.gz'); do
  gunzip --to-stdout "$_file" \
    | grep 'Benchmarkycsb' -B 10 -A 10 \
    | gzip > "$OUTPUT_DIR/$(basename "$_file")"
done

Io Profiling (`docs/io_profiling.md`) Copy Section

I/O Profiling

Linux provide extensive kernel profiling capabilities, including the
ability to trace operations at the block I/O layer. These tools are
incredibly powerful, though sometimes overwhelming in their
flexibility. This document captures some common recipes for profiling
Linux I/O.

• Perf
• Blktrace

Perf Copy Chapter

The Linux perf command can instrument CPU performance counters, and
the extensive set of kernel trace points. A great place to get started
understanding perf are Brendan Gregg's perf
examples.

The two modes of operation are "live" reporting via perf top, and
record and report via perf record and perf {report,script}.

Recording the stack traces for block:block_rq_insert event allows
determination of what Pebble level code is generating block requests.

Installation Copy Section

Ubuntu AWS installation:

sudo apt-get install linux-tools-common linux-tools-4.4.0-1049-aws linux-cloud-tools-4.4.0-1049-aws

Recording Copy Section

perf record (and perf top) requires read and write access to
/sys/kernel/debug/tracing. Running as root as an easiest way to get
the right permissions.

# Trace all block device (disk I/O) requests with stack traces, until Ctrl-C.
sudo perf record -e block:block_rq_insert -ag

# Trace all block device (disk I/O) issues and completions with stack traces, until Ctrl-C.
sudo perf record -e block:block_rq_issue -e block:block_rq_complete -ag

The -a flag records events on all CPUs (almost always desirable).

The -g flag records call graphs (a.k.a stack traces). Capturing the
stack trace makes the recording somewhat more expensive, but it
enables determining the originator of the event. Note the stack traces
include both the kernel and application code, allowing pinpointing the
source of I/O as due to flush, compaction, WAL writes, etc.

The -e flag controls which events are instrumented. The list of
perf events is enormous. See sudo perf list.

The -o flag controls where output is recorded. The default is
perf.data.

In order to record events for a specific duration, you can append -- sleep <duration> to the command line.

# Trace all block device (disk I/O) requests with stack traces for 10s.
sudo perf record -e block:block_rq_insert -ag -- sleep 10

Reporting Copy Section

The recorded perf data (perf.data) can be explored using perf report and perf script.

# Show perf.data in an ncurses browser.
sudo perf report

# Show perf.data as a text report.
sudo perf report --stdio

As an example, perf report --stdio from perf data gathered using
perf record -e block:block_rq_insert -ag will show something like:

/* Detailed source-code truncated for AI context efficiency. */

This is showing that 96.76% of block device requests on the entire
system were generated by the pebble process, and 85.58% of the
block device requests on the entire system were generated from WAL
syncing within this pebble process.

The perf script command provides access to the raw request
data. While there are various pre-recorded scripts that can be
executed, it is primarily useful for seeing call stacks along with the
"trace" data. For block requests, the trace data shows the device, the
operation type, the offset, and the size.

/* Detailed source-code truncated for AI context efficiency. */

Let's break down the trace data:

259,0 WS 0 () 3970952 + 256
 |     |         |       |
 |     |         |       + size (sectors)
 |     |         |
 |     |         + offset (sectors)
 |     |
 |     +- flags: R(ead), W(rite), B(arrier), S(ync), D(iscard), N(one)
 |
 +- device: <major>, <minor>

The above is indicating that a synchronous write of 256 sectors was
performed starting at sector 3970952. The sector size is device
dependent and can be determined with blockdev --report <device>,
though it is almost always 512 bytes. In this case, the sector size
is 512 bytes indicating that this is a write of 128 KB.

Blktrace Copy Chapter

The blktrace tool records similar info to perf, but is targeted to
the block layer instead of being general purpose. The blktrace
command records data, while the blkparse command parses and displays
data. The btrace command is a shortcut for piping the output from
blktrace directly into `blkparse.

Installation Copy Section

Ubuntu AWS installation:

sudo apt-get install blktrace

Usage Copy Chapter

# Pipe the output of blktrace directly into blkparse.
sudo blktrace -d /dev/nvme1n1 -o - | blkparse -i -

# Equivalently.
sudo btrace /dev/nvme1n1

The information captured by blktrace is similar to what perf captures:

sudo btrace /dev/nvme1n1
...
259,0    4      186     0.016411295 11538  Q  WS 129341760 + 296 [pebble]
259,0    4      187     0.016412100 11538  Q  WS 129342016 + 40 [pebble]
259,0    4      188     0.016412200 11538  G  WS 129341760 + 256 [pebble]
259,0    4      189     0.016412714 11538  G  WS 129342016 + 40 [pebble]
259,0    4      190     0.016413148 11538  U   N [pebble] 2
259,0    4      191     0.016413255 11538  I  WS 129341760 + 256 [pebble]
259,0    4      192     0.016413321 11538  I  WS 129342016 + 40 [pebble]
259,0    4      193     0.016414271 11538  D  WS 129341760 + 256 [pebble]
259,0    4      194     0.016414860 11538  D  WS 129342016 + 40 [pebble]
259,0   12      217     0.016687595     0  C  WS 129341760 + 256 [0]
259,0   12      218     0.016700021     0  C  WS 129342016 + 40 [0]

The standard format is:

<device> <cpu> <seqnum> <timestamp> <pid> <action> <RWBS> <start-sector> + <size> [<command>]

See man blkparse for an explanation of the actions.

The blktrace output can be used to highlight problematic I/O
patterns. For example, it can be used to determine there are an
excessive number of small sequential read I/Os indicating that dynamic
readahead is not working correctly.

Memory (`docs/memory.md`) Copy Section

Memory Management

Background Copy Chapter

Pebble has two significant sources of memory usage: MemTables and the
Block Cache. MemTables buffer data that has been written to the WAL
but not yet flushed to an SSTable. The Block Cache provides a cache of
uncompressed SSTable data blocks.

Originally, Pebble used regular Go memory allocation for the memory
backing both MemTables and the Block Cache. This was problematic as it
put significant pressure on the Go GC. The higher the bandwidth of
memory allocations, the more work GC has to do to reclaim the
memory. In order to lessen the pressure on the Go GC, an "allocation
cache" was introduced to the Block Cache which allowed reusing the
memory backing cached blocks in most circumstances. This produced a
dramatic reduction in GC pressure and a measurable performance
improvement in CockroachDB workloads.

Unfortunately, the use of Go allocated memory still caused a
problem. CockroachDB running on top of Pebble often resulted in an RSS
(resident set size) 2x what it was when using RocksDB. The cause of
this effect is due to the Go runtime's heuristic for triggering GC:

A collection is triggered when the ratio of freshly allocated data
to live data remaining after the previous collection reaches this
percentage.

This percentage can be configured by the
GOGC environment variable or by
calling
debug.SetGCPercent. The
default value is 100, which means that GC is triggered when the
freshly allocated data is equal to the amount of live data at the end
of the last collection period. This generally works well in practice,
but the Pebble Block Cache is often configured to be 10s of gigabytes
in size. Waiting for 10s of gigabytes of data to be allocated before
triggering a GC results in very large Go heap sizes.

Manual Memory Management Copy Chapter

Attempting to adjust GOGC to account for the significant amount of
memory used by the Block Cache is fraught. What value should be used?
10%? 20%? Should the setting be tuned dynamically? Rather than
introducing a heuristic which may have cascading effects on the
application using Pebble, we decided to move the Block Cache and
MemTable memory out of the Go heap. This is done by using the C memory
allocator, though it could also be done by providing a simple memory
allocator in Go which uses mmap to allocate memory.

In order to support manual memory management for the Block Cache and
MemTables, Pebble needs to precisely track their lifetime. This was
already being done for the MemTable in order to account for its memory
usage in metrics. It was mostly being done for the Block Cache. Values
stores in the Block Cache are reference counted and are returned to
the "alloc cache" when their reference count falls
to 0. Unfortunately, this tracking wasn't precise and there were
numerous cases where the cache values were being leaked. This was
acceptable in a world where the Go GC would clean up after us. It is
unacceptable if the leak becomes permanent.

Leak Detection Copy Chapter

In order to find all of the cache value leaks, Pebble has a leak
detection facility built on top of
runtime.SetFinalizer. A
finalizer is a function associated with an object which is run when
the object is no longer reachable. On the surface, this sounds perfect
as a facility for performing all memory reclamation. Unfortunately,
finalizers are generally frowned upon by the Go implementors, and come
with very loose guarantees:

The finalizer is scheduled to run at some arbitrary time after the
program can no longer reach the object to which obj points. There is
no guarantee that finalizers will run before a program exits, so
typically they are useful only for releasing non-memory resources
associated with an object during a long-running program

This language is somewhat frightening, but in practice finalizers are run at the
end of every GC period. Pebble primarily relies on finalizers for its leak
detection facility. In the block cache, a finalizer is associated with the Go
allocated cache.Value object. When the finalizer is run, it checks that the
buffer backing the cache.Value has been freed. This leak detection facility is
enabled by the "invariants" build tag which is enabled by the Pebble unit
tests.

There also exists a very specific memory reclamation use case in the block cache
that ensures that structs with transitively reachable fields backed by manually
allocated memory that are pooled in a sync.Pool are freed correctly when their
parent struct is released from the pool and consequently garbage collected by
the Go runtime (see internal/cache/entry.go). The loose guarantees provided by
the runtime are reasonable to rely on in this case to prevent a memory leak.

Range Deletions (`docs/range_deletions.md`) Copy Section

Range Deletions

TODO: The following explanation of range deletions does not take into account
the recent change to prohibit splitting of a user key between sstables. This
change simplifies the logic, removing 'improperly truncated range tombstones.'

TODO: The following explanation of range deletions ignores the
kind/trailer that appears at the end of keys after the sequence
number. This should be harmless but need to add a justification on why
it is harmless.

Background and Notation Copy Chapter

Range deletions are represented as [start, end)#seqnum. Points
(set/merge/...) are represented as key#seqnum. A range delete [s, e)#n1
deletes every point k#n2 where k \in [s, e) and n2 < n1.
The inequality n2 < n1 is to handle the case where a range delete and
a point have the same sequence number -- this happens during sstable
ingestion where the whole sstable is assigned a single sequence number
that applies to all the data in it.

There is additionally an infinity sequence number, represented as
inf, which is not used for any point, that we can use for reasoning
about range deletes.

It has been asked why range deletes use an exclusive end key instead
of an inclusive end key. For string keys, one can convert a desired
range delete on [s, e] into a range delete on [s, ImmediateSuccessor(e)).
For strings, the immediate successor of a key
is that key with a \0 appended to it. However one cannot go in the
other direction: if one could represent only inclusive end keys in a
range delete and one desires to delete a range with an exclusive end
key [s, e)#n, one needs to compute ImmediatePredecessor(e) which
is an infinite length string. For example,
ImmediatePredecessor("ab") is "aa\xff\xff....". Additionally,
regardless of user needs, the exclusive end key helps with splitting a
range delete as we will see later.

We will sometimes use ImmediatePredecessor and ImmediateSuccessor in
the following for illustrating an idea, but we do not rely on them as
something that is viable to produce for a particular kind of key. And
even if viable, these functions are not currently provided to
RockDB/Pebble.

Visualization Copy Section

If we consider a 2 dimensional space with increasing keys on the X
axis (with every possible user key represented) and increasing
sequence numbers on the Y axis, range deletes apply to a rectangle
whose bottom edge sits on the X axis.

The actual space represented by the ordering in our sstables is a one
dimensional space where k1#n1 is less than k2#n2 if either of the
following holds:

• k1 < k2

• k1 = k2 and n1 > n2 (under the assumption that no two points with
  the same key have the same sequence number).

^
  |   .       > .        > .        > yy
  |   .      >  .       >  .       >  .
  |   .     >   .      >   .      >   .
n |   V    >    xx    >    .     >    V
  |   .   >     x.   >     x.   >     . 
  |   .  >      x.  >      x.  >      .
  |   . >       x. >       x. >       .
  |   .>        x.>        x.>        .
  ------------------------------------------>
                k        IS(k)    IS(IS(k))

The above figure uses . to represent points and the X axis is dense in
that it represents all possible keys. xx represents the start of a
range delete and x. are the points which it deletes. The arrows V and
> represent the ordering of the points in the one dimensional space.
IS is shorthand for ImmediateSuccessor and the range delete represented
there is [k, IS(IS(k)))#n. Ignore yy for now.

The one dimensional space works fine in a world with only points. But
issues arise when storing range deletes, that represent an action in 2
dimensional space, into this one dimensional space.

Range Delete Boundaries and the Simplest World Copy Chapter

RocksDB/Pebble store the inclusive bounds of each sstable in one dimensional
space. The range deletes two dimensional behavior and exclusive end key needs
to be adapted to this requirement. For a range delete [s, e)#n,
the smallest key it acts on is s#(n-1) and the largest key it
acts on is ImmediatePredecessor(e)#0. So if we position the range delete
immediately before the smallest key it acts on and immediately after
the largest key it acts on we can give it a tight inclusive bound of
[s#n, e#inf].

Note again that this range delete does not delete everything in its
inclusive bound. For example, range delete ["c", "h")#10 has a tight
inclusive bound of ["c"#10, "h"#inf] but does not delete "d"#11
which lies in that bound. Going back to our earlier diagram, the one
dimensional inclusive bounds go from the xx to yy but there are
.s in between, in the one dimensional order, that are not deleted.

This is the reason why one cannot in general
use a range delete to seek over all points within its bounds. The one
exception to this seeking behaviour is that when we can order sstables
from new to old, one can "blindly" use this range delete in a newer
sstable to seek to "h" in all older sstables since we know those
older sstables must only have point keys with sequence numbers < 10
for the keys in interval ["c", "h"). This partial order across
sstables exists in RocksDB/Pebble between memtable, L0 sstables (where
it is a total order) and across sstables in different levels.

Coming back to the inclusive bounds of the range delete, [s#n, e#inf]:
these bounds participate in deciding the bounds of the
sstable. In this world, one can read all the entries in an sstable and
compute its bounds. However being able to construct these bounds by
reading an sstable is not essential -- RocksDB/Pebble store these
bounds in the MANIFEST. This latter fact has been exploited to
construct a real world (later section) where the bounds of an sstable
are not computable by reading all its keys.

If we had a system with one sstable per level, for each level lower
than L0, we are effectively done. We have represented the tight bounds
of each range delete and it is within the bounds of the sstable. This
works even with L0 => L0 compactions assuming they output exactly one
sstable.

The Mostly Simple World Copy Chapter

Here we have multiple files for levels lower than L0 that are non
overlapping in the file bounds. These multiple files occur because
compactions produce multiple files. This introduces the need to split a
range delete across the files being produced by a compaction.

There is a clean way to split a range delete [s, e)#n into 2 parts
(which can be recursively applied to split into arbitrarily many
parts): split into [s, m)#n and [m, e)#n. These range deletes
apply to non-overlapping points and their tight bounds are [s#m, m#inf], [m#n, e#inf] which are also non-overlapping.

Consider the following example of an input range delete ["c", "h")#10 and
the following two output files from a compaction:

sst1            sst2
last point is "e"#7 | first point is "f"#20

The range delete can be split into ["c", "f")#10 and ["f", "h")#10, by using the first point key of sst2 as the split
point. Then the bounds of sst1 and sst2 will be [..., "f"#inf] and
["f"#20, ...] which are non-overlapping. It is still possible to compute
the sstable bounds by looking at all the entries in the sstable.

The Real World Copy Chapter

Continuing with the same range delete ["c", "h")#10, we can have the
following sstables produced during a compaction:

sst1       sst2         sst3        sst4     sst5
points: "e"#7 | "f"#12 "f"#7 | "f"#4 "f"#3 | "f"#1 | "g"#15

The range deletes written to these ssts are

sst1           sst2            sst3           sst4          sst5
["c", "h")#10 | ["f", "h")#10 | ["f", "h")#10 | ["f", "h")#10 | ["g", "h")#10

The Pebble code that achieves this effect is in
rangedel.Fragmenter. It is a code structuring artifact that sst1
does not contain a range delete equal to ["c", "f")#10 and sst4 does
not contain ["f", "g")#10. However for the range deletes in sst2 and
sst3 we cannot do any better because we don't know what the key
following "f" will be (the compaction cannot look ahead) and because
we don't have an ImmediateSuccessor function (otherwise we could
have written ["f", ImmediateSuccessor("f"))#10 to sst2, sst3). But
the code artifacts are not the ones introducing the real complexity.

The range delete bounds are

sst1        sst2, sst3, sst4          sst5
["c"#10, "h"#inf] ["f"#10, "h"#inf]   ["g"#10, "h"#inf]

We note the following:

• The bounds of range deletes are overlapping since we have been
  unable to split the range deletes. If these decide the sstable
  bounds, the sstables will have overlapping bounds. This is not
  permissible.

• The range deletes included in each sstable result in that sstable
  being "self-sufficient" wrt having the range delete that deletes
  some of the points in the sstable (let us assume that the points in
  this example have not been dropped from that sstable because of a
  snapshot).

• The transitions from sst1 to sst2 and sst4 to sst5 are clean in
  that we can pretend that the range deletes in those files are actually:

sst1           sst2            sst3           sst4          sst5
["c", "f")#10 | ["f", "g")#10 | ["f", "g")#10 | ["f", "g")#10 | ["g", "h")#10

We could achieve some of these clean transitions (but not all) with a
code change. Also note that these better range deletes maintain the
"self-sufficient" property.

Making Non-overlapping SSTable bounds Copy Section

We force the sstable bounds to be non-overlapping by setting them to:

sst1              sst2           sst3            sst4              sst5
["c"#10, "f"#inf] ["f"#12, "f"#7] ["f"#4, "f"#3] ["f"#1, "g"#inf] ["g"#15, "h"#inf]

Note that for sst1...sst4 the sstable bounds are smaller than the
bounds of the range deletes contained in them. The code that
accomplishes this is Pebble is in compaction.go -- we will not discuss the
details of that logic here but note that it is placing an inf
sequence number for a clean transition and for an unclean transition
it is using the point keys as the bounds.

Associated with these narrower bounds, we add the following
requirement: a range delete in an sstable must act-within the bounds of
the sstable it is contained in. In the above example:

• sst1: range delete ["c", "h")#10 must act-within the bound ["c"#10, "f"#inf]

• sst2: range delete ["f", "h")#10 must act-within the bound ["f"#12, "f"#7]

• sst3: range delete ["f", "h")#10 must act-within the bound ["f"#4, "f"#3]

• sst4: range delete ["f", "h")#10 must act-within the bound ["f"#1, "g"#inf]

• And so on.

The intuitive reason for the act-within requirement is that
sst5 can be compacted and moved down to a lower level independent of
sst1-sst4, since it was at a clean boundary. We do not want the
range delete ["f", "h")#10 sitting in sst1...sst4 at the higher
level to act on "g"#15 that has been moved to the lower level. Note
that this incorrect action can happen due to 2 reasons:

1. the invariant that lower levels have older data for keys
   that also exist in higher levels means we can (a) seek a lower level
   sstable to the end of a range delete from a higher level, (b) for a key
   lookup, stop searching in lower levels once a range delete is encountered
   for that key in a higher level.

2. Sequence number zeroing logic can change the sequence number of
   "g"#15 to "g"#0 (for better compression) once it realizes that
   there are no older versions of "g". It would be incorrect for this
   "g"#0 to be deleted.

Loss of Power

This act-within behavior introduces some "loss of power" for
the original range delete ["c", "h")#10. By acting within sst2...sst4
it can no longer delete keys "f"#6, "f"#5, "f"#2.

Luckily for us, this is harmless since these keys cannot have existed
in the system due to the levelling behavior: we cannot be writing
sst2...sst4 to level i if versions of "f" younger than "f"#4 are
already in level i or version older than "f"#7 have been left in
level i - 1. There is some trickery possible to prevent this "loss of
power" for queries (see the "Putting it together" section), but given
the history of bugs in this area, we should be cautious.

Improperly truncated Range Deletes Copy Section

We refer to range deletes that have experienced this "loss of power"
as improper. In the above example the range deletions in sst2, sst3, sst4
are improper. The problem with improper range deletions occurs
when they need to participate in a future compaction: even though we
have restricted them to act-within their current sstable boundary, we
don't have a way of "writing" this restriction to a new sstable,
since they still need to be written in the [s, e)#n format.

For example, sst2 has delete ["f", "h")#10 that must act-within
the bound ["f"#12, "f"#7]. If sst2 was compacted down to the next
level into a new sstable (whose bounds we cannot predict because they
depend on other data written to that sstable) we need to be able to
write a range delete entry that follows the original restriction. But
the narrowest we can write is ["f", ImmediateSuccessor("f"))#10. This
is an expansion of the act-within restriction with potentially
unintended consequences. In this case the expansion happened in the suffix.
For sst4, the range deletion ["f", "h")#10 must act-within ["f"#1, "g"#inf],
and we can precisely represent the constraint on the suffix by writing
["f", "g")#10 but it does not precisely represent that this range delete
should not apply to "f"#9..."f"#2.

In comparison, the sst1 range delete ["c", "h")#10 that must act-within
the bound ["c"#10, "f"#inf] is not improper. This restriction can
be applied precisely to get a range delete ["c", "f")#10.

The solution to this is to note that while individual sstables have
improper range deletes, if we look at a collection of sstables we
can restore the improper range deletes spread across them to their proper self
(and their full power). To accurately find these improper range
deletes would require looking into the contents of a file, which is
expensive. But we can construct a pessimistic set based on
looking at the sequence of all files in a level and partitioning them:
adjacent files f1, f2 with largest and smallest bound k1#n1,
k2#n2 must be in the same partition if

k1 = k2 and n1 != inf

In the above example sst2, sst3, sst4 are one partition. The
spanning bound of this partition is ["f"#12, "g"#inf] and the
range delete ["f", "h")#10 when constrained to act-within this
spanning bound is precisely the range delete ["f", "g")#10. Intuitively, the "loss of power" of this range delete has
been restored for the sake of making it proper, so it can be
accurately "written" in the output of the compaction (it may be
improperly fragmented again in the output, but we have already
discussed that). Such partitions are called "atomic compaction groups"
and must participate as a whole in a compaction (and a
compaction can use multiple atomic compaction groups as input).

Consider another example:

sst1              sst2
points:  "e"#12         |  "e"#10
delete: ["c", "g")#8    | ["c", "g")#8
bounds  ["c"#8, "e"#12] | ["e"#10, "g"#inf]

sst1, sst2 are an atomic compaction group. Say we violated the
requirement that both be inputs in a compaction and only compacted
sst2 down to level i + 1 and then down to level i + 2. Then we add
sst3 with bounds ["h"#10, "j"#5] to level i and sst1 and sst3 are
compacted to level i + 1 into a single sstable. This new sstable
will have bounds ["c"#8, "j"#5] so these bounds do not help with the
original apply-witin constraint on ["c", "g")#8 (that it should
apply-within ["c"#8, "e"#12]). The narrowest we can construct (if we had
ImmediateSuccessor) would be ["c", ImmediateSuccessor("e"))#8. Now we
can incorrectly apply this range delete that is in level i + 1 to "e"#10
sitting in level i + 2. Note that this example can be made worse using
sequence number zeroing -- "e"#10 may have been rewritten to "e"#0.

If a range delete [s, e)#n is in an atomic compaction group with
spanning bounds [k1#n1, k2#n2] our construction above guarantees the
following properties

• k1#n1 <= s#n, so the bounds do not constrain the start of the
  range delete.

• k2 >= e or n2 = inf, so if k2 is constraining the range delete
  it will properly truncate the range delete.

New sstable at sequence number 0

A new sstable can be assigned sequence number 0 (and be written to L0)
if the keys in the sstable are not in any other sstable. This
comparison uses the keys and not key#seqnum, so the loss and
restoration of power does not cause problems since that occurs within
the versions of a single key.

Flawed optimizations

For the case where the atomic compaction group correspond to the lower
level of a compaction, it may initially seem to be correct to use only
a prefix or suffix of that group in a compaction. In this case the
prefix (suffix) will correspond to the largest key (smallest key) in
the input sstables in the compaction and so can continue to constrain
the range delete. For example, sst1 and sst2 are in the same atomic
compaction group

sst1               sst2
points: "c"#10 "e"#12    |  "e"#10
delete: ["c", "g")#8     | ["c", "g")#8
bounds  ["c"#10, "e"#12] | ["e"#10, "g"#inf]

and this is the lower level of a compaction with

sst3
points: "a"#14 "d"#15
bounds  ["a"#14, "d"#15]

we could allow for a compaction involving sst1 and sst3 which would produce

sst4
points: "a"#14 "c"#10 "d"#15 "e"#12
delete: ["c", "g")#8
bounds  ["a"#14, "e"#12]

and the range delete is still improper but its act-within constraint has
not expanded.

But we have to be very careful to not have a more significant loss of power
of this range delete. Consider a situation where sst3 had a single delete
"e"#16. It still does not overlap in bounds with sst2 and we again pick
sst1 and sst3 for compaction. This single delete will cause "e"#12 to be deleted
and sst4 bounds would be (unless we had complicated code preventing it):

sst4
points: "a"#14 "c"#10 "d"#15
delete: ["c", "g")#8
bounds  ["a"#14, "d"#15]

Now this delete cannot delete "dd"#6 and we have lost the ability to know
that sst4 and sst2 are in the same atomic compaction group.

Putting it together Copy Section

Summarizing the above, we have:

• SStable bounds logic that ensures sstables are not
  overlapping. These sstables contain range deletes that extend outside
  these bounds. But these range deletes should apply-within the
  sstable bounds.

• Compactions: they need to constrain the range deletes in the inputs
  to apply-within, but this can create problems with writing the
  improper range deletes. The solution is to include the full
  atomic compaction group in a compaction so we can restore the
  improper range deletes to their proper self and then apply the
  constraints of the atomic compaction group.

• Queries: We need to act-within the file bound constraint on the range delete.
  Say the range delete is [s, e)#n and the file bound is [b1#n1, b2#n2]. We are guaranteed that b1#n1 <= s#n so the only
  constraint can come from b2#n2.

  • Deciding whether a range delete covers a key in the same or lower levels.

    • b2 >= e: there is no act-within constraint.
    • b2 < e: to be precise we cannot let it delete b2#n2-1 or
      later keys. But it is likely that allowing it to delete up to
      b2#0 would be ok due to the atomic compaction group. This
      would prevent the so-called "loss of power" discussed earlier if
      one also includes the argument that the gap in the file bounds
      that also represents the loss of power is harmless (the gap
      exists within versions of key, and anyone doing a query for that
      key will start from the sstable to the left of the gap). But it
      may be better to be cautious.

  • For using the range delete to seek sstables at lower levels.

    • b2 >= e: seek to e since there is no act-within constraint.
    • b2 < e: seek to b2. We are ignoring that this range delete
      is allowed to delete some versions of b2 since this is just a
      performance optimization.

Rocksdb (`docs/rocksdb.md`) Copy Section

Pebble vs RocksDB: Implementation Differences

RocksDB is a key-value store implemented using a Log-Structured
Merge-Tree (LSM). This document is not a primer on LSMs. There exist
some decent
introductions
on the web, or try chapter 3 of Designing Data-Intensive
Applications.

Pebble inherits the RocksDB file formats, has a similar API, and
shares many implementation details, but it also has many differences
that improve performance, reduce implementation complexity, or extend
functionality. This document highlights some of the more important
differences.

• Internal Keys
• Indexed Batches
• Large Batches
• Commit Pipeline
• Range Deletions
• Flush and Compaction Pacing
• Write Throttling
• Other Differences

Internal Keys Copy Chapter

The external RocksDB API accepts keys and values. Due to the LSM
structure, keys are never updated in place, but overwritten with new
versions. Inside RocksDB, these versioned keys are known as Internal
Keys. An Internal Key is composed of the user specified key, a
sequence number and a kind. On disk, sstables always store Internal
Keys.

+-------------+------------+----------+
  | UserKey (N) | SeqNum (7) | Kind (1) |
  +-------------+------------+----------+

The Kind field indicates the type of key: set, merge, delete, etc.

While Pebble inherits the Internal Key encoding for format
compatibility, it diverges from RocksDB in how it manages Internal
Keys in its implementation. In RocksDB, Internal Keys are represented
either in encoded form (as a string) or as a ParsedInternalKey. The
latter is a struct with the components of the Internal Key as three
separate fields.

struct ParsedInternalKey {
  Slice  user_key;
  uint64 seqnum;
  uint8  kind;
}

The component format is convenient: changing the SeqNum or Kind is
field assignment. Extracting the UserKey is a field
reference. However, RocksDB tends to only use ParsedInternalKey
locally. The major internal APIs, such as InternalIterator, operate
using encoded internal keys (i.e. strings) for parameters and return
values.

To give a concrete example of the overhead this causes, consider
Iterator::Seek(user_key). The external Iterator is implemented on
top of an InternalIterator. Iterator::Seek ends up calling
InternalIterator::Seek. Both Seek methods take a key, but
InternalIterator::Seek expects an encoded Internal Key. This is both
error prone and expensive. The key passed to Iterator::Seek needs to
be copied into a temporary string in order to append the SeqNum and
Kind. In Pebble, Internal Keys are represented in memory using an
InternalKey struct that is the analog of ParsedInternalKey. All
internal APIs use InternalKeys, with the exception of the lowest
level routines for decoding data from sstables. In Pebble, since the
interfaces all take and return the InternalKey struct, we don’t need
to allocate to construct the Internal Key from the User Key, but
RocksDB sometimes needs to allocate, and encode (i.e. make a
copy). The use of the encoded form also causes RocksDB to pass encoded
keys to the comparator routines, sometimes decoding the keys multiple
times during the course of processing.

Indexed Batches Copy Chapter

In RocksDB, a batch is the unit for all write operations. Even writing
a single key is transformed internally to a batch. The batch internal
representation is a contiguous byte buffer with a fixed 12-byte
header, followed by a series of records.

+------------+-----------+--- ... ---+
  | SeqNum (8) | Count (4) |  Entries  |
  +------------+-----------+--- ... ---+

Each record has a 1-byte kind tag prefix, followed by 1 or 2 length
prefixed strings (varstring):

+----------+-----------------+-------------------+
  | Kind (1) | Key (varstring) | Value (varstring) |
  +----------+-----------------+-------------------+

(The Kind indicates if there are 1 or 2 varstrings. Set, Merge,
and DeleteRange have 2 varstrings, while Delete has 1.)

Adding a mutation to a batch involves appending a new record to the
buffer. This format is extremely fast for writes, but the lack of
indexing makes it untenable to use directly for reads. In order to
support iteration, a separate indexing structure is created. Both
RocksDB and Pebble use a skiplist for the indexing structure, but with
a clever twist. Rather than the skiplist storing a copy of the key, it
simply stores the offset of the record within the mutation buffer. The
result is that the skiplist acts a multi-map (i.e. a map that can have
duplicate entries for a given key). The iteration order for this map
is constructed so that records sort on key, and for equal keys they
sort on descending offset. Newer records for the same key appear
before older records.

While the indexing structure for batches is nearly identical between
RocksDB and Pebble, how the index structure is used is completely
different. In RocksDB, a batch is indexed using the
WriteBatchWithIndex class. The WriteBatchWithIndex class provides
a NewIteratorWithBase method that allows iteration over the merged
view of the batch contents and an underlying "base" iterator created
from the database. BaseDeltaIterator contains logic to iterate over
the batch entries and the base iterator in parallel which allows us to
perform reads on a snapshot of the database as though the batch had
been applied to it. On the surface this sounds reasonable, yet the
implementation is incomplete. Merge and DeleteRange operations are not
supported. The reason they are not supported is because handling them
is complex and requires duplicating logic that already exists inside
RocksDB for normal iterator processing.

Pebble takes a different approach to iterating over a merged view of a
batch's contents and the underlying database: it treats the batch as
another level in the LSM. Recall that an LSM is composed of zero or
more memtable layers and zero or more sstable layers. Internally, both
RocksDB and Pebble contain a MergingIterator that knows how to merge
the operations from different levels, including processing overwritten
keys, merge operations, and delete range operations. The challenge
with treating the batch as another level to be used by a
MergingIterator is that the records in a batch do not have a
sequence number. The sequence number in the batch header is not
assigned until the batch is committed. The solution is to give the
batch records temporary sequence numbers. We need these temporary
sequence numbers to be larger than any other sequence number in the
database so that the records in the batch are considered newer than
any committed record. This is accomplished by reserving the high-bit
in the 56-bit sequence number for use as a marker for batch sequence
numbers. The sequence number for a record in an uncommitted batch is:

RecordOffset | (1<<55)

Newer records in a given batch will have a larger sequence number than
older records in the batch. And all of the records in a batch will
have larger sequence numbers than any committed record in the
database.

The end result is that Pebble's batch iterators support all of the
functionality of regular database iterators with minimal additional
code.

Large Batches Copy Chapter

The size of a batch is limited only by available memory, yet the
required memory is not just the batch representation. When a batch is
committed, the commit operation iterates over the records in the batch
from oldest to newest and inserts them into the current memtable. The
memtable is an in-memory structure that buffers mutations that have
been committed (written to the Write Ahead Log), but not yet written
to an sstable. Internally, a memtable uses a skiplist to index
records. Each skiplist entry has overhead for the index links and
other metadata that is a dozen bytes at minimum. A large batch
composed of many small records can require twice as much memory when
inserted into a memtable than it required in the batch. And note that
this causes a temporary increase in memory requirements because the
batch memory is not freed until it is completely committed.

A non-obvious implementation restriction present in both RocksDB and
Pebble is that there is a one-to-one correspondence between WAL files
and memtables. That is, a given WAL file has a single memtable
associated with it and vice-versa. While this restriction could be
removed, doing so is onerous and intricate. It should also be noted
that committing a batch involves writing it to a single WAL file. The
combination of restrictions results in a batch needing to be written
entirely to a single memtable.

What happens if a batch is too large to fit in a memtable? Memtables
are generally considered to have a fixed size, yet this is not
actually true in RocksDB. In RocksDB, the memtable skiplist is
implemented on top of an arena structure. An arena is composed of a
list of fixed size chunks, with no upper limit set for the number of
chunks that can be associated with an arena. So RocksDB handles large
batches by allowing a memtable to grow beyond its configured
size. Concretely, while RocksDB may be configured with a 64MB memtable
size, a 1GB batch will cause the memtable to grow to accommodate
it. Functionally, this is good, though there is a practical problem: a
large batch is first written to the WAL, and then added to the
memtable. Adding the large batch to the memtable may consume so much
memory that the system runs out of memory and is killed by the
kernel. This can result in a death loop because upon restarting as the
batch is read from the WAL and applied to the memtable again.

In Pebble, the memtable is also implemented using a skiplist on top of
an arena. Significantly, the Pebble arena is a fixed size. While the
RocksDB skiplist uses pointers, the Pebble skiplist uses offsets from
the start of the arena. The fixed size arena means that the Pebble
memtable cannot expand arbitrarily. A batch that is too large to fit
in the memtable causes the current mutable memtable to be marked as
immutable and the batch is wrapped in a flushableBatch structure and
added to the list of immutable memtables. Because the flushableBatch
is readable as another layer in the LSM, the batch commit can return
as soon as the flushableBatch has been added to the immutable
memtable list.

Internally, a flushableBatch provides iterator support by sorting
the batch contents (the batch is sorted once, when it is added to the
memtable list). Sorting the batch contents and insertion of the
contents into a memtable have the same big-O time, but the constant
factor dominates here. Sorting is significantly faster and uses
significantly less memory due to not having to copy the batch records.

Note that an effect of this large batch support is that Pebble can be
configured as an efficient on-disk sorter: specify a small memtable
size, disable the WAL, and set a large L0 compaction threshold. In
order to sort a large amount of data, create batches that are larger
than the memtable size and commit them. When committed these batches
will not be inserted into a memtable, but instead sorted and then
written out to L0. The fully sorted data can later be read and the
normal merging process will take care of the final ordering.

Commit Pipeline Copy Chapter

The commit pipeline is the component which manages the steps in
committing write batches, such as writing the batch to the WAL and
applying its contents to the memtable. While simple conceptually, the
commit pipeline is crucial for high performance. In the absence of
concurrency, commit performance is limited by how fast a batch can be
written (and synced) to the WAL and then added to the memtable, both
of which are outside of the purview of the commit pipeline.

To understand the challenge here, it is useful to have a conception of
the WAL (write-ahead log). The WAL contains a record of all of the
batches that have been committed to the database. As a record is
written to the WAL it is added to the memtable. Each record is
assigned a sequence number which is used to distinguish newer updates
from older ones. Conceptually the WAL looks like:

+--------------------------------------+
| Batch(SeqNum=1,Count=9,Records=...)  |
+--------------------------------------+
| Batch(SeqNum=10,Count=5,Records=...) |
+--------------------------------------+
| Batch(SeqNum=15,Count=7,Records...)  |
+--------------------------------------+
| ...                                  |
+--------------------------------------+

Note that each WAL entry is precisely the batch representation
described earlier in the Indexed Batches
section. The monotonically increasing sequence numbers are a critical
component in allowing RocksDB and Pebble to provide fast snapshot
views of the database for reads.

If concurrent performance was not a concern, the commit pipeline could
simply be a mutex which serialized writes to the WAL and application
of the batch records to the memtable. Concurrent performance is a
concern, though.

The primary challenge in concurrent performance in the commit pipeline
is maintaining two invariants:

1. Batches need to be written to the WAL in sequence number order.
2. Batches need to be made visible for reads in sequence number
   order. This invariant arises from the use of a single sequence
   number which indicates which mutations are visible.

The second invariant deserves explanation. RocksDB and Pebble both
keep track of a visible sequence number. This is the sequence number
for which records in the database are visible during reads. The
visible sequence number exists because committing a batch is an atomic
operation, yet adding records to the memtable is done without an
exclusive lock (the skiplists used by both Pebble and RocksDB are
lock-free). When the records from a batch are being added to the
memtable, a concurrent read operation may see those records, but will
skip over them because they are newer than the visible sequence
number. Once all of the records in the batch have been added to the
memtable, the visible sequence number is atomically incremented.

So we have four steps in committing a write batch:

1. Write the batch to the WAL
2. Apply the mutations in the batch to the memtable
3. Bump the visible sequence number
4. (Optionally) sync the WAL

Writing the batch to the WAL is actually very fast as it is just a
memory copy. Applying the mutations in the batch to the memtable is by
far the most CPU intensive part of the commit pipeline. Syncing the
WAL is the most expensive from a wall clock perspective.

With that background out of the way, let's examine how RocksDB commits
batches. This description is of the traditional commit pipeline in
RocksDB (i.e. the one used by CockroachDB).

RocksDB achieves concurrency in the commit pipeline by grouping
concurrently committed batches into a batch group. Each group is
assigned a "leader" which is the first batch to be added to the
group. The batch group is written atomically to the WAL by the leader
thread, and then the individual batches making up the group are
concurrently applied to the memtable. Lastly, the visible sequence
number is bumped such that all of the batches in the group become
visible in a single atomic step. While a batch group is being applied,
other concurrent commits are added to a waiting list. When the group
commit finishes, the waiting commits form the next group.

There are two criticisms of the batch grouping approach. The first is
that forming a batch group involves copying batch contents. RocksDB
partially alleviates this for large batches by placing a limit on the
total size of a group. A large batch will end up in its own group and
not be copied, but the criticism still applies for small batches. Note
that there are actually two copies here. The batch contents are
concatenated together to form the group, and then the group contents
are written into an in memory buffer for the WAL before being written
to disk.

The second criticism is about the thread synchronization points. Let's
consider what happens to a commit which becomes the leader:

1. Lock commit mutex
2. Wait to become leader
3. Form (concatenate) batch group and write to the WAL
4. Notify followers to apply their batch to the memtable
5. Apply own batch to memtable
6. Wait for followers to finish
7. Bump visible sequence number
8. Unlock commit mutex
9. Notify followers that the commit is complete

The follower's set of operations looks like:

1. Lock commit mutex
2. Wait to become follower
3. Wait to be notified that it is time to apply batch
4. Unlock commit mutex
5. Apply batch to memtable
6. Wait to be notified that commit is complete

The thread synchronization points (all of the waits and notifies) are
overhead. Reducing that overhead can improve performance.

The Pebble commit pipeline addresses both criticisms. The main
innovation is a commit queue that mirrors the commit order. The Pebble
commit pipeline looks like:

1. Lock commit mutex

• Add batch to commit queue
• Assign batch sequence number
• Write batch to the WAL

2. Unlock commit mutex
3. Apply batch to memtable (concurrently)
4. Publish batch sequence number

Pebble does not use the concept of a batch group. Each batch is
individually written to the WAL, but note that the WAL write is just a
memory copy into an internal buffer in the WAL.

Step 4 deserves further scrutiny as it is where the invariant on the
visible batch sequence number is maintained. Publishing the batch
sequence number cannot simply bump the visible sequence number because
batches with earlier sequence numbers may still be applying to the
memtable. If we were to ratchet the visible sequence number without
waiting for those applies to finish, a concurrent reader could see
partial batch contents. Note that RocksDB has experimented with
allowing these semantics with its unordered writes option.

We want to retain the atomic visibility of batch commits. The publish
batch sequence number step needs to ensure that we don't ratchet the
visible sequence number until all batches with earlier sequence
numbers have applied. Enter the commit queue: a lock-free
single-producer, multi-consumer queue. Batches are added to the commit
queue with the commit mutex held, ensuring the same order as the
sequence number assignment. After a batch finishes applying to the
memtable, it atomically marks the batch as applied. It then removes
the prefix of applied batches from the commit queue, bumping the
visible sequence number, and marking the batch as committed (via a
sync.WaitGroup). If the first batch in the commit queue has not be
applied we wait for our batch to be committed, relying on another
concurrent committer to perform the visible sequence ratcheting for
our batch. We know a concurrent commit is taking place because if
there was only one batch committing it would be at the head of the
commit queue.

There are two possibilities when publishing a sequence number. The
first is that there is an unapplied batch at the head of the
queue. Consider the following scenario where we're trying to publish
the sequence number for batch B.

+---------------+-------------+---------------+-----+
  | A (unapplied) | B (applied) | C (unapplied) | ... |
  +---------------+-------------+---------------+-----+

The publish routine will see that A is unapplied and then simply
wait for B's done sync.WaitGroup to be signalled. This is safe
because A must still be committing. And if A has concurrently been
marked as applied, the goroutine publishing A will then publish
B. What happens when A publishes its sequence number? The commit
queue state becomes:

+-------------+-------------+---------------+-----+
  | A (applied) | B (applied) | C (unapplied) | ... |
  +-------------+-------------+---------------+-----+

The publish routine pops A from the queue, ratchets the sequence
number, then pops B and ratchets the sequence number again, and then
finds C and stops. A detail that it is important to notice is that
the committer for batch B didn't have to do any more work. An
alternative approach would be to have B wakeup and ratchet its own
sequence number, but that would serialize the remainder of the commit
queue behind that goroutine waking up.

The commit queue reduces the number of thread synchronization
operations required to commit a batch. There is no leader to notify,
or followers to wait for. A commit either publishes its own sequence
number, or performs one synchronization operation to wait for a
concurrent committer to publish its sequence number.

Range Deletions Copy Chapter

Deletion of an individual key in RocksDB and Pebble is accomplished by
writing a deletion tombstone. A deletion tombstone shadows an existing
value for a key, causing reads to treat the key as not present. The
deletion tombstone mechanism works well for deleting small sets of
keys, but what happens if you want to all of the keys within a range
of keys that might number in the thousands or millions? A range
deletion is an operation which deletes an entire range of keys with a
single record. In contrast to a point deletion tombstone which
specifies a single key, a range deletion tombstone (a.k.a. range
tombstone) specifies a start key (inclusive) and an end key
(exclusive). This single record is much faster to write than thousands
or millions of point deletion tombstones, and can be done blindly --
without iterating over the keys that need to be deleted. The downside
to range tombstones is that they require additional processing during
reads. How the processing of range tombstones is done significantly
affects both the complexity of the implementation, and the efficiency
of read operations in the presence of range tombstones.

A range tombstone is composed of a start key, end key, and sequence
number. Any key that falls within the range is considered deleted if
the key's sequence number is less than the range tombstone's sequence
number. RocksDB stores range tombstones segregated from point
operations in a special range deletion block within each sstable.
Conceptually, the range tombstones stored within an sstable are
truncated to the boundaries of the sstable, though there are
complexities that cause this to not actually be physically true.

In RocksDB, the main structure implementing range tombstone processing
is the RangeDelAggregator. Each read operation and iterator has its
own RangeDelAggregator configured for the sequence number the read
is taking place at. The initial implementation of RangeDelAggregator
built up a "skyline" for the range tombstones visible at the read
sequence number.

10   +---+
 9   |   |
 8   |   |
 7   |   +----+
 6   |        |
 5 +-+        |  +----+
 4 |          |  |    |
 3 |          |  |    +---+
 2 |          |  |        |
 1 |          |  |        |
 0 |          |  |        |
  abcdefghijklmnopqrstuvwxyz

The above diagram shows the skyline created for the range tombstones
[b,j)#5, [d,h)#10, [f,m)#7, [p,u)#5, and [t,y)#3. The
skyline is queried for each key read to see if the key should be
considered deleted or not. The skyline structure is stored in a binary
tree, making the queries an O(logn) operation in the number of
tombstones, though there is an optimization to make this O(1) for
next/prev iteration. Note that the skyline representation loses
information about the range tombstones. This requires the structure to
be rebuilt on every read which has a significant performance impact.

The initial skyline range tombstone implementation has since been
replaced with a more efficient lookup structure. See the
DeleteRange
blog post for a good description of both the original implementation
and the new (v2) implementation. The key change in the new
implementation is to "fragment" the range tombstones that are stored
in an sstable. The fragmented range tombstones provide the same
benefit as the skyline representation: the ability to binary search
the fragments in order to find the tombstone covering a key. But
unlike the skyline approach, the fragmented tombstones can be cached
on a per-sstable basis. In the v2 approach, RangeDelAggregator keeps
track of the fragmented range tombstones for each sstable encountered
during a read or iterator, and logically merges them together.

Fragmenting range tombstones involves splitting range tombstones at
overlap points. Let's consider the tombstones in the skyline example
above:

10:   d---h
 7:     f------m
 5: b-------j     p----u
 3:                   t----y

Fragmenting the range tombstones at the overlap points creates a
larger number of range tombstones:

10:   d-f-h
 7:     f-h-j--m
 5: b-d-f-h-j     p---tu
 3:                   tu---y

While the number of tombstones is larger there is a significant
advantage: we can order the tombstones by their start key and then
binary search to find the set of tombstones overlapping a particular
point. This is possible because due to the fragmenting, all the
tombstones that overlap a range of keys will have the same start and
end key. The v2 RangeDelAggregator and associated classes perform
fragmentation of range tombstones stored in each sstable and those
fragmented tombstones are then cached.

In summary, in RocksDB RangeDelAggregator acts as an oracle for
answering whether a key is deleted at a particular sequence
number. Due to caching of fragmented tombstones, the v2 implementation
of RangeDelAggregator implementation is significantly faster to
populate than v1, yet the overall approach to processing range
tombstones remains similar.

Pebble takes a different approach: it integrates range tombstones
processing directly into the mergingIter structure. mergingIter is
the internal structure which provides a merged view of the levels in
an LSM. RocksDB has a similar class named
MergingIterator. Internally, mergingIter maintains a heap over the
levels in the LSM (note that each memtable and L0 table is a separate
"level" in mergingIter). In RocksDB, MergingIterator knows nothing
about range tombstones, and it is thus up to higher-level code to
process range tombstones using RangeDelAggregator.

While the separation of MergingIterator and range tombstones seems
reasonable at first glance, there is an optimization that RocksDB does
not perform which is awkward with the RangeDelAggregator approach:
skipping swaths of deleted keys. A range tombstone often shadows more
than one key. Rather than iterating over the deleted keys, it is much
quicker to seek to the end point of the range tombstone. The challenge
in implementing this optimization is that a key might be newer than
the range tombstone and thus shouldn't be skipped. An insight to be
utilized is that the level structure itself provides sufficient
information. A range tombstone at Ln is guaranteed to be newer than
any key it overlaps in Ln+1.

Pebble utilizes the insight above to integrate range deletion
processing with mergingIter. A mergingIter maintains a point
iterator and a range deletion iterator per level in the LSM. In this
context, every L0 table is a separate level, as is every
memtable. Within a level, when a range deletion contains a point
operation the sequence numbers must be checked to determine if the
point operation is newer or older than the range deletion
tombstone. The mergingIter maintains the invariant that the range
deletion iterators for all levels newer that the current iteration key
are positioned at the next (or previous during reverse iteration)
range deletion tombstone. We know those levels don't contain a range
deletion tombstone that covers the current key because if they did the
current key would be deleted. The range deletion iterator for the
current key's level is positioned at a range tombstone covering or
past the current key. The position of all of other range deletion
iterators is unspecified. Whenever a key from those levels becomes the
current key, their range deletion iterators need to be
positioned. This lazy positioning avoids seeking the range deletion
iterators for keys that are never considered.

For a full example, consider the following setup:

p0:               o
  r0:             m---q

  p1:              n p
  r1:       g---k

  p2:  b d    i
  r2: a---e           q----v

  p3:     e
  r3:

The diagram above shows is showing 4 levels, with pX indicating the
point operations in a level and rX indicating the range tombstones.

If we start iterating from the beginning, the first key we encounter
is b in p2. When the mergingIter is pointing at a valid entry, the
range deletion iterators for all of the levels less that the current
key's level are positioned at the next range tombstone past the
current key. So r0 will point at [m,q) and r1 at [g,k). When
the key b is encountered, we check to see if the current tombstone
for r0 or r1 contains it, and whether the tombstone for r2,
[a,e), contains and is newer than b.

Advancing the iterator finds the next key at d. This is in the same
level as the previous key b so we don't have to reposition any of
the range deletion iterators, but merely check whether d is now
contained by any of the range tombstones at higher levels or has
stepped past the range tombstone in its own level. In this case, there
is nothing to be done.

Advancing the iterator again finds e. Since e comes from p3, we
have to position the r3 range deletion iterator, which is empty. e
is past the r2 tombstone of [a,e) so we need to advance the r2
range deletion iterator to [q,v).

The next key is i. Because this key is in p2, a level above e,
we don't have to reposition any range deletion iterators and instead
see that i is covered by the range tombstone [g,k). The iterator
is immediately advanced to n which is covered by the range tombstone
[m,q) causing the iterator to advance to o which is visible.

Flush and Compaction Pacing Copy Chapter

Flushes and compactions in LSM trees are problematic because they
contend with foreground traffic, resulting in write and read latency
spikes. Without throttling the rate of flushes and compactions, they
occur "as fast as possible" (which is not entirely true, since we
have a bytes_per_sync option). This instantaneous usage of CPU and
disk IO results in potentially huge latency spikes for writes and
reads which occur in parallel to the flushes and compactions.

RocksDB attempts to solve this issue by offering an option to limit
the speed of flushes and compactions. A maximum bytes/sec can be
specified through the options, and background IO usage will be limited
to the specified amount. Flushes are given priority over compactions,
but they still use the same rate limiter. Though simple to implement
and understand, this option is fragile for various reasons.

1. If the rate limit is configured too low, the DB will stall and
   write throughput will be affected.
2. If the rate limit is configured too high, the write and read
   latency spikes will persist.
3. A different configuration is needed per system depending on the
   speed of the storage device.
4. Write rates typically do not stay the same throughout the lifetime
   of the DB (higher throughput during certain times of the day, etc) but
   the rate limit cannot be configured during runtime.

RocksDB also offers an
"auto-tuned" rate limiter
which uses a simple multiplicative-increase, multiplicative-decrease
algorithm to dynamically adjust the background IO rate limit depending
on how much of the rate limiter has been exhausted in an interval.
This solves the problem of having a static rate limit, but Pebble
attempts to improve on this with a different pacing mechanism.

Pebble's pacing mechanism uses separate rate limiters for flushes and
compactions. Both the flush and compaction pacing mechanisms work by
attempting to flush and compact only as fast as needed and no faster.
This is achieved differently for flushes versus compactions.

For flush pacing, Pebble keeps the rate at which the memtable is
flushed at the same rate as user writes. This ensures that disk IO
used by flushes remains steady. When a mutable memtable becomes full
and is marked immutable, it is typically flushed as fast as possible.
Instead of flushing as fast as possible, what we do is look at the
total number of bytes in all the memtables (mutable + queue of
immutables) and subtract the number of bytes that have been flushed in
the current flush. This number gives us the total number of bytes
which remain to be flushed. If we keep this number steady at a constant
level, we have the invariant that the flush rate is equal to the write
rate.

When the number of bytes remaining to be flushed falls below our
target level, we slow down the speed of flushing. We keep a minimum
rate at which the memtable is flushed so that flushes proceed even if
writes have stopped. When the number of bytes remaining to be flushed
goes above our target level, we allow the flush to proceed as fast as
possible, without applying any rate limiting. However, note that the
second case would indicate that writes are occurring faster than the
memtable can flush, which would be an unsustainable rate. The LSM
would soon hit the memtable count stall condition and writes would be
completely stopped.

For compaction pacing, Pebble uses an estimation of compaction debt,
which is the number of bytes which need to be compacted before no
further compactions are needed. This estimation is calculated by
looking at the number of bytes that have been flushed by the current
flush routine, adding those bytes to the size of the level 0 sstables,
then seeing how many bytes exceed the target number of bytes for the
level 0 sstables. We multiply the number of bytes exceeded by the
level ratio and add that number to the compaction debt estimate.
We repeat this process until the final level, which gives us a final
compaction debt estimate for the entire LSM tree.

Like with flush pacing, we want to keep the compaction debt at a
constant level. This ensures that compactions occur only as fast as
needed and no faster. If the compaction debt estimate falls below our
target level, we slow down compactions. We maintain a minimum
compaction rate so that compactions proceed even if flushes have
stopped. If the compaction debt goes above our target level, we let
compactions proceed as fast as possible without any rate limiting.
Just like with flush pacing, this would indicate that writes are
occurring faster than the background compactions can keep up with,
which is an unsustainable rate. The LSM's read amplification would
increase and the L0 file count stall condition would be hit.

With the combined flush and compaction pacing mechanisms, flushes and
compactions only occur as fast as needed and no faster, which reduces
latency spikes for user read and write operations.

Write throttling Copy Chapter

RocksDB adds artificial delays to user writes when certain thresholds
are met, such as l0_slowdown_writes_threshold. These artificial
delays occur when the system is close to stalling to lessen the write
pressure so that flushing and compactions can catch up. On the surface
this seems good, since write stalls would seemingly be eliminated and
replaced with gradual slowdowns. Closed loop write latency benchmarks
would show the elimination of abrupt write stalls, which seems
desirable.

However, this doesn't do anything to improve latencies in an open loop
model, which is the model more likely to resemble real world use
cases. Artificial delays increase write latencies without a clear
benefit. Writes stalls in an open loop system would indicate that
writes are generated faster than the system could possibly handle,
which adding artificial delays won't solve.

For this reason, Pebble doesn't add artificial delays to user writes
and writes are served as quickly as possible.

Other Differences Copy Section

• internalIterator API which minimizes indirect (virtual) function
  calls
• Previous pointers in the memtable and indexed batch skiplists
• Elision of per-key lower/upper bound checks in long range scans
• Improved Iterator API
  • SeekPrefixGE for prefix iteration
  • SetBounds for adjusting the bounds on an existing Iterator
• Simpler Get implementation

RFCS 20211018 Range Keys (`docs/RFCS/20211018_range_keys.md`) Copy Section

• Feature Name: Range Keys
• Status: draft
• Start Date: 2021-10-18
• Authors: Sumeer Bhola, Jackson Owens
• RFC PR: #1341
• Pebble Issues:
  https://github.com/cockroachdb/pebble/issues/1339
• Cockroach Issues:
  https://github.com/cockroachdb/cockroach/issues/70429
  https://github.com/cockroachdb/cockroach/issues/70412

** Design Draft**

Summary

An ongoing effort within CockroachDB to preserve MVCC history across all SQL
operations (see cockroachdb/cockroach#69380) requires a more efficient method of
deleting ranges of MVCC history.

This document describes an extension to Pebble introducing first-class support
for range keys. Range keys map a range of keyspace to a value. Optionally, the
key range may include an suffix encoding a version (eg, MVCC timestamp). Pebble
iterators may be configured to surface range keys during iteration, or to mask
point keys at lower MVCC timestamps covered by range keys.

CockroachDB will make use of these range keys to enable history-preserving
removal of contiguous ranges of MVCC keys with constant writes, and efficient
iteration past deleted versions.

Background

A previous CockroachDB RFC cockroach/cockroachdb#69380 describes the motivation
for the larger project of migrating MVCC-noncompliant operations into MVCC
compliance. Implemented with the existing MVCC primitives, some operations like
removal of an index or table would require performing writes linearly
proportional to the size of the table. Dropping a large table using existing
MVCC point-delete primitives would be prohibitively expensive. The desire for a
sublinear delete of an MVCC range motivates this work.

The detailed design for MVCC compliant bulk operations (high-level
description;
detailed design draft for DeleteRange in internal
doc),
ran into complexity by placing range operations above the Pebble layer, such
that Pebble sees these as points. The complexity causes are various: (a) which
key (start or end) to anchor this range on, when represented as a point (there
are performance consequences), (b) rewriting on CockroachDB range splits (and
concerns about rewrite volume), (c) fragmentation on writes and complexity
thereof (and performance concerns for reads when not fragmenting), (d) inability
to efficiently skip older MVCC versions that are masked by a [k1,k2)@ts (where
ts is the MVCC timestamp).

Pebble currently has only one kind of key that is associated with a range:
RANGEDEL [k1, k2)#seq, where [k1, k2) is supplied by the caller, and is used
to efficiently remove a set of point keys.

First-class support for range keys in Pebble eliminates all these issues.
Additionally, it allows for future extensions like efficient transactional range
operations. This issue describes how this feature would work from the
perspective of a user of Pebble (like CockroachDB), and sketches some
implementation details.

Design

Interface Copy Chapter

New `Comparer` requirements Copy Section

The Pebble Comparer type allows users to optionally specify a Split function
that splits a user key into a prefix and a suffix. This Split allows users
implementing MVCC (Multi-Version Concurrency Control) to inform Pebble which
part of the key encodes the user key and which part of the key encodes the
version (eg, a timestamp). Pebble does not dictate the encoding of an MVCC
version, only that the version form a suffix on keys.

The range keys design described in this RFC introduces stricter requirements for
user-provided Split implementations and the ordering of keys:

1. The user key consisting of just a key prefix k must sort before all
   other user keys containing that prefix. Specifically
   Compare(k[:Split(k)], k) < 0 where Split(k) < len(k).
2. A key consisting of a bare suffix must be a valid key and comparable. The
   ordering of the empty key prefix with any suffixes must be consistent with
   the ordering of those same suffixes applied to any other key prefix.
   Specifically Compare(k[Split(k):], k2[Split(k2):]) == Compare(k, k2) where
   Compare(k[:Split(k)], k2[:Split(k2)]) == 0.

The details of why these new requirements are necessary are explained in the
implementation section.

Writes Copy Section

This design introduces three new write operations:

• RangeKeySet([k1, k2), [optional suffix], <value>): This represents the
  mapping [k1, k2)@suffix => value. Keys k1 and k2 must not contain a
  suffix (i.e., Split(k1)==len(k1) and Split(k2)==len(k2)).

• RangeKeyUnset([k1, k2), [optional suffix]): This removes a mapping
  previously applied by RangeKeySet. The unset may use a smaller key range
  than the original RangeKeySet, in which case only part of the range is
  deleted. The unset only applies to range keys with a matching optional suffix.
  If the optional suffix is absent in both the RangeKeySet and RangeKeyUnset,
  they are considered matching.

• RangeKeyDelete([k1, k2)): This removes all range keys within the provided
  key span. It behaves like an Unset unencumbered by suffix restrictions.

For example, consider RangeKeySet([a,d), foo) (i.e., no suffix). If
there is a later call RangeKeyUnset([b,c)), the resulting state seen by
a reader is [a,b) => foo, [c,d) => foo. Note that the value is not
modified when the key is fragmented.

Partially overlapping RangeKeySets with the same suffix overwrite one
another. For example, consider RangeKeySet([a,d), foo), followed by
RangeKeySet([c,e), bar). The resulting state is [a,c) => foo, [c,e) => bar.

Point keys (eg, traditional keys defined at a singular byte string key) and
range keys do not overwrite one another. They have a parallel existence. Point
deletes only apply to points. Range unsets only apply to range keys. However,
users may configure iterators to mask point keys covered by newer range keys.
This masking behavior is explicitly requested by the user in the context of the
iteration. Masking is described in more detail below.

There exist separate range delete operations for point keys and range keys. A
RangeKeyDelete may remove part of a range key, just like the new
RangeKeyUnset operation introduced earlier. RangeKeyDeletes differ from
RangeKeyUnsets, because the latter requires that the suffix matches and
applies only to range keys. RangeKeyDeletes completely clear all existing
range keys within their span at all suffix values.

The optional suffix in RangeKeySet and RangeKeyUnset operations is related
to the pebble Comparer.Split operation which is explicitly documented as being
for MVCC
keys,
without mandating exactly how the versions are represented. RangeKeySet and
RangeKeyUnset keys with different suffixes do not interact logically, although
Pebble will observably fragment ranges at intersection points.

Iteration Copy Section

A user iterating over a key interval [k1,k2) can request:

• [I1] An iterator over only point keys.

• [I2] A combined iterator over point and range keys. This is what
  we mainly discuss below in the implementation discussion.

• [I3] An iterator over only range keys. In the CockroachDB use
  case, range keys will need to be subject to MVCC GC just like
  point keys — this iterator may be useful for that purpose.

The pebble.Iterator type will be extended to provide accessors for
range keys for use in the combined and exclusively range iteration
modes.

/* Detailed source-code truncated for AI context efficiency. */

When a combined iterator exposes range keys, it exposes all the range
keys covering Key. During iteration with a combined iterator, an
iteration position may surface just a point key, just a range key or
both at the currently-positioned Key.

Described another way, a Pebble combined iterator guarantees that it
will stop at all positions within the keyspace where:

1. There exists a point key at that position.
2. There exists a range key that logically begins at that position.

In addition to the above positions, a Pebble iterator may also stop at keys
in-between the above positions due to fragmentation. Range keys are defined over
continuous spans of keyspace. Range keys with different suffix values may
overlap each other arbitrarily. To surface these arbitrarily overlapping spans
in an understandable and efficient way, the Pebble iterator surfaces range keys
fragmented at intersection points. Consider the following sequence of writes:

RangeKeySet([a,z), @1, 'apple')
    RangeKeySet([c,e), @3, 'banana')
    RangeKeySet([e,m), @5, 'orange')
    RangeKeySet([b,k), @7, 'kiwi')

This yields a database containing overlapping range keys:

@7 → kiwi     |-----------------)
  @5 → orange         |---------------)
  @3 → banana     |---)
  @1 → apple  |-------------------------------------------------)
              a b c d e f g h i j k l m n o p q r s t u v w x y z

During iteration, these range keys are surfaced using the bounds of their
intersection points. For example, a scan across the keyspace containing only
these range keys would observe the following iterator positions:

Key() = a   RangeKeyBounds() = [a,b)   RangeKeys() = {(@1,apple)}
  Key() = b   RangeKeyBounds() = [b,c)   RangeKeys() = {(@7,kiwi), (@1,apple)}
  Key() = c   RangeKeyBounds() = [c,e)   RangeKeys() = {(@7,kiwi), (@3,banana), (@1,apple)}
  Key() = e   RangeKeyBounds() = [e,k)   RangeKeys() = {(@7,kiwi), (@5,orange), (@1,apple)}
  Key() = k   RangeKeyBounds() = [k,m)   RangeKeys() = {(@5,orange), (@1,apple)}
  Key() = m   RangeKeyBounds() = [m,z)   RangeKeys() = {(@1,apple)}

This fragmentation produces a more understandable interface, and avoids forcing
iterators to read all range keys within the bounds of the broadest range key.
Consider this example:

iterator pos          [ ] - sstable bounds
                         |
L1:         [a----v1@t2--|-h]     [l-----unset@t1----u]
L2:                 [e---|------v1@t1----------r]
             a b c d e f g h i j k l m n o p q r s t u v w x y z

If the iterator is positioned at a point key g, there are two overlapping
physical range keys: [a,h)@t2→v1 and [e,r)@t1→v1.

However, the RangeKeyUnset([l,u), @t1) removes part of the [e,r)@t1→v1 range
key, truncating it to the bounds [e,l). The iterator must return the truncated
bounds that correctly respect the RangeKeyUnset. However, when the range keys
are stored within a log-structured merge tree like Pebble, the RangeKeyUnset
may not be contained within the level's sstable that overlaps the current point
key. Searching for the unset could require reading an unbounded number of
sstables, losing the log-structured merge tree's property that bounds read
amplification to the number of levels in the tree.

Fragmenting range keys to intersection points avoids this problem. The iterator
positioned at g only surfaces range key state with the bounds [e,h), the
widest bounds in which it can guarantee t2→v1 and t1→v1 without loading
additional sstables.

Iteration order

Recall that the user-provided Comparer.Split(k) function divides all user keys
into a prefix and a suffix, such that the prefix is k[:Split(k)], and the
suffix is k[Split(k):]. If a key does not contain a suffix, the key equals the
prefix.

An iterator that is configured to surface range keys alongside point keys will
surface all range keys covering the current Key() position. Revisiting an
earlier example with the addition of three new point key-value pairs:
a→artichoke, b@2→beet and t@3→turnip. Consider '@' to form the suffix
where present, with <number> denoting a MVCC timestamp. Higher, more-recent
timestamps sort before lower, older timestamps.

.                                                   a   → artichoke
  @7 → kiwi     |-----------------)
  @5 → orange         |---------------)
                . b@2                                             b@2 → beet
  @3 → banana     |---)                             . t@3         t@3 → turnip
  @1 → apple  |-------------------------------------------------)
              a b c d e f g h i j k l m n o p q r s t u v w x y z

An iterator configured to surface both point and range keys will visit the
following iterator positions during forward iteration:

Key()   HasPointAndRange()   Value()      RangeKeyBounds()    RangeKeys()
  a       (true,  true)        artichoke    [a,b)               {(@1,apple)}
  b       (false, true)        -            [b,c)               {(@7,kiwi), (@1,apple)}
  b@2     (true,  true)        beet         [b,c)               {(@7,kiwi), (@1,apple)}
  c       (false, true)        -            [c,e)               {(@7,kiwi), (@3,banana), (@1,apple)}
  e       (false, true)        -            [e,k)               {(@7,kiwi), (@5,orange), (@1,apple)}
  k       (false, true)        -            [k,m)               {(@5,orange), (@1,apple)}
  m       (false, true)        -            [m,z)               {(@1,apple)}
  t@3     (true,  true)        turnip       [m,z)               {(@1,apple)}

Note that:

• While positioned over a point key (eg, Key() = 'a', 'b@2' or t@3'), the
  iterator exposes both the point key's value through Value() and the
  overlapping range keys values through RangeKeys().

• There can be multiple range keys covering a Key(), each with a different
  suffix.

• There cannot be multiple range keys covering a Key() with the same suffix,
  since the most-recently committed one (eg, the one with the highest sequence
  number) will win, just like for point keys.

• If the iterator has configured lower and/or upper bounds, they will truncate
  the range key to those bounds. For example, if the above iterator had an upper
  bound 'y', the [m,z) range key would be surfaced with the bounds [m,y)
  instead.

Masking

Range key masking provides additional, optional functionality designed
specifically for the use case of implementing a MVCC-compatible delete range.

When constructing an iterator that iterators over both point and range keys, a
user may request that range keys mask point keys. Masking is configured with a
suffix parameter that determines which range keys may mask point keys. Only
range keys with suffixes that sort after the mask's suffix mask point keys. A
range key that meets this condition only masks points with suffixes that sort
after the range key's suffix.

/* Detailed source-code truncated for AI context efficiency. */

Example: A user may construct an iterator with RangeKeyMasking.Suffix set to
@50. The range key [a, c)@60 would mask nothing, because @60 is a more
recent timestamp than @50. However a range key [a,c)@30 would mask a@20
and apple@10 but not apple@40. A range key can only mask keys with MVCC
timestamps older than the range key's own timestamp. Only range keys with
suffixes (eg, MVCC timestamps) may mask anything at all.

The pebble Iterator surfaces all range keys when masking is enabled. Only point
keys are ever skipped, and only when they are contained within the bounds of a
range key with a more-recent suffix, and the range key's suffix is older than
the timestamp encoded in RangeKeyMasking.Sufffix.

Implementation Copy Chapter

Write operations Copy Section

This design introduces three new Pebble write operations: RangeKeySet,
RangeKeyUnset and RangeKeyDelete. Internally, these operations are
represented as internal keys with new corresponding key kinds encoded as a part
of the key trailer. These keys are stored within special range key blocks
separate from point keys, but within the same sstable. The range key blocks hold
RangeKeySet, RangeKeyUnset and RangeKeyDelete keys, but do not hold keys
of any other kind. Within the memtables, these range keys are stored in a
separate skip list.

• RangeKeySet([k1,k2), @suffix, value) is encoded as a k1.RANGEKEYSET key
  with a value encoding the tuple (k2,@suffix,value).
• RangeKeyUnset([k1,k2), @suffix) is encoded as a k1.RANGEUNSET key
  with a value encoding the tuple (k2,@suffix).
• RangeKeyDelete([k1,k2) is encoded as a k1.RANGEKEYDELETE key with a value
  encoding k2.

Range keys are physically fragmented as an artifact of the log-structured merge
tree structure and internal sstable boundaries. This fragmentation is essential
for preserving the performance characteristics of a log-structured merge tree.
Although the public interface operations for RangeKeySet and RangeKeyUnset
require both boundary keys [k1,k2) to always be bare prefixes (eg, to not have
a suffix), internally these keys may be fragmented to bounds containing
suffixes.

Example: If a user attempts to write RangeKeySet([a@v1, c@v2), @v3, value),
Pebble will return an error to the user. If a user writes RangeKeySet([a, c), @v3, value), Pebble will allow the write and may later internally fragment the
RangeKeySet into three internal keys:

• RangeKeySet([a, a@v1), @v3, value)
• RangeKeySet([a@v1, c@v2), @v3, value)
• RangeKeySet([c@v2, c), @v3, value)

This fragmentation preserve log-structured merge tree performance
characteristics because it allows a range key to be split across many sstables,
while preserving locality between range keys and point keys. Consider a
RangeKeySet([a,z), @1, foo) on a database that contains millions of point keys
in the range [a,z). If the [a,z) range key was not permitted to be fragmented
internally, it would either need to be stored completely separately from the
point keys in a separate sstable or in a single intractably large sstable
containing all the overlapping point keys. Fragmentation allows locality,
ensuring point keys and range keys in the same region of the keyspace can be
stored in the same sstable.

RangeKeySet, RangeKeyUnset and RangeKeyDelete keys are assigned sequence
numbers, like other internal keys. Log-structured merge tree level invariants
are valid across range key, point keys and between the two. That is:

1. The point key k1#s2 cannot be at a lower level than k2#s1 where
   k1==k2 and s1 < s2. This is the invariant implemented by all LSMs.
2. RangeKeySet([k1,k2))#s2 cannot be at a lower level than
   RangeKeySet([k3,k4))#s1 where [k1,k2) overlaps [k3,k4) and s1 < s2.
3. RangeKeySet([k1,k2))#s2 cannot be at a lower level than a point key
   k3#s1 where k3 \in [k1,k2) and s1 < s2.

Like other tombstones, the RangeKeyUnset and RangeKeyDelete keys are elided
when they fall to the bottomost level of the LSM and there is no snapshot
preventing its elision. There is no additional garbage collection problem
introduced by these keys.

There is no Merge operation that affects range keys.

Physical representation

RangeKeySet, RangeKeyUnset and RangeKeyDelete keys are keyed by their
start key. This poses an obstacle. We must be able to support multiple range
keys at the same sequence number, because all keys within an ingested sstable
adopt the same sequence number. Duplicate internal keys (keys with equal user
keys, sequence numbers and kinds) are prohibited within Pebble. To resolve this
issue, fragments with the same bounds are merged within snapshot stripes into a
single physical key-value, representing multiple logical key-value pairs:

k1.RangeKeySet#s2 → (k2,[(@t2,v2),(@t1,v1)])

Within a physical key-value pair, suffix-value pairs are stored sorted by
suffix, descending. This has a minor advantage of reducing iteration-time
user-key comparisons when there exist multiple range keys in a table.

Unlike other Pebble keys, the RangeKeySet and RangeKeyUnset keys have values
that encode fields of data known to Pebble. The value that the user sets in a
call to RangeKeySet is opaque to Pebble, but the physical representation of
the RangeKeySet's value is known. This encoding is a sequence of fields:

• End key, varstring, encodes the end user key of the fragment.
• A series of (suffix, value) tuples representing the logical range keys that
  were merged into this one physical RangeKeySet key:
  • Suffix, varstring
  • Value, varstring

Similarly, RangeKeyUnset keys are merged within snapshot stripes and have a
physical representation like:

k1.RangeKeyUnset#s2 → (k2,[(@t2),(@t1)])

A RangeKeyUnset key's value is encoded as:

• End key, varstring, encodes the end user key of the fragment.
• A series of suffix varstrings.

When RangeKeySet and RangeKeyUnset fragments with identical bounds meet
within the same snapshot stripe within a compaction, any of the
RangeKeyUnset's suffixes that exist within the RangeKeySet key are removed.

A RangeKeyDelete key has no additional data beyond its end key, which is
encoded directly in the value.

NB: RangeKeySet and RangeKeyUnset keys are not merged within batches or the
memtable. That's okay, because batches are append-only and indexed batches will
refragment and merge the range keys on-demand. In the memtable, every key is
guaranteed to have a unique sequence number.

Sequence numbers Copy Section

Like all Pebble keys, RangeKeySet, RangeKeyUnset and RangeKeyDelete are
assigned sequence numbers when committed. As described above, overlapping
RangeKeySets and RangeKeyUnsets are fragmented to have matching start and
end bounds. Then the resulting exactly-overlapping range key fragments are
merged into a single internal key-value pair, within the same snapshot stripe
and sstable. The original, unmerged internal keys each have their own sequence
numbers, indicating the moment they were committed within the history of all
write operations.

Recall that sequence numbers are used within Pebble to determine which keys
appear live to which iterators. When an iterator is constructed, it takes note
of the current visible sequence number, and for the lifetime of the iterator,
only surfaces keys less than that sequence number. Similarly, snapshots read the
current visible sequence number, remember it, but also leave a note asking
compactions to preserve history at that sequence number. The space between
snapshotted sequence numbers is referred to as a snapshot stripe, and
operations cannot drop or otherwise mutate keys unless they fall within the same
snapshot stripe. For example a k.MERGE#5 key may not be merged with a
k.MERGE#1 operation if there's an open snapshot at #3.

The new RangeKeySet, RangeKeyUnset and RangeKeyDelete keys behave
similarly. Overlapping range keys won't be merged if there's an open snapshot
separating them. Consider a range key a-z written at sequence number #1 and
a point key d.SET#2. A combined point-and-range iterator using a sequence
number #3 and positioned at d will surface both the range key a-z and the
point key d.

In the context of masking, the suffix-based masking of range keys can cause
potentially unexpected behavior. A range key [a,z)@10 may be committed as
sequence number #1. Afterwards, a point key d@5#2 may be committed. An
iterator that is configured with range-key masking with suffix @20 would mask
the point key d@5#2 because although d@5#2's sequence number is higher,
range-key masking uses suffixes to impose order, not sequence numbers.

Boundaries for sstables Copy Section

Range keys follow the same relationship to sstable boundaries as the existing
RANGEDEL tombstones. The bounds of an internal range key are user keys. Every
range key is limited by its containing sstable's bounds.

Consider these keys, annotated with sequence numbers:

Point keys: a#50, b#70, b#49, b#48, c#47, d#46, e#45, f#44
Range key: [a,e)#60

We have created three versions of b in this example. In previous versions,
Pebble could split output sstables during a compaction such that the different
b versions span more than one sstable. This creates problems for RANGEDELs
which span these two sstables which are discussed in the section on improperly
truncated RANGEDELS.
We manage to tolerate this for RANGEDELs since their semantics are defined by
the system, which is not true for these range keys where the actual semantics
are up to the user.

Pebble now disallows such sstable split points. In this example, by postponing
the sstable split point to the user key c, we can cleanly split the range key
into [a,c)#60 and [c,e)#60. The sstable end bound for the first sstable
(sstable bounds are inclusive) will be c#inf (where inf is the largest possible
seqnum, which is unused except for these cases), and sstable start bound for the
second sstable will be c#60.

The above example deals exclusively with point and range keys without suffixes.
Consider this example with suffixed keys, and compaction outputs split in the
middle of the b prefix:

first sstable: points: a@100, a@30, b@100, b@40 ranges: [a,c)@50
second sstable: points: b@30, c@40, d@40, e@30, ranges: [c,e)@50

When the compaction code decides to defer b@30 to the next sstable and finish
the first sstable, the range key [a,c)@50 is sitting in the fragmenter. The
compaction must split the range key at the bounds determined by the user key.
The compaction uses the first point key of the next sstable, in this case
b@30, to truncate the range key. The compaction flushes the fragment
[a,b@30)@50 to the first sstable and updates the existing fragment to begin at
b@30.

If a range key extends into the next file, the range key's truncated end is used
for the purposes of determining the sstable end boundary. The first sstable's
end boundary becomes b@30#inf, signifying the range key does not cover b@30.
The second sstable's start boundary is b@30.

Block property collectors Copy Section

Separate block property collectors may be configured to collect separate
properties about range keys. This is necessary for CockroachDB's MVCC block
property collectors to ensure the sstable-level properties are correct.

Iteration Copy Section

This design extends the *pebble.Iterator with the ability to iterate over
exclusively range keys, range keys and point keys together or exclusively point
keys (the previous behavior).

• Pebble already requires that the prefix k follows the same key validity
  rules as k@suffix.

• Previously, Pebble did not require that a user key consisting of just a prefix
  k sort before the same prefix with a non-empty suffix. CockroachDB has
  adopted this behavior since it results in the following clean behavior:
  RANGEDEL over [k1, k2) deletes all versioned keys which have prefixes in the
  interval [k1, k2). Pebble will now require this behavior for all users using
  MVCC keys. Specifically, it must hold that Compare(k[:Split(k)], k) < 0 if
  Split(k) < len(k).

TKTK: Discuss merging iterator

Determinism

Range keys will be split based on boundaries of sstables in an LSM. Users of an
LSM typically expect that two different LSMs with different sstable settings
that receive the same writes should output the same key-value pairs when
iterating. To provide this behavior, the iterator implementation may be
configured to defragment range keys during iteration time. The defragmentation
behavior would be:

• Two visible ranges [k1,k2)@suffix1=>val1, [k2,k3)@suffix2=>val2 are
  defragmented if suffix1==suffix2 and val1==val2, and become [k1,k3).

• Defragmentation during user iteration does not consider the sequence number.
  This is necessary since LSM state can be exported to another LSM via the use
  of sstable ingestion, which can collapse different seqnums to the same seqnum.
  We would like both LSMs to look identical to the user when iterating.

The above defragmentation is conceptually simple, but hard to implement
efficiently, since it requires stepping ahead from the current position to
defragment range keys. This stepping ahead could switch sstables while there are
still points to be consumed in a previous sstable. This determinism is useful
for testing and verification purposes:

• Randomized and metamorphic testing is used extensively to reliably test
  software including Pebble and CockroachDB. Defragmentation provides
  the determinism necessary for this form of testing.

• CockroachDB's replica divergence detector requires a consistent view of the
  database on each replica.

In order to provide determinism, Pebble constructs an internal range key
iterator stack that's separate from the point iterator stack, even when
performing combined iteration over both range and point keys. The separate range
key iterator allows the internal range key iterator to move independently of the
point key iterator. This allows the range key iterator to independently visit
adjacent sstables in order to defragment their range keys if necessary, without
repositioning the point iterator.

Two spans [k1,k2) and [k3, k4) of range keys are defragmented if their bounds
abut and their user observable-state is identical. That is, k2==k3 and each
spans' contains exactly the same set of range key (, ) pairs. In
order to support RangeKeyUnset and RangeKeyDelete, defragmentation must be
applied after resolving unset and deletes.

Merging iteration

Recall that range keys are stored in the same sstables as point keys. In a
log-structured merge tree, these sstables are distributed across levels. Within
a level, sstables are non-overlapping but between levels sstables may overlap
arbitrarily. During iteration, keys across levels must be merged together. For
point keys, this is typically done with a heap.

Range keys too must be merged across levels, and the earlier described
fragmentation at intersection boundaries must be applied. To implement this, a
range key merging iterator is defined.

A merging iterator is initialized with an arbitrary number of child iterators
over fragmented spans. Each child iterator exposes fragmented range keys, such
that overlapping range keys are surfaced in a single span with a single set of
bounds. Range keys from one child iterator may overlap key spans from another
child iterator arbitrarily. The high-level algorithm is:

1. Initialize a heap with bound keys from child iterators' range keys.
2. Find the next [or previous, if in reverse] two unique user keys' from bounds.
3. Consider the span formed between the two unique user keys a candidate span.
4. Determine if any of the child iterators' spans overlap the candidate span.
   4a. If any of the child iterator's current bounds are end keys (during
   forward iteration) or start keys (during reverse iteration), then all the
   spans with that bound overlap the candidate span.
   4b. If no spans overlap, forget the smallest (forward iteration) or largest
   (reverse iteration) unique user key and advance the iterators to the next
   unique user key. Start again from 3.

Consider the example:

i0:     b---d e-----h
       i1:   a---c         h-----k
       i2:   a------------------------------p

fragments:   a-b-c-d-e-----h-----k----------p

None of the individual child iterators contain a span with the exact bounds
[c,d), but the merging iterator must produce a span [c,d). To accomplish this,
the merging iterator visits every span between unique boundary user keys. In the
above example, this is:

[a,b), [b,c), [c,d), [d,e), [e, h), [h, k), [k, p)

The merging iterator first initializes the heap to prepare for iteration. The
description below discusses the mechanics of forward iteration after a call to
First, but the mechanics are similar for reverse iteration and other positioning
methods.

During a call to First, the heap is initialized by seeking every level to the
first bound of the first fragment. In the above example, this seeks the child
iterators to:

i0: (b, boundKindStart, [ [b,d) ])
i1: (a, boundKindStart, [ [a,c) ])
i2: (a, boundKindStart, [ [a,p) ])

After fixing up the heap, the root of the heap is the bound with the smallest
user key ('a' in the example). During forward iteration, the root of the heap's
user key is the start key of next merged span. The merging iterator records this
key as the start key. The heap may contain other levels with range keys that
also have the same user key as a bound of a range key, so the merging iterator
pulls from the heap until it finds the first bound greater than the recorded
start key.

In the above example, this results in the bounds [a,b) and child iterators in
the following positions:

i0: (b, boundKindStart, [ [b,d) ])
i1: (c, boundKindEnd,   [ [a,c) ])
i2: (p, boundKindEnd,   [ [a,p) ])

With the user key bounds of the next merged span established, the merging
iterator must determine which, if any, of the range keys overlap the span.
During forward iteration any child iterator that is now positioned at an end
boundary has an overlapping span. (Justification: The child iterator's end
boundary is ≥ the new end bound. The child iterator's range key's corresponding
start boundary must be ≤ the new start bound since there were no other user keys
between the new span's bounds. So the fragments associated with the iterator's
current end boundary have start and end bounds such that start ≤ < ≤ end).

The merging iterator iterates over the levels, collecting keys from any child
iterators positioned at end boundaries. In the above example, i1 and i2 are
positioned at end boundaries, so the merging iterator collects the keys of [a,c)
and [a,p). These spans contain the merging iterator's [a,b) span, but they may
also extend beyond the new span's start and end. The merging iterator returns
the keys with the new start and end bounds, preserving the underlying keys'
sequence numbers, key kinds and values.

It may be the case that the merging iterator finds no levels positioned at span
end boundaries in which case the span overlaps with nothing. In this case the
merging iterator loops, repeating the above process again until it finds a span
that does contain keys.

Efficient masking

Recollect that in the earlier example from the iteration interface, during
forward iteration an iterator would output the following keys:

Key()   HasPointAndRange()   Value()      RangeKeyBounds()    RangeKeys()
  a       (true,  true)        artichoke    [a,b)               {(@1,apple)}
  b       (false, true)        -            [b,c)               {(@7,kiwi), (@1,apple)}
  b@2     (true,  true)        beet         [b,c)               {(@7,kiwi), (@1,apple)}
  c       (false, true)        -            [c,e)               {(@7,kiwi), (@3,banana), (@1,apple)}
  e       (false, true)        -            [e,k)               {(@7,kiwi), (@5,orange), (@1,apple)}
  k       (false, true)        -            [k,m)               {(@5,orange), (@1,apple)}
  m       (false, true)        -            [m,z)               {(@1,apple)}
  t@3     (true,  true)        turnip       [m,z)               {(@1,apple)}

When implementing an MVCC "soft delete range" operation using range keys, the
range key [b,k)@7→kiwi may represent that all keys within the range [b,k) are
deleted at MVCC timestamp @7. During iteration, it would be desirable if the
caller could indicate that it does not want to observe any "soft deleted" point
keys, and the iterator can safely skip them. Note that in a MVCC system, whether
or not a key is soft deleted depends on the timestamp at which the database is
read.

This is implemented through "range key masking," where a range key may act as a
mask, hiding point keys with MVCC timestamps beneath the range key. This
iterator option requires that the client configure the iterator with a MVCC
timestamp suffix representing the timestamp at which history should be read.
All range keys with suffixes (MVCC timestamps) less than or equal to the
configured suffix serve as masks. All point keys with suffixes (MVCC timestamps)
less than a covering, masking range key's suffix are hidden.

Specifically, when configured with a RangeKeyMasking.Suffix s, and there
exists a range key with suffix r covering a point key with suffix p, and s
≤ r < p then the point key is elided.

In the above example, if RangeKeyMasking.Suffix is set to @7, every range
key serves as a mask and the point key b@2 is hidden during iteration because
it's contained within the masking [b,k)@7→kiwi range key. Note that t@3
would not be masked, because its timestamp @3 is more recent than the only
range key that covers it ([a,z)@1→apple).

If RangeKeyMasking.Suffix were set to @6 (a historical, point-in-time read),
the [b,k)@7→kiwi range key would no longer serve as a mask, and b@2 would be
visible.

To efficiently implement masking, we cannot rely on the LSM invariant since
b@100 can be at a lower level than [a,e)@50. Instead, we build on
block-property filters, supporting special use of a MVCC timestamp block
property in order to skip blocks wholly containing point keys that are masked by
a range key. The client may configure a block-property collector to record the
highest MVCC timestamps of point keys within blocks.

During read time, when positioned within a range key with a suffix ≤
RangeKeyMasking.Suffix, the iterator configures sstable readers to use a
block-property filter to skip any blocks for which the highest MVCC timestamp is
less than the provided suffix. Additionally, these iterators must consult index
block bounds to ensure the block-property filter is not applied beyond the
bounds of the masking range key.

CockroachDB use Copy Section

CockroachDB initially will only use range keys to represent MVCC range
tombstones. See the MVCC range tombstones tech note for more details:

https://github.com/cockroachdb/cockroach/blob/master/docs/tech-notes/mvcc-range-tombstones.md

Alternatives Copy Section

A1. Automatic elision of range keys that don't cover keys

We could decide that range keys:

• Don't contribute to MVCCStats themselves.
• May be elided by Pebble when they cover zero point keys.

This means that CockroachDB garbage collection does not need to explicitly
remove the range keys, only the point keys they deleted. This option is clean
when paired with RANGEDELs dropping both point and range keys. CockroachDB can
issue RANGEDELs whenever it wants to drop a contiguous swath of points, and
not worry about the fact that it might also need to update the MVCC stats for
overlapping range keys.

However, this option makes deterministic iteration over defragmented range keys
for replica divergence detection challenging, because internal fragmentation may
elide regions of a range key at any point. Producing a normalized form would
require storing state in the value (ie, the original start key) and
recalculating the smallest and largest extant covered point keys within the
range key and replica bounds. This would require maintaining O(range-keys)
state during the storage.ComputeStatsForRange pass over a replica's combined
point and range iterator.

This likely forces replica divergence detection to use other means (eg, altering
the checksum of covered points) to incorporate MVCC range tombstone state.

This option is also highly tailored to the MVCC Delete Range use case. Other
range key usages, like ranged intents, would not want this behavior, so we don't
consider it further.

A2. Separate LSM of range keys

There are two viable options for where to store range keys. They may be encoded
within the same sstables as points in separate blocks, or in separate sstables
forming a parallel range-key LSM. We examine the tradeoffs between storing range
keys in the same sstable in different blocks ("shared sstables") or separate
sstables forming a parallel LSM ("separate sstables"):

• Storing range keys in separate sstables is possible because the only
  interactions between range keys and point keys happens at a global level.
  Masking is defined over suffixes. It may be extended to be defined over
  sequence numbers too (see 'Sequence numbers' section below), but that is
  optional. Unlike range deletion tombstones, range keys have no effect on point
  keys during compactions.

• With separate sstables, reads may need to open additional sstable(s) and read
  additional blocks. The number of additional sstables is the number of nonempty
  levels in the range-key LSM, so it grows logarithmically with the number of
  range keys. For each sstable, a read must read the index block and a data
  block.

• With our expectation of few range keys, the range-key LSM is expected to be
  small, with one or two levels. Heuristics around sstable boundaries may
  prevent unnecessary range-key reads when there is no covering range key. Range
  key sstables and blocks are expected to have much higher table and block cache
  hit rates, since they are orders of magnitude less dense. Reads in any
  overlapping point sstables all access the same range key sstables.

• With shared sstables, SeekPrefixGE cannot use bloom filters to entirely
  eliminate sstables that contain range keys. Pebble does not always use bloom
  filters in L6, so once a range key is compacted into L6 its impact to
  SeekPrefixGE is lessened. With separate sstables, SeekPrefixGE can always
  use bloom filters for point-key sstables. If there are any overlapping
  range-key sstables, the read must read them.

• With shared sstables, range keys create dense sstable boundaries. A range key
  spanning an sstable boundary leaves no gap between the sstables' bounds. This
  can force ingested sstables into higher levels of the LSM, even if the
  sstables' point key spans don't overlap. This problem was previously observed
  with wide RANGEDEL tombstones and was mitigated by prioritizing compaction
  of sstables that contain RANGEDEL keys. We could do the same with range
  keys, but the write amplification is expected to be much worse. The RANGEDEL
  tombstones drop keys and eventually are dropped themselves as long as there is
  not an open snapshot. Range keys do not drop data and are expected to persist
  in L6 for long durations, always requiring ingested sstables to be inserted
  into L5 or above.

• With separate sstables, compaction logic is separate, which helps avoid
  complexity of tricky sstable boundary conditions. Because there are expected
  to be an order of magnitude fewer range keys, we could impose the constraint
  that a prefix cannot be split across multiple range key sstables. The
  simplified compaction logic comes at the cost of higher levels, iterators, etc
  all needing to deal with the concept of two parallel LSMs.

• With shared sstables, the LSM invariant is maintained between range keys and
  point keys. For example, if the point key b@20 is committed, and
  subsequently a range key RangeKey([a,c), @25, ...) is committed, the range
  key will never fall below the covered point b@20 within the LSM.

We decide to share sstables, because preserving the LSM invariant between range
keys and point keys is expected to be useful in the long-term.

A3. Sequence number masking

In the CockroachDB MVCC range tombstone use case, a point key should never be
written below an existing range key with a higher timestamp. The MVCC range
tombstone use case would allow us to dictate that an overlapping range key with
a higher sequence number always masks range keys with lower sequence numbers.
Adding this additional masking scope would avoid the comparatively costly suffix
comparison when a point key is masked by a range key. We need to consider how
sequence number masking might be affected by the merging of range keys within
snapshot stripes.

Consider the committing of range key [a,z)@{t1}#10, followed by point keys
d@t2#11 and m@t2#11, followed by range key [j,z)@{t3}#12. This sequencing
respects the expected timestamp, sequence number relationship in CockroachDB's
use case. If all keys are flushed within the same sstable, fragmentation and
merging overlapping fragments yields range keys [a,j)@{t1}#10,
[j,z)@{t3,t1}#12. The key d@t2#11 must not be masked because it's not
covered by the new range key, and indeed that's the case because the covering
range key's fragment is unchanged [a,j)@{t1}#10.

For now we defer this optimization, with the expectation that we may not be able
to preserve this relationship between sequence numbers and suffixes in all range
key use cases.

RFCS 20220112 Pebble Sstable Format Versions (`docs/RFCS/20220112_pebble_sstable_format_versions.md`) Copy Section

• Feature Name: Pebble SSTable Format Versions
• Status: completed
• Start Date: 2022-01-12
• Authors: Nick Travers
• RFC PR: https://github.com/cockroachdb/pebble/pull/1450
• Pebble Issues:
  https://github.com/cockroachdb/pebble/issues/1409
  https://github.com/cockroachdb/pebble/issues/1339
• Cockroach Issues:

Summary

To safely support changes to the SSTable structure, a new versioning scheme
under a Pebble magic number is proposed.

This RFC also outlines the relationship between the SSTable format version and
the existing Pebble format major version, in addition to how the two are to
be used in Cockroach for safely enabling new table format versions.

Motivation

Pebble currently uses a "format major version" scheme for the store (or DB)
that indicates which Pebble features should be enabled when the store is first
opened, before any SSTables are opened. The versions indicate points of
backwards incompatibility for a store. For example, the introduction of the
SetWithDelete key kind is gated behind a version, as is block property
collection. This format major version scheme was introduced in
#1227.

While Pebble can use the format major version to infer how to load and
interpret data in the LSM, the SSTables that make up the store itself have
their own notion of a "version". This "SSTable version" (also referred to as a
"table format") is written to the footer (or trailing section) of each SSTable
file and determines how the file is to be interpreted by Pebble. As of the time
of writing, Pebble supports two table formats - LevelDB's format, and RocksDB's
v2 format. Pebble inherited the latter as the default table format as it was
the version that RocksDB used at the time Pebble was being developed, and
remained the default to allow for a simpler migration path from Cockroach
clusters that were originally using RocksDB as the storage engine. The
RocksDBv2 table format adds various features on top of the LevelDB format,
including a two-level index, configurable checksum algorithms, and an explicit
versioning scheme to allow for the introduction of changes, amongst other
features.

While the RocksDBv2 SSTable format has been sufficient for Pebble's needs since
inception, new Pebble features and potential backports from RocksDB itself
require that the SSTable format evolve over time and therefore that the table
format be updated. As the majority of new features added over time will be
specific to Pebble, it does not make sense to repurpose the RocksDB format
versions that exist upstream for use with Pebble features (at the time of
writing, RocksDB had added versions 3 and 4 on top of the version 2 in use by
Pebble). A new Pebble-specific table format scheme is proposed.

In the context of a distributed system such as Cockroach, certain SSTable
features are backwards incompatible (e.g. the block property collection and
filtering feature extends the RocksDBv2 SSTable block index format to encoded
various block properties, which is a breaking change). Participants must
first ensure that their stores have the code-level features available to read
and write these newer SSTables (indicated by Pebble's format major version).
Once all stores agree that they are running the minimum Pebble format major
version and will not roll back (e.g. Cockroach cluster version finalization),
SSTables can be written and read using more recent table formats. The Pebble
"format major version" and "table format version" are therefore no longer
independent - the former implies an upper bound on the latter.

Additionally, certain SSTable generation operations are independent of a
specific Pebble instance. For example, SSTable construction for the purposes of
backup and restore generates SSTables that are stored external to a specific
Pebble store (e.g. in cloud storage) can be used at a later point in time to
restore a store. SSTables constructed for such purposes must be carefully
versioned to ensure compatibility with existing clusters that may run with a
mixture of Pebble versions.

As a real-world example of the need for the above, consider two Cockroach nodes
each with a Pebble store, one at version A, the other at version B (version A
(newer) > B (older)). Store A constructs an SSTable for an external backup
containing a newer block index format (for block property collection). This
SSTable is then imported in to store B. Store B fails to read the SSTable as it
is not running with a format major version recent enough make sense of the
newer index format. The two stores require a method for agreeing on a minimum
supported table format.

The remainder of this document outlines a new table format for Pebble. This new
table format will be used for new table-level features such as block properties
and range keys (see
#1339), but also for
backporting table-level features from RocksDB that would be useful to Pebble
(e.g. version 3 avoids encoding sequence numbers in the index, and version 4
uses delta encoding for the block offsets in the index, both of which are
useful for Pebble).

Technical design

Pebble magic number Copy Chapter

The last 8 bytes of an SSTable is referred to as the "magic number".

LevelDB uses the first 8 bytes of the SHA1 hash of the string
http://code.google.com/p/leveldb/ for the magic number.

RocksDB uses its own magic number, which indicates the use of a slightly
different table layout - the footer (the name for the end of an SSTable) is
slightly larger to accommodate a 32-bit version number and 8 bits for a
checksum type to be used for all blocks in the SSTable.

A new 8-byte magic number will be introduced for Pebble:

\xf0\x9f\xaa\xb3\xf0\x9f\xaa\xb3 // 🪳🪳

Pebble version scheme Copy Chapter

Tables with a Pebble magic number will use a dedicated versioning scheme,
starting with version 1. No new versions other than version 2 will be
supported for tables containing the RocksDB magic number.

The choice of switching to a Pebble versioning scheme starting 1 simplifies
the implementation. Essentially all existing Pebble stores are managed via
Cockroach, and were either previously using RocksDB and migrated to Pebble, or
were created with Pebble stores. In both situations the table format used is
RocksDB v2.

Given that Pebble has not needed (and likely will not need) to support other
RocksDB table formats, it is reasonable to introduce a new magic number for
Pebble and reset the version counter to v1.

The following initial versions will correspond to the following new Pebble
features, that have yet to be introduced to Cockroach clusters as of the time
of writing:

• Version 1: block property collectors (block properties are encoded into the
  block index)
• Version 2: range keys (a new block is present in the table for range keys).

Subsequent alterations to the SSTable format should only increment the Pebble
version number. It should be noted that backported RocksDB table format
features (e.g. RocksDB versions 3 and 4) would use a different version number,
within the Pebble version sequence. While possibly confusing, the RocksDB
features are being "adopted" by Pebble, rather than directly ported, so a
Pebble specific version number is appropriate.

An alternative would be to allow RocksDB table format features to be backported
into Pebble under their existing RocksDB magic number, alongside
Pebble-specific features. The complexity required to determine the set of
characteristics to read and write to each SSTable would increase with such a
scheme, compared to the simpler "linear history" approach described above,
where new features simply ratchet the Pebble table format version number.

Footer format Copy Chapter

The footer format for SSTables with Pebble magic numbers will remain the same
as the RocksDB footer format - specifically, the trailing 53-bytes of the
SSTable consisting of the following fields with the given indices,
little-endian encoded:

• 0: Checksum type
• 1-20: Meta-index block handle
• 21-40: Index block handle
• 41-44: Version number
• 45-52: Magic number

Changes / additions to `sstable.TableFormat` Copy Chapter

The sstable.TableFormat enum is a uint32 representation of the tuple
`(magic number, format version). The current values are:

type TableFormat uint32

const (
  TableFormatRocksDBv2 TableFormat = iota
  TableFormatLevelDB
)

It should be noted that this enum is not persisted in the SSTable. It is
purely an internal type that represents the tuple that simplifies a number of
version checks when reading / writing an SSTable. The values are free to
change, provided care is taken with default values and existing usage.

The existing sstable.TableFormat will be altered to reflect the "linear"
nature of the version history. New versions will be added with the next value
in the sequence.

const (
	TableFormatUnspecified TableFormat = iota
  TableFormatLevelDB    // The original LevelDB table format.
  TableFormatRocksDBv2  // The current default table format.
	TableFormatPebblev1   // Block properties.
	TableFormatPebblev2   // Range keys.
  ...
  TableFormatPebbleDBvN
)

The introduction of TableFormatUnspecified can be used to ensure that where a
sstable.TableFormat is not specified, Pebble can select a suitable default
for writing the table (most likely based on the format major version in use by
the store; more in the next section).

Interaction with the format major version Copy Chapter

The FormatMajorVersion type is used to determine the set of features the
store supports.

A Pebble store may be read-from / written-to by a Pebble binary that supports
newer features, with more recent Pebble format major versions. These newer
features could include the ability to read and write more recent SSTables.
While the store could read and write SSTables at the most recent version the
binary supports, it is not safe to do so, for reasons outlined earlier.

The format major version will have a "maximum table format version" associated
with it that indicates the maximum sstable.TableFormat that can be safely
handled by the store.

When introducing a new table format version, it should be gated behind an
associated FormatMajorVersion that has the new table format as its "maximum
table format version".

For example:

// Existing versions.
FormatDefault.MaxTableFormat()                       // sstable.TableFormatRocksDBv2
...
FormatSetWithDelete.MaxTableFormat()                 // sstable.TableFormatRocksDBv2
// Proposed versions with Pebble version scheme.
FormatBlockPropertyCollector.MaxTableFormat()        // sstable.TableFormatPebbleDBv1
FormatRangeKeys.MaxTableFormat()                     // sstable.TableFormatPebbleDBv2

Usage in Cockroach Copy Chapter

The introduction of new SSTable format versions needs to be carefully
coordinated between stores to ensure there are no incompatibilities (i.e. newer
store writes an SSTable that cannot be understood by other stores).

It is only safe to use a new table format when all nodes in a cluster have been
finalized. A newer Cockroach node, with newer Pebble code, should continue to
write SSTables with a table format version equal to or less than the smallest
table format version across all nodes in the cluster. Once the cluster version
has been finalized, and (*DB).RatchetFormatMajorVersion(FormatMajorVersion)
has been called, nodes are free to write SSTables at newer table format
versions.

At runtime, Pebble exposes a (*DB).FormatMajorVersion() method, which may be
used to determine the current format major version of the store, and hence, the
associated table format version.

In addition to the above, there are situations where SSTables are created for
consumption at a later point in time, independent of any Pebble store -
specifically backup and restore. Currently, Cockroach uses two functions in
pkg/sstable to construct SSTables for both ingestion and backup
(here
and
here).
Both will need to be updated to take into account the cluster version to ensure
that SSTables with newer versions are only written once the cluster version has
been finalized.

Cluster version migration sequencing Copy Section

Cockroach uses cluster versions as a guarantee that all nodes in a cluster are
running at a particular binary version, with a particular set of features
enabled. The Pebble store is ratcheted as the cluster version passes certain
versions that correspond to new Pebble functionality. Care must be taken to
prevent subtle race conditions while the cluster version is being updated
across all nodes in a cluster.

Consider a cluster at cluster version n-1 with corresponding Pebble format
major version A. A new cluster version n introduces a new Pebble format
major version B with new table level features. One by one, nodes will bump
their format major versions from A to B as they are upgraded to cluster
version n. There exists a period of time where nodes in a cluster are split
between cluster versions n-1 and n, and Pebble format major versions A
and B. If version B introduces SSTable level features that nodes with
stores at format major version A do not yet understand, there exists the risk
for runtime incompatibilities.

To guard against the window of incompatibility, two cluster versions are
employed when bumping Pebble format major versions that correspond to new
SSTable level features. The first cluster version is used to synchronize all
stores at the same Pebble format major version (and therefore table format
version). The second cluster version is used as a feature gate that enables
Cockroach nodes to make use of the newer table format, relying on the guarantee
that if a node is at version n + 1, then all other nodes in the cluster must
all be at least at version n, and therefore have Pebble stores at format
major version B.

RFCS 20220311 Pebble Flushable Ingested Sstable (`docs/RFCS/20220311_pebble_flushable_ingested_sstable.md`) Copy Section

• Feature Name: Flushable Ingested SSTable
• Status: in-progress
• Start Date: 2022-03-11
• Authors: Mufeez Amjad
• RFC PR: #1586
• Pebble Issues: #25
• Cockroach Issues:

Summary Copy Chapter

To avoid a forced flush when ingesting SSTables that have an overlap with a
memtable, we "lazily" add the SSTs to the LSM as a *flushableEntry to
d.mu.mem.queue. In comparison to a regular ingest which adds the SSTs to the
lowest possible level, the SSTs will get placed in the memtable queue before
they are eventually flushed (to the lowest level possible). This state is only
persisted in memory until a flush occurs, thus we require a WAL entry to replay
the ingestion in the event of a crash.

Motivation Copy Chapter

Currently, if any of the SSTs that need to be ingested have an overlap with a
memtable, we
wait
for the memtable to be flushed before the ingestion can proceed. This is to
satisfy the invariant that newer entries (those in the ingested SSTs) in the LSM
have a higher sequence number than old entries (those in the memtables). This
problem is also present for subsequent normal writes that are blocked behind the
ingest waiting for their sequence number to be made visible.

Technical Design Copy Chapter

The proposed design is mostly taken from Peter's suggestion in #25. The core
requirements are:

1. Replayable WAL entry for the ingest.
2. Implementation of the flushable interface for a new ingestedSSTables struct.
3. Lazily adding the ingested SSTs to the LSM.
4. Flushing logic to move SSTs into L0-L6.

1. WAL Entry Copy Section

We require a WAL entry to make the ingestion into the flushable queue
replayable, and there is a need for a new type of WAL entry that does not get
applied to the memtable. 2 approaches were considered:

1. Using seqnum=0 to differentiate this new WAL entry.
2. Introduce a new InternalKeyKind for the new WAL entry,
   InternalKeyKindIngestSST.

We believe the second approach is better because it avoids modifying batch
headers which can be messy/hacky and because seqnum=0 is already used for
unapplied batches. The second approach also gives way for a simpler/cleaner
implementation because it utilizes the extensibility of InternalKeyKind and is
similar to the treatment of InternalKeyKindLogData. It also follows the
correct seqnum semantics for SSTable ingestion in the event of a WAL replay —
each SST in the ingestion batch already gets its own sequence number.

This change will need to be gated on a FormatMajorVersion because if the store
is opened with an older version of Pebble, Pebble will not understand any WAL
entry that contains the new InternalKeyKind.

When performing an ingest (with overlap), we create a batch with the header:

+-------------+------------+--- ... ---+
| SeqNum (8B) | Count (4B) |  Entries  |
+-------------+------------+--- ... ---+

whereSeqNum is the current running sequence number in the WAL, Count is the
number of ingested SSTs, and each entry has the form:

+-----------+-----------------+-------------------+
| Kind (1B) | Key (varstring) | Value (varstring) |
+-----------+-----------------+-------------------+

where Kind is InternalKeyKindIngestSST, and Key is a path to the
ingested SST on disk.

When replaying the WAL, we check every batch's first entry and if keykind == InternalKeyKindIngestSSTs then we continue reading the rest of the entries in
the batch of SSTs and replay the ingestion steps - we construct a
flushableEntry and add it to the flushable queue:

b = Batch{db: d}
b.SetRepr(buf.Bytes())
seqNum := b.SeqNum()
maxSeqNum = seqNum + uint64(b.Count())
br := b.Reader()
if kind, _, _, _ := br.Next(); kind == InternalKeyKindIngestSST {
  // Continue reading the rest of the batch and construct flushable 
  // of sstables with correct seqnum and add to queue.
  buf.Reset()
  continue
}

2. `flushable` Implementation Copy Section

Introduce a new flushable type: ingestedSSTables.

type ingestedSSTables struct {
    files []*fileMetadata
    size  uint64

    cmp      Compare
    newIters tableNewIters
}

which implements the following functions from the flushable interface:

1. `newIter(o *IterOptions) internalIterator`

We return a levelIter since the ingested SSTables have no overlap, and we can
treat them like a level in the LSM.

levelSlice := manifest.NewLevelSliceKeySorted(s.cmp, s.files)
return newLevelIter(*o, s.cmp, nil, s.newIters, levelSlice.Iter(), 0, nil)

On the client-side, this iterator would have to be used like this:

var iter internalIteratorWithStats
var rangeDelIter keyspan.FragmentIterator
iter = base.WrapIterWithStats(mem.newIter(&dbi.opts))
switch mem.flushable.(type) {
case *ingestedSSTables:
    iter.(*levelIter).initRangeDel(&rangeDelIter)
default:
    rangeDelIter = mem.newRangeDelIter(&dbi.opts)
}

mlevels = append(mlevels, mergingIterLevel{
    iter:         iter,
    rangeDelIter: rangeDelIter,
})

2. `newFlushIter(o *IterOptions, bytesFlushed *uint64) internalIterator`

3. `newRangeDelIter(o *IterOptions) keyspan.FragmentIterator`

The above two methods would return nil. By doing so, in c.newInputIter():

if flushIter := f.newFlushIter(nil, &c.bytesIterated); flushIter != nil {
    iters = append(iters, flushIter)
}
if rangeDelIter := f.newRangeDelIter(nil); rangeDelIter != nil {
    iters = append(iters, rangeDelIter)
}

we ensure that no iterators on ingestedSSTables will be used while flushing in
c.runCompaction().

The special-cased flush process for this flushable is described in Section
4.

4. `newRangeKeyIter(o *IterOptions) keyspan.FragmentIterator`

Will wait on range key support in levelIter to land before implementing.

5. `inuseBytes() uint64` and `totalBytes() uint64`

For both functions, we return 0.

Returning 0 for inuseBytes() means that the calculation of c.maxOverlapBytes
is not affected by the SSTs (the ingested SSTs don't participate in the
compaction).

We don't want the size of the ingested SSTs to contribute to the size of the
memtable when determining whether or not to stall writes
(MemTableStopWritesThreshold); they should contribute to the L0 read-amp
instead (L0StopWritesThreshold). Thus, we'll have to special case for ingested
SSTs in d.makeRoomForWrite() to address this detail.

totalBytes() represents the number of bytes allocated by the flushable, which
in our case is 0. A consequence for this is that the size of the SSTs do not
count towards the flush threshold calculation. However, by setting
flushableEntry.flushForced we can achieve the same behaviour.

6. `readyForFlush() bool`

The flushable of ingested SSTs can always be flushed because the files are
already on disk, so we return true.

3. Lazily adding the ingested SSTs to the LSM Copy Section

The steps to add the ingested SSTs to the flushable queue are:

1. Detect an overlap exists (existing logic).

Add a check that falls back to the old ingestion logic of blocking the ingest on
the flush when len(d.mu.mem.queue) >= MemtablesStopWritesThreshold - 1. This
reduces the chance that many short, overlapping, and successive ingestions cause
a memtable write stall.

Additionally, to mitigate the hiccup on subsequent normal writes, we could wait
before the call to d.commit.AllocateSeqNum until:

1. the number of immutable memtables and ingestedSSTs in the flushable queue
   is below a certain threshold (to prevent building up too many sublevels)

2. the number of immutable memtables is low. This could lead to starvation if
   there is a high rate of normal writes.

3. Create a batch with the list of ingested SSTs.

b := newBatch()
for _, path := range paths:
    b.IngestSSTs([]byte(path), nil)

3. Apply the batch.

In the call to d.commit.AllocateSeqNum, b.count sequence numbers are already
allocated before the prepare step. When we identify a memtable overlap, we
commit the batch to the WAL manually (through logic similar to
commitPipeline.prepare). The apply step would be a no-op if we performed a
WAL write in the prepare step. We would also need to truncate the memtable/WAL
after this step.

5. Create ingestedSSTables flushable and flushableEntry.

We'd need to call ingestUpdateSeqNum on these SSTs before adding them to the
flushable. This is to respect the sequence number ordering invariant while the
SSTs reside in the flushable queue.

6. Add to flushable queue.

Pebble requires that the last entry in d.mu.mem.queue is the mutable memtable
with value d.mu.mem.mutable. When adding a flushableEntry to the queue, we
want to maintain this invariant. To do this we pass nil as the batch to
d.makeRoomForWrite(). The result is

| immutable old memtable | mutable new memtable |

We then append our new flushableEntry, and swap the last two elements in
d.mu.mem.queue:

| immutable old memtable | ingestedSSTables | mutable new memtable |

Because we add the ingested SSTs to the flushable queue when there is overlap,
and are skipping applying the version edit through the apply step of the
ingestion, we ensure that the SSTs are only added to the LSM once.

7. Call d.maybeScheduleFlush().

Because we've added an immutable memtable to the flushable queue and set
flushForced on the flushableEntry, this will surely result in a flush. This
call can be done asynchronously.

We can then return to caller without waiting for the flush to finish.

4. Flushing logic to move SSTs into L0-L6 Copy Section

By returning nil for both flushable.newFlushIter() and
flushable.newRangeDelIter(), the ingestedSSTables flushable will not be
flushed normally.

The suggestion in issue #25 is to move the SSTs from the flushable queue into
L0. However, only the tables that overlap with the memtable will need to target
L0 (because they will likely overlap with L0 post flush), the others can be
moved to lower levels in the LSM. We can use the existing logic in
ingestTargetLevel to determine which level to move the ingested SSTables to
during c.runCompaction(). However, it's important to do this step after the
memtable has been flushed to use the correct version when determining overlap.

The flushable of ingested SSTs should not influence the bounds on the
compaction, so we will have to skip updating c.smallest and c.largest in
d.newFlush() for this flushable.

RFCS 20221122 Virtual Sstable (`docs/RFCS/20221122_virtual_sstable.md`) Copy Section

• Feature Name: Virtual sstables
• Status: in-progress
• Start Date: 2022-10-27
• Authors: Arjun Nair
• RFC PR: https://github.com/cockroachdb/pebble/pull/2116
• Pebble Issues:
  https://github.com/cockroachdb/pebble/issues/1683

** Design Draft**

Summary

The RFC outlines the design to enable virtualizing of physical sstables
in Pebble.

A virtual sstable has no associated physical data on disk, and is instead backed
by an existing physical sstable. Each physical sstable may be shared by one, or
more than one virtual sstable.

Initially, the design will be used to lower the read-amp and the write-amp
caused by certain ingestions. Sometimes, ingestions are unable to place incoming
files, which have no data overlap with other files in the lsm, lower in the lsm
because of file boundary overlap with files in the lsm. In this case, we are
forced to place files higher in the lsm, sometimes in L0, which can cause higher
read-amp and unnecessary write-amp as the file is moved lower down the lsm. See
https://github.com/cockroachdb/cockroach/issues/80589 for the problem occurring
in practice.

Eventually, the design will also be used for the disaggregated storage masking
use-case: https://github.com/cockroachdb/cockroach/pull/70419/files.

This document describes the design of virtual sstables in Pebble with enough
detail to aid the implementation and code review.

Design

Ingestion Copy Section

When an sstable is ingested into Pebble, we try to place it in the lowest level
without any data overlap, or any file boundary overlap. We can make use of
virtual sstables in the cases where we're forced to place the ingested sstable
at a higher level due to file boundary overlap, but no data overlap.

s2
ingest:                     [i-j-------n]
                                  s1
L6:                 [e---g-----------------p---r]
             a b c d e f g h i j k l m n o p q r s t u v w x y z

Consider the sstable s1 in L6 and the ingesting sstable s2. It is clear that
the file boundaries of s1 and s2 overlap, but there is no data overlap as shown
in the diagram. Currently, we will be forced to ingest the sstable s2 into a
level higher than L6. With virtual sstables, we can split the existing sstable
s1 into two sstables s3 and s4 as shown in the following diagram.

s3         s2        s4
L6:                 [e---g]-[i-j-------n]-[p---r]
             a b c d e f g h i j k l m n o p q r s t u v w x y z

The sstable s1 will be deleted from the lsm. If s1 was a physical sstable, then
we will keep the file on disk as long as we need to so that it can back the
virtual sstables.

There are cases where the ingesting sstables have no data overlap with existing
sstables, but we can't make use of virtual sstables. Consider:

s2
ingest:               [f-----i-j-------n]
                                  s1
L6:                 [e---g-----------------p---r]
             a b c d e f g h i j k l m n o p q r s t u v w x y z

We cannot use virtual sstables in the above scenario for two reasons:

1. We don't have a quick method of detecting no data overlap.
2. We will be forced to split the sstable in L6 into more than two virtual
   sstables, but we want to avoid many small virtual sstables in the lsm.

Note that in Cockroach, the easier-to-solve case happens very regularly when an
sstable spans a range boundary (which pebble has no knowledge of), and we ingest
a snapshot of a range in between the two already-present ranges.

slide in between two existing sstables is more likely to happen. It occurs when
we ingest a snapshot of a range in between two already present ranges.

ingestFindTargetLevel changes:

• The ingestFindTargetLevel function is used to determine the target level
  of the file which is being ingested. Currently, this function returns an int
  which is the target level for the ingesting file. Two additional return
  parameters, []manifest.NewFileEntry and *manifest.DeletedFileEntry, will be
  added to the function.

• If ingestFindTargetLevel decides to split an existing sstable into virtual
  sstables, then it will return new and deleted entries. Otherwise, it will only
  return the target level of the ingesting file.

• Within the ingestFindTargetLevel function, the overlapWithIterator
  function is used to quickly detect data overlap. In the case with file
  boundary overlap, but no data overlap, in the lowest possible level, we will
  split the existing sstable into virtual sstables and generate the
  NewFileEntrys and the DeletedFileEntry. The FilemetaData section
  describes how the various fields in the FilemetaData will be computed for
  the newly created virtual sstables.

• Note that we will not split physical sstables into virtual sstables in L0 for
  the use case described in this RFC. The benefit of doing so would be to reduce
  the number of L0 sublevels, but the cost would be additional implementation
  complexity(see the FilemetaData section). We also want to avoid too many
  virtual sstables in the lsm as they can lead to space amp(see Compaction
  section). However, in the future, for the disaggregated storage masking case,
  we would need to support ingestion and use of virtual sstables in L0.

• Note that we may need an upper bound on the number of times an sstable is
  split into smaller virtual sstables. We can further reduce the risk of many
  small sstables:

  1. For CockroachDB's snapshot ingestion, there is one large sst (up to 512MB)
     and many tiny ones. We can choose the apply this splitting logic only for
     the large sst. It is ok for the tiny ssts to be ingested into L0.
  2. Split only if the ingested sst is at least half the size of the sst being
     split. So if we have a smaller ingested sst, we will pick a higher level to
     split at (where the ssts are smaller). The lifetime of virtual ssts at a
     higher level is smaller, so there is lower risk of littering the LSM with
     long-lived small virtual ssts.
  3. For disaggregated storage implementation, we can avoid masking for tiny
     sstables being ingested and instead write a range delete like we currently
     do. Precise details on the masking use case are out of the scope of this
     RFC.

ingestApply changes:

• The new and deleted file entries returned by the ingestFindTargetLevel
  function will be added to the version edit in ingestApply.
• We will appropriately update the levelMetrics based on the new information
  returned by ingestFindTargetLevel.

`FilemetaData` changes Copy Section

Each virtual sstables will have a unique file metadata value associated with it.
The metadata may be borrowed from the backing physical sstable, or it may be
unique to the virtual sstable.

This rfc lists out the fields in the FileMetadata struct with information on
how each field will be populated.

Atomic.AllowedSeeks: Field is used for read triggered compactions, and we can
populate this field for each virtual sstable since virtual sstables can be
picked for compactions.

Atomic.statsValid: We can set this to true(1) when the virtual sstable is
created. On virtual sstable creation we will estimate the table stats of the
virtual sstable based on the table stats of the physical sstable. We can also
set this to 0 and let the table stats job asynchronously compute the stats.

refs: The will be turned into a pointer which will be shared by the
virtual/physical sstables. See the deletion section of the RFC to learn how the
refs count will be used.

FileNum: We could give each virtual sstable its own file number or share
the file number between all the virtual sstables. In the former case, the virtual
sstables will be distinguished by the file number, and will have an additional
metadata field to indicate the file number of the parent sstable. In the latter
case, we can use a few of the most significant bits of the 64 bit file number to
distinguish the virtual sstables.

The benefit of using a single file number for each virtual sstable, is that we
don't need to use additional space to store the file number of the backing
physical sstable.

It might make sense to give each virtual sstable its own file number. Virtual
sstables are picked for compactions, and compactions and compaction picking
expect a unique file number for each of the files which it is compacting.
For example, read compactions will use the file number of the file to determine
if a file picked for compaction has already been compacted, the version edit
will expect a different file number for each virtual sstable, etc.

There are direct references to the FilemetaData.FileNum throughout Pebble. For
example, the file number is accessed when the DB.Checkpoint function is
called. This function iterates through the files in each level of the lsm,
constructs the filepath using the file number, and reads the file from disk. In
such cases, it is important to exclude virtual sstables.

Size: We compute this using linear interpolation on the number of blocks in
the parent sstable and the number of blocks in the newly created virtual sstable.

SmallestSeqNum/LargestSeqNum: These fields depend on the parent sstable,
but we would need to perform a scan of the physical sstable to compute these
accurately for the virtual sstable upon creation. Instead, we could convert
these fields into lower and upper bounds of the sequence numbers in a file.

These fields are used for l0 sublevels, pebble tooling, delete compaction hints,
and a lot of plumbing. We don't need to worry about the L0 sublevels use case
because we won't have virtual sstables in L0 for the use case in this RFC. For
the rest of the use cases we can use lower bound for the smallest seq number,
and an upper bound for the largest seq number work.

TODO(bananabrick): Add more detail for any delete compaction hint changes if
necessary.

Smallest/Largest: These, along with the smallest/largest ranges for the range
and point keys can be computed upon virtual sstable creation. Precisely, these
can be computed when we try and detect data overlap in the overlapWithIterator
function during ingestion.

Stats: TableStats will either be computed upon virtual sstable creation
using linear interpolation on the block counts of the virtual/physical sstables
or asynchronously using the file bounds of the virtual sstable.

PhysicalState: We can add an additional struct with state associated with
physical ssts which have been virtualized.

type PhysicalState struct {
  // Total refs across all virtual ssts * versions. That is, if the same virtual
  // sst is present in multiple versions, it may have multiple refs, if the
  // btree node is not the same.
  totalRefs int32

  // Number of virtual ssts in the latest version that refer to this physical
  // SST. Will be 1 if there is only a physical sst, or there is only 1 virtual
  // sst referencing this physical sst.
  // INVARIANT: refsInLatestVersion <= totalRefs
  // refsInLatestVersion == 0 is a zombie sstable.
  refsInLatestVersion int32

  fileSize uint64

  // If sst is not virtualized and in latest version
  // virtualSizeSumInLatestVersion == fileSize. If
  // virtualSizeSumInLatestVersion > 0 and
  // virtualSizeSumInLatestVersion/fileSize is very small, the corresponding
  // virtual sst(s) should be candidates for compaction. These candidates can be
  // tracked via btree annotations. Incrementlly updated in
  // BulkVersionEdit.Apply, when updating refsInLatestVersion.
  virtualSizeSumInLatestVersion uint64
}

The Deletion section and the Compactions section describe why we need to
store the PhysicalState.

Deletion of physical and virtual sstables Copy Section

We want to ensure that the physical sstable is only deleted from disk when no
version references it, and when there are no virtual sstables which are backed
by the physical sstable.

Since FilemetaData.refs is a pointer which is shared by the physical and
virtual sstables, the physical sstable won't be deleted when it is removed
from the latest version as the FilemetaData.refs will have been increased
when the virtual sstable is added to a version. Therefore, we only need to
ensure that the physical sstable is eventually deleted when there are no
versions which reference it.

Sstables are deleted from disk by the DB.doDeleteObsoleteFiles function which
looks for files to delete in the DB.mu.versions.obsoleteTables slice.
So we need to ensure that any physical sstable which was virtualized is added to
the obsolete tables list iff FilemetaData.refs is 0.

Sstable are added to the obsolete file list when a Version is unrefed and
when DB.scanObsoleteFiles is called when Pebble is opened.

When a Version is unrefed, sstables referenced by it are only added to the
obsolete table list if the FilemetaData.refs hits 0 for the sstable. With
virtual sstables, we can have a case where the last version which directly
references a physical sstable is unrefed, but the physical sstable is not added
to the obsolete table list because its FilemetaData.refs count is not 0
because of indirect references through virtual sstables. Since the last Version
which directly references the physical sstable is deleted, the physical sstable
will never get added to the obsolete table list. Since virtual sstables keep
track of their parent physical sstable, we can just add the physical sstable to
the obsolete table list when the last virtual sstable which references it is
deleted.

DB.scanObsoleteFiles will delete any file which isn't referenced by the
VersionSet.versions list. So, it's possible that a physical sstable associated
with a virtual sstable will be deleted. This problem can be fixed by a small
tweak in the d.mu.versions.addLiveFileNums to treat the parent sstable of
a virtual sstable as a live file.

Deleted files still referenced by older versions are considered zombie sstables.
We can extend the definition of zombie sstables to be any sstable which is not
directly, or indirectly through virtual sstables, referenced by the latest
version. See the PhysicalState subsection of the FilemetaData section
where we describe how the references in the latest version will be tracked.

Reading from virtual sstables Copy Section

Since virtual sstables do not exist on disk, we will have to redirect reads
to the physical sstable which backs the virtual sstable.

All reads to the physical files go through the table cache which opens the file
on disk and creates a Reader for the reads. The table cache currently creates
a FileNum -> Reader mapping for the physical sstables.

Most of the functions in table cache API take the file metadata of the file as
a parameter. Examples include newIters, newRangeKeyIter, withReader, etc.
Each of these functions then calls a subsequent function on the sstable
Reader.

In the Reader API, some functions only really need to be called on physical
sstables, whereas some functions need to be called on both physical and virtual
sstables. For example, the Reader.EstimateDiskUsage usage function, or the
Reader.Layout function only need to be called on physical sstables, whereas,
some function like, Reader.NewIter, and Reader.NewCompactionIter need to
work with virtual sstables.

We could either have an abstraction over the physical sstable Reader per
virtual sstable, or update the Reader API to accept file bounds of the
sstable. In the latter case, we would create one Reader on the physical
sstable for all of the virtual sstables, and update the Reader API to accept
the file bounds of the sstable.

Changes required to share a Reader on the physical sstable among the virtual
sstable:

• If the file metadata of the virtual sstable is passed into the table cache, on
  a table cache miss, the table cache will load the Reader for the physical
  sstable. This step can be performed in the tableCacheValue.load function. On
  a table cache hit, the file number of the parent sstable will be used to fetch
  the appropriate sstable Reader.
• The Reader api will be updated to support reads from virtual sstables. For
  example, the NewCompactionIter function will take additional
  lower,upper []byte parameters.

Updates to iterators:

• Reader.NewIter already has lower,upper []byte parameters so this requires
  no change.
• Add lower,upper fields to the Reader.NewCompactionIter. The function
  initializes single level and two level iterators, and we can pass in the
  lower,upper values to those. TODO(bananabrick): Make sure that the value
  of bytesIterated in the compaction iterator is still accurate.
• Reader.NewRawRangeKeyIter/NewRawRangeDelIter: We need to add lower/upper
  fields to the functions. Both iterators make use of a fragmentBlockIter. We
  could filter keys above the fragmentBlockIter or add filtering within the
  fragmentBlockIter. To add filtering within the fragmentBlockIter we will
  initialize it with two additional lower/upper []byte fields.
• We would need to update the SetBounds logic for the sstable iterators to
  never set bounds for the iterators outside the virtual sstable bounds. This
  could lead to keys outside the virtual sstable bounds, but inside the physical
  sstable bounds, to be surfaced.

TODO(bananabrick): Add a section about sstable properties, if necessary.

Compactions Copy Section

Virtual sstables can be picked for compactions. If the FilemetaData and the
iterator stack changes work, then compaction shouldn't require much, if any,
additional work.

Virtual sstables which are picked for compactions may cause space amplification.
For example, if we have two virtual sstables a and b in L5, backed by a
physical sstable c, and the sstable a is picked for a compaction. We will
write some additional data into L6, but we won't delete sstable c because
sstable b still refers to it. In the worst case, sstable b will never be
picked for compaction and will never be compacted into and we'll have permanent
space amplification. We should try prioritize compaction of sstable b to
prevent such a scenario.

See the PhysicalState subsection in the FilemetaData section to see how
we'll store compaction picking metrics to reduce virtual sstable space-amp.

`VersionEdit` decode/encode Copy Section

Any additional fields added to the FilemetaData need to be supported in the
version edit decode/encode functions.

RFCS 20240701 Tombstone Density Heuristic (`docs/RFCS/20240701_tombstone_density_heuristic.md`) Copy Section

• Feature Name: Compaction heuristics for point tombstone density
• Status: done as of 2024-08-15
• Start Date: 2024-06-28
• Authors: Anish Shanbhag
• RFC PR: cockroachdb#3719
• Pebble Issues: https://github.com/cockroachdb/pebble/issues/918

Summary

This design document outlines a new compaction type in Pebble which specifically targets the reduction of point tombstone density to enhance read performance. The heuristic is designed to eliminate high densities of point tombstones which slow down iteration due to unnecessary I/O and CPU usage.

The new heuristic was introduced in cockroachdb#3790.

Motivation

Pebble currently contains a variety of compaction heuristics which are mostly based on SSTable file size. One weak point in the compaction heuristics involves the case where we have a large buildup of close-together point tombstones, which causes reads for keys after the tombstone cluster to become extremely slow.

As identified here, uncompacted point tombstones reduce read performance in two ways: the extra CPU cycles needed to iterate over them during a seek, and the extra I/O needed to load more blocks which contain live keys.

It's important that we reduce tombstone density before the tombstones are read because there are many cases where tombstones are written for very long periods before any reads are triggered.

Even though our current heuristics take the potential amount of reclaimed space from compacting point tombstones into account, there are specific situations where this is not sufficient to prevent point tombstone buildup. Specifically, these are some of the factors that lead to this issue:

1. Tombstone buildup usually only happens in large stores (> 10 GB) once multiple levels of the LSM start to be populated.
2. The LSM is "too well shaped" in that the size ratio between levels is at the proper value, so compaction scores for each level are all calculated to be <1 and thus no compactions are scheduled.
   • Observed in this escalation (internal only)
3. Read performance becomes especially bad when we have a high density of point tombstones in higher levels (L0-3) which span many SSTables in the bottommost levels (L4-6).
4. The problem is especially apparent when there's one key range which we write to/delete from frequently and an adjacent key range which we read frequently.
   • RocksDB describes how queues commonly contain this type of workload.
   • We've seen this behavior multiple times with CockroachDB's implementation of the KV liveness range.
     • Observed in multiple escalations including here and here (internal only)
     • We had the raft log sandwiched between the frequently-read keys used for expiration-based leases. Nodes used to gossip their liveness every few seconds, which writes and deletes messages from the raft log over and over. This makes the raft log span numerous SSTables that fill up the cache with tombstones, removing the frequently-read lease expiration keys from the cache. Liveness has since been changed to use a different implementation but the root cause still exists here.
   • Outbox/queue-based workloads also run into this issue because we continuously delete keys from the start of a range and add keys to the end of the range.
5. Tombstones build up more often when KV pairs are small in size because more KVs fit into a single SSTable. In this case, heuristics that measure the possibility of disk space reclamation don't work because the tombstones take up little space despite filling up the key space.
6. The problem is specific to operations including SeekGE/SeekLT and Next/Prev because we sequentially iterate over multiple keys during these. For example, if we Next into a swath of tombstones, we need to step through all of the tombstones before reaching a live key.

Design

The new compaction heuristic introduces the concept of a "tombstone-dense" data block. A data block is considered tombstone-dense if it fulfills either of the following criteria:

1. The block contains at least N point tombstones. The default value for N is 100, and is controlled through a new option options.Experimental.NumDeletionsThreshold.
2. The ratio of the uncompressed size of point tombstones to the uncompressed size of the block is at least Y. For example, with the default value of 0.5, a data block of size 4KB would be considered tombstone-dense if it contains at least 2KB of point tombstones. The threshold is configured through a new option options.Experimental.DeletionSizeRatioThreshold.

The two criteria above are meant to eliminate wasteful data blocks that would consume unnecessary resources during reads. The count-based threshold prevents CPU waste, and the size-based threshold prevents I/O waste.

A table is considered eligible for the new tombstone compaction type if the percent of tombstone-dense data blocks (compared to the total number of data blocks in the table) is at least X%. The default is 5% and is configured via the new options.Experimental.TombstoneDenseCompactionThreshold. This option may also be set to zero or a negative value to disable tombstone density compactions.

Tombstone-dense data blocks are identified during sstable write time, and their count is recorded in a new table property called NumTombstoneDenseBlocks. During table stats collection, this property is used in conjunction with the NumDataBlocks property to calculate the new TombstoneDenseBlocksRatio table stat. If this calculated ratio is above TombstoneDenseCompactionThreshold, the table becomes eligible for a tombstone density compaction.

We use a manifest.Annotator in a similar way to elision-only compactions in order to prioritize compacting the table with the highest TombstoneDenseBlocksRatio if there are multiple eligible tables.

Tombstone density compactions are executed the same as a default compaction once the candidate file has been chosen. They are prioritized strictly below default compactions and strictly above read-triggered compactions.

Design Exploration Copy Chapter

Below are some ideas which were previously explored when designing this heuristic. Although the heuristic introduced in cockroachdb#3790 differs from these, the ideas may be useful if we still see this problem in the future.

(Expand to view)

1. Tombstone Ratio Copy Section

Note: this heuristic was implemented in cockroachdb#3793 and was found to be somewhat ineffective based the benchmarks tested there

The simplest way to detect a buildup of point tombstones is to define some threshold percentage (TOMBSTONE_THRESHOLD) which indicates that any SSTable where NumDeletions/NumEntries > TOMBSTONE_THRESHOLD should be compacted. For example, if TOMBSTONE_THRESHOLD = 0.6 an SSTable with 10,000 internal keys would be scheduled for compaction if it has at least 6000 tombstones.

• Only considers tombstone density for one SSTable - overlaps with other tables aren't considered
• Runs into issues if we have a swath of point tombstones in a very large SSTable - they still slow down reads but aren't big compared to the overall number of keys in the table
• Probably insufficient to use on its own, but we could try combining this with other methods
  • For example, both RocksDB and ScyllaDB use this in combination with more complex strategies

2. More Granularity Copy Section

For more granularity on a per-SSTable basis, i.e. it's important to know where tombstones are clustered within an SSTable, there are two possible options:

• Divide the key range of the SSTable into buckets of X keys and calculate how many have >Y% tombstones in them
  • If at least Z buckets are tombstone dense, compact this table
• Adapt the sliding window approach from RocksDB
  • RocksDB uses an approach where they "slide a window" across the SSTable keys and schedule compaction if the window has a high enough ratio of tombstones. In other words, while writing if there are ever at least X tombstones in the last Y keys, compact this table
  • We could adapt this 1:1 or try some modifications:
    • Allow the window to expand while tombstones are still being written in order to check the exact key ranges which are tombstone dense. Prioritize compaction of SSTables based on the length of its tombstone swaths

Like the TOMBSTONE_THRESHOLD strategy, this only considers single SSTables, so we can just calculate these metrics on the fly while writing the SSTable and immediately schedule them for compaction if they meet a density criteria.

Note: the heuristic we implemented in cockroachdb#3790 is an example of this category, as we measure tombstone density at block-level granularity with that approach.

3. Key Range Statistics Copy Section

Both methods above only consider tombstone density on a per SSTable basis. We could have a situation where a single continuous key range actually spans tombstone swaths across many levels of the LSM, in which case looking at a single SSTable may not indicate that the key range is tombstone-dense.

In this case, we want the ability to query if a certain key range a->b is "tombstone dense", and if so then compact table(s) overlapping that range. Range annotations which were introduced in cockroachdb#3759 would be a good fit for the implementation.

Given this method to query tombstone stats for arbitrary key ranges, here's a sketch of how the overall compaction process could look:

• After writing an SSTable, add this SSTable and all SSTables which overlap with its key range (using version.Overlaps) to a global set needsTombstoneCheck which marks them as possibly eligible for a tombstone density compaction
  • If the logic below ends up being fast enough, we could avoid having needsTombstoneCheck entirely and check whether compaction is needed during a write itself. But if not, we should defer the check in order to keep writes fast
• Inside pickAuto, we'll check whether any SSTable in needsTombstoneCheck should be compacted
  • For each SSTable T in needsTombstoneCheck, we can get the following info using the Annotator and the table statistics we already have (assuming this SSTable spans the key range a->b:
    • This SSTable
      • number of tombstones in T
      • number of internal keys in T
    • Whole LSM
      • number of tombstones across the whole LSM between a->b
      • total number of internal keys across the whole LSM between a->b
      • Note: if we use the technique from # 2 above to find the tombstone-dense range m->n within this SSTable, we could also get more granular stats:
        • number of tombstones across the whole LSM between m->n
        • number of internal keys across the whole LSM between m->n
  • We now have the 6 stats above about the SSTable's key range, not including any other possible queries we could also make. I'm still unsure about which of these are actually important, and what's the best way to reconcile these into a single signal how how strongly we want to compact this SSTable. My current intuition is that we want to avoid situations where we have a large number of tombstones overlapping a large number of keys in lower levels, so maybe we output a signal proportional to this sstable's tombstone count / total key count of overlapping sstables, or this sstable's tombstone count / total key count of sstables overlapping with this sstable's tombstone cluster(s) in the more granular case? Open to suggestions here. I'm also wondering if we should explicitly prioritize compaction of lower levels vs. higher levels (e.g. L0 vs. L5)
  • Similar to the check in read-based compaction, we'll want to make sure the SSTable still actually exists before compacting it, since it could have been compacted away between being added to needsTombstoneCheck and right now.

4. Maximum Granularity Copy Section

If we find that the key range statistics method above works well but we want even more granularity for key ranges, i.e. because the overestimate of whole-LSM stats above becomes an issue, then we could include per-block tombstone/key counts in the index block of each SSTable, which would allow us to get a more precise count of tombstones for a given key range. This would look pretty similar to the logic separating partial vs. full overlaps in estimateReclaimedSizesBeneath, except we'd be checking tombstone/key count instead of disk usage.

• If we store a running total of the tombstones for each block in the index entry, making this query would be O(log n) or faster, not including the I/O overhead of reading the index block

Testing

Testing methodology and results can be found here. Tombstone buildup has been frequently observed in queue-based workloads and the benchmark introduced in cockroachdb#3744 is meant to capture this case. Below are some further ideas for testing in case they're needed:

• Idea from here - seed a new node with a replication snapshot, which has the tendency for tomstone buildup
• cockroachdb/cockroach#113069 measures performance of liveness range scans since those were often slowed down by tombstones. Even though it looks like liveness logic has changed since then to avoid this, we could adapt the test to induce slow reads.
• Create reproduction roachtests for past slowdown scenarios we've observed

Testdata Write Throughput Summary.Json (`docs/testdata/write-throughput/summary.json`) Copy Section

{
"write/values=1024": [
{
"name": "write/values=1024",
"date": "20260125-abc123def0",
"opsSec": 58825,
"writeAmp": 1.17,
"summaryPath": "20260125-pebble-write-size=1024-run_1-summary.json"
},
{
"name": "write/values=1024",
"date": "20260126-def456abc1",
"opsSec": 65525,
"writeAmp": 1.39,
"summaryPath": "20260126-pebble-write-size=1024-run_1-summary.json"
},
{
"name": "write/values=1024",
"date": "20260127-e789012345",
"opsSec": 62000,
"writeAmp": 1.28,
"summaryPath": "20260127-pebble-write-size=1024-run_1-summary.json"
},
{
"name": "write/values=1024",
"date": "20260128-f012345678",
"opsSec": 67000,
"writeAmp": 1.42,
"summaryPath": "20260128-pebble-write-size=1024-run_1-summary.json"
},
{
"name": "write/values=1024",
"date": "20260129",
"opsSec": 60000,
"writeAmp": 1.22,
"summaryPath": "20260129-pebble-write-size=1024-run_1-summary.json"
},
{
"name": "write/values=1024",
"date": "20260130-b345678901",
"opsSec": 68000,
"writeAmp": 1.45,
"summaryPath": "20260130-pebble-write-size=1024-run_1-summary.json"
},
{
"name": "write/values=1024",
"date": "20260131-c456789012",
"opsSec": 63500,
"writeAmp": 1.32,
"summaryPath": "20260131-pebble-write-size=1024-run_1-summary.json"
},
{
"name": "write/values=1024",
"date": "20260201-d567890123",
"opsSec": 64500,
"writeAmp": 1.35,
"summaryPath": "20260201-pebble-write-size=1024-run_1-summary.json"
},
{
"name": "write/values=1024",
"date": "20260202-e678901234",
"opsSec": 61000,
"writeAmp": 1.25,
"summaryPath": "20260202-pebble-write-size=1024-run_1-summary.json"
},
{
"name": "write/values=1024",
"date": "20260203-f789012345",
"opsSec": 67500,
"writeAmp": 1.43,
"summaryPath": "20260203-pebble-write-size=1024-run_1-summary.json"
}
]
}

--- METRICS ---

• Files Extracted: 15
• Estimated Token Budget: ~48562 tokens
• Canonical Reference: https://codewiki.google/github.com/cockroachdb/pebble