Granted Patent B1

US 9,176,871 · App. 13/760,945 · Granted Nov 3, 2015

Abstract

Claims (103)

1. 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.

2. The method of claim 1 further comprising:

prior to performing the garbage collection operation, performing a first recursive touch-traversal operation that starts at the particular chunk;

in response to the first recursive touch-traversal operation being completed for the particular tree, storing a cache entry for the particular chunk;

wherein the cache entry indicates the last-touched timestamp assigned to the particular chunk during the first recursive touch-traversal operation; and

wherein the step of determining whether to initiate the particular recursive touch-traversal operation is based on the last-touched timestamp indicated in the cache entry.

3. The method of claim 2 , wherein:

the cache entry is one of a plurality of cache entries in a cache;

each cache entry, of the plurality of cache entries:

was added to the cache in response to a recursive touch-traversal operation touching all chunks in a corresponding tree or sub-tree of the hierarchical file system;

identifies the chunk that is the root of the corresponding tree of sub-tree; and

includes a sub-tree-timestamp that is the same as or earlier than the last-touched timestamp of any chunk of the corresponding tree or sub-tree.

4. The method of claim 2 wherein the first recursive touch-traversal operation is a touch-traversal operation that is performed pro-actively independent of any sweep phase operation.

5. The method of claim 4 wherein initiation of the first recursive touch-traversal operation was triggered, at least in part, based on how much time had passed since performance of a previous pro-actively performed touch-traversal operation.

6. The method of claim 4 wherein initiation of the first recursive touch-traversal operation was triggered, at least in part, based on system conditions.

7. The method of claim 1 further comprising:

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;

selecting a particular snapshot, of the plurality of snapshots, that reflects the name store as of the second particular time; and

during the 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.

8. The method of claim 7 wherein:

the plurality of snapshots include one or more full snapshots and one or more incremental snapshots; and

the method further comprises creating the particular snapshot by combining a full snapshot with at least one incremental snapshot made subsequent to the full snapshot.

9. The method of claim 1 wherein at least one chunk belongs to multiple distinct trees within the hierarchical file system.

10. 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.

11. The method of claim 10 wherein:

the plurality of snapshots include one or more full snapshots and one or more incremental snapshots;

the method further comprises creating the particular snapshot by combining a full snapshot with at least one incremental snapshot made subsequent to the full snapshot; and

the at least one incremental snapshot includes an incremental snapshot associated with the second particular time.

12. The method of claim 10 further comprising allowing updates to be made to the hierarchical file system during the trace phase.

13. 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.

14. The one or more non-transitory computer-readable media of claim 13 , wherein the method further comprises:

prior to performing the garbage collection operation, performing a first recursive touch-traversal operation that starts at the particular chunk;

in response to the first recursive touch-traversal operation being completed for the particular tree, storing a cache entry for the particular chunk;

wherein the cache entry indicates the last-touched timestamp assigned to the particular chunk during the first recursive touch-traversal operation; and

wherein the step of determining whether to initiate the particular recursive touch-traversal operation is based on the last-touched timestamp indicated in the cache entry.

15. The one or more non-transitory computer-readable media of claim 14 , wherein:

the cache entry is one of a plurality of cache entries in a cache;

each cache entry, of the plurality of cache entries:

was added to the cache in response to a recursive touch-traversal operation touching all chunks in a corresponding tree or sub-tree of the hierarchical file system;

identifies the chunk that is the root of the corresponding tree of sub-tree; and

includes a sub-tree-timestamp that is the same as or earlier than the last-touched timestamp of any chunk of the corresponding tree or sub-tree.

16. The one or more non-transitory computer-readable media of claim 14 wherein the first recursive touch-traversal operation is a touch-traversal operation that is performed pro-actively independent of any sweep phase operation.

17. The one or more non-transitory computer-readable media of claim 16 wherein initiation of the first recursive touch-traversal operation was triggered, at least in part, based on how much time had passed since performance of a previous pro-actively performed touch-traversal operation.

18. The one or more non-transitory computer-readable media of claim 16 wherein initiation of the first recursive touch-traversal operation was triggered, at least in part, based on system conditions.

19. The one or more non-transitory computer-readable media of claim 13 wherein the method further comprises:

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;

selecting a particular snapshot, of the plurality of snapshots, that reflects the name store as of the second particular time; and

during the 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.

20. The one or more non-transitory computer-readable media of claim 19 wherein:

the plurality of snapshots include one or more full snapshots and one or more incremental snapshots; and

the method further comprises creating the particular snapshot by combining a full snapshot with at least one incremental snapshot made subsequent to the full snapshot.

21. 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.

22. The one or more non-transitory computer-readable media of claim 21 wherein:

the plurality of snapshots include one or more full snapshots and one or more incremental snapshots;

the method further comprises creating the particular snapshot by combining a full snapshot with at least one incremental snapshot made subsequent to the full snapshot; and

the at least one incremental snapshot includes an incremental snapshot associated with the second particular time.

23. The one or more non-transitory computer-readable media of claim 21 wherein the method further comprises allowing updates to be made to the hierarchical file system during the trace phase.

Assignments (6)