RFC: js-ipfs Garbage Collection

[dirkmc]

This issue is to discuss how best to implement Garbage Collection in js-ipfs

The go-ipfs Garbage Collector

We would like to learn from the experience of go-ipfs when building a Garbage Collector for js-ipfs.

Triggers

• Manual: ipfs repo gc
• Daemon flag: --enable-gc causes GC to run
  • only if storage exceeds StorageGCWatermark% of StorageMax (90% of 10G by default)
  • periodically every GCPeriod (1 hour by default)
  • when a file is added to unixfs (currently disabled)

Algorithm

Source code

// GC performs a mark and sweep garbage collection of the blocks in the blockstore
// first, it creates a 'marked' set and adds to it the following:
// - all recursively pinned blocks, plus all of their descendants (recursively)
// - bestEffortRoots, plus all of its descendants (recursively)
// - all directly pinned blocks
// - all blocks utilized internally by the pinner
//
// The routine then iterates over every block in the blockstore and
// deletes any block that is not found in the marked set.
func GC(ctx context.Context, bs bstore.GCBlockstore, dstor dstore.Datastore, pn pin.Pinner, bestEffortRoots []cid.Cid) <-chan Result {

Note that bestEffortRoutes currently only contains the MFS root

Proposal for a js-ipfs Garbage Collector

Requirements

• Manually Garbage Collect all blocks that are not pinned, not in MFS and not used internally
  ipfs repo gc: mark and sweep - remove all unreachable blocks
• Passively Garbage Collect old blocks when new blocks are added to the blockstore
  ipfs daemon --enable-gc causes GC to run
  • whenever a block is added to blockstore
  • only if storage exceeds StorageGCWatermark% of StorageMax (90% of 10G by default)
  • remove only excess blocks, least recently accessed blocks first

Algorithm for passive GC

• Track reference counts using persistent reference counting algorithm
  • reference count increment:
    • each time a block is pinned directly or indirectly
      • pinner must ensure that multiple pins of same hash are only registered once
    • on mfs add
  • reference count decrement:
    • each time a block is unpinned directly or indirectly
    • on mfs rm
  • maintain last block access time

[dirkmc]

@Stebalien @magik6k could I ask for your input on the above proposal, and to correct anything I misunderstood about how go GC works

@alanshaw suggested using a tiered datastore. It would track

• references to a block
• the last access time of a block
• which blocks are used by GC internally

Please CC anyone else who you think might have knowledge of this area

[Stebalien]

Overall, that looks like a good proposal to me.

Note: ipfs repo gc doesn't have to use mark and sweep assuming you have passive reference counts.

maintain last block access time

That may not scale well. We can make this approximate ("accessed within the last day") to reduce the overhead of repeated access but this will still turn reads into writes.

remove only excess blocks, least recently accessed blocks first

Ideally, this would use a combination of frequency and recency.

[dirkmc]

Note: ipfs repo gc doesn't have to use mark and sweep assuming you have passive reference counts.

@Stebalien I was thinking that to minimize overhead I wouldn't maintain reference counts for blocks that are not pinned and not in MFS. Because ipfs repo gc is triggered manually it seems less of a problem for it to stop the world. Based on your experience with go-ipfs, which approach would you recommend for ipfs repo gc between mark-and-sweep (with less overhead) vs passive reference counts (faster but more overhead)?

That may not scale well. We can make this approximate ("accessed within the last day") to reduce the overhead of repeated access but this will still turn reads into writes.

You're right, scaling will be a challenge, even just for reference counts. A couple of ideas off the top of my head:

1. GC runs in a background process

• Batch updates to reference counts / last access
• GC runs continuously but
  • checks these in-memory queued updates in addition to persisted reference count / last access information
  • writes batches every N ref count changes and P period of time
• If there is a crash
  • reference counts can be re-calculated
  • last access is just a heuristic for caching so it's not imperative that it be recoverable

2. Move GC into datastore-interface

• Datastore itself probably has access to metadata like file access time
• May simplify accounting

[alanshaw]

remove only excess blocks, least recently accessed blocks first

We should ensure that a block sticks around for an hour at minimum even if not accessed. This allows us to manage expecations on how long data will persist on a preload node/gateway.

Access time would really help to more intelligently clean up blocks, ideally we wouldn't collect a block that is often accessed but not pinned. However, storing creation time instead would at least allow us to clean up blocks not pinned and older than an hour without writing on read.

on mfs add

Remember it's basically any MFS command that you'd need to recalc references and that when you make changes anywhere in the MFS tree you propogate all the way back to the root.

Datastore itself probably has access to metadata like file access time

I'm sure you know but the datastore is pluggable - not everything is stored as a file - s3, url, in memory.

---

I would really love to have passive GC in JS IPFS. Personally I'd focus on the minimum viable (stop the world) first and then when you have that working you'll have a better idea of what's possible or not and then you can move on to a more advanced algorithm.

[Stebalien]

I was thinking that to minimize overhead I wouldn't maintain reference counts for blocks that are not pinned and not in MFS.

Unless I'm mistaken, we shouldn't need to maintain reference counts for un-pinned blocks regardless. How does passive GC differ from active ipfs repo gc in this case?

Batch updates to reference counts / last access
...
reference counts can be re-calculated

True. For reference counts, we could also try some kind of write-ahead log. That should be pretty easy to maintain without too much overhead (one more write per block).

Move GC into datastore-interface

I'm not sure if the datastore has enough information for this. In go, at least, the datastore just deals with blobs of data and knows nothing about IPLD, references, etc.

---

@alanshaw

We should ensure that a block sticks around for an hour at minimum even if not accessed. This allows us to manage expecations on how long data will persist on a preload node/gateway.

We should definitely make some configurable grace period but, IMO, we should set this to 0 on our gateways. Users shouldn't expect us to store stuff for them.

However, storing creation time instead would at least allow us to clean up blocks not pinned and older than an hour without writing on read.

We'd probably want both: sparse access time updates (i.e., record an access every hour) and a creation date. We can reduce the frequency of access time updates as the content ages.

My rational is that data is usually ephemeral or permanent. The longer data sticks around, the longer it's likely to stick around so we don't want to just remove old data.

Remember it's basically any MFS command that you'd need to recalc references and that when you make changes anywhere in the MFS tree you propogate all the way back to the root.

We can do this lazily on GC.

I would really love to have passive GC in JS IPFS. Personally I'd focus on the minimum viable (stop the world) first and then when you have that working you'll have a better idea of what's possible or not and then you can move on to a more advanced algorithm.

Yeah, that's probably the best approach. I'd just keep alternatives in mind before over-optimizing that approach.

[dirkmc]

Unless I'm mistaken, we shouldn't need to maintain reference counts for un-pinned blocks regardless. How does passive GC differ from active ipfs repo gc in this case?

You're right I don't think we need to maintain reference counts for blocks that are not pinned and not in MFS. If they are pinned or in MFS we will need to, because for example a block could be part of a file in MFS and also part of another file that's pinned.

Passive GC differs from active, manually run GC in that

• it is triggered when a block is added to the blockstore (if we're over the GC highwater mark)
• it only removes enough blocks to drop below the GC highwater mark
• it doesn't stop the world, it just removes the most eligible blocks for deletion

For reference counts, we could also try some kind of write-ahead log

I think that's a good idea 👍

I'd focus on the minimum viable (stop the world) first

Sounds like the consensus is to implement stop-the-world mark and sweep first, as we'll need it anyway, and then look at adding a more sophisticated reference counting algorithm that takes into account creation time and last access time. Does that sound right?

[dirkmc]

Unless I'm mistaken, we shouldn't need to maintain reference counts for un-pinned blocks regardless. How does passive GC differ from active ipfs repo gc in this case?

Sorry @Stebalien I just realized what you meant - you're saying that if we're already reference counting we don't need to mark and sweep, we just remove all blocks that are not reference counted, is that right?

If that's the case then maybe it does make sense to skip the mark and sweep implementation, and go straight for the more sophisticated implementation with reference counting. Thoughts @alanshaw?

[Stebalien]

That's what I meant however, going the simpler route first is probably still the better solution. On the other hand, that depends on how pressing fixing this is.