The Deep End: Distributed Systems, Consensus, and State

When you write a single-threaded program running on a single machine, life is easy. You write a variable to memory, and the next line reads it back. It's there. It's correct.

When you move to a distributed system, you are essentially trying to make a fleet of independent, unreliable machines scattered across the globe pretend they are just one big, reliable computer. This is a brilliant illusion, and maintaining it requires overcoming the fundamental laws of physics.

Let's turn over every rock in the landscape of Distributed Systems, Consensus, and State.

In a single machine, we have a CPU clock. In a distributed system, every machine has its own quartz crystal. These crystals vibrate at slightly different frequencies, meaning clocks drift.

If Server A says an event happened at 10:00:00.001 and Server B says an event happened at 10:00:00.002, we cannot guarantee Server A's event actually happened first. Network Time Protocol (NTP) helps, but it only synchronizes to within a few milliseconds. In a computer context, a millisecond is an eternity.

Since we can't trust wall-clock time, we use logical time. We only care about causal ordering: did event X cause event Y?

Lamport Timestamps Proposed by Leslie Lamport in 1978. Every node keeps a simple integer counter.

EXPANDCOPY
go
type LamportClock struct {
    time int32
    mu   sync.Mutex
}

func (l *LamportClock) Tick() int32 {
    l.mu.Lock()
    defer l.mu.Unlock()
    l.time++
    return l.time
}

func (l *LamportClock) SendEvent() int32 {
    return l.Tick()
}

// When receiving a message, update your clock to be strictly 
// greater than the sender's clock.
func (l *LamportClock) ReceiveEvent(receivedTime int32) int32 {
    l.mu.Lock()
    defer l.mu.Unlock()
    if receivedTime > l.time {
        l.time = receivedTime
    }
    l.time++
    return l.time
}

Rule: If A -> B (A causes B), then L(A) < L(B). However, the reverse is not true. If L(A) < L(B), we don't know if A caused B or if they are just concurrent events that happened to occur in that order.

Vector Clocks To solve the concurrency ambiguity of Lamport clocks, we use Vector Clocks. Instead of a single integer, a vector clock is an array of integers, one for each node in the system.

EXPANDCOPY
go
type VectorClock struct {
    nodeID int
    vector []int32
    mu     sync.Mutex
}

func NewVectorClock(nodeID, totalNodes int) *VectorClock {
    return &VectorClock{
        nodeID: nodeID,
        vector: make([]int32, totalNodes),
    }
}

func (v *VectorClock) Tick() {
    v.mu.Lock()
    defer v.mu.Unlock()
    v.vector[v.nodeID]++
}

func (v *VectorClock) SendEvent() []int32 {
    v.Tick()
    v.mu.Lock()
    defer v.mu.Unlock()
    
    copyVec := make([]int32, len(v.vector))
    copy(copyVec, v.vector)
    return copyVec
}

func (v *VectorClock) ReceiveEvent(receivedVector []int32) {
    v.mu.Lock()
    defer v.mu.Unlock()
    
    for i := 0; i < len(v.vector); i++ {
        if receivedVector[i] > v.vector[i] {
            v.vector[i] = receivedVector[i]
        }
    }
    v.vector[v.nodeID]++
}

If Vector A is strictly less than Vector B (every element in A is <= the corresponding element in B, and at least one is strictly <), then A casually precedes B. If neither is strictly less, they are concurrent! Systems like Amazon DynamoDB and Cassandra use variations of this to detect and resolve write conflicts.

Imagine two generals on two hills, trying to coordinate an attack on a valley below. They can only communicate by sending messengers through the valley, where they might be captured.

• General A sends: "Attack at dawn."
• General B receives it, but A doesn't know if B got it. So B sends an ACK: "I will attack at dawn."
• B doesn't know if A received the ACK. If A didn't, A might abort the attack, leaving B to fight alone. So A sends an ACK to the ACK.
• This creates an infinite loop of uncertainty.

Theorem: In a network with unreliable communication (messages can be dropped), it is impossible to guarantee consensus. We build systems that are "good enough" probabilistically, using timeouts and retries, but absolute mathematical certainty is impossible over a faulty network.

What if the messengers get through, but some of the generals are traitors? A traitor might tell General A "attack" and General B "retreat".

Systems that can survive nodes actively lying or sending corrupted data are Byzantine Fault Tolerant (BFT). Bitcoin and blockchain networks are BFT systems (using Proof of Work to make lying computationally expensive). Most enterprise databases (like Zookeeper, etcd, or Postgres) are Crash Fault Tolerant (CFT) — they assume nodes might die or packets might drop, but nodes don't maliciously lie.

CAP Theorem: In a distributed data store, you can only guarantee two of the following three:

• Consistency: Every read receives the most recent write or an error.
• Availability: Every request receives a (non-error) response, without the guarantee that it contains the most recent write.
• Partition Tolerance: The system continues to operate despite an arbitrary number of messages being dropped by the network.

Reality Check: You cannot sacrifice Partition Tolerance. Network partitions will happen. Someone will trip over a router cable. Therefore, you must choose between C (CP systems) and A (AP systems) when a failure occurs.

• CP System (e.g., Zookeeper, MongoDB with strong consistency): If a network link breaks, the system stops accepting writes to prevent data divergence.
• AP System (e.g., Cassandra, DynamoDB): If a link breaks, both sides keep accepting writes. You get high availability, but the data will diverge (requiring Eventual Consistency and conflict resolution later).

PACELC Theorem: An extension of CAP. It states: If there is a Partition (P), how does the system trade off Availability and Consistency (A and C); Else (E), when the system is running normally, how does the system trade off Latency (L) and Consistency (C)?

How do multiple nodes agree on a single value (or a sequence of values, i.e., a replicated log)?

Created by Leslie Lamport, Paxos is mathematically beautiful but notoriously difficult to understand and implement correctly.

Phases:

1. Prepare/Promise: A Proposer generates an ID (N) and sends Prepare(N) to a quorum (majority) of Acceptors. If N is higher than any ID the Acceptor has ever seen, it promises to not accept proposals < N and returns its highest previously accepted value.
2. Accept/Accepted: The Proposer looks at the Promises. If an Acceptor returned a value, the Proposer MUST propose that value. Otherwise, it can propose its own. It sends Accept(N, Value) to the quorum. If the Acceptor hasn't promised to a higher N in the meantime, it accepts it.

Pseudocode for a Paxos Acceptor in Go:

EXPANDCOPY
go
type Promise struct {
    Status           string
    AcceptedProposal int
    AcceptedValue    any
}

type Acceptor struct {
    minProposal      int
    acceptedProposal int
    acceptedValue    any
    mu               sync.Mutex
}

func (a *Acceptor) ReceivePrepare(n int) Promise {
    a.mu.Lock()
    defer a.mu.Unlock()
    
    if n > a.minProposal {
        a.minProposal = n
        return Promise{
            Status:           "PROMISE", 
            AcceptedProposal: a.acceptedProposal, 
            AcceptedValue:    a.acceptedValue,
        }
    }
    return Promise{Status: "REJECT"}
}

func (a *Acceptor) ReceiveAccept(n int, value any) string {
    a.mu.Lock()
    defer a.mu.Unlock()
    
    if n >= a.minProposal {
        a.minProposal = n
        a.acceptedProposal = n
        a.acceptedValue = value
        return "ACCEPTED"
    }
    return "REJECT"
}

Created by Diego Ongaro and John Ousterhout specifically to be understandable. It powers systems like etcd (the brain behind Kubernetes) and Consul. It divides consensus into three subproblems: Leader Election, Log Replication, and Safety.

1. Leader Election Nodes are Followers, Candidates, or Leaders. Time is divided into Terms. If a Follower hears nothing (no heartbeat) for a randomized timeout (e.g., 150-300ms), it becomes a Candidate, increments the Term, votes for itself, and requests votes from others. If it gets a majority, it becomes the Leader. Randomized timeouts are crucial to prevent split votes where multiple nodes become candidates simultaneously forever.

2. Log Replication The Leader accepts client requests. It appends the command to its log. It sends AppendEntries RPCs to all followers. Once a majority of followers acknowledge the write, the Leader commits the entry and applies it to its state machine, then tells followers to apply it.

Pseudocode for Raft Leader Log Replication in Go:

EXPANDCOPY
go
func (l *RaftLeader) HandleClientRequest(command any) string {
    entry := LogEntry{Term: l.currentTerm, Command: command}
    
    l.mu.Lock()
    l.log = append(l.log, entry)
    l.mu.Unlock()
    
    var wg sync.WaitGroup
    var mu sync.Mutex
    acks := 1 // Self acknowledges automatically
    
    for _, follower := range l.followers {
        wg.Add(1)
        go func(f *Node) {
            defer wg.Done()
            // Real implementation uses timeouts and handles RPC errors
            success := l.sendAppendEntries(f, entry)
            if success {
                mu.Lock()
                acks++
                mu.Unlock()
            }
        }(follower)
    }
    
    wg.Wait() // Wait for responses
    
    // Wait for Quorum (N/2 + 1)
    if acks > (len(l.followers)+1)/2 {
        l.mu.Lock()
        l.commitIndex = len(l.log) - 1
        l.applyToStateMachine(entry.Command)
        l.mu.Unlock()
        return "SUCCESS"
    }
    
    return "FAIL_NO_QUORUM"
}

