Consistent Cut

ConsistentCut is a distributed algorithm that splits WAL on 2 global areas - Before and After. It guarantees that every transaction committed Before also will be committed Before on every other node participated in the transaction. It means that an Ignite nodes can safely recover themself to the consistent Before state without any coordination with each other.

The border between Before and After areas consists of two WAL records - ConsistentCutStartRecord and ConsistentCutFinishRecord. It guarantees that the Before consists of:

1. Transactions committed before ConsistentCutStartRecord AND weren't included into ConsistentCutFinishRecord#after().
2. Transactions committed between ConsistentCutStartRecord and ConsistentCutFinishRecord AND were included into ConsistentCutFinishRecord#before().

On the picture below the Before area consist of transactions colored to yellow, while After is green.

/** */
public class ConsistentCutStartRecord extends WALRecord {
	/** Consistent Cut ID. */
	private final UUID cutId;
}


/** */
public class ConsistentCutFinishRecord extends WALRecord {
	/** Consistent Cut ID. */
	private final UUID cutId;

    /**
     * Collections of transactions committed BEFORE.
     */
    private final Set<GridCacheVersion> before;

     /**
     * Collections of transactions committed AFTER.
     */
    private final Set<GridCacheVersion> after;
 }

Algorithm

Picture bellow illustrates steps of the algorithm on single node:

1. Initial state:
   
   1. No concurrent ConsistentCut process is running.
   2. lastFinishedCutId holds previous ConsistentCutId, or null.
2. User starts a command for creating new incremental snapshot:
   1. Ignite node inits a DistributedProcess with discovery message SnapshotOperationRequest that holds new ConsistentCutId (goal is to notify every node in a cluster about running incremental snapshot). 
   2. DistributedProcess store the topology version topVer on which ConsistentCut started.
3. Process of creation of incremental snapshot can be started by two events (what will happen earlier):
   1. Receive the SnapshotOperationRequest#ConsistentCutId by DiscoverySPI (by the DistributedProcess).
   2. Receive the ConsistentCutAwareMessage#ConsistentCutId by CommunicationSPI (by transaction messages - Prepare, Finish).
