Top 80 SystemDesign Interview Questions & Answers

A Content Delivery Network (CDN) is a globally distributed network of servers (Points of Presence — PoPs) that cache and serve content from locations geographically closer to the user.

How it works:

1. User requests cdn.example.com/image.jpg
2. DNS resolves to the nearest CDN edge server (based on anycast routing or GeoDNS)
3. Edge server checks its cache:
   • Cache hit: Returns content immediately (~5-20ms)
   • Cache miss: Fetches from origin, caches it, returns to user
4. Subsequent requests from same region → cache hit

What CDNs cache:

• Static assets: JS, CSS, images, fonts, videos
• Cacheable API responses (with proper Cache-Control headers)
• Dynamically rendered HTML (edge-side rendering)

CDN Features:

• SSL termination at edge — reduces TLS handshake latency
• DDoS protection — absorbs traffic at edge, protects origin
• Compression — Brotli/gzip at edge
• Image optimization — WebP conversion, resizing on-the-fly
• Edge computing — Cloudflare Workers, Lambda@Edge for logic at edge

Cache-Control headers:

• Cache-Control: public, max-age=86400 — CDN caches for 24h
• Cache-Control: no-store — never cache (user-specific data)
• Vary: Accept-Encoding — cache separate copy per encoding

Cache invalidation: URL versioning (main.abc123.js) or CDN API purge

Providers: Cloudflare, AWS CloudFront, Fastly, Akamai, Azure CDN

Use when: Serving media/static assets globally; high traffic with cacheable content; DDoS protection needed; reducing origin load.

Monolithic Architecture: All application functionality is deployed as a single unit. UI, business logic, and data access are tightly coupled in one codebase and deployed together.

Pros: Simple development/debugging, no network overhead between components, easy transactions, great for small teams Cons: Scaling requires scaling the entire app, deployment risk (one change = full redeploy), technology lock-in, team coupling at scale

Microservices Architecture: Application is decomposed into small, independent services, each owning its business capability, data store, and deployment lifecycle.

Pros:

