Shallow cache for content replication

• US 10,534,708 B1
• Filed: 06/25/2018
• Issued: 01/14/2020
• Est. Priority Date: 06/25/2018
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Barker, Ross Neal, Sufaru, Adrian
• Primary Examiner(s): Kim, Hong C
• Application Number:
  US16/017,985
• Publication Number:
  US 20190391917A1
• Time in Patent Office: 568 Days
• Field of Search: 707634, 707635, 707692, 707205, 709212, 709219, 711162, 711118
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/119 Details of migration of file systems migration mechanisms in storage systems G06F3/0647
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: G06F 2212/27 Using a specific cache architecture

Abstract

Embodiments relate to efficiently replicating data from a source storage space to a target storage space. The storage spaces share a common namespace of paths where content units are stored. A shallow cache is maintained for the target storage space. Each entry in the cache includes a hash of a content unit in the target storage space and associated hierarchy paths in the target storage space where the corresponding content unit is stored. When a set of content units in the source storage space is to be replicated at the target storage space, any content unit with a hash in the cache is replicated from one of the associated paths in the cache, thus avoiding having to replicate content from the source storage space.

Claims

1. A method performed by a computing device comprising processing hardware and storage hardware, the method comprising:

storing, in the storage hardware, a local data store comprised of local data items having respective unique storage paths where they are stored in the local data store;

maintaining a shallow cache comprised of cache entries, each cache entry representing a respective local data item in the local data store, each cache entry comprising a hash of the correspondingly represented local data item and comprising a set of paths where respective copies of the local data item are stored in the local data store;

determining to add a dataset from a remote device to the data store, the dataset represented by a manifest comprising a list of manifest entries, each manifest entry comprising a hash of a respective remote data item at the remote device and a set of paths where respective copies of the remote data item are stored on the remote device;

based on determining to add the dataset from the remote device to the data store, adding the dataset by;

for each manifest entry in the manifest, determining whether any cache entry contains the hash of the manifest entry; and

when a cache entry is determined to contain a hash of a manifest entry, copying a local data item (i) from a path in the cache entry'"'"'s set of paths (ii) to each of the paths in the manifest entry'"'"'s set of paths.

2. A method according to claim 1, wherein when determined that no cache entry contains the hash of the manifest entry, copying a corresponding remote data item to the local data store at the paths in the manifest entry'"'"'s path set.

3. A method according to claim 1, further comprising determining that a given hash in the manifest is present in a given cache entry in the shallow cache, determining that each of the paths in the set of paths in the given cache entry do not contain a given data item that corresponds to the given hash, and based thereon copying the given data item from the remote device to the local data store and updating the shallow cache accordingly.

4. A method according to claim 1, wherein the local data store comprises a filesystem, the data items in the data store comprises files in the filesystem, and the paths in the sets of paths in the cache entries comprises filepaths in the file system.

5. A method according to claim 1, further comprising determining to copy another dataset from the remote device, accessing a second manifest corresponding to the other dataset, and adding hashes and paths from the second manifest to the shallow cache.

6. A method according to claim 1, further comprising allowing data items to be deleted from the local data store without requiring corresponding updates to the shallow cache.

7. A method according to claim 1, further comprising receiving multiple manifests for respective datasets and consolidating paths thereof that are associated with same hashes in the manifests.

8. A computing device comprising:

processing hardware configured to interoperate with storage hardware;

the storage hardware, the storage hardware storing instructions configured to, when executed by the processing hardware, cause the computing device to perform a process comprising;

providing a content-addressable storage that stores a hierarchy of files, each file stored at a respective unique path in the hierarchy of files, wherein instances of same files are stored at different respective unique paths in the hierarchy of files;

maintaining a shallow cache comprised of hashes of files in the hierarchy of files, the shallow cache further comprised of path lists associated with the hashes, respectively, each path list associated with a respective hash comprising a list of one or more paths in the hierarchy of files storing one or more respective instances of the file corresponding to the hash, wherein at least some of the path lists comprise multiple paths; and

adding files to respective new paths in the content-addressable storage by, each time a file is to be added to one or more new paths in the content-addressable storage, determining if a hash of the file is present in the shallow cache, wherein when a file'"'"'s hash is determined to be present in the shallow cache the file is copied from a path in the corresponding path list to each of the corresponding new paths.

9. A computing device according to claim 8, wherein when a file'"'"'s hash is determined to not be present in the shallow cache the file is copied from a remote source to each of the new paths that correspond to the file.

10. A computing device according to claim 8, wherein files in the content-addressable storage that have respective hashes and path lists in the shallow cache are allowed to be deleted without correspondingly updating the shallow cache.

11. A computing device according to claim 10, wherein when a path list in the shallow cache is used to add a new instance of the corresponding file to the content-addressable storage, a path in the path list is determined to not exist and based thereon another path in the path list is used as a source to add the new instance of the corresponding file.

12. A computing device according to claim 9, wherein the files being added to the content-addressable storage are obtained from a remote server via a network, and wherein the remote server is part of a cloud service and the files being added are identified by the cloud service.

13. A computing device according to claim 8, the process further comprising, when adding a new file to the content-addressable storage using the shallow cache, determining that a path in a path list in the shallow cache is invalid and based thereon removing the path from the path list.

14. A computing device according to claim 8, wherein when a file and corresponding new paths are being added to the content-addressable storage, each path in the new paths is added to the content-addressable storage and each added path in the new paths comprises a location where an instance of the file is stored.

15. Computer-readable storage hardware storing instructions configured to cause a computing device to perform a process, the storage hardware not comprising a signal, the process comprising:

maintaining a storage comprised of content units, each content unit stored at a full path, each full path belonging to a same namespace, wherein some of the full paths contain instances of a same respective content unit;

maintaining a location cache that indicates which content units are stored at which full paths in the storage, wherein, given an arbitrary content unit, full paths where respective instances of the arbitrary content unit are stored in the storage can be obtained based on a hash of the arbitrary content unit;

receiving a first request to add a first target content unit to the storage at first target full paths in the namespace;

responding to the first request by obtaining a first target hash of the first target content unit, obtaining a source full path from the location cache based on the target hash, and using the obtained source full path to copy a content unit at the source full path to each of the target full paths.

16. Computer-readable storage hardware according to claim 15, wherein the location cache comprises hashes of respective content units, and wherein the source full path is obtained from the location cache by searching for the first target hash in the location cache.

17. Computer-readable storage hardware according to claim 15, the process further comprising receiving a second request to add a second target content unit to the storage at second target full paths in the namespace, determining that the location cache does not contain a valid location of the second target content unit, and based thereon copying the second target content unit from a remote storage to the storage at the second target full paths.

18. Computer-readable storage hardware according to claim 15, the process further comprising receiving a second request to add a second target content unit to the storage at second target full paths in the namespace, determining that the location cache contains a candidate full path corresponding to a hash of the second target content unit, and computing a hash of a content unit stored at the candidate full path.

19. Computer-readable storage hardware according to claim 18, the process further comprising determining that the computed hash of the content unit at the candidate full path does not match a hash of the second target content unit and based thereon determining not to use the content unit at the candidate full path to satisfy the second request.

20. Computer-readable storage hardware according to claim 15, a set of full paths in an entry in the cache includes a path that does not contain a content unit matching the hash associated with the entry.