Distributed Systems: Architecture and Consistency

Fundamentals

Distributed system: collection of independent computers that appears as a single coherent system. Motivations: scalability, fault tolerance, low latency (geographic distribution), data sovereignty. Challenges: partial failures, network partitions, clock synchronization, consistency vs. availability trade-offs. Fallacies of distributed computing (Deutsch, 1994): the network is reliable, latency is zero, bandwidth is infinite, etc. Types: client-server, peer-to-peer, event-driven, microservices. Communication: RPC (gRPC, Thrift), message queues (Kafka, RabbitMQ), REST/GraphQL APIs.

CAP Theorem and Consistency

CAP Theorem (Brewer, 2000): in the presence of a network partition (P), a distributed system can provide either Consistency (C) or Availability (A), not both. CP systems: HBase, MongoDB (with majority reads) — return errors during partitions rather than stale data. AP systems: Cassandra, DynamoDB — always respond but may return stale data. PACELC (Abadi): extends CAP: if Partition → choose A or C; Else → choose Latency or Consistency. Consistency models: linearizability (strongest), sequential consistency, causal consistency, eventual consistency. CRDTs (Conflict-free Replicated Data Types): data structures that always converge — G-Counter, LWW-Register, OR-Set.

Consensus Algorithms

Consensus: getting N nodes to agree on a value despite failures. FLP impossibility (1985): no deterministic async consensus with even one crash failure. Paxos (Lamport, 1989): proposer-acceptor-learner roles, quorum-based (majority). Multi-Paxos: optimized for log replication with a stable leader. Raft (Ongaro & Ousterhout, 2014): understandable consensus — leader election, log replication, safety. Terms/epochs: monotonically increasing, prevent stale leaders. Byzantine fault tolerance (BFT): tolerates malicious nodes (PBFT: 3f+1 nodes for f Byzantine faults). Blockchain: BFT consensus at internet scale (PoW, PoS). Zab (ZooKeeper), Viewstamped Replication, EPaxos (leaderless).

Distributed Databases

Sharding: horizontal partitioning of data across nodes (hash-based, range-based, directory-based). Replication: single-leader (MySQL, PostgreSQL streaming), multi-leader (CockroachDB), leaderless (Dynamo-style). Google Spanner: globally distributed, strongly consistent, TrueTime API (GPS + atomic clocks for bounded clock uncertainty). CockroachDB: open-source Spanner-inspired, serializable transactions. Amazon DynamoDB: serverless, eventual/strong consistency, single-digit ms latency. Apache Cassandra: wide-column, tunable consistency (ONE, QUORUM, ALL). NewSQL: combining SQL interface with NoSQL scalability (TiDB, YugabyteDB, VoltDB). Vector clocks: tracking causal ordering in eventually consistent systems.

Microservices and Patterns

Microservices: independently deployable services, each owning its data. Service mesh: Istio, Linkerd — sidecar proxies for mTLS, load balancing, observability. Saga pattern: distributed transactions across services using compensating actions (choreography vs. orchestration). CQRS (Command Query Responsibility Segregation): separate read/write models. Event sourcing: storing all changes as immutable events, replay for state reconstruction. Circuit breaker: preventing cascade failures (Hystrix, Resilience4j). Observability: distributed tracing (Jaeger, Zipkin), structured logging, metrics (Prometheus). Chaos engineering: Netflix Chaos Monkey, deliberately injecting failures to improve resilience.

Frequently Asked Questions

What is the CAP theorem?

The CAP theorem states that a distributed system can provide at most two of three guarantees: Consistency, Availability, and Partition tolerance. Since network partitions are inevitable, the real choice is between C and A during partitions.

What is Raft consensus?

Raft is a consensus algorithm designed for understandability, using leader election, log replication, and safety mechanisms to ensure all nodes agree on the same sequence of commands.

What is eventual consistency?

Eventual consistency guarantees that if no new updates are made, all replicas will eventually converge to the same value. It trades strong consistency for higher availability and lower latency.

What are microservices?

Microservices is an architectural style where an application is composed of small, independently deployable services, each responsible for a specific business capability and owning its own data store.

What is sharding?

Sharding is the practice of horizontally partitioning data across multiple database nodes to distribute load and scale beyond the capacity of a single machine.

Try it live

Everything above runs in your browser — open Hash Function Avalanche Visualizer and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.