Merkle trees and build systems

GC with OSTree is indeed a problem with large numbers of refs (or really a large amount of data). The design was mostly focused on the base operating system case where this isn't a problem.

That said, there are a few tricks one can use, such as having multiple repositories, and then one could implement GC by pulling recently-used refs from one into a new repo (which is really just hardlinking, so pretty cheap), then delete the old repo and move it into place. We could probably add this as a primitive into OSTree itself - it'd make GC cost closer to O(data preserved) and not O(data). Could also amortize by having multiple repos that have different subsets of refs and prune them at different points, re-importing whatever canonical data as needed.

(There's a hugely interesting sub-topic here around whether OSTree is a *cache* of something like a .deb/rpm or whether it's canonical, i.e. your build system outputs it)