Range Tombstone Conversion: Faster Scans Over Long Runs of Deletes (opens in new tab)

RocksDB has historically been known for poor performance when tombstones accumulate. This has become a common problem within Meta, and the community has raised it as well. Here, we introduce an optimization that attempts to convert contiguous tombstones into a range tombstone during scans. As a result, instead of skipping through N tombstones, we only need to skip through a single range tombstone. Background: point tombstones and range tombstones RocksDB is an LSM-tree, so a delete does not e...