The Bupstash Garbage Collector | Hacker News Reader

The Bupstash Garbage Collector

acha.ninja

I wrote something similar, except using sequential IDs instead of being content addressed. With immutable objects, forward references aren't possible.

This made the GC algorithm concurrent for free.

You'd take a lock on initiating a GC to record the roots, then release it. From that point onwards, you can take your time doing a mark and sweep on the database, only sweeping objects that have an id less than the highest of your root objects.

It also made generational collection pretty easy. If you bound your marking and sweeping with an arbitrary lower limit in addition to the higher limit from the roots, it would collect correctly within that range and waste no energy exploring past it.

I used this to aggressively clean up new objects without having to wait for a full GC. The project was storing Clojure style persistent hash maps on disk for real time log analysis, approximately 100gb or so.

Unfortunately, none of these tricks would apply to a CAS system. I do wonder if it would help running the speculative collection twice before taking out the lock, though.

> With immutable objects, forward references aren't possible.

This aligns well with a tree of backup objects (immutable append-only acyclic graph data structure) but this approach wouldn't work for general programming, right?

My understanding is that LISP's letrec and the equivalent in other functional languages, means that even seemingly immutable abstractions aren't really immutable from the point of view of the GC, and cycles are a possibility. I don't think it would be possible to properly implement Haskell using ordinary reference-counting, for instance. The purity of the language wouldn't save you from reference-cycles.

Right, that's true that it's possible to "tie the knot" with laziness and build circular or self references in functional languages. I didn't mean to make a claim that extended past the limits of the system I built and it's important to note that.

> that's true that it's possible to "tie the knot" with laziness and build circular or self references in functional languages

I wonder if it would be possible to construct a practical functional language that never does so. I imagine not.

> I didn't mean to make a claim that extended past the limits of the system I built

I don't think you did, I was just wondering how much further the idea could be taken.

If you can be guaranteed to have no forward references, wouldn't this mean that you can also not have cycles and therefore could make do with a much simpler refcounting setup?

You could definitely do it with refcounting, but I'm not sure it's simpler when not in memory.

You need to be able to defer the cost of freeing objects, otherwise updating a root object will randomly be very expensive as you free 20gb of garbage before acknowledging the write.

This deferred queue is going to need to live in the database, and be processed in atomic chunks that pop an item off the queue, update the refcounts, and add any further work items. Otherwise if the power goes out, your refcounts are left in who knows what state.

That doesn't exactly sound hard, but the system I built was pretty simple too. And my preference leans towards not mutating object metadata after it's been written to.

False positives from Bloom filters could be decreased exponentially at every GC operation (I'm not sure how quickly, but more or less for free) by using a new key for the Bloom filter hashes (e.g. the current timestamp) so that every block that was retained as a false positive last time is aggregated with different pseudorandom sets of other blocks, with a high probability of getting lucky.

Ohh thanks, this is also a good idea.

The author may want to consider cuckoo filters over bloom filters. IIRC, there are versions of them that allow for dynamic resizing.

Very interesting article. I have to wonder how much benefit a user would get from letting parts of the backup run concurrently with other operations. Aren’t backups usually just run relatively infrequently on a fixed, automated schedule?

Cuckoo filters sound interesting, I will definitely investigate further, thanks!

> I have to wonder how much benefit a user would get from letting parts of the backup run concurrently with other operations. Aren’t backups usually just run relatively infrequently on a fixed, automated schedule?

This is good point, i think it depends a lot on the repository size and storage latency. Some other similar backup tools can take many hours to do a garbage collection on a huge repository, so I'm trying to avoid that if I can. In the end it hasn't been a huge complexity burden and I hope I can keep it that way.

> Aren’t backups usually just run relatively infrequently on a fixed, automated schedule?

not familiar with this system, but for large setups, having the maintenance operations block usage can reduce the backup window enough that it impacts your desired scheduling pattern

Reply on news.ycombinator.com