Distributed Systems: Theory and Practice

Fundamental theory

FLP, CAP, BASE, and ACID

The FLP impossibility result

In an asynchronous model, a distributed system may be unable to reach consensus if even one process becomes unavailable. Practical distributed systems address issues such as livelock so that the system can reach agreement within a bounded period.

The CP section of the diagram is missing another common example: ZooKeeper.

ACID describes rigid transactions that aim for strong consistency. Relational databases such as MySQL are representative examples.

BASE describes flexible transactions that trade strong consistency for a degree of availability. Intermediate states may exist during processing, but the system eventually becomes consistent. Distributed systems such as Spanner are representative examples.

The CAP theorem

A distributed system cannot simultaneously provide consistency (C), availability (A), and partition tolerance (P); at most, it can fully provide two. A networked distributed system generally cannot give up partition tolerance, so its design tends toward either AP or CP.

The familiar “pick two” description is easy to misunderstand:

1. Partitions are uncommon. When no partition exists, there is little reason to sacrifice consistency or availability.
2. The trade-off between availability and consistency can change repeatedly within one system. Both properties also exist on a spectrum—for example, availability can vary, as can the chosen consistency level.

In practice, the trade-off should be made according to the application.

Consider ZooKeeper:

• C: eventual consistency, with data generally synchronizing across nodes within tens of seconds.
• A: data remains available, and more than half the nodes hold the latest data. A caller that must read the latest data needs to invoke sync manually.
• P: adding nodes greatly increases write-synchronization latency and makes leader election more expensive. Observer nodes can reduce the impact.

ZooKeeper is a CP system because requests receive a consistent view of the data, but the service does not guarantee that every request will succeed—for example, during a network partition. This makes an AP system such as Eureka a better fit for service discovery in some cases.

Distributed transactions

Several application-level patterns can provide eventual consistency:

• Reliable events: combine a message queue with a local or external event table.
• Business compensation: apply compensating actions after business or technical failures.
• TCC: implement two-phase commit at the application layer.
• Saga.

At the time of writing, Alibaba had also open-sourced Fescar.

The need for distributed transactions largely comes from horizontally partitioned databases and service-oriented architectures, where one operation may span multiple databases. From one perspective, these requirements mainly arise in companies with complex domains such as finance, global services such as Google’s, or enough data to require database sharding.

Common consistency protocols include:

• ZAB
• Raft
• Viewstamped Replication
• Quorum
• Gossip

They can broadly be viewed as variations on Paxos.

Common Paxos-like distributed transaction implementations include:

• MySQL XA
• TCC, or Try-Confirm-Cancel, for which an open-source implementation is available

This article is another useful reference: Distributed transactions in core financial systems.

Distributed locks

The usual choices are:

• A single Redis instance or the official Redlock algorithm
• ZooKeeper

The right option depends on the business requirements. If lock correctness is not critical—for example, if a 1% duplicate-lock rate is acceptable—a single Redis instance is the simplest option.

Practical distributed-system use cases

• WeChat’s PaxosStore
• Alibaba’s AliSQL X-Cluster
• TiDB with multiple Raft groups
• Google Spanner

---

Originally published on SegmentFault.