cockroachdb / cockroachdb/pebble

db: lower-level gap heuristic

Open
#2,366 2 comments 0 reactions 0 assignees View on GitHub
A-storage T-storage
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.