Datastore Garbage Collection

[vyzo]

We currently have no mechanism for deleting objects from the datastore; this is partly by design, as we want the datastore to behave as an immutable append-only store, and partly by implementation constraints as tracking objects in the datastore is expensive (storage cost, performance effects on the ingestion critical path).

Nonetheless, we do need a mechanism for pruning the local datastore, for example when an operator decides to unmerge some large dataset.

Here are two possible approaches:

• Directly track all object deletions and at GC time iterate through the statements in StatementDB to find unreferenced objects and delete them. The downside is that we need to track object deletions, which has storage and complexity cost. It's also not clear if there will be any space saving in the datastore, at least not without compaction.
• Use a semi-space garbage collection. This is the superior approach in terms of implementation simplicity and also most effective pruning of the datastore. With the semi space approach, at GC we create a new rocks db datastore open for bulk load; We then iterate through statements in the db, and copy all referenced objects from the current datastore the new space. When we are done, we compact the new datastore and delete the old one. The downside is that it requires free space in the file system for the copy, which may not be feasible for capped nodes. This may be remedied by deleting copied objects from the old datastore, and compacting it at regular intervals, although this adds complexity and has the same caveats about deletions effecting actual datastore size.

[parkan]

I really like approach 2, though another downside is that this requires complete write lock for the full run (or else a very clever way of handling implications of writes) and cannot be done piecemeal.

[vyzo]

There is also the direct approach of iterating through the datastore, but this depends on the effect of OptimizeForPointLookup on iterators.

It's not clear if they don't work at all, they return keys out of order, or they work slowly. But if we do have working iterators (eg with out of order traversal), we can then use a third approach: go through the statements in the db to find all referenced objects, and then iterate through the datastore to find all unreferenced objects, which are then deleted (it's unclear if deletion is possible while iterating), followed by datastore compaction.

[parkan]

@vyzo I think this is basically the approach that the IPFS GC process takes