US 11,455,319 B2Granted

Merkle tree forest for synchronizing data buckets of unlimited size in object storage systems

AssigneeEMC IP Holding Company LLC

InventorsAlex Solan, Jehuda Shemer

Life of this patent

Estimating the term…

Loading patent…

Abstract

Embodiments extend using sparse Merkle trees for smart synchronization of S3 buckets by overcoming fixed size limitations through creating another Merkle tree when the fixed size limit of the first tree is exceeded, and creating yet another tree when the second tree is filled up, and so on as needed. The method maintains a list of trees, in which each tree can be synchronized separately by keeping a strict division to trees according to generation number. The generation is passed from a source site to a target site during replication operations. The tagging of the generation number also makes it easy and efficient to remove an older version of an element or deal with deleted elements. This allows efficient syncing between two data object buckets without a size limitation on number of elements in a bucket.

Claims18

Dependent claims

A method of synchronizing object data between a source site and a target site, comprising:

creating, in each of the source and target sites, an initial Merkle tree having a fixed size with each node having a hashed value of the metadata for the node and that of any children of that node;
receiving data to be stored in the initial Merkle tree until the fixed size is reached;
creating, upon reaching the fixed size, additional Merkle trees each of a respective fixed size in a sequence of successive additional Merkle trees as each additional Merkle tree receives data in excess of its respective fixed size;
associating a unique generation number with each of the initial Merkle tree and additional Merkle trees, as maintained in an index table;
determining, from the index table the existence of any missing additional Merkle trees that are in the source site but not in the target site;
and
copying data of the missing additional Merkle trees from the source site to the target site using a Merkle tree synchronization, and wherein a new object of the received data is created in a POST operation by entering an element key and hash of the object value to a current Merkle tree, an existing data object is updated in a PUT operation by deleting its previous version from a previous Merkle tree in which the previous version resides, and an existing data object is deleted in a DELETE operation by fetching a corresponding generation tag for the existing data object and deleting it from the corresponding Merkle tree process.

4 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/803,902Filed 27 Feb 2020 · continuation in part
Priority: 29 Jan 2020
Published: US 2021/0232594 A129 Jul 2021
Granted: 27 Sep 2022
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06F 16/27
Of structured data, e.g. relational data: replication, distribution or synchronisation of data between databases or within a distributed database…
G06F 16/2246
Indexing structures: trees, e.g. B+trees
G06F 16/2255
Indexing structures: hash tables
G06F 16/2282
Indexing; Data structures therefor; Storage structures: tablespace storage structures; Management thereof

Family

Application16/776,129Parent of this continuation-in-part · filed 29 Jan 2020
US 2021/0232594 A1Pre-grant publication · published 29 Jul 2021
US 11,711,204 B2Related patent
US 2021/0234671 A1Published application
US 11,455,319 B2This patent

From the US filing history. Foreign family members aren’t listed.