cockroachdb / cockroachdb/pebble

compaction: apply higher-level range deletions

Open
#1,961 2 comments 0 reactions 0 assignees View on GitHub
A-storage C-performance T-storage
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.