greglook
Garbage collection
Because merkledag structures are persistent, over time there will be 'garbage' nodes that build up in the block store. There's a number of reasons that this might happen, but the most common is updating a ref with new versions of a structure over time. Keeping old versions around forever is generally not a viable storage strategy.
To keep the backing block stores clean, the library should offer a simple mark-and-sweep garbage collector. The algorithm should accept a set of nodes as the 'roots' of the graph and trace out all the reachable block ids based on the node links. Anything not reachable from these roots should be removed from the block store in the sweep phase.
It's probably a good idea to allow a grace period for new blocks being written by processes which have not yet updated the ref; in this case, the sweeping phase should be tuned to forgive unreachable blocks which are younger than some threshold age.