4. On receiving the ConsistentCutId, every node: 
   1. Checks whether ConsistentCut has already started (ConsistentCut is running) or finished (lastFinishedCutId == id) for this id, skip if it has.
   2. In case ConsistentCut is inited by CommunicationSPI then compare the ConsistentCutAwareMessage#topVer with local node order:
      1. Local node order equals to new topVer on the moment when node joined to a cluster.
      2. If the order is higher than ConsistentCut topVer it means the node joined after ConsistentCut started. Skip start ConsistentCut on this node.
   3. In the message thread atomically inits ConsistentCut:
      1. creates new ConsistentCut future.
      2. creates committingTx (Goal is to not miss transactions. This collection doesn't remove transactions unlike IgniteTxManager#activeTx does).
      3. starts wraps outgoing messages to ConsistentCutAwareMessage (contains ConsistentCutId).
   4. In the background thread:
      
      1. Writes a ConsistentCutStartRecord  to WAL with the received ConsistentCutId.
      2. Creates a copy (weakly-consistent) of IgniteTxManager#activeTx. Set listeners on those tx#finishFuture.
         1. For optimization it's safely exclude transactions that tx#status == ACTIVE. It's guaranteed that such transactions belongs After side.
      3. Creates a copy of committingTxs (contains transactions that are might be cleaned from IgniteTxManager#activeTx). Set listeners on those tx#finishFuture.
      4. Set committingTxs to null.
5. While the DistributedProcess  is running every node wraps outgoing transaction messages (Prepare, Finish) to ConsistentCutAwareMessage (if transaction has not committed yet on sender node) or ConsistentCutAwareTxFinishMessage (if transaction has committed on a sender node). Messages contain info:
   1. ConsistentCutId (to trigger ConsistentCut  on remote node, if not yet).
   2. ConsistentCutAwareTxFinishMessage messages contains additionally txCutId. It set on the node that commits first (if null then transaction starts committing Before Consistent Cut started, otherwise After):
      1. For 2PC it is an originated node.
      2. For 1PC it is a backup node.
6. Fills committingTxs if ConsistentCut is running and committingTxs is not null:
   1. Every transaction is added into committingTxs right before it is removed from IgniteTxManager#activeTx.
7. For every receiving ConsistentCutAwareTxFinishMessage Ignite marks the related transaction with message#txCutId before it starts handling the received message.
8. For every listening transaction, the callback is called when transaction finished:
   

   1. check If transaction state is UNKNOWN or status is RECOVERY_FINISH, then complete ConsistentCut with exception.

   2. If transaction mapped to a higher topology version than ConsistentCut topVer, then put it into after (topology changed after ConsistentCut started).
   3. if tx#txCutId equals to local, then put transaction into after, otherwise put into before.
9. After every listening transaction finished:
   1. Writes a ConsistentCutFinishRecord  into WAL with the collections ( before, after ). 
   2. Completes ConsistentCut  future.
   3. Note, that it continues to wrap messages even after local ConsistentCut finish.
10. After ConsistentCut finish, DistributeProcess automatically notifies a node-initiator about local procedure has finished.
11. After all nodes finished ConsistentCut, on every node:
    
    1. Updates lastFinishedCutId with the current id.
    2. ConsistentCut  future becomes null.
    3. Stops signing outgoing transaction messages.
12. Node initiator checks that every node completes correctly.
    1. If any node complete exceptionally - complete Incremental Snapshot with exception.

Consistent and inconsistent Cuts

Consistent Cut is such cut that correctly finished on all baseline nodes - ConsistentCutStartRecord  and ConsistentCutFinishRecord  are written.

"Inconsistent" Cut is such a cut when one or more baseline nodes hasn't wrote ConsistentCutFinishRecord . It's possible in cases:

1. any errors appeared during processing local Cut.
2. if a transaction is recovered with transaction recovery protocol (tx.finalizationStatus == RECOVERY_FINISH).
3. if transaction finished in UNKNOWN state.
4. topology change

Wrapping messages

On the picture below on left side is a diagram of sending transaction messages. Before sending message it checks whether cut is running. If it is then wraps the message, otherwise send ordinary message (PrepareRequest in example).

Ignite transaction protocol includes multiple messages. But only some of them affects meaningful (relating to the algorithm) that change state of transactions (PREPARED, COMMITTED):

1. GridNearTxPrepareRequest / GridDhtTxPrepareRequest
2. GridNearTxPrepareResponse / GridDhtTxPrepareResponse

3. GridNearTxFinishRequest / GridDhtTxFinishRequest

Those messages are wrapped in ConsistentCutAwareMessage  that is prepared right before sending message on other node. They used the current ConsistentCutId.

class ConsistentCutAwareMessage {
	/** Original transaction message. */
	Message msg;

	/** Consistent Cut ID. */
	UUID cutId;

	/** Cluster topology version on which Consistent Cut started. */
	long topVer;
}

Also some messages require to be combine with additional ConsistentCutId to check it them on primary/backup node.

1. GridNearTxFinishRequest / GridDhtTxFinishRequest
2. GridNearTxPrepareResponse / GridDhtTxPrepareResponse (for 1PC algorithm).

Those messages are wrapped in ConsistentCutAwareTxFinishMessage  that is prepared right before transaction starts committing on first committing node. They used the current ConsistentCutId for this setting. If current ConsistentCutId is not null, then transaction starts committing after ConsistentCut started and it means that this transaction belongs the After side. 

class ConsistentCutAwareTransactionFinishMessage extends ConsistentCutAwareMessage {
	/** Consistent Cut ID after which transaction committed. */
    @Nullable UUID txCutId;
}

Links

1. ON DISTRIBUTED SNAPSHOTS, Ten H. LAI and Tao H. YANG, 29 May 1987