Cloud storage using Merkle trees
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.
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 change blocks for the object at the source location;
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; and
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, further wherein upon encountering a missing Merkle node during the step of copying, pushing the missing Merkle node onto a stack.
2. The method according to claim 1 , further comprising:
updating the deduplicating block store with the change blocks based upon the synchronized Merkle tree nodes.
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 missing Merkle nodes in the Merkle tree.
5. The method according to claim 1 , further comprising:
popping the Merkle node from the stack to the deduplicating block store; and
placing a missing data block associated with the missing Merkle node in the deduplicating block store according to the Merkle tree.
6. The method according to claim 1 , wherein the stack resides on the deduplicating block store.
7. The method according to claim 1 , wherein the stack resides on a client device.
8. The method according to claim 1 , further comprising establishing a progress indicator that represents Merkle nodes currently in the stack.
9. The method according to claim 2 , further comprising generating a new identifier for each of the change blocks.
10. A system, comprising:
a processor; and
logic encoded in one or more tangible, non-transitory 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 change blocks for the object at a source location;
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; and
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, further wherein upon encountering a missing Merkle node during the step of copying, pushing the missing Merkle node onto a stack.
11. The system according to claim 10 , further comprising:
updating the deduplicating block store with the change blocks based upon the synchronized Merkle tree nodes.
12. The system according to claim 10 , 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.
13. The system according to claim 10 , wherein the processor further executes the logic to perform an operation of evaluating the Merkle tree in top-to-bottom order to determine missing Merkle nodes in the Merkle tree.
14. The system according to claim 10 , wherein the processor further executes the logic to perform operations of:
popping the Merkle node from the stack to the deduplicating block store; and
placing a missing data block associated with the missing Merkle node in the deduplicating block store according to the Merkle tree.
15. The system according to claim 10 , wherein the stack resides on any of the deduplicating block store and a client device.
16. The system according to claim 10 , wherein the processor further executes the logic to perform an operation of establishing a progress indicator that represents Merkle nodes currently in the stack.
17. The system according to claim 11 , wherein the processor further executes the logic to perform an operation of generating a new identifier for each of the change blocks of the synchronized Merkle tree nodes.
18. 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; and
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, further wherein upon encountering a missing Merkle node during the step of copying, pushing the missing Merkle node onto a stack.