Chapter 1: Distributed Systems Overview

What is a Distributed System?

A distributed system is a collection of independent computers that work together to appear as a single system to users. Instead of relying on one powerful machine, work and data are spread across many machines connected by a network.

Examples include Google Search, Amazon, Netflix, Uber, WhatsApp, and ChatGPT.

Mental model

          User
            │
     ┌──────▼──────┐
     │ Load Balancer│
     └──────┬──────┘
            │
   ┌────────┼────────┐
   ▼        ▼        ▼
 App 1    App 2    App 3
   │        │        │
   └────────┼────────┘
            │
        Distributed DB

Instead of one computer doing everything, many computers cooperate to process requests, store data, and tolerate failures.

Why Do We Need Distributed Systems?

A single machine eventually becomes the bottleneck.

Common limitations include:

  • CPU
  • Memory
  • Storage
  • Network bandwidth
  • Geographic latency
  • Hardware failures

Distributed systems solve these by adding more machines rather than buying larger ones.

Primary goals

Goal Why it matters
Scalability Handle more users and data
Availability Stay online despite failures
Fault Tolerance Continue operating when machines fail
Performance Reduce latency and increase throughput
Reliability Avoid losing data
Cost Scale with commodity hardware

The Core Challenge

The hardest part of distributed systems isn’t writing code.

It’s coordinating machines that:

  • fail independently
  • communicate over unreliable networks
  • have different clocks
  • process messages at different speeds

Unlike local function calls, every network request can be:

  • delayed
  • duplicated
  • reordered
  • dropped

This is why distributed systems are fundamentally different from single-machine programming.

Fundamental Tradeoffs

Every distributed system balances competing goals.

Want More… Usually Means Less…
Consistency Availability
Availability Strong consistency
Durability Write latency
Throughput Coordination
Simplicity Flexibility

Interview takeaway:

There is no perfect distributed system. Every design is a series of tradeoffs.

Common Building Blocks

Most modern systems follow a similar architecture.

Users
   │
DNS
   │
Load Balancer
   │
Application Servers
   │
Cache
   │
Database
   │
Object Storage

Supporting infrastructure typically includes:

  • Message queues
  • Service discovery
  • Monitoring
  • Logging
  • Coordination services
  • Configuration management

Nearly every system design interview starts with this architecture.

Key Characteristics

Distributed systems typically provide:

Scalability

  • Add more machines to handle growth.

Availability

  • Continue serving users despite failures.

Fault Tolerance

  • Recover automatically from machine or network failures.

Concurrency

  • Many machines process requests simultaneously.

Transparency

  • Users interact with one logical system, even though many machines are involved.

Common Challenges

Every distributed system eventually encounters:

  • Partial failures
  • Network partitions
  • Clock skew
  • Data replication
  • Load balancing
  • Cache invalidation
  • Leader election
  • Hot partitions
  • Distributed transactions

The rest of this cheat sheet explores how these problems are solved.

Interview Questions

You should be able to answer:

  • Why distribute a system instead of using a larger machine?
  • What problems do distributed systems solve?
  • What new challenges do they introduce?
  • Why is networking harder than local execution?
  • What are the major system goals?

Chapter Summary

Remember these five ideas:

  1. Distributed systems are many computers acting as one.
  2. Networks are unreliable, unlike local memory.
  3. Machines fail, so failure is the normal case.
  4. Every design involves tradeoffs.
  5. Nearly every interview question builds on these fundamentals.

Chapter 2: Scalability

What is Scalability?

Scalability is the ability of a system to handle increasing users, traffic, or data without a proportional drop in performance.

A scalable system should continue to perform well as demand grows.

Examples:

  • A social network adding millions of users
  • An e-commerce site handling Black Friday traffic
  • ChatGPT serving millions of simultaneous requests

Interview takeaway

Scalability is usually achieved by adding machines, not buying larger ones.

Dimensions of Scale

Systems rarely scale along just one axis.

Dimension Example
Users Daily active users grow from 1M → 100M
Requests API QPS increases during peak traffic
Data Logs, images, videos, and user data grow continuously
Compute More CPU and GPU resources needed
Geography Users distributed across multiple regions

Interview tip

Always ask: “What is growing?” Different bottlenecks require different solutions.

Vertical Scaling (Scale Up)

Increase the resources of a single machine.

Examples:

  • More CPU cores
  • More RAM
  • Faster SSDs
  • Larger GPUs
Small Server
      │
      ▼
 Bigger Server

Advantages

  • Simple
  • No application changes
  • Strong consistency (single machine)

Disadvantages

  • Hardware limits
  • Expensive
  • Single point of failure
  • Downtime for upgrades

Good for:

  • Small systems
  • Databases that fit on one machine
  • Early-stage products

Horizontal Scaling (Scale Out)

Add more machines instead of making one machine bigger.

      Server
         │
         ▼
 ┌────┬────┬────┐
 │App1│App2│App3│
 └────┴────┴────┘

Advantages

  • Nearly unlimited growth
  • Better fault tolerance
  • Lower cost with commodity hardware
  • Supports global deployments

Disadvantages

  • Coordination complexity
  • Network communication
  • Data partitioning
  • Replication challenges

Interview takeaway

Nearly every modern internet-scale system uses horizontal scaling.

Elasticity vs Scalability

People often confuse these.

Scalability Can the system handle more load?

Elasticity Can the system automatically add or remove resources as load changes?

Example

Traffic doubles.

Scalable: You manually add more servers.

Elastic: Cloud infrastructure automatically launches more servers.

Stateless vs Stateful Services

Stateless

Each request is independent.

Client
   │
Load Balancer
   │
───────────────
│ App │ App │ App │
───────────────

Requests can go to any server.

Examples:

  • REST APIs
  • Web servers
  • Authentication services

Advantages

  • Easy horizontal scaling
  • Easy load balancing
  • Simple failure recovery

Stateful

Servers store session or application state.

Examples:

  • Databases
  • Redis
  • Multiplayer game servers

Challenges

  • Sticky sessions
  • Replication
  • Migration
  • Failover

Interview tip

Keep application servers stateless whenever possible.

Identifying Bottlenecks

Scaling starts by finding the bottleneck.

Common bottlenecks include:

CPU

  • Heavy computation
  • ML inference
  • Compression

Memory

  • Large caches
  • Large models

Disk

  • Database I/O
  • Logging

Network

  • Large media files
  • Cross-region traffic

Database

  • Lock contention
  • Too many writes
  • Slow queries

Scaling the wrong component doesn’t improve performance.

Amdahl’s Law

Overall performance is limited by the portion of the system that cannot be parallelized.

Example

If 90% of a workload is parallelizable, adding more machines helps.

If only 20% is parallelizable, adding servers provides little benefit.

Interview takeaway

Not every problem scales linearly.

Common Scaling Strategies

Problem Solution
Too many requests Add application servers
Database overloaded Read replicas
Writes overloaded Sharding
Slow responses Caching
Background work Message queues
Large files CDN/Object storage
Regional latency Multi-region deployment

Notice how the rest of the handbook naturally expands on these solutions.

Horizontal Scaling Isn’t Free

Adding servers introduces new challenges:

  • Load balancing
  • Partitioning
  • Replication
  • Consensus
  • Distributed transactions
  • Clock synchronization
  • Failure handling

Scaling solves one problem while creating several others.

Interview Questions

You should be able to answer:

  • When would you scale vertically instead of horizontally?
  • Why are stateless services easier to scale?
  • What is elasticity?
  • What component is likely to become the next bottleneck?
  • Why doesn’t adding more servers always improve performance?

Chapter Summary

Remember these six ideas:

  1. Scale horizontally whenever possible.
  2. Stateless services are easy to replicate.
  3. Always identify the bottleneck before scaling.
  4. Elasticity is automatic scaling.
  5. Scaling introduces coordination problems.
  6. Every future topic (load balancing, sharding, replication, caching) exists because of scalability.

Chapter 3: Load Balancing

What is Load Balancing?

A load balancer distributes incoming requests across multiple servers so that no single server becomes overloaded.

Instead of every request going to one machine, traffic is spread across many healthy servers.

Mental model

               Clients
                  │
                  ▼
          ┌────────────────┐
          │ Load Balancer  │
          └───────┬────────┘
                  │
      ┌───────────┼───────────┐
      ▼           ▼           ▼
    App 1       App 2       App 3

Without a load balancer:

  • One server gets overloaded.
  • Other servers sit idle.
  • A single failure takes down the service.

Why Do We Need It?

As systems grow, we add more application servers.

The load balancer solves three problems:

  • Distributes traffic evenly
  • Detects unhealthy servers
  • Provides a single entry point for clients

Interview takeaway

A load balancer enables horizontal scaling.

Layer 4 vs Layer 7

Layer 4 (Transport)

Routes based on:

  • IP
  • TCP/UDP port

Pros

  • Very fast
  • Low overhead

Cons

  • Doesn’t inspect requests

Examples

  • AWS Network Load Balancer
  • Google Cloud TCP Load Balancer

Layer 7 (Application)

Routes based on:

  • URL path
  • HTTP headers
  • Cookies
  • Hostname

Examples

/images → Image Service

/api → Backend API

/login → Auth Service

Pros

  • Intelligent routing
  • A/B testing
  • API gateway features

Cons

  • Higher overhead

Examples

  • NGINX
  • Envoy
  • HAProxy
  • AWS ALB

Interview rule

Use Layer 7 for web applications and microservices.

Common Routing Algorithms

Round Robin

Each request goes to the next server.

1 → App1

2 → App2

3 → App3

4 → App1

Pros

  • Simple
  • Even distribution

Cons

  • Ignores server load

Least Connections

Send traffic to the server with the fewest active requests.

Best when requests have different durations.

Example

App1 : 120 requests

App2 : 15 requests

→ choose App2

Weighted Round Robin

Some servers receive more traffic.

Example

App1 weight = 4

App2 weight = 2

App3 weight = 1

Useful when machines have different capacities.

Hash-Based Routing

Choose a server using a hash.

Example

hash(userID)

↓

Server

Advantages

  • Same user consistently reaches the same server.
  • Useful for caching and sticky sessions.

Consistent Hashing

Instead of remapping almost every key when servers change, only a small fraction move.

Used in:

  • Redis clusters
  • Cassandra
  • Dynamo
  • CDNs

We’ll cover it in detail during partitioning.

Health Checks

Load balancers continuously monitor servers.

Healthy

GET /health

200 OK

Unhealthy

500

Timeout

Connection refused

If a server fails, it is removed automatically.

Clients never notice.

Session Affinity (Sticky Sessions)

Normally

Request 1 → App2

Request 2 → App1

Request 3 → App3

With sticky sessions

User A

↓

Always App2

Advantages

  • Easy session management

Disadvantages

  • Uneven load
  • Harder scaling
  • Poor failover

Interview recommendation

Avoid sticky sessions when possible.

Instead:

  • Store sessions in Redis
  • Use JWTs
  • Keep services stateless

Active-Active vs Active-Passive

Active-Active

LB

↓

App1

App2

App3

All servers handle traffic.

Pros

  • Maximum utilization
  • Better throughput
  • No idle servers

Active-Passive

Primary

↓

Backup

Backup waits until failure.

Pros

  • Simpler failover

Cons

  • Idle resources

Global Load Balancing

Users should connect to the nearest region.

US Users

↓

US Region

European Users

↓

EU Region

Asia Users

↓

Asia Region

Techniques

  • GeoDNS
  • Anycast
  • Global load balancers

Benefits

  • Lower latency
  • Better availability
  • Regional failover

Common Interview Tradeoffs

Situation Solution
Equal servers Round robin
Variable request times Least connections
Different server sizes Weighted routing
Same user on same server Hashing / Sticky sessions
Regional traffic Geo routing

Common Failures

Hot server

One machine gets most requests.

Fix:

  • Better routing algorithm
  • Autoscaling

Unhealthy server

