distributed systems

Reading Time: 3 minutes

Distributed systems are fundamental to modern computing, but they come with inherent trade-offs. The CAP theorem, introduced by Eric Brewer, provides a framework for understanding these trade-offs by defining three key properties: Consistency, Availability, and Partition Tolerance. In this article, we will explore CAP theorem step by step, starting from its basic definition to its deeper implications in distributed system design.

1. What is the CAP Theorem?

Imagine an online banking system with multiple servers across different regions. If a customer deposits money in one branch, that update must reflect accurately across all servers to prevent double spending. However, if a network failure occurs between data centers, the system faces a dilemma:

Should it prioritize consistency and prevent withdrawals until all servers are synchronized?
Should it prioritize availability and allow transactions to proceed, even if some servers have outdated information?
Or should it tolerate network partitions and find a balance between the two?

The CAP theorem provides a framework to understand and resolve such trade-offs in distributed system design.

The CAP theorem states that in a distributed data system, it is impossible to achieve all three of the following simultaneously:

Consistency (C) – Every read receives the most recent write or an error.
Availability (A) – Every request receives a response (success or failure), even in the presence of failures.
Partition Tolerance (P) – The system continues to function despite network partitions.

In practice, distributed systems must make trade-offs between these properties, choosing to optimize for two at the expense of the third.

2. Breaking Down the CAP Properties

Consistency (C)

Consistency ensures that all nodes return the same data at any given time. If a write is performed on one node, all subsequent reads on any node should reflect that write.

Example: A traditional relational database (e.g., PostgreSQL) ensures strict consistency by using distributed transactions.

Availability (A)

Availability ensures that every request to the system receives a response, even if some nodes are unavailable.

Example: A DNS system is highly available, meaning queries always receive responses, even if some servers are down.

Partition Tolerance (P)

Partition tolerance means that the system continues to operate even when network failures occur, causing communication issues between nodes.

Example: A global system like Apache Cassandra remains operational even if some nodes lose connectivity due to network failures.

3. CAP Theorem in Practice

Since no distributed system can achieve all three properties, they typically fall into one of the following categories:

CP (Consistency + Partition Tolerance) – Ensures data consistency even during network failures but may sacrifice availability.
- Example: Apache Zookeeper prioritizes consistency and partition tolerance but may become unavailable if a partition occurs.
AP (Availability + Partition Tolerance) – Ensures availability during network failures but may return stale or inconsistent data.
- Example: DynamoDB prioritizes availability and partition tolerance, allowing eventual consistency.
CA (Consistency + Availability) – Provides consistency and availability but cannot tolerate network partitions.
- Example: A traditional relational database like MySQL in a single-node setup.

4. Implications of CAP on System Design

When designing a distributed system, understanding CAP helps in making informed trade-offs:

If strong consistency is needed, use a CP system.
If high availability is critical, an AP system is preferable.
If partitioning is not a concern, a CA system can work, but it is rare in distributed environments.

5. CAP Theorem in Real-World Systems

Many modern distributed databases adopt a flexible consistency model rather than strictly following CAP trade-offs:

Hazelcast – Prioritizes consistency with partition tolerance in its CP subsystem.
MongoDB – Offers tunable consistency to balance between AP and CP properties.
Cassandra – Favors availability and partition tolerance, achieving eventual consistency.

6. Further Reading

For a deeper understanding of CAP theorem, check out:

Reading Time: 3 minutes

A distributed system needs a reliable mechanism for reaching consensus across multiple nodes. The RAFT algorithm is one such consensus algorithm. It was designed to be easier to understand than Paxos (an earlier, more complex protocol for providing consensus in distributed networks,) while maintaining strong fault tolerance.

1. What is RAFT?

