Maintaining and using a cache of child-to-parent mappings in a content-addressable storage system

1. A method comprising:

maintaining a cache of child-to-parent mappings;

wherein each child-to-parent mapping corresponds to a particular chunk in a hierarchy of chunks stored in a content-addressable storage system, wherein the content-addressable storage system allows retrieval of items based on data that is generated from content of the items, and maps the particular chunk to a parent chunk in the hierarchy of chunks;

wherein the hierarchy of chunks includes a first root chunk associated with a first file system volume;

in response to a change to the file system volume that causes associating a new root chunk with the first file system volume, updating the cache by adding one or more first child-to-parent mappings based on traversing at least a portion of a current file system hierarchy from the new root chunk, and removing one or more second child-to-parent mappings based on traversing at least a portion of a prior file system hierarchy from the first root chunk.

2. The method of claim 1 , wherein updating the cache comprises:

(a) establishing the new root chunk as a current parent chunk;

(b) for each child chunk of the current parent chunk, performing the steps of:

(b1) if the cache does not contain a child-to-parent mapping that maps the child chunk to the current parent chunk, adding this child-to-parent mapping to the cache;

(b2) if the cache did not contain any child-to-parent mapping that maps the child chunk to any chunk before step (b1), then performing step (b) with the child chunk established as the current parent chunk;

(c) establishing the first root chunk as the current parent chunk;

(d) for each child chunk of the current parent chunk, performing the steps of:

(d1) removing from the cache a child-to-parent mapping that maps the child chunk to the current parent chunk; and

(d2) if the cache no longer contains any child-to-parent mappings that map the child chunk to any chunk, then performing step (d) with the child chunk established as the current parent chunk.

3. The method of claim 1 , further comprising:

receiving a specific hash value;

obtaining a specific chunk based on the specific hash value, wherein the specific chunk corresponds to a file;

when the file is modified, causing the modified file to be saved in the file system, wherein saving the modified file in the first file system volume comprises:

storing at least one new chunk in the content-addressable chunk store based on the modified file;

determining, based on the cache of child-to-parent mappings, at least one ancestor chunk comprising the first root chunk;

generating at least one new parent chunk based on the at least one ancestor chunk and the new chunk, wherein the at least one new parent chunk includes the new root chunk.

4. The method of claim 3 , wherein the specific hash value is received based on a search of an index of one or more chunks stored in the content-addressable storage system.

5. The method of claim 1 , wherein, for a particular child chunk corresponding to multiple child-to-parent mappings in the cache of child-to-parent mappings, the multiple child-to-parent mappings are stored as one hash-to-hash-set entry.

6. The method of claim 1 , wherein the cache is stored as at least one chunk in the content-addressable storage system.

7. The method of claim 1 , further comprising:

based on the one or more first child-to-parent mappings added, generating a list of added chunks added to the hierarchy of chunks;

based on the one or more second child-to-parent mappings removed, generating a list of removed chunks removed from the hierarchy of chunks.

8. The method of claim 7 , further comprising:

updating a file system size of the first file system volume based on the list of added chunks and the list of removed chunks.

9. The method of claim 7 , further comprising updating a local cache of non-payload chunks of the first file system volume based on the list of added chunks and the list of removed chunks.

10. The method of claim 7 , further comprising updating an index of one or more chunks stored in the content-addressable storage system based on the list of added chunks and the list of removed chunks.

11. A non-transitory computer-readable medium storing instructions which, when executed by one or more processors, cause the one or more processors to carry out:

maintaining a cache of child-to-parent mappings;

wherein each child-to-parent mapping corresponds to a particular chunk in a hierarchy of chunks stored in a content-addressable storage system, wherein the content-addressable storage system allows retrieval of items based on data that is generated from content of the items, and maps the particular chunk to a parent chunk in the hierarchy of chunks;

wherein the hierarchy of chunks includes a first root chunk associated with a first file system volume;

in response to a change to the first file system volume that causes associating a new root chunk with the first file system volume, updating the cache by adding one or more first child-to-parent mappings based on traversing at least a portion of a current file system hierarchy from the new root chunk, and removing one or more second child-to-parent mappings based on traversing at least a portion of a prior file system hierarchy from the first root chunk.

12. The non-transitory computer-readable medium of claim 11 , wherein updating the cache comprises:

(a) establishing the new root chunk as a current parent chunk;

(b) for each child chunk of the current parent chunk, performing the steps of:

(b1) if the cache does not contain a child-to-parent mapping that maps the child chunk to the current parent chunk, adding this child-to-parent mapping to the cache;

(b2) if the cache did not contain any child-to-parent mapping that maps the child chunk to any chunk before step (b1), then performing step (b) with the child chunk established as the current parent chunk;

(c) establishing the first root chunk as the current parent chunk;

(d) for each child chunk of the current parent chunk, performing the steps of:

(d1) removing from the cache a child-to-parent mapping that maps the child chunk to the current parent chunk; and

(d2) if the cache no longer contains any child-to-parent mappings that map the child chunk to any chunk, then performing step (d) with the child chunk established as the current parent chunk.

13. The non-transitory computer-readable medium of claim 11 , wherein the instructions further cause the one or more processors to carry out:

receiving a specific hash value;

obtaining a specific chunk based on the specific hash value, wherein the specific chunk corresponds to a file;

when the file is modified, causing the modified file to be saved in the file system, wherein saving the modified file in the first file system volume comprises:

storing at least one new chunk in the content-addressable chunk store based on the modified file;

determining, based on the cache of child-to-parent mappings, at least one ancestor chunk comprising the first root chunk;

generating at least one new parent chunk based on the at least one ancestor chunk and the new chunk, wherein the at least one new parent chunk includes the new root chunk.

14. The non-transitory computer-readable medium of claim 13 , wherein the specific hash value is received based on a search of an index of one or more chunks stored in the content-addressable storage system.

15. The non-transitory computer-readable medium of claim 11 , wherein, for a particular child chunk corresponding to multiple child-to-parent mappings in the cache of child-to-parent mappings, the multiple child-to-parent mappings are stored as one hash-to-hash-set entry.

16. The non-transitory computer-readable medium of claim 11 , wherein the cache is stored as at least one chunk in the content-addressable storage system.

17. The non-transitory computer-readable medium of claim 11 , wherein the instructions further cause the one or more processors to carry out:

based on the one or more first child-to-parent mappings added, generating a list of added chunks added to the hierarchy of chunks;

based on the one or more second child-to-parent mappings removed, generating a list of removed chunks removed from the hierarchy of chunks.

18. The non-transitory computer-readable medium of claim 17 , wherein the instructions further cause the one or more processors to carry out:

updating a file system size of the first file system volume based on the list of added chunks and the list of removed chunks.

19. The non-transitory computer-readable medium of claim 17 , wherein the instructions further cause the one or more processors to carry out:

updating a local cache of non-payload chunks of the first file system volume based on the list of added chunks and the list of removed chunks.

20. The non-transitory computer-readable medium of claim 17 , wherein the instructions further cause the one or more processors to carry out:

updating an index of one or more chunks stored in the content-addressable storage system based on the list of added chunks and the list of removed chunks.