cockroachdb / cockroachdb/pebble
compaction: apply higher-level range deletions
- Dominant language
- Go
- Stars
- 6k
- Forks
- 584
- Avg merge
- 16h 35m
- Merged PRs (30d)
- 5
Description
Motivated by cockroachlabs/support#1788, although RCA is still underway. Informs #1793.
In CockroachDB, most operations are performed within the bounds of a replica, including garbage collection and replica removal. This means the broadest range tombstones we observe are bounded by replica bounds. With a default max range size of 512 MB and a L6 target file size of 128 MB, it's expected that a substantial portion of a range's data exists in sstables that contain data from other ranges too. This limits the effectiveness of delete-only compactions, since a delete-only compaction can only trigger if an sstable is wholly contained by a single file's range tombstones.
Replicas may be processed (by garbage collection, decommissioning, etc) in an arbitrary order that doesn't match key order. Range deletion compaction heuristics can result in some tombstones descending the LSM while adjacent or proximate range tombstones are committed but exist within higher levels of the LSM. A compaction in a lower level of the LSM may unnecessarily rewrite data that's already been deleted but the deleting tombstone is still within a higher level. It would save write amplification and CPU to skip over these deleted keys if the lower-level compaction knew that they were deleted.
One idea: Currently whenever a file containing range tombstones is completed, we already estimate the disk space beneath the file's range tombstones in order to inform compaction heuristics and potentially schedule delete-only compactions. While performing this computation, if a substantial portion of a lower-level file's disk space is deleted by a tombstone, we could mark an indicator bit on the lower-level file's `fileMetadata`. Then, when a compaction is triggered, we check all inputs' indicator bits. For any files with marked bits, we examine overlapping files in higher levels and open range deletion iterators into any files containing range deletions. During compaction, we allow these range deletions to elide keys but do not write them to output files.
Jira issue: PEBBLE-144
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.