cockroachdb / cockroachdb/pebble

db: specialize ingest for excise by excising from memtables

Open
#3,038 0 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

This relates to https://github.com/cockroachdb/pebble/issues/2676, but takes a different approach.

Flushable ingest has not solved all our ingest problems.
- It avoids latency hiccups for concurrent writes. But, like regular ingest, it results in flushing of small memtables (see the effect mentioned in https://github.com/cockroachdb/cockroach/issues/104862#issuecomment-1599602996 where snapshot application is happening due to merges). The most common reason that there is memtable overlap is that HardState etc. is written for uninitialized replicas before the ingest (there are ways to address this in the KV layer, but it is messy -- see https://github.com/cockroachdb/cockroach/issues/99273).
- We can't currently use it when doing `IngestAndExcise`. Using this with `IngestAndExcise` will possibly require constructing a stack of iters above the memtables consisting (from lower to higher) a rangedel for the excise, up to 2 levels for the shared ssts, up to 1 level for the local sst. This adds more complexity to flushable ingests, and transiently causes higher read amp.

A different approach would be to ingest into the appropriate level immediately, by excising from the memtables. Like flushable ingest, it would avoid latency hiccups for concurrent writes, and ingests won't need to wait. Additionally, it would not create small memtables, or transiently increase read amp.

All ingests that excise in CockroachDB logically look like the following:

```
-l-- -l-- -l-- ----l-----
-rd- -rd- -rd- ----s-----
----s-----
-rangedel-
```

where rd is a rangedel, and the l is a local sst and s is a shared sst. The rd rangedels are “special” in that they must also be included in the corresponding sst. The rightmost span is the “global key” span that contains most of the data: when the shared ssts are absent, the l sst may also contain a rangedel, but it is not required. The rangedels span the full width of each sst. The ssts on the left are typically very small, and we could model those as a batch instead if we had an atomic IngestAndExciseAndApplyBatch operation offered by Pebble (which is possibly more complicated than what is outlined here).

We sketch the approach at a very high level.

The rangedels all represent key spans to be excised.

Simpler case: there is no ongoing flush that overlaps with these excised key spans
- Record the spans to be excised in a fragmented rangedel data-structure that must be merged with memtables (but not with ssts) when doing flush reads or user-facing reads. The seqnum of these spans will decide which points in the memtables are deleted, i.e., we are not creating a new memtable and using levels to decide what the rangedel deletes.
- Create and apply a version edit that
- virtualizes ssts to do the excising for only the large global span (we could also excise for the smaller spans but that is likely worse due to creation of small virtual ssts).
- adds the ingested ssts
- records the excise spans and their seqnum so that they can be applied to the memtables that have not yet flushed (for crash recovery).

Less simple case: There is an ongoing flush that overlaps with these excised key spans. Flushes are performance sensitive and we do not want to fail this flush.
We tell the ongoing flush that it should excise these spans from its output ssts when it is done (we could also make this change for ongoing compactions, instead of failing them as we currently do). NB: even the small key spans need to have this excising done. In the CockroachDB context consider some cases:
- The HardState of an uninitialized range was being flushed: one of the small ssts will get split into two virtual ssts.
- The HardState of the uninitialized range is in a mutable memtable (common case): no sst from the ongoing flush will overlap.
- Applying a snapshot to an already initialized range, and the ongoing flush was flushing changes to the state machine: up to 4 key spans may overlap, corresponding to the RangeAppliedStateKey, raft state (log and HardState), lock table, global key space. This worst case is not bad, and should not be common either.

Jira issue: PEBBLE-89

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.