• Independent deployment and scaling
• Technology heterogeneity (each service picks its stack)
• Fault isolation (one service crash doesn't bring down others)
• Teams can work independently
• Easier to understand each service in isolation

Cons:

• Distributed systems complexity: network failures, latency, partial failures
• Cross-service transactions require Saga pattern
• Operational overhead: service discovery, observability, multiple deployments
• Data consistency challenges
• Over-engineering for small teams

When to use microservices:

• Large organization with multiple autonomous teams
• Different components have vastly different scaling needs
• Need independent deployment velocity
• Amazon's rule: 'Two-pizza team should own a service'

Strangler Fig Pattern: Don't rewrite the monolith — incrementally extract services piece by piece.

SQL (Relational Databases): PostgreSQL, MySQL, Oracle

• Schema: Fixed, predefined schema with tables, rows, foreign keys
• Consistency: ACID transactions — Atomicity, Consistency, Isolation, Durability
• Joins: Native, efficient multi-table joins
• Scaling: Primarily vertical; horizontal sharding is hard
• Query: Powerful SQL — aggregations, joins, window functions

NoSQL Databases — 4 types:

1. Document stores (MongoDB, Firestore): JSON-like documents. Great for hierarchical, flexible-schema data. Use for: user profiles, product catalogs

2. Key-Value stores (Redis, DynamoDB): Simple get/set by key. Extremely fast. Use for: caches, session storage, rate limiting counters

3. Wide-column stores (Cassandra, HBase): Rows with dynamic columns grouped into column families. Great for time-series, write-heavy workloads. Use for: IoT data, event logs, time-series metrics

4. Graph databases (Neo4j, Amazon Neptune): Nodes and edges. Use for: social networks, fraud detection, recommendation engines

Choose SQL when:

• Complex relationships and joins are needed
• ACID transactions are required (financial, medical)
• Data schema is well-defined and stable
• Team is comfortable with relational modeling

Choose NoSQL when:

• Horizontal scalability is critical
• Schema is flexible or unknown upfront
• Specific access patterns dominate (key lookups, time-series)
• Eventual consistency is acceptable

System Design is the process of defining the architecture, components, modules, interfaces, and data flow of a system to satisfy specified requirements. It bridges the gap between a problem statement and a working, scalable solution.

In interviews it matters because:

• It reveals how you think about trade-offs (consistency vs availability, latency vs throughput)
• It shows whether you can reason about scale — from 1K to 100M users
• It tests your knowledge of real distributed systems primitives: databases, caches, queues, load balancers
• Senior engineers are expected to design systems that survive real-world load, failures, and growth

Key areas tested: Scalability, Reliability, Availability, Consistency, Maintainability, Cost efficiency.

Before diving into design, always clarify these non-functional requirements (NFRs):

1. Scale — How many users (DAU/MAU)? How many requests per second (RPS)?
2. Latency — p99 latency target? (e.g., <100ms for reads)
3. Availability — 99.9% (8.7h downtime/yr) vs 99.99% (52min/yr) vs 99.999%?
4. Consistency — Strong, eventual, or read-your-writes?
5. Durability — Can we lose any data? (financial systems: no; analytics: maybe)
6. Read/Write ratio — Read-heavy (Twitter timeline) vs write-heavy (logging)?
7. Data size — How much data stored? Growth rate?
8. Geo-distribution — Single region or global?
9. Security & Compliance — PII data? GDPR? HIPAA?

These shape every architectural decision that follows.

Back-of-the-envelope (BOE) calculations give you order-of-magnitude estimates to drive architectural decisions.

Key numbers to memorize:

• L1 cache: ~1ns | RAM: ~100ns | SSD: ~100μs | Network: ~1ms
• 1 server can handle ~1,000–10,000 RPS depending on workload
• 1 TB = 10^12 bytes | 1 PB = 10^15 bytes
• 86,400 seconds/day ≈ 100K

Example — Design Twitter:

• 300M DAU, each reads 100 tweets/day = 300M × 100 / 86,400 ≈ 347K read RPS
• 300M DAU, each tweets 1/day = 300M / 86,400 ≈ 3,500 write RPS
• 1 tweet = 280 chars ≈ 1KB. 3,500 writes/s × 1KB = 3.5 MB/s ingestion
• Storage: 3,500 × 1KB × 86,400 × 365 ≈ 110 TB/year

This immediately tells you: read-heavy system, needs aggressive caching, separate read/write paths.

Vertical Scaling (Scale Up): Adding more resources to a single machine — more CPU cores, more RAM, faster SSDs.

• ✅ Simple — no code changes, no distributed systems complexity
• ✅ Strong consistency — single node, no synchronization issues
• ❌ Has a hardware ceiling — you can't scale infinitely
• ❌ Single point of failure
• ❌ Downtime during upgrades

Horizontal Scaling (Scale Out): Adding more machines and distributing the load across them.

• ✅ Theoretically unlimited scale
• ✅ High availability — failure of one node doesn't bring down the system
• ✅ Cost-effective using commodity hardware
• ❌ Complexity — distributed systems, data partitioning, network failures
• ❌ Requires stateless services or shared state management

When to choose: Start vertical for simplicity. Move horizontal when you hit the vertical ceiling or need fault tolerance. Most large-scale systems use horizontal scaling with a load balancer in front.

A load balancer distributes incoming network traffic across multiple backend servers to ensure no single server becomes a bottleneck.

Types:

• L4 (Transport layer) — routes based on IP + TCP/UDP port. Fast, low overhead. No content inspection.
• L7 (Application layer) — routes based on HTTP headers, URL paths, cookies. Enables content-aware routing (e.g., route /api to API servers, /static to CDN).

Algorithms:

1. Round Robin — requests distributed sequentially. Simple, works when servers are uniform.
2. Weighted Round Robin — servers with more capacity get proportionally more requests.
3. Least Connections — new request goes to server with fewest active connections. Great for long-lived connections.
4. IP Hash — client IP determines server. Provides session stickiness. Problem: uneven distribution if many users share an IP.
5. Least Response Time — routes to fastest responding server. Requires health probing.
6. Random — randomly picks a server. Surprisingly effective at scale.

Health checks: Load balancers continuously ping backends; unhealthy servers are removed from rotation automatically.

REST (Representational State Transfer):

• Protocol: HTTP/1.1 or HTTP/2, JSON payload
• Contract: OpenAPI/Swagger specification (optional, not enforced)
• Verbs: GET, POST, PUT, DELETE map to CRUD
• Streaming: Not natively supported (workarounds: SSE, WebSockets)
• Browser support: Universal
• Tooling: Universal, every language has libraries
• Debugging: Human-readable JSON, easy with curl/Postman

gRPC (Google Remote Procedure Call):

• Protocol: HTTP/2 (required), binary Protobuf payload
• Contract: .proto file (enforced — strongly typed schema)
• Paradigms: Unary, client streaming, server streaming, bidirectional streaming
• Performance: ~7-10× smaller payload than JSON; ~5-8× faster serialization
• Browser support: Limited (grpc-web required; no native browser HTTP/2 trailers support)
• Code generation: Auto-generates client/server stubs in 10+ languages from .proto
• Debugging: Binary — need tools like grpcurl, Evans

When to choose REST:

• Public-facing APIs (external clients, browser apps)
• Simple CRUD operations
• Teams new to the API type
• Maximum ecosystem compatibility
• OpenAPI documentation is important

When to choose gRPC:

• Internal service-to-service communication (microservices)
• High-throughput, latency-sensitive calls
• Multi-language microservices (strong contract guarantees)
• Bidirectional streaming needed
• Mobile clients where bandwidth matters

Real-world: Netflix uses gRPC internally between hundreds of microservices; REST for external API

The Sidecar pattern deploys a helper container alongside a service container in the same pod (Kubernetes) or on the same host. The sidecar augments the primary service with cross-cutting concerns without modifying the service code.

How it works: The primary service and sidecar share the same network namespace (same localhost) and optionally the same filesystem. The sidecar intercepts or augments traffic to/from the primary container.

Common sidecar use cases:

1. Service mesh proxy (Envoy/Linkerd):

   • All inbound/outbound traffic routed through sidecar
   • mTLS, load balancing, circuit breaking, tracing — transparently
   • Service code unchanged

2. Log shipping (Fluentd/Logstash):

   • Service writes logs to a shared volume
   • Sidecar tails log files, ships to Elasticsearch/Splunk
   • Service doesn't need log shipping SDK

3. Config management (Vault Agent):

   • Sidecar authenticates with Vault, fetches secrets
   • Writes secrets to shared memory filesystem
   • Service reads from filesystem — no Vault SDK needed

4. Metrics collection (Prometheus exporter):

   • Sidecar exposes /metrics endpoint
   • Scrapes application metrics, converts to Prometheus format

5. Ambassador proxy:

   • Sidecar proxies requests to external services
   • Handles retry logic, rate limiting, circuit breaking
   • Service code stays clean

Benefits:

• Language agnostic: sidecar can be written in any language
• Separation of concerns: operational complexity outside the service
• Consistent policy enforcement across all services

Trade-off: Added resource overhead (every pod has extra container), complexity

MapReduce (Hadoop):

• Processing model: Map → Shuffle → Reduce (strictly sequential stages)
• State: Writes intermediate results to HDFS disk between every stage
• Latency: High — disk I/O between stages (minutes to hours per job)
• Programming model: Low-level Java API (verbose)
• Fault tolerance: Re-run failed tasks by re-reading from HDFS checkpoints
• Use case: Batch processing where latency isn't critical; datasets that exceed RAM

Apache Spark:

• Processing model: DAG (Directed Acyclic Graph) of transformations — lazy evaluation
• State: Keeps intermediate results in memory (RDD caching/persistence)
• Latency: 10-100× faster than MapReduce for iterative algorithms
• Programming model: High-level APIs in Python, Scala, Java, R (DataFrame, SQL, MLlib)
• Fault tolerance: RDD lineage — if partition lost, recompute from lineage (not from disk checkpoint)
• Streaming: Spark Streaming (micro-batch) and Spark Structured Streaming (continuous)

Why Spark is faster: Iterative ML algorithms (gradient descent, k-means) run MapReduce stage: read HDFS → process → write HDFS → repeat 100 iterations = 100 HDFS reads/writes. Spark keeps data in memory across iterations — 100× speedup.

When to use each:

• MapReduce: Enormous datasets (petabytes) that don't fit in cluster RAM; simple one-pass ETL; legacy Hadoop ecosystems
• Spark: Machine learning (iterative algorithms), interactive analytics, streaming, complex multi-stage pipelines; the modern default for big data processing

Modern landscape: Spark on Kubernetes (no Hadoop needed), Delta Lake for ACID on Spark, Databricks as managed Spark

Request-Response (Synchronous): Service A sends a request to Service B and waits for a response before continuing.

• Temporal coupling: Both services must be available simultaneously
• Tight coupling: A knows B exists and where it is
• Latency: A's response time depends on B's response time
• Simplicity: Easy to reason about; immediate feedback; simple error handling
• Use: CRUD APIs, user-facing operations needing immediate result, simple integrations

Event-Driven Architecture (Asynchronous): Service A publishes an event to a broker; Service B (and potentially C, D) consume that event independently.

• Temporal decoupling: Services don't need to be available at the same time
• Loose coupling: A doesn't know who cares about its events; B doesn't know who produced the event
• Scalability: Consumers process at their own pace; absorbs traffic spikes
• Fan-out: One event consumed by multiple services independently
• Resilience: If B is down, events queue up and are processed when B recovers
• Complexity: Harder to trace flow; eventual consistency; ordering guarantees harder; debugging harder
• Use: Background jobs, cross-service notifications, data pipelines, audit logging

Key trade-off question: 'Does the user need the result NOW or can we process it later?'

• Book a hotel → synchronous (user needs confirmation now)
• Send confirmation email → asynchronous (can happen seconds later)
• Generate invoice → asynchronous (can take a minute)
• Update search index → asynchronous (eventual consistency acceptable)

Hybrid is normal: Most large systems use both patterns — synchronous for user-facing APIs, async for background processing and cross-service data propagation.

OLTP (Online Transaction Processing): Operational workloads — inserting, updating, deleting records in real-time as part of running the business.

• Operations: Simple queries (by primary key), short transactions, many concurrent users
• Data volume: Months of 'hot' data; older data archived
• Latency: Sub-millisecond to single-digit ms required
• Concurrency: Thousands of concurrent transactions
• Schema: Normalized (3NF) to minimize redundancy and update anomalies
• Examples: Web app database, order management, inventory, banking transactions
• Databases: PostgreSQL, MySQL, Oracle, SQL Server, CockroachDB

OLAP (Online Analytical Processing): Analytical workloads — complex queries over large historical datasets to derive business insights.

• Operations: Complex aggregations over millions/billions of rows, few concurrent users
• Data volume: Years of historical data (TB to PB)
• Latency: Seconds to minutes acceptable
• Concurrency: Dozens of analysts
• Schema: Denormalized (Star schema, Snowflake schema) for query performance
• Examples: Revenue dashboards, customer cohort analysis, fraud pattern detection
• Databases: BigQuery, Snowflake, Redshift, ClickHouse, Databricks

Star Schema (data warehouse):

• Fact table: Metrics and foreign keys (orders: order_id, customer_id, product_id, amount, date)
• Dimension tables: Descriptive attributes (customers, products, time dimensions)
• Optimized for GROUP BY, aggregation queries

The pipeline: OLTP DB → ETL/ELT (dbt, Airbyte) → Data Warehouse (OLAP) → BI Tool (Looker, Tableau)

HTAP (Hybrid): Some systems try to serve both (TiDB, AlloyDB) — useful but trade-offs exist

The Twelve-Factor App is a methodology for building scalable, maintainable, cloud-native applications, formalized by Heroku.

The 12 factors:

1. Codebase: One codebase tracked in VCS; many deploys (dev/staging/prod from same repo)
2. Dependencies: Explicitly declare and isolate dependencies (package.json, requirements.txt, go.mod). Never rely on system-installed packages.
3. Config: Store config in environment variables (not hardcoded, not config files checked into git). Sensitive values from secrets manager.
4. Backing services: Treat databases, caches, queues as attached resources — interchangeable via config URL.
5. Build, release, run: Strictly separate build (compile) → release (build + config) → run (execute) stages. Releases are immutable.
6. Processes: Execute as one or more stateless processes. All persistent state in backing services (DB/cache). Enables horizontal scaling.
7. Port binding: Export services via port binding. App is self-contained web server (not deployed into external web server).
8. Concurrency: Scale out via the process model. Different process types (web, worker) can scale independently.
9. Disposability: Fast startup, graceful shutdown. Handle SIGTERM; finish current requests; drain queues. Enables rolling deploys and autoscaling.
10. Dev/prod parity: Keep environments as similar as possible. Use same DB type locally as in prod. Same backing services.
11. Logs: Treat logs as event streams. Write to stdout; environment handles routing/storage.
12. Admin processes: Run admin/management tasks as one-off processes (migrations, scripts) in the same environment as the app.

Why it matters: Following these principles makes apps naturally container-friendly, horizontally scalable, and environment-agnostic — prerequisites for Kubernetes and cloud-native deployment.

Three approaches for pushing real-time updates from server to client:

Long Polling:

• Client sends HTTP request; server holds it open until data is available (or timeout)
• Server responds → client immediately sends new request
• Effectively simulates push with repeated requests
• ✅ Works through proxies/firewalls; simple to implement
• ❌ High latency (request overhead per message); not truly real-time; heavy server connection load
• Use: Simple notifications, fallback when WebSockets blocked

Server-Sent Events (SSE):

• Client opens HTTP connection; server pushes events as text/event-stream
• Unidirectional: server → client only
• HTTP/1.1: 6 connection limit per domain; HTTP/2: multiplexed
• Built-in reconnection, event IDs, last-event-id for replay
• ✅ Simple API (EventSource); works through HTTP proxies; built-in reconnect
• ❌ Unidirectional only; not all proxies handle long connections well
• Use: News feeds, live dashboards, server logs streaming, AI chat streaming

WebSocket:

• Full-duplex, bidirectional persistent connection (upgraded from HTTP)
• Both client and server can send messages at any time
• Low overhead: 2-byte frame header vs full HTTP headers
• ✅ Truly bidirectional; low latency; efficient for high-frequency messages
• ❌ More complex; some proxies/firewalls block WS; stateful connection complicates scaling
• Use: Chat applications, multiplayer games, collaborative editing, live trading

Scaling WebSockets:

• Sticky sessions (session affinity at load balancer) OR
• Redis Pub/Sub: all WebSocket servers subscribe; when message arrives, publish to Redis, all WS servers receive and forward to appropriate connected clients

Comparison:

A vector database stores and indexes high-dimensional vector embeddings, enabling similarity search — finding the N most semantically similar items to a query.

Why it exists: Traditional databases find exact matches (WHERE id = 5) or substring matches (LIKE '%keyword%'). They can't find 'conceptually similar' documents.

ML models (OpenAI embeddings, Sentence-BERT) convert text/images/audio into dense vector representations (e.g., 1536-dimensional float arrays). Semantically similar content has vectors that are close together in this high-dimensional space.

The search problem: Given a query vector, find the K most similar vectors in a database of millions/billions. Exact nearest neighbor (exhaustive) is O(N×D) — too slow at scale.

Approximate Nearest Neighbor (ANN) algorithms:

1. HNSW (Hierarchical Navigable Small World): Graph-based; builds a layered graph of connections; greedy traversal finds near-optimal neighbors. O(log N) search. Used by: pgvector, Weaviate, Milvus.

2. IVF (Inverted File Index): Clusters vectors into Voronoi cells; search only cells nearest to query. O(√N). Used by: FAISS, Pinecone.

3. LSH (Locality Sensitive Hashing): Hash similar vectors into same buckets. O(1) bucket lookup. Less accurate.

Vector database features beyond simple search:

• Filtering: nearest(query_vector) WHERE category = 'electronics'
• Hybrid search: Combine vector similarity with keyword BM25 scoring
• Metadata storage: Store original text, IDs, and payload alongside vectors

Popular databases: Pinecone (managed), Weaviate, Qdrant, Milvus, Chroma, pgvector (PostgreSQL extension)

Use cases: Semantic search, RAG (Retrieval Augmented Generation), recommendation systems, image similarity, anomaly detection

The N+1 query problem occurs when fetching a list of N entities and then making 1 additional query per entity — resulting in N+1 total queries instead of 1-2.

Classic example:

# Fetch all orders (1 query)
orders = db.query('SELECT * FROM orders LIMIT 100')  # 1 query

# For each order, fetch the customer (N queries)
for order in orders:
    customer = db.query('SELECT * FROM customers WHERE id = ?', order.customer_id)  # 100 queries!

# Total: 101 queries instead of 1!

Solutions in relational databases:

1. JOIN in SQL: SELECT o.*, c.* FROM orders o JOIN customers c ON o.customer_id = c.id — 1 query

2. Eager loading (ORM): Order.includes(:customer) in Rails, FetchType.EAGER in JPA, Prisma's include

3. Batch loading (DataLoader pattern):

   • Collect all requested IDs within a single tick
   • Issue 1 batched query: SELECT * FROM customers WHERE id IN (1, 2, 3, ...)
   • Return results to individual requestors
   • Used by: Facebook DataLoader (GraphQL), Prisma, Hasura

In GraphQL (critical problem): GraphQL resolvers are called per field, making N+1 endemic. DataLoader is the standard solution — batch and cache within a request.

Detection:

• ORM slow query logging: log queries taking >100ms + queries-per-request counter
• APM tools (Datadog, New Relic) show query count per endpoint
• Query log analysis: detect identical queries repeated N times
• Django Debug Toolbar, Bullet gem (Rails), Hibernate statistics

In microservices: N+1 at service level: fetching a list from Service A, then calling Service B once per item. Fix: Add a batch endpoint to Service B; or use async fan-out with Promise.all.

Row-Oriented (Row Store): Stores entire rows together on disk. When you read a record, all columns come with it.

• Read pattern: Full row access is fast (fetch record by primary key)
• Write pattern: Inserting/updating a row is one operation
• Compression: Poor — each row has mixed types and values
• Use case: OLTP — transaction processing, web applications (PostgreSQL, MySQL, SQL Server)

Column-Oriented (Column Store): Stores each column's values together on disk. A query touching 3 columns of a 100-column table reads only 3% of the data.

• Read pattern: Analytical queries that aggregate a few columns across many rows are extremely fast
• Write pattern: Slower — inserting a row requires writing to many separate column files
• Compression: Excellent — same column has same type; repeated values compress well (run-length encoding, dictionary encoding)
• Use case: OLAP — analytics, data warehousing (BigQuery, Redshift, ClickHouse, Snowflake, Parquet files)

Example — 'Total sales by region' query:

• Row store: Reads ALL columns of ALL rows (99% unnecessary I/O)
• Column store: Reads ONLY region and amount columns (2% of data I/O)

Vectorized execution: Column stores apply CPU SIMD instructions to operate on arrays (columns) simultaneously. Dramatically faster than row-by-row processing.

Hybrid (HTAP): Some databases support both workloads: TiDB, Google AlloyDB, SingleStore. Row store for OLTP; column store (secondary indexes or separate columnstore index) for analytics.

The Bulkhead pattern (named after ship hull compartments that prevent one flood from sinking the whole ship) isolates resources for different services or operations so that a failure in one doesn't exhaust resources for others.

The problem without bulkhead: All microservice calls share one thread pool. Slow Recommendation Service causes threads to pile up waiting. All 200 threads exhausted. Now slow Recommendation blocks fast User Service calls too. Everything fails.

Bulkhead implementations:

1. Thread Pool Isolation (Hystrix):

• Separate thread pool per downstream dependency
• Recommendation Service: 20 threads
• Payment Service: 10 threads
• User Service: 15 threads
• If Recommendation Service is slow and exhausts its 20 threads — Payment and User are unaffected

2. Connection Pool Isolation:

• Separate database connection pools per service/use case
• Read pool: 50 connections (for high-volume reads)
• Write pool: 20 connections (for transactional writes)
• Analytics pool: 5 connections (for slow reporting queries)
• Analytics queries never starve critical OLTP operations

3. Semaphore Isolation:

• Limit concurrent calls to a downstream service using a semaphore
• If semaphore count is exhausted, fail-fast immediately
• No thread pool overhead; suitable for low-latency operations

4. Process/Container Isolation:

• Run different microservices in separate processes/containers/VMs
• Memory leak in one service can't crash others

Combined with Circuit Breaker: Bulkhead prevents resource exhaustion; Circuit Breaker stops calling a failing service. Together they provide comprehensive fault isolation.

A Bloom filter is a space-efficient probabilistic data structure that answers the question 'Is this element in the set?' with:

• Definitely NOT in set: 100% accurate
• Probably in set: With a small false positive probability (no false negatives)

How it works:

1. Initialize a bit array of M bits (all zeros)
2. Choose K independent hash functions
3. Add element: Hash it K times; set those K bits to 1
4. Check element: Hash it K times; if ANY of the K bits is 0 → definitely not in set; if ALL are 1 → probably in set

Parameters:

• Larger bit array (M) → lower false positive rate
• More hash functions (K) → lower FP rate up to a point, then increases
• Optimal K = (M/N) × ln(2) where N is expected element count
• Typical FP rate: 1% at 10 bits per element

Practical applications:

1. LSM-tree/RocksDB: 'Is this key in this SSTable?' — avoids unnecessary disk reads. Dramatically reduces read amplification.

2. Cassandra: 'Is this partition key on this node?' — prevents unnecessary disk lookups on reads.

3. Google BigTable/Spanner: Used in storage layers.

4. Distributed deduplication: 'Have we processed this event/URL before?' — check Bloom filter before DB lookup.

5. Browser safe browsing: Chrome's malicious URL list is a Bloom filter (100M+ URLs in ~1MB) — check locally, query server only on positive match.

6. API rate limiting: Detect if an IP has been seen before without storing all IPs.

Limitations: Cannot delete elements (use Counting Bloom Filter for that); false positives exist; size must be pre-allocated.

Horizontal Pod Autoscaler (HPA): Scales the number of pod replicas within existing nodes based on observed metrics.

• Metrics sources: CPU utilization, memory utilization, custom metrics (RPS via Prometheus), external metrics (SQS queue depth via KEDA)
• Algorithm: desiredReplicas = ceil(currentReplicas × currentMetric / targetMetric)
• Example: Target CPU 50%; current CPU 80% with 3 pods → ceil(3 × 80/50) = 5 pods
• Cooldown periods: scale-up immediately; scale-down waits 5 minutes (avoid flapping)
• Does NOT add nodes — only adds/removes pods within current node capacity

Cluster Autoscaler (CA): Scales the number of nodes in the cluster based on pending pods and underutilized nodes.

• Scale UP trigger: Pod can't be scheduled because no node has enough resources (pod is 'Pending')
• Scale DOWN trigger: A node is underutilized (<50% CPU/memory) and its pods can be moved to other nodes
• Cloud-provider aware: Provisions new VMs from auto-scaling group (AWS ASG, GKE Node Pool, AKE VMSS)
• Scale down: Drains pods (respects PodDisruptionBudgets), removes node
• Conservative: Takes 10-15 minutes to provision a new node

KEDA (Kubernetes Event-Driven Autoscaler): Extends HPA with event-driven triggers:

• Scale pods based on: Kafka consumer lag, SQS queue depth, Prometheus metrics, cron schedule
• Can scale to zero (no traffic = no pods, no cost)

Combined workflow:

1. Traffic spike → HPA scales pods → pods can't schedule (no node capacity)
2. Cluster Autoscaler detects pending pods → provisions new nodes
3. New nodes join cluster → pods schedule → traffic handled
4. Traffic drops → HPA scales down pods → nodes underutilized → Cluster Autoscaler removes nodes

Already covered in question 7. This entry covers practical implementation implications.

Achieving Strong Consistency — Techniques:

1. Consensus protocols (Raft/Paxos): All writes go through a leader that ensures majority acknowledgment before commit. Used by etcd, CockroachDB.

2. 2-Phase Locking (2PL): Database acquires read/write locks for transaction duration. No new reads during write. Serializable isolation.

3. Serializable Snapshot Isolation (SSI): PostgreSQL's approach. MVCC-based, detects conflicts at commit time. Serializable without most locking overhead.

4. Synchronous replication: Primary waits for all replicas to acknowledge.

Achieving Eventual Consistency — Techniques:

1. Async replication with conflict resolution: LWW, vector clocks, CRDTs

2. Gossip protocols: Nodes periodically exchange state; convergence without central coordinator

3. Anti-entropy: Background process scans and syncs diverged replicas using Merkle trees

The practical spectrum (weakest → strongest): Eventual → Monotonic Read → Consistent Prefix → Read-Your-Writes → Bounded Staleness → Strong

Bounded staleness (Azure Cosmos DB): Reads may lag behind writes by at most K versions or T seconds — useful middle ground.

Real decision framework:

• User balance, inventory count, seat availability → Strong
• Social feed, view counts, recommendations → Eventual
• Profile updates visible to same user → Read-Your-Writes

Data Warehouse:

• Stores structured, processed data in a schema-on-write model (schema defined before loading)
• Optimized for complex analytical queries (OLAP)
• Data is cleaned, transformed, and integrated (ETL pipeline: Extract, Transform, Load)
• High query performance on structured data
• Examples: Snowflake, BigQuery, Redshift, Azure Synapse
• Use: Business intelligence dashboards, financial reporting, structured analytics

Data Lake:

• Stores raw data in any format (structured, semi-structured, unstructured): JSON, Parquet, CSV, images, logs, video
• Schema-on-read: schema applied when data is queried, not when stored
• ELT (Extract, Load, Transform): load raw data first, transform later for specific use cases
• Cheaper storage (S3/GCS/ADLS) but slower query unless optimized
• Examples: AWS S3 + Athena, Azure Data Lake, GCS + BigQuery
• Use: Data science, ML training data, long-term raw data retention, exploratory analysis

Data Lakehouse (modern approach): Combines the best of both: raw storage with warehouse-like performance and ACID transactions.

• Technologies: Delta Lake (Databricks), Apache Iceberg, Apache Hudi
• Features: ACID transactions on data lake files, schema enforcement, time travel (query historical snapshots), Z-ordering for query optimization
• Used by: Uber, Netflix, LinkedIn

Typical modern stack: Source systems → Kafka → Data Lake (S3 + Iceberg) → dbt transformations → Data Warehouse (Snowflake) → BI Tool (Tableau/Looker)

Distributed systems fail in partial, unpredictable ways. These patterns make systems resilient:

1. Retry with Exponential Backoff + Jitter: Retry failed requests with increasing delays. Jitter randomizes delay to prevent synchronized retry storms.

delay = min(cap, base * 2^attempt) + random(0, base)

2. Circuit Breaker: Stop calling a failing service; return fallback immediately. (Covered in detail separately.)

3. Timeout: Never wait indefinitely. Set aggressive timeouts (p99 latency × 1.5). Prevents thread exhaustion.

4. Bulkhead: Isolate resources per dependency using separate thread pools or connection pools. Failure in one bulkhead doesn't exhaust resources for others. (Like ship compartments — one floods, ship survives.)

5. Fallback: Return cached, default, or degraded response when primary path fails.

• Recommendation service down → return trending items
• Personalization service down → return generic homepage

6. Dead Letter Queue (DLQ): Messages that fail after N retries go to DLQ for manual inspection and replay.

7. Idempotency: Design operations so retrying them has the same effect as executing once. Use idempotency keys (UUID per request). Store in Redis to detect duplicate requests.

8. Graceful Degradation: System remains functional at reduced capacity when components fail. Feature flags disable non-critical features.

9. Health Checks & Autoscaling: Probes (liveness/readiness in Kubernetes) detect unhealthy instances; autoscaling handles sudden traffic spikes.

10. Chaos Engineering: Proactively inject failures (Chaos Monkey, Gremlin) to validate resilience assumptions.

Idempotency: An operation is idempotent if performing it multiple times has the same effect as performing it once.

Why critical: In distributed systems, networks fail, timeouts occur, and clients retry. Without idempotency, a retry of a payment request could charge the user twice.

HTTP methods and idempotency:

• GET, HEAD, PUT, DELETE → naturally idempotent by design
• POST → not idempotent by default (each call creates a new resource)
• PATCH → depends on implementation

Implementing idempotent POST endpoints:

Pattern 1 — Idempotency Key header:

POST /payments
Idempotency-Key: 550e8400-e29b-41d4-a716-446655440000

{
  "amount": 100,
  "currency": "USD"
}

• Server stores (idempotency_key, response) in Redis with 24h TTL
• On first request: process and store result
• On duplicate request: return stored result without reprocessing
• Used by: Stripe, Braintree, all payment APIs

Pattern 2 — Natural idempotency keys:

• Use business-meaningful unique ID: order_id, transaction_id
• INSERT ... ON CONFLICT DO NOTHING (PostgreSQL)
• DynamoDB ConditionExpression: attribute_not_exists(pk)

Pattern 3 — Optimistic locking with version:

• Include expected version in request
• Reject if version doesn't match current state

Considerations:

• Idempotency key store must itself be reliable
• Consider using the same TX ID across retries
• Log idempotency key hits for monitoring

Requirements:

• Return top 5 suggestions as user types
• Latency < 100ms end-to-end
• Suggestions ranked by popularity
• Support 10M queries/day

Data Collection:

• Log every completed search query
• Count frequency per query string
• Weekly batch job aggregates counts → stored in key-value store

Trie Data Structure: Trie (prefix tree) stores all query strings. Each node represents a character. Path from root to node = prefix.

• Store top-K suggestions at each node (precomputed)
• Query: traverse trie following each typed character → return stored top-K at leaf
• Update frequency: batch update trie weekly (not real-time — too expensive)

Architecture:

User types → Browser (debounced 300ms) → API Gateway
  → Load Balancer → Autocomplete Servers (N nodes)
    → Redis (prefix → [top 5 suggestions]) ← most requests served here
    → Trie service (on cache miss)
    → Cassandra (raw frequency data, updated by batch job)

Redis storage:

• Key: prefix string (e.g., 'appl')
• Value: sorted set of suggestions with frequency score
• ZREVRANGE 'appl' 0 4 WITHSCORES → top 5

Handling updates:

• Real-time: Too expensive to update trie on every query
• Batch: Hadoop/Spark job runs nightly; recalculates top-K per prefix; updates Redis
• Lag: Suggestions reflect last 7 days of data

Filtering: Block offensive/inappropriate suggestions; maintain blocklist

Personalization: User's recent searches boosted; federated learning for privacy

Kubernetes (K8s) is a container orchestration platform that automates deployment, scaling, and management of containerized applications.

Core concepts:

• Pod: Smallest deployable unit. One or more containers sharing network and storage.
• Deployment: Manages a set of identical Pods. Handles rolling updates, rollbacks.
• Service: Stable DNS name and IP that load-balances across Pods (even as they come and go).
• Ingress: HTTP/HTTPS routing rules mapping external URLs to Services.
• ConfigMap/Secret: Configuration and sensitive data injected into Pods.
• Namespace: Virtual cluster isolation within a physical cluster.
• HorizontalPodAutoscaler (HPA): Scales Pods up/down based on CPU/memory/custom metrics.

Why it enables scale:

1. Self-healing: Restarts crashed containers, replaces failed nodes, kills unresponsive pods.
2. Horizontal scaling: HPA adds pods when CPU > 70%, removes when load drops.
3. Rolling deployments: Zero-downtime deploys by gradually replacing old pods with new ones.
4. Service discovery: Services get stable DNS names regardless of pod IP changes.
5. Resource management: CPU/memory requests and limits prevent noisy neighbor problems.

Kubernetes architecture:

• Control Plane: API Server, etcd (cluster state), Scheduler (pod placement), Controller Manager
• Worker Nodes: kubelet (pod lifecycle), kube-proxy (networking), container runtime (containerd)

Production patterns: GitOps with ArgoCD/Flux, Helm charts for packaging, Istio for service mesh, KEDA for event-driven autoscaling

Observability is the ability to understand the internal state of a system from its external outputs. In distributed systems, you can't attach a debugger — you need to infer system behavior from telemetry data.

The Three Pillars:

1. Metrics: Numerical measurements over time. Aggregated, low-cost to store.

• Types: Counter (requests served), Gauge (current memory usage), Histogram (request latency distribution)
• Key metrics: Request rate, Error rate, Latency (p50/p95/p99), Saturation (queue depth, CPU)
• RED Method: Rate, Errors, Duration — for services
• USE Method: Utilization, Saturation, Errors — for resources
• Tools: Prometheus + Grafana, Datadog, CloudWatch

2. Logs: Immutable, timestamped records of discrete events.

• Structured logging (JSON) vs unstructured text — always use structured
• Correlation ID: inject a trace ID into every log entry to correlate across services
• Log levels: DEBUG (dev), INFO (key events), WARN (unexpected but handled), ERROR (needs attention)
• Tools: ELK Stack (Elasticsearch + Logstash + Kibana), Loki + Grafana, Splunk, Datadog Logs

3. Traces (Distributed Tracing): Records the end-to-end journey of a request across multiple services.

• Span: A unit of work with start time, duration, and metadata
• Trace: Collection of related spans forming a DAG
• Parent-child span relationships show service call hierarchy
• Tools: Jaeger, Zipkin, AWS X-Ray, Tempo, Datadog APM
• Standards: OpenTelemetry (vendor-neutral instrumentation)

Why all three: Metrics say 'there's a problem', logs say 'what happened', traces say 'where in the call chain it happened'.

The Strangler Fig Pattern (coined by Martin Fowler) describes how to incrementally migrate a monolith to microservices without a risky 'big bang' rewrite.

Named after: The strangler fig tree that grows around a host tree, eventually replacing it as the host dies.

Approach:

1. Place a Facade/Proxy (API Gateway or reverse proxy) in front of the monolith
2. Intercept requests at the facade
3. For each feature you want to extract: a. Build the new microservice independently b. Gradually route traffic for that feature from monolith → new service c. Verify the new service works correctly d. Remove the old code from the monolith
4. Repeat until the monolith is empty and can be decommissioned

Example migration path:

Week 1-4:   Auth service extracted (facade routes /auth/* to new service)
Week 5-8:   User profile service extracted
Week 9-12:  Order service extracted
...
Month 12:   Monolith decommissioned

Data migration challenge:

• New service needs its own database (database-per-service pattern)
• Use CDC/Debezium to sync monolith DB → new service DB during transition
• Eventually: new service writes to its own DB; monolith reads from it via API

Benefits:

• No big-bang rewrite (which almost always fails)
• Rollback: if new service fails, route traffic back to monolith
• Delivers business value continuously
• Team learns microservices gradually

Anti-pattern: Distributed monolith — extracted 'services' that are still tightly coupled

An API Gateway is a single entry point for all client requests in a microservices architecture. It sits between clients and backend services.

Core responsibilities:

1. Request Routing: Routes /api/users to User Service, /api/orders to Order Service
2. Authentication & Authorization: Validates JWT tokens, API keys — services don't need to implement this individually
3. Rate Limiting: Throttle requests per client/API key
4. SSL Termination: Handles HTTPS; backend services can use plain HTTP internally
5. Load Balancing: Distributes requests across service instances
6. Request/Response Transformation: Protocol translation, field renaming, version mapping
7. Caching: Cache responses for common GET requests
8. Logging & Monitoring: Centralized request logging, metrics, distributed tracing injection
9. Circuit Breaking: Detect failing backend services, return fallback
10. API Composition: Aggregate multiple service calls into one response (BFF pattern)

Popular implementations:

• Kong: Lua-based, highly extensible plugin ecosystem
• AWS API Gateway: Serverless, integrates with Lambda/ECS
• Nginx/Nginx Plus: High-performance, mature
• Traefik: Kubernetes-native, auto-discovers services
• Istio Ingress Gateway: Service mesh gateway

BFF Pattern (Backend for Frontend): Separate gateways for web vs mobile vs third-party. Each BFF optimizes responses for its specific client's needs without compromising other clients.

Database replication copies data from one database server (primary/master) to one or more other servers (replicas/secondaries).

Goals: High availability, read scaling, geographic distribution, backup

Replication Patterns:

1. Single-Leader (Master-Slave) Replication:

• All writes go to the primary; replicas receive the replication stream
• Reads can be served from replicas (read scaling)
• ✅ Simple, consistent write path
• ❌ Primary is a bottleneck for writes; failover requires promoting a replica
• Used by: MySQL, PostgreSQL streaming replication

2. Multi-Leader (Active-Active) Replication:

• Multiple nodes accept writes; changes replicated to each other
• ✅ Better write availability; lower write latency in multi-region setups
• ❌ Write conflicts — two nodes accept conflicting writes to same record
• Conflict resolution: Last Write Wins (LWW), version vectors, application-level merge
• Used by: CouchDB, Cassandra (multi-datacenter), Google Docs (offline edits)

3. Leaderless Replication:

• Any replica accepts writes; client writes to multiple replicas simultaneously
• Quorum reads/writes: W + R > N ensures reading at least one up-to-date node
• ✅ High availability; survives any node failures up to quorum
• ❌ Complex; potential for stale reads
• Used by: Cassandra, DynamoDB, Riak

Replication lag: Async replication means replicas can be slightly behind (seconds to minutes). Read-after-write consistency requires routing user's reads to primary or same replica they wrote to.

High Availability (HA) means a system remains operational and accessible for a high percentage of time, minimizing downtime.

Availability tiers:

• 99.9% = 8.7 hours downtime/year
• 99.99% = 52 minutes/year
• 99.999% (five nines) = 5.26 minutes/year

Key Strategies:

1. Eliminate Single Points of Failure (SPOFs):

• Redundant load balancers (active-passive or active-active)
• Database replication with automatic failover
• Multiple availability zones for every critical component

2. Redundancy & Failover:

• Active-Active: All instances serve traffic; if one fails, others absorb load
• Active-Passive: Standby takes over when primary fails (cold or warm standby)
• Health checks + automatic failover (DNS failover, cloud load balancer health checks)

3. Geographic Distribution:

• Multi-region deployment with traffic routing (Route 53 latency-based, failover routing)
• Global CDN for static assets and cacheable content

4. Graceful Degradation:

• If recommendation service is down, show popular items instead of crashing
• Feature flags to disable non-critical features under load

5. Chaos Engineering:

• Netflix Chaos Monkey randomly kills instances in production
• Validates that redundancy actually works
• Builds muscle memory for handling failures

6. Observability:

• SLIs/SLOs/SLAs: Define and measure what 'available' means
• Runbooks for every alert
• Automated remediation for known failure modes

MTTR vs MTBF: Minimize Mean Time To Recovery (MTTR) through automation, not just Mean Time Between Failures.

RPO (Recovery Point Objective): The maximum amount of data loss acceptable, measured in time. 'How old can the data be when we recover?'

• RPO = 1 hour → we can tolerate losing 1 hour of data
• RPO = 0 → zero data loss; requires synchronous replication
• Impacts: Backup frequency, replication strategy, storage costs

RTO (Recovery Time Objective): The maximum amount of downtime acceptable. 'How long can the system be down?'

• RTO = 4 hours → system must be back online within 4 hours
• RTO = 0 → zero downtime; requires active-active configuration
• Impacts: Failover automation, standby infrastructure, operational maturity

Cost relationship: Lower RPO and RTO = higher infrastructure and operational cost

Strategies per RTO/RPO target:

Backup & Restore: Daily backups to S3. RTO=hours, RPO=24h. Cheapest. Warm Standby: Scaled-down replica running, can be scaled up quickly. RTO=minutes. Hot Standby: Full-capacity replica ready to serve immediately. RTO=seconds. Active-Active: Multiple regions serving live traffic simultaneously. RTO≈0, RPO≈0.

Example for e-commerce: RPO=1min (can't lose more than 1 min of orders), RTO=5min (must be back in 5 min) → Warm standby + synchronous replication for write DB.

Synchronous Replication: The primary waits for all replicas to acknowledge the write before returning success to the client.

• ✅ Zero data loss — all replicas have the data before success is acknowledged
• ✅ Strong consistency — reads from any replica are up-to-date
• ❌ Write latency increases — must wait for the slowest replica
• ❌ Availability risk — if a replica is slow or unreachable, writes block
• Use: Financial transactions, critical data where losing any write is unacceptable
• Examples: PostgreSQL synchronous_commit=on, Google Spanner

Asynchronous Replication: The primary acknowledges success immediately after writing locally, replicates to replicas in the background.

• ✅ Low write latency — no waiting for replicas
• ✅ Higher availability — replica failure doesn't block writes
• ❌ Potential data loss — if primary crashes before replication, recent writes are lost (RPO > 0)
• ❌ Replication lag — replicas may be seconds to minutes behind
• Use: Read-scaling replicas, cross-region secondaries, analytics replicas
• Examples: MySQL async replication, PostgreSQL hot standby

Semi-synchronous (hybrid): At least one replica must acknowledge before success. Others replicate asynchronously.

• Balances: Minimal data loss without requiring all replicas to be fast
• MySQL supports this natively

Quorum writes (Cassandra/DynamoDB): Write must be acknowledged by W out of N replicas (configurable). Flexible trade-off between durability and latency.

Synchronous Communication: Service A calls Service B and waits for a response.

• REST/HTTP: Simple, universal, human-readable. Use for CRUD operations and simple request-response.
• gRPC: Binary protocol (Protobuf), strongly typed contracts, streaming support, lower latency. Use for internal service-to-service high-throughput calls.
• GraphQL: Flexible querying, reduces over/under-fetching. Use for client-facing APIs.

Pros: Simple mental model, immediate response Cons: Temporal coupling — both services must be up; cascading failures; tight latency dependency

Asynchronous Communication: Service A publishes a message/event; Service B processes it at its own pace.

• Message queues: RabbitMQ, SQS — task distribution, guaranteed processing
• Event streaming: Kafka — event log, replay, fan-out to multiple consumers

Pros: Decoupled — services can fail independently; absorbs spikes; enables fan-out Cons: Eventual consistency; harder to trace; complex error handling; out-of-order messages

Choosing between them:

• User-facing operations needing immediate response → Sync (REST/gRPC)
• Background processing (resize image, send email) → Async
• One event triggers multiple downstream actions → Async pub/sub
• Order matters, replay needed → Kafka

Circuit Breaker pattern (Hystrix, Resilience4j): Wraps sync calls; if downstream service fails repeatedly, 'open the circuit' and return fallback — prevents cascading failures.

The circuit breaker pattern is a stability mechanism that prevents a failing service from taking down its callers through a cascade of failures.

The problem: Service A calls Service B. Service B is slow (database overload). A's threads block waiting for B's response. A's thread pool exhausts. A starts failing. Service C which calls A also fails. The entire system collapses.

Circuit Breaker states:

1. Closed (normal): Requests flow through. Failures are counted.
2. Open (failure mode): After failure threshold exceeded (e.g., 50% errors in 30s), circuit opens. Calls are rejected immediately with fallback (no waiting for timeout).
3. Half-Open (recovery probe): After a cooldown period, allow a limited number of test requests. If they succeed → go back to Closed. If they fail → back to Open.

Configuration parameters:

• Failure threshold: % of requests that must fail to open circuit
• Slow call threshold: requests exceeding X ms count as failures
• Wait duration in Open state
• Number of probe calls in Half-Open

Fallback strategies:

• Return cached data
• Return a default/degraded response
• Fail fast with meaningful error message
• Queue request for later retry

Implementation: Resilience4j (Java), Hystrix (deprecated), Polly (.NET), built into Istio service mesh

Complementary patterns: Bulkhead (isolate thread pools per dependency), Retry with exponential backoff and jitter, Timeout configuration

Service discovery is the mechanism by which microservices find the network location (IP:port) of other services, given that in dynamic environments (Kubernetes, auto-scaling), service instances constantly start, stop, and change IP.

Two patterns:

1. Client-Side Discovery:

• Client queries a Service Registry (Eureka, Consul, etcd) directly
• Client selects an instance (load balancing logic on client)
• ✅ Client has full control over selection
• ❌ Client must implement discovery logic in every language/service
• Examples: Netflix Eureka, Consul

2. Server-Side Discovery:

• Client calls a Load Balancer/API Gateway
• LB queries Service Registry and forwards request
• ✅ Client is decoupled from discovery; any client can use it
• ❌ LB becomes a potential bottleneck
• Examples: AWS ALB + ECS, Kubernetes kube-proxy, Nginx with Consul template

Service Registry: A database of service instances and their locations.

• Self-registration: Each service registers itself on startup, deregisters on shutdown, sends heartbeats
• Third-party registration: Orchestrator (Kubernetes) manages registration

In Kubernetes:

• Services get stable DNS names: payment-service.default.svc.cluster.local
• kube-proxy handles routing; CoreDNS handles name resolution
• No external registry needed — etcd stores service endpoints

Health checks: Registry removes unhealthy instances automatically when heartbeats stop

Both are concurrency control mechanisms to handle multiple transactions accessing the same data simultaneously.

Pessimistic Locking: Assumes conflicts WILL happen — locks the resource before reading/writing.

• Database acquires a row lock (SELECT FOR UPDATE in SQL)
• Other transactions attempting to access the locked row are blocked until the lock is released
• ✅ Guarantees no conflict
• ❌ Can lead to deadlocks; reduces throughput; long waits under contention
• Use when: Conflicts are frequent; operations are short; correctness is critical (inventory deduction, balance update)

Optimistic Locking: Assumes conflicts are RARE — doesn't lock; detects conflict at commit time.

• Add a version column to the table
• Read: SELECT id, data, version FROM items WHERE id=1 → version=5
• Update: UPDATE items SET data=new, version=6 WHERE id=1 AND version=5
• If 0 rows affected → someone else updated (version changed) → retry
• ✅ High throughput; no blocking; no deadlocks
• ❌ Retry overhead if conflicts are frequent; more complex application code
• Use when: Conflicts are rare; reads vastly outnumber writes; long operations where holding a lock is impractical

Real-world example:

• Pessimistic: SELECT seat FOR UPDATE when booking a flight seat — two people shouldn't book the same seat
• Optimistic: Updating a user's profile — conflicts rare, version check sufficient

In distributed systems: Redis WATCH/MULTI/EXEC implements optimistic locking; compare-and-swap (CAS) operations in DynamoDB/Cassandra

CAP theorem states that a distributed system can only simultaneously guarantee two of three properties:

• C — Consistency: Every read receives the most recent write (all nodes see the same data)
• A — Availability: Every request receives a (non-error) response, even if it's not the latest
• P — Partition Tolerance: The system continues operating even when network partitions occur

Key insight: In a real distributed system, network partitions always happen (P is non-negotiable). So the real choice is:

• CP systems (sacrifice availability): PostgreSQL with synchronous replication, HBase, Zookeeper. Use when: financial transactions, inventory counts — correctness over uptime.
• AP systems (sacrifice consistency): Cassandra, DynamoDB, CouchDB. Use when: social feeds, shopping carts — availability over perfect accuracy.

Modern nuance — PACELC theorem extends CAP: Even when there's no partition (E), you must choose between Latency (L) and Consistency (C). This is more practical for day-to-day decisions.

Example decisions:

• Bank balance: CP — never show wrong balance
• Twitter likes count: AP — showing 1,000,001 vs 1,000,000 is acceptable

Strong Consistency: After a write completes, all subsequent reads from any node return that value. Feels like a single machine.

• Implementation: Synchronous replication, consensus protocols (Raft, Paxos)
• Cost: Higher latency (must wait for all replicas to acknowledge)
• Use cases: Bank balances, inventory, seat reservations

Eventual Consistency: If no new updates are made, all replicas will eventually converge to the same value. Reads may return stale data temporarily.

• Implementation: Async replication, gossip protocols
• Cost: Complexity in handling conflicts (Last Write Wins, vector clocks, CRDTs)
• Use cases: DNS propagation, social media likes/views, shopping cart (Amazon's famous Dynamo)

Causal Consistency: Operations that are causally related are seen in order by all nodes. Concurrent (unrelated) operations may be seen in different orders.

• 'If you see my reply, you must also see the message I replied to'
• Implementation: Vector clocks, logical timestamps
• Use cases: Collaborative editing, comment threads, chat apps

Read-your-writes Consistency: After you write, your subsequent reads always see your write (even if others don't yet).

• Implementation: Route user's reads to the same replica they wrote to (sticky sessions or primary reads)
• Use cases: User profile updates — you should see your own changes immediately

Sharding (horizontal partitioning) splits a large database across multiple machines, each responsible for a subset of the data.

Why shard?

• Single DB server can't handle the write throughput or data volume
• Vertical scaling has hit its ceiling

Sharding Strategies:

1. Range-based sharding: Shard by key range (A-F → shard 1, G-M → shard 2)

   • ✅ Easy range queries
   • ❌ Hot spots — if most users are 'A-F', shard 1 is overloaded

2. Hash-based sharding: shard = hash(key) % num_shards

   • ✅ Even distribution
   • ❌ Range queries span multiple shards
   • ❌ Resharding is painful — changing num_shards remaps most keys

3. Consistent hashing: Ring-based hashing where adding/removing nodes only remaps a fraction of keys

   • ✅ Minimal redistribution on topology changes
   • Used by: Cassandra, DynamoDB, Memcached

4. Directory-based sharding: A lookup service maps keys to shards

   • ✅ Flexible routing
   • ❌ Lookup service becomes a bottleneck/SPOF

Problems sharding introduces:

• Cross-shard joins: Must be done at application layer — expensive
• Cross-shard transactions: Requires 2-phase commit (2PC) — complex
• Hotspots: Celebrity problem — one key gets disproportionate traffic
• Rebalancing: Moving data when adding shards
• Schema changes: Must be applied to all shards

Consistent hashing maps both data keys and server nodes onto a virtual ring (0 to 2^32-1). A key is assigned to the first node clockwise from its hash position on the ring.

Standard hashing problem: shard = hash(key) % N — when N changes, nearly all keys remap. Adding 1 server to a 10-server cluster remaps ~91% of keys.

Consistent hashing solution: When a node is added/removed, only the keys between that node and its predecessor need to move. Adding 1 server to a 10-server cluster remaps only ~1/11 ≈ 9% of keys.

Virtual nodes (vnodes): Each physical server is assigned multiple positions on the ring (e.g., 150 virtual nodes each). This:

• Ensures more uniform distribution even with heterogeneous hardware
• Reduces the hot-spot risk if one physical node happens to get assigned a dense key range
• Cassandra, DynamoDB use this approach

Real-world usage: Cassandra, DynamoDB, Memcached (ketama), Chord DHT, Riak

Example: If ring has servers A, B, C at positions 0, 120, 240 degrees:

• Key hashing to 60 → goes to B (first clockwise)
• Key hashing to 180 → goes to C
• Remove B → keys that were going to B now go to C. Only B's keys move.

ACID is the set of properties that guarantee reliable database transactions:

A — Atomicity: All operations in a transaction succeed or all fail. No partial updates.

• Implementation: Write-Ahead Log (WAL). If the system crashes mid-transaction, the WAL is replayed or rolled back on recovery.

C — Consistency: Transaction brings the database from one valid state to another. All integrity constraints (foreign keys, unique constraints, check constraints) are maintained.

• Implementation: Constraint validation before commit.

I — Isolation: Concurrent transactions behave as if they were executed serially. No dirty reads, phantom reads, or non-repeatable reads (depending on isolation level).

• Isolation levels: Read Uncommitted < Read Committed < Repeatable Read < Serializable
• Implementation: MVCC (Multi-Version Concurrency Control) — PostgreSQL, MySQL InnoDB. Keeps multiple versions of rows, readers don't block writers.

D — Durability: Once a transaction is committed, it persists even through crashes.

• Implementation: WAL written to durable storage before acknowledging commit. Fsync to disk.

The cost: ACID guarantees come with performance overhead — locking, WAL writes, constraint checks. This is why high-throughput systems sometimes relax isolation levels or use eventual consistency.

Caching stores copies of frequently accessed data in fast storage (memory) to reduce latency and backend load.

Cache Placement Strategies:

1. Cache-Aside (Lazy Loading): Application checks cache first; on miss, loads from DB and populates cache.

   • ✅ Only caches what's actually needed
   • ❌ Cold start — first requests are slow; risk of stale data
   • Used by: Most web applications

2. Write-Through: On write, update both cache and DB synchronously.

   • ✅ Cache always fresh
   • ❌ Write latency increases; caches data that may never be read

3. Write-Behind (Write-Back): Write to cache immediately, async flush to DB.

   • ✅ Very low write latency
   • ❌ Risk of data loss if cache fails before flush

4. Read-Through: Cache sits in front of DB; cache fetches from DB on miss automatically.

   • ✅ Application only talks to cache
   • ❌ Cache vendor must support this

Eviction Policies:

• LRU (Least Recently Used): Evict the item not accessed for the longest time. Most common.
• LFU (Least Frequently Used): Evict the item accessed fewest times. Better for skewed access patterns.
• FIFO: Evict oldest inserted item. Simple but poor performance.
• TTL (Time-To-Live): Items expire after a fixed duration regardless of access.

Cache invalidation challenges:

• 'There are only two hard things in CS: cache invalidation and naming things'
• Strategies: TTL expiry, event-driven invalidation (pub/sub on data change), versioned cache keys

A cache stampede (thundering herd) occurs when a popular cache entry expires and thousands of concurrent requests simultaneously find a cache miss and all rush to regenerate the same data from the database — overwhelming the DB.

Scenario:

• Redis cache for a trending tweet expires
• 10,000 concurrent requests all get cache miss
• 10,000 queries hit the database simultaneously
• DB is overwhelmed; system may cascade-fail

Prevention Strategies:

1. Mutex/Lock: First thread acquires a distributed lock, regenerates cache, others wait.

   • ✅ Only one DB query
   • ❌ Other requests are blocked during regeneration

2. Probabilistic Early Expiration (XFetch algorithm):

   • Slightly before TTL expires, start returning stale data while recomputing in background
   • Formula: expiry - current_time < -1/β * log(random()) triggers early refresh
   • ✅ No blocking, no thundering herd

3. Background refresh: A background job proactively refreshes cache before expiry.

   • ✅ No stampede risk
   • ❌ Harder to implement for dynamic keys

4. Jitter on TTL: Add random offset to TTL so not all entries expire at the same time.

   • TTL = base_ttl + random(0, base_ttl * 0.1)
   • ✅ Simple, distributes expiry over time

5. Stale-While-Revalidate: Serve stale data while triggering async background update.

   • Used natively by CDNs and HTTP cache headers

A message queue is middleware that enables asynchronous communication between services by decoupling the producer (sender) from the consumer (receiver).

Core concepts:

• Producer: Publishes messages to the queue
• Consumer: Reads and processes messages from the queue
• Broker: The queue server (Kafka, RabbitMQ, SQS)
• At-least-once / Exactly-once delivery: Guarantees on message delivery

When to use a message queue:

1. Decoupling services: Payment service doesn't wait for notification service. Each can fail independently.
2. Handling traffic spikes: Queue absorbs burst traffic; consumers process at their own pace
3. Async processing: Image resizing, email sending, PDF generation — don't block the user request
4. Fan-out: One event triggers multiple downstream services (order placed → inventory, shipping, notification)
5. Retry logic: Failed messages can be retried with exponential backoff
6. Rate limiting: Limit how fast consumers process (e.g., don't overwhelm a third-party API)

Kafka vs RabbitMQ vs SQS:

• Kafka: High-throughput, log-based, replay-able, millions of messages/sec. Use for: event streaming, audit logs, data pipelines
• RabbitMQ: Traditional queue, complex routing (exchanges, bindings). Use for: task queues, RPC patterns
• SQS: Managed AWS queue, simple, scales automatically. Use for: AWS-native architectures

Message Queue (Point-to-Point):

• One producer, one consumer per message
• Message is removed from queue once consumed
• Load balancing across consumers: multiple consumers compete; each message processed by exactly one
• Use: Task distribution, worker pools
• Examples: RabbitMQ (basic queues), SQS, Redis Lists

Pub/Sub (Publish-Subscribe):

• One producer, multiple subscribers — each subscriber gets a copy of every message
• Publisher doesn't know who the subscribers are (loose coupling)
• Messages may be retained for replay (Kafka) or ephemeral (Redis Pub/Sub)
• Use: Event broadcasting, fan-out, real-time notifications
• Examples: Kafka Topics, Google Pub/Sub, Redis Pub/Sub, SNS

Kafka bridges both models:

• Topics with consumer groups = queue semantics (each message processed once per group)
• Topics with multiple consumer groups = pub/sub semantics (each group gets every message)
• Log retention = replay capability (replay events from any point in time)

Practical example:

• Order service publishes 'order.placed' event
• Queue: inventory-update worker picks it up (exactly once)
• Pub/Sub: inventory service, notification service, AND analytics service all receive a copy independently

Requirements clarification:

• 100M URLs shortened/day (write: ~1,200/sec)
• 10B redirects/day (read: ~115,000/sec) → heavily read-heavy
• Short URL must be unique, ~7 characters
• URLs must not expire (or configurable TTL)

Short URL Generation:

• 7 alphanumeric chars (62^7 ≈ 3.5 trillion) — enough headroom
• Base62 encoding of an auto-incremented ID or MD5/SHA256 hash (take first 7 chars)
• Preferred: Use a distributed ID generator (Snowflake) → encode as Base62
• Avoid hash collisions: if collision detected, append counter and retry

Architecture:

Client → CDN → Load Balancer → Shortening Service
                              ↓
                     ID Generator (Zookeeper)
                              ↓
                     PostgreSQL (long URL store)
                     
Client → CDN → Load Balancer → Redirect Service
                              ↓ (cache miss)
                     Redis Cache (shortCode → longURL)
                              ↓ (cache miss)
                     PostgreSQL (read replica)

Database schema:

CREATE TABLE urls (
  id BIGINT PRIMARY KEY,
  short_code VARCHAR(7) UNIQUE,
  long_url TEXT NOT NULL,
  user_id BIGINT,
  created_at TIMESTAMP,
  expires_at TIMESTAMP
);
CREATE INDEX idx_short_code ON urls(short_code);

Key decisions:

• Redis cache for redirect lookup (LRU, TTL=24h) — 80%+ hit rate expected
• CDN at edge for most popular URLs
• 301 (permanent) vs 302 (temporary) redirect — 302 for analytics (every hit logged), 301 to offload servers
• Rate limiting on write API to prevent abuse

Zero-downtime deployment means deploying new code to production without any period where the service is unavailable or degraded.

Why it's hard:

• Database schema changes must be compatible with both old and new code simultaneously
• In-flight requests during deployment must complete successfully
• Services may depend on each other — all must handle old and new versions simultaneously

Deployment Strategies:

1. Rolling Deployment: Replace pods/instances one at a time (or batch). At any point, mix of old and new versions running.

• ✅ Simple; no extra infrastructure
• ❌ Backward compatibility required (both versions run simultaneously)
• ❌ Slow to complete; rollback requires another rolling update

2. Blue-Green Deployment: Maintain two identical environments (blue = current, green = new). Switch traffic at load balancer atomically.

• ✅ Instant rollback: switch back to blue
• ✅ No mixed-version period
• ❌ 2× infrastructure cost; DB schema must work with both versions

3. Canary Deployment: Route small percentage of traffic (1-5%) to new version; gradually increase.

• ✅ Validates with real traffic; limits blast radius of bugs
• ✅ A/B test new features on subset of users
• ❌ Requires sophisticated traffic splitting (Istio, nginx weight routing)

4. Shadow Deployment (Traffic Mirroring): All production traffic mirrored to new version; new version runs but responses discarded.

• ✅ Test new version with production load/data with zero risk
• ❌ Double infrastructure cost during test; side effects must be suppressed

Database migrations for zero-downtime:

1. Never delete or rename columns/tables in one step
2. Expand-contract pattern: Add new column (nullable) → backfill → switch code → drop old column (weeks later)
3. Feature flags to control cutover

Tools: Kubernetes rolling updates, ArgoCD (GitOps), Flagger (automated canary with metrics-based promotion), Argo Rollouts

The Reactive Manifesto (2014) defines four principles for building modern large-scale distributed systems. A system that embodies all four principles is called reactive.

The four traits:

1. Responsive: The system responds in a timely manner if at all possible. This is not just about speed — it's about providing consistent quality of service under normal and peak load.

• Defines and maintains upper response time bounds
• Degrades gracefully, never becoming unresponsive

2. Resilient: The system stays responsive in the face of failure. Failures are isolated and contained; recovery is delegated.

• Replication, containment, isolation, delegation
• Failures don't cascade; components fail independently
• Circuit breaker, bulkhead patterns

3. Elastic: The system stays responsive under varying workload. It can scale out and in as demand changes.

• No contention points or central bottlenecks
• Shard or replicate components
• Commodity hardware; cost-effective scaling

4. Message-Driven: The system relies on asynchronous message-passing for communication between components.

• Loose coupling, isolation, location transparency
• Backpressure: consumers signal capacity to producers (avoid overwhelming)
• Non-blocking I/O, event loops (Netty, Node.js, Akka)

Practical implications:

• Non-blocking I/O over thread-per-request (Vert.x, Spring WebFlux, Akka, Node.js)
• Backpressure with reactive streams (Project Reactor, RxJava)
• Event-driven architecture over synchronous calls
• Actor model for message-driven concurrency (Akka, Erlang OTP)

Not all systems need to be reactive. CRUD web apps with moderate traffic don't. Systems expecting millions of concurrent connections, real-time responsiveness, or bursty load do.

Multi-tenancy means a single software instance serves multiple customers (tenants) with isolation between them.

Isolation models (spectrum from cheap to expensive):

1. Shared Everything (Pool model):

• All tenants share same database, same tables, same application
• tenant_id column in every table for filtering
• ✅ Cheapest to operate, highest utilization
• ✅ Easy to update (one deployment)
• ❌ Noisy neighbor risk (one large tenant degrades others)
• ❌ Compliance risk (accidental data leakage)
• Use: Free/low-cost tiers

2. Shared Database, Separate Schema:

• One DB, but each tenant gets their own schema/namespace
• tenant_A.orders, tenant_B.orders
• ✅ Better isolation; per-tenant schema migrations possible
• ❌ Schema migrations must run per tenant (N times)
• Use: Mid-tier SaaS

3. Separate Database per Tenant:

• Each tenant has their own database (or database cluster)
• ✅ Strong isolation; independent backup/restore; compliance-friendly
• ✅ No cross-tenant data leakage possible
• ❌ Expensive; N databases to maintain; connection pooling complexity (PgBouncer per tenant)
• Use: Enterprise tiers, financial SaaS, healthcare

4. Separate Infrastructure:

• Dedicated compute, database, and network per tenant
• ✅ Maximum isolation and customization
• ❌ Very expensive; complex to manage
• Use: Government, banks, Fortune 500 enterprise

Tenant routing:

• Subdomain-based: acme.myapp.com → resolve tenant from subdomain
• JWT claim: tenant_id in auth token, validated at API gateway
• Row-level security: PostgreSQL RLS policies enforce tenant_id filtering at DB level

Rate limiting per tenant: Essential to prevent noisy neighbor — per-tenant quotas enforced at API gateway

Indexing is the single most impactful performance lever in relational databases. A missing index = full table scan; a proper index = O(log N) lookup.

How B-tree indexes work: Maintain a sorted structure. Binary search to find key = O(log N). Then pointer to actual row. Add overhead to every INSERT/UPDATE/DELETE (index must be updated).

Index types:

1. B-tree (default): Equality and range queries. WHERE id = 5, WHERE created_at BETWEEN ...
2. Hash index: Only equality. Faster for pure equality but no range support. Used internally in some join operations.
3. Composite index: Index on multiple columns. (user_id, created_at) — can use for queries filtering by user_id alone OR user_id + created_at. Column order matters!
4. Partial index: Index on subset of rows. CREATE INDEX ON orders(user_id) WHERE status = 'PENDING' — small, fast index for a common filter.
5. GIN index: For full-text search, array/JSONB column queries (PostgreSQL).
6. Covering index (Index-only scan): Index includes all columns needed by the query — no table access needed. CREATE INDEX ON orders(user_id) INCLUDE (amount, created_at).

Indexing principles:

• Index columns in WHERE, JOIN ON, and ORDER BY clauses
• High-cardinality columns benefit most from indexing (user_id: good; boolean: poor)
• Composite index column order: most selective column first, or match query's filter order
• Every index costs write performance — don't over-index
• Use EXPLAIN ANALYZE to verify index usage

Common pitfalls:

• Function on indexed column defeats index: WHERE LOWER(email) = ... won't use index on email — create functional index instead
• Implicit type cast defeats index: WHERE user_id = '123' (string vs int)
• Index on low-cardinality column (status ENUM) often not used — optimizer prefers seq scan

Requirements:

• Global leaderboard of top N players by score
• Near real-time updates (score changes reflect within seconds)
• User's own rank visible even if outside top N
• 10M users, scores updated 1M times/hour

Why not SQL?

• SELECT RANK() OVER (ORDER BY score DESC) FROM players WHERE user_id = X
• Full table scan on every score update — O(N log N) — 10M rows = too slow
• Not scalable for high-frequency updates

Redis Sorted Set — the standard solution:

ZADD leaderboard 1500 "user:123"  # Add/update user score
ZRANK leaderboard "user:123"     # Get user's rank (0-indexed)
ZREVRANKBY leaderboard "user:123" # Rank from top
ZREVRANGEBYSCORE leaderboard +inf -inf LIMIT 0 100 WITHSCORES  # Top 100

• ZADD: O(log N) — update score and position
• ZRANK: O(log N) — get rank of any user
• ZREVRANGE: O(log N + K) — get top K
• Redis Sorted Set uses skiplist for O(log N) operations across all operations

Architecture:

Score event → Kafka → Score processor → ZADD to Redis Sorted Set
Leaderboard API → Redis ZREVRANGE (top 100)
User rank API → Redis ZREVRANK (user's position)

Handling scale:

• Sharded leaderboards: Divide by score range. Top 1000 in one Redis, 1001-10000 in another.
• Periodic snapshots: PostgreSQL stores authoritative scores; Redis is the leaderboard cache rebuilt hourly.
• Segment leaderboards: Daily, weekly, all-time in separate sorted sets.

Redis Cluster consideration: Sorted sets must be on same node for transactions. Use single key for the global leaderboard; consistent hashing places it on one node.

Hexagonal Architecture (also called Ports and Adapters, coined by Alistair Cockburn) structures the application so that the core business logic is completely independent of external systems (databases, HTTP, message queues, third-party APIs).

The structure:

External World ←→ [Adapters] ←→ [Ports] ←→ [Application Core/Domain]

• Core (Hexagon): Pure business logic. No dependencies on frameworks, databases, or infrastructure. Can be tested in pure memory.
• Ports: Interfaces that the core exposes (input ports: use cases) or requires (output ports: repository interfaces)
• Adapters: Implementations of ports. HTTP controller → input port. JPA repository → output port. Kafka producer → output port.

Example:

Input adapters (drive the app):
- REST Controller → calls OrderService (input port)
- CLI → calls OrderService
- Kafka consumer → calls OrderService

Core:
- OrderService (business logic)
  - uses: OrderRepository (output port interface)
  - uses: PaymentGateway (output port interface)

Output adapters (driven by the app):
- PostgresOrderRepository → implements OrderRepository
- StripePaymentAdapter → implements PaymentGateway
- MockPaymentGateway (test) → implements PaymentGateway

Why it improves testability:

• Unit test core business logic with in-memory implementations (no DB, no network)
• Swap PostgreSQL for in-memory Map for tests
• Swap Stripe for mock payment gateway
• Integration tests only test adapters in isolation

Related patterns: Clean Architecture (Robert Martin), Onion Architecture — same principle, different visual metaphor. Domain-Driven Design naturally fits inside the hexagon.

Pessimistic Concurrency Control (PCC): Assumes conflicts will occur — prevents them by acquiring locks before accessing data.

Distributed implementations:

• Distributed lock (Redis Redlock): Acquire lock before critical section; release after
• Database row-level lock: SELECT FOR UPDATE in PostgreSQL — row locked until transaction commits
• 2-Phase Locking (2PL): Acquire all locks in growing phase; release in shrinking phase

Properties:

• ✅ Prevents all conflicts; correct under high contention
• ❌ Deadlock risk in distributed systems (cycles of lock dependencies)
• ❌ Lock holder crash → stuck locks until TTL expires (Redis) or transaction times out (DB)
• ❌ Throughput limited by lock contention
• Use: Inventory deduction, seat reservation, financial transfers

Optimistic Concurrency Control (OCC): Assumes conflicts are rare — detects conflicts at commit time.

Distributed implementations:

• Version/ETag: Client reads entity with version; writes include If-Match: version. Server rejects if version changed.
• DynamoDB ConditionExpression: condition: attribute(version) = :expected_version
• CAS (Compare-and-Swap): Atomic hardware instruction extended to distributed systems
• Redis WATCH: Watch a key; if it changes before EXEC, transaction aborts

Properties:

• ✅ No locks — maximum throughput when conflicts are rare
• ✅ No deadlocks possible
• ❌ Conflicts cause retries — CPU waste under high contention
• ❌ Complex retry logic in application
• Use: Profile updates, configuration changes, low-contention scenarios

Rule of thumb: High contention → pessimistic. Low contention → optimistic. Read-heavy, rare writes → optimistic always wins.

Requirements:

• Schedule millions of tasks: one-time, recurring (cron expressions)
• Exactly-once execution guarantee
• Sub-second scheduling accuracy
• Tasks can be arbitrary webhooks or functions
• Task history and failure retry

Core Challenges:

1. No single point of failure for the scheduler
2. Exactly-once execution — don't run the same task twice
3. Scale to millions of schedules
4. Fault tolerance — tasks must run even if scheduler nodes crash

Architecture:

[Scheduler API] → PostgreSQL (task definitions)
[Quartz Cluster / Custom] → Picks up due tasks
  → Kafka ('task-execution' topic)
    → Worker Pool → Executes task (HTTP call, Lambda invoke)
      → Update status in PostgreSQL
      → DLQ on failure → Retry queue

Task Storage (PostgreSQL):

CREATE TABLE scheduled_tasks (
  id UUID PRIMARY KEY,
  cron_expression VARCHAR(100),
  next_run_at TIMESTAMP,
  last_run_at TIMESTAMP,
  status VARCHAR(20),  -- PENDING, RUNNING, SUCCEEDED, FAILED
  payload JSONB,
  retry_count INT DEFAULT 0
);
CREATE INDEX idx_next_run ON scheduled_tasks(next_run_at, status);

Exactly-once using distributed lock:

Every 5 seconds:
1. SELECT tasks WHERE next_run_at <= NOW() AND status = 'PENDING' LIMIT 100
2. For each task: acquire Redis distributed lock (SETNX task_id)
3. If lock acquired: push to Kafka, update status to 'RUNNING'
4. Worker executes; updates status to SUCCEEDED or FAILED
5. Calculate next_run_at from cron expression

Leader election: Only one scheduler node polls at a time; others are hot standbys (Zookeeper or etcd)

Tools: Apache Airflow (DAG workflows), Quartz Scheduler (Java), Temporal (durable execution), Kubernetes CronJobs

The Write-Ahead Log (WAL) is a fundamental database durability mechanism: all changes are first written to an append-only log file before being applied to the actual data files.

The core principle: The log record must be written to durable storage before the data page is modified.

Why it's necessary: If the database crashes mid-operation, the in-memory changes are lost. Without WAL, partial writes could leave the database in a corrupt state.

How recovery works:

1. On startup after crash, DB reads the WAL
2. Finds the last checkpoint (last known consistent state)
3. REDO: Replays committed transactions from the WAL that weren't yet written to data files
4. UNDO: Rolls back uncommitted transactions using WAL undo records
5. Database is in a consistent state again

WAL enables multiple features:

1. Durability (D in ACID): fsync() after WAL write = guaranteed durability
2. Streaming replication: Send WAL stream to replicas → they replay and stay in sync (PostgreSQL, MySQL binlog)
3. Point-in-time recovery (PITR): Replay WAL from a base backup to any point in time
4. CDC: Debezium reads WAL to capture changes for event streaming

Performance optimization:

• synchronous_commit = off (PostgreSQL): Acknowledge commit before WAL fsync. Risk: last few transactions may be lost on crash. Gain: much lower latency.
• WAL buffers: batch WAL writes to reduce fsync frequency
• Group commit: multiple transactions share one fsync call

A service mesh is a dedicated infrastructure layer for handling service-to-service (east-west) communication within a microservices architecture.

How it works: A lightweight sidecar proxy (Envoy) is injected alongside every service pod. All network traffic flows through the sidecar — services communicate with each other through the mesh without being aware of it.

Service Mesh capabilities:

• Mutual TLS (mTLS): Automatic encryption and authentication between all services
• Load balancing: Intelligent client-side load balancing at L7 with multiple algorithms
• Circuit breaking: Automatically detect and isolate failing services
• Distributed tracing: Inject trace headers automatically; no code changes needed
• Traffic management: Canary deployments, A/B testing, traffic mirroring, fault injection
• Observability: Metrics, traces, and logs for every service-to-service call
• Retry policies: Automatic retries with backoff configured via YAML

API Gateway vs Service Mesh:

Popular service meshes: Istio (most feature-rich), Linkerd (lightweight, easier), Consul Connect, AWS App Mesh

Trade-off: Adds ~5-10ms latency per hop; significant operational complexity; overkill for small numbers of services

Apache Kafka achieves extraordinary throughput (millions of messages/second) through several layered optimizations:

1. Sequential Disk I/O: Kafka writes to append-only log files on disk. Sequential writes are 100× faster than random writes (even vs SSD). Log files grow in one direction — no fragmentation, no seek time.

2. Zero-Copy (sendfile syscall): Traditional path: Disk → OS buffer → Application buffer → Socket buffer → Network Kafka path: Disk → OS buffer → Network (via sendfile() — kernel copies directly) Elimination of 2 memory copies dramatically reduces CPU and memory usage.

3. Batching:

• Producers batch messages and send in bulk (configurable linger.ms and batch.size)
• Consumers fetch large batches per poll
• Compression applied per batch (Snappy, LZ4, Zstd) — better compression ratio on batches than individual messages

4. Partitioning:

• Topics divided into partitions; each partition is an independent log
• Multiple producers write to different partitions in parallel
• Multiple consumers in a group each read from exclusive partitions in parallel
• Linear throughput scaling: double partitions ≈ double throughput

5. Page Cache (OS): Kafka doesn't maintain its own cache — relies on OS page cache. Since reads are sequential, OS prefetches efficiently. Recent messages (most commonly read) stay in memory naturally.

6. Replication pipeline: Leader writes to its log; followers fetch in parallel. Replication is itself a sequential log read — same I/O efficiency benefits.

Benchmark: A single Kafka broker can sustain 100MB/s+ writes; a 3-broker cluster with 6 partitions easily handles 500MB/s.

Requirements:

• Globally unique IDs across all services and machines
• Sortable by time (chronologically ordered)
• High throughput (100K IDs/sec per node)
• No central coordinator (no SPOF)

Why not use UUIDs?

• UUIDs are random → poor database index performance (random page splits in B-trees)
• Not sortable by time
• 128 bits (wasteful)

Twitter Snowflake ID (64 bits):

[1 bit: sign] [41 bits: timestamp] [10 bits: machine ID] [12 bits: sequence]

• 41-bit timestamp: milliseconds since custom epoch (Jan 1, 2010). Supports 69 years.
• 10-bit machine ID: Up to 1024 unique machines/workers (configurable: 5 bits datacenter + 5 bits machine)
• 12-bit sequence: 4096 IDs per millisecond per machine. If exhausted, wait until next millisecond.

Properties:

• ✅ 64-bit integer — fits in BIGINT, fast indexing
• ✅ Time-sortable — newer IDs are lexicographically larger
• ✅ Decentralized — each machine generates independently
• ✅ 4096 IDs/ms/machine × 1024 machines = 4B IDs/ms total

Machine ID assignment:

• Assigned at startup via Zookeeper or etcd
• Or: use datacenter ID + host ID from config

Clock skew problem:

• If system clock goes backward (NTP sync) → duplicate IDs
• Solution: If current_time < last_timestamp → wait until clock catches up
• Use monotonic clock instead of wall clock when possible

Alternatives: ULID (URL-safe Snowflake variant), UUID v7 (time-ordered UUID, RFC 9562), database sequences (single SPOF)

This is an expanded deep-dive on implementing Saga with both patterns in production.

Saga with Choreography — Order Service example:

1. OrderService creates order (PENDING) → publishes OrderCreated event
2. InventoryService receives OrderCreated → reserves items → publishes InventoryReserved
3. PaymentService receives InventoryReserved → charges card → publishes PaymentCharged  
4. ShippingService receives PaymentCharged → creates shipment → publishes ShipmentCreated
5. OrderService receives ShipmentCreated → updates order to CONFIRMED

Rollback (if Payment fails):
PaymentService → publishes PaymentFailed
InventoryService receives PaymentFailed → releases reservation → publishes InventoryReleased
OrderService receives InventoryReleased → marks order CANCELLED

Saga with Orchestration — Temporal example:

@workflow.defn
class OrderWorkflow:
    @workflow.run
    async def run(self, order: Order):
        # Each activity has retry policy and timeout
        await workflow.execute_activity(reserve_inventory, order)
        
        try:
            await workflow.execute_activity(charge_payment, order)
        except Exception:
            await workflow.execute_activity(release_inventory, order)
            raise
            
        await workflow.execute_activity(create_shipment, order)

Idempotency in Sagas: Each step must be idempotent — if a compensating transaction runs due to network issue and same message arrives twice, the result must be the same. Use idempotency keys.

Saga state tracking:

• Choreography: Reconstruct saga state from events in Kafka/event store
• Orchestration: Orchestrator persists its state durably (Temporal stores workflow state in its DB)

Testing Sagas: Inject failures at each step; verify compensating transactions run correctly; validate final state consistency

Requirements:

• 1-on-1 and group chat (up to 500 members)
• Message delivery: real-time, ordered, at-least-once
• Online/offline presence
• Message history, search
• 500M users, 100B messages/day

Connection Management: Long-lived WebSocket connections between clients and Chat Servers. Users connect to geographically closest server.

• 500M users × 1 WebSocket = 500M connections
• ~100K connections per server → ~5,000 servers

Message Flow (1-on-1):

User A → [WebSocket] → Chat Server A
  → Kafka ('messages' topic, partition by conversation_id)
    → Message Processor
      → Store in Cassandra (partitioned by conversation_id + timestamp)
      → Check User B online? 
        → Yes: Push to User B's Chat Server via Redis pub/sub or service mesh
        → No: Store in offline message queue; push notification via APNs/FCM

Message Storage (Cassandra):

CREATE TABLE messages (
  conversation_id UUID,
  message_id TIMEUUID,  -- time-ordered unique ID (for pagination)
  sender_id UUID,
  content TEXT,
  created_at TIMESTAMP,
  PRIMARY KEY (conversation_id, message_id)
) WITH CLUSTERING ORDER BY (message_id DESC);

Presence System:

• Client sends heartbeat every 5 seconds
• Redis stores user:{id}:last_seen with 10s TTL
• Fanout presence updates to friends via Kafka

Group Chat:

• Message stored once, fanned out to all members
• For large groups: fan-out on read vs fan-out on write trade-off

Message ordering:

• Use TIMEUUID (Cassandra) or Snowflake IDs for globally ordered IDs
• Client-side sequence numbers for gap detection

The Outbox Pattern solves the dual-write problem in microservices: how to atomically update a database AND publish an event/message to a broker — without distributed transactions.

The problem:

// ❌ This is NOT atomic — what if step 2 fails?
1. UPDATE database (order created)
2. PUBLISH message to Kafka (order.created event)
// If Kafka publish fails → DB updated but event never sent → data inconsistency

Outbox Pattern solution:

// ✅ Single atomic DB transaction:
1. INSERT into orders table
2. INSERT into outbox table (same transaction)
   {event_type: 'order.created', payload: {...}, status: 'PENDING'}
// Both succeed or both fail — atomically

// Separate background process (Outbox Relay/Polling Publisher):
3. Poll outbox table for PENDING records
4. Publish to Kafka
5. Mark outbox record as PUBLISHED

Transactional Outbox implementation options:

1. Polling publisher: Background job queries WHERE status = 'PENDING'. Simple but adds DB load and has latency.

2. Transaction log tailing (CDC): Tools like Debezium tail the database's WAL/binlog. Events captured directly from DB changes → Kafka. Near real-time, no polling overhead. Production gold standard.

Idempotent consumers: Since outbox guarantees at-least-once delivery, consumers must handle duplicates using idempotency keys.

Tools: Debezium (CDC), Kafka Connect, Eventuate Tram framework

Used by: All serious event-driven microservices architectures (Amazon, Uber, Netflix)

Change Data Capture (CDC) is a pattern that captures every change (INSERT, UPDATE, DELETE) made to a database and makes those changes available as a stream of events — without modifying the application.

How it works: Databases maintain a transaction log (WAL in PostgreSQL, binlog in MySQL, redo log in Oracle) for recovery purposes. CDC tools tap into this log to capture changes.

Debezium (most popular CDC tool):

1. Connects to database as a replication client
2. Reads WAL/binlog changes in real-time
3. Publishes each change as a structured JSON event to Kafka
4. Event contains: before/after state, operation type, timestamp, transaction ID

CDC use cases:

1. Outbox pattern relay: Capture outbox table inserts → Kafka without polling

2. Cache invalidation: When DB row changes → invalidate/update Redis cache automatically

3. Search index sync: User profile updated in PostgreSQL → Elasticsearch updated via CDC

4. Data lake/warehouse sync: Stream operational DB changes to BigQuery/Snowflake in near real-time

5. Microservices migration: Sync old monolith DB to new service DB during strangler fig migration

6. Audit logging: Capture every change to sensitive records for compliance

Supported databases: PostgreSQL (pgoutput plugin), MySQL (binlog), MongoDB (change streams), SQL Server (CDC feature), Oracle (LogMiner)

Considerations: Replication slot management (PostgreSQL WAL can grow if Debezium falls behind), schema changes require careful handling

Redis Cluster provides horizontal scaling and high availability for Redis, distributing data across multiple nodes.

Hash Slots:

• Redis Cluster divides the keyspace into 16,384 hash slots
• Each master node is responsible for a range of slots: Node A → 0-5460, Node B → 5461-10922, Node C → 10923-16383
• Key assignment: slot = CRC16(key) % 16384

Replication:

• Each master node has one or more replica nodes
• Replicas serve reads (with possible staleness) and take over if master fails
• Minimum production setup: 3 masters + 3 replicas

Failure Detection & Failover:

• Nodes communicate via gossip protocol
• If a master doesn't respond, other masters mark it as PFAIL (probable fail)
• When majority agree → FAIL; a replica promotes itself to master
• Cluster remains available as long as at least one node per shard is alive

Resharding:

• Add/remove nodes: slots migrate from one node to another
• Keys move live using MIGRATE command — zero-downtime

Limitations:

• Multi-key operations only work if keys are on the same slot → use hash tags: {user:123}:sessions and {user:123}:profile always go to same slot
• Transactions (MULTI/EXEC) only work within a single slot

Cluster vs Sentinel:

• Sentinel: High availability for single master without sharding
• Cluster: Sharding + HA; needed when data exceeds single node capacity

Two-Phase Commit (2PC) is a distributed consensus protocol that coordinates all nodes in a distributed transaction to either all commit or all abort.

Phase 1 — Prepare (Voting):

• Coordinator sends PREPARE to all participants
• Each participant writes undo/redo logs, acquires locks, and votes YES (can commit) or NO (cannot commit)
• If any participant votes NO → coordinator sends ABORT to all

Phase 2 — Commit/Abort:

• If all voted YES → coordinator sends COMMIT to all participants
• All participants make changes permanent and release locks
• If any voted NO → coordinator sends ABORT; participants rollback

Limitations:

1. Blocking protocol: If the coordinator crashes after Phase 1 (before sending commit), participants are left holding locks indefinitely — the system is stuck ('in-doubt' transaction)

2. Single point of failure: Coordinator failure = system halt

3. Performance: Two round trips; participants hold locks throughout; high latency

4. Network partition: Partition during Phase 2 means some nodes committed, others didn't — inconsistency

3PC (Three-Phase Commit): Adds a PRE-COMMIT phase to avoid blocking, but doesn't handle network partitions and is rarely used in practice.

Modern alternatives:

• Saga pattern: Eventual consistency with compensating transactions (no 2PC)
• Consensus algorithms (Raft/Paxos): Used internally by distributed databases
• Google Spanner TrueTime: Hardware-level clock uncertainty bounds to achieve external consistency

Raft is a consensus algorithm designed to be more understandable than Paxos. It ensures distributed systems agree on a single value or sequence of values even when nodes fail.

Node Roles:

• Leader: Handles all client requests; replicates log to followers; one at a time
• Follower: Passive; replicates from leader; votes in elections
• Candidate: Follower that times out; initiates election

Leader Election:

• Followers wait for heartbeats from the leader (randomized timeout: 150-300ms)
• If no heartbeat → become Candidate, increment term, vote for self, send RequestVote RPCs
• Majority vote → become Leader
• Randomized timeouts prevent split votes

Log Replication:

1. Client sends command to Leader
2. Leader appends to its log
3. Leader sends AppendEntries RPC to all Followers
4. Followers append to their logs
5. When majority acknowledge → Leader commits entry
6. Leader applies to state machine, responds to client
7. Leader informs Followers of commit in next heartbeat

Safety guarantees:

• Only nodes with the most up-to-date log can be elected leader (election restriction)
• Committed entries are never lost
• All nodes apply log entries in the same order

Used in: etcd (Kubernetes), CockroachDB, TiKV, Consul, InfluxDB

vs Paxos: Raft is equivalent in power but decomposed into understandable subproblems (leader election, log replication, membership changes)

B-Tree (Balanced Tree): Used by: PostgreSQL, MySQL InnoDB, SQLite

• Data stored in sorted, balanced tree on disk
• In-place updates: find the page, update it
• Reads: O(log n) — traverse tree
• Writes: Random I/O — must find and update the correct page on disk; WAL written for durability
• ✅ Fast reads, good for random access patterns
• ❌ Write amplification: WAL + actual page update; fragmentation over time (VACUUM)
• Great for: OLTP workloads with mix of reads and writes

LSM-Tree (Log-Structured Merge-Tree): Used by: RocksDB, Cassandra, LevelDB, HBase, InfluxDB

• Writes go to in-memory MemTable (sorted structure)
• When MemTable is full → flush to immutable SSTable (Sorted String Table) on disk
• SSTables are periodically compacted (merged and sorted) in the background
• Reads: Must check MemTable + multiple SSTables → use Bloom filters to skip irrelevant SSTables

Comparison:

Bloom Filters in LSM: Probabilistic data structure that quickly tells you 'this key is DEFINITELY NOT in this SSTable' — avoids unnecessary disk reads. Small false positive rate acceptable.

Requirements:

• 100M users; support push, email, SMS channels
• User preferences: opted-in channels, quiet hours, language
• Reliability: must not lose notifications; at-least-once delivery
• Throughput: handle 10M notifications/hour (burst)

High-Level Architecture:

API/Event Sources → Notification Service → Channel Workers
                                        ↓
                              [Kafka Topics per channel]
                              push-notifications-topic
                              email-notifications-topic  
                              sms-notifications-topic
                                        ↓
                    Push Worker  Email Worker  SMS Worker
                         ↓           ↓            ↓
                    FCM/APNs    SendGrid/SES   Twilio

Key Components:

1. Notification Service: Validates request, checks user preferences/opt-outs, enriches with user data, publishes to appropriate Kafka topics

2. User Preference Store (Redis): User → {email_enabled, push_enabled, sms_enabled, quiet_hours_start, quiet_hours_end, timezone}

3. Channel Workers: Kafka consumers that batch messages and call third-party providers (FCM, APNs, SendGrid, Twilio)

4. Retry/DLQ: Failed deliveries go to Dead Letter Queue; retry with exponential backoff (3 attempts); alert on repeated failures

5. Priority Queues: Separate Kafka topics for CRITICAL (OTP, payment alerts) vs MARKETING notifications

Preventing duplicate sends:

• Idempotency key per notification
• Redis-based dedup within a 24-hour window

Monitoring: Delivery rate, failure rate per provider, p99 end-to-end latency

A rate limiter controls how many requests a client can make in a given time window to prevent abuse and ensure fair usage.

Algorithms:

1. Fixed Window Counter:

   • Increment counter per user per time window (e.g., 100 req/min)
   • Reset at window boundary
   • ❌ Boundary burst: 100 at 12:00:59 + 100 at 12:01:00 = 200 in 2 seconds

2. Sliding Window Log:

   • Store timestamp of every request in a sorted set
   • Count requests in last 60 seconds
   • ✅ Precise, no boundary burst
   • ❌ Memory-heavy for high-traffic users

3. Sliding Window Counter (hybrid):

   • Interpolate between current and previous window counters
   • Rate = prev_count × (1 - elapsed/window) + curr_count
   • ✅ Memory efficient, accurate enough
   • Used by Cloudflare

4. Token Bucket:

   • Bucket holds N tokens. Each request consumes 1 token. Tokens replenish at fixed rate.
   • ✅ Allows bursting (drain full bucket quickly), then throttles
   • ✅ Smooth rate limiting
   • Used by AWS API Gateway

5. Leaky Bucket:

   • Requests enter queue; processed at fixed output rate
   • ✅ Smooth output, good for traffic shaping
   • ❌ Queue can fill; requests dropped or queued

Distributed Rate Limiting with Redis:

local current = redis.call('INCR', key)
if current == 1 then
  redis.call('EXPIRE', key, window_seconds)
end
if current > limit then
  return 0  -- rejected
end
return 1  -- allowed

Architecture at scale: Redis cluster for state, Lua scripts for atomic operations, Sliding window counter per user_id or IP, X-RateLimit-* headers in response.

A Saga is a pattern for managing long-lived distributed transactions across multiple microservices without using a 2-phase commit (2PC).

Problem: In microservices, a business transaction (e.g., e-commerce order) spans multiple services: Order, Inventory, Payment, Shipping. Each has its own database. ACID transactions across service boundaries require 2PC, which is slow and creates distributed locks.

Saga solution: Break the distributed transaction into a sequence of local transactions, each with a corresponding compensating transaction for rollback.

Two Saga implementations:

1. Choreography-based:

   • Each service publishes events; next service listens and acts
   • No central coordinator
   • ✅ Loose coupling, simple
   • ❌ Hard to track overall state; 'distributed spaghetti'
   • Flow: Order created → Inventory reserved → Payment charged → Order confirmed

2. Orchestration-based:

   • A central Saga Orchestrator coordinates each step
   • Knows the full workflow; sends commands to each service
   • ✅ Centralized visibility, easier to debug
   • ❌ Orchestrator can become a bottleneck
   • Tools: AWS Step Functions, Temporal, Conductor

Compensating transactions example:

• Step 1: Reserve inventory → Compensate: Release inventory
• Step 2: Charge payment → Compensate: Issue refund
• Step 3: Create shipment → Compensate: Cancel shipment

If Step 3 fails: cancel shipment → refund → release inventory (reverse order)

Saga guarantees: Eventually consistent, not ACID. Intermediate states are visible during execution.

Traditional CRUD: Stores the current state of an entity. When state changes, the old value is overwritten. History is lost.

Event Sourcing: Instead of storing current state, store a log of all events that led to that state. Current state is derived by replaying events.

Example — Bank account:

• CRUD: accounts table, balance = 1500. Update balance on each transaction.
• Event Sourcing: Events log:
  • AccountOpened(balance=0)
  • MoneyDeposited(amount=2000)
  • MoneyWithdrawn(amount=500)
  • Current balance = replay: 0 + 2000 - 500 = 1500

Advantages:

• Complete audit log — every change recorded, mandatory for finance/compliance
• Temporal queries — 'What was the balance on Jan 15?' — just replay up to that date
• Event replay — rebuild any read model from scratch; migrate to new schema
• Debugging — reproduce any historical state exactly
• CQRS-friendly — events feed multiple read-optimized projections

Disadvantages:

• Query complexity — querying current state requires aggregation
• Event store growth — must snapshot periodically to avoid replaying from day 1
• Schema evolution — changing event structure is hard; old events must still be processable
• Learning curve — fundamentally different mental model

Commonly paired with: CQRS (Command Query Responsibility Segregation), Kafka as the event log, Axon Framework, EventStoreDB

CQRS (Command Query Responsibility Segregation) separates the model for writing data (Commands) from the model for reading data (Queries).

Traditional model: Single model serves both reads and writes. Optimizing for one often degrades the other.

CQRS model:

• Command side: Receives commands (CreateOrder, CancelOrder), validates, updates the write model (event store or DB), emits events
• Query side: Listens to events, builds denormalized read models (projections) optimized for specific queries

How it complements Event Sourcing:

1. Event Sourcing generates events as the write model
2. Those events are projected into multiple read-optimized stores:
   • PostgreSQL for reporting queries
   • Elasticsearch for full-text search
   • Redis for real-time dashboards
   • MongoDB for flexible document queries

Example — E-commerce:

• Command: PlaceOrder → write to order event store
• Projection 1: OrderSummary table in PostgreSQL for 'My Orders' page
• Projection 2: InventoryView in Redis for real-time stock levels
• Projection 3: Elasticsearch index for order search

Benefits:

• Read models independently optimized and scaled
• Read model can be rebuilt anytime from events
• Reads and writes scale independently

Complexity costs: Eventual consistency between write and read models; more moving parts; not justified for simple CRUD apps

Requirements:

• 300M users; each follows up to 5,000 accounts
• Feed: latest 1,000 posts from followed accounts
• Post latency: appear in followers' feeds within 5 seconds of posting
• Read-heavy: 100 reads per write

Two approaches:

1. Fan-out on Write (Push model): When user A posts → immediately write post to all followers' feed caches.

Post created → Kafka 'post-events' → FanOut Service
  → For each of A's followers:
    LPUSH feed:{follower_id} post_id  (Redis list, 1000 items max)
    LTRIM feed:{follower_id} 0 999

• ✅ Read is O(1): just read from Redis list
• ✅ Real-time feed updates
• ❌ Celebrity problem: Justin Bieber has 100M followers → 100M Redis writes per post
• ❌ Users with many followers cause write spikes

2. Fan-out on Read (Pull model): When user opens feed → query posts from all followed accounts in real-time.

Feed request → Fetch user's follow list (cached)
→ SELECT * FROM posts WHERE user_id IN (...) ORDER BY created_at DESC LIMIT 100

• ✅ No write fan-out; posting is fast
• ❌ Read is expensive: query across thousands of followed accounts
• ❌ High read latency

3. Hybrid (Twitter's actual approach):

• Regular users (< 10M followers): fan-out on write
• Celebrity accounts (> threshold): fan-out on read only when their followers request feed
• Merge: Redis cached feed + real-time celebrity posts at read time

Storage:

• Post data: Cassandra (write-heavy, time-series, scales horizontally)
• Feed cache: Redis sorted sets (post_id scored by timestamp)
• User graph: Graph DB or Cassandra with adjacency list

Ranking:

• Chronological feed: simplest (Redis sorted set with timestamp as score)
• Algorithmic feed: ML ranking based on engagement signals — much more complex infrastructure

Geo-replication replicates data across multiple geographically separated data centers or cloud regions.

Goals:

• Reduce latency for global users (serve from nearest region)
• Survive regional outages (DR/HA)
• Comply with data sovereignty laws (data stays in EU)

Challenges:

• Speed of light: US East ↔ EU ≈ 70ms. Can't have strong consistency without paying this latency penalty.
• Network partitions between regions are more frequent than within a region

Geo-routing strategies:

1. Geographically partitioned data (Sharding by region):

• EU users → EU region, US users → US region
• Data never crosses regions (compliance-friendly)
• ✅ Low latency for local users, compliance
• ❌ Global queries span regions; users can't move regions easily

2. Global leader + regional replicas:

• All writes go to global primary (e.g., US-East)
• Regional replicas handle local reads (eventual consistency)
• ✅ Simple consistency model
• ❌ Write latency for non-primary regions; global leader is SPOF

3. Multi-leader (active-active):

• Each region has its own leader that accepts writes
• Regions replicate to each other asynchronously
• ✅ Low write and read latency everywhere
• ❌ Write conflicts; complex resolution needed
• Examples: CockroachDB, Spanner, Cassandra multi-DC

Google Spanner's approach:

• External consistency (linearizability) globally using TrueTime API
• GPS + atomic clocks give bounded clock uncertainty (~7ms)
• 2-phase locking with TrueTime timestamps ensures global order

CDN + Edge: Static content served from 200+ edge PoPs globally with <20ms latency anywhere

A vector clock is a logical clock mechanism that tracks causality in distributed systems — determining whether events are causally related or concurrent.

Structure: Each node maintains a vector of counters, one per node in the system.

• 3 nodes: [Node_A_counter, Node_B_counter, Node_C_counter]
• Node A's vector clock: [2, 1, 0] means 'I've processed 2 events, I know node B has processed 1, and node C hasn't done anything I know about'

Rules:

1. Before sending a message: increment own counter
2. On receiving a message: merged[i] = max(local[i], received[i]) for all i; then increment own counter

Comparing vector clocks:

• VC1 < VC2 (VC1 happened before VC2): all VC1 entries ≤ corresponding VC2 entries
• VC1 concurrent with VC2: neither is < the other

DynamoDB conflict resolution:

• Amazon Dynamo paper uses vector clocks to track versions of a value
• On write conflict (two concurrent writes): both versions preserved with their vector clocks
• Application or last-write-wins policy reconciles conflicts on read
• DynamoDB simplified to use version numbers (scalability tradeoff)

Alternative — CRDTs (Conflict-free Replicated Data Types): Data structures designed so concurrent operations can ALWAYS be merged without conflicts:

• G-Counter: Only increment; merge = max. Used for: like counts, view counts
• LWW-Register: Last-write-wins register. Used for: simple key-value updates
• OR-Set: Add/remove set where adds always win concurrent removes. Used for: shopping carts
• Used by: Riak, Redis (some data types), collaborative editing (like Figma, Google Docs)

The gossip protocol (epidemic protocol) is a decentralized communication protocol where nodes periodically exchange information with random peers — like how gossip spreads through a social network.

Properties:

• Decentralized: No central coordinator
• Probabilistic: Information spreads exponentially (each round doubles coverage)
• Resilient: Works even if many nodes are down or partitioned
• Eventually consistent: All nodes converge on the same state within logarithmic rounds

Gossip for failure detection:

1. Each node maintains a membership list: {node_id, heartbeat_counter, last_updated}
2. Every T seconds, each node:
   • Increments its own heartbeat counter
   • Selects K random peers
   • Sends its membership list to those peers
3. Receiving node merges lists: heartbeat = max(own, received) per entry
4. If a node's heartbeat hasn't been updated in T_fail seconds → marked as suspicious
5. If still no update after T_cleanup seconds → marked as failed

The math: N nodes, each gossips to K peers per round. After O(log N) rounds, all nodes have the update. For 1000 nodes, ~10 rounds.

Real-world usage:

• Cassandra: Gossip for membership, failure detection, and schema propagation
• Redis Cluster: Gossip for cluster state and failure detection
• Amazon DynamoDB: Gossip-based ring membership
• Consul: Gossip-based agent health checking (SWIM protocol)
• Kubernetes: Not gossip — uses etcd + watch mechanism instead

SWIM Protocol (Scalable Weakly-consistent Infection-style process group Membership): More sophisticated gossip with piggybacked failure detection probes — used by Consul and Memberlist library

Requirements:

• Store billions of files (objects) up to several TB each
• Durability: 99.999999999% (11 nines) — never lose data
• Availability: 99.99%
• Global access with low latency

Architecture (S3-like object store):

Metadata layer:

• Stores: bucket/key → {storage locations, size, checksum, metadata}
• Sharded across many nodes (consistent hashing on bucket+key)
• Must be durable and consistent (Raft-based or Paxos)

Storage layer:

• Objects split into chunks (e.g., 64MB blocks)
• Each chunk stored on multiple data nodes (3× replication)
• Data nodes organized in fault domains (rack-aware placement)

Write path:

Client → Upload API → Metadata service (validates, assigns chunk locations)
  → Client streams chunks directly to data nodes
  → Replication: data node replicates to 2 more nodes (pipeline replication)
  → On 3 copies ACKed: metadata committed → success returned

Read path:

Client → GET request with bucket/key → Metadata service returns chunk locations
  → Client fetches chunks from nearest data nodes
  → Reassembles object

Durability techniques:

• 3× replication (or Erasure Coding for cost efficiency: 6+3 RS code = 12 disks for 9 disks of data, can lose any 3)
• Checksums on every chunk → detect silent bit rot
• Periodic scrubbing: background process reads and verifies all chunks
• Cross-region replication for geo-redundancy

HDFS differences:

• NameNode (centralized metadata) + DataNodes
• Block-based, optimized for large sequential reads (MapReduce/Spark)
• HDFS NameNode is a historical SPOF (mitigated by HDFS HA with Zookeeper)

Requirements:

• 200M subscribers, 500M streams/day
• Video encoding, storage, delivery
• <2 second startup time; minimal buffering
• Multiple resolutions, devices, codecs

Content Ingestion Pipeline:

Studio Upload → S3 Raw Storage
  → Transcoding Service (AWS Elemental MediaConvert / custom)
    → Multiple resolutions: 4K, 1080p, 720p, 480p, 360p
    → Multiple codecs: H.264, H.265/HEVC, AV1 (30% better compression)
    → Adaptive bitrate segments (HLS/DASH, ~2-10 second chunks)
    → Stored in S3

Content Delivery:

• Netflix uses its own CDN: Open Connect Appliances (OCA)
• OCAs deployed inside ISP networks (last-mile optimization)
• During off-peak hours, Netflix proactively pushes popular content to OCAs
• 90%+ of traffic served from ISP-embedded OCAs

Adaptive Bitrate Streaming (ABR):

• Player monitors download speed and buffer level
• Switches quality levels dynamically: good connection → 4K, poor → 360p
• HLS (Apple) / DASH (others): Video split into small segments; player fetches next segment

Microservices at Netflix:

• Playback API, Content API, Recommendation, Auth, Billing — all separate
• All ride on Netflix OSS stack: Eureka (discovery), Zuul (gateway), Hystrix (circuit breaker), Ribbon (load balancer)

Recommendation System:

• Collaborative filtering + Deep learning
• A/B testing at massive scale (Experimentation Platform)
• Personalized thumbnails (different images shown to different users for same content)

Chaos Engineering: Netflix pioneered Chaos Monkey; regularly kills production instances to validate resilience

Requirements:

• Sub-millisecond get/put operations
• Horizontal scalability to petabytes
• High availability (99.999%)
• Tunable consistency (eventual to strong)

Core Architecture:

Data Distribution: Consistent hashing with virtual nodes. Keys distributed across N nodes. Each physical node has 150 vnodes on the ring.

Replication: Each key is replicated to N=3 nodes (coordinator + next 2 on ring). Replication factor is configurable.

Read/Write Quorum:

• W = nodes that must acknowledge a write
• R = nodes that must respond to a read
• N = total replicas
• For strong consistency: W + R > N (e.g., W=2, R=2, N=3)
• For eventual consistency: W=1, R=1 (fastest but possibly stale)

Write Path:

1. Client sends write to any node (coordinator)
2. Coordinator uses consistent hashing to find home nodes
3. Coordinator forwards write to all N replicas
4. Waits for W acknowledgments → success
5. Remaining replicas update asynchronously

Read Path:

1. Client sends read to any node
2. Coordinator requests from R replicas
3. Returns value with latest timestamp (LWW conflict resolution)
4. If replicas disagree → read repair in background

Anti-Entropy: Merkle trees used to detect and sync diverged data between replicas without scanning all data.

Gossip Protocol: Nodes exchange state information with random peers periodically — failure detection and membership changes propagate within seconds.

Storage Engine: LSM-tree (Log-Structured Merge-tree) for high write throughput: writes go to in-memory memtable → flushed to immutable SSTable files → periodic compaction