File system storage in cloud using data and metadata merkle trees

• US 10,387,271 B2
• Filed: 05/10/2017
• Issued: 08/20/2019
• Est. Priority Date: 05/10/2017
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Elastifile Ltd.
• Inventors: Mosek, Amir, Frank, Shahar
• Primary Examiner(s): Le, Hung D
• Application Number:
  US15/591,131
• Publication Number:
  US 20180329785A1
• Time in Patent Office: 832 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data

Abstract

A data storage apparatus includes an interface for communicating with a backup storage system, and one or more processors. The one or more processors are configured to store a local copy of at least part of a file system represented by hierarchical structure of directories and files, to store a backup copy of the at least part of the file system in the backup storage system, to store a dual Merkle tree that is calculated over the backup copy and includes (i) a metadata Merkle tree including Metadata Merkle-Tree Keys (MD-MTKs) and (ii) a data Merkle tree including Data Merkle-Tree Keys (D-MTKs), and to update the backup copy to match the local copy using the dual Merkle tree.

Claims

1. A data storage apparatus, comprising:

an interface, for communicating with a backup storage system; and

one or more processors, configured to;

store a local copy of at least part of a file system represented by a hierarchical structure of nodes, each node including content and corresponding metadata;

store a backup copy of the at least part of the file system in the backup storage system;

store a metadata Merkle tree that is calculated over the backup copy, wherein each given node in the metadata Merkle tree includes a metadata key calculated over the metadata of a corresponding node of the backup copy, but not over the content of the corresponding node, and over the metadata keys of the child nodes of the given node; and

update the backup copy to match the local copy using the metadata Merkle tree, by;

calculating a temporary metadata Merkle tree over the stored local copy;

determining nodes of the temporary metadata Merkle tree having a different metadata key than the corresponding metadata key of the stored metadata Merkle tree; and

for the nodes determined to have a different metadata key, updating the content of the backup copy from the content of the stored local copy.

2. The apparatus according to claim 1, wherein the one or more processors are configured to update the content of the backup copy by:

calculating a first data key over at least part of the file in the local copy;

comparing the first data key with a second data key of the at least part of the file, which is stored in the metadata Merkle tree; and

updating the at least part of the file in the backup copy only if the first data key does not match the second data key.

3. The apparatus according to claim 2, wherein the one or more processors are configured to store the backup copy by storing at least part of a file in an object whose object name comprises the data key of the at least part of the file, and to update the at least part of the file by incrementing a reference count of the object.

4. The apparatus according to claim 3, wherein the one or more processors are configured to update the at least part of the file by writing content of the at least part of the file to the backup storage system only in response to a failure to increment the reference count.

5. The apparatus according to claim 1, wherein the corresponding metadata of each node comprises a time stamp of a most recent time the content of the node was modified.

6. A method for data storage, comprising:

storing a local copy of at least part of a file system represented by a hierarchical structure of nodes, each node including content and corresponding metadata;

storing a backup copy of the at least part of the file system in a backup storage system;

storing a metadata Merkle tree that is calculated over the backup copy, wherein each given node in the metadata Merkle tree includes a metadata key calculated over the metadata of a corresponding node of the backup copy, but not over the content of the corresponding node, and over the metadata keys of the child nodes of the given node; and

updating the backup copy to match the local copy using the metadata Merkle tree, by;

calculating a temporary metadata Merkle tree over the stored local copy;

determining nodes of the temporary metadata Merkle tree having a different metadata key than the corresponding metadata key of the stored metadata Merkle tree; and

for the nodes determined to have a different metadata key, updating the content of the backup copy from the content of the stored local copy.

7. The method according to claim 6, wherein updating the content of the backup copy comprises:

calculating a first data key over at least part of the file in the local copy;

comparing the first data key with a second data key of the at least part of the file, which is stored in the metadata Merkle tree; and

updating the at least part of the file in the backup copy only if the first data key does not match the second data key.

8. The method according to claim 7, wherein storing the backup copy comprises storing at least part of a file in an object whose object name comprises the data key of the at least part of the file, and wherein updating the backup copy comprises updating the at least part of the file by incrementing a reference count of the object.

9. The method according to claim 8, wherein updating the at least part of the file comprises writing content of the at least part of the file to the backup storage system only in response to a failure to increment the reference count.

10. A computer software product, the product comprising a tangible non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by one or more processors, cause the processors to:

store a local copy of at least part of a file system represented by a hierarchical structure of nodes, each node including content and corresponding metadata;

store a backup copy of the at least part of the file system in a backup storage system;

store a metadata Merkle tree that is calculated over the backup copy, wherein each given node in the metadata Merkle tree includes a metadata key calculated over the metadata of a corresponding node of the backup copy, but not over the content of the corresponding node, and over the metadata keys of the child nodes of the given node; and

update the backup copy to match the local copy using the metadata Merkle tree, by;

calculating a temporary metadata Merkle tree over the stored local copy;

determining nodes of the temporary metadata Merkle tree having a different metadata key than the corresponding metadata key of the stored metadata Merkle tree; and

for the nodes determined to have a different metadata key, updating the content of the backup copy from the content of the stored local copy.