Designing Distributed Systems

Designing Distributed Systems

Design scalable, reliable, and fault-tolerant distributed systems using proven patterns and consistency models.

Purpose

Distributed systems are the foundation of modern cloud-native applications. Understanding fundamental trade-offs (CAP theorem, PACELC), consistency models, replication patterns, and resilience strategies is essential for building systems that scale globally while maintaining correctness and availability.

When to Use This Skill

Apply when:

• Designing microservices architectures with multiple services
• Building systems that must scale across multiple datacenters or regions
• Choosing between consistency vs availability during network partitions
• Selecting replication strategies (single-leader, multi-leader, leaderless)
• Implementing distributed transactions (saga pattern, event sourcing, CQRS)
• Designing partition-tolerant systems with proper consistency guarantees
• Building resilient services with circuit breakers, bulkheads, retries
• Implementing service discovery and inter-service communication

Core Concepts

CAP Theorem Fundamentals

CAP Theorem: In a distributed system experiencing a network partition, choose between Consistency (C) or Availability (A). Partition tolerance (P) is mandatory.

Network partitions WILL occur → Always design for P

During partition:
├─ CP (Consistency + Partition Tolerance)
│  Use when: Financial transactions, inventory, seat booking
│  Trade-off: System unavailable during partition
│  Examples: HBase, MongoDB (default), etcd
│
└─ AP (Availability + Partition Tolerance)
   Use when: Social media, caching, analytics, shopping carts
   Trade-off: Stale reads possible, conflicts need resolution
   Examples: Cassandra, DynamoDB, Riak

PACELC: Extends CAP to consider normal operations (no partition).

• If Partition: Choose Availability (A) or Consistency (C)
• Else (normal): Choose Latency (L) or Consistency (C)

Consistency Models Spectrum

Strong Consistency ◄─────────────────────► Eventual Consistency
      │                    │                      │
  Linearizable      Causal Consistency     Convergent
  (Slowest,         (Middle Ground,        (Fastest,
   Most Consistent)  Causally Ordered)     Eventually Consistent)

Strong Consistency (Linearizability):

• All operations appear atomically in sequential order
• Reads always return most recent write
• Use for: Bank balances, inventory stock, seat booking
• Trade-off: Higher latency, reduced availability

Eventual Consistency:

• If no new updates, all replicas eventually converge
• Use for: Social feeds, product catalogs, user profiles, DNS
• Trade-off: Stale reads possible, conflict resolution needed

Causal Consistency:

• Causally related operations seen in same order by all nodes
• Use for: Chat apps, collaborative editing, comment threads
• Trade-off: More complex than eventual, requires causality tracking

Bounded Staleness:

• Staleness bounded by time or version count
• Use for: Real-time dashboards, leaderboards, monitoring
• Trade-off: Must monitor lag, more complex than eventual

Replication Patterns

1. Leader-Follower (Single-Leader):

• All writes to leader, replicated to followers
• Followers handle reads (load distribution)
• Synchronous: Wait for follower ACK (strong consistency, higher latency)
• Asynchronous: Don't wait (eventual consistency, possible data loss)
• Use for: Most common pattern, strong consistency with sync replication

2. Multi-Leader:

• Multiple leaders accept writes in different datacenters
• Leaders replicate to each other
• Conflict resolution required: Last-Write-Wins, application merge, vector clocks
• Use for: Multi-datacenter, low write latency, geo-distributed users
• Trade-off: Conflict resolution complexity

3. Leaderless (Dynamo-style):

• No single leader, quorum-based reads/writes
• Quorum rule: W + R > N (W=write quorum, R=read quorum, N=replicas)
• Example: N=5, W=3, R=2 → Strong consistency (overlap guaranteed)
• Use for: Maximum availability, partition tolerance
• Trade-off: Complexity, read repair needed

Partitioning Strategies

Hash Partitioning (Consistent Hashing):

• Key → Hash(Key) → Partition assignment
• Even distribution, minimal rebalancing when nodes added/removed
• Use for: Point queries by ID, even distribution critical
• Examples: Cassandra, DynamoDB, Redis Cluster

Range Partitioning:

• Key ranges assigned to partitions (A-F, G-M, N-S, T-Z)
• Enables range queries, ordered data
• Risk: Hot spots if data skewed
• Use for: Time-series data, leaderboards, range scans
• Examples: HBase, Bigtable

Geographic Partitioning:

• Partition by location (US-East, EU-West, APAC)
• Use for: Data locality, GDPR compliance, low latency
• Examples: Spanner, Cosmos DB

Resilience Patterns

Circuit Breaker:

[Closed] → Normal operation
   │ (failures exceed threshold)
   ▼
