CAP, BASE, Consistent Hashing, Gossip, Raft & Distributed Transactions Explained

CAP Theorem

The CAP theorem states that a distributed system can at most provide two of the following three guarantees simultaneously:

Consistency (C) : All nodes see the same latest data. Writes go to a leader and are replicated to followers; reads return the most recent version.

Availability (A) : Every non‑failed node can serve requests, ensuring the system remains responsive even if some data is stale.

Partition tolerance (P) : The system continues operating despite network partitions that cause nodes to lose communication.

Because network delays are inevitable, partition tolerance must be satisfied, forcing a trade‑off between consistency and availability. In practice, CP systems (e.g., financial services) prioritize strong consistency, while AP systems (e.g., news‑feed counters) favor availability.

BASE Model

To relax the strictness of CAP, the BASE model was proposed (originating from eBay) and consists of:

Basically Available (BA) : The system remains operational even when some components degrade, providing degraded performance rather than total failure.

Soft state (S) : System state may change over time without input, allowing temporary inconsistencies such as replication lag.

Eventual consistency (E) : After a period of instability, all replicas converge to the same state.

BASE is suitable for scenarios where temporary inconsistency is acceptable as long as the system eventually becomes consistent.

Consistent Hashing

Traditional modulo hashing (e.g., hash(key) % num) causes massive cache invalidation when a new node is added, because most keys remap to different servers. Consistent hashing solves this by mapping both keys and servers onto a logical ring.

Hash each server node onto the ring.

Hash each key onto the same ring and walk clockwise to the first server encountered; that server stores the key.

When a new server joins, only the keys that fall between the predecessor and the new node need to be moved, dramatically reducing cache miss impact.

To avoid data skew when servers cluster on the ring, virtual nodes are introduced: each physical server is represented by multiple points on the ring, spreading the load more evenly.

hash(k0)%3=0 #No.0
hash(k1)%3=1 #No.1
hash(k2)%3=2 #No.2

hash(k0)%4=0 #No.1
hash(k1)%4=1 #No.2
hash(k2)%4=2 #No.3

Gossip Protocol

Gossip (or epidemic) protocols disseminate state changes across a cluster in a peer‑to‑peer fashion, achieving eventual consistency without a central coordinator.

Nodes periodically select a few peers and push their known updates.

Recipients repeat the process, spreading the information like a virus.

Each node avoids sending to the node it just received from, reducing redundant traffic.

The protocol tolerates message loss; eventually all nodes receive the update.

Typical use cases include membership discovery and state propagation in systems such as Redis Cluster and Consul.

Raft Consensus Algorithm

Raft provides a practical way to achieve strong consistency in a replicated log. Nodes assume one of three roles:

Leader : Handles all client writes, appends entries to its log, and replicates them to followers.

Follower : Passively receives log entries from the leader and votes in elections.

Candidate : A follower that times out without hearing from a leader and starts an election.

Raft splits the problem into two sub‑problems: leader election and log replication.

Leader Election

All nodes start as followers. Each follower runs a randomized election timer; when it expires without a heartbeat, the node becomes a candidate, votes for itself, and solicits votes from others. If a candidate receives votes from a majority, it becomes the leader and begins sending heartbeats.

Log Replication

When the leader receives a client request, it appends the command to its log and replicates the entry to a majority of followers via AppendEntries messages (often piggy‑backed on heartbeats). Once a majority acknowledges, the leader commits the entry, applies it to its state machine, and replies to the client.

Distributed Transactions

Two‑Phase Commit (2PC)

2PC coordinates a transaction across multiple resources via a central coordinator:

Prepare phase : The coordinator asks all participants to get ready to commit.

Commit phase : If all participants respond positively, the coordinator sends a commit; otherwise it sends a rollback.

2PC provides strong consistency but suffers from a single point of failure and can block if the coordinator crashes.

Three‑Phase Commit (3PC)

3PC adds a pre‑commit phase to mitigate blocking:

Prepare : Participants indicate readiness.

Pre‑commit : Coordinator ensures all participants have persisted the prepare state.

Commit : Final commit or rollback is issued.

3PC reduces the window where a coordinator failure can leave participants in an uncertain state, but it still cannot guarantee absolute safety under arbitrary network partitions.

Try‑Confirm‑Cancel (TCC)

TCC splits a business operation into three explicit steps:

Try : Reserve or lock required resources without making permanent changes.

Confirm : Actually perform the operation and commit.

Cancel : Release reserved resources if the confirm step fails.

TCC offers fine‑grained compensation but requires significant code changes and idempotent handling of confirm/cancel retries.

All three protocols share the limitation that network failures or crashes can lead to temporary inconsistencies; practical systems often combine them with retry mechanisms, message queues, and monitoring to achieve acceptable reliability.