Requests continue to a failed machine.

Fix:

  • Health checks

Uneven capacity

Small machine receives same traffic as large one.

Fix:

  • Weighted routing

Sticky sessions

One server fills with long-lived users.

Fix:

  • Externalize session state

Interview Questions

You should be able to answer:

  • Why do we need a load balancer?
  • Layer 4 vs Layer 7?
  • Why are stateless services easier to balance?
  • When would you use least connections instead of round robin?
  • Why are sticky sessions discouraged?
  • How does the system detect failed servers?

Chapter Summary

Remember these seven ideas:

  1. Load balancers distribute requests across servers.
  2. Layer 4 routes network traffic, while Layer 7 understands HTTP requests.
  3. Health checks prevent traffic from reaching failed servers.
  4. Stateless services make load balancing simple.
  5. Weighted routing handles heterogeneous hardware.
  6. Sticky sessions should generally be avoided.
  7. Global load balancing reduces latency and improves availability.

Chapter 4: Partitioning (Sharding)

What is Partitioning?

Partitioning (or sharding) is the process of splitting data across multiple machines so that no single machine stores everything.

Instead of one database holding all users, each machine stores only a subset of the data.

Mental model

Without partitioning

        Database
   ┌───────────────┐
   │ All Users     │
   └───────────────┘


With partitioning

┌─────────┐ ┌─────────┐ ┌─────────┐
│Shard A  │ │Shard B  │ │Shard C  │
├─────────┤ ├─────────┤ ├─────────┤
│Users 1-3│ │Users 4-6│ │Users 7-9│
└─────────┘ └─────────┘ └─────────┘

Interview takeaway

Partitioning scales writes and storage.

Replication scales reads and availability.

Why Partition?

Eventually one database becomes the bottleneck.

Common limits:

  • Storage
  • CPU
  • Memory
  • Disk I/O
  • Write throughput

Adding replicas won’t increase write capacity because every write still goes to the leader.

Instead, split the data across multiple leaders.

Choosing a Partition Key

Every record needs a rule that determines where it lives.

Good partition keys:

  • Evenly distribute data
  • Minimize hotspots
  • Keep related data together
  • Rarely change

Examples

Application Partition Key
Social network User ID
Banking Account ID
E-commerce Customer ID
Ride sharing City or Region
Messaging Conversation ID

Interview tip

A poor partition key is one of the most common causes of scaling problems.

Partitioning Strategies

1. Hash Partitioning

Hash the key and assign it to a shard.

hash(user123)

↓

Shard 2

Pros

  • Even distribution
  • Simple
  • Handles random traffic well

Cons

  • Poor range queries
  • Nearby keys end up on different shards

Examples

  • DynamoDB
  • Cassandra
  • Redis Cluster

2. Range Partitioning

Each shard stores a range of values.

Shard A

A - G

Shard B

H - P

Shard C

Q - Z

Pros

  • Efficient range scans
  • Good locality

Cons

  • Hotspots
  • Uneven growth

Examples

  • Bigtable
  • HBase
  • Traditional SQL databases

3. Directory-Based Partitioning

A lookup service maps each key to a shard.

User123

↓

Lookup Table

↓

Shard 5

Pros

  • Flexible
  • Easy to rebalance

Cons

  • Requires metadata service
  • Extra lookup

4. Consistent Hashing

Regular hashing has a problem.

Suppose:

4 servers

↓

Add server #5

With modulo hashing:

Almost every key moves.

With consistent hashing:

Only a small fraction of keys move.

Mental model

      Ring

  A

D         B

    C

Keys are placed on the ring and assigned to the next server clockwise.

Adding or removing a server only affects nearby keys.

Used by:

  • Cassandra
  • Dynamo
  • Redis
  • CDNs

Interview takeaway

Consistent hashing minimizes data movement when cluster membership changes.

Rebalancing

As data grows, shards become uneven.

Rebalancing redistributes data across machines.

Triggers:

  • New servers
  • Removed servers
  • Hot partitions
  • Storage imbalance

Good systems rebalance automatically.

Hot Partitions

Not all shards receive equal traffic.

Example

Celebrity account

↓

Millions of requests

↓

Single shard overloaded

Even if storage is balanced, traffic may not be.

Solutions

  • Better partition key
  • Random suffixes
  • Further splitting
  • Caching
  • Read replicas

Interview tip

Most real-world scaling issues are caused by hotspots rather than storage limits.

Cross-Shard Queries

Suppose users are partitioned by User ID.

Question:

“Find everyone in California.”

Every shard must be searched.

This is called a scatter-gather query.

Pros

  • Works for any query

Cons

  • Slow
  • Expensive
  • Difficult to scale

Interview recommendation

Choose partition keys that match common access patterns.

Joins Across Shards

Example

Orders

↓

Shard A

Customers

↓

Shard B

Joining requires network communication.

Strategies

  • Duplicate small data
  • Denormalize
  • Application joins
  • Avoid distributed joins

Partitioning vs Replication

Partitioning Replication
Splits data Copies data
Scales writes Scales reads
Increases storage Improves availability
Every record lives on one shard Every record exists on multiple replicas

Interview takeaway

Most production systems use both.

Example:

           Users

              │

     Partition by User ID

      ┌───────┴───────┐
      ▼               ▼
   Shard A         Shard B
   ┌─────┐         ┌─────┐
   │ R1  │         │ R1  │
   │ R2  │         │ R2  │
   │ R3  │         │ R3  │
   └─────┘         └─────┘

Each shard is then replicated independently.

Common Interview Questions

You should be able to answer:

  • Why partition instead of adding replicas?
  • How do you choose a partition key?
  • What causes hotspots?
  • Why is consistent hashing useful?
  • How do systems rebalance data?
  • Why are cross-shard joins expensive?

Chapter Summary

Remember these eight ideas:

  1. Partitioning splits data across machines to scale writes and storage.
  2. The partition key determines where data lives.
  3. Hash partitioning balances load, while range partitioning supports efficient scans.
  4. Consistent hashing minimizes data movement when nodes join or leave.
  5. Rebalancing redistributes data as the cluster changes.
  6. Hot partitions are often caused by skewed traffic, not uneven storage.
  7. Cross-shard queries and joins are expensive because they require coordination across machines.
  8. Partitioning and replication solve different problems and are almost always used together.

Chapter 5: Replication

What is Replication?

Replication is the process of storing multiple copies of the same data on different machines.

If one machine fails, another replica can continue serving requests.

Mental model

Without replication

     User Data
         │
     ┌────────┐
     │Server A│
     └────────┘

Server A fails ❌

Data unavailable


With replication

          User Data
              │
     ┌────────┬────────┬────────┐
     ▼        ▼        ▼
 Server A  Server B  Server C

Interview takeaway

Partitioning distributes data.

Replication duplicates data.

Most production systems use both.

Why Replicate?

Replication provides three major benefits.

Goal Benefit
Availability Continue serving requests during failures
Durability Reduce the risk of data loss
Read Scalability Serve reads from multiple replicas

Interview tip

Replication improves reliability, not write throughput.

Replication Architectures

1. Leader-Follower (Primary-Replica)

One replica accepts writes. Followers copy changes from the leader.

          Write
            │
            ▼
        Leader
       /   |   \
      ▼    ▼    ▼
 Follower Follower Follower

Reads → Leader or Followers
Writes → Leader only

Write Flow

  1. Client sends write to leader.
  2. Leader commits locally.
  3. Leader replicates to followers.
  4. Followers acknowledge.

Read Flow

Applications may read:

  • From leader (strong consistency)
  • From followers (better scalability)

Advantages

  • Simple
  • Strong consistency possible
  • Excellent read scaling
  • Easy failover

Disadvantages

  • Leader is a write bottleneck
  • Replication lag
  • Leader election after failures

Examples

  • PostgreSQL
  • MySQL
  • MongoDB
  • Spanner (with additional consensus)

Replication Lag

Followers are usually slightly behind the leader.

Example

Time

Leader

Write X

Follower

........Write X

During this delay:

Leader → newest data

Follower → stale data

Possible effects

  • User refreshes page and doesn’t see their update.
  • Different users see different values.

Interview tip

Replication lag is one of the most common consistency issues.

Read Replicas

Followers can answer read requests.

          Write
            │
            ▼
        Leader
       /   |   \
      ▼    ▼    ▼
 Read   Read   Read

Benefits

  • Higher read throughput
  • Lower latency
  • Better availability

Good for

  • Product catalogs
  • Analytics
  • Dashboards
  • News feeds

Failover

If the leader crashes:

Leader ❌

↓

Follower promoted

↓

New Leader

This process is called failover.

Automatic failover requires:

  • Failure detection
  • Leader election
  • Client redirection

We’ll cover leader election in the Consensus chapter.

2. Multi-Leader Replication

Multiple replicas accept writes.

US Leader  ←→  EU Leader
      │             │
 Local Users   Local Users

Advantages

  • Lower write latency
  • Regional writes
  • Better disaster recovery

Disadvantages

  • Conflicting updates
  • More complex synchronization
  • Conflict resolution required

Examples

  • Geo-distributed applications
  • Offline editing
  • Collaborative documents

Conflict Resolution

Suppose:

US writes:

Name = Alice

EU writes:

Name = Bob

Both occur before synchronization.

Possible solutions

  • Last write wins
  • Application-defined merge
  • Version vectors
  • CRDTs (advanced)

Interview takeaway

Multi-leader systems trade consistency for availability and latency.

3. Leaderless Replication

No leader exists.

Clients write directly to multiple replicas.

        Client
      /   |   \
     ▼    ▼    ▼
    R1   R2   R3

Data is considered written after enough replicas acknowledge.

Advantages

  • No single write bottleneck
  • High availability
  • Survives replica failures

Disadvantages

  • More complex reads
  • Conflict resolution
  • Eventual consistency

Examples

  • Dynamo
  • Cassandra
  • Riak

Read Repair

Suppose:

Replica 1

Version 5

Replica 2

Version 4

Replica 3

Version 5

During a read:

System detects Replica 2 is outdated.

Replica 2 is automatically updated.

This is called read repair.

Hinted Handoff

Suppose Replica B is temporarily unavailable.

Instead of rejecting writes:

Replica A temporarily stores B’s updates.

When B returns:

Stored updates are forwarded.

Benefits

  • Higher availability
  • No lost writes

Common in leaderless systems.

Synchronous vs Asynchronous Replication

Synchronous

Leader waits for replicas before replying.

Write

↓

Leader

↓

Followers

↓

ACK

↓

Client

Pros

  • Strong consistency
  • No data loss after acknowledgment

Cons

  • Higher latency
  • Slower writes

Asynchronous

Leader responds immediately.

Replication happens afterward.

Write

↓

Leader

↓

Client

↓

Followers (later)

Pros

  • Fast writes
  • Better throughput

Cons

  • Replication lag
  • Possible data loss if leader crashes before replication

Interview tip

Most production systems use asynchronous replication by default, sometimes with synchronous replication for critical data.

Replication vs Backup

Replication is not a backup.

Replication Backup
Keeps copies synchronized Preserves historical state
Protects against machine failures Protects against accidental deletion or corruption
Errors replicate too Previous versions can be restored

Common Interview Tradeoffs

Requirement Preferred Approach
Read-heavy workload Leader-follower with read replicas
Lowest write latency Multi-leader
Maximum availability Leaderless
Simple operations Leader-follower
Strong consistency Synchronous replication
High throughput Asynchronous replication

Common Interview Questions

You should be able to answer:

  • Why replicate data?
  • Why doesn’t replication increase write throughput?
  • What is replication lag?
  • When would you use read replicas?
  • Leader-follower vs leaderless?
  • Multi-leader vs leader-follower?
  • Synchronous vs asynchronous replication?
  • Why isn’t replication a backup?

Chapter Summary

