Another possible mechanism for doing GC at scale (a variation on Asynchronous Reconciliation in the article) in some file/object store, is doing a probabilistic mark and sweep using bloom filters. The mark phase can be done in parallel building many bloom filters for the files/objects found. Then the bloom filters are merged (or'ed together essentially) and then a parallel sweep phase can use the bloom filter to answ…
If you like big beautiful storage and probabilistic structures check out https://www.usenix.org/conference/osdi14/technical-sessions/... . The coho data folks ended up in AWS S3 a few years later.
Thanks! I hadn't seen it and it may come handy!