RAFT is widely used in distributed systems that require strong consistency. In a distributed environment, multiple nodes work together to store and process data reliably. However, ensuring that all nodes agree on the same state at any given time is a challenge. RAFT helps solve this problem by ensuring that commands are consistently applied across all nodes, preventing conflicts and maintaining data integrity. Unlike traditional databases that rely on a single primary instance for writes, distributed systems using RAFT elect a leader that coordinates operations, ensuring that updates are applied in the same order across all nodes. This makes RAFT a crucial component for building fault-tolerant, highly available distributed applications.

RAFT (Reliable, Replicated, and Fault-Tolerant) is a consensus algorithm used to manage a replicated log in distributed systems. It ensures that multiple nodes in a distributed system agree on the same sequence of commands, maintaining consistency even in the face of network failures.

(For comparison, another well-known consensus algorithm is Paxos, which is more complex but serves a similar purpose. You can read more about it here.)

Key Goals of RAFT:

Leader Election – Ensuring that one node acts as the leader at any given time.
Log Replication – Maintaining a consistent log across all nodes.
Safety & Fault Tolerance – Ensuring that committed entries are never lost, even if some nodes fail.

RAFT is used in distributed databases, coordination services, and in-memory data grids like Hazelcast to ensure consistency.

2. RAFT’s Three Key Roles

RAFT divides nodes into three roles:

Leader – The central authority that handles client requests and replicates logs.
Followers – Passive nodes that accept updates from the leader.
Candidates – Nodes that attempt to become the leader during elections.

At any given time, there is at most one leader, while all other nodes function as followers.

3. Leader Election Process

When a RAFT cluster starts, or if the leader fails, an election process takes place:

A follower node times out and transitions to a candidate state.
The candidate requests votes from other nodes.
If a majority of nodes vote for the candidate, it becomes the leader.
The leader then starts sending heartbeat messages to followers, maintaining authority.

Example: Leader Election

Node A (Follower) -> Times out -> Becomes Candidate
Node A requests votes from Nodes B & C
Nodes B & C vote for A (majority wins)
Node A becomes the Leader

This mechanism ensures a stable leadership structure even during network failures.

4. Log Replication

Once a leader is established, it manages log replication:

The leader receives a client request.
The request is appended to the leader’s log.
The leader sends the log entry to followers.
Once a majority acknowledges the entry, it is committed.
Followers apply the committed log to their state machine.

What is a Log in RAFT?

A log in RAFT is an append-only structure that stores client requests (commands). The leader ensures that all followers maintain an identical sequence of logs so that they reach the same state.

Example: Log Replication

Client -> Sends "Write X=10" to Leader
Leader -> Appends "Write X=10" to log
Leader -> Sends entry to Followers
Majority acknowledges -> Entry is committed

This ensures all nodes eventually apply the same commands in order.

Log Consistency Rules in RAFT

Leader Enforces Order: Followers must accept logs from the leader that match their current state.
Log Matching Property: If two logs share the same index and term, they must contain the same command.
Commit Rule: A log entry is committed when a majority of nodes replicate it.

Example of Log Entries

Log Index	Term	Command
1	1	Write X = 5
2	2	Write Y = 20
3	2	Write X = 10

The Log Index ensures the correct order.
The Term tracks the leader’s election cycle.
The Command is the action that changes the system state.

Logs serve as the foundation for fault tolerance in RAFT, ensuring that even if a node fails, the system can recover and maintain a consistent state.

5. Handling Failures

RAFT ensures that failures do not cause inconsistencies by following strict rules:

Election Timeout: If a leader crashes, a new election starts after a timeout.
Log Matching Property: Followers accept only consistent log updates from the leader.
Commit Consistency: Entries are only committed when a majority acknowledges them.

This design prevents split-brain scenarios and guarantees system integrity.

6. RAFT in Practice

Many distributed systems, including Hazelcast, leverage RAFT for high availability and fault tolerance. Hazelcast’s CP Subsystem implements RAFT to ensure data consistency in distributed environments.

7. Further Reading

For a deeper dive into RAFT, check out:

MMDC

Category: distributed systems

Understanding the CAP Theorem