Support table compaction

[v0y4g3r]

What type of enhancement is this?

Performance

What does the enhancement do?

So far GreptimeDB supports flushing rows in memtable to SST files in level 0. But SST files in level 0 is not sorted in time bucket order, so retrieving rows in a given time range needs to scan all SST files in level 0. Just like other LSM tree based storage engines, we need to compact SST files in different levels to:

• merge insert/delete records with the same primary key;
• sort all rows in timestamp order and evenly distribute those rows to SST files in level 1 so that no SST file in level 1 contains intersecting time range;
• delete expired SST files according to TTL;
• we can intriduce compression and indexing tasks when compacting SST files in the future.

The RFC can be found at #939.

Implementation challenges

We need to implement those component:

• compaction scheduler (along with task control to limit performance impact to foreground queries) feat: compaction scheduler and rate limiter #947;
• compaction strategy: we can begin with file-num based strategy that trigger compaction as soon as the number of SST files in level 0 exceeds some threshold feat: L0 to L1 compaction strategy #964;
  • time bucket calculation: read time ranges of SST files in level 0 and calculate the proper time bucket for level 1 SST files so that data can be evenly distributed in level 1 SST files;
    track the referencer of SST files and only delete these SSTs when it's been marked as "deleted" and reference count is 0.
• table compaction task: use merged reader along with dedup reader to read rows from all SST files in level 0 feat: compaction reader and writer #972.
• integrate compaction components to datanode instance feat: compaction integration #997.

Future work

• We may break the snapshot read semantic when implementing compaction, since with the same sequence for snapshot read, the seceond read may find some rows are deleted because of compaction.
• Persist time window config into region manifest to ensure Level1's time window size remains consistent. Persist compaction time window to table manifest #1055
• Refactor region SST struct to hold an UUID as SST key to reduce overhead. Refactor region SST struct to hold an UUID as SST key to reduce overhead #1053
• purge SST files to reclaim disk space Implement Time-To-Live table attribute #601 ;
  • purge compacted SST files feat: file purger #1030;
  • purge expired SST files according to table TTL
    • issue Implement Time-To-Live table attribute #601
    • pull request feat: support table ttl #1052
• Support more compaction strategies
  • Time Window CompactionStrategy #1068

[killme2008]

we may break the snapshot read semantic when implementing compaction, since with the same sequence for snapshot read, the second read may find some rows are deleted because of compaction.

Do we have any solutions to fix this issue? Looks like it's impossible.

[waynexia]

Do we have any solutions to fix this issue? Looks like it's impossible.

Maybe we need to introduce some mechanism like MVCC for it, but I think it's not necessary to do so.

[v0y4g3r]

we may break the snapshot read semantic when implementing compaction, since with the same sequence for snapshot read, the second read may find some rows are deleted because of compaction.

Do we have any solutions to fix this issue? Looks like it's impossible.

We need to keep track of all SnapshotImpls that currently refering level 0 SST files, and postpone the deletion of compacted level 0 SST files until all created snapshot reads are finished.

[evenyag]

we may break the snapshot read semantic when implementing compaction, since with the same sequence for snapshot read, the second read may find some rows are deleted because of compaction.

I think this might not be a problem. Now we only support reading the latest data. In this case, we acquire a reference to a stable Version struct which references the old SSTs. But we need to make the file metadata reference counted and delete the file after no "read" referencing it.

Do we have any solutions to fix this issue?

Introduces snapshot like other dbs if we need a stable snapshot but also want to release the unused SSTs.

[killme2008]

I think we can close this issue. Open a new issue when we want to support other compaction features.