Granted Patent B2

US 8,924,365 · App. 13/250,128 · Granted Dec 30, 2014

Abstract

Claims (69)

1. A computer-implemented method for resolving eventual consistency conflicts within a prefix hash tree comprising the steps of:

using an algorithm to create a prefix hash tree that relates to a distributed hash table, the prefix hash tree having multiple nodes, wherein the nodes comprise leaf nodes and internal nodes;

aggregating all distinct records across all conflicting nodes, wherein conflicting nodes are nodes that have identical data records, and counting records returned to obtain an aggregated record count;

splitting the conflicting nodes that have the aggregated record count exceeding a max record count, such that the aggregated records are divided by a prefix into each new node, resulting in the consolidation of duplicate data that were in conflicting nodes into a single data record in a single node; and

splitting conflicting nodes that are internal nodes regardless of the aggregated record count.

2. The compute implemented method of claim 1 , further comprising the steps of:

reading a node by a user, the node having conflicting records entered by different users prior to the reading by the user, the conflicting records having different content but are written to a same node of the tree; and

resolving the conflicting records by said splitting.

3. The computer-implemented method of claim 1 , further comprising the steps of:

reading a record from a node by a user, the record having data that the user desires to delete; and

marking the record for deletion by updating a delete-indicator within the record.

4. The computer-implemented method of claim 3 , wherein the step of marking further includes marking the record with a delete-timestamp.

5. The computer-implemented method of claim 4 , further comprising the steps of:

executing a computer software program to inspect the delete-timestamp; and

if the delete-timestamp falls within a pre-determined time frame, then delete the record.

6. The computer-implemented method of claim 3 , further comprising the steps of:

executing a computer software program to inspect the delete-indicator; and

if the delete-indicator lists the record as to be deleted, then delete the record.

7. A computer-implemented method for resolving eventual consistency conflicts within a prefix hash tree comprising the steps of:

using an algorithm to create a prefix hash tree that relates to a distributed hash table, the prefix hash tree having multiple nodes, wherein the nodes are leaf nodes and internal nodes;

obtaining a maximum tree depth of the prefix hash tree;

obtaining a max record count for each node;

aggregating all distinct records across all conflicting nodes, wherein conflicting nodes are nodes that have identical data records, and counting records returned to obtain an aggregated record count; obtaining the nodes that are related to a new record that is to be inserted beginning at a deepest node;

inserting the new record into the deepest node that has an aggregate record count less than the max record count, then obtaining a next node upward; and

repeating the insert process when the aggregate record count is less than the max record count and the aggregate record count of the next node upward is less than the max record count, otherwise end insertion of the new record.

8. The computer-implemented method of claim 7 , further comprising the steps of:

reading a node by a user, the node having conflicting records entered by different users prior to the reading by the user, the conflicting records having different content but are written to a same node of the tree;

if the number of a rented records exceeds a max record count limit, then splitting the node;

wherein the aggregated records are divided by a prefix into each new node; and

if one or more of the returned conflicting node values is an internal node, splitting the node regardless of the number of aggregated records.

9. The computer-implemented method of claim 7 , further comprising the steps of:

reading a record from a node by a user, the record having data that the user desires to delete; and

marking the record for deletion by updating a delete-indicator within the record.

10. The computer-implemented method of claim 7 , wherein the step of marking further includes marking the record with a delete-timestamp.

11. The computer-implemented method of claim 10 , further comprising the steps of:

executing a computer software program to inspect the delete-timestamp; and

if the delete-timestamp falls within a pre-determined time frame, then delete the record.

12. The computer-implemented method of claim 7 , further comprising the steps of:

executing a computer software program to inspect the delete-indicator; and

if the delete-indicator lists the record as to be deleted, then delete the record.

13. A computer-implemented method for resolving eventual consistency within a prefix hash tree, the method comprising the steps of:

using an algorithm to create a prefix hash tree that relates to a distributed hash table, the prefix hash tree having multiple nodes, wherein the nodes comprise leaf nodes and internal nodes;

reading a node by a user, the node having conflicting records entered by different users prior to the reading by the user, the conflicting records having different content but are written to a same node of the tree;

aggregating all distinct records across all conflicting node values returned;

if the number of aggregated records exceeds a max record count limit, then splitting the node;

wherein the aggregated records are divided by a prefix into each new node; and

if one or more of the returned conflicting node values is an internal node, splitting the node regardless of the number of aggregated records.

14. An eventual consistency resolution system comprising:

at least one of a plurality of servers;

at least one of a plurality of program storage devices readable by machine such that the at least one of a plurality of program storage devices and the at least one of a plurality of servers are connected together to form a network, wherein the at least one of a plurality of program storage devices embodies a program of instructions executable by the machine to perform method steps for eventual consistency resolution, the method steps comprising:

using an algorithm to create a prefix hash tree that relates to a distributed hash table, the prefix hash tree having multiple nodes, wherein the nodes are leaf nodes and internal nodes;

obtaining a maximum tree depth of the prefix hash tree;

obtaining a max record count for each node;

aggregating all distinct records across all conflicting nodes, wherein conflicting nodes are nodes that have identical data records, and counting records returned to obtain an aggregated record count; obtaining the nodes that are related to a new record that is to be inserted beginning at a deepest node;

inserting the new record into the deepest node that has an aggregate record count less than the max record count, then obtaining a next node upward; and

repeating the insert process when the aggregate record count is less than the max record count and the aggregate record count of the next node upward is less than the max record count, otherwise ending insertion of the new record.

15. The system of claim 14 , wherein the machine comprises at least one of a server, a personal computer, a tablet computer, a smart-phone, a cellular device, and a main-frame computer.

16. The system of claim 14 , wherein the network comprises at least one of wireless, broadband, hard-wired, and internet.

17. The system of claim 14 , wherein the method further comprises the steps of:

reading a node by a user, the node having conflicting records entered by different users prior to the reading by the user, the conflicting records having different content but are written to a same node of the tree;

if the number of aggregated records exceeds a max record count limit, then splitting the node;

wherein the aggregated records are divided by a prefix into each new node; and

if one or more of the returned conflicting node values is an internal node, splitting the node regardless of the number of aggregated records.

18. The system of claim 14 , wherein the method further comprises the steps of: reading a record from a node by a user, the record having data that the user desires to delete; and

marking the record for deletion by updating a delete-indicator within the record.

19. The system of claim 14 , wherein the step of marking further includes marking the record with a delete-timestamp.

20. The system of claim 14 , wherein the method further comprises the steps of:

executing a computer software program to inspect the delete-timestamp; and

if the delete-timestamp falls within a pre-determined time frame, then delete the record.

Assignments (10)