...

Picture bellow illustrates steps of the algorithm on single node:

Image Added

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 consistent cut 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: 
Checks whether
5. it starts local ConsistentCut: 
   1. There are 2 roles that node might play:
      1. ROLE#1 - wraps outgoing messages - for all Ignite nodes: client, baseline, non-baseline server nodes.
      2. ROLE#2 - prepares data to be written in WAL - for baseline nodes only.
   2. Before start check:
      1. Whether ConsistentCut has already started (ConsistentCut !=
nullis running
6. 1. 1. null) or finished (lastFinishedCutId == id) for this id, skip if it has.
      2. On non-baseline nodes 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.
   2. ROLE#1:
      1. creates new ConsistentCut future.
         1. If node is  non-baseline (client, non-baseline servers) - complete it right after creation, and notify a node-initiator about local procedure has finished (by DistributedProcess protocol).
      2. While ConsistentCut != null wraps outgoing messages to ConsistentCutAwareMessage. It contains info:
         
         1. ConsistentCutId (to start ConsistentCut  on remote node, if not yet).
         2. Messages contain additional field txCutId. It is originally set on the nodes that commit first:
            1. For 2PC it is an originated node.
            2. For 1PC it is a backup node.
         3. If txCutId equals to null then transaction starts committing Before Consistent Cut started, otherwise After.
      3. On receive ConsistentCutAwareMessage that makes transaction committed (FinishRequest for 2PC, PrepareResponse for 1PC) sets tx#txCutId = message#txCutId.
   3. ROLE#2 - for baseline nodes only:
      1. In the message thread atomically inits ConsistentCut:
         1. creates new ConsistentCut future.
         2. creates empty collection removedActiveTxs (This collection doesn't remove transactions unlike IgniteTxManager#activeTx does).
      2. In the background thread:
         
         1. Writes a
ConsistentCutStartRecord 
7. 1. 1. 1. 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 removedActiveTxs (contains transactions that are might be cleaned from IgniteTxManager#activeTx). Set listeners on those tx#finishFuture.
         4. Set removedActiveTxs to null. We don't care of txs concurrently added to removedActiveTxs, they just don't land into "before" or "after" set and will be excluded from recovery.
Fills
8. 1. 1. In transaction threads fills removedActiveTxs if ConsistentCut
is running and removedActiveTxs is not
9. 1. 1. != null and removedActiveTxs != null:
         1. Every transaction is added into removedActiveTxsright before it is removed from IgniteTxManager#activeTx.
      2. 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.
         3. if tx#txCutId equals to local, then put transaction into after, otherwise put into before.
      3. After every listening transaction finished:
         1. Writes a
ConsistentCutFinishRecord 
10. 1. 1. 1. ConsistentCutFinishRecord  into WAL with the collections ( before, after ). 
          2. Completes
ConsistentCut  future.
11. On non-baseline nodes (clients, non-baseline servers):
1. 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.
2. In the message thread creates completed ConsistentCut future.
12. On all nodes (clients, non-baseline, baseline): 
1. While ConsistentCut != null wraps outgoing messages to ConsistentCutAwareMessage. It contains info:
   
1. ConsistentCutId (to start ConsistentCut  on remote node, if not yet).
2. Some messages sets additional field txCutId. It set on the node that commits first:
1. For 2PC it is an originated node.
2. For 1PC it is a backup node.
3. If txCutId set to null then transaction starts committing Before Consistent Cut started, otherwise After.
2. For receiving ConsistentCutAwareMessage that make transaction committed (FinishRequest for 2PC, PrepareResponse for 1PC) Ignite set tx#txCutId = message#txCutId before it starts handling the received message.
13. 1. 1. 1. ConsistentCut  future.
       2. Notify a node
After ConsistentCut future finish, DistributeProcess automatically notifies a node
14. 1. 1. -initiator about local procedure has finished (by DistributedProcess protocol).
15. After all nodes finished ConsistentCut, on every node:
    
    1. Updates lastFinishedCutId with the current id.
ConsistentCut 
16. 1. ConsistentCut  future becomes null.
    2. Stops signing outgoing transaction messages.
17. Node initiator checks that every node completes correctly.
    1. If any node complete exceptionally - complete Incremental Snapshot with exception.

Consistent and inconsistent Cuts

...

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

...

messages

...

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

...

Code Block
language java title ConsistentCutAwareMessage
class ConsistentCutAwareMessage { /** Original transaction message. */ Message msg; /** Consistent Cut ID. */ UUID cutId; /** Consistent Cut ID after which transaction committed. */ @Nullable UUID txCutId; /** Cluster topology version on which Consistent Cut started. */ long topVer; }

Transaction

A new field added to IgniteInternalTx

class IgniteInternalTx {     
    /**
     * @param ID of {@link ConsistentCut} AFTER which this transaction was committed, {@code null} if transaction
     *           committed BEFORE.
     */
    public void cutId(@Nullable UUID id);
}

Consistent Cut Classes

// Class is responsible for managing all stuff related to Consistent Cut. It's an entrypoint for transaction threads to check running consistent cut.
class ConsistentCutManager extends GridCacheSharedManagerAdapter {               
    // Current Consistent Cut. All transactions threads wraps outgoing messages if this field is not null.  */
    volatile @Nullable ConsistentCut cut;
	
	// Entrypoint for handling received new Consistent Cut ID.
	void handleConsistentCutId(UUID id);
}

class ConsistentCut extends GridFutureAdapter<WALPointer> {          
	Set<GridCacheVersion> beforeCut;

    Set<GridCacheVersion> afterCut;

    Set<IgniteInternalFuture<IgniteInternalTx>> removedActive;
}

Links

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