# Technical Documentation: cockroachdb/pebble > ℹ️ **Provenance:** Multi-Tier Ingestion · [CodeWiki Reference](https://codewiki.google/github.com/cockroachdb/pebble) ### Overview (`README.md`) # 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 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 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](docs/rocksdb.md) doc for more details on implementation differences. ## RocksDB Compatibility 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](https://github.com/cockroachdb/pebble/issues/97). ## Format major versions 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`](https://pkg.go.dev/github.com/cockroachdb/pebble#Options) supplied to [`Open`](https://pkg.go.dev/github.com/cockroachdb/pebble#Open), or upgrade the format major version at runtime using [`DB.RatchetFormatMajorVersion`](https://pkg.go.dev/github.com/cockroachdb/pebble#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. | Name | Value | Migration | Pebble support | |------------------------------------|-------|------------|----------------| | FormatMostCompatible | 1 | No | v1 | | FormatVersioned | 3 | No | v1 | | FormatSetWithDelete | 4 | No | v1 | | FormatBlockPropertyCollector | 5 | No | v1 | | FormatSplitUserKeysMarked | 6 | Background | v1 | | FormatSplitUserKeysMarkedCompacted | 7 | Blocking | v1 | | FormatRangeKeys | 8 | No | v1 | | FormatMinTableFormatPebblev1 | 9 | No | v1 | | FormatPrePebblev1Marked | 10 | Background | v1 | | FormatSSTableValueBlocks | 12 | No | v1 | | FormatFlushableIngest | 13 | No | v1, v2, master | | FormatPrePebblev1MarkedCompacted | 14 | Blocking | v1, v2, master | | FormatDeleteSizedAndObsolete | 15 | No | v1, v2, master | | FormatVirtualSSTables | 16 | No | v1, v2, master | | FormatSyntheticPrefixSuffix | 17 | No | v2, master | | FormatFlushableIngestExcises | 18 | No | v2, master | | FormatColumnarBlocks | 19 | No | v2, master | 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/pebble@v1.1.3 db upgrade ``` For reference, the table below lists the range of supported Pebble format major versions for CockroachDB releases. | CockroachDB release | Earliest supported | Latest supported | |---------------------|------------------------------------|-----------------------------| | 20.1 through 21.1 | FormatMostCompatible | FormatMostCompatible | | 21.2 | FormatMostCompatible | FormatSetWithDelete | | 21.2 | FormatMostCompatible | FormatSetWithDelete | | 22.1 | FormatMostCompatible | FormatSplitUserKeysMarked | | 22.2 | FormatMostCompatible | FormatPrePebblev1Marked | | 23.1 | FormatSplitUserKeysMarkedCompacted | FormatFlushableIngest | | 23.2 | FormatPrePebblev1Marked | FormatVirtualSSTables | | 24.1 | FormatFlushableIngest | FormatSyntheticPrefixSuffix | | 24.2 | FormatVirtualSSTables | FormatSyntheticPrefixSuffix | | 24.3 | FormatSyntheticPrefixSuffix | FormatColumnarBlocks | ## Pedigree 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 ### Example Code ```go 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`) # arenaskl Fast, lock-free, arena-based Skiplist implementation in Go that supports iteration in both directions. ## Advantages 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 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 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 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`) # batchskl Fast, non-concurrent skiplist implementation in Go that supports forward and backward iteration. ## Limitations * 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 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 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`) 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”? 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... ``` - `` is an arbitrary identifier you chose. - `` is a zero-padded, 6-digit decimal. - `` is the new state you’re storing. For example, if your marker is named `foo`, you might see files like: ```text marker.foo.000001.alpha marker.foo.000002.beta ``` --- ## 2. High-level API ### ReadMarker(fs, dir, markerName) - 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) - Same as `ReadMarker`, but also opens `dir` for later syncing. - Returns a `*Marker` object plus the current value. --- ## 3. Core logic: parsing and scanning ```go 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 Once you have a `*Marker`, you can do two things: ### Move(newValue string) 1. Increment the internal `iter` counter. 2. Build a filename `marker...`. 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() 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 Imagine we start with an empty directory and markerName = `"task"`: ```shell $ 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 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 `` is long; Linux allows up to around 255 bytes per component. Keep your values short. --- ### Summary - **Naming scheme**: `marker..<6-digit-iter>.` - **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`) 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`](https://s3.console.aws.amazon.com/s3/buckets/pebble-benchmarks) S3 bucket. The data was trimmed so as to reduce the amount of data checked into version control, with something akin to: ```bash 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`) # 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](#perf) * [Blktrace](#blktrace) ## Perf 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](http://www.brendangregg.com/perf.html). 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 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 `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 ` 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 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: , ``` 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 `, 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 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 Ubuntu AWS installation: ``` sudo apt-get install blktrace ``` ## Usage ``` # 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: ``` + [] ``` 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`) # Memory Management ## Background 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`](https://golang.org/pkg/runtime/) environment variable or by calling [`debug.SetGCPercent`](https://golang.org/pkg/runtime/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 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 In order to find all of the cache value leaks, Pebble has a leak detection facility built on top of [`runtime.SetFinalizer`](https://golang.org/pkg/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`) # 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 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 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 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 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 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 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 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 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`) # 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](http://www.benstopford.com/2015/02/14/log-structured-merge-trees/) on the web, or try chapter 3 of [Designing Data-Intensive Applications](https://www.amazon.com/Designing-Data-Intensive-Applications-Reliable-Maintainable/dp/1449373321). 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](#internal-keys) * [Indexed Batches](#indexed-batches) * [Large Batches](#large-batches) * [Commit Pipeline](#commit-pipeline) * [Range Deletions](#range-deletions) * [Flush and Compaction Pacing](#flush-and-compaction-pacing) * [Write Throttling](#write-throttling) * [Other Differences](#other-differences) ## Internal Keys 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. ```c++ 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 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 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 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](#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 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](https://rocksdb.org/blog/2018/11/21/delete-range.html) 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 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](https://rocksdb.org/blog/2017/12/18/17-auto-tuned-rate-limiter.html) 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 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 * `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`) - 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](https://github.com/cockroachdb/cockroach/blob/master/docs/RFCS/20210825_mvcc_bulk_ops.md); detailed design draft for DeleteRange in internal [doc](https://docs.google.com/document/d/1ItxpitNwuaEnwv95RJORLCGuOczuS2y_GoM2ckJCnFs/edit#heading=h.x6oktstoeb9t)), 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 ### New `Comparer` requirements 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 This design introduces three new write operations: - `RangeKeySet([k1, k2), [optional suffix], )`: 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 `RangeKeySet`s 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. `RangeKeyDelete`s differ from `RangeKeyUnset`s, because the latter requires that the suffix matches and applies only to range keys. `RangeKeyDelete`s 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](https://github.com/cockroachdb/pebble/blob/e95e73745ce8a85d605ef311d29a6574db8ed3bf/internal/base/comparer.go#L69-L88), 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 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 `` 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 ### Write operations 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 `varstring`s. 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 Like all Pebble keys, `RangeKeySet`, `RangeKeyUnset` and `RangeKeyDelete` are assigned sequence numbers when committed. As described above, overlapping `RangeKeySet`s and `RangeKeyUnset`s 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 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 `RANGEDEL`s which span these two sstables which are discussed in the section on [improperly truncated RANGEDELS](https://github.com/cockroachdb/pebble/blob/master/docs/range_deletions.md#improperly-truncated-range-deletes). We manage to tolerate this for `RANGEDEL`s 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 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 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 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 #### 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 `RANGEDEL`s dropping both point and range keys. CockroachDB can issue `RANGEDEL`s 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`) - 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](https://github.com/cockroachdb/pebble/issues/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](https://github.com/cockroachdb/pebble/issues/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 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 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 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` The `sstable.TableFormat` enum is a `uint32` representation of the tuple `(magic number, format version). The current values are: ```go 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. ```go 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 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: ```go // 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 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](https://github.com/cockroachdb/cockroach/blob/20eaf0b415f1df361246804e5d1d80c7a20a8eb6/pkg/storage/sst_writer.go#L57) and [here](https://github.com/cockroachdb/cockroach/blob/20eaf0b415f1df361246804e5d1d80c7a20a8eb6/pkg/storage/sst_writer.go#L78)). 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 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`) - Feature Name: Flushable Ingested SSTable - Status: in-progress - Start Date: 2022-03-11 - Authors: Mufeez Amjad - RFC PR: [#1586](https://github.com/cockroachdb/pebble/pull/1586) - Pebble Issues: [#25](https://github.com/cockroachdb/pebble/issues/25) - Cockroach Issues: ## Summary 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 Currently, if any of the SSTs that need to be ingested have an overlap with a memtable, we [wait](https://github.com/cockroachdb/pebble/blob/56c5aebe151977964db7e464bb6c87ebd3451bd5/ingest.go#L671) 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 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 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 | +-------------+------------+--- ... ---+ ``` where`SeqNum` 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: ```go 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 Introduce a new flushable type: `ingestedSSTables`. ```go 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. ```go 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: ```go 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()`: ```go 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-flushing-logic-to-move-ssts-into-l0). #### 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 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. 2. Create a batch with the list of ingested SSTs. ```go 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 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`) - 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 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 `NewFileEntry`s 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 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 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 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 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 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`) - 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](https://github.com/cockroachdb/pebble/issues/918#issuecomment-1564714073), 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](https://github.com/cockroachdb/pebble/blob/3ef2e5b1f693dfbf78785e14f603a443af3c674b/compaction_picker.go#L919) for each level are all calculated to be <1 and thus no compactions are scheduled. - Observed in [this escalation](https://github.com/cockroachlabs/support/issues/2628) (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](https://github.com/facebook/rocksdb/wiki/Implement-Queue-Service-Using-RocksDB#reclaiming-space-of-deleted-items-faster). - We've seen this behavior multiple times with CockroachDB's implementation of the KV liveness range. - Observed in multiple escalations including [here](https://github.com/cockroachlabs/support/issues/2107) and [here](https://github.com/cockroachlabs/support/issues/2640) (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 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 **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](https://github.com/facebook/rocksdb/blob/main/include/rocksdb/utilities/table_properties_collectors.h#L53) and [ScyllaDB](https://enterprise.docs.scylladb.com/stable/kb/garbage-collection-ics.html) use this in combination with more complex strategies ### 2. More Granularity 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](https://github.com/facebook/rocksdb/blob/22fe23edc89e9842ed72b613de172cd80d3b00da/utilities/table_properties_collectors/compact_on_deletion_collector.cc#L33) - 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 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`](https://github.com/cockroachdb/pebble/blob/4981bd0e5e9538a032a4caf3a12d4571abb8c206/compaction_picker.go#L1324), 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 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`](https://github.com/cockroachdb/pebble/blob/master/table_stats.go#L606), 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](https://github.com/cockroachdb/pebble/pull/3790#issuecomment-2251439492). 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](https://github.com/cockroachdb/pebble/issues/918#issuecomment-1599478862) - 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`) { "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