Remember these ten ideas:

  1. Replication creates multiple copies of data for availability and durability.
  2. Leader-follower is the most common replication model.
  3. Read replicas improve read scalability but may return stale data.
  4. Replication lag is the delay between the leader and followers.
  5. Failover promotes a follower when the leader fails.
  6. Multi-leader reduces write latency but introduces conflicts.
  7. Leaderless replication maximizes availability but requires quorum reads and writes.
  8. Synchronous replication favors consistency, while asynchronous replication favors performance.
  9. Replication improves reliability, not write throughput.
  10. Replication protects against machine failures, not accidental data loss.

Chapter 6: Consistency

What is Consistency?

Consistency defines what different clients observe when reading replicated data.

The key question is:

“If one client writes new data, when will everyone else see that update?”

Different systems make different guarantees depending on the tradeoff between correctness, latency, and availability.

Interview takeaway

Consistency is about what clients observe, not whether replicas eventually synchronize.

The Fundamental Problem

Suppose we have three replicas.

        User
          │
          ▼
        Leader
       /      \
 Replica B   Replica C

A client writes:

Balance = $100

Immediately afterward, another client reads from Replica C.

Should they see:

$100

or

$90

That question is consistency.

Strong Consistency

After a successful write, every future read returns the latest value.

Write X

↓

Read

↓

Always X

Advantages

  • Simple mental model
  • No stale reads
  • Easier application logic

Disadvantages

  • Higher latency
  • More coordination
  • Lower availability during failures

Examples

  • Google Spanner
  • Traditional SQL databases
  • etcd

Good for

  • Banking
  • Payments
  • Inventory
  • Configuration systems

Eventual Consistency

Replicas may temporarily disagree, but if no new writes occur, they eventually converge.

Time

Leader

Version 5

Replica

Version 4

↓

Version 5

Advantages

  • High availability
  • Low latency
  • Excellent scalability

Disadvantages

  • Stale reads
  • Temporary inconsistencies
  • More application complexity

Examples

  • Cassandra
  • DynamoDB (default)
  • DNS
  • Many caches

Good for

  • Social media
  • Product catalogs
  • Analytics
  • Recommendations

Interview takeaway

Most internet-scale systems use eventual consistency for non-critical data.

Causal Consistency

Operations that are causally related are observed in the same order by everyone.

Example

Alice posts:

"I'm here!"

Bob replies:

"Welcome!"

Everyone must see:

"I'm here!"

↓

"Welcome!"

They should never see the reply before the original post.

Sequential Consistency

All clients observe the same global order of operations, although that order doesn’t have to match real time.

Example

Write A

Write B

Everyone agrees:

A happened before B

even if A and B occurred on different machines.

Linearizability

The strongest commonly discussed consistency model.

Every operation appears to happen atomically at one instant between its start and finish.

Mental model

Write

─────●─────

Read

────────●──

If the write finishes before the read starts, the read must observe the new value.

Interview shortcut

Linearizable = behaves like a single perfect computer.

Session Guarantees

Applications often don’t need full strong consistency.

Instead, they provide guarantees within one user’s session.

Read-Your-Writes

If you write data, you’ll always see your own update.

Example

Update profile picture.

Refresh page.

You expect to see the new picture immediately.

Monotonic Reads

Once you’ve seen newer data, you never go backwards.

Bad

Version 5

↓

Version 4

Good

4

↓

5

↓

6

Monotonic Writes

Writes from one client are applied in the order they were issued.

Writes Follow Reads

If you’ve observed a value, future writes are based on at least that version.

Useful in collaborative editing.

Consistency Spectrum

Strong
   │
Linearizable
   │
Sequential
   │
Causal
   │
Session Guarantees
   │
Eventual

Moving upward:

↑ More coordination

↑ Higher latency

↑ Stronger guarantees

Moving downward:

↑ Better availability

↑ Better scalability

Choosing the Right Model

Application Consistency
Bank account Strong
Payments Strong
Inventory Strong
Chat messages Causal
Social feed Eventual
Product catalog Eventual
Analytics Eventual
Configuration service Strong

Interview tip

Don’t default to strong consistency. Match the guarantee to the business requirement.

Common Interview Tradeoffs

Want… Usually Means…
Strong consistency More coordination
Lower latency Weaker consistency
Better availability Eventual consistency
Simpler applications Strong consistency
Higher throughput Less synchronization

Common Interview Questions

You should be able to answer:

  • What is consistency?
  • Strong vs eventual consistency?
  • What is linearizability?
  • What is causal consistency?
  • What are session guarantees?
  • Why doesn’t every system use strong consistency?
  • Which applications require strong consistency?

Chapter Summary

Remember these ten ideas:

  1. Consistency defines what clients observe after writes.
  2. Strong consistency guarantees every read sees the latest write.
  3. Eventual consistency allows temporary divergence but guarantees convergence.
  4. Linearizability is the strongest commonly used consistency model.
  5. Causal consistency preserves cause-and-effect relationships.
  6. Session guarantees improve user experience without global coordination.
  7. Stronger consistency requires more coordination and latency.
  8. Weaker consistency improves scalability and availability.
  9. Choose consistency based on business requirements, not preference.
  10. There is no universally “best” consistency model.

Chapter 7: CAP Theorem

What is the CAP Theorem?

The CAP Theorem states that if a network partition occurs, a distributed system must choose between:

  • Consistency (C): Every read returns the latest write.
  • Availability (A): Every request receives a response.
  • Partition Tolerance (P): The system continues operating despite network failures.

Interview takeaway

CAP is only about what happens during a network partition.

The Three Properties

Consistency (C)

All clients see the same data at the same time.

Example

Client 1

Write X

↓

Client 2

Read

↓

Must see X

If the write succeeds, every future read observes it.

Availability (A)

Every request receives a response.

Even if some machines have failed, the system continues answering requests.

Important:

Availability says nothing about whether the answer is the newest one.

A stale response is still considered “available.”

Partition Tolerance (P)

A network partition means some machines cannot communicate.

      Network Failure

 Replica A      X      Replica B

Both replicas are still running.

They simply cannot exchange messages.

This is the key scenario CAP addresses.

Why is Partition Tolerance Non-Negotiable?

Networks fail.

Examples include:

  • Cable cuts
  • Router failures
  • Cloud outages
  • Cross-region network issues
  • Packet loss
  • Temporary disconnects

You cannot choose to ignore partitions.

In practice:

P is mandatory.

The real choice is:

Consistency or Availability during a partition.

Interview shortcut

Think of CAP as “CP vs AP.”

CP Systems

Choose Consistency.

Example

Replica A and Replica B lose communication.

Replica A receives a write.

To preserve consistency:

Replica A refuses the write until communication is restored.

Write

↓

Cannot verify with replicas

↓

Reject request

Advantages

  • No stale reads
  • Strong guarantees
  • Easier reasoning

Disadvantages

  • Some requests fail during partitions

Examples

  • Spanner
  • ZooKeeper
  • etcd

Good for

  • Banking
  • Metadata
  • Configuration
  • Leader election

AP Systems

Choose Availability.

Partition occurs.

Replica A accepts writes.

Replica B also accepts writes.

Both continue serving users.

Partition

↓

Both replicas continue operating

↓

Synchronize later

Advantages

  • Always available
  • Better user experience
  • Lower latency

Disadvantages

  • Temporary inconsistency
  • Conflict resolution required

Examples

  • Cassandra
  • Dynamo
  • Riak

Good for

  • Social feeds
  • Recommendations
  • Shopping carts
  • Analytics

Visual Summary

             Network Partition

                   │

          ┌────────┴────────┐

          ▼                 ▼

      Consistency      Availability

      Reject writes     Accept writes

      No stale data     Possible stale data

Why CA Doesn’t Really Exist

People often say systems can be:

CA

CP

AP

In reality:

Without partitions:

Nearly every system behaves like CA.

With partitions:

You must choose CP or AP.

Since partitions are unavoidable, pure CA systems don’t exist in real distributed environments.

Interview tip

If someone says “My system is CA,” ask:

“What happens when the network breaks?”

Real-World Examples

Bank Transfer

You transfer $100.

The network partitions.

Would you rather:

Option 1

The transaction temporarily fails.

or

Option 2

Your account shows two different balances.

Most people choose Option 1.

Banks are CP.

Instagram Likes

You like a photo.

Your friend sees:

124 likes

instead of

125 likes

for a few seconds.

Not a big problem.

Instagram can choose AP for this feature.

Inventory Systems

One item left.

Two customers purchase simultaneously.

Strong consistency prevents overselling.

Usually implemented as CP.

CAP vs Consistency Models

CAP and consistency models are related but different.

Consistency Models CAP
Defines what clients observe Defines behavior during partitions
Always relevant Only relevant during partitions
Strong, causal, eventual, etc. CP or AP tradeoff

Interview tip

Don’t confuse “strong consistency” with “CP.”

A system can provide strong consistency most of the time, and CAP only becomes relevant when communication between replicas fails.

Common Misconceptions

“Choose any two.”

Not exactly.

The famous slogan is misleading.

Partition tolerance isn’t optional.

The real decision is:

When partitions occur:

Consistency

or

Availability?

“AP means incorrect.”

No.

AP systems eventually converge.

They simply allow temporary inconsistency.

“CP systems never fail.”

False.

CP systems preserve correctness by rejecting or delaying requests.

Failures become visible to users.

Common Interview Questions

You should be able to answer:

  • What is a network partition?
  • Why is P mandatory?
  • What happens in a CP system during a partition?
  • What happens in an AP system?
  • Why doesn’t CA really exist?
  • Which applications should choose CP?
  • Which applications should choose AP?

Chapter Summary

Remember these eight ideas:

  1. CAP only applies during network partitions.
  2. Partition tolerance is unavoidable in distributed systems.
  3. CP systems reject or delay requests to preserve consistency.
  4. AP systems continue serving requests but may return stale data.
  5. Strong consistency and CAP are related but not the same concept.
  6. Most production systems are effectively choosing between CP and AP during failures.
  7. The right choice depends on business requirements.
  8. Correctness-critical systems usually prefer CP, while user-facing, latency-sensitive systems often prefer AP.

Chapter 8: Quorums

What is a Quorum?

A quorum is the minimum number of replicas that must participate in a read or write operation before it is considered successful.

Instead of waiting for every replica, we wait for “enough” replicas.

Interview takeaway

Quorums balance consistency, availability, and latency.

Why Do We Need Quorums?

Suppose we replicate every piece of data three times.

          User
            │
            ▼
     ┌──────┬──────┬──────┐
     ▼      ▼      ▼
    R1     R2     R3

If one replica is temporarily unavailable, should every write fail?

No.

Instead, require only a majority of replicas.

This allows the system to continue operating despite failures.

The Three Numbers

Every quorum system revolves around three values.

Symbol Meaning
N Total number of replicas
W Replicas that must acknowledge a write
R Replicas contacted during a read

Example

N = 3

R = 2

W = 2

Majority Quorums

The most common configuration is:

N = 3

R = 2

W = 2

Write

Client

↓

R1 ✓

R2 ✓

