Method and system for discarding locally committed transactions to ensure consistency in a server cluster

• US 6,449,734 B1
• Filed: 04/17/1998
• Issued: 09/10/2002
• Est. Priority Date: 04/17/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shrivastava, Sunita, Vert, John D.
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): Backer, Firmin
• Application Number:
  US09/062,211
• Time in Patent Office: 1,607 Days
• Field of Search: 714/15, 714/4, 714/38, 714/51, 370/60, 707/10, 707/202, 707/203, 707/204, 707/511, 707/8, 709/219, 709/223, 709/24
• US Class Current: 714/15
• CPC Class Codes: G06F 11/1425 by reconfiguration of node membership
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A method and system for forming a new cluster of servers having state data that is consistent with the state data of a cluster that previously existed. The previous cluster preserves its state data by recording transactions to a log file in conjunction with a sequence number maintained by each node. The node that recorded the transaction then increments its copy of the sequence number and attempts to replicate the transaction to other nodes of the cluster. If the transaction is replicated, each other node commits the transaction and increments its sequence number. If the node fails before it can replicate the transaction, then no other nodes will increment their sequence numbers, whereby the next logged transaction has the same sequence number as the previously logged, but orphaned replicated transaction. When a new node forms a cluster, it unrolls the log file so as to become consistent with the state of the previous cluster. Logged transactions having duplicate sequence numbers indicate that the first such transaction was not fully replicated. To remain consistent, the first transaction is discarded and not used to update the state of the new cluster.

Claims

1. In a cluster of nodes, a method of recording and retrieving cluster modification data, comprising, associating a sequence number with each set of cluster modification data, recording each set of modification data in association with the sequence number at a log on a common storage device that is accessible to each node capable of forming a new cluster, adjusting the sequence number at each node each time that modification data is successfully replicated to that node, detecting unsuccessfully replicated sets of modification data by retrieving sets of modification data with the sequence number associated therewith from the log on the common storage device, and for each set of modification data retrieved, if the sequence number associated therewith is unique within the log, updating data of a node with the modification data from the log, and if the sequence number is not unique within the log and thereby indicative of at least one unsuccessful replication, determining which set of modification data associated with that sequence number was recorded later in time, and updating data of the node with the later recorded modification data.

2. The method of claim 1 wherein adjusting the sequence number comprises incrementing the sequence number.

3. The method of claim 1 wherein each set of modification data comprises a transaction.

4. The method of claim 3 wherein two transactions have a duplicate sequence number associated therewith, and wherein determining which set of modification data associated with the sequence number was recorded later in time includes discarding the first of the two transactions.

5. The method of claim 3 wherein determining which set of modification data associated with the sequence number was recorded later in time includes reading a current transaction and a transaction recorded immediately thereafter, determining the sequence numbers associated with each transaction, comparing the sequence numbers with one another, and if the sequence numbers are the same, discarding the current transaction.

6. The method of claim 1 further comprising forming a new cluster.

7. The method of claim 6 wherein a node forming the new cluster retrieves the sets of modification data from the log on the common storage device and updates locally maintained modification data with the modification data from the log.

8. The method of claim 1 wherein recording each set of modification data comprises writing the modification data to the log on the common storage device in a sequential order.

9. The method of claim 1 wherein retrieving the sets of modification data comprises reading the modification data from the log on the common storage device.

10. The method of claim 1 wherein retrieving the sets of modification data comprises determining a starting point up to which the cluster data of a node is consistent with the modification data, and retrieving the modification data based on the starting point.

17. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

11. A system for forming a new cluster of nodes having state data that is consistent with the state data of a previous cluster of nodes, comprising:

a storage device having a log file thereon accessible by at least one of the nodes of the previous cluster and a node forming the new cluster;

the previous cluster including a plurality of nodes, a mechanism for replicating transactions comprising cluster state data to each of the nodes, a mechanism for recording transactions to the log file, each transaction recorded in conjunction with a sequence number provided by a node associated with that transaction, and each node including a mechanism for adjusting a value of the sequence number in response to a transaction committed thereby; and

the node forming the new cluster including a process for reading the log file and updating the cluster state data of said node based on the transactions in the log file, the process using one transaction per sequence number by comparing the sequence numbers of the transactions recorded in the log file and detecting and handling a partially committed transaction by discarding any transaction therein that precedes another transaction having the same sequence number.

12. The system of claim 11 wherein the storage device comprises a quorum resource.

13. The system of claim 11 wherein each node of the previous cluster includes a copy of the sequence number, and wherein the mechanism for adjusting the sequence number increments the copy of the sequence number therein.

14. The system of claim 11 wherein the new node includes a database for maintaining the cluster state data.

15. The system of claim 11 wherein the mechanism for replicating transactions includes the global update protocol and wherein at least one of the nodes is a locker node.

16. A method for forming a new cluster of nodes having state data that is consistent with the state data of a previous cluster of nodes, comprising:

preserving the state data of the previous cluster by;

recording transactions comprising state data information to a log file in conjunction with a sequence number provided by a node associated with that transaction;

replicating at least some of the transactions comprising cluster state data to each of the nodes, each node having a transaction replicated thereto committing each transaction and adjusting a local copy of the sequence number; and

,

forming a new cluster at a new node by;

reading the log file;

comparing the sequence numbers of the transactions recorded in the log file to detect transactions that were not replicated to each node of the previous cluster;

discarding any transaction in the log file that precedes another transaction having the same sequence number; and

updating the cluster state data of the new node based on the transactions that were not discarded.

18. A computer-readable medium having computer-executable instructions for performing the method of claim 16.

19. A method of forming a new cluster at a node, comprising, accessing sequence numbers associated with sets of state data logged by at least one other node of a previous cluster, selecting at least two of the sequence numbers, evaluating the sequence numbers selected to determine whether any of the sequence numbers are similar, and if so, taking action with respect to at least one set of state data associated with the similar numbers to ensure that the new cluster state is consistent with the previous cluster state.

20. The method of claim 19 wherein taking action includes discarding at least one set of state data preceding a set of state data associated with the similar numbers, and using non-discarded state data.

21. The method of claim 19 wherein selecting at least two of the sequence numbers includes maintaining a checkpoint, and looking for identical sequence numbers based on the checkpoint.

22. The system of claim 21 further comprising a checkpoint maintained by the node forming the later cluster, wherein the node forming the later cluster detects information by examining the sequence numbers in the log based on the checkpoint.

23. The system of claim 21 wherein the node forming the later cluster is configured to take action by maintaining the information associated with a last logged sequence numbers of the similar sequence numbers in the log.

24. The system of claim 21 wherein the log is maintained on a quorum resource.