Back to results
US 9,176,871 B1Granted
Garbage collection of chunks
Assigneeupthere, inc.
InventorBertrand Serlet
Life of this patent
Estimating the term…
Abstract
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.
Claims23
A method comprising:
- implementing a hierarchical file system that supports modifications using chunks stored in a content addressable storage system, wherein at least a portion of the chunks represents file content;
- wherein making a modification in the hierarchical file system comprises storing one or more new chunks in the content addressable storage system that represent the hierarchical file system structure after the modification;
- performing a garbage collection operation that reclaims stale chunks, within the content addressable storage system, that no longer reflect a current state of the hierarchical file system as of a first particular time due to one or more modifications in the hierarchical file system;
- wherein performing the garbage collection operation includes:
- during a trace phase of the garbage collection operation, performing one or more recursive touch-traversal operations to establish new last-touched timestamps for chunks visited during the recursive touch-traversal operations;
- wherein each of the one or more recursive touch-traversal operations is initiated at a distinct chunk that, as of a second particular time that is later than the first particular time, was a current root of a corresponding tree within the hierarchical file system;
- during the trace phase, determining whether to initiate a particular recursive touch-traversal operation at a particular chunk, which was the current root of a particular tree within the hierarchical file system as of the second particular time, based, at least in part, on a sub-tree-timestamp maintained for the particular tree;
- responsive to the sub-tree-timestamp of the particular tree being before the first particular time, initiating the particular recursive touch-traversal operation at the particular chunk;
- responsive to the sub-tree-timestamp of the particular tree being after the first particular time, performing the trace phase without initiating any recursive touch-traversal operation at the particular chunk;
- during a sweep phase, reclaiming chunks, within the content addressable storage system, that have last-touched timestamps that are before the first particular time;
- wherein the method is performed by one or more computing devices.
8 more elements
A method comprising:
- implementing a hierarchical file system that supports modifications using chunks stored in a content addressable storage system, wherein at least a portion of the chunks represents file content;
- wherein making a modification in the hierarchical the system comprises storing one or more new chunks in the content addressable storage system that represent the hierarchical file system structure after the modification;
- maintaining file-to-chunk mappings for the hierarchical file system in a name store;
- creating a plurality of snapshots of the name store, wherein each snapshot of the plurality of snapshots reflects the name store at a distinct point in time;
- performing a garbage collection operation that reclaims stale chunks, within the content addressable storage system, that no longer reflect a current state of the hierarchical file system as of a first particular time due to one or more modifications in the hierarchical file system;
- wherein performing the garbage collection operation includes:
- selecting a particular snapshot, of the plurality of snapshots, that reflects the name store as of a second particular time that is after the first particular time;
- during a trace phase of the garbage collection operation, using the particular snapshot to identify chunks that, as of the second particular time, were current roots of corresponding trees within the hierarchical file system;
- during the trace phase of the garbage collection operation, performing one or more recursive touch-traversal operations to establish new last-touched timestamps for chunks visited during the recursive touch-traversal operations;
- wherein each of the one or more recursive touch-traversal operations is initiated at a distinct chunk identified using the particular snapshot;
- during a sweep phase, reclaiming chunks, within the content addressable storage system, that have last-touched timestamps that are before the first particular time;
- wherein the method is performed by one or more computing devices.
9 more elements
One or more non-transitory computer-readable media storing instructions which, when executed by one or more processors, cause the one or more processors to perform a method comprising the steps of:
- implementing a hierarchical file system that supports modifications using chunks stored in a content addressable storage system, wherein at least a portion of the chunks represents file content;
- wherein making a modification in the hierarchical file system comprises storing one or more new chunks in the content addressable storage system that represent the hierarchical file system structure after the modification;
- performing a garbage collection operation that reclaims stale chunks, within the content addressable storage system, that no longer reflect a current state of the hierarchical file system as of a first particular time due to one or more modifications in the hierarchical file system;
- wherein performing the garbage collection operation includes:
- during a trace phase of the garbage collection operation, performing one or more recursive touch-traversal operations to establish new last-touched timestamps for chunks visited during the recursive touch-traversal operations;
- wherein each of the one or more recursive touch-traversal operations is initiated at a distinct chunk that, as of a second particular time that is later than the first particular time, was a current root of a corresponding tree within the hierarchical file system;
- during the trace phase, determining whether to initiate a particular recursive touch-traversal operation at a particular chunk, which was the current root of a particular tree within the hierarchical file system as of the second particular time, based, at least in part, on a sub-tree-timestamp maintained for the particular tree;
- responsive to the sub-tree-timestamp of the particular tree being before the first particular time, initiating the particular recursive touch-traversal operation at the particular chunk;
- responsive to the sub-tree-timestamp of the particular tree being after the first particular time, performing the trace phase without initiating any recursive touch-traversal operation at the particular chunk;
- during a sweep phase, reclaiming chunks, within the content addressable storage system, that have last-touched timestamps that are before the first particular time.
7 more elements
One or more non-transitory computer-readable media storing instructions which, when executed by one or more processors, cause the one or more processors to perform a method comprising the steps of:
- implementing a hierarchical file system that supports modifications using chunks stored in a content addressable storage system, wherein at least a portion of the chunks represents file content;
- wherein making a modification in the hierarchical file system comprises storing one or more new chunks in the content addressable storage system that represent the hierarchical file system structure after the modification;
- maintaining file-to-chunk mappings for the hierarchical file system in a name store;
- creating a plurality of snapshots of the name store, wherein each snapshot of the plurality of snapshots reflects the name store at a distinct point in time;
- performing a garbage collection operation that reclaims stale chunks, within the content addressable storage system, that no longer reflect a current state of the hierarchical file system as of a first particular time due to one or more modifications in the hierarchical file system;
- wherein performing the garbage collection operation includes:
- selecting a particular snapshot, of the plurality of snapshots, that reflects the name store as of a second particular time that is after the first particular time;
- during a trace phase of the garbage collection operation, using the particular snapshot to identify chunks that, as of the second particular time, were current roots of corresponding trees within the hierarchical file system;
- during the trace phase of the garbage collection operation, performing one or more recursive touch-traversal operations to establish new last-touched timestamps for chunks visited during the recursive touch-traversal operations;
- wherein each of the one or more recursive touch-traversal operations is initiated at a distinct chunk identified using the particular snapshot;
- and
- during a sweep phase, reclaiming chunks, within the content addressable storage system, that have last-touched timestamps that are before the first particular time.
9 more elements
Dependencies are inferred from the claim text.