cockroachdb / cockroachdb/pebble
db: lower-level gap heuristic
- Dominant language
- Go
- Stars
- 6k
- Forks
- 584
- Avg merge
- 16h 35m
- Merged PRs (30d)
- 5
Description
Consider a workload where the keyspaces a-f and u-z are write heavy, while the keyspace g-t is read only. Incoming writes to a-f and u-z keyspaces can easily be included in the same sstable, spanning the read-only g-t keyspace. These sstables unnecessarily increase the read amplification of reads in the g-t keyspace.
```
L2 [─•─────────────•──────────────────────────────────────────•─•─] [•──••─•─••─]
L3 [──•────•────•──•] [─••─────────••]
L4 [•──•─•] [•──•────────────────────────────────────────────•──•─•─] [─••───]
L5 [••] [••] [•─•─•────────────────────────────────────────────•] [••─•─•─] [•]
L6 [•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•]
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
```
Ideally, we'd avoid constructing sstables spanning the read-only region so that only the regions receiving writes suffer read-amp:
```
L2 [─•─────────────•] [•─•─] [•──••─•─••─]
L3 [──•────•────•──•] [─••─────────••]
L4 [•──•─•] [•──•] [•──•─•─] [─••───]
L5 [••] [••] [•─•─•] [•] [••─•─•─] [•]
L6 [•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•][•]
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
```
User-defined "guards" #517 are one approach to this problem, but shift the compaction-output splitting problem to the user. Setting too aggressive of guards can result in many little files in the LSM.
There might be an opportunity for a heuristic that incorporates lower level file boundaries into the compaction iterator's `frontiers` type, and notices when the next key skips over a large gap in lower levels. When a large enough gap is encountered, the output can be split early.
See cockroachdb/cockroach#93427 for another approach at reducing the effective read-amp in this kind of scenario.
Jira issue: PEBBLE-202
Epic CRDB-40361
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by reading the compaction iterator's frontiers type and the discussion of user-defined guards in #517. Compare the proposed lower-level gap heuristic with cockroachdb/cockroach#93427. Done means a reviewed approach that avoids spanning large lower-level gaps without producing excessive output fragmentation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go
- Domain
- database, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100