Atomicity in the Distributed Systems

As per wikipedia,

Atomicity is one of the ACID transaction properties in the database systems. An atomic transaction is indivisible and irreducible series of database operations such that either all occur, or none occur.

Atomicity in single node systems

For a single node database systems, the atomicity is usually achieved by using write-ahead logs (WAL) provided by their storage service. Any transaction that is committed will be first commited to the log on the disk before it is applied to its internal structure. In this way, if the database systems crash, then they recover the data from its log system.

Atomicity helps the database systems to stay consistent. Without it, half-committed transactions can leave the database in an inconsistent state. Infact, the C and I relies on atomicity to abort the transaction in case of consistency or isolation violation.

Atomicity in distributed systems

However in case of multiple node database systems, there are a number of factors which can make it very hard to implement atomicity.

1. Transactions can be done over multiple objects over the multiple partitions over multiple nodes.
2. Some nodes may crash before committing the transaction.
3. Transaction might be committed on some nodes which may lead to inconsistency b/w replicas.

A lot can happen in the distributed systems and ensuring atomicity is a challenge. However a lot of research has been done to overcome the issues. There are two ways in which one can implement atomicity in distributed systems,

Two-phase commit (2PC)

Two-phase commit achieves atomic transactions over multiple nodes in a three step manner. It uses coordinator which is normally implemented on the client application and a number of participants.

1. Normal read/write operation: Client application will read/write data from/to the participants using a transaction ID provided at the beginning.
2. Prepare phase: Coordinator will ask the participants to prepare and participants reply Yes to indicate that they are ready to commit.
3. Commit/Abort Phase: If coordinator detects that all the participants have replied Yes, it will then ask the participants to commit. If any of them replies no, the coordinator will ask the participants to abort the transaction.

Fault tolerance If any of the participants crash before the prepare phase, the transaction will be aborted and will be retried until the node becomes available again. If participant succeeds in the prepare phase but fails in the commit or abort phase, then the coordinator will keep on retrying indefinitely until the participant succeeds to preserve the atomicity guarantee.

However, if the coordinator itself crashes before the commit or abort phase, the participants are left in a uncertainty until coordinator recovers.

Side note: Coordinator maintains a log structure on the disk to keep track of the committed or aborted transactions.

Coordinator is a single point of failure in the two-phase commit method. In order to fix two-phase commit, the 3-phase is also recommended, however, it breaks the atomicity guarantee by relying on the network timeouts (which can be unbounded).

Fault-tolerant Consensus

It is possible to achieve atomicity as well as some kind of fault tolerance using the consensus methods. In 2PC, the transaction can not proceed if any of the node crashes. However, in distributed consensus, one can tolerate certain number of node crashes until there is still quorum present (generally more than half number of nodes).

Formally, a consensus algorithm must satisfy the following properties [1]:

1. Uniform agreement: No two nodes will decide differently.
2. Integrity: No node decides twice.
3. Validity: If a node decides value v, then v was proposed by some node.
4. Termination: Every node that does not crash eventually decides some value.

First 3 are safety properties and last is the liveness property. Using consensus algorithm, one can achieve total order broadcast. Consensus mechanisms, in general, elect a single leader and that leader will replicate its log to all replicas. Consensus algorithms require for a particular term[2] or epoch or ballot number, the leader is unique. Even if leader is dead, the other nodes will start the voting mechanism by incrementing their term numbers. In order to become leader, nodes will need to have votes from a quorum of nodes.

Total Order Broadcast is a guarantee that messages delivered to a system will be in same order on all the nodes.

Although consensus algorithms seem to be providing atomicity, they are not used that much in the systems. This is because of the added cost to the performance of the system because of the replication.

References

• [1] Designing data-intensive applications, Martin Kleppman.
• [2] In Search of an Understandable Consensus Algorithm, Diego Ongaro and John Ousterhout.