Cloud storage using merkle trees

• US 10,599,533 B2
• Filed: 05/18/2017
• Issued: 03/24/2020
• Est. Priority Date: 05/07/2013
• Status: Active Grant

• Current Assignee: eFolder, Inc.
• Original Assignee: eFolder, Inc.
• Inventors: Petri, Robert, Parab, Nitin
• Primary Examiner(s): Whipple, Brian
• Assistant Examiner(s): Mekonen, Tesfu N
• Application Number:
  US15/599,417
• Publication Number:
  US 20170257254A1
• Time in Patent Office: 1,041 Days
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• 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 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

Efficient cloud storage systems, methods, and media are provided herein. Exemplary methods may include locating a Merkle tree of a stored object on a deduplicating block store, comparing an object at a source location to the Merkle tree of the stored object, determining changed blocks for the object at a source location, and transmitting a message across a network to the deduplicating block store, the message including the change blocks and Merkle nodes that correspond to the change blocks.

Claims

1. A method, comprising:

locating a Merkle tree of a stored object on a deduplicating block store;

comparing an object at a source location to the Merkle tree of the stored object;

determining changed blocks for the object at the source location;

transmitting a message across a network to the deduplicating block store, the message comprising the change blocks and Merkle nodes that correspond to the change blocks, wherein the Merkle nodes that correspond to the change blocks comprise at least one missing Merkle node that is missing from the Merkle tree of the stored object;

synchronizing the transmitted Merkle nodes for the change blocks with Merkle nodes of the Merkle tree of the stored object, wherein synchronizing comprises copying the Merkle nodes of the Merkle tree in bottom-to-top order to ensure that when a check of any Merkle node is performed that all child Merkle nodes associated with the Merkle node are present; and

pushing the at least one missing Merkle node onto a stack residing on the deduplicating block store.

2. The method according to claim 1, further comprising:

updating the deduplicating block store with the change blocks based upon the Merkle nodes of the Merkle tree that were synchronized.

3. The method according to claim 1, further comprising:

generating the Merkle tree, the Merkle tree comprising Merkle nodes that represent blocks stored in the deduplicating block store; and

exposing the Merkle tree to a client device through an application programming interface.

4. The method according to claim 1, further comprising evaluating the Merkle tree in top-to-bottom order to determine the at least one missing Merkle node.

5. The method according to claim 1, further comprising:

popping the at least one missing Merkle node from the stack to the deduplicating block store; and

placing a missing data block associated with the at least one missing Merkle node in the deduplicating block store according to the Merkle tree.

6. The method according to claim 1, further comprising establishing a progress indicator that represents how many Merkle nodes are currently in the stack.

7. The method according to claim 2, further comprising generating a new identifier for each of the changed blocks.

8. A system, comprising:

a processor; and

logic encoded in one or more non-transitory computer readable media for execution by the processor and when executed operable to perform operations comprising;

locating a Merkle tree of a stored object on a deduplicating block store;

comparing an object at a source location to the Merkle tree of the stored object;

determining changed blocks for the object at a source location;

transmitting a message across a network to the deduplicating block store, the message comprising the change blocks and Merkle nodes that correspond to the change blocks, wherein the Merkle nodes that correspond to the change blocks comprise at least one missing Merkle node that is missing from the Merkle tree of the stored object;

causing the transmitted Merkle nodes for the change blocks to be synchronized with Merkle nodes of the Merkle tree of the stored object, wherein synchronizing comprises copying the Merkle nodes of the Merkle tree in bottom-to-top order to ensure that when a check of any Merkle node is performed that all child Merkle nodes associated with the Merkle node are present; and

pushing the at least one missing Merkle node onto a stack residing on the deduplicating block store.

9. The system according to claim 8, further comprising:

updating the deduplicating block store with the change blocks based upon the Merkle nodes of the Merkle tree that were synchronized.

10. The system according to claim 8, wherein the processor further executes the logic to perform operations of:

generating the Merkle tree, the Merkle tree comprising Merkle nodes that represent blocks stored in the deduplicating block store; and

exposing the Merkle tree to a client device.

11. The system according to claim 8, wherein the processor further executes the logic to perform an operation of evaluating the Merkle tree in top-to-bottom order to determine the at least one missing Merkle node.

12. The system according to claim 8, wherein the processor further executes the logic to perform operations of:

popping the at least one Merkle node from the stack to the deduplicating block store; and

placing a missing data block associated with the at least one missing Merkle node in the deduplicating block store according to the Merkle tree.

13. The system according to claim 8, wherein the processor further executes the logic to perform an operation of establishing a progress indicator that represents how many Merkle nodes are currently in the stack.

14. The system according to claim 9, wherein the processor further executes the logic to perform an operation of generating a new identifier for each of the changed blocks of the synchronized Merkle tree nodes.

15. A method, comprising:

generating a first Merkle tree for an object, the first Merkle tree comprising Merkle nodes that represent blocks of the object;

examining an input data stream;

generating a second Merkle tree for the object using the input data stream;

comparing the first Merkle tree and the second Merkle tree to one another to determine changed Merkle nodes that do not correspond between the first Merkle tree and the second Merkle tree;

transmitting data blocks that correspond to the changed Merkle nodes from a source location to a deduplicating block store, wherein the data blocks comprise at least one missing Merkle node that is missing from the first Merkle tree;

synchronizing the transmitted data blocks for the changed Merkle nodes with Merkle nodes of at least one Merkle tree, wherein synchronizing comprises copying the Merkle nodes of the Merkle tree in bottom-to-top order to ensure that when a check of any Merkle node is performed that all child Merkle nodes associated with the Merkle node are present; and

pushing the at least one missing Merkle node onto a stack residing on the deduplicating block store.