Consistent Cut

ConsistentCut splits timeline on 2 global areas - BEFORE and AFTER. It guarantees that every transaction committed BEFORE also will be committed BEFORE on every other node. It means that an Ignite node can safely recover itself to this point without any coordination with other nodes.

Algorithm

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.
User starts a command for creating new incremental snapshot:
1. Ignite node inits a DistributedProcess with special message holds new ConsistentCutMarker .
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)
On receiving the marker, every node:
1. In message thread atomically: creates new ConsistentCut future, creates committingTxs, starts signing outgoing messages with the ConsistentCutMarker .
2. In background thread:
  1. Writes a ConsistentCutStartRecord to WAL with the received ConsistentCutMarker .
  2. Collects active transactions - concat of IgniteTxManager#activeTx and committingTxs .
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.
For every collected active transaction, node waits for Finish message, to extract the ConsistentCutMarker and 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
After all transactions finished:
1. Writes a ConsistentCutFinishRecord into WAL with the collections ( before, after ).
2. Stops filling committingTxs .
3. Completes ConsistentCut future, and notifies a node-initiator about finishing local procedure (with DistributedProcess protocol).
After all nodes finished ConsistentCut :
1. every node stops signing outgoing transaction messages
2. ConsistentCut future becomes null.
3. Ignite node now in the initial state again.

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:

any errors appeared during processing local Cut.
if a transaction is recovered with transaction recovery protocol (tx.finalizationStatus == RECOVERY_FINISH).
if transaction finished in UNKNOWN state.
baseline topology change, Ignite nodes finishes local Cuts running in this moment, making them inconsistent.

ConsistentCutMarker

Every ignite nodes tracks current ConsistentCutMarker :

ConsistentCutVersion

class ConsistentCutMarker {
	UUID id;
}

id is just a unique ConsistentCut ID (is assigned on the node initiator).

Signing 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):

GridNearTxPrepareRequest / GridDhtTxPrepareRequest
GridNearTxPrepareResponse / GridDhtTxPrepareResponse
GridNearTxFinishRequest / GridDhtTxFinishRequest

Also some messages require to be signed with ConsistentCutMarker to check it them on primary/backup node:

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

WAL records

There are 2 records: ConsistentCutStartRecord for Start event and ConsistentCutFinishRecord for Finish event.

ConsistentCutStartRecord: record is written to WAL in moment when CC starts on a local node. It helps to limit amout of active transactions to check. But there is no strict guarantee for all transactions belonged to the BEFORE side to be physically committed before ConsistentCutStartRecord, and vice versa. This is the reason for having ConsistentCutFinishRecord.
ConsistentCutFinishRecord: This record is written to WAL after Consistent Cut stopped analyzing transactions and storing them in a particular bucket (BEFORE or AFTER).

It guarantees that the BEFORE side consist 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().

It guarantees that the AFTER side consist of:
1. transactions physically committed before ConsistentCutStartRecord and were included into ConsistentCutFinishRecord#after();
2. transactions physically committed after ConsistentCutStartRecord and weren't included into ConsistentCutFinishRecord#before().

ConsistentCutRecord

/** */
public class ConsistentCutStartRecord extends WALRecord {
	/** Marker that inits Consistent Cut. */
	private final ConsistentCutMarker marker;
}


/** */
public class ConsistentCutFinishRecord extends WALRecord {
    /**
     * Collections of TXs committed BEFORE the ConsistentCut (sent - received).
     */
    private final Set<GridCacheVersion> before;

     /**
     * Collections of TXs committed AFTER the ConsistentCut (exclude).
     */
    private final Set<GridCacheVersion> after;
 }

Unstable topology

There are some cases to handle for unstable topology:

Client or non-baseline server node leaves – no need to handle.
Server node leaves:
1. all nodes finish local running ConsistentCut, making them in-consistent
Server node joins:
1. all nodes finish local running ConsistentCut, making them in-consistent
2. new node checks whether rebalance was required for recovering. If it is required, then handle it TBD

TBD: Which ways to use to avoid inconsistency between data and WAL after rebalance. There are options:

First solution: set flag ConsistentCutManager#inconsistent to true , and persist this flag within local MetaStorage.
1. On receiving new ConsistentCutVersion check the flag and raise an exception.
2. Clean flag on recovering from ClusterSnapshot, or after creating a ClusterSnapshot.
3. + Simple handling in runtime.
4. - Need to rebalance a single node after PITR with file-based (or other?) rebalance: more time for recovery, file-based rebalance has not-resolved issues yet(?).
Do not disable WAL during rebalance:
+ WAL now is consistent with data, can use it for PITR after rebalancing
- Too many inserts during rebalance may affect rebalance speed, IO utilization
Automatically create snapshots for rebalancing cache groups:
+ Guarantee of consistency (snapshot is created on PME, after rebalance).
+ Faster recovery.
- Complexity of handling - Ignite should provide additional tool for merging WAL and multiple snapshots created in different time
? is it possible to create snapshot only on single rebalanced node?
? Is it possible to sync current PME (on node join) with starting snapshot?
Write a special Rebalance record to WAL with description of demanded partition:
1. During restore read this record and repeat the historical rebalance at this point, after rebalance resume recovery with existing WALs.
2. In case Record contains full rebalance - stops recovering with WAL and fallback to full rebalance.
  ? Is it possible to rebalance only specific cache groups, and continue to WAL recovery for others.
  - For historical rebalance during recovery need separate logic for extracting records from WAL archives from other nodes.

Links

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

Page tree