Conflict resolution in database replication through autonomous node qualified folding

• US 7,627,611 B2
• Filed: 08/17/2007
• Issued: 12/01/2009
• Est. Priority Date: 08/17/2006
• Status: Active Grant

• Current Assignee: OSISoft Incorporated (Schneider Electric SE)
• Original Assignee: OSISoft Incorporated (Schneider Electric SE)
• Inventors: Gusciora, Paul H.
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): ORTIZ DITREN, BELIX M
• Application Number:
  US11/893,988
• Publication Number:
  US 20080052322A1
• Time in Patent Office: 837 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

In a method for distributed database replication, local change records describing the local changes to the database at a node are transmitted to other nodes. Each node receives from the other nodes other change records describing changes to the database at the other nodes, and a log of change records is accumulated. Each change record describes a change made to a row at a source node, e.g., using data such as an identifier of the source node, a source node abstract clock value, a row identifier, and cell values of the row before and after the change. Autonomously from the other nodes, each node applies the other change records to its local copy of the database, considering the other change records in source node abstract clock order. The other change records are applied by checking for a collision between the other change records and the database and, when a collision is detected, selecting a persistent result by sequentially scanning through the log of change records in order of local abstract clock value to identify the persistent result.

Claims

1. A computer-implemented method implemented in each node of a distributed database system comprising multiple nodes, the method comprising:

storing a database, wherein the database is a local copy of a distributed database;

maintaining a local abstract clock value;

accepting local changes to the database;

incrementing the local abstract clock value each time a local change is accepted;

transmitting to other nodes local change records describing the local changes to the database;

receiving from the other nodes other change records describing changes to the database at the other nodes;

accumulating a log of change records, wherein the change records comprise the local change records and the other change records, wherein each change record describes a change made to a row at a source node, wherein each change record comprises an identifier of the source node, a source node abstract clock value, a row identifier, a row version number, and cell values of the row before and after the change;

autonomously applying the other change records to the database, wherein the other change records are considered in source node abstract clock order, wherein autonomously applying the other change records comprises detecting a collision between the other change records and the database and, when a collision is detected, selecting a persistent result,

wherein selecting a persistent result comprises, for each change record, sequentially scanning through the log of change records in order of local abstract clock value to identify the persistent result.

2. The method of claim 1 wherein detecting a collision comprises checking if a record in the database has values that match original values for the identifier of a source node, a source node abstract clock value, a row identifier, a row version number, and changed cell values of a change record under consideration.

3. The method of claim 1 wherein scanning through the log of change records comprises identifying a changed record matching values of a change record being considered.

4. The method of claim 3 wherein scanning through the log of change records further comprises discarding the change record being considered if the identified change record changed a column value changed by the change record being considered.

5. The method of claim 1 wherein selecting a persistent result comprises, for a change record being considered, selecting a currently existing value in the database if the change record being considered is discarded by the scanning through the log of change records.

6. The method of claim 1 wherein selecting a persistent result comprises, for a change record being considered, selecting a new value from the change record being considered if the change record being considered is not discarded by the scanning through the log of change records.

7. The method of claim 1 wherein selecting the persistent result comprises, if there is a tie between multiple other change records, breaking the tie by calculating a weighted parameterized function to select a winning change record, wherein the weighted parameterized function includes a predetermined time threshold.

8. The method of claim 1 further comprising maintaining, for each of the other nodes, a highest value of a source abstract clock value of other change records received from the other nodes.

9. The method of claim 1 further comprising receiving a request for a list containing a highest value of a source abstract clock value for each of the other nodes, and transmitting the list in response to the request.

10. The method of claim 1 further comprising transmitting to another node a request for change records whose abstract clock values are greater than a specified value.

11. The method of claim 1 further comprising forwarding the received other change records to one or more nodes.

12. The method of claim 1 further comprising transmitting to the other nodes change records describing changes to the database resulting from the applying of the other change records to the database.

13. The method of claim 1 further comprising receiving from another node a request for change records whose abstract clock values are greater than a specified value and transmitting to the another node local change records satisfying the request.

14. The method of claim 1 wherein each change record further comprises a time stamp indicating a time of the change made to the row at the source node.