Consistency of Distributed Transactions

Linearizability

Linearizability, also known as atomic consistency, is the strongest level of consistency that a distributed data system offers. It states two characteristics,

  1. All replicas act as there is only one copy of data.
  2. All operations on the data are atomic
  1. Locking mechanism and Leader election
  2. Constraints and uniqueness guarantees

Consistency vs. Ordering

A linearizable system behaves as every operation takes effect atomically at one point in time. The defines implies that operations are executed in a well-defined order. If there is only one copy of data, every operation can be sorted through a global order, called total order. In a distributed system, all data replicas must maintain the same order, therefore linearizability is also known as total order broadcast.

Atomic Commitment

Another perspective of consistency is the atomic commitment. In a single host application, an atomic commitment depends on the storage engine to make the request durable, first the data and then the commit record. Therefore, the key deciding moment for whether the transaction commits or abort is the when the durable storage system writes the request.

  1. Some nodes may detect a constraint violation or conflict
  2. Requests may be lost due to network.
  3. Some nodes may crash and recover to a previous state without recent commit.
  1. Prepare phase. During this phase, a coordinator initial a prepare request to all participants with transaction data. Each participants check locally and aye to the prepare request if it can fulfill the request. Otherwise, it rejects the prepare request. This is the decision moment for participant to commit or abort. Once a participant vote yes to a request, it cannot reject the transaction later.
  2. Commit phase. After coordinator confirms with all participants, the coordinator may send the transaction to all the participants through a commit phase. This is the decision moment for coordinator to commit the transaction. Once the coordinator decide to commit, it must guarantee the commit request is acknowledged by all participants with necessary unlimited retries. Participant must reply the commit phase.

What is next?

After high level theoretical concepts in the last few posts, we will put things together and discuss an architecture view of distributed data system in the next post.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store