GC old tombstones

[dgrnbrg]

We can safely delete tombstone entries when they are the oldest value known. This process can become a part of merging. During this time, it can also clean up the running keydir.

[dgrnbrg]

To clean up the running keydir, we can use (.remove chm k v), which is a conditional remove that would let us specify to remove only the GCed value, not a newer one.

[dgrnbrg]

We can implement this by making merge be 2 operations: small merge and big merge

• Small merge chooses the target files for the merge and copies all relevant keydir entries to new files, then deletes the old files in any order
• Big merge chooses all files up to certain id for the merge, and only copies non-tombstone keydir entries to new files, then deletes the old files from earliest id to latest

We will do small merges whenever the fragmentation threshold gets high enough. We can do big merges whenever the number of expired keys grows big or the size in memory of expired keys grows big. We can attach another field to KDEs which is :expired? so that we can track expired key count efficiently when merging.

[dgrnbrg]

It turns out that the way bitcask handles this is by marking each fully copied file with the setuid after all the data is copied out of it. Then, it periodically sweeps those files with the setuid bit set.