Identifying and resolving differences between datastores

Patent metadata

Field	Value
Publication number	US-11663192-B2
Application number	US-202017117900-A
Country	US
Kind code	B2
Filing date	Dec 10, 2020
Priority date	Dec 10, 2020
Publication date	May 30, 2023
Grant date	May 30, 2023

Abstract

Techniques for efficiently maintaining consistency of data items across storage partitions are disclosed using a hierarchical multi-level hash tree. Copies of a data item may be associated with corresponding attributes that are used to generate hash values for the data item. Hash values of the attributes may then be used to label nodes in a multi-level hash tree. Differences between the replicated copies of a data item may be quickly identified by comparing hash values associated with successively lower peer nodes in corresponding hash trees. Once identified, systems may update versions of a data item that are no longer current.

First claim

What is claimed is:

1. One or more non-transitory computer-readable media storing instructions, which when executed by one or more hardware processors, cause performance of operations comprising:
identifying at least one attribute of a first data item of a plurality of data items;
applying a hash function to the at least one attribute to compute a first data item hash value;
mapping the first data item hash value to a first leaf node of a first plurality of leaf nodes of a first multi-level hash tree, the first leaf node being associated with a first node hash value;
storing a new association between the first data item and the first leaf node;
updating the first node hash value corresponding to the first leaf node based on the new association between first data item and the first leaf node; and
updating node hash values corresponding to a subset of nodes of the first multi-level hash tree that are direct or indirect parents of the first leaf node;
comparing a first set of node hash values corresponding to the nodes of the first multi-level hash tree to a second set of node hash values corresponding to nodes of a second multi-level hash tree until at least a difference is identified between (a) the first node hash value corresponding to the first leaf node of the first multi-level hash tree and (b) a second node hash value corresponding to a second leaf node of the second multi-level hash tree;
wherein the second leaf node of the second multi-level hash tree is a peer of the first leaf node of the first multi-level hash tree;
responsive to identifying the difference between the first node hash value and the second node hash value:
determining that the first data item, associated with the first leaf node, is an updated version of a second data item associated with the second leaf node by comparing one or more data items associated with the first leaf node to one or more data items associated with the second leaf node; and
updating the second data item to match the first data item.

2. The one or more media of claim 1 , wherein the comparing operation comprises:
selecting, for comparison, a target node of the first multi-level hash tree and a peer target node of the second multi-level hash tree; and
responsive to determining that a first node hash value of the target node of the first multi-level hash tree and a second node hash value of the peer target node of the second multi-level hash tree are different, executing a descending comparison of hash values of child nodes of the target node to hash values of peer child nodes of the second multi-level hash tree;
wherein the child nodes of the first multi-level hash tree are selected more frequently in a first descending direction for comparison to the peer child nodes of the second multi-level hash tree than in a second descending direction.

3. The one or more media of claim 2 , wherein child nodes of the first multi-level hash tree in the first descending direction are selected from two times to four times more often than child nodes in the second descending direction.

4. The one or more media of claim 1 , wherein the operations further comprise determining a storage location for storing the first data item based on a second hash value corresponding to the at least one attribute.

5. The one or more media of claim 1 , wherein data items corresponding to first leaf node are stored in a particular memory region.

6. The one or more media of claim 5 , wherein the particular memory region is identified in the first leaf node using a data item identifier.

7. The one or more media of claim 1 , wherein the at least one attribute comprises an account identifier.

8. The one or more media of claim 1 , wherein the at least one attribute comprises a time associated with a data transaction event.

9. The one or more media of claim 1 , wherein the at least one attribute comprises a table identifier.

10. The one or more media of claim 1 , wherein the at least one attribute comprises a data storage tier identifier.

11. The one or more media of claim 1 , wherein the at least one attribute comprises one or more of the following:
an account identifier identifying an account associated with the first data item;
a time associated with a data transaction event executed on the first data item;
a table identifier identifying a data structure associated with the first data item;
a data storage tier identifier identifying storage of the first data item in an active tier; and
a data storage tier identifier identifying storage of the first data item in an inactive tier.

12. The one or more media of claim 1 , wherein updating the hash value for at least one node at each level of the multi-level hash tree, comprises:
updating a first hash value for at least one first node at a first level of the multi-level hash tree connected to the leaf node; and
updating a second hash value for at least one second node at a second level of the multi-level hash tree connected to the leaf node through the first node.

13. A method comprising:
identifying at least one attribute of a first data item of a plurality of data items;
applying a hash function to the at least one attribute to compute a first data item hash value;
mapping the first data item hash value to a first leaf node of a first plurality of leaf nodes of a first multi-level hash tree, the first leaf node being associated with a first node hash value;
storing a new association between the first data item and the first leaf node;
updating the first node hash value corresponding to the first leaf node based on the new association between the first data item and the first leaf node; and
updating node hash values corresponding to a subset of nodes of the first multi-level hash tree that are direct or indirect parents of the first leaf node in the first multi-level hash tree;
comparing a first set of node hash values corresponding to the nodes of the first multi-level hash tree to a second set of node hash values corresponding to nodes of a second multi-level hash tree until at least a difference is identified between (a) the first node hash value corresponding to the first leaf node of the first multi-level hash tree and (b) a second node hash value corresponding to a second leaf node of the second multi-level hash tree;
wherein the second leaf node of the second multi-level hash tree is a peer of the first leaf node of the first multi-level hash tree;
responsive to identifying the difference between the first node hash value and the second node hash value:
determining that the first data item, associated with the first leaf node, is an updated version of a second data item associated with the second leaf node by comparing one or more data items associated with the first leaf node to one or more data items associated with the second leaf node; and
updating the second data item to match the first data item.

14. The method of claim 13 , wherein the comparing operation comprises:
selecting, for comparison, a target node of the first multi-level hash tree and a peer target node of the second multi-level hash tree; and
responsive to determining that a first node hash value of the target node of the first multi-level hash tree and a second node hash value of the peer target node of the second multi-level hash tree are different, executing a descending comparison of hash values of child nodes of the target node to hash values of peer child nodes of the second multi-level hash tree;
wherein the child nodes of the first multi-level hash tree are selected more frequently in a first descending direction for comparison to the peer child nodes of the

Assignees

• Oracle Int Corp

Inventors

• Dereszynski Ethan William
• Mcnamara Sean Jay

Classifications

• G06F16/2255

  Hash tables · CPC title

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F16/2379

  Updates performed during online database operations; commit processing · CPC title

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F16/178

  Techniques for file synchronisation in file systems · CPC title