Page History

Definitions

Paper [1] defines a distributed snapshot algorithm. It uses some definitions, let's describe them in terms of Ignite:

1. Message  - transaction message (...FinishRequest for 2PC, ...PrepareResponse for 1PC)
   1. it is guaranteed that it's sent after all transaction DataRecords are written into WAL on sending node.
2. Channel  - TCP communication connection from one node to another, by that the Messages is sent.
3. ChannelState  - for single channel it's a set of Messages that was sent, but not committed yet on receiver.
   1. In Ignite we can think that ChannelState is represented by active transactions in PREPARING, and greater, states.
4. IncrementalSnapshot  - on Ignite node it is represented with 2 WAL records (ConsistentCutStartRecord  commits the WAL state, ConsistentCutFinishRecord  describes the ChannelState ). It guarantees that every node in cluster includes in the snapshot:
   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() .
5. Marker  - mark that piggy backs on the Message, and notifies a node about running snapshot.

   1. After IS start and before finish all PrepareRequest , FinishRequest  are wrapper by ConsistentCutMarkerMessage  instead of regular Message . This is done to notify target node ⁣⁣via communication channel about running IS .

6. Consistent Cut  - Successful attempt of creating IncrementalSnapshot.
7. Inconsistent Cut  - Failed attempt of creating a IncrementalSnapshot, due to inability to correctly describe a ChannelState .

Note, ConsistentCut  can't guarantee that specific transaction that runs concurrently with the algorithm will land before or after cut, it only guarantees that set of the transactions before(or after) the cut will be the same on the each node in cluster.

Algorithm

...

1. Initial state:
   1. Ignite WAL are in consistent state relatively to previous full or incremental snapshot.
   2. Every Ignite node has local ConsistentCut  future equals to null.
   3. Empty collection committingTxs  that goal is to track COMMITTING+ transactions, that aren't part of IgniteTxManager#activeTx.
2. User starts a command for creating new incremental snapshot:
   1. Ignite node inits
   a IncrementalSnapshot, by starting DistributedProcess  with
   1. a DistributedProcess with special message holds new ConsistentCutMarker .
3. Process of creation of incremental snapshot can be started by two events (what will happen earlier):
   1. Receive the ConsistentCutMarker by discovery.
   2. Receive the ConsistentCutMarker by transaction message (Prepare, Finish)
4. On receiving the marker, every node: 
   1. In message thread atomically
   Every nodes starts a local snapshot process after receiving the marker message (whether by discovery, or by communication with transaction message) 
   1. Atomically: creates new ConsistentCut  future, creates committingTxscreates committingTxs, starts signing outgoing messages with the ConsistentCutMarker .
   2. In background thread:
      Write
      1. Writes a ConsistentCutStartRecord  to WAL with the received ConsistentCutMarker .
      Collect of
      1. Collects active transactions - concat of IgniteTxManager#activeTx and committingTxs
        Prepares 2 empty collections - beforeandafter
      1.  
      cut (describes ChannelState )
      1. .
   3. While global ConsistentCut  is running every node signs output transaction messages:
      1. Prepare messages signed with the ConsistentCutMarker  (to trigger ConsistentCut  on remote node, if not yet).
      2. Finish messages signed with the ConsistentCutMarker  (to trigger...) and transaction ConsistentCutMarker  (to notify nodes which side of cut this transaction belongs to).
      3. Finish messages is signed with transaction ConsistentCutMarker on node that commits first (near node for 2PC, backup or primary for 1PC).
   4. For every collected active transaction, node waits for Finish message, to extract the ConsistentCutMarker  and fills prepares before , after  collections:
      1. if received marker is null or differs from local, then transaction on before  side
      2. if received color equals to local, then transaction on after  side
   5. After all transactions finished:
      1. Writes a ConsistentCutFinishRecord  ConsistentCutFinishRecord  into WAL with ChannelState the collections ( before, after ). 
      2. Stops filling committingTxs .
      3. Completes ConsistentCut  future, and notifies a node-initiator about finishing local procedure (with DistributedProcess  protocol).
   6. After all nodes finished ConsistentCut , :
      1. every node stops signing outgoing transaction messages
      -
      2. ConsistentCut  future becomes null.

   Consistent and inconsistent Cuts

   ...