Identifying and resolving differences between datastores
AssigneeOracle International Corporation
InventorsEthan William Dereszynski, Sean Jay McNamara
Life of this patent
Estimating the term…
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.
Claims20
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 a plurality of attributes of a first data item of a plurality of data items, wherein the plurality of attributes comprise at least one of:
- 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;
- or
- a data storage tier identifier identifying storage of the first data item in an active tier or inactive tier;
- applying a hash function to the plurality of attribute values to compute a first hash value;
- mapping the first hash value to a first leaf node of a first plurality of leaf nodes of a first multi-level hash tree;
- storing an association between the first data item and the first leaf node;
- updating a node hash value corresponding to the first leaf node based on the first data item;
- and
- updating node hash values corresponding to nodes of the first leaf node in the first multi-level hash tree that are directly or indirectly connected to the first leaf node,
- wherein updating each node hash value includes updating a hash value for at least one node at each level of the multi-level hash tree.
A method comprising:
- identifying a plurality of attributes of a first data item of a plurality of data items, wherein the plurality of attributes comprise at least one of:
- 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;
- or
- a data storage tier identifier identifying storage of the first data item in an active tier or inactive tier;
- applying a hash function to the plurality of attribute values to compute a first hash value;
- mapping the first hash value to a first leaf node of a first plurality of leaf nodes of a first multi-level hash tree;
- storing an association between the first data item and the first leaf node;
- updating a node hash value corresponding to the first leaf node based on the first data item;
- and
- updating node hash values corresponding to nodes of the first leaf node in the first multi-level hash tree that are directly or indirectly connected to the first leaf node,
- wherein updating each node hash value includes updating a hash value for at least one node at each level of the multi-level hash tree.
A system comprising:
- at least one device including a hardware processor;
- the system being configured to perform operations comprising:
- identifying a plurality of attributes of a first data item of a plurality of data items, wherein the plurality of attributes comprise at least one of:
- 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;
- or
- a data storage tier identifier identifying storage of the first data item in an active tier or inactive tier;
- applying a hash function to the plurality of attribute values to compute a first hash value;
- mapping the first hash value to a first leaf node of a first plurality of leaf nodes of a first multi-level hash tree;
- storing an association between the first data item and the first leaf node;
- updating a node hash value corresponding to the first leaf node based on the first data item;
- and
- updating node hash values corresponding to nodes of the first leaf node in the first multi-level hash tree that are directly or indirectly connected to the first leaf node,
- wherein updating each node hash value includes updating a hash value for at least one node at each level of the multi-level hash tree.
Dependencies are inferred from the claim text.