Combining merkle trees in graph databases

• US 10,242,065 B1
• Filed: 06/30/2016
• Issued: 03/26/2019
• Est. Priority Date: 06/30/2016
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Starling, Jennifer, Brenner, Adam, Norton, Jeffrey, Auchmoody, Scott, Malamut, Mark D
• Primary Examiner(s): Rahim, Monjur
• Application Number:
  US15/197,863
• Time in Patent Office: 999 Days
• Field of Search: 713189
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• 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/50 using hash chains, e.g. blockchains or hash trees

Abstract

Combining a Merkle tree with a graph database by defining a Merkle tree with each node having a hashed value of the metadata for the node and any children of that node, associating non-hashed data with the hashed data for each node, wherein the non-hashed data has an up-pointer from a child node to any of its immediate parent node, and defining bi-directional edges between the nodes of the Merkle tree having a graph database structure to create a reference for the up-pointers associated with each Merkle tree node. The bi-directional edges with up-pointers along with the Merkle tree hash scheme allows efficient traversal of the tree where the hash values indicate non-changed nodes to prevent traversing the database, and further allows efficient path definitions by allowing database processes to walk up edges.

Claims

1. A computer implemented method of implementing a Merkle tree having bi-directional edges to process data in a database, the method comprising:

defining, by a hardware processor executing a database management process, a Merkle tree with each node having a hashed value of the metadata for the node and that of any children of that node;

associating non-hashed data with the hashed data for each node, wherein the non-hashed data comprises an initial up-pointer from a child node to any of its immediate parent node;

defining, by the processor, a graph database using graph structures for semantic queries with nodes, bi-directional edges and properties to represent the data;

combining the Merkle tree and graph database to define up-pointers and down-pointers comprising edges between the nodes of the Merkle tree using the bi-directional edges of the graph database to create a reference for the initial up-pointers associated with each Merkle tree node to thereby facilitate efficient traversal of the database through both the up-pointers and down-pointers, and efficient detection of any change in the database through changes in the hashed data, and wherein the bi-directional edges with the initial up-pointers along with the original Merkle tree hash scheme allows for efficient traversal of the tree where the hash values indicate non-changed nodes to prevent traversing corresponding sections of the database, and further allows efficient path definitions and data location by allowing database processes to walk up edges; and

storing the Merkle tree in a memory coupled to the processor.

2. The method of claim 1 wherein the non-hashed data is associated with the hashed data by encoding the initial up-pointer according to a defined scheme and concatenating the non-hashed data with the hashed data.

3. The method of claim 1 wherein the non-hashed data is associated with the hashed data by encoding the initial up-pointer according to a defined scheme and defining a separate data structure for the non-hashed data, and associating it with a corresponding Merkle tree node through an index or pointer.

4. The method of claim 1 further comprising assigning a weighted value to each up-pointer to represent a bias associated with a corresponding node.

5. The method of claim 1 wherein the database represents a deduplicated storage catalog maintained in a large-scale data storage network executing a backup process from one or more data sources to a plurality of storage devices.

6. The method of claim 5 wherein network devices and resources are stored as corresponding data elements in a storage catalog processed by the database management process associated with a backup management server, and wherein functions using the Merkle tree for the data elements include deduplication, path traversal, and garbage collection processes.

7. A method of implementing a graph database having hash-encoded nodes to process data in a database, comprising:

defining, by a hardware processor executing a database management process, a graph database using graph structures for semantic queries with nodes, bi-directional edges and properties to represent the data;

labeling each node with the hashed value of the node and any children to integrate a Merkle tree structure into the graph database;

labeling each node with initial up-pointers to the node'"'"'s parent node;

wherein the integrated Merkle tree and graph database define up-pointers and down-pointers comprising edges between the nodes of the Merkle tree using the bi-directional edges of the graph database to create a reference for the initial up-pointers associated with each Merkle tree node to thereby facilitate efficient traversal of the database through both the up-pointers and down-pointers, and efficient detection of any change in the database through changes in the hashed data, wherein the bi-directional edges with the initial up-pointers along with the original Merkle tree hash scheme allows for efficient traversal of the tree where the hash values indicate non-changed nodes to prevent traversing corresponding sections of the database, and further allows efficient path definitions and data location by allowing database processes to walk up edges; and

storing the Merkle tree in a memory coupled to the processor.

8. The method of claim 7, wherein database records are stored in the nodes of the graph database, and the bi-directional edges comprise typed, directed arcs.

9. The method of claim 8 wherein each node and edge is assigned named attributes that are encoded to include the initial up-pointers as non-hashed data and the hashed value of the node in the Merkle tree format.

10. The method of claim 7 further comprising assigning a weighted value to each up-pointer to represent a bias associated with a corresponding node.

11. The method of claim 7 wherein the database represents a deduplicated storage catalog maintained in a large-scale data storage network executing a backup process from one or more data sources to a plurality of storage devices.

12. The method of claim 11 wherein network devices and resources are stored as corresponding data elements in a storage catalog processed by the database management process associated with a backup management server, and wherein functions using the Merkle tree for the data elements include deduplication, path traversal, and garbage collection processes.

13. A computer program product, comprising a non-transitory computer-readable medium having a computer-readable program code embodied therein, the computer-readable program code adapted to execute a method of implementing a Merkle tree in a graph database to process data in a database, comprising:

defining, by a hardware processor executing a database management process, a Merkle tree with each node having a hashed value of the metadata for the node and that of any children of that node;

associating non-hashed data with the hashed data for each node, wherein the non-hashed data comprises an initial up-pointer from a child node to any of its immediate parent node;

defining, by the processor, a graph database using graph structures for semantic queries with nodes, bi-directional edges and properties to represent the data;

combining the Merkle tree and graph database to define up-pointers and down-pointers comprising edges between the nodes of the Merkle tree using the bi-directional edges of the graph database to create a reference for the initial up-pointers associated with each Merkle tree node to thereby facilitate efficient traversal of the database through both the up-pointers and down-pointers, and efficient detection of any change in the database through changes in the hashed data, wherein the bi-directional edges with the initial up-pointers along with the original Merkle tree hash scheme allows for efficient traversal of the tree where the hash values indicate non-changed nodes to prevent traversing corresponding sections of the database, and further allows efficient path definitions and data location by allowing database processes to walk up edges; and

storing the Merkle tree in a memory coupled to the processor.