EXECUTING DISTRIBUTED GLOBALLY-ORDERED TRANSACTIONAL WORKLOADS IN REPLICATED STATE MACHINES

• US 20140310240A1
• Filed: 09/11/2013
• Published: 10/16/2014
• Est. Priority Date: 04/15/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: ZHANG, LI, MENG, SHICONG
• Granted Patent: US 9,465,650 B2
• Time in Patent Office: Days
• US Class Current: 707/615
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

A method of transaction replication includes transmitting at least one transaction received during an epoch from a local node to remote nodes of a domain of 2N+1 nodes at the end of an epoch (N is an integer greater than or equal to 1). The remote nodes log receipt of the at least one transaction, notify the local node of the receipt of the at least one transaction, transmit the at least one transaction to all of the 2N+1 nodes, and add the at least one transaction to an execution order upon receiving at least N+1 copies of the at least one transaction.

Claims

1. A computer readable storage medium embodying instructions executed by a processor to perform a method of transaction replication, comprising:

transmitting at least one transaction received during an epoch, by a local datastore node, to at least one remote datastore node of a plurality of remote datastore nodes upon an end of the epoch, wherein the epoch corresponds to a predefined time period having a fixed length, and the local datastore node and the plurality of remote datastore nodes are part of a domain of 2N+1 datastore nodes, wherein N is an integer greater than or equal to 1;

logging a receipt of the at least one transaction, by the at least one remote datastore node, upon receiving the at least one transaction at the at least one remote datastore node;

notifying the local datastore node of the receipt of the at least one transaction, by the at least one remote datastore node, upon receiving the at least one transaction at the at least one remote datastore node;

transmitting the at least one transaction to all datastore nodes in the domain other than the local datastore node and the at least one remote datastore node, by the at least one remote datastore node, upon receiving the at least one transaction at the at least one remote datastore node; and

adding the at least one transaction to an execution order, at each of the datastore nodes of the domain, upon receiving at least N+1 copies of the at least one transaction at each of the datastore nodes.

2. The computer readable storage medium of claim 1, further comprising:

measuring an elapsed time, by the at least one remote datastore node, since last logging the receipt of the at least one transaction;

transmitting a timeout message to all datastore nodes in the domain, by the at least one remote datastore node, upon the elapsed time exceeding a predefined timeout threshold;

transmitting a timeout confirmation message to all datastore nodes in the domain, by each of the datastore nodes of the domain, upon receiving at least N+1 timeout confirmation messages regarding the local datastore node at each of the datastore nodes; and

removing the local datastore node from a participating datastore node list, by each of the datastore nodes of the domain, upon receiving at least N+1 timeout confirmation messages regarding the local datastore node at each of the datastore nodes.

3. The computer readable storage medium of claim 2, further comprising:

discarding unfinished processes that have occurred prior to removal from the participating datastore node list, by the local datastore node, upon being removed from the participating datastore node list;

transmitting a recovery notification message, to each of the datastore nodes in the domain, by the local datastore node; and

adding the local datastore node to the participating datastore node list, by each of the datastore nodes of the domain, upon each of the datastore nodes receiving at least N+1 copies of the recovery notification message.

4. The computer readable storage medium of claim 3, wherein the local datastore node is added to the participating datastore node list by each of the datastore nodes of the domain during different epochs.

5. The computer readable storage medium of claim 1, further comprising:

generating a local signature corresponding to the local datastore node, by the local datastore node;

transmitting the local signature, by the local datastore node, to all datastore nodes in the domain;

generating a remote signature corresponding to the at least one remote datastore node, by the at least one remote datastore node;

transmitting the remote signature, by the at least one remote datastore node, to all datastore nodes in the domain;

transmitting a signature mismatch notification linked to the remote signature, by the at least one remote datastore node, to the local datastore node upon determining that the remote signature does not match the local signature; and

disconnecting the local datastore node from the domain of datastore nodes upon the local datastore node receiving at least N+1 signature mismatch notifications linked to the remote signature.

6. The computer readable storage medium of claim 5, further comprising:

restoring the disconnected local datastore node using the remote signature.