CLOUD STORAGE USING MERKLE TREES

• US 20160110261A1
• Filed: 12/21/2015
• Published: 04/21/2016
• Est. Priority Date: 05/07/2013
• Status: Abandoned Application

• Current Assignee: eFolder, Inc.
• Original Assignee: Axcient
• Inventors: Parab, Nitin, Brown, Aaron
• Application Number:
  US14/977,607
• Publication Number:
  US 20160110261A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/174 Redundancy elimination performed by the file system management of the data involved in backup or backup restore using de-duplication of the data G06F11/14
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/12 Transmitting and receiving encryption devices synchronised or initially set up in a particular manner

Abstract

Efficient cloud storage systems, methods, and media are provided herein. Exemplary methods may include storing a data stream on a client side de-duplicating block store of a client device, generating a data stream Merkle tree of the data stream, storing a secure hash algorithm (SHA) key for the data stream Merkle tree, as well as the data stream Merkle tree on the client side de-duplicating block store, recursively iterating through the data stream Merkle tree using an index of a snapshot Merkle tree of the client device that is stored on a cloud data center to determine missing Merkle nodes or missing data blocks which are present in the data stream Merkle tree but not present in the snapshot Merkle tree stored on the cloud data center, and transmitting over a wide area network (WAN) the missing data blocks to the cloud data center.

Claims

1. A data stream synchronization method, comprising:

storing a data stream on a client side de-duplicating block store of a client device;

generating a data stream Merkle tree of the data stream;

storing a secure hash algorithm (SHA) key for the data stream Merkle tree, as well as the data stream Merkle tree on the client side de-duplicating block store;

recursively iterating through the data stream Merkle tree using an index of a snapshot Merkle tree of the client device that is stored on a cloud data center to determine missing Merkle nodes or missing data blocks which are present in the data stream Merkle tree but not present in the snapshot Merkle tree stored on the cloud data center; and

transmitting over a wide area network (WAN) the missing data blocks to the cloud data center.

2. The method according to claim 1, further comprising storing the missing Merkle nodes or missing data blocks in a child first, parent second arrangement.

3. The method according to claim 1, further comprising reconstructing the data stream Merkle tree on the cloud data center.

4. The method according to claim 1, wherein recursively iterating comprising walking a breadth of the data stream Merkle tree and pushing all non-existent Merkle nodes on a same level into a stack on the client side de-duplicating block store.

5. The method according to claim 4, further comprising transmitting the non-existent Merkle nodes in the stack over the WAN in multiple threads in parallel.

6. The method according to claim 4, further comprising popping the non-existent Merkle nodes from the client side de-duplicating block store to the cloud data center.

7. The method according to claim 5, wherein the non-existent Merkle nodes are transferred in such a way that a sequentially consistent relationship is maintained for Merkle roots.

8. The method according to claim 1, further comprising storing the missing data blocks as blobs in a blobstore.

9. The method according to claim 1, wherein transmitting over the WAN includes executing PUT operations for missing data blocks, wherein the PUT operations are idempotent because the PUT operations are defined with equivalent bulk variants allowing synchronization of a plurality of PUT operations for the same missing data blocks.

10. The method according to claim 1, wherein recursively iterating comprises:

creating a first directed acyclic graph of the data stream Merkle tree and the snapshot Merkle tree to determine data blocks reachable by a Merkle root; and

creating a second directed acyclic graph with the data blocks that are only present on the cloud data center removed, wherein the second directed acyclic graph has an initial height.

11. The method according to claim 10, wherein transmitting over the WAN includes:

transmitting leaves of the second directed acyclic graph so as to create a third directed acyclic graph that has a height of the initial height minus one; and

creating additional directed acyclic graphs and transmitting their leaves until the Merkle root is reached.

12. The method according to claim 1, wherein the missing data blocks are transmitted in a PUT operation that operates within a session and are placed into a session local cache on the cloud data store.

13. The method according to claim 12, wherein the missing data blocks of the session are stored together as an extent on the data store to preserve temporal locality of the missing data blocks as a spatial locality on the cloud data store.

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

generating a SHA key value for each of the missing data blocks;

adding the SHA key values to the index.

15. The method according to claim 1, further comprising performing garbage collection by:

marking each block within the snapshot Merkle tree with a generation number;

refreshing the generation number of blocks of the snapshot Merkle tree which are referenced by at least one other block; and

deleting a block from a blockstore if the block is not referenced by at least one other block or does not have a current generation number; and

deleting a blob associated with the block from a blobstore.

16. The method according to claim 1, wherein the refreshing process is executed after each new data stream synchronization process.

17. A system, comprising:

a cloud data center comprising a cloud side de de-duplicating block store; and

a client side appliance that is coupled to the cloud data center over a wide area network (WAN), the client side appliance being configured to;

store a data stream on a client side de-duplicating block store of a client device;

generate a data stream Merkle tree of the data stream;

store a secure hash algorithm (SHA) key for the data stream Merkle tree, as well as the data stream Merkle tree on the client side de-duplicating block store;

recursively iterate through the data stream Merkle tree using an index of a snapshot Merkle tree of the client device that is stored on a cloud data center to determine missing Merkle nodes or missing data blocks which are present in the data stream Merkle tree but not present in the snapshot Merkle tree stored on the cloud data center; and

transmit over the wide area network (WAN) the missing data blocks to the cloud a center.

18. The method according to claim 17, wherein the cloud data center comprises a blockstore that stores the missing data blocks and a blobstore that stores blobs associated with the missing data blocks.

19. The method according to claim 18, wherein the blobs are associated with the blocks using SHA key values of the blocks that are stored in the index.