System and method for replication of distributed databases that span multiple primary nodes

• US 20020184239A1
• Filed: 06/01/2001
• Published: 12/05/2002
• Est. Priority Date: 06/01/2001
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Johnson, Charles S., Mosher, Malcolm Jr.
• Granted Patent: US 6,785,696 B2
• Time in Patent Office: Days
• US Class Current: 707/200
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A method and system for backing up primary nodes onto backup nodes where the primary nodes can each originate a distributed transaction and can participate in a distributed transaction. The backup nodes, after a primary node failure, undo all transactions whose state is unknown on the backup node and all committed transactions which, if kept, would lead to an inconsistent set of backup nodes. First, committed transactions are undone if commits for them were not received on all back up nodes to the primary nodes that participated in the transaction. Second, all committed transactions that potentially depend on the committed transactions that were undone are also undone. Only those transactions that are provably independent of the committed transactions that were undone are kept. The result is a set of back up nodes which can support operations until the failing primary node is restored.

Claims

1. A method of backing up a distributed database system including a plurality of primary nodes, each with a database and transaction monitor, each primary node configured to participate in at least one distributed transaction, and each primary node having a backup node with a database, the method comprising:

performing a local backup operation on the database of each backup node to leave on the backup node'"'"'s database only those transactions received as committed or aborted from the backup node'"'"'s primary node; and

performing a global backup operation to undo any committed transaction whose presence causes the backup nodes to primary nodes that participated in the distributed transaction to be inconsistent.

2. A method of backing up a distributed database system as recited in claim 1, wherein the step of performing a global backup operation includes:

finding a common synchronization point among the backup nodes;

producing for each backup node a local commit list that contains all transactions received as committed on each backup node from the common synchronization point through the last committed transaction received on the backup node;

modifying the local commit list at each backup node to mark as undo

(i) committed transactions that are not fully committed and

(ii) committed transactions that are potentially dependent on transactions not fully committed;

forming a network undo list based on the modified local commit list; and

undoing the updates for those transactions in the network undo list.

3. A method of backing up a distributed database system as recited in claim 2, wherein the step of modifying the local commit list at each backup node includes determining which transactions in the local commit list at each node did not commit on all the primary nodes that participated in the distributed transaction and marking them for undo.

4. A method of backing up a distributed database system as recited in claim 2, wherein the step of modifying the local commit list at each backup node includes determining whether a candidate committed transaction subsequent to a non-fully committed transaction in a local commit list is potentially dependent on transaction not fully committed by:

obtaining from each of the participating nodes of the transaction the order of commits of the transaction not fully committed and the candidate committed transaction; and

detecting whether the order of commits is different at any of the participating nodes; and

if the order of commits is not different on at least one participating node, marking the candidate transaction as undo.

5. A method of determining potential dependency of a second transaction on a first transaction, at least two transaction nodes participating in each transaction, the method comprising:

obtaining a first list of the participating nodes of the first transaction;

obtaining a second list of participating nodes of the second transaction, wherein each node participating has an ordered list of transactions that committed on the node; and

if at least one node is common to both lists;

determining an order of commits of the first and second transactions a selected common node based the ordered list of transactions at the selected node;

for each other node common to both lists;

determining an order of commits of the first and second transactions at the other common node based on the ordered list of transactions at the other common node; and

comparing the order of commits of the first and second transaction at the other common node with the order of commits of the two transactions at the selected common node;

if the order of commits at any other common node is different from the order of commits at the selected common node, declaring that the second transaction does not depend on the first transaction; and

otherwise, declaring that there is a potential dependency of the second transaction on the first transaction.

6. A method of providing a common synchronization point to a plurality of nodes of a distributed transaction system, each node having a master audit trail and one of the primary nodes being designated a master node of the distributed transaction system, comprising:

starting a timer;

upon the lapse of a timer, performing a distributed update transaction of a network synchronization file on each primary node by a process on the network master, the synchronization file containing a counter value field that contains a count of the number of distributed update transactions to the synchronization file, a current transaction field for identifying the distributed update transaction that was last counted by the counter field and a previous transaction field for identifying the distributed update transaction prior to the transaction identified in the current transaction field;

committing the distributing update transaction, whereby a commit record is placed in the audit trail for each of the primary nodes; and

continuing at the step of starting the timer.