facebook / facebook/rocksdb

Is in-place sstable truncation possible?

Open
#4,085 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
32.1k
Forks
6.9k
Avg merge
32m
Merged PRs (30d)
1

Description

The current compaction mechanisms require that whenever an `Ln->Ln+1` compaction occurs a compaction that involves table `T` at `Ln` will have to include any overlapping tables in `Ln+1`. For example, consider this simple LSM structure:

```
L1: g------------t
L2: a-----------m o----------z
```

If we're compacting `L1:[g-t]` to `L2`, we need to include `L2:[a-m]` and `L2:[o-z]` in the compaction. Failure to do so would result in a violation of the invariant that tables do not overlap within a level (except for `L0`, which is special).

The motivation for thinking about the base compaction mechanics is that we've been observing compactions in CockroachDB which involve gigabytes of data. The reason for these large compactions has been range tombstones (those issues are discussed elsewhere). This weekend I was thinking about the problem from a different direction. What if we could truncate `L1:[g-t]` in place?

Sstables are immutable, but the sstable metadata is not stored in the sstable itself but in the MANIFEST. Can we perform a compaction of `L1:[g-t]` to `L2` which only involves `L2:[o-z]`, resulting in the following LSM:

```
L1: g--------o
L2: a-----------m o----------z
```

The idea here is that the table `L1:[g-o]` would be the same on-disk file (i.e. the same file number) as `L1:[g-t]` but we would have updated the `FileMetaData` in the new version. Iterators would have to respect the sstable boundaries (I believe Get would automatically be handled correctly).

If I squint, this seems feasible. Are there practical difficulties involved? Has this previously been considered and discarded for some reason?

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.