US Patent 9176871 Garbage collection of chunks

Various techniques are provided for performing garbage collection in a chunk store that is being used to implement a hierarchical file system. In general, the techniques involve a “trace” phase in which all chunks that correspond to current versions of files are marked, and then a sweep phase in which all chunks that were not marked during the trace phase are reclaimed. Various techniques are also described for using snapshots to avoid the need to halt operations on the file system while the trace phase is being performed. In addition, techniques are provided for using a cache of last-touched timestamps to avoid the need to mark all current chunks in each trace phase.