Compaction filters

[iczero]

Is your feature request related to a problem? Please describe.
Sometimes it is desired to have expiration for items in the database. For example, a session store where sessions expire, or a cache with simple expiry times. In such cases, deletion is not required to happen immediately, but it is still preferred to eventually get rid of the expired or stale data at some point.

Describe the solution you'd like
RocksDB allows the user to specify a compaction filter, but I am not sure if this idea would work in Fjall. The compaction filter can exclude k/v pairs during compaction, therefore deleting them.

Alternatively something else that can efficiently accomplish the same.

Describe alternatives you've considered

• Delete expired values when reading: works (and would be required even if such a feature were implemented) but requires a value to be read before it can be deleted. Stale values will still get compacted, which might be a waste of resources.
• Periodically scan the keyspace and delete expired values: requires scanning entire keyspace, probably less efficient than compaction filter.

Additional context
N/A

[iczero]

I may be able to work on this. Is it currently blocked on the 3.0 changes?

I was looking around a bit and I think this is relevant: https://github.com/fjall-rs/lsm-tree/blob/3.0.0/src/compaction/stream.rs. Please correct me if I am wrong.

[marvin-j97]

I may be able to work on this. Is it currently blocked on the 3.0 changes?

It would definitely good to base this on the 3.0.0 branch or even #157 (WIP).

I was looking around a bit and I think this is relevant: https://github.com/fjall-rs/lsm-tree/blob/3.0.0/src/compaction/stream.rs. Please correct me if I am wrong.

I would probably add it here:

lsm-tree/src/compaction/worker.rs

Line 329 in a4497f2

for (idx, item) in merge_iter.enumerate() {

in the loop to filter for KVs. There are two things to consider though:

• the GC watermark; we cannot get rid of KVs that have seqno > gc_watermark (called eviction_seqno there).
• Blobs could benefit from only filtering by key to avoid loading the blob (called FilterBlobByKey in RocksDB), but blobs are currently WIP in Automatic blob garbage collection #157
• in the blob PR, there is a callback in the compaction stream that gets called when KVs are dropped, that is required for the blog GC to work; when the compaction filter drops blob pointers it needs to call that callback somehow