[Open] → Fail fast (don't call failing service)
   │ (timeout expires)
   ▼
[Half-Open] → Try single request
   │ success → [Closed]
   │ failure → [Open]

• Prevents cascading failures
• Fast-fail instead of waiting for timeout
• See references/resilience-patterns.md

Bulkhead Isolation:

• Isolate resources (thread pools, connection pools)
• Failure in one partition doesn't affect others
• Like ship compartments preventing total flooding

Timeout and Retry:

• Timeout: Set deadlines, fail fast if exceeded
• Retry: Exponential backoff with jitter
• Idempotency: Ensure safe retry (critical)

Rate Limiting and Backpressure:

• Protect services from overload
• Token bucket, leaky bucket algorithms
• Backpressure: Signal upstream to slow down

Transaction Patterns

Saga Pattern:

• Coordinate distributed transactions across services
• No distributed 2PC (two-phase commit)

Choreography: Services react to events

Order Service → OrderCreated event
Payment Service → listens → PaymentProcessed event
Inventory Service → listens → InventoryReserved event
(Compensating: if payment fails → InventoryReleased event)

Orchestration: Central coordinator

Saga Orchestrator:
1. Call Order Service
2. Call Payment Service
3. Call Inventory Service
(If step fails → call compensating transactions in reverse)

Event Sourcing:

• Store state changes as immutable events
• Rebuild state by replaying events
• Audit trail, time travel, debugging
• Trade-off: Query complexity, snapshot optimization

CQRS (Command Query Responsibility Segregation):

• Separate read and write models
• Write model: Normalized, transactional
• Read model: Denormalized, cached, optimized
• Use for: Different read/write patterns, high read:write ratio (10:1+)
• Often paired with Event Sourcing

Service Discovery

Client-Side Discovery:

• Client queries service registry (Consul, etcd, Eureka)
• Client load balances and calls service directly
• Pro: No proxy overhead
• Con: Client complexity

Server-Side Discovery:

• Client calls load balancer
• Load balancer queries registry and routes
• Pro: Simple clients
• Con: Load balancer single point of failure

Service Mesh:

• Sidecar proxies handle discovery, routing, retry, circuit breaking
• Examples: Istio, Linkerd
• Pro: Decouples communication logic from services
• Con: Operational complexity

Caching Strategies

Cache-Aside (Lazy Loading):

Read:
1. Check cache → hit? return
2. Miss? Query database
3. Store in cache, return

Write-Through:

Write:
1. Write to cache
2. Cache writes to database synchronously
3. Return success

Write-Behind (Write-Back):

Write:
1. Write to cache
2. Return success
3. Cache writes to database asynchronously (batched)

Cache Invalidation:

• TTL (Time-To-Live): Expire after duration
• Event-based: Invalidate on data change
• Manual: Explicit invalidation on update

Decision Frameworks

Choosing Consistency Model

Decision Tree:
├─ Money involved? → Strong Consistency
├─ Double-booking unacceptable? → Strong Consistency
├─ Causality important (chat, edits)? → Causal Consistency
├─ Read-heavy, stale tolerable? → Eventual Consistency
└─ Default? → Eventual (then strengthen if needed)

Choosing Replication Pattern

├─ Single region writes? → Leader-Follower
├─ Multi-region writes + conflicts OK? → Multi-Leader
├─ Multi-region writes + no conflicts? → Leader-Follower with failover
└─ Maximum availability? → Leaderless (quorum)

Choosing Partitioning Strategy

├─ Need range scans? → Range Partitioning (risk: hot spots)
├─ Data residency requirements? → Geographic Partitioning
└─ Default? → Hash Partitioning (consistent hashing)

Quick Reference Tables

CAP/PACELC System Comparison

Consistency Model Use Cases

Quorum Configurations

Progressive Disclosure

Detailed References

For comprehensive coverage of specific topics, see:

• references/cap-pacelc-theorem.md - CAP and PACELC deep-dive with PACELC matrix
• references/consistency-models.md - Strong, eventual, causal, bounded staleness patterns
• references/replication-patterns.md - Leader-follower, multi-leader, leaderless replication
• references/partitioning-strategies.md - Hash, range, geographic partitioning with examples
• references/consensus-algorithms.md - Raft and Paxos overview (when consensus needed)
• references/resilience-patterns.md - Circuit breaker, bulkhead, timeout, retry, rate limiting
• references/saga-pattern.md - Choreography vs orchestration with working examples
• references/event-sourcing-cqrs.md - Event sourcing and CQRS implementation patterns
• references/service-discovery.md - Client-side, server-side, service mesh patterns
• references/caching-strategies.md - Cache-aside, write-through, write-behind, invalidation

Working Examples

Complete, runnable examples demonstrating patterns:

• examples/consistent-hashing/ - Consistent hashing implementation with virtual nodes
• examples/circuit-breaker/ - Circuit breaker pattern with state transitions
• examples/saga-orchestration/ - Saga orchestrator with compensating transactions
• examples/event-sourcing/ - Event store with replay and snapshots
• examples/cqrs/ - CQRS with separate read/write models
• examples/service-discovery/ - Consul-based service discovery and registration

ASCII Diagrams

Visual representations for complex concepts:

• diagrams/cap-theorem.txt - CAP theorem decision tree
• diagrams/replication-topologies.txt - Leader-follower, multi-leader, leaderless
• diagrams/saga-flow.txt - Saga choreography and orchestration flows
• diagrams/caching-patterns.txt - Cache-aside, write-through, write-behind

Integration with Other Skills

Related Skills:

For Kubernetes deployment: See kubernetes-operations skill for pod anti-affinity, service mesh For infrastructure: See infrastructure-as-code skill for deploying distributed systems For databases: See databases-sql and databases-nosql for replication configuration For messaging: See message-queues skill for event-driven architectures, saga orchestration For monitoring: See observability skill for distributed tracing, monitoring patterns For testing: See performance-engineering skill for load testing distributed systems For security: See security-hardening skill for mTLS, service authentication

Common Patterns

Multi-Datacenter Pattern

1. Choose replication: Multi-leader or Leaderless
2. Partition data geographically
3. Implement conflict resolution (LWW, vector clocks, app-specific)
4. Monitor replication lag
5. Add circuit breakers between datacenters

Event-Driven Saga Pattern

1. Define saga steps and compensating actions
2. Choose choreography (events) or orchestration (coordinator)
3. Implement idempotent handlers (retries safe)
4. Publish events with outbox pattern (transactional)
5. Monitor saga progress and timeouts

High-Availability Pattern

1. Use leaderless replication (N=5, W=3, R=2)
2. Partition with consistent hashing
3. Add circuit breakers for failing nodes
4. Implement read repair and anti-entropy
5. Monitor quorum health

Best Practices

Design for Failure:

• Network partitions will occur - always design for partition tolerance
• Use timeouts, retries with exponential backoff
• Implement circuit breakers to prevent cascading failures
• Test chaos engineering scenarios (partition nodes, inject latency)

Choose Consistency Carefully:

• Default to eventual consistency, strengthen only where needed
• Strong consistency has real costs (latency, availability)
• Use bounded staleness for middle ground

Idempotency is Critical:

• Design operations to be safely retryable
• Use unique request IDs for deduplication
• Essential for saga compensating transactions

Monitor and Observe:

• Distributed tracing with correlation IDs
• Monitor replication lag, quorum health
• Alert on circuit breaker state changes
• Track saga progress and failures

Partition Strategically:

• Hash partitioning for even distribution
• Range partitioning for range queries (monitor hot spots)
• Geographic partitioning for compliance, latency

Version Everything:

• Event schemas evolve - use versioning
• API versioning for service compatibility
• Database schema migrations in distributed systems

Anti-Patterns to Avoid

Distributed Monolith:

• Microservices with tight coupling
• Shared database across services
• Fix: Database per service, async communication

Two-Phase Commit (2PC) Overuse:

• Slow, blocking, reduces availability
• Fix: Use saga pattern for distributed transactions

Ignoring Network Failures:

• Assuming network is reliable
• Fix: Always add timeouts, retries, circuit breakers

Strong Consistency Everywhere:

• Unnecessary latency and complexity
• Fix: Use eventual consistency by default, strengthen where needed

No Conflict Resolution Strategy:

• Multi-leader without handling conflicts
• Fix: Choose LWW, vector clocks, or app-specific merge

Cache Stampede:

• TTL expires, all clients query database
• Fix: Probabilistic early expiration, request coalescing

Troubleshooting

Replication Lag Too High:

• Check network bandwidth between datacenters
• Monitor write throughput on leader
• Consider async replication or multi-leader

Split-Brain Scenario:

• Multiple leaders elected during partition
• Fix: Use consensus (Raft, Paxos) for leader election
• Implement fencing tokens to prevent dual writes

Hot Partitions:

• Range partitioning with skewed data
• Fix: Add hash component, manually redistribute, use composite keys

Saga Timeout/Stalled:

• Service unavailable, saga can't complete
• Fix: Implement saga timeout with automated rollback
• Dead letter queue for manual intervention

Conflict Resolution Failures:

• Multi-leader conflicts unhandled
• Fix: Implement clear resolution strategy (LWW, merge, manual)
• Monitor conflict rate, alert on spikes

Caching Strategies

Table of Contents

1. Cache-Aside (Lazy Loading) 2. Write-Through 3. Write-Behind (Write-Back) 4. Cache Invalidation 5. Best Practices

Cache-Aside (Lazy Loading)

Pattern

Read:
1. Check cache → hit? return
2. Miss? Query database
3. Store in cache, return

Write:
1. Write to database
2. Invalidate cache (optional)

Implementation

import redis
import json

class CacheAside:
    def __init__(self, cache, database):
        self.cache = cache  # Redis
        self.db = database
    
    def get(self, key):
        # Try cache first
        cached = self.cache.get(key)
        if cached:
            return json.loads(cached)
        
        # Cache miss - query database
        value = self.db.query(key)
        if value:
            self.cache.setex(key, 3600, json.dumps(value))
        return value
    
    def set(self, key, value):
        # Write to database
        self.db.write(key, value)
        # Invalidate cache
        self.cache.delete(key)

Write-Through

Pattern

Write:
1. Write to cache
2. Cache writes to database synchronously
3. Return success

Implementation

class WriteThrough:
    def __init__(self, cache, database):
        self.cache = cache
        self.db = database
    
    def set(self, key, value):
        # Write to database first
        self.db.write(key, value)
        # Then update cache
        self.cache.set(key, json.dumps(value))
    
    def get(self, key):
        # Always from cache
        cached = self.cache.get(key)
        return json.loads(cached) if cached else None

Write-Behind (Write-Back)

Pattern

Write:
1. Write to cache
2. Return success immediately
3. Cache writes to database asynchronously (batched)

Benefits: Low latency writes

Trade-off: Data loss if cache fails before DB write

Cache Invalidation

Strategies

TTL (Time-To-Live):

cache.setex(key, 3600, value)  # Expire after 1 hour

Event-Based:

# Invalidate on update
def update_user(user_id, data):
    db.update(user_id, data)
    cache.delete(f"user:{user_id}")

Manual:

# Explicit invalidation
cache.delete(key)

Best Practices

• Set appropriate TTLs
• Handle cache misses gracefully (thundering herd)
• Monitor cache hit rate
• Use consistent hashing for distributed caches

CAP and PACELC Theorem

Table of Contents

1. CAP Theorem Deep-Dive 2. PACELC Extension 3. PACELC Matrix 4. Real-World System Classification 5. Decision Framework

CAP Theorem Deep-Dive

Definition

In a distributed system experiencing a network partition, choose between:

• Consistency (C): All nodes see the same data at the same time
• Availability (A): Every request receives a response (success or failure)
• Partition Tolerance (P): System continues operating despite network failures

Critical Insight: Partition tolerance is mandatory in distributed systems. Network failures WILL occur. The choice is between C or A during partitions.

CAP Decision Tree

START: Designing distributed system
  │
  ├─► Will network partitions occur?
  │   Answer: YES (always in distributed systems)
  │
  ├─► DURING PARTITION, choose:
  │   │
  │   ├─► CP (Consistency + Partition Tolerance)
  │   │   │
  │   │   ├─ Behavior: Reject writes, return errors
  │   │   ├─ Use when: Correctness > availability
  │   │   ├─ Examples:
  │   │   │   - Banking (account balance must be correct)
  │   │   │   - Inventory (prevent overselling)
  │   │   │   - Seat booking (no double-booking)
  │   │   │   - Distributed locks
  │   │   │
  │   │   ├─ Systems: HBase, MongoDB (default), etcd, Consul
  │   │   └─ Trade-off: System unavailable during partition
  │   │
  │   └─► AP (Availability + Partition Tolerance)
  │       │
  │       ├─ Behavior: Accept writes, resolve conflicts later
  │       ├─ Use when: Availability > strict consistency
  │       ├─ Examples:
  │       │   - Social media (likes, follows, posts)
  │       │   - Shopping cart (can merge carts)
  │       │   - Product catalog (stale prices OK briefly)
  │       │   - Analytics (approximate counts acceptable)
  │       │
  │       ├─ Systems: Cassandra, DynamoDB, Riak, Couchbase
  │       └─ Trade-off: Stale reads, conflict resolution needed

CP Systems: Consistency + Partition Tolerance

Behavior During Partition:

┌─────────────────────────────────────────────────────┐
│              CP System During Partition             │
├─────────────────────────────────────────────────────┤
│ Datacenter A          │     Network Partition       │
│   ┌─────────┐        │                             │
│   │ Leader  │        │         Datacenter B        │
│   │         │        │           ┌─────────┐       │
│   │ Can     │        │           │Follower │       │
│   │ serve   │        │           │         │       │
│   │ writes  │        │   ╳╳╳╳╳   │ Cannot  │       │
│   │ (quorum)│◄───────┼───╳╳╳╳╳───│ reach   │       │
│   └─────────┘        │   ╳╳╳╳╥   │ quorum  │       │
│      ▲               │          │         │       │
│      │               │          │ REJECTS │       │
│   Succeeds           │          │ WRITES  │       │
│                      │          └─────────┘       │
│                      │             ▲               │
│                      │             │               │
│                      │          Returns            │
│                      │          Error              │
└─────────────────────────────────────────────────────┘

Result: Only partition with quorum accepts writes
        Other partition rejects writes (unavailable)

Examples:

• MongoDB (default): Requires majority for writes during partition
• etcd: Raft consensus requires quorum (N/2 + 1)
• HBase: Region servers must reach ZooKeeper quorum

AP Systems: Availability + Partition Tolerance

Behavior During Partition:

┌─────────────────────────────────────────────────────┐
│              AP System During Partition             │
├─────────────────────────────────────────────────────┤
│ Datacenter A          │     Network Partition       │
│   ┌─────────┐        │                             │
│   │ Node 1  │        │         Datacenter B        │
│   │         │        │           ┌─────────┐       │
│   │ Accepts │        │           │ Node 2  │       │
│   │ write   │        │           │         │       │
│   │ x=1     │        │   ╥╥╥╥╥   │ Accepts │       │
│   │         │        │   ╥╥╥╥╥   │ write   │       │
│   └─────────┘        │   ╥╥╥╥╥   │ x=2     │       │
│      ▲               │          └─────────┘       │
│      │               │             ▲               │
│   Client A           │          Client B           │
│   (succeeds)         │          (succeeds)         │
│                      │                              │
│ When partition heals:                              │
│   Conflict: x=1 vs x=2                             │
│   Resolution: Last-Write-Wins, vector clocks, etc. │
└─────────────────────────────────────────────────────┘

Result: Both partitions accept writes
        Conflicts resolved after partition heals

Examples:

• Cassandra: Tunable consistency (can choose AP with QUORUM ONE)
• DynamoDB: Eventual consistency by default
• Riak: Last-Write-Wins or sibling resolution

PACELC Extension

Why PACELC?

CAP only describes behavior during partitions. What about normal operations (99%+ of the time)?

PACELC: If Partition, choose A or C; Else (normal), choose Latency or Consistency

PACELC Components

P-A-C-E-L-C
│ │ │ │ │ │
│ │ │ │ │ └─ Consistency (normal operation)
│ │ │ │ └─── Latency (normal operation)
│ │ │ └───── Else (no partition)
│ │ └─────── Consistency (during partition)
│ └───────── Availability (during partition)
└─────────── Partition occurs

PACELC Decision Matrix

┌─────────────────────────────────────────────────────┐
│               PACELC Trade-offs                     │
├─────────────────────────────────────────────────────┤
│                                                      │
│ IF PARTITION OCCURS:                                │
│   PA: Choose Availability (stale reads OK)          │
│   PC: Choose Consistency (reject some requests)     │
│                                                      │
│ ELSE (Normal Operation):                            │
│   EL: Choose Latency (async replication, fast)     │
│   EC: Choose Consistency (sync replication, slow)   │
│                                                      │
│ Common Combinations:                                 │
│   PA/EL: High availability, eventual consistency    │
│   PC/EC: Strong consistency, reduced availability   │
│   PC/EL: Hybrid (consistent during partition,       │
│          optimized for latency normally)            │
└─────────────────────────────────────────────────────┘

PACELC Matrix

Database Classification

Detailed System Behaviors

PA/EL Systems (DynamoDB, Cassandra):

During Partition:
  - Accept writes in both partitions (A)
  - Conflicts resolved later

Normal Operation:
  - Async replication (L)
  - Low latency writes
  - Eventual consistency

PC/EC Systems (MongoDB, etcd):

During Partition:
  - Only majority partition accepts writes (C)
  - Minority partition rejects writes

Normal Operation:
  - Synchronous replication (C)
  - Higher latency (wait for replicas)
  - Strong consistency

Tunable Systems (Cosmos DB):

Cosmos DB offers 5 consistency levels:
  1. Strong (PC/EC)
  2. Bounded Staleness (PC/EC with lag bound)
  3. Session (PA/EL with session consistency)
  4. Consistent Prefix (PA/EL with ordered reads)
  5. Eventual (PA/EL)

Real-World System Classification

Banking System (PC/EC)

Requirements:
  - Account balance must be correct
  - No overdrafts allowed
  - Transactions must be atomic

Design:
  ├─ During Partition: Choose Consistency (PC)
  │  Reject writes if quorum unavailable
  │
  └─ Normal Operation: Choose Consistency (EC)
     Synchronous replication to all replicas
     Higher latency acceptable for correctness

Technology: Spanner, VoltDB, PostgreSQL (sync replication)

Social Media Feed (PA/EL)

Requirements:
  - Users can always post
  - Slight delay in seeing posts OK
  - Likes/follows can be approximate

Design:
  ├─ During Partition: Choose Availability (PA)
  │  Accept posts in all datacenters
  │  Resolve conflicts later (merge likes)
  │
  └─ Normal Operation: Choose Latency (EL)
     Async replication for low latency
     Eventual consistency acceptable

Technology: Cassandra, DynamoDB, Couchbase

E-Commerce (Hybrid: PC for inventory, PA for catalog)

Inventory:
  ├─ PC/EC: Strong consistency for stock count
  └─ Prevent overselling

Product Catalog:
  ├─ PA/EL: Eventual consistency for descriptions, prices
  └─ Stale data acceptable briefly

Shopping Cart:
  ├─ PA/EL: Eventually consistent, can merge carts
  └─ High availability critical

Decision Framework

Step 1: Identify Requirements

Ask: 1. Is data correctness critical? (banking, inventory) 2. Is availability more important than consistency? (social media) 3. Are users globally distributed? (latency matters) 4. Can the system tolerate stale reads? (analytics)

Step 2: Choose CAP Profile

Correctness Critical:
  └─► CP (Consistency + Partition Tolerance)
      Examples: Banking, inventory, booking

Availability Critical:
  └─► AP (Availability + Partition Tolerance)
      Examples: Social media, analytics, catalog

Hybrid (Different Per Feature):
  └─► CP for critical data, AP for non-critical
      Examples: E-commerce, SaaS platforms

Step 3: Choose PACELC Profile

Low Latency Critical:
  └─► PA/EL (Eventual consistency, async replication)
      Examples: Social media, caching, analytics

Strong Consistency Critical:
  └─► PC/EC (Strong consistency, sync replication)
      Examples: Banking, financial systems

Middle Ground:
  └─► PC/EL (Consistent during partition, optimized latency normally)
      Examples: Session stores, collaborative editing

Step 4: Select Technology

PA/EL Systems:
  - Cassandra (wide-column, tunable)
  - DynamoDB (key-value, managed)
  - Riak (key-value, open-source)

PC/EC Systems:
  - MongoDB (document, strong by default)
  - etcd (key-value, Raft consensus)
  - Spanner (SQL, global consistency)

Tunable Systems:
  - Cosmos DB (multi-model, 5 levels)
  - Cassandra (tunable quorum)
  - PostgreSQL (async, sync, quorum replication)

Example Decision Path

Use Case: Multi-Region Order System

Step 1: Requirements
  - Orders must be processed (availability)
  - Payment must be correct (consistency)
  - Users globally distributed (latency)

Step 2: Hybrid Approach
  ├─ Order placement: PA/EL (accept orders anywhere)
  ├─ Payment processing: PC/EC (strong consistency)
  └─ Order history: PA/EL (eventual consistency)

Step 3: Technology Choices
  ├─ Order service: DynamoDB (PA/EL)
  ├─ Payment service: PostgreSQL with sync replication (PC/EC)
  └─ Read model (CQRS): Elasticsearch (PA/EL)

Step 4: Conflict Resolution
  ├─ Orders: Timestamps + vector clocks
  ├─ Payments: Saga pattern with compensation
  └─ Idempotency: Unique request IDs

Best Practices

Start with PACELC, not just CAP:

• CAP only covers partition scenarios
• PACELC covers both partition and normal operation
• Most systems operate normally 99%+ of the time

Don't Assume CA is Achievable:

• CA (Consistency + Availability without Partition Tolerance) is impossible in distributed systems
• Network partitions WILL occur

Use Tunable Consistency:

• Cassandra: Per-query consistency (ONE, QUORUM, ALL)
• Cosmos DB: 5 consistency levels
• Choose based on operation criticality

Test Partition Scenarios:

• Use chaos engineering (e.g., Chaos Monkey)
• Simulate network partitions in testing
• Verify behavior matches expectations (CP or AP)

Monitor Trade-offs:

• Track replication lag (PA/EL systems)
• Monitor quorum health (PC systems)
• Alert on inconsistency windows exceeding SLA

Consensus Algorithms

Table of Contents

1. What is Consensus 2. Raft Algorithm 3. Paxos Algorithm 4. When to Use Consensus 5. Consensus vs Replication

What is Consensus

Definition

Consensus is the problem of getting multiple nodes to agree on a single value, even in the presence of failures.

Requirements (FLP Impossibility)

Consensus algorithm must guarantee: 1. Agreement: All correct nodes decide on the same value 2. Validity: Decided value was proposed by some node 3. Termination: All correct nodes eventually decide

FLP Impossibility: Cannot guarantee all three in an asynchronous system with even one failure. Practical algorithms trade termination for safety.

Use Cases

• Leader election: Elect exactly one leader
• Distributed locks: Only one node acquires lock
• Configuration management: All nodes agree on config
• Atomic commit: All nodes commit or all abort

Raft Algorithm

Overview

Raft is a consensus algorithm designed for understandability. It's equivalent to Paxos in fault-tolerance and performance.

Raft Components

┌──────────────────────────────────────────────────────┐
│                  Raft Roles                          │
├──────────────────────────────────────────────────────┤
│ LEADER:                                               │
│   - Handles all client requests                      │
│   - Replicates log to followers                      │
│   - Only one leader per term                         │
│                                                       │
│ FOLLOWER:                                             │
│   - Passive: responds to leader/candidate requests   │
│   - Becomes candidate if no heartbeat               │
│                                                       │
│ CANDIDATE:                                            │
│   - Requests votes from other nodes                  │
│   - Becomes leader if wins majority                  │
└──────────────────────────────────────────────────────┘

Raft Leader Election

┌──────────────────────────────────────────────────────┐
│              Raft Leader Election                    │
├──────────────────────────────────────────────────────┤
│ 1. Initial State: All nodes are followers           │
│    Election timeout: 150-300ms (randomized)          │
│                                                       │
│ 2. Follower times out (no heartbeat from leader)    │
│    → Becomes CANDIDATE                               │
│    → Increments term number                          │
│    → Votes for itself                                │
│    → Sends RequestVote RPCs to all nodes             │
│                                                       │
│ 3. Other nodes respond:                              │
│    ├─ Grant vote if:                                 │
│    │  - Haven't voted this term                      │
│    │  - Candidate's log is up-to-date                │
│    │                                                  │
│    └─ Deny vote otherwise                            │
│                                                       │
│ 4. Outcomes:                                          │
│    ├─ Wins election (majority votes)                 │
│    │  → Becomes LEADER                               │
│    │  → Sends heartbeats to all nodes                │
│    │                                                  │
│    ├─ Another node wins election                     │
│    │  → Receives heartbeat from new leader           │
│    │  → Becomes FOLLOWER                             │
│    │                                                  │
│    └─ Split vote (no majority)                       │
│       → Times out                                    │
│       → Starts new election (higher term)            │
└──────────────────────────────────────────────────────┘

Raft Log Replication

┌──────────────────────────────────────────────────────┐
│              Raft Log Replication                    │
├──────────────────────────────────────────────────────┤
│ Leader:  [1][2][3][4][5]                             │
│           │  │  │  │  │                              │
│           └──┼──┼──┼──┼──► AppendEntries RPC        │
│              │  │  │  │                              │
│ Follower 1: [1][2][3][4][5]  (up-to-date)           │
│                                                       │
│ Follower 2: [1][2][3][ ][ ]  (lagging)               │
│              └──────────────► Receives entries 4,5   │
│                                                       │
│ Follower 3: [1][2][X][4][ ]  (conflict at 3)         │
│              └──────────────► Deletes 3, gets 3,4,5  │
│                                                       │
│ Commit:                                               │
│   Leader commits entry when replicated to majority   │
│   Leader notifies followers of commit index          │
│   Followers apply committed entries to state machine │
└──────────────────────────────────────────────────────┘

Raft Safety Properties

Election Safety: At most one leader per term Leader Append-Only: Leader never deletes/overwrites entries Log Matching: If two logs contain same entry at same index, all preceding entries are identical Leader Completeness: If entry committed in term T, present in all leaders of future terms State Machine Safety: If node applies entry at index i, no other node applies different entry at i

Example: etcd

# Start etcd cluster (3 nodes for fault tolerance)
etcd --name node1 --initial-cluster node1=http://10.0.1.1:2380,node2=http://10.0.1.2:2380,node3=http://10.0.1.3:2380
etcd --name node2 --initial-cluster node1=http://10.0.1.1:2380,node2=http://10.0.1.2:2380,node3=http://10.0.1.3:2380
etcd --name node3 --initial-cluster node1=http://10.0.1.1:2380,node2=http://10.0.1.2:2380,node3=http://10.0.1.3:2380

# Write key-value (goes to leader, replicated via Raft)
etcdctl put mykey "myvalue"

# Read key (can read from any node)
etcdctl get mykey

# Check cluster status
etcdctl endpoint status --cluster

# Simulate leader failure (kill leader process)
# Raft elects new leader automatically (election timeout ~300ms)
# Writes continue with new leader

# Leader election observable:
# - Term number increases
# - New leader sends heartbeats
# - Old leader becomes follower when recovered

Paxos Algorithm

Overview

Paxos is the original consensus algorithm, known for complexity but proven correct.

Paxos Roles

┌──────────────────────────────────────────────────────┐
│                  Paxos Roles                         │
├──────────────────────────────────────────────────────┤
│ PROPOSER:                                             │
│   - Proposes values                                  │
│   - Coordinates consensus rounds                     │
│                                                       │
│ ACCEPTOR:                                             │
│   - Votes on proposed values                         │
│   - Majority of acceptors must agree                 │
│                                                       │
│ LEARNER:                                              │
│   - Learns chosen value                              │
│   - Passive (doesn't participate in voting)          │
│                                                       │
│ Note: Nodes can play multiple roles                  │
└──────────────────────────────────────────────────────┘

Paxos Phases

┌──────────────────────────────────────────────────────┐
│              Paxos Two-Phase Process                 │
├──────────────────────────────────────────────────────┤
│ PHASE 1: Prepare                                      │
│   Proposer:                                          │
│   1. Choose proposal number n (higher than any seen) │
│   2. Send PREPARE(n) to majority of acceptors        │
│                                                       │
│   Acceptors:                                          │
│   3. If n > highest seen:                            │
│      - Promise not to accept proposals < n           │
│      - Reply with highest accepted proposal (if any) │
│                                                       │
│ PHASE 2: Accept                                       │
│   Proposer:                                          │
│   4. If majority promises:                           │
│      - If any acceptor returned value, use it        │
│      - Otherwise, use own value                      │
│   5. Send ACCEPT(n, value) to majority               │
│                                                       │
│   Acceptors:                                          │
│   6. If haven't promised higher n:                   │
│      - Accept proposal (n, value)                    │
│      - Reply with acceptance                         │
│                                                       │
│ LEARN:                                                │
│   7. Majority accepts → Value is chosen              │
│   8. Notify learners of chosen value                 │
└──────────────────────────────────────────────────────┘

Paxos Example

Scenario: 5 nodes (A, B, C, D, E) need to agree on value

Round 1:
  Proposer A: PREPARE(1) → B, C, D
  B, C, D: Promise (no prior proposals)
  Proposer A: ACCEPT(1, "value_A") → B, C, D
  B, C, D: Accept
  Result: "value_A" chosen

Round 2 (concurrent with Round 1):
  Proposer E: PREPARE(2) → B, C, D
  B, C, D: Promise (already accepted (1, "value_A"))
  Proposer E: ACCEPT(2, "value_A") → Must use "value_A"
  B, C, D: Accept
  Result: "value_A" chosen (consistency maintained)

Multi-Paxos

Single Paxos: Expensive (2 round trips per decision)
Multi-Paxos: Optimize for multiple decisions
  - Elect stable leader
  - Leader skips Phase 1 for subsequent proposals
  - Similar to Raft (leader-based)

Used by: Google Chubby, Google Spanner

When to Use Consensus

Scenarios Requiring Consensus

Leader Election:

Problem: Need exactly one leader
Solution: Raft/Paxos elects leader with majority votes
Examples: etcd, Consul, ZooKeeper

Distributed Locks:

Problem: Multiple services need exclusive access to resource
Solution: Consensus on lock ownership
Examples: etcd locks, Consul sessions

Configuration Management:

Problem: All nodes need same configuration
Solution: Consensus on config values
Examples: etcd for Kubernetes config

Atomic Commit (Distributed Transactions):

Problem: All nodes must commit or all must abort
Solution: Two-phase commit with consensus for coordinator election
Examples: Spanner, CockroachDB

When NOT to Use Consensus

High Write Throughput:

Consensus is slow (coordination overhead)
Alternative: Leaderless replication (Dynamo-style)

Eventual Consistency Acceptable:

Consensus is overkill for social media, caching
Alternative: Asynchronous replication

Single Datacenter:

Leader-follower sufficient (simpler than consensus)
Alternative: PostgreSQL streaming replication

Consensus vs Replication

Comparison

Decision Framework

Choose Consensus When:
├─ Automatic leader election required
├─ Strong consistency critical
├─ Partition tolerance essential
└─ Complexity acceptable

Choose Replication When:
├─ Manual failover acceptable
├─ Lower latency needed
├─ Simpler operations preferred
└─ Eventual consistency OK

Technology Examples

Consensus-Based:

• etcd: Raft for key-value store
• Consul: Raft for service discovery, configuration
• ZooKeeper: ZAB (Zookeeper Atomic Broadcast, Paxos-like)
• CockroachDB: Raft for distributed SQL
• TiDB: Raft for distributed SQL

Replication-Based:

• PostgreSQL: Streaming replication (leader-follower)
• MySQL: Binary log replication
• MongoDB: Replica sets (with automatic failover, not full consensus)
• Redis: Sentinel (master-replica with failover)

Best Practices

Cluster Size:

• Odd numbers (3, 5, 7) for quorum
• 3 nodes: Tolerates 1 failure
• 5 nodes: Tolerates 2 failures
• More nodes = higher latency

Network Stability:

• Consensus sensitive to network partitions
• Ensure low-latency, stable network
• Co-locate nodes in same datacenter if possible

Monitoring:

• Track leader elections (frequency)
• Monitor quorum health
• Alert on slow consensus rounds
• Watch for split votes

Testing:

• Chaos engineering (kill nodes during consensus)
• Network partition tests
• Leader election under load

Consistency Models

Table of Contents

1. Consistency Spectrum 2. Strong Consistency (Linearizability) 3. Sequential Consistency 4. Causal Consistency 5. Eventual Consistency 6. Bounded Staleness 7. Choosing Consistency Models

Consistency Spectrum

Strongest ◄─────────────────────────────────────────────► Weakest
   │           │              │              │              │
   │           │              │              │              │
Linearizable Sequential   Causal        Bounded        Eventual
(Strictest)  (Program     (Causally     Staleness     (Converges
             order)       ordered)      (Time-bounded) eventually)

Trade-offs:
Latency:    Highest  →→→→→→→→→→→→→→→→→→→→→→→→→→→→→→  Lowest
Throughput: Lowest   →→→→→→→→→→→→→→→→→→→→→→→→→→→→→→  Highest
Availability: Low    →→→→→→→→→→→→→→→→→→→→→→→→→→→→→→  High
Complexity: Low      →→→→→→→→→→→→→→→→→→→→→→→→→→→→→→  High

Strong Consistency (Linearizability)

Definition

All operations appear to execute atomically in some sequential order. Once a write completes, all subsequent reads see that value or a newer one.

Formal Guarantee

If operation A completes before operation B begins, then B must see the effects of A.

Timeline Example

┌──────────────────────────────────────────────────────┐
│         Strong Consistency (Linearizable)           │
├──────────────────────────────────────────────────────┤
│ Time →                                               │
│                                                       │
│ Client A:  Write(x=1) ───┬───► [Complete]           │
│                          │                           │
│                          │ (replication latency)     │
│                          │                           │
│ Client B:                └──────► Read(x) → 1        │
│                                    │                  │
│ Client C:                          └───► Read(x) → 1 │
│                                                       │
│ Guarantee: All reads after write see new value      │
│            No stale reads allowed                    │
└──────────────────────────────────────────────────────┘

Implementation Approaches

1. Single-Leader with Synchronous Replication:

┌────────────┐
│   Leader   │ ◄── All writes
└─────┬──────┘
      │ (sync replication)
      ├──────────┬──────────┐
      ▼          ▼          ▼
  Follower   Follower   Follower
  (wait ACK) (wait ACK) (wait ACK)
      │          │          │
      └──────────┴──────────┘
              │
        Write confirmed only after
        all replicas ACK

2. Consensus Algorithms (Raft, Paxos):

• Leader election + log replication
• Majority quorum required
• Examples: etcd, Consul

3. Two-Phase Commit (2PC):

• Coordinator + participants
• Prepare phase + commit phase
• Blocking (not recommended for high availability)

Use Cases

Financial Transactions:

-- Bank transfer: Must be atomic and consistent
BEGIN TRANSACTION;
  UPDATE accounts SET balance = balance - 100 WHERE id = 'A';
  UPDATE accounts SET balance = balance + 100 WHERE id = 'B';
COMMIT;

-- Subsequent read must see both updates
SELECT balance FROM accounts WHERE id IN ('A', 'B');

Inventory Management:

Read stock: 5 items
Client attempts purchase: 2 items
Write new stock: 3 items

All subsequent reads must see 3 (or fewer if another purchase)
Never see stale value of 5

Seat/Ticket Booking:

• Prevent double-booking
• Once seat sold, all clients see it as unavailable

Trade-offs

Benefits:

• ✅ Simplifies application logic (no conflicts)
• ✅ Immediate consistency guarantees
• ✅ Easy to reason about

Costs:

• ❌ Higher latency (coordination overhead)
• ❌ Reduced availability (partition blocks writes)
• ❌ Lower throughput (synchronous operations)

Technology Examples

Sequential Consistency

Definition

Operations from each client appear in the order they were issued, but operations from different clients may be interleaved differently at different nodes.

Difference from Linearizability

• Linearizability: Global real-time ordering
• Sequential: Per-client ordering, but no global time

Timeline Example

┌──────────────────────────────────────────────────────┐
│            Sequential Consistency                    │
├──────────────────────────────────────────────────────┤
│ Client A:  Write(x=1) → Write(x=2)                  │
│                         (Order preserved)            │
│                                                       │
│ Client B:  Read(x) → May see 0, 1, or 2             │
│            But if sees 2, cannot later see 1         │
│            (Order within client preserved)           │
│                                                       │
│ Node 1 sees: x=1, x=2                                │
│ Node 2 sees: x=1, x=2  (Same order)                 │
│                                                       │
│ Guarantee: Per-client program order preserved        │
│            But no real-time ordering across clients  │
└──────────────────────────────────────────────────────┘

Use Cases

• Distributed caches with invalidation
• Session stores
• Collaborative applications (weaker than causal)

Implementation

• Lamport clocks
• Vector clocks (partial)
• FIFO queues per client

Causal Consistency

Definition

Operations that are causally related are seen by all nodes in the same order. Concurrent operations may be seen in different orders.

Causality Rules

Event A → Event B (A "happens-before" B) if:
1. A and B occur on same process, A before B
2. A is send(message), B is receive(message)
3. Transitivity: A→B and B→C, then A→C

Concurrent events (A || B):
  Neither A→B nor B→A
  Can be observed in any order

Timeline Example

┌──────────────────────────────────────────────────────┐
│              Causal Consistency Example              │
├──────────────────────────────────────────────────────┤
│ Alice:  Post message A                               │
│            │                                          │
│            │ (causes - Bob sees A first)             │
│            ▼                                          │
│ Bob:    Reply B (to A)                               │
│            │                                          │
│            │ (causes - Carol sees A and B first)     │
│            ▼                                          │
│ Carol:  Reply C (to B)                               │
│                                                        │
│ Guarantee: All users see messages A → B → C          │
│            (Causally ordered)                         │
│                                                        │
│ Charlie: Post X (concurrent with A, B, C)            │
│                                                        │
│ No Guarantee: X may appear anywhere in timeline      │
│               (Not causally related to A, B, C)      │
│                                                        │
│ Possible orderings for users:                        │
│ - User 1 sees: A, B, X, C                            │
│ - User 2 sees: X, A, B, C                            │
│ - User 3 sees: A, B, C, X                            │
│                                                        │
│ Invalid ordering: B, A, C (violates causality)       │
└──────────────────────────────────────────────────────┘

Use Cases

Chat Applications:

User A: "What's for dinner?"
User B: "Pizza!" (reply to A)
User C: "Sounds great!" (reply to B)

All users must see:
  "What's for dinner?" → "Pizza!" → "Sounds great!"

Concurrent message: "Meeting at 3pm" may appear anywhere

Collaborative Editing:

User A: Add paragraph at line 10
User B: Edit paragraph at line 10 (depends on A's add)

All editors must see A's add before B's edit

Comment Threads:

• Replies to comments preserve causality
• Concurrent comments can appear in any order

Implementation Approaches

1. Vector Clocks:

class VectorClock:
    def __init__(self, node_id, nodes):
        self.node_id = node_id
        self.clock = {node: 0 for node in nodes}

    def increment(self):
        self.clock[self.node_id] += 1

    def update(self, other_clock):
        for node, count in other_clock.items():
            self.clock[node] = max(self.clock[node], count)
        self.increment()

    def happens_before(self, other):
        # self → other if self ≤ other and self ≠ other
        return (all(self.clock[n] <= other.clock[n] for n in self.clock)
                and self.clock != other.clock)

    def concurrent(self, other):
        return not (self.happens_before(other) or other.happens_before(self))

2. Lamport Timestamps:

class LamportClock:
    def __init__(self):
        self.time = 0

    def tick(self):
        self.time += 1
        return self.time

    def update(self, received_time):
        self.time = max(self.time, received_time) + 1
        return self.time

3. Database Support:

• Azure Cosmos DB: Session consistency level
• Cassandra: WITH CONSISTENCY QUORUM + lightweight transactions

Trade-offs

Benefits:

• ✅ Stronger than eventual, weaker than strong
• ✅ Better performance than strong consistency
• ✅ Intuitive for users (causality preserved)
• ✅ Suitable for collaborative applications

Costs:

• ❌ More complex than eventual consistency
• ❌ Requires tracking causality metadata
• ❌ Higher storage overhead (vector clocks)

Eventual Consistency

Definition

If no new updates are made, all replicas will eventually converge to the same value. Stale reads are possible.

Timeline Example

┌──────────────────────────────────────────────────────┐
│            Eventual Consistency Timeline             │
├──────────────────────────────────────────────────────┤
│ Time →                                               │
│                                                       │
│ Client A:  Write(x=1) ──► Leader (success)          │
│                │                                      │
│                │ (async replication starts)          │
│                │                                      │
│ Client B:      └──► Read(x) → 0 (STALE!)            │
│                          │                            │
│                          │ (replication continues)   │
│                          │                            │
│ Client B (later):        └──► Read(x) → 1 (fresh)   │
│                                                       │
│ Guarantee: Eventually consistent (seconds to minutes)│
│            Intermediate stale reads possible         │
└──────────────────────────────────────────────────────┘

Conflict Resolution Strategies

1. Last-Write-Wins (LWW):

def resolve_lww(value1, timestamp1, value2, timestamp2):
    if timestamp1 > timestamp2:
        return value1
    return value2

2. Application-Specific Merge:

def merge_shopping_carts(cart1, cart2):
    # Union of items with quantity sum
    merged = {}
    for item_id, qty in cart1.items():
        merged[item_id] = qty
    for item_id, qty in cart2.items():
        merged[item_id] = merged.get(item_id, 0) + qty
    return merged

3. Conflict-Free Replicated Data Types (CRDTs):

# G-Counter (Grow-only counter)
class GCounter:
    def __init__(self, node_id, nodes):
        self.node_id = node_id
        self.counts = {node: 0 for node in nodes}

    def increment(self):
        self.counts[self.node_id] += 1

    def value(self):
        return sum(self.counts.values())

    def merge(self, other):
        for node, count in other.counts.items():
            self.counts[node] = max(self.counts[node], count)

Use Cases

Social Media:

• Likes, follows, unfollows (counts can be approximate)
• Post feeds (slight delay acceptable)
• Profile updates (stale OK briefly)

Product Catalogs:

• Prices, descriptions (brief staleness OK)
• Inventory counts (with reservation system)

DNS:

• Zone updates propagate eventually
• TTL-based caching

Analytics:

• View counts, metrics (approximation acceptable)
• Aggregations (eventual consistency sufficient)

Implementation Techniques

1. Asynchronous Replication:

Leader → Log entry → Async send to followers
         ↓
    Return success
    (Don't wait for followers)

2. Anti-Entropy (Gossip Protocol):

def gossip_protocol(node, peers, interval=10):
    while True:
        # Select random peer
        peer = random.choice(peers)

        # Exchange data
        my_data = node.get_data()
        peer_data = peer.get_data()

        # Merge (reconcile differences)
        node.merge(peer_data)
        peer.merge(my_data)

        time.sleep(interval)

3. Read Repair:

def read_with_repair(key, replicas, quorum):
    # Read from quorum nodes
    responses = [replica.read(key) for replica in replicas[:quorum]]

    # Find most recent value
    latest = max(responses, key=lambda r: r.timestamp)

    # Repair stale replicas in background
    for replica, response in zip(replicas, responses):
        if response.timestamp < latest.timestamp:
            asyncio.create_task(replica.write(key, latest))

    return latest.value

Trade-offs

Benefits:

• ✅ Low latency (no coordination)
• ✅ High availability (accepts writes anytime)
• ✅ Scales better (no synchronous waits)
• ✅ Partition-tolerant

Costs:

• ❌ Application must handle stale reads
• ❌ Conflict resolution complexity
• ❌ Hard to reason about (non-deterministic)
• ❌ Testing challenges

Bounded Staleness

Definition

Reads may lag behind writes, but staleness is bounded by time or number of versions.

Timeline Example

┌──────────────────────────────────────────────────────┐
│      Bounded Staleness (Bound: 5 seconds)           │
├──────────────────────────────────────────────────────┤
│ Time →                                               │
│                                                       │
│ T=0:   Write(x=1) ──► Leader                         │
│                                                       │
│ T=2:   Read(x) → May return 0 or 1 (within bound)   │
│                                                       │
│ T=4:   Read(x) → May return 0 or 1 (within bound)   │
│                                                       │
│ T=6:   Read(x) → MUST return 1 (bound exceeded)     │
│                                                       │
│ Guarantee: Staleness ≤ 5 seconds                     │
│            OR                                         │
│ Guarantee: Staleness ≤ K versions behind             │
└──────────────────────────────────────────────────────┘

Configuration Examples

Time-Based Bound:

-- Azure Cosmos DB: Bounded Staleness
-- Max lag: 10 seconds OR 1000 operations
CREATE COLLECTION my_collection
WITH CONSISTENCY_LEVEL = 'BoundedStaleness',
     MAX_STALENESS_PREFIX = 1000,
     MAX_STALENESS_INTERVAL = 10;

Version-Based Bound:

def read_with_bound(key, max_versions_behind):
    # Read with staleness bound
    current_version = leader.get_version(key)
    replica_value, replica_version = replica.read(key)

    # If too stale, read from leader
    if current_version - replica_version > max_versions_behind:
        return leader.read(key)

    return replica_value

Use Cases

Real-Time Dashboards:

• Metrics with acceptable lag (e.g., 10 seconds)
• SLA: "Dashboard data max 30 seconds old"

Inventory with Buffer:

• Stock count can be slightly stale
• Buffer ensures no overselling

Leaderboards:

• Slight delay acceptable (eventual rankings)
• Bound: "Rank updates within 1 minute"

Trade-offs

Benefits:

• ✅ Middle ground: consistency + performance
• ✅ Predictable staleness window
• ✅ Suitable for real-time systems with tolerance

Costs:

• ❌ More complex than eventual
• ❌ Requires monitoring lag
• ❌ Must handle bound violations

Choosing Consistency Models

Decision Framework

START: Choose consistency model
  │
  ├─► Money involved? → Strong Consistency
  │
  ├─► Double-booking unacceptable? → Strong Consistency
  │
  ├─► Causality important (chat, edits)? → Causal Consistency
  │
  ├─► Stale reads tolerable with time bound? → Bounded Staleness
  │
  ├─► Read-heavy, stale tolerable? → Eventual Consistency
  │
  └─► Default? → Eventual (then strengthen if needed)

Use Case Matrix

Implementation Checklist

For Strong Consistency:

• [ ] Use synchronous replication or consensus (Raft, Paxos)
• [ ] Accept higher latency for correctness
• [ ] Plan for reduced availability during partitions
• [ ] Consider PostgreSQL sync replication, etcd, Spanner

For Eventual Consistency:

• [ ] Implement conflict resolution strategy (LWW, merge, CRDTs)
• [ ] Design for idempotency (safe retries)
• [ ] Monitor convergence time
• [ ] Consider Cassandra, DynamoDB, Riak

For Causal Consistency:

• [ ] Implement vector clocks or Lamport timestamps
• [ ] Track causality metadata
• [ ] Test causality violations
• [ ] Consider Azure Cosmos DB (Session consistency)

For Bounded Staleness:

• [ ] Define acceptable staleness window
• [ ] Monitor replication lag
• [ ] Alert on bound violations
• [ ] Consider Azure Cosmos DB (Bounded Staleness level)

Service Discovery

Table of Contents

1. Client-Side Discovery 2. Server-Side Discovery 3. Service Mesh

Client-Side Discovery

Architecture

Service Registry (Consul, etcd, Eureka)
  ↑
  | (register)
  |
Services (register on startup)
  ↑
  | (query & call)
  |
Client (queries registry, selects instance, calls directly)

Implementation (Consul)

import consul
import random
import requests

class ServiceDiscovery:
    def __init__(self, consul_host='localhost', consul_port=8500):
        self.consul = consul.Consul(host=consul_host, port=consul_port)
    
    def register(self, service_name, service_id, host, port, health_check_url):
        self.consul.agent.service.register(
            name=service_name,
            service_id=service_id,
            address=host,
            port=port,
            check=consul.Check.http(health_check_url, interval='10s')
        )
    
    def discover(self, service_name):
        index, services = self.consul.health.service(service_name, passing=True)
        return [{'host': s['Service']['Address'], 'port': s['Service']['Port']} 
                for s in services]
    
    def call_service(self, service_name, path):
        instances = self.discover(service_name)
        if not instances:
            raise Exception(f"No instances of {service_name}")
        
        # Load balance (random)
        instance = random.choice(instances)
        url = f"http://{instance['host']}:{instance['port']}{path}"
        return requests.get(url)

# Usage
sd = ServiceDiscovery()
sd.register('payment-service', 'payment-1', 'localhost', 8080, 'http://localhost:8080/health')
response = sd.call_service('payment-service', '/process-payment')

Server-Side Discovery

Architecture

Client → Load Balancer → Service Registry → Services

The load balancer queries the service registry and routes requests.

Benefits: Simple clients

Trade-off: Load balancer as single point of failure

Service Mesh

Concept

Sidecar proxies handle service discovery, routing, retries, circuit breaking.

Examples

• Istio: Full-featured service mesh
• Linkerd: Lightweight service mesh
• Consul Connect: Service mesh from Consul

Architecture

Service A Container + Envoy Sidecar
  ↓ (routes through)
Service B Container + Envoy Sidecar

Benefits

• Decouples communication logic
• Centralized traffic management
• mTLS encryption
• Observability (tracing, metrics)

Trade-offs

• Operational complexity
• Latency overhead (proxy hop)
• Resource usage (sidecar per service)