Safety (Log Matching Property) If two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index. The Leader forces followers' logs to match its own exactly.

What happens if the network partitions, and the old Leader is separated from the majority? The majority elects a New Leader. But the Old Leader doesn't know this! It still thinks it's the leader (Split Brain).

If a client talks to the Old Leader, it will try to write data. However, in Raft, the Old Leader cannot get a majority of ACKs (because it's physically isolated), so the write fails. The core system is safe!

But what if the Old Leader is interacting with an external system (like an S3 storage bucket or an email API) that doesn't understand Raft consensus?

1. Old Leader pauses due to a long Garbage Collection spike.
2. Majority detects timeout and elects New Leader.
3. New Leader writes to the Storage Bucket.
4. Old Leader wakes up, still thinks it's leader, and writes to Storage Bucket, overwriting the New Leader's data!

Solution: Fencing Tokens Every time a Leader is elected, it gets a monotonically increasing token (e.g., its Raft Term number). It passes this token to the Storage Service with every single write. The Storage Service remembers the highest token it has ever seen. If the Old Leader (Token 5) tries to write, but the Storage Service has already seen the New Leader (Token 6), the Storage Service rejects the Old Leader's write.

What if you need to update a Postgres Database and publish a Kafka message transactionally?

Two-Phase Commit (2PC) A coordinator asks all databases: "Can you commit?" (Prepare phase). If ALL say "Yes", the coordinator says "Commit!" (Commit phase). The Problem: It's heavily blocking. If a database locks a row during the Prepare phase and the coordinator crashes before sending the Commit command, the row is locked forever. It scales terribly in microservice architectures.

The Saga Pattern Used in modern, highly scalable microservices. A long-running transaction is broken into localized, independent transactions. If step 1 (Deduct Funds) succeeds, we trigger step 2 (Ship Item). If step 2 fails, we DO NOT rollback the database transaction (it already committed locally). Instead, we issue a Compensating Transaction (Refund Funds). It embraces Eventual Consistency.

Pseudocode for a Choreography-based Saga in Go:

EXPANDCOPY
go
// In the Inventory Service
func HandleOrderPlacedEvent(event OrderEvent) {
    err := inventoryService.ReserveItems(event.Items)
    if err != nil {
        // The compensating action trigger
        publishEvent(OrderFailedEvent{
            OrderID: event.OrderID, 
            Reason:  "No Stock",
        })
        return
    }
    
    publishEvent(InventoryReservedEvent{OrderID: event.OrderID})
}

// In the Payment Service
func HandleOrderFailedEvent(event OrderFailedEvent) {
    // This explicitly undoes the successful payment step
    paymentService.RefundCustomer(event.OrderID)
}

Because networks drop packets, a client might send a POST request to "Charge $50". The server receives it, charges$50, but the response back to the client is dropped by a faulty router. The client, thinking it failed, retries. Does the user get charged $100?

To prevent this, every destructive operation in a distributed system must use an Idempotency Key.

EXPANDCOPY
go
func ChargeCard(ctx context.Context, userID string, amount float64, idempotencyKey string) (*Result, error) {
    // Check if we already successfully processed this exact request
    var previousResult Result
    err := db.QueryRowContext(ctx, "SELECT result FROM idempotency_table WHERE key = $1", idempotencyKey).Scan(&previousResult)
    if err == nil {
        return &previousResult, nil // Return cached result, do NOT charge again
    }

    // Begin database transaction
    tx, err := db.BeginTx(ctx, nil)
    if err != nil {
        return nil, err
    }
    defer tx.Rollback() // Safe to defer, no-op if committed

    result, err := stripeAPI.Charge(userID, amount)
    if err != nil {
        // If external call failed, don't save the key, so the client can safely retry
        return nil, err
    }

    _, err = tx.ExecContext(ctx, "INSERT INTO idempotency_table (key, result) VALUES ($1, $2)", idempotencyKey, result)
    if err != nil {
        // Might happen if two identical requests slipped past the SELECT at the exact same time
        // (A unique constraint on idempotency_table.key handles this safety net)
        return nil, err
    }
    
    tx.Commit()
    return &result, nil
}

Building distributed systems is the art of strategic paranoia. You must assume every network packet will be dropped, every server will randomly restart, every clock is fundamentally wrong, and every dependent service will go down at the worst possible time.

By utilizing logical clocks, consensus algorithms like Raft, Quorums, Fencing Tokens, the Saga pattern, and Idempotent APIs, we can tame the inherent chaos of the network and build systems that appear flawless, coherent, and singular to the end user.

Welcome to the deep end.