R3 (doesn't matter)

The write succeeds because two replicas acknowledged it.

Read

Client

↓

Read R2

Read R3

At least one replica must contain the latest value.

The Key Equation

The most important formula in quorum systems:

[ R + W > N ]

Why?

Because every read overlaps with every successful write.

That overlap guarantees the reader contacts at least one replica containing the newest data.

Interview tip

This is one of the few distributed systems equations worth memorizing.

Example

Suppose

N = 3

R = 2

W = 2

A write reaches

Replica 1 ✓

Replica 2 ✓

Later a read contacts

Replica 2 ✓

Replica 3

Replica 2 participated in both operations.

The latest value is observed.

What Happens if the Equation Doesn’t Hold?

Example

N = 3

R = 1

W = 1

Possible write

Replica 1

Possible read

Replica 3

No overlap.

The read may return stale data.

This configuration maximizes availability but weakens consistency.

Common Configurations

Configuration Behavior
R=1, W=1 Fastest, weakest consistency
R=1, W=N Fast reads, slow writes
R=N, W=1 Slow reads, fast writes
R=2, W=2 (N=3) Balanced majority quorum
R=N, W=N Strongest consistency, highest latency

Read Repair

Suppose

Replica A

Version 10

Replica B

Version 9

Replica C

Version 10

A read contacts all three replicas.

The system notices Replica B is stale.

It automatically updates Replica B.

This is called read repair.

It helps replicas converge over time.

Sloppy Quorums

Suppose Replica B is unavailable.

Instead of rejecting the write:

Replica A ✓

Replica C ✓

Temporary Replica D ✓

The system temporarily stores the data elsewhere.

Later, the data is moved back.

Benefits

  • Higher availability
  • Fewer rejected writes

Tradeoff

  • Weaker consistency guarantees

Quorums and CAP

Quorums don’t eliminate the CAP tradeoff.

Instead, they let us tune the system.

Increase W

  • Stronger consistency
  • Higher write latency
  • Lower availability

Decrease W

  • Faster writes
  • Better availability
  • Greater chance of stale reads

Likewise for R.

Leaderless Replication

Quorums are most commonly used in leaderless systems.

            Client
          /    |    \
         ▼     ▼     ▼
       R1     R2     R3

The client waits until W replicas acknowledge the write.

Later, reads contact R replicas.

Examples

  • Cassandra
  • Dynamo
  • Riak

Leader-Based Systems

Leader-follower databases also use quorum concepts.

Example

Raft requires a majority of replicas to acknowledge log entries before they are committed.

We’ll see this in the next chapter on Consensus.

Common Interview Tradeoffs

Increase… Effect
W Better consistency, slower writes
R Better read freshness, slower reads
N Higher fault tolerance, more storage and network overhead

Common Interview Questions

You should be able to answer:

  • What is a quorum?
  • What do N, R, and W represent?
  • Why does (R + W > N) matter?
  • Why aren’t all replicas required?
  • What is read repair?
  • What are sloppy quorums?
  • How do quorums relate to CAP?

Chapter Summary

Remember these nine ideas:

  1. A quorum is the minimum number of replicas needed for a successful operation.
  2. N is the replication factor, W is the write quorum, and R is the read quorum.
  3. The key equation is (R + W > N).
  4. Majority quorums provide a good balance between consistency and availability.
  5. Smaller quorums improve latency but increase the chance of stale reads.
  6. Read repair helps stale replicas catch up.
  7. Sloppy quorums improve availability during failures.
  8. Leaderless databases rely heavily on quorum protocols.
  9. Quorums are one practical way to navigate the CAP tradeoff.

Chapter 9: Consensus (Raft & Paxos)

What is Consensus?

Consensus is the process by which multiple machines agree on a single value or sequence of operations, even if some machines fail.

The fundamental question is:

“How can a group of unreliable machines behave like one reliable machine?”

Interview takeaway

Consensus is about agreement, not replication.

Why Do We Need Consensus?

Imagine three replicas.

      A      B      C

Suppose A crashes.

Who becomes the new leader?

If B thinks it’s the leader and C also thinks it’s the leader, the system can become inconsistent.

Consensus ensures:

  • Only one leader exists.
  • Everyone agrees on the same order of operations.
  • Every replica eventually reaches the same state.

What Problems Does Consensus Solve?

Consensus is commonly used for:

Problem Example
Leader election Choose one primary node
Metadata Store cluster configuration
Membership Track which nodes are alive
Log replication Keep replicas in the same order
Configuration Kubernetes, etcd, ZooKeeper

Notice:

Consensus usually manages metadata.

Your user data often uses different replication mechanisms.

The Consensus Properties

A correct consensus algorithm guarantees:

Agreement

Every healthy node chooses the same value.

Validity

Only proposed values can be chosen.

Termination

Eventually a decision is reached.

Fault Tolerance

The system continues despite some failures.

Raft

Raft is the consensus algorithm you’ll most likely discuss in interviews.

It was designed to be easier to understand than Paxos.

Mental model

Follower

↓

Election

↓

Leader

↓

Replicate Log

↓

Followers

Everything revolves around one leader.

Node States

Every Raft node is always in one of three states.

Follower

↓

Candidate

↓

Leader

Followers

  • Do nothing except respond to requests.

Candidate

  • Runs for election.

Leader

  • Handles client writes.
  • Replicates log entries.

Interview shortcut

Most of the time, every node is a follower.

Leader Election

Initially

Follower

Follower

Follower

Suppose the leader crashes.

Followers stop receiving heartbeats.

Election timeout expires.

One follower becomes a candidate.

Candidate

↓

Requests votes

If it receives a majority:

Leader

Otherwise:

A new election begins.

Heartbeats

Leaders periodically send heartbeat messages.

Leader

↓

Heartbeat

↓

Followers

Purpose

  • Prove leader is alive.
  • Prevent unnecessary elections.

If heartbeats stop:

Followers assume the leader failed.

Log Replication

Clients never write directly to followers.

Instead

Client

↓

Leader

↓

Followers

The leader appends every operation to its log.

Example

1

Create User

2

Deposit $100

3

Update Email

Followers copy the exact same log.

If everyone has the same ordered log, everyone eventually reaches the same state.

Interview takeaway

Raft replicates commands, not database pages.

Commit Rule

A command isn’t committed immediately.

Instead:

Leader waits until a majority acknowledge it.

Example

Leader ✓

Follower ✓

Follower ✗

Two out of three replicas.

The command is committed.

This is where Raft uses quorum voting.

Split Brain

Imagine two leaders.

Leader A

Leader B

Both accept writes.

The cluster diverges.

Consensus prevents this.

Only a majority can elect a leader.

There can only be one leader at a time.

Failure Example

Cluster

A

B

C

Leader A crashes.

B becomes candidate.

B receives votes from B and C.

2 / 3

Majority

B becomes leader.

Clients continue writing.

Paxos

Paxos solves the same problem.

Compared to Raft:

Raft Paxos
Easier to understand More mathematically elegant
Single clear leader More abstract
Popular in education and industry Popular in research
Common interview topic Less often discussed in depth

Interview tip

You rarely need to explain Paxos in detail.

Understanding why Raft was created is usually enough.

Consensus vs Replication

A very common interview question.

Replication

Copies data.

Consensus

Ensures everyone agrees on the order of updates.

Replication answers

“Where are my copies?”

Consensus answers

“Which update happened first?”

Consensus vs Quorums

Quorums

Majority voting for reads and writes.

Consensus

Majority voting to agree on one history.

Consensus often uses quorum voting internally.

Consensus vs Distributed Transactions

Consensus

Agreement.

Distributed transactions

Atomic execution across services.

Very different problems.

Real-World Systems

System Uses Consensus?
etcd Yes (Raft)
ZooKeeper Yes (ZAB, Raft-like)
Kubernetes Yes (via etcd)
CockroachDB Yes (Raft)
Spanner Yes (Paxos)

Interview takeaway

Consensus is usually used for cluster metadata, not every application request.

Common Interview Questions

You should be able to answer:

  • What problem does consensus solve?
  • Why do we need leader election?
  • What are the three Raft node states?
  • Why are heartbeats necessary?
  • How does Raft commit a log entry?
  • Why can’t there be two leaders?
  • Raft vs Paxos?
  • Consensus vs replication?
  • Consensus vs quorums?

Chapter Summary

Remember these ten ideas:

  1. Consensus ensures replicas agree on one history despite failures.
  2. Raft is the most common consensus algorithm discussed in interviews.
  3. Every node is a follower, candidate, or leader.
  4. Leaders are elected by majority vote.
  5. Heartbeats prevent unnecessary elections.
  6. Clients write only to the leader.
  7. Log entries are committed after a majority acknowledge them.
  8. Consensus prevents split-brain scenarios.
  9. Replication copies data, while consensus orders updates.
  10. Systems like Kubernetes, etcd, CockroachDB, and Spanner rely on consensus.

Chapter 10: Time & Ordering

Why is Time Hard?

On a single machine, ordering is simple.

Write A

↓

Write B

A clearly happened before B.

In a distributed system, operations occur on different machines with different clocks.

Machine A          Machine B

10:00:01          09:59:58

Whose clock is correct?

You can’t reliably tell.

Interview takeaway

There is no perfectly synchronized global clock.

The Two Problems

Distributed systems must answer:

  1. What time did an event happen?
  2. Which event happened first?

These are not always the same question.

Clock Skew

Every machine has its own physical clock.

Those clocks naturally drift over time.

Server A

12:00:00

Server B

11:59:58

Even a small difference can cause:

  • Incorrect timestamps
  • Wrong ordering
  • Expired sessions
  • Duplicate processing

Physical Clocks

Most systems synchronize clocks using NTP.

Server

↓

NTP

↓

Adjust clock

Advantages

  • Simple
  • Works well for timestamps

Disadvantages

  • Never perfectly synchronized
  • Network delays introduce error

Interview tip

Never rely solely on timestamps to order distributed events.

Logical Clocks

Instead of measuring time, logical clocks measure causality.

Question:

Did Event A happen before Event B?

Not:

What time was it?

Lamport Clocks

Each node maintains a logical counter.

Rules

  1. Increment before every event.
  2. Include the counter in every message.
  3. Receiver sets:

[ \text{clock} = \max(\text{local}, \text{received}) + 1 ]

Example

Node A

1

↓

Send (2)

──────────────►

Node B

5

↓

Receives (2)

↓

Clock becomes 6

Advantages

  • Simple
  • Establishes a consistent event ordering

Limitation

Lamport clocks cannot tell whether two events were truly independent.

Vector Clocks

Instead of one counter, each node tracks one counter per node.

Example

A

[3,1,0]

B

[3,2,0]

C

[3,2,1]

Advantages

  • Detect concurrent events
  • Capture causality

Disadvantages

  • Metadata grows with cluster size
  • More complex

Used in

  • Dynamo
  • Riak
  • Version conflict detection

Happens-Before Relationship

Event A “happens before” Event B if:

  • A occurred first on the same machine, or
  • A sent a message that B received.

Example

A writes

↓

Message sent

↓

B receives

We know:

A happened before B.

Independent events have no defined order.

Concurrent Events

Suppose:

Machine A

Write X

Machine B

Write Y

No messages are exchanged.

Which happened first?

Answer:

You cannot know.

They are concurrent.

Interview takeaway

Concurrency is fundamental to distributed systems.

Event Ordering

Different systems require different guarantees.

Ordering Example
No ordering Metrics collection
Per-partition ordering Kafka
Total ordering Raft log
Causal ordering Chat applications

Stronger ordering requires more coordination.

Google’s TrueTime

Most systems cannot provide globally synchronized clocks.

Spanner introduces TrueTime.

Instead of returning a single timestamp, it returns an interval.

Current time

[10:00:00.100,

10:00:00.105]

The true time lies somewhere inside the interval.

By waiting until the uncertainty window passes, Spanner can safely assign globally ordered timestamps.

Interview takeaway

TrueTime enables Spanner’s globally consistent transactions.

Timeouts

Many distributed algorithms depend on timeouts.

Example

Raft leader election.

Heartbeat stops

↓

Election timeout expires

↓

Start election

Timeouts detect failures.

They do not prove failures.

The network might simply be slow.

Idempotency

Because messages may be delayed or retried, operations should often be idempotent.

Example

Transfer $100

↓

Retry

↓

Should still execute once

Common techniques

  • Request IDs
  • Sequence numbers
  • Deduplication tables

Common Interview Tradeoffs

Goal Technique
Human-readable timestamps Physical clocks
Event ordering Logical clocks
Detect concurrency Vector clocks
Global transactions TrueTime
Safe retries Idempotency

Common Interview Questions

You should be able to answer:

  • Why can’t distributed systems trust clocks?
  • What is clock skew?
  • Physical vs logical clocks?
  • Lamport vs vector clocks?
  • What does “happens-before” mean?
  • Why are concurrent events difficult?
  • What is TrueTime?
  • Why are idempotent operations important?

Chapter Summary

Remember these ten ideas:

  1. Every machine has its own imperfect clock.
  2. Clock skew makes timestamps unreliable for ordering.
  3. Physical clocks estimate time, while logical clocks capture causality.
  4. Lamport clocks establish a consistent event order.
  5. Vector clocks detect concurrent updates.
  6. Not every pair of events has a meaningful order.
  7. Different systems require different ordering guarantees.
  8. TrueTime enables Spanner’s globally ordered transactions.
  9. Timeouts detect suspected failures, not guaranteed failures.
  10. Idempotency makes retries safe in unreliable networks.

Chapter 11: Distributed Transactions

What is a Distributed Transaction?

A distributed transaction is a single logical operation that spans multiple services or databases.

Example:

Transfer Money

Debit Account A

↓

Credit Account B

↓

Send Notification

All steps should either:

  • Succeed together
  • Fail together

Interview takeaway

Distributed transactions try to preserve consistency across multiple systems.

Why Are They Hard?

On a single database:

BEGIN

Update A

Update B

COMMIT

Easy.

Across services:

Account Service

↓

Payment Service

↓

Notification Service

Each service:

  • Has its own database
  • Can fail independently
  • Has its own network latency

There is no shared transaction manager.

ACID Refresher

Traditional database transactions guarantee:

Property Meaning
Atomicity All or nothing
Consistency Database remains valid
Isolation Concurrent transactions don’t interfere
Durability Committed changes survive failures

These guarantees are relatively straightforward inside a single database.

Across multiple services, they become much harder.

Two-Phase Commit (2PC)

The classic distributed transaction protocol.

Phase 1: Prepare

Coordinator asks every participant:

Can you commit?

Example

Coordinator

↓

Service A ✓

Service B ✓

Service C ✓

Each participant:

  • Executes locally
  • Locks its data
  • Replies Yes or No

Phase 2: Commit

If everyone votes Yes:

Commit

Otherwise:

Abort

Everyone either commits or rolls back.

Advantages

  • Strong consistency
  • Atomic updates
  • Simple mental model

Disadvantages

Blocking

Suppose the coordinator crashes after everyone prepares.

Participants remain locked waiting for instructions.

Prepared

↓

Waiting...

↓

Waiting...

↓

Waiting...

The transaction cannot complete.

Latency

Every participant must coordinate before committing.

As more services are added:

  • More network calls
  • More waiting
  • Higher failure probability

Why Modern Systems Avoid 2PC

Most internet-scale systems prioritize:

  • Availability
  • Throughput
  • Independent service ownership

2PC reduces all three.

Interview takeaway

2PC is correct but rarely used across microservices.

Saga Pattern

Instead of one large transaction:

Break work into multiple local transactions.

Example

Reserve Flight

↓

Reserve Hotel

↓

Reserve Rental Car

Each service commits independently.

If something later fails:

Run compensating actions.

Compensation

Example

Reserve Hotel

↓

Reserve Flight

↓

Payment fails

↓

Cancel Flight

↓

Cancel Hotel

Rather than rolling back, we perform new operations that undo the work.

Choreography vs Orchestration

Choreography

Each service publishes events.

Order Created

↓

Inventory Service

↓

Payment Service

↓

Shipping Service

Pros

  • Loosely coupled
  • Easy to extend

Cons

  • Harder to understand
  • Complex debugging

Orchestration

One coordinator controls the workflow.

Orchestrator

↓

Inventory

↓

Payment

↓

Shipping

Pros

  • Easier monitoring
  • Simpler workflow

Cons

  • Central coordinator

Idempotency

Messages may be retried.

Example

Charge Customer

↓

Timeout

↓

Retry

Without idempotency:

Customer gets charged twice.

Instead:

Use a unique request ID.

Repeated requests return the same result.

Interview takeaway

Distributed systems should assume retries happen.

Outbox Pattern

Problem

Suppose:

Save Order

↓

Crash

↓

Publish Event

The database is updated.

The event is never published.

System becomes inconsistent.

Solution

Database Transaction

Save Order

+

Save Event

↓

Commit

↓

Background Worker

↓

Publish Event

The database and event are committed atomically.

Publishing happens later.

Used by many event-driven systems.

Exactly Once?

Interview trick question.

Exactly-once delivery is extremely difficult.

Most systems instead provide:

  • At least once delivery
  • Idempotent consumers

Together they behave almost like exactly once.

Common Interview Tradeoffs

Approach Advantages Disadvantages
2PC Strong consistency Blocking, slow
Saga High availability Compensation required
Outbox Reliable events Eventual consistency
Idempotency Safe retries Additional bookkeeping

Where Are These Used?

Pattern Typical Usage
ACID Single SQL database
2PC Banking, legacy enterprise systems
Saga Microservices
Outbox Event-driven architectures
Idempotency Payments, APIs, messaging

Common Interview Questions

You should be able to answer:

  • Why are distributed transactions difficult?
  • What are the two phases of 2PC?
  • Why can 2PC block?
  • Why do most microservices prefer sagas?
  • What is a compensating transaction?
  • Choreography vs orchestration?
  • Why is idempotency important?
  • What problem does the outbox pattern solve?

Chapter Summary

Remember these ten ideas:

  1. Distributed transactions span multiple services or databases.
  2. ACID is straightforward within one database but difficult across many services.
  3. 2PC provides atomic commits but introduces blocking and latency.
  4. Modern distributed systems generally avoid 2PC for user-facing workloads.
  5. Sagas replace one global transaction with a sequence of local transactions.
  6. Compensating actions undo completed work when later steps fail.
  7. Choreography is decentralized, while orchestration uses a central coordinator.
  8. Idempotency ensures retries don’t produce duplicate side effects.
  9. The outbox pattern keeps database updates and events consistent.
  10. Most large-scale systems favor eventual consistency and compensation over global transactions.

Chapter 12: Messaging

What is Messaging?

Messaging allows services to communicate asynchronously through an intermediary (a message broker or queue), instead of calling each other directly.

Instead of waiting for another service to finish, a producer sends a message and continues processing.

Interview takeaway

Messaging decouples producers from consumers.

Why Do We Need Messaging?

Imagine an order service.

Without messaging:

Client
   │
   ▼
Order Service
   │
   ├──► Payment
   ├──► Inventory
   ├──► Shipping
   └──► Email

If any downstream service is slow or unavailable, the entire request is delayed or fails.

With messaging:

Client
   │
   ▼
Order Service
   │
   ▼
 Message Queue
   │
 ┌─┼─────────────┐
 ▼ ▼             ▼
Payment      Inventory
Shipping       Email

The order service responds immediately after publishing the message. Consumers process it independently.

Core Components

Component Role
Producer Sends messages
Broker Stores and routes messages
Consumer Processes messages
Queue Holds messages until consumed
Topic Broadcasts messages to subscribers

Queues vs Pub/Sub

Queue (Point-to-Point)

Each message is processed by exactly one consumer.

Producer
    │
    ▼
 Queue
 ┌──┴──┐
 ▼     ▼
Worker1 Worker2

Only one worker processes each message.

Use cases

  • Background jobs
  • Image processing
  • Video transcoding
  • Email sending

Publish/Subscribe (Pub/Sub)

Every subscriber receives a copy.

          Producer
             │
             ▼
           Topic
     ┌──────┼──────┐
     ▼      ▼      ▼
 Analytics Search Notifications

Use cases

  • Event-driven systems
  • Notifications
  • Audit logs
  • Cache invalidation

Interview shortcut

Queue = work distribution.

Pub/Sub = event distribution.

Why Asynchronous Communication?

Synchronous RPC

Service A

↓

Wait...

↓

Service B

Latency accumulates.

Asynchronous messaging

Service A

↓

Publish

↓

Continue

Broker

↓

Service B (later)

Advantages

  • Higher throughput
  • Better fault tolerance
  • Independent scaling
  • Better resilience

Tradeoff

You usually get eventual consistency instead of immediate consistency.

Message Ordering

Some applications don’t care about order.

Example

Metrics collection.

Others do.

Example

Bank account events.

Deposit $100

↓

Withdraw $20

Reversing them changes the result.

Ordering options

Ordering Example
None Metrics
Per partition Kafka
Global Rare, expensive

Interview tip

Global ordering is difficult and expensive. Most systems only guarantee ordering within a partition.

Delivery Guarantees

At Most Once

Message is delivered zero or one time.

Pros

  • No duplicates

Cons

  • Messages may be lost

At Least Once

Retry until acknowledged.

Pros

  • No message loss

Cons

  • Duplicates possible

Most production systems use this.

Exactly Once

Each message is processed exactly once.

In practice:

Very difficult.

Usually implemented through:

  • At-least-once delivery
  • Idempotent consumers

Interview takeaway

“Exactly once” usually means exactly-once processing semantics, not literally one network delivery.

Dead Letter Queue (DLQ)

Suppose a consumer repeatedly fails.

Message

↓

Retry

↓

Retry

↓

Retry

↓

Dead Letter Queue

Benefits

  • Prevents blocking the queue
  • Allows manual investigation
  • Avoids infinite retry loops

Retry Strategies

Immediate retries can make outages worse.

Instead:

Exponential backoff.

Retry 1

1 second

Retry 2

2 seconds

Retry 3

4 seconds

Retry 4

8 seconds

Often combined with random jitter to prevent many clients from retrying simultaneously.

Backpressure

Suppose producers generate messages faster than consumers process them.

Producer

1000 msgs/sec

↓

Queue

↓

Consumer

100 msgs/sec

The queue grows indefinitely.

Solutions

  • Autoscale consumers
  • Rate limiting
  • Flow control
  • Drop low-priority messages

Popular Messaging Systems

System Best For
Kafka High-throughput event streaming
RabbitMQ Traditional message queues
Amazon SQS Managed cloud queue
Google Pub/Sub Global event streaming
Pulsar Multi-tenant streaming

Interview tip

Kafka is a distributed log first and a messaging system second.

Messaging vs RPC

RPC Messaging
Synchronous Asynchronous
Immediate response Eventual processing
Tight coupling Loose coupling
Lower latency Better scalability
Caller waits Caller continues

Use RPC when:

  • Immediate response is required.

Use messaging when:

  • Work can happen later.

Common Interview Tradeoffs

Requirement Preferred Solution
Immediate result RPC
High throughput Messaging
Loose coupling Pub/Sub
Background work Queue
Reliable processing At least once + idempotency
Fault isolation Messaging

Common Interview Questions

You should be able to answer:

  • Why use messaging instead of RPC?
  • Queue vs Pub/Sub?
  • At-most-once vs at-least-once vs exactly-once?
  • Why are idempotent consumers important?
  • What is a dead letter queue?
  • What is backpressure?
  • Why is global ordering difficult?
  • Why does Kafka only guarantee ordering within a partition?

Chapter Summary

Remember these ten ideas:

  1. Messaging enables asynchronous communication between services.
  2. Queues distribute work, while Pub/Sub distributes events.
  3. Messaging improves scalability, resilience, and fault isolation.
  4. Most production systems favor at-least-once delivery with idempotent consumers.
  5. Dead letter queues isolate permanently failing messages.
  6. Exponential backoff prevents retry storms.
  7. Backpressure occurs when producers outpace consumers.
  8. Ordering guarantees are usually limited to a partition.
  9. Kafka is optimized for durable, high-throughput event streams.
  10. Use RPC for immediate responses and messaging for decoupled, asynchronous workflows.

Chapter 13: Caching

What is a Cache?

A cache stores frequently accessed data in a faster storage layer to reduce latency and backend load.

Instead of repeatedly fetching data from a slow database, applications first check the cache.

Interview takeaway

The fastest request is the one that never reaches the database.

Why Cache?

Without a cache

Client
   │
   ▼
Application
   │
   ▼
Database (10 ms)

Every request hits the database.

With a cache

Client
   │
   ▼
Application
   │
   ▼
Cache (1 ms)
   │
   ▼
Database (only on cache miss)

Benefits

  • Lower latency
  • Higher throughput
  • Reduced database load
  • Lower infrastructure cost

Cache Hierarchy

CPU Cache
      │
Memory Cache
      │
CDN / Edge Cache
      │
Application Cache (Redis/Memcached)
      │
Database

The closer data is to the user, the faster it is to access.

Cache Hit vs Cache Miss

Cache Hit

Application

↓

Cache ✓

↓

Return value

No database access.

Cache Miss

Application

↓

Cache ✗

↓

Database

↓

Update Cache

↓

Return value

Cache-Aside (Lazy Loading)

Most common pattern.

Read Request

↓

Cache?

↓

Hit → Return

↓

Miss

↓

Database

↓

Populate Cache

Pros

  • Simple
  • Only caches frequently accessed data

Cons

  • First request is slower
  • Possible stale data

Examples

  • Redis
  • Memcached
  • Most web applications

Write-Through Cache

Every write updates both the cache and the database.

Write

↓

Cache

↓

Database

Pros

  • Cache always up to date
  • Simple reads

Cons

  • Slower writes
  • Unused data may be cached

Write-Back (Write-Behind)

Write to the cache first.

Persist to the database later.

Write

↓

Cache

↓

Return

↓

Database (later)

Pros

  • Very fast writes
  • High throughput

Cons

  • Data loss if the cache fails before persistence
  • More complex

Examples

  • Some storage engines
  • High-performance buffering systems

Write-Around

Writes bypass the cache.

Write

↓

Database

Cache is updated only when the data is read later.

Good for

  • Data that’s rarely read
  • Large write-heavy workloads

Cache Eviction Policies

Caches have limited memory.

Eventually, entries must be removed.

LRU (Least Recently Used)

Evict the least recently accessed item.

Most common.

LFU (Least Frequently Used)

Evict the least frequently accessed item.

Useful when frequently used items should stay cached.

FIFO

Evict the oldest entry.

Simple but rarely optimal.

Time-to-Live (TTL)

Cached entries expire automatically.

Cache

↓

TTL = 10 minutes

↓

Expire

Benefits

  • Limits stale data
  • Simple invalidation

Tradeoff

Choosing the right TTL.

Too short

  • More database traffic

Too long

  • Stale data

Cache Invalidation

One of the hardest problems in distributed systems.

Example

Price changes

↓

Database updated

↓

Cache still has old value

Users see stale data.

Common strategies

  • TTL
  • Explicit invalidation
  • Event-driven invalidation
  • Versioned keys

Interview takeaway

Caching is easy. Keeping the cache correct is hard.

Cache Stampede

Suppose a popular key expires.

10,000 Requests

↓

Cache Miss

↓

Database

Every request hits the database simultaneously.

Possible outcome

Database overload.

Solutions

  • Request coalescing (single flight)
  • Early refresh
  • Randomized TTLs
  • Background refresh

Hot Keys

One cache entry receives enormous traffic.

Trending Product

↓

Millions of Reads

↓

One Redis Node

Solutions

  • Replicate cache
  • Shard cache
  • Local in-memory cache
  • CDN

Distributed Cache

Instead of every application maintaining its own cache:

App1

App2

App3

↓

Redis Cluster

Benefits

  • Shared state
  • Better cache utilization
  • Easier scaling

Tradeoffs

  • Network latency
  • Another distributed system to manage

CDN (Content Delivery Network)

Caches static content close to users.

Examples

  • Images
  • CSS
  • JavaScript
  • Videos

Benefits

  • Lower latency
  • Reduced origin traffic
  • Better global performance

Examples

  • Cloudflare
  • CloudFront
  • Fastly

Common Interview Tradeoffs

Requirement Strategy
Most web apps Cache-aside
Consistent reads Write-through
Fast writes Write-back
Rarely read data Write-around
Simple invalidation TTL
Popular objects CDN

Common Interview Questions

You should be able to answer:

  • Why cache?
  • Cache hit vs cache miss?
  • Cache-aside vs write-through vs write-back?
  • Why is cache invalidation difficult?
  • What is a cache stampede?
  • What are hot keys?
  • Why use Redis instead of local memory?
  • What eviction policy would you choose?

Chapter Summary

Remember these ten ideas:

  1. Caches trade memory for lower latency and reduced backend load.
  2. Cache-aside is the most common caching strategy.
  3. Write-through prioritizes consistency, while write-back prioritizes performance.
  4. TTL is the simplest invalidation mechanism but introduces staleness tradeoffs.
  5. Cache invalidation is often harder than caching itself.
  6. Cache stampedes occur when many requests miss the same key simultaneously.
  7. Hot keys can overload individual cache nodes.
  8. Distributed caches share state across application servers.
  9. CDNs cache static content near users.
  10. A good cache improves performance without becoming a source of inconsistency.

Chapter 14: Fault Tolerance

What is Fault Tolerance?

Fault tolerance is the ability of a system to continue operating correctly despite failures.

Failures are expected, not exceptional.

Interview takeaway

Distributed systems are designed assuming machines, networks, and services will eventually fail.

Types of Failures

Machine Failure

A server crashes or becomes unreachable.

App Server ❌

Solution

  • Replication
  • Failover
  • Health checks

Network Failure

Machines are healthy but cannot communicate.

App A  ✖️  App B

Solution

  • Timeouts
  • Retries
  • CAP tradeoffs

Slow Responses

The service is alive but much slower than expected.

Often more dangerous than a complete failure.

Solution

  • Timeouts
  • Circuit breakers

Dependency Failure

A downstream service fails.

API

↓

Payment Service ❌

Without protection:

Everything waits.

Timeouts

Never wait forever.

Request

↓

Wait 2 s

↓

Timeout

Benefits

  • Detect slow dependencies
  • Prevent thread exhaustion
  • Improve responsiveness

Interview rule

Every network call should have a timeout.

Retries

Many failures are temporary.

Request

↓

Fail

↓

Retry

↓

Success

Good for

  • Network glitches
  • Temporary overload
  • Leader election

Bad for

  • Invalid requests
  • Permanent errors

Exponential Backoff

Avoid retrying immediately.

Instead:

1 s

↓

2 s

↓

4 s

↓

8 s

Often combined with random jitter to prevent many clients from retrying simultaneously.

Circuit Breaker

Suppose a dependency is failing.

Without protection

Thousands of requests

↓

Fail

↓

More requests

↓

More failures

The failing service becomes overwhelmed.

Circuit breaker

Failure threshold reached

↓

Circuit opens

↓

Requests fail immediately

↓

Recovery check

↓

Circuit closes

Benefits

  • Prevents cascading failures
  • Gives dependencies time to recover
  • Improves overall stability

Bulkhead Pattern

Don’t let one failing component consume all resources.

Example

Pool A

Payment

Pool B

Search

If Payment becomes overloaded:

Search continues operating.

Think of ship bulkheads.

One flooded compartment doesn’t sink the entire ship.

Graceful Degradation

Instead of failing completely:

Disable non-essential features.

Example

Search works.

Recommendations are temporarily unavailable.

Users still receive value.

Load Shedding

When overloaded:

Reject low-priority requests.

Capacity

1000 requests/sec

Incoming

1500 requests/sec

↓

Reject 500

Better to reject some traffic than fail everyone.

Rate Limiting

Prevent clients from overwhelming the system.

Common algorithms

Token Bucket

Tokens accumulate over time.

Requests consume tokens.

Allows short bursts.

Leaky Bucket

Requests leave at a fixed rate.

Smooths traffic.

Fixed Window

Example

100 requests/minute.

Simple.

May allow bursts at window boundaries.

Sliding Window

Tracks requests continuously.

More accurate than fixed windows.

Health Checks

Services periodically verify dependencies.

Healthy

GET /health

200 OK

Unhealthy

500

Timeout

Load balancers remove unhealthy instances automatically.

Redundancy

Never rely on a single machine.

Primary

↓

Replica

Use redundancy for:

  • Servers
  • Databases
  • Load balancers
  • Regions

Disaster Recovery

Protect against regional failures.

Strategies

  • Multi-region deployment
  • Backups
  • Cross-region replication
  • Automated failover

Measure using:

RPO (Recovery Point Objective)

Maximum acceptable data loss.

RTO (Recovery Time Objective)

Maximum acceptable downtime.

Common Interview Tradeoffs

Goal Technique
Recover from transient failures Retries
Avoid hanging forever Timeouts
Prevent retry storms Exponential backoff + jitter
Prevent cascading failures Circuit breaker
Isolate failures Bulkheads
Protect the system Rate limiting
Handle overload Load shedding
Survive disasters Multi-region replication

Common Interview Questions

You should be able to answer:

  • What types of failures occur in distributed systems?
  • Why should every RPC have a timeout?
  • When should you retry?
  • Why use exponential backoff?
  • What problem does a circuit breaker solve?
  • What is graceful degradation?
  • Bulkheads vs circuit breakers?
  • What are RPO and RTO?

Chapter Summary

Remember these ten ideas:

  1. Failures are expected in distributed systems.
  2. Timeouts prevent resources from waiting indefinitely.
  3. Retries recover from transient failures but must be used carefully.
  4. Exponential backoff with jitter prevents retry storms.
  5. Circuit breakers stop cascading failures.
  6. Bulkheads isolate failures so one component doesn’t impact others.
  7. Graceful degradation preserves core functionality during outages.
  8. Load shedding protects the system under extreme load.
  9. Health checks enable automatic failover.
  10. Disaster recovery planning balances downtime (RTO) and data loss (RPO).

Chapter 15: Coordination

What is Coordination?

Coordination is the process of keeping multiple machines in agreement about shared system state.

Unlike consensus, which solves the agreement problem, coordination services provide practical building blocks for applications to use that agreement.

Interview takeaway

Application data lives in databases.

Cluster metadata lives in coordination systems.

Why Do We Need Coordination?

Imagine a cluster of application servers.

App 1

App 2

App 3

Questions arise:

  • Who is the leader?
  • Which nodes are healthy?
  • Where is each service running?
  • What configuration should everyone use?
  • Who owns this distributed lock?

A coordination service answers these questions.

What Does a Coordination Service Store?

Examples include:

  • Leader information
  • Cluster membership
  • Configuration
  • Distributed locks
  • Service discovery metadata

Not:

  • User profiles
  • Orders
  • Images
  • Chat messages

Interview rule

Never store large application data in ZooKeeper or etcd.

Leader Election

Suppose three servers exist.

A

B

C

One must become leader.

Leader

↓

Followers

If the leader crashes:

A new leader is elected.

Coordination services make this automatic.

Examples

  • Kubernetes controller
  • Kafka controller
  • Database primaries

Distributed Locks

Suppose two workers process the same job.

Worker A

Worker B

↓

Same file

Without coordination:

Both process it.

With a distributed lock:

Acquire Lock

↓

Worker A ✓

Worker B waits

Only one worker proceeds.

Use cases

  • Cron jobs
  • Schema migrations
  • Inventory updates
  • Scheduled tasks

Service Discovery

In cloud environments, servers are constantly added and removed.

Instead of hardcoding IP addresses:

Payment Service

↓

Coordination Service

↓

10.1.2.5

Applications ask:

“Where is the payment service?”

The coordination service provides the current location.

Examples

  • Kubernetes Services
  • Consul
  • etcd

Cluster Membership

Machines join and leave.

The system needs to know:

Cluster

A

B

C

↓

B crashes

↓

Cluster

A

C

Coordination services maintain the authoritative list of active nodes.

Configuration Management

Instead of every server reading local files:

Config Service

↓

Feature Flags

↓

Database URLs

↓

Timeouts

Every application reads configuration from one central location.

Benefits

  • Consistent configuration
  • Dynamic updates
  • Easier operations

Watchers (Notifications)

Applications can subscribe to changes.

Example

Leader changes

↓

Coordination Service

↓

Notify Applications

No polling required.

Common uses

  • Leader changes
  • Config updates
  • Node joins/leaves

ZooKeeper

One of the earliest coordination systems.

Provides

  • Leader election
  • Configuration
  • Distributed locks
  • Membership

Uses the ZAB consensus protocol.

Historically used by:

  • Kafka
  • Hadoop
  • HBase

etcd

Modern coordination system based on Raft.

Provides

  • Strong consistency
  • Key-value storage
  • Watches
  • Leader election

Most famous use

Kubernetes stores its cluster state in etcd.

Consul

Focuses on service discovery and configuration.

Provides

  • Service registry
  • Health checks
  • Configuration
  • Distributed key-value store

Popular in microservice architectures.

Comparing Coordination Systems

System Best Known For
ZooKeeper Distributed coordination
etcd Kubernetes metadata
Consul Service discovery

Coordination vs Consensus

Common interview question.

Consensus

Agreement algorithm.

Examples

  • Raft
  • Paxos

Coordination

Applications built on top of consensus.

Examples

  • etcd
  • ZooKeeper
  • Consul

Interview shortcut

Consensus is the engine.

Coordination is the product built using it.

Coordination vs Databases

Database Coordination Service
Stores user data Stores cluster metadata
Optimized for throughput Optimized for consistency
Large datasets Small datasets
User queries Infrastructure state

Common Interview Tradeoffs

Requirement Solution
Elect one leader Coordination service
One worker at a time Distributed lock
Find running services Service discovery
Cluster configuration Central configuration store
Detect failures Membership + health checks

Common Interview Questions

You should be able to answer:

  • Why do distributed systems need coordination?
  • What should be stored in ZooKeeper or etcd?
  • How does leader election work?
  • What are distributed locks?
  • What is service discovery?
  • ZooKeeper vs etcd?
  • Coordination vs consensus?
  • Why doesn’t Kubernetes store its metadata in MySQL?

Chapter Summary

Remember these ten ideas:

  1. Coordination services manage cluster metadata, not application data.
  2. They provide leader election, locks, service discovery, configuration, and membership.
  3. Distributed locks ensure only one node performs a critical operation.
  4. Service discovery lets applications find each other dynamically.
  5. Membership tracking identifies healthy nodes.
  6. Watchers notify clients when important state changes.
  7. ZooKeeper, etcd, and Consul are the most common coordination systems.
  8. etcd uses Raft to provide strong consistency.
  9. Coordination services prioritize correctness over throughput.
  10. Consensus enables coordination, while coordination exposes useful infrastructure primitives.

Chapter 16: Storage Systems

Why Are There So Many Databases?

No single database is best for every workload.

Some optimize for:

  • Strong consistency
  • Low latency
  • Massive scale
  • Flexible schemas
  • Analytics
  • Graph traversal

Interview takeaway

Choose the database that matches the access pattern, not the one with the most features.

SQL vs NoSQL

SQL (Relational)

Stores data in structured tables.

```text id=”0llvqk” Customers

Orders

Products


Characteristics

* Fixed schema
* ACID transactions
* Rich joins
* Strong consistency
* SQL queries

Good for

* Banking
* Payments
* Inventory
* ERP
* CRM

Examples

* PostgreSQL
* MySQL
* SQL Server
* Spanner

---

## NoSQL

Designed for horizontal scalability and flexible data models.

Characteristics

* Flexible schema
* Horizontal scaling
* High availability
* Often eventual consistency

Interview tip

NoSQL doesn't mean "No SQL."

It means "Not only SQL."

---

# Types of NoSQL Databases

## 1. Key-Value Stores

Data model

```text id="e9b0mc"
Key

↓

Value

Examples

```text id=”z3ocqg” User123

↓

JSON


Advantages

* Extremely fast
* Simple
* Highly scalable

Disadvantages

* Limited queries
* No joins

Examples

* Redis
* DynamoDB
* Riak

Best for

* Sessions
* Shopping carts
* User profiles
* Feature flags

---

## 2. Document Databases

Store structured documents.

```text id="v0h0ta"
Customer

{

name,

orders,

address

}

Advantages

  • Flexible schema
  • Rich queries
  • Natural JSON model

Disadvantages

  • Limited joins
  • Document growth

Examples

  • MongoDB
  • Couchbase

Best for

  • User profiles
  • CMS
  • Product catalogs

3. Wide-Column Databases

Store rows with dynamic columns.

Optimized for:

  • Massive scale
  • Large write throughput

Examples

  • Cassandra
  • Bigtable
  • HBase

Good for

  • IoT
  • Logs
  • Time-series
  • Telemetry

4. Graph Databases

Store relationships directly.

```text id=”gqq1my” Alice

↓

Friend

↓

Bob


Advantages

* Efficient relationship traversal

Examples

* Neo4j
* Amazon Neptune

Good for

* Fraud detection
* Social networks
* Recommendation graphs
* Knowledge graphs

---

# Comparing Data Models

| Model       | Best For      | Weakness                  |
| ----------- | ------------- | ------------------------- |
| Relational  | Transactions  | Harder to scale writes    |
| Key-Value   | Fast lookups  | Limited queries           |
| Document    | Flexible data | Large joins               |
| Wide-Column | Massive scale | Complex querying          |
| Graph       | Relationships | General-purpose workloads |

---

# Google Spanner

Global relational database.

Key ideas

* SQL
* Horizontal scaling
* Strong consistency
* TrueTime
* Synchronous replication

Good for

* Financial systems
* Enterprise applications
* Global transactions

Interview takeaway

Spanner combines SQL with global consistency.

---

# Bigtable

Google's wide-column database.

Optimized for

* Huge datasets
* High write throughput
* Sequential access

Used by

* Search indexing
* Maps
* Analytics

Not designed for joins or transactions.

---

# Cassandra

Leaderless wide-column database.

Characteristics

* AP (CAP)
* Eventual consistency
* High availability
* Massive scalability
* Tunable consistency with quorums

Good for

* Logs
* Metrics
* Time-series
* Write-heavy workloads

---

# DynamoDB

Managed key-value database.

Characteristics

* Automatic scaling
* Low latency
* Regional replication
* Tunable consistency

Good for

* Mobile apps
* Gaming
* User profiles
* Serverless applications

---

# Redis

In-memory key-value store.

Characteristics

* Extremely fast
* Optional persistence
* Rich data structures
* Often used as a cache

Good for

* Sessions
* Leaderboards
* Rate limiting
* Distributed locks
* Caching

---

# MongoDB

Document database.

Characteristics

* JSON documents
* Flexible schema
* Secondary indexes
* Rich queries

Good for

* Content management
* User profiles
* Catalogs

---

# Choosing a Database

| Requirement          | Good Choice          |
| -------------------- | -------------------- |
| Strong transactions  | PostgreSQL / Spanner |
| Global SQL           | Spanner              |
| Caching              | Redis                |
| Flexible JSON        | MongoDB              |
| Massive writes       | Cassandra            |
| Time-series          | Cassandra / Bigtable |
| Fast key lookup      | DynamoDB             |
| Relationship queries | Neo4j                |

---

# OLTP vs OLAP

## OLTP (Online Transaction Processing)

Characteristics

* Small transactions
* Frequent writes
* Low latency

Examples

* Banking
* E-commerce
* Reservations

---

## OLAP (Online Analytical Processing)

Characteristics

* Large scans
* Aggregations
* Reporting

Examples

* Dashboards
* Business intelligence
* Data warehouses

Interview tip

Don't run analytics on your production OLTP database.

---

# Common Interview Tradeoffs

| Requirement            | Database       |
| ---------------------- | -------------- |
| ACID                   | SQL            |
| Horizontal writes      | Cassandra      |
| Flexible schema        | MongoDB        |
| Fast cache             | Redis          |
| Global consistency     | Spanner        |
| Relationship traversal | Graph database |

---

# Common Interview Questions

You should be able to answer:

* SQL vs NoSQL?
* Why use MongoDB instead of PostgreSQL?
* Redis vs DynamoDB?
* Cassandra vs Bigtable?
* What makes Spanner unique?
* When would you choose a graph database?
* OLTP vs OLAP?
* Why are joins difficult in distributed systems?

---

# Chapter Summary

Remember these ten ideas:

1. No database is optimal for every workload.
2. SQL databases prioritize consistency and transactions.
3. NoSQL databases prioritize scalability and flexibility.
4. Key-value stores optimize simple lookups.
5. Document databases optimize flexible JSON data.
6. Wide-column databases optimize massive write throughput.
7. Graph databases optimize relationship traversal.
8. Redis is primarily an in-memory cache and key-value store.
9. Spanner provides globally consistent SQL.
10. Database choice should be driven by workload and access patterns.

---

## How this connects

```text
We now know:

✓ Distributed storage
✓ Replication
✓ Consistency
✓ Database choices

Next question:

How do we know whether our distributed system is actually healthy?

↓

Observability

Chapter 17: Observability

What is Observability?

Observability is the ability to understand the internal state of a system by examining its outputs.

Those outputs are primarily:

  • Metrics
  • Logs
  • Traces

Interview takeaway

Monitoring tells you that something is wrong.

Observability helps you understand why.

The Three Pillars

            Observability
          /       |       \
      Metrics    Logs    Traces

Each answers a different question.

Metrics

Numerical measurements collected over time.

Examples

  • CPU utilization
  • Memory usage
  • Requests/second
  • Error rate
  • Latency
  • Queue depth
  • Cache hit rate

Example

Latency

200 ms

↓

350 ms

↓

1200 ms

You immediately know performance degraded.

Advantages

  • Lightweight
  • Easy to graph
  • Great for dashboards and alerts

Limitations

Metrics tell you that something happened, not why.

Logs

Detailed records of individual events.

Example

10:01:02

User 123

Payment failed

Timeout

Good for

  • Debugging
  • Error investigation
  • Auditing

Advantages

  • Rich detail
  • Easy root cause analysis

Disadvantages

  • Huge storage requirements
  • Difficult to aggregate

Distributed Tracing

Follows one request as it moves across services.

Example

Client

↓

API

↓

Payment

↓

Inventory

↓

Shipping

Instead of isolated logs, you see the entire request path.

Example trace

Request 8A92

API

45 ms

↓

Payment

210 ms

↓

Inventory

18 ms

↓

Shipping

30 ms

Immediately obvious:

Payment is the bottleneck.

Interview takeaway

Tracing explains where latency comes from.

The Four Golden Signals

Google SRE popularized four key metrics.

Latency

How long requests take.

Traffic

How much work the system performs.

Examples

  • Requests/sec
  • Queries/sec
  • Messages/sec

Errors

How many requests fail.

Examples

  • HTTP 500
  • Timeouts
  • Exceptions

Saturation

How close the system is to capacity.

Examples

  • CPU
  • Memory
  • Queue length
  • Thread pool utilization

Interview tip

If asked which metrics to monitor first, start with these four.

SLIs, SLOs, and SLAs

SLI (Service Level Indicator)

A measured metric.

Example

99.95% successful requests.

SLO (Service Level Objective)

The target.

Example

99.9% availability.

SLA (Service Level Agreement)

A contractual guarantee.

Example

99.9% uptime or receive service credits.

Interview shortcut

SLI = Measurement

SLO = Goal

SLA = Contract

Dashboards

Dashboards should answer:

  • Is the service healthy?
  • Is it getting worse?
  • Which dependency is failing?
  • Is traffic normal?

Avoid dashboards with hundreds of charts.

Focus on actionable metrics.

Alerting

Good alerts:

  • Wake you only when action is required.
  • Detect user-impacting problems.
  • Minimize false positives.

Poor alerts:

  • CPU briefly spikes to 85%.
  • One request fails.

Good example

5xx error rate > 5%

for 10 minutes

Root Cause Analysis

Suppose users report:

Search is slow.

Investigation

Latency ↑

↓

Trace

↓

Database latency ↑

↓

CPU normal

↓

Queue depth ↑

↓

Slow query found

Observability lets you narrow the problem quickly.

Common Metrics by Component

Component Important Metrics
API Latency, QPS, error rate
Database Query latency, connections, slow queries
Cache Hit ratio, memory usage, evictions
Queue Queue depth, consumer lag, retries
Load Balancer Throughput, error rate, healthy instances
Kafka Consumer lag, partition imbalance
Redis Hit rate, memory, evictions

Logging Best Practices

Use structured logs.

Instead of

Payment failed

Prefer

{
  "request_id": "abc123",
  "user_id": 42,
  "service": "payment",
  "status": "timeout"
}

Benefits

  • Searchable
  • Machine-readable
  • Easy correlation across services

Correlation IDs

A request should carry the same ID through every service.

Request ID

↓

API

↓

Payment

↓

Inventory

↓

Shipping

Makes tracing and debugging much easier.

Common Interview Tradeoffs

Requirement Technique
System health Metrics
Root cause Logs
End-to-end latency Traces
Business reliability SLOs
Cross-service debugging Correlation IDs

Common Interview Questions

You should be able to answer:

  • Metrics vs logs vs traces?
  • What are the four golden signals?
  • SLI vs SLO vs SLA?
  • What makes a good alert?
  • Why are correlation IDs important?
  • How do you debug latency across microservices?
  • Which metrics would you monitor for Redis, Kafka, or a database?

Chapter Summary

Remember these ten ideas:

  1. Observability helps explain why systems behave the way they do.
  2. Metrics measure trends, logs explain events, and traces follow requests.
  3. The four golden signals are latency, traffic, errors, and saturation.
  4. SLIs measure performance, SLOs define targets, and SLAs are contractual guarantees.
  5. Good dashboards highlight user-impacting issues.
  6. Alerts should be actionable and minimize noise.
  7. Distributed tracing identifies bottlenecks across services.
  8. Structured logs are easier to search and analyze than free-form text.
  9. Correlation IDs tie together logs and traces from multiple services.
  10. Strong observability dramatically reduces time to detect and resolve incidents.

Chapter 18: Distributed Systems Interview Playbook

The Mental Model

Every distributed system design can be broken into the same sequence of questions.

Don’t jump to Kafka, Redis, or Cassandra.

Instead, reason from first principles.

1. What Are We Optimizing?

Every system has different priorities.

Ask:

  • Read-heavy or write-heavy?
  • Latency or throughput?
  • Availability or consistency?
  • Cost or performance?
  • Global or regional?

These decisions drive everything else.

2. How Does the System Scale?

First scale compute.

Client

↓

Load Balancer

↓

Stateless App Servers

Then ask:

Does storage also need to scale?

If yes:

Partition the data.

3. How Is Data Partitioned?

Choose a partition key.

Examples

User ID

Tenant ID

Region

Conversation ID

Avoid

  • Hot partitions
  • Frequent repartitioning
  • Cross-shard queries

4. How Is Data Replicated?

Ask

Why are we replicating?

Read scaling?

Availability?

Durability?

Then choose

Leader-Follower

Leaderless

Multi-Leader

5. What Consistency Does the Business Need?

Not every workload needs strong consistency.

Requirement Consistency
Payments Strong
Inventory Strong
Chat Causal
Social Feed Eventual
Analytics Eventual

Business requirements determine the consistency model.

6. What Happens When Things Fail?

Always assume failures.

Consider

  • Machine failure
  • Network failure
  • Regional outage
  • Dependency failure

Mitigations

  • Retries
  • Timeouts
  • Circuit breakers
  • Failover

7. Where Should We Cache?

Ask

Can this request avoid the database?

Possible cache layers

Browser

CDN

Redis

Application

Database

8. Is Asynchronous Processing Better?

Don’t make users wait.

Instead

Request

↓

Queue

↓

Background Worker

Good candidates

  • Email
  • Notifications
  • Video processing
  • Analytics

9. How Will We Observe the System?

Monitor

Latency

Traffic

Errors

Saturation

Add

  • Logs
  • Traces
  • Alerts

10. What Tradeoffs Are We Making?

Every design is a compromise.

Ask yourself

Am I trading

Consistency

for

Availability?

Latency

for

Durability?

Memory

for

Speed?

Simplicity

for

Scalability?

Interview takeaway

Explicitly stating your tradeoffs often matters more than picking the “perfect” technology.

The Decision Matrix

Need… Consider…
More compute Horizontal scaling
More read throughput Read replicas
More write throughput Partitioning
Faster responses Caching
Loose coupling Messaging
High availability Replication
Strong consistency Consensus
Dynamic service locations Service discovery
Reliable retries Idempotency
Fault isolation Circuit breakers
Cluster metadata etcd / ZooKeeper
Global SQL Spanner
Massive writes Cassandra
Flexible documents MongoDB
Fast key-value access Redis / DynamoDB

The Golden Rules

  1. Networks are unreliable.
  2. Machines fail.
  3. Clocks cannot be trusted.
  4. Data grows.
  5. Traffic is uneven.
  6. Everything eventually becomes distributed.
  7. Every guarantee costs something.
  8. Simplicity scales surprisingly well.
  9. Design for failures, not the happy path.
  10. State your tradeoffs clearly.

The One-Page Interview Cheat Sheet

If you only remember one page, remember this.

Question Think About
Scale? Horizontal scaling
Reads? Replicas
Writes? Partitioning
Latency? Caching
Availability? Replication
Ordering? Consensus
Failures? Retries + Circuit Breakers
Async work? Queues
Monitoring? Metrics + Logs + Traces
Metadata? Coordination

The Complete Mental Model

                Users
                  │
                  ▼
          Load Balancer
                  │
                  ▼
        Stateless App Servers
          │              │
          ▼              ▼
      Cache          Message Queue
          │              │
          ▼              ▼
     Distributed Database
          │
    ┌─────┴─────┐
    ▼           ▼
Partitioning  Replication
    │           │
    └─────┬─────┘
          ▼
     Consistency
          │
          ▼
      Quorums
          │
          ▼
      Consensus
          │
          ▼
     Coordination
          │
          ▼
 Observability & Recovery

Everything in distributed systems builds on this stack.

Final Takeaways

Remember these ten ideas:

  1. Scale compute before storage.
  2. Partition to scale writes.
  3. Replicate to improve availability and read throughput.
  4. Choose the weakest consistency model that satisfies the business need.
  5. Use messaging to decouple services.
  6. Cache aggressively, but plan for invalidation.
  7. Design assuming failures are inevitable.
  8. Observe everything with metrics, logs, and traces.
  9. Every design is a set of tradeoffs.
  10. Always explain why you made those tradeoffs.

What I’d Add Before Publishing

I think this guide is now structurally complete, but I’d add three appendices that would make it significantly more valuable:

Appendix A: Complexity Cheat Sheet (2-3 pages)

A quick reference for common algorithms and concepts:

  • Consistent hashing
  • Raft election
  • Quorum formulas
  • Cache patterns
  • Retry strategies
  • Rate limiting algorithms
  • Partitioning methods

Appendix B: Architecture Patterns (4-5 pages)

Common interview building blocks:

  • URL Shortener
  • News Feed
  • Chat
  • Payment System
  • Search
  • Notification Service
  • Rate Limiter

Each pattern would be one page showing which distributed systems concepts are typically used.

Appendix C: Company-Specific Technologies (4-5 pages)

Company Technologies
Google Spanner, Bigtable, Borg, Colossus
Amazon DynamoDB, S3, SQS, SNS
Meta TAO, Memcache, ZippyDB
Netflix EVCache, Cassandra, Kafka
Uber Schemaless, Ringpop, Cadence
OpenAI (Generic patterns: Redis, Kafka, Kubernetes, object storage, vector databases, inference infrastructure)

I actually think there’s one thing missing that would make this feel complete:

A visual “map” of distributed systems.

Most people learn these topics individually, but they don’t understand how they relate. I’d end with a 2 to 3 page “Distributed Systems at a Glance.”

Appendix A: Distributed Systems at a Glance

The Big Picture

                  USERS
                    │
                    ▼
             Load Balancer
                    │
      ┌─────────────┴─────────────┐
      ▼                           ▼
 Stateless App Servers      Stateless App Servers
      │                           │
      ├─────────────┬─────────────┤
      ▼             ▼             ▼
    Cache      Message Queue   Object Storage
      │             │
      ▼             ▼
      └──────► Distributed Database ◄──────┐
                     │                      │
             ┌───────┴────────┐             │
             ▼                ▼             │
        Partitioning     Replication        │
             │                │             │
             └────────┬───────┘             │
                      ▼                     │
                 Consistency                │
                      │                     │
                      ▼                     │
                  CAP Theorem              │
                      │                     │
                      ▼                     │
                   Quorums                 │
                      │                     │
                      ▼                     │
                  Consensus                │
                      │                     │
                      ▼                     │
                 Coordination              │
                      │                     │
                      ▼                     │
      Metrics • Logs • Traces • Alerting ◄─┘

Everything you’ve learned fits somewhere on this diagram.

The Story of a Request

One request touches nearly every concept.

User

↓

DNS

↓

Load Balancer

↓

Application Server

↓

Cache?

↓

Hit

↓

Return


Miss

↓

Database

↓

Partition

↓

Leader Replica

↓

Followers

↓

Consensus

↓

Response

↓

Metrics

↓

Logs

↓

Trace

That’s essentially an entire distributed system in one flow.

Concept Dependency Graph

One of the biggest problems with books is they teach concepts out of order.

This is how they actually depend on each other.

Distributed Systems

↓

Scalability

↓

Load Balancing

↓

Partitioning

↓

Replication

↓

Consistency

↓

CAP

↓

Quorums

↓

Consensus

↓

Coordination

↓

Transactions

↓

Messaging

↓

Caching

↓

Fault Tolerance

↓

Storage

↓

Observability

Notice how each chapter naturally builds on the previous one.

Which Problem Does Each Concept Solve?

Problem Solution
One server overloaded Horizontal scaling
One server receives too much traffic Load balancing
Database too large Partitioning
Database failure Replication
Stale reads Consistency
Network partition CAP tradeoff
Replica disagreement Quorums
Multiple leaders Consensus
Shared cluster state Coordination
Cross-service updates Distributed transactions
Slow synchronous calls Messaging
High latency Caching
Service failures Fault tolerance
Choosing a database Storage systems
Debugging production Observability

This table alone answers about half the questions interviewers ask.

Tradeoff Matrix

Every distributed systems decision is a tradeoff.

Want More… Usually Means Less…
Consistency Availability
Availability Strong consistency
Durability Write latency
Read performance Write simplicity
Throughput Coordination
Simplicity Flexibility
Flexibility Predictability
Low latency Strong guarantees

One of the biggest signs of seniority is recognizing and explaining these tradeoffs.

Interview Flow

Every system design interview tends to follow the same path.

Requirements

↓

Traffic Estimation

↓

High-Level Design

↓

Scale Compute

↓

Scale Storage

↓

Partition

↓

Replicate

↓

Cache

↓

Async Processing

↓

Failure Handling

↓

Observability

If you follow this sequence, you’ll rarely miss a major design component.

The One-Page Review

If you have five minutes before an interview, review this.

Question First Thing to Consider
How do I scale compute? Stateless services + load balancer
How do I scale storage? Partitioning
How do I improve availability? Replication
How do I improve read performance? Replicas + caching
How do I improve write throughput? Partitioning
How do I keep replicas synchronized? Consistency + quorums
How do I elect a leader? Consensus
How do services communicate? RPC + messaging
How do I survive failures? Retries + circuit breakers
How do I debug production? Metrics + logs + traces