System Design — Cheat Sheet

Vertical scaling (scale up): Add more resources (CPU, RAM) to an existing machine. Simple — no application changes needed. Limited by hardware ceiling, has a single point of failure, and causes downtime during upgrades. Horizontal scaling (scale out): Add more machines and distribute load across them. Requires load balancers, stateless services, and distributed data. More complex but provides near-unlimited capacity and no single point of failure. Modern systems prefer horizontal scaling with stateless microservices. Vertical scaling is often used for databases where horizontal scaling requires sharding.

CAP theorem states that a distributed system can guarantee at most two of three properties: • Consistency (C): Every read receives the most recent write or an error • Availability (A): Every request receives a response (not necessarily the latest data) • Partition Tolerance (P): The system continues operating despite network partitions Since network partitions are unavoidable in distributed systems, you must choose between CP or AP: • CP systems (HBase, Zookeeper, etcd): Sacrifice availability during partitions. Return errors rather than stale data. • AP systems (Cassandra, CouchDB, DynamoDB): Sacrifice consistency during partitions. Return potentially stale data. Many modern databases offer tunable consistency, allowing you to choose per-operation.

Consistent hashing maps both keys and nodes to positions on a virtual ring (hash space). A key is assigned to the first node clockwise from its position. Problem it solves: With simple modulo hashing (key % n), adding or removing a node remaps almost all keys — causing a cache stampede or massive data movement. With consistent hashing, only K/n keys are remapped when a node is added/removed (K = keys, n = nodes). Virtual nodes: Each physical node gets multiple positions on the ring, improving load balance. Adding a node reduces the responsibility of its neighbors. Used in: Amazon DynamoDB, Apache Cassandra, Memcached (Ketama), Redis Cluster, load balancers.

Sharding splits data across multiple database nodes (shards), each responsible for a subset of the data. Enables horizontal scaling of databases. Sharding strategies: • Range-based: Shard by key range (users A–M on shard 1, N–Z on shard 2). Simple but causes hot spots with popular ranges. • Hash-based: Hash the shard key and distribute evenly. Avoids hot spots but makes range queries expensive. • Directory-based: A lookup table maps keys to shards. Flexible but adds latency and a central SPOF. Challenges: Cross-shard joins require application-level aggregation. Cross-shard transactions are complex (2PC or Saga). Re-sharding is painful. Auto-increment IDs must be globally unique (use UUID or Snowflake IDs).

Cache invalidation is one of the hardest problems in distributed systems. Common strategies: • Cache-aside (Lazy loading): Application reads from cache; on miss, reads from DB and populates cache. Risk: stale data until TTL expires. • Write-through: Write to cache and DB simultaneously. Cache always consistent but adds write latency. • Write-behind (Write-back): Write to cache only; flush to DB asynchronously. Fast writes but risk of data loss. • Write-around: Write directly to DB, bypass cache. Use for data written once and rarely read. • TTL expiration: Simple but may serve stale data until expiry. • Event-driven invalidation: Publish DB change events; cache consumers invalidate entries. Consistent but complex.

Functional requirements: Generate short URL from long URL, redirect to original, track click analytics. Core design: • Short code generation: Use a counter + base62 encoding, or hash (MD5/SHA256) the long URL and take first 7 characters (collision risk needs handling). Or a random generator with uniqueness check. • Storage: Map shortCode → {longUrl, userId, createdAt, expiresAt}. Use a fast KV store (Redis) as cache, backed by a relational or wide-column DB. • Redirect: 301 (permanent, browsers cache — reduces load) vs 302 (temporary, allows tracking every click). Scaling: • Read-heavy → cache popular short codes in Redis • ID generation: Use a distributed ID generator (Snowflake) or pre-generate code batches • Analytics: Stream click events to Kafka → aggregate with Flink/Spark

Saga manages distributed transactions across multiple services without 2PC. Each service performs its local transaction and publishes an event. Downstream services listen and continue. On failure, compensating transactions roll back completed steps. Two implementations: • Choreography: Services communicate via events (Kafka). Each service knows what to do on success/failure. Decentralized but hard to trace the overall flow. • Orchestration: A central Saga Orchestrator (a service or state machine) tells each participant what to do and handles failures. Easier to visualize but adds a central component. Challenge: Compensating transactions may not be perfectly reversible (e.g., "cancel email sent"). Design idempotent compensations and accept eventual consistency.

CQRS (Command Query Responsibility Segregation) separates read (Query) and write (Command) models into distinct services/databases. Write side: Optimized for consistency and integrity (normalized relational DB). Returns only success/failure. Read side: Optimized for query performance (denormalized, pre-aggregated, Elasticsearch, Redis). Serves data directly without joins. Syncing: Changes on the write side are propagated to the read side via events (often via Event Sourcing). When to use: High read/write ratio with complex query requirements, reporting heavy systems, or when read/write scalability needs differ. Adds significant complexity — avoid for CRUD applications.

Rate limiting controls how many requests a client can make in a time window. • Token Bucket: Tokens added at a fixed rate; each request consumes one token. Allows bursts up to bucket size. Smooth on average. • Leaky Bucket: Requests fill a queue (bucket); processed at a fixed rate — excess spills (dropped). Enforces strict output rate, no bursts. • Fixed Window Counter: Count requests per window (e.g., per minute). Simple but allows double the rate at window boundary (burst attack). • Sliding Window Log: Store timestamps of requests; count in the last N seconds. Accurate but memory-intensive. • Sliding Window Counter: Hybrid of fixed window + sliding. Uses weighted average of two windows. Good accuracy with low memory. Redis is commonly used for distributed rate limiting (INCR + TTL or Lua scripts for atomicity).

The Circuit Breaker prevents cascading failures when a downstream service is slow or unavailable. Like an electrical circuit breaker, it "trips" to stop sending requests. Three states: • Closed (normal): Requests flow through. Failures tracked. If failure rate exceeds threshold, trip to Open. • Open (broken): Requests fail immediately (short circuit) without calling the downstream service. After a timeout, move to Half-Open. • Half-Open (testing): Allow a few probe requests. If they succeed, close the circuit. If they fail, re-open. Libraries: Resilience4j (Java), Hystrix (deprecated). Configure: failure threshold, wait duration in Open state, permitted calls in Half-Open. Combine with fallback logic (return cached data or default response) for graceful degradation.

HA means the system remains operational despite failures. Target: 99.9% (8.7h downtime/year), 99.99% (52min), 99.999% (5min). Strategies: • Redundancy: Multiple instances of each service, active-active or active-passive • Load balancing: Distribute traffic, health check and remove failed instances • Database HA: Replication (primary-replica), automatic failover (Patroni for PostgreSQL) • No single points of failure: Identify and eliminate them (load balancers themselves need HA — DNS round-robin or Anycast) • Graceful degradation: Serve reduced functionality rather than full failure • Health checks & auto-healing: Kubernetes restarts failed pods automatically • Multi-AZ/Multi-Region deployment: Survive data center failures • Chaos engineering (Netflix Chaos Monkey): Continuously test resilience

Eventual consistency guarantees that, if no new updates are made, all replicas will converge to the same value eventually. There's no guarantee of when — reads may return stale data. Contrast with strong consistency: Every read reflects the most recent write (requires coordination, adds latency). Techniques to handle eventual consistency: • Version vectors / timestamps: Detect conflicts between replicas • Last-Write-Wins (LWW): Use timestamp to resolve conflicts (risk of data loss) • CRDTs (Conflict-Free Replicated Data Types): Data structures that merge automatically without conflicts (counters, sets) • Read-your-writes: Route reads from a writer to the same replica • Monotonic reads: Route all reads from a client to the same replica Eventual consistency is acceptable for social feeds, analytics, DNS, and shopping carts.

A message queue (Kafka, RabbitMQ, SQS) decouples producers from consumers by persisting messages asynchronously. Use cases: • Async processing: Email/notification sending, image processing — don't block the HTTP response • Traffic spikes: Queue absorbs bursts; consumers process at their pace • Fan-out: Broadcast one event to multiple consumers (Kafka topics) • Reliability: Messages persist until consumed; services don't lose data if downstream is down • Microservice decoupling: Services don't need to know each other's address Trade-off: Adds complexity, eventual consistency, harder to debug, requires monitoring consumer lag. Don't use when: Strong consistency is required (use synchronous RPC), real-time response is needed, or when a direct call is simpler.

SQL (Relational): Structured schema, ACID transactions, powerful joins and complex queries. Examples: PostgreSQL, MySQL. Best for: financial systems, e-commerce orders, any data with complex relationships. NoSQL categories: • Document (MongoDB): Flexible JSON documents, good for hierarchical data, catalog, CMS • Key-Value (Redis, DynamoDB): Ultra-fast lookups by key, sessions, caching, leaderboards • Wide-Column (Cassandra, HBase): Optimized for time-series, high-write workloads, IoT data • Graph (Neo4j): Relationships as first-class citizens, social networks, fraud detection NoSQL advantages: Horizontal scaling, flexible schema, high throughput for specific access patterns. Trade-offs: Limited joins, weaker consistency guarantees (most), harder to query ad-hoc.

A CDN (Content Delivery Network) is a geographically distributed network of edge servers that cache and serve content close to users. How it works: Static assets (JS, CSS, images, videos) and cacheable API responses are cached at edge nodes. User requests are routed to the nearest edge via Anycast DNS or BGP. On cache miss, the edge fetches from the origin and caches the response. Benefits: • Reduced latency: Serve from a node 10ms away instead of an origin 200ms away • Origin offload: 90%+ of requests served from edge • DDoS mitigation: Absorb attacks at the edge before reaching the origin • Availability: Even if origin is down, cached content continues to be served Providers: Cloudflare, AWS CloudFront, Fastly, Akamai.

Two-Phase Commit (2PC) provides strong consistency but is slow, blocking, and fragile — a coordinator failure leaves participants in limbo. Alternatives: • Saga pattern: Chain of local transactions with compensating rollbacks. Achieves eventual consistency. • Outbox pattern: Write to a local "outbox" table in the same DB transaction as the business operation. A separate process publishes outbox messages to Kafka reliably (transactional messaging without 2PC). • TCC (Try-Confirm-Cancel): Reserve resources in Try phase, confirm or cancel asynchronously. Used in payments. • Event Sourcing: All state changes stored as events. No distributed transaction needed — events are the source of truth. Key insight: Accept that distributed transactions have at-least-once semantics — design all operations to be idempotent.

High-level design: • API layer: REST endpoint accepts notification request (to, type, template, data) • Message queue: Publish to Kafka topic by channel (email-notifications, sms-notifications, push-notifications) • Channel workers: Separate consumers per channel that call providers (SendGrid for email, Twilio for SMS, FCM/APNs for push) • Template service: Render notification body from templates • User preference service: Check user's channel preferences and DND settings before sending • Rate limiting: Per-user rate limits to prevent spam • Retry logic: Exponential backoff for failed sends • Status tracking: Store notification_id → {status, sentAt, provider, error} Scale: Each channel worker scales independently. Kafka partitioning by user_id ensures per-user ordering.

REST: HTTP/1.1, text-based (JSON/XML), human-readable, wide tooling support. Request/response model. Stateless. Best for public APIs, browser clients, and simple CRUD operations. gRPC: HTTP/2, binary Protocol Buffers (protobuf), compact and fast, strongly typed contract (proto files). Supports 4 communication modes: unary, server streaming, client streaming, bidirectional streaming. Excellent for internal microservice communication. gRPC advantages: 5–10× smaller payload than JSON, multiplexing over single connection, auto-generated type-safe client stubs in multiple languages. Choose REST for: public APIs, browser clients, teams unfamiliar with gRPC. Choose gRPC for: internal service-to-service communication, low-latency requirements, streaming use cases.

The Outbox Pattern solves the dual-write problem: reliably publishing an event to a message broker after a database write, without 2PC. Problem: You write to DB and publish to Kafka separately — if the service crashes between the two, you lose either the DB write or the event. Solution: Write both the business record and the event to an outbox table in a single DB transaction. A separate Message Relay process (Debezium CDC, polling worker) reads unpublished outbox rows and publishes them to Kafka, then marks them as published. Guarantee: At-least-once delivery (the relay may retry on failure). Design consumers to be idempotent (use event ID for deduplication). Debezium monitors the DB's WAL (write-ahead log) and publishes events with sub-second latency.

Architecture: Redis Cluster or Memcached in front of the database. Multiple instances for availability and horizontal scalability. Key decisions: • Eviction policy: LRU (evict least recently used), LFU (least frequently used), or no-eviction with explicit TTLs • Cache warming: Preload popular data on startup to avoid cold-start stampede • Cache stampede (thundering herd): Many simultaneous misses after expiry. Solutions: Mutex on cache miss (only one thread fetches, others wait), probabilistic early expiration, background refresh • Consistency: Decide between cache-aside, write-through, or write-behind based on consistency requirements • Key naming: Namespace keys (users:123:profile) to avoid collisions and support bulk invalidation with pattern matching • Cluster mode: Redis Cluster shards data across 16384 hash slots for horizontal scale

Synchronous: Caller blocks and waits for the response. HTTP/REST and gRPC are synchronous. Simple to reason about, easier debugging, natural request-response flow. Problem: Tight coupling — caller is blocked if callee is slow or down. Cascading failures propagate upstream. Asynchronous: Caller sends a message and continues. Kafka, RabbitMQ, SQS are async. Decouples producer from consumer, absorbs traffic spikes, enables retry without caller involvement. Problem: Complex — eventual consistency, harder debugging, need correlation IDs to trace flows. Hybrid: Use sync for queries needing immediate results (product lookup), async for commands (order placed, email sent). CQRS naturally separates these. Fire-and-forget for non-critical operations (audit logs, analytics). Implement async with a message broker and inbox/outbox patterns for reliability.

Components: • API Layer: Accept notification requests, validate, persist to DB • Message Queue: Kafka for durability and high throughput (partition by user_id for ordering) • Worker Services: Channel-specific workers (Email, SMS, Push, In-App) • Template Engine: Render personalized messages • User Preference Store: Redis cache of user channel preferences and opt-outs • Delivery Tracking: Record sent, delivered, opened events Flow: Client → API → Kafka topic notifications → Workers pull messages, check preferences, render template → Send via provider (SendGrid, Twilio, APNs/FCM) At 100M/day = ~1,160/second. Kafka handles millions/sec. Scale workers horizontally. Use provider bulk APIs. Implement exponential backoff for failed deliveries. Rate limit per user (no more than N per hour). Priority queues: transactional notifications over marketing.

B-Tree index: Default. Supports equality and range queries. Best for columns with high cardinality used in WHERE, ORDER BY, JOIN. Works for prefix searches on strings. Hash index: O(1) exact-match lookup. Only supports equality (=), not ranges or ORDER BY. Good for in-memory tables (MEMORY engine in MySQL). Composite index: Index on multiple columns. Left-prefix rule: (a, b, c) index benefits queries filtering on (a), (a,b), (a,b,c) but NOT on (b) or (c) alone. Column order matters — put equality columns first, range columns last. Covering index: Index contains all columns needed for a query. No table lookup needed (index-only scan). Fastest read performance. Partial index: Index on a subset of rows (WHERE is_active = true). Smaller, faster for selective queries. Full-text index: Tokenizes text for CONTAINS/MATCH queries. Use Elasticsearch for production full-text search. Spatial/GIS index: R-Tree for geospatial queries (PostGIS, MySQL SPATIAL).

Requirements: ~100M URLs/day created, 1B reads/day, short codes must be unique, redirects must be fast. Core algorithm: Generate a 7-character base-62 code (62^7 = 3.5 trillion unique URLs). Options: MD5/SHA-256 hash of URL then take first 7 chars (risk of collision), auto-increment ID encoded in base-62, or pre-generated random code pool. Schema: { short_code (PK), original_url, created_at, user_id, expiry, click_count } Redirect flow: Browser → Load balancer → App server → Cache (Redis) → DB → 302 redirect Caching: Cache short_code → URL mapping in Redis. TTL matches URL expiry. Cache hit rate should be very high (Pareto: 20% of URLs get 80% of traffic). Write: Validate original URL, generate code, check uniqueness, persist, invalidate cache if needed. Scale: 1B reads/day = 11,500/sec → multiple app servers, global CDN for redirect edge nodes, read replicas for DB. Click analytics via async Kafka pipeline to Clickhouse.

Eventual consistency: In a distributed system, if no new updates are made to a given data item, eventually all reads will return the same value. There's a window of inconsistency between updates propagating to all replicas. Examples: DNS propagation, DynamoDB with eventual reads, Cassandra by default. Handling it: • Version vectors / vector clocks: Track causality to detect conflicting updates • Last-Write-Wins (LWW): Use timestamps (risk: clock skew causes data loss) • Conflict-free Replicated Data Types (CRDTs): Mathematical structures that merge automatically (counters, sets, maps) • Read-your-writes: Route same user's reads to same node (sticky sessions or primary reads) • Monotonic reads: Ensure a user never sees older data after seeing newer data • Compensating transactions: Detect and resolve eventual conflicts with business logic (inventory correction, refunds) Domains that tolerate it: Social feeds, counters, carts (merge). Cannot tolerate: financial balances, inventory with zero-floor constraints.

For full-text search, use Elasticsearch or OpenSearch — do not try to build this on SQL LIKE queries at scale. Architecture: • Ingestion pipeline: Source DB → CDC (Debezium) or application events → Kafka → Indexer service → Elasticsearch • Query layer: Search API → Elasticsearch → Ranking → Response • Index design: Define mappings (field types, analyzers, tokenizers). Use inverted index for text, BKD tree for numerics/ranges, geo-point for location. Relevance: TF-IDF or BM25 scoring. Boost fields (title > body). Apply business boosts (sponsored, popular). Scalability: Shard index across nodes (primary + replica shards). More shards = more parallel search. More replicas = more read throughput and HA. Typeahead/Autocomplete: Edge n-gram tokenizer, completion suggester, or Redis Sorted Set with prefix scan for ultra-low latency. Caching: Cache popular query results in Redis with short TTL. Cache at CDN layer for anonymous users.

Pessimistic locking: Lock the resource before reading/writing. Other transactions block until the lock is released. Implemented with SELECT ... FOR UPDATE in SQL. Prevents all conflicts but reduces concurrency. Use when conflicts are frequent or data integrity is critical (financial transactions, inventory decrement). Optimistic locking: Read without locking. At write time, verify nothing changed using a version number or timestamp. If changed, reject and retry. Implemented with a version column: UPDATE ... WHERE id=? AND version=?. Higher concurrency — reads never block. Use when conflicts are rare (user profile updates, CMS content). Comparison: • Pessimistic: Prevents conflicts, lower concurrency, risk of deadlocks • Optimistic: Higher concurrency, requires retry logic, causes conflict failures under high contention Database support: JPA @Version annotation implements optimistic locking. Throws OptimisticLockException on conflict.

Core data structure: Redis Sorted Set (ZSET). O(log N) for add/update score, O(log N) for rank lookup, O(log N + K) for range queries. Operations: • ZADD leaderboard score userId — add or update score • ZREVRANK leaderboard userId — get rank (0-based, descending) • ZREVRANGE leaderboard 0 9 WITHSCORES — top 10 • ZINCRBY leaderboard delta userId — increment score atomically Scale: One Redis instance handles 100K+ ops/sec. For global leaderboards, partition by time (daily, weekly, all-time) — separate ZSET per window, expire daily ZSETs automatically. Persistence: Write scores to DB asynchronously (Kafka → consumer → PostgreSQL). Redis is source of truth for real-time ranking; DB for historical reporting. User profile enrichment: Leaderboard stores userId only. Fetch names/avatars from user service or cache. Batch-fetch to avoid N+1. Fairness: Timestamp as tiebreaker (earlier = better): compound score = score * 10^10 + (MAX_TS - timestamp).

Write-ahead log: All changes are written to an append-only log on disk before being applied to the actual data files. This guarantees durability and atomicity without fsync on every data page write. How it works: Transaction writes changes to WAL → WAL is fsynced to disk → Transaction commits → Data pages updated in memory (dirty) → Background checkpoint writes dirty pages to disk. On crash, replay WAL from last checkpoint to restore committed transactions. Benefits: • Crash recovery: Replay uncommitted transactions, roll back incomplete ones • Replication: PostgreSQL streaming replication ships WAL segments to standby. MySQL binlog is a similar concept. • CDC: Debezium reads PostgreSQL WAL (logical decoding) to capture row-level changes for event streaming. • Point-in-time recovery: Apply WAL segments from a base backup to restore to any point in time. Overhead: Sequential disk writes (fast). Checkpoint frequency trades crash recovery time vs I/O.

Two-Phase Commit (2PC): Coordinator asks all participants to prepare (lock resources), then sends commit or rollback. Strong consistency but synchronous, blocks on coordinator failure, poor availability. Rarely used in microservices. Saga Pattern (recommended): Break the transaction into local transactions, each with a compensating transaction. Two implementations: Choreography Saga: Each service publishes events that trigger the next step. Decentralized, no coordinator. Hard to track overall state, risk of cyclic dependencies. Orchestration Saga: A central Saga Orchestrator sends commands to services and handles failures by calling compensating transactions. Easier to understand and debug, single source of truth for saga state. Example: Order service creates order → Payment service charges card → Inventory service reserves stock → Shipping service schedules pickup. If inventory fails: Shipping skipped, Inventory compensates (no-op), Payment compensates (refund), Order compensates (cancel). Tools: Temporal, Conductor, Axon Framework for saga orchestration.

Core requirements: 1-on-1 and group messaging, online presence, read receipts, message history. Connection layer: WebSocket connections maintained per user (persistent). Each user connects to a Chat Server. Use a connection manager to map userId → server. Message flow: Sender → Chat Server A → Kafka → Chat Server B (recipient's server) → WebSocket → Recipient. If recipient offline: Store in DB, deliver when reconnected (push notification to wake app). Storage: Messages stored in Cassandra (optimized for time-series, write-heavy). Schema: partition by conversation_id, cluster by message_id (time-sortable UUID). Efficient for loading conversation history. Presence: User heartbeat every 30s → Presence Service updates Redis (userId → last_seen). Subscribe to presence events via pub/sub. Read receipts: Message states: sent → delivered → read. Publish state change events back through the system. Group chat: Fanout to all members. For large groups (>500), use server-side fanout via Kafka partitions per group.

Service mesh: An infrastructure layer that handles service-to-service communication via sidecar proxies (e.g., Envoy). Deployed alongside each service pod. Features: mTLS encryption between services, traffic management (load balancing, retries, timeouts, canary routing), observability (distributed tracing, metrics, logs), circuit breaking, rate limiting — all without application code changes. Popular implementations: Istio (most feature-rich, complex), Linkerd (lighter weight, easier), Consul Connect. When to use: • You have 10+ microservices with complex inter-service traffic • You need mTLS without modifying every service • You want centralized observability and traffic policy • You're doing canary/traffic-shifting deployments When NOT to use: • Small teams with few services — the operational overhead (CRDs, control plane, debugging sidecar issues) is significant • Monoliths or simple 2-3 service setups Alternatives: Libraries like Resilience4j in the app, API gateway for edge traffic management.

Upload pipeline: User uploads raw video → Object storage (S3) → Transcoding service (FFmpeg workers) → Multiple resolutions (1080p, 720p, 480p, 360p) + formats (HLS, DASH) → CDN distribution. HLS/DASH: Video split into 2-10s segments. Manifest file lists segments per quality level. Player adapts quality based on bandwidth (adaptive bitrate streaming). Storage: Raw uploads in S3 (cold). Processed segments in S3 distributed to CDN edge nodes globally. Metadata (title, description, views, likes) in PostgreSQL with Redis cache. Thumbnails in CDN. Serving: Video requests → CDN edge → S3 (cache miss). CDN absorbs 90%+ of traffic. Use pre-signed URLs for private content. View counting: Increment counter via Kafka (event: video_viewed) → Consumer aggregates → Periodic DB write. Redis for real-time approximate count. Exact count via Kafka Streams aggregation. Recommendation: Collaborative filtering + content-based ML model. Pre-computed recommendations stored in Redis, refreshed periodically.

Load Balancer: Distributes traffic across multiple instances of the same service. Operates at L4 (TCP/IP) or L7 (HTTP). Core function: health checks + routing. Examples: AWS ALB, NGINX, HAProxy. Features: Round-robin, least-connections, IP-hash algorithms. SSL termination, sticky sessions. API Gateway: Single entry point for all client requests to multiple backend services. Operates at L7. Core function: routing to different services based on URL path + cross-cutting concerns. Features: Authentication/authorization, rate limiting, request/response transformation, protocol translation (REST → gRPC), request aggregation, circuit breaking, API versioning, developer portal. When to use which: • Both together: API Gateway (edge) → Load Balancer (per service cluster) • Load balancer alone: Internal service-to-service traffic • API Gateway: External API management, BFF (Backend For Frontend) pattern Examples: Kong, AWS API Gateway, Apigee, Traefik, Netflix Zuul.

Cascading failure: Service A fails → B depending on A fails → C depending on B fails → whole system down. Prevention strategies: 1. Circuit Breaker: After N failures in a time window, open the circuit. Fail fast without calling the failing service. Half-open state probes recovery. 2. Timeouts: Every external call must have a deadline. Without timeouts, threads pile up on slow calls, exhausting the thread pool. 3. Bulkhead: Isolate resources per dependency. Use separate thread pools or connection pools for each downstream service. Failure in one doesn't starve others. 4. Rate Limiting: Protect services from overload by limiting incoming requests. 5. Retries with exponential backoff + jitter: Avoid synchronized retry storms after transient failures. Max retry limit. 6. Graceful degradation: Return cached response, default value, or partial result when dependency is unavailable. 7. Health checks + fast failure: Load balancers remove unhealthy instances quickly. Tooling: Resilience4j (Java), Polly (.NET), Hystrix (deprecated).

Message Queue: A queue where producers publish messages and consumers consume them in FIFO order. Point-to-point: one message is consumed by exactly one consumer. Examples: AWS SQS, RabbitMQ queues. Message Broker: A middleware that routes messages between producers and consumers. Supports multiple messaging patterns: queues (point-to-point), topics/pub-sub (one-to-many), request-reply. Handles routing, transformation, protocol translation. Examples: RabbitMQ (broker), ActiveMQ. Kafka: A distributed log/event streaming platform. Not a traditional queue or broker. Messages persist and are replayable. Consumers maintain their own offset. Multiple consumer groups can each read all messages independently. High throughput (millions/sec). Best for event sourcing, CDC, stream processing. Choose: • SQS/RabbitMQ queue: Simple task distribution, at-most-once or at-least-once delivery, auto-delete after consume • Pub-sub: One event to many subscribers (fanout) • Kafka: Event streaming, auditability, replay, stream processing (Kafka Streams, Flink)

Algorithms: Token Bucket: Bucket holds up to B tokens. Refills at rate R tokens/sec. Each request consumes one token. Allows bursts up to bucket size. Redis: INCRBY with TTL or Lua script for atomicity. Leaky Bucket: Requests enter a queue and are processed at a fixed rate. Smooth output — no bursts. Good for traffic shaping. Fixed Window Counter: Count requests per time window (per minute). Simple but allows 2× burst at window boundary. Sliding Window Log: Store timestamp of each request. Count requests in the last N seconds. Accurate but memory-intensive. Sliding Window Counter: Hybrid — approximation using current + previous window count weighted by position. Good balance. Distributed implementation: Redis + Lua script (atomic increment + expire). Use MULTI/EXEC or Lua to prevent race conditions. Rate limit key: rate:userId:endpoint:window. Response headers: X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset, Retry-After on 429. Layers: Per-user, per-IP, per-API-key, global.

Replication: Copy the same data to multiple nodes. Each replica has the full dataset. Purpose: High availability (failover to replica), read scalability (distribute reads across replicas), geographic distribution (replicas closer to users). Types: • Synchronous: Primary waits for replica confirmation before committing. No data loss, higher latency. • Asynchronous: Primary commits, replica catches up. Lower latency, potential data loss on failover. Partitioning (Sharding): Split data across multiple nodes. Each node has a subset of the data. Purpose: Write scalability (spread writes across shards), storage scalability (more nodes = more total storage), query parallelism. They are complementary: Each partition/shard is typically replicated (e.g., each Kafka partition has 3 replicas; each Cassandra shard is replicated across N nodes based on replication factor). Combination: MongoDB replica sets (replication) + sharding (partitioning). Cassandra: consistent hashing for partitioning + replication factor for copies.

Two approaches: Push (fanout on write) vs Pull (fanout on read). Fanout on write (push model): When a user tweets, immediately push to all followers' feed lists in Redis. O(N) write cost, O(1) read. Problem: celebrity with 50M followers triggers 50M writes per tweet — "hot user" problem. Fanout on read (pull model): On feed load, fetch tweets from all followed users, merge, sort by time. O(1) write, O(N) read per load. Expensive reads — doesn't scale for users following thousands. Hybrid (Twitter's actual approach): Fanout on write for non-celebrities (< threshold followers). Fanout on read for celebrities. At read time, merge pre-computed feed (regular users) with real-time tweets from followed celebrities. Storage: Feed stored in Redis (list of tweet IDs). Tweet content in separate store (Cassandra). Fetch tweet details separately. Ranking: Chronological (simple) or algorithmic (ML model scores tweets by predicted engagement). Twitter uses ranked feed by default.

Observability: The ability to understand the internal state of a system from its external outputs. More than just monitoring — it enables asking new questions without deploying new instrumentation. Three pillars: 1. Metrics: Numerical measurements over time. Low storage cost, aggregated. Types: counter (requests_total), gauge (memory_usage_bytes), histogram (request_duration_seconds), summary. Tools: Prometheus + Grafana. Use for dashboards, SLO tracking, alerting. 2. Logs: Structured records of discrete events. Rich context per event. Use JSON structured logging with correlation ID. Tools: ELK stack (Elasticsearch, Logstash, Kibana), Loki + Grafana, CloudWatch. Use for debugging specific incidents. 3. Distributed Traces: End-to-end view of a request as it flows through multiple services. Each span records service, operation, duration, parent span. Context propagated via trace-id/span-id headers (W3C TraceContext standard). Tools: Jaeger, Zipkin, AWS X-Ray, Tempo. Use for latency attribution and finding slow services. OpenTelemetry: Vendor-neutral SDK for all three pillars — the standard instrumentation layer.

SQL (Relational): Structured schema, ACID transactions, relations via foreign keys, SQL query language. Best for: complex queries, multi-table joins, financial data needing strong consistency. NoSQL categories: • Document (MongoDB, CouchDB): JSON documents, flexible schema, nested objects. Best for: content management, catalogs, user profiles. • Key-Value (Redis, DynamoDB): Fast O(1) lookup by key. Best for: caching, sessions, shopping carts. • Wide-Column (Cassandra, HBase): Rows + dynamic columns, optimized for write-heavy time-series. Best for: IoT, activity logs, leaderboards. • Graph (Neo4j, Neptune): Nodes and edges, relationship traversal. Best for: social networks, fraud detection, recommendation engines. CAP tradeoffs: SQL is typically CP. Cassandra/DynamoDB are AP. Redis can be configured either way. Choose SQL when: ACID is required, data is highly relational, ad-hoc queries needed. Choose NoSQL when: Massive scale, flexible/evolving schema, specific access patterns dominate, partition tolerance is priority.

Idempotency: Calling an operation multiple times produces the same result. Essential for safe retry on network failures. Idempotency key approach: Client generates a unique key (UUID) per logical operation. Sends it in header: Idempotency-Key: <uuid>. Server implementation: 1. Check if key exists in idempotency store (Redis with TTL, or DB table) 2. If exists: return the cached response from the previous successful execution 3. If new: Process the request, store the result keyed by idempotency key, return result Important: Store key BEFORE processing, or use a transaction to set key + process atomically. Without this, a crash between process and store leaves the key unstored — next retry reprocesses. Natural idempotency: PUT (replace entire resource) and DELETE are naturally idempotent. GET/HEAD are safe and idempotent. POST is not by default — requires idempotency keys. Database upserts: INSERT ... ON CONFLICT DO UPDATE makes writes idempotent. Use event_id as unique key to deduplicate message processing. Used by: Stripe, Braintree, Twilio — all payment APIs require idempotency keys.

Requirements: Execute millions of jobs at specified times or intervals. Jobs must run exactly once (or at-least-once). Handle failures, retries, distributed execution. Components: • Job Store: Database (PostgreSQL) with jobs table: {id, type, payload, scheduled_at, status, attempts, worker_id, locked_until} • Scheduler: Polls DB for jobs due in the next N seconds. Acquires lock via optimistic locking or SELECT FOR UPDATE SKIP LOCKED (PostgreSQL) to prevent double execution. • Worker Pool: Workers pull locked jobs, execute, update status (done/failed), release lock. • Retry: On failure, update attempts + 1, calculate next retry time (exponential backoff), reset status to pending. SELECT FOR UPDATE SKIP LOCKED: PostgreSQL feature that locks selected rows and skips already-locked rows — perfect for job queue polling. Multiple workers can poll without coordination. Cron scheduling: Parse cron expression, calculate next_run, persist next_run as scheduled_at after each execution. Distributed leader election: Only one scheduler instance polls to avoid duplicate scheduling (use Zookeeper or database advisory locks). Production tools: Quartz Scheduler, Temporal, Sidekiq (Ruby), Celery (Python).

2PC (Two-Phase Commit): Coordinator sends PREPARE to all participants (they lock resources and log). If all say OK, coordinator sends COMMIT; else ROLLBACK. Strong consistency but blocking — if coordinator fails after PREPARE, participants block indefinitely with locks held. Poor availability under partial failure. Rarely used across microservice boundaries. Saga: Sequence of local transactions. Each step publishes event/sends command to trigger next step. On failure, execute compensating transactions in reverse order to undo completed steps. Choreography Saga: Services react to events. No central coordinator. Pros: loose coupling. Cons: hard to track overall progress, complex to debug, risk of cycles. Orchestration Saga: Saga Orchestrator service directs each participant: "charge payment," "reserve inventory." Tracks state machine. On failure, sends compensation commands. Pros: single source of truth, easier monitoring. Cons: orchestrator is a central component. Key difference from 2PC: Sagas do not hold locks across service boundaries. Consistency is eventual. Each local transaction commits immediately. Compensations are business-level undos (refund, cancel), not DB rollbacks. Use Saga when: Cross-service data changes, microservices architecture, availability > strong consistency.

Core features: Upload/download/sync files across devices, share files, versioning. Upload flow: • Client chunks file into 4MB blocks • Compute SHA-256 hash per block • Send only blocks not already on server (deduplication) • Server assembles chunks, stores in S3 or equivalent object store • DB records: files (metadata), file_versions, file_chunks, user_storage_usage Sync engine: Client maintains local DB of (path → block hashes). On file change, compute diff, upload changed blocks only. Server notifies other devices via long-poll or WebSocket. Client downloads changed blocks and reconstructs file. Deduplication: Same block appearing across multiple files is stored once. SHA-256 hash as content address. Saves massive storage (e.g., common system files). Versioning: Keep N versions per file. Each version is a list of block references. Roll back by restoring previous version's block list. Charged storage = unique blocks only. Scale: Block metadata in PostgreSQL. Block content in S3 (cheap, durable). Delta sync reduces bandwidth by 60-90%.

Monolith advantages: Simple deployment (one artifact), no network overhead for internal calls, easier debugging, ACID transactions across all data, one codebase to understand. Monolith disadvantages: Scales as a unit (can't scale individual components), risky deployments (one change deploys everything), technology lock-in, large teams stepping on each other. Microservices advantages: Independent deployment and scaling, technology diversity, team autonomy, isolated failures, can evolve services independently. Microservices disadvantages: Network latency and partial failures, distributed transaction complexity, operational overhead (many services to deploy/monitor/secure), eventual consistency, service discovery, inter-service contract versioning. Migration path: "Strangler Fig" pattern — gradually extract services from monolith. Start with clear domain boundaries, not technical layers. Conclusion: Start with a well-modularized monolith (majestic monolith). Extract to microservices when you hit clear scaling or team scaling problems. Most startups suffer more from premature microservices than staying monolithic too long.

DNS resolution: Client asks recursive resolver → Resolver checks root nameserver → Root returns TLD (.com) nameserver → TLD returns authoritative nameserver → Authoritative returns IP → Resolver caches and returns IP to client. TTL (Time To Live): How long DNS records are cached at each hop. Lower TTL = faster propagation of changes but more DNS queries. Higher TTL = less query load but slower failover. DNS load balancing: • Round-robin DNS: Return multiple A records. Client picks one (usually first). Simple but no health checking, no intelligent routing. • Weighted round-robin: Assign weights to favor some servers. • GeoDNS / Latency-based: Return IP closest to client's location (AWS Route 53 latency routing). Reduces latency for global users. • Failover DNS: Primary IP returned normally. On failure, health check detects it and TTL expires, then secondary IP returned. Limitations of DNS LB: No session affinity, clients cache aggressively (TTL ignored sometimes), no real-time health checking. Usually combined with layer-4/7 load balancer for production. AWS Route 53 supports: weighted, latency, failover, geolocation, geoproximity, multivalue answer routing policies.

Strangler Fig: A migration strategy for incrementally replacing a legacy system with a new system, without a big-bang rewrite. Named after the fig tree that slowly replaces its host tree. Approach: 1. Deploy the new system alongside the old one 2. Place a routing layer (API gateway, reverse proxy) in front of both 3. Incrementally move functionality from old to new: new endpoint goes to new system, legacy endpoint stays on old 4. Over time, more and more traffic routes to the new system 5. When old system handles 0% of traffic, decommission it Benefits: No risky big-bang cutover, rollback is easy (reroute traffic), can test new system incrementally, parallel validation. Challenges: Running two systems simultaneously costs more. Data synchronization between systems during migration. Routing layer is a temporary but important component. Integration tests across both systems. Applied to databases: Use CDC (Debezium) to sync data from old DB to new DB during migration. Cut over reads once new DB is caught up. Works well with feature flags: Enable new implementation for a percentage of users.

Flash sale challenge: Thousands of concurrent purchases for limited stock (e.g., 100 items, 10,000 concurrent buyers). Must prevent overselling, must handle extreme traffic spike. Solutions: 1. Database pessimistic lock: SELECT stock FROM inventory WHERE id=? FOR UPDATE; check > 0; decrement; commit. Correct but creates a bottleneck — single lock per item. Works for moderate traffic. 2. Optimistic lock: Read stock + version, UPDATE WHERE version=old_version. On conflict, retry. Good concurrency, but high retry rate under extreme contention. 3. Redis atomic decrement: DECRBY stock item_id qty. Return value: if ≥ 0, purchase allowed; if < 0, INCRBY to restore and reject. Redis handles 100K+ ops/sec. Eventual write to DB via queue. 4. Request queue + serialization: All purchase requests go to Kafka. Single consumer processes them in order, guaranteeing no oversell. Trades latency for correctness. 5. Pre-allocation: For flash sales, pre-generate a pool of purchase tokens in Redis. First N requests claim a token. No stock check needed — token = reserved unit. Anti-bot: Rate limit per user, CAPTCHA, IP throttling before purchase endpoint.

Pull: Consumers request data from producers on their own schedule. Consumers control pace — no risk of being overwhelmed. Consumer can batch, replay from offset (Kafka pull model). Simpler producer (no need to know about consumers). Latency: polling interval introduces delay. Push: Producer sends data to consumers immediately. Low latency — consumers get data as soon as it's available. Problem: if consumer is slow, it gets overwhelmed (backpressure needed). Producer must track consumer registration and state. Kafka uses pull: Consumers poll at their own rate, track offsets. Producer writes to log, doesn't know about consumers. Enables replay and multiple independent consumer groups. Webhooks use push: Source system sends HTTP POST to registered URL on event. Simple integration but destination must be available and must handle duplicate delivery (retry on failure). Server-Sent Events (SSE): Server pushes events to browser over HTTP/1.1. Good for real-time dashboards, notifications. Long-polling: Client polls, server holds response until event available. Simulates push. Replaced by WebSockets or SSE in modern systems.

CDN (Content Delivery Network): A geographically distributed network of edge servers that cache and serve content from locations close to users. How it works: 1. Content origin (your servers/S3) holds the canonical copy 2. CDN edge nodes (PoPs — Points of Presence) worldwide cache content 3. User's DNS request resolves to the nearest edge node (GeoDNS or Anycast) 4. Edge serves from cache (HIT) or fetches from origin, caches, and serves (MISS) 5. Cache-Control headers (max-age, s-maxage) control how long edge caches content What to serve from CDN: • Static assets: JS, CSS, images, fonts • Videos (HLS segments) • API responses that are read-heavy and infrequently updated (product catalog) • Pre-rendered HTML pages Cache invalidation: CDN cache busting via filename hashing (app.a1b2c3.js). Or explicit purge API call on deploy. HTTPS: CDN terminates TLS at edge — reduces latency (TLS handshake near user). Origin connection uses keep-alive. Providers: Cloudflare, CloudFront (AWS), Fastly, Akamai. CDN also provides: DDoS protection, WAF, image optimization, edge compute (Cloudflare Workers).

Key challenge: Real-time decisions (< 100ms) while processing billions of transactions, with evolving fraud patterns. Architecture: • Real-time layer: Transaction event → Kafka → Stream processor (Flink/Kafka Streams) → Feature computation → ML model inference → Risk score → Allow/Block/Review • Batch layer: Nightly ML model retraining on labeled data (fraud/not-fraud). Feature store updated with aggregated user behavior. • Feature store: Precomputed user/device features (tx count last hour, avg amount, unusual location) in Redis for sub-ms lookup. Features used: Velocity (N transactions in M minutes), device fingerprint, IP geolocation vs billing address, amount vs historical average, merchant category, time of day, device change. ML models: Gradient boosted trees (XGBoost) for interpretability, neural networks for complex patterns, anomaly detection for novel fraud types. Feedback loop: Chargebacks and confirmed fraud → labeled training data → retrained models. Human review queue for medium-confidence scores. Rule engine: Hardcoded rules (amount > $10K = manual review) alongside ML for compliance, interpretability, and catch obvious patterns without ML overhead.

CRUD: Store current state. Each write overwrites previous state. You know the current value but not how you got there. Event Sourcing: Store all events that led to current state. State is derived by replaying events. Never overwrite — only append. Example: Bank account • CRUD: balance = 1000 • Event Sourcing: [Opened(0), Deposited(500), Deposited(700), Withdrawn(200)] → replay → balance = 1000 Benefits: • Complete audit log — every state transition is recorded • Temporal queries — what was the state at any point in time? • Rebuild projections — replay events to build any read model • Debug by replaying events to reproduce bugs • Event-driven integration — emit events to downstream systems Challenges: • Event schema evolution — old events must stay valid as schema changes • Snapshots needed — replaying 10M events every time is slow (snapshot state every N events) • Eventual consistency in read models (projections) • Query complexity — no simple SELECT; must use projections Paired with CQRS: Command side appends events; Query side maintains projections optimized for reads.

Requirements: Find all available drivers within X km of a user's location in real-time. Driver locations update every few seconds. Geospatial indexing: Divide earth into a grid. Common approaches: • Geohash: Encode lat/lon as a base-32 string. Neighboring cells share common prefix. Store in Redis GEOADD or DB spatial index. GEORADIUS query for nearby drivers. • Quadtree: Recursively subdivide space into quadrants. Adaptive — denser in cities, sparse in rural. • S2 Geometry (Google/Uber): Hierarchical cell decomposition of sphere. Used by Uber (H3 library). Architecture: 1. Driver app sends location every 4s → Location Update Service 2. Service writes to Redis GEOADD (key: city:available_drivers, score: geohash, member: driverId) 3. User requests ride → Dispatch Service queries GEORADIUS from user location → Returns nearby driver IDs 4. Fetch driver details, ETA, route from matching service Scale: Redis Cluster partitioned by city. One shard per city for locality. Location updates: 1M drivers × 4s = 250K updates/sec — Redis handles this. ETA computation: Road network graph (OSM data), Dijkstra/A* with real-time traffic adjustment.

API versioning allows evolving your API without breaking existing clients. Strategies: 1. URL path versioning: /api/v1/users, /api/v2/users. Most visible, easy to test in browser/curl. Caching friendly. Recommended for REST public APIs. 2. Query parameter: /api/users?version=2. Flexible but optional — easy to forget. Less common. 3. Header versioning: API-Version: 2 or Accept: application/vnd.company.v2+json. Clean URLs but harder to test and debug. 4. Content negotiation (Accept header): Accept: application/vnd.company.resource-v2+json. RESTful purists prefer this. Hard to discover and document. Breaking vs non-breaking changes: • Breaking: Remove/rename fields, change field types, change behavior, remove endpoints → requires version bump • Non-breaking: Add new optional fields, add new endpoints → safe to add without version bump Deprecation: Mark old version as deprecated in response headers. Set a sunset date. Give clients 6-12 months. Monitor usage of old version. Semantic versioning: Use for APIs: MAJOR.MINOR.PATCH. Only MAJOR changes break clients.

Bloom filter: A probabilistic data structure that tests set membership. Returns "definitely not in set" or "probably in set." Never has false negatives; may have false positives. Space-efficient (100× smaller than a hash set). How it works: K hash functions map each element to K bits in a bit array. To insert: set those K bits. To check membership: if all K bits are set → probably member; if any bit is 0 → definitely not member. Cannot delete (use Counting Bloom filter for deletion). False positive rate: Controlled by bit array size (m) and number of hash functions (k). For 1% FPR with 1M elements: ~10MB bit array. System design uses: • Database: Check Bloom filter before disk read — skip I/O if key definitely not in data file. Cassandra, HBase use per-SSTable Bloom filters. • Cache: Skip cache lookup if key definitely not cached. Avoid cache-aside DB hits for nonexistent keys (attackers sending random keys — cache penetration attack). • URL deduplication: Web crawlers check if URL already visited. • Username availability check: Before DB query. • Spam filter: Email/URL blacklist lookup. • Bitcoin: SPV wallets use Bloom filters to fetch relevant transactions without revealing addresses.

Zero-downtime deployment strategies: Rolling deployment: Replace instances one by one (or in small batches). At any point, some instances run old version, some new. Traffic gradually shifts. Risk: brief mixed-version state — API must be backward compatible. Blue/Green deployment: Spin up a complete new (green) environment. After testing, switch load balancer to route all traffic to green. Old (blue) kept as rollback. Instant cutover, easy rollback, but costs double the resources temporarily. Canary release: Route a small percentage (1-5%) of traffic to new version. Monitor error rate, latency, business metrics. Gradually increase percentage. Roll back if metrics degrade. Minimizes blast radius of bad deployments. Feature flags: Deploy code with new feature disabled. Enable for specific users or percentage. Independent of deployment — decouple code release from feature release. Database migrations for zero-downtime: Never alter a column used by old code in one step. Use expand-contract (parallel change) pattern: 1. Add new column (nullable) — both old and new code work 2. Backfill data in new column 3. Deploy code using new column 4. Remove old column once old code is fully replaced Never: Remove a column/table that old deployed code still references.

Two Generals Problem: Two allied armies (Blue) want to attack an enemy (Red), but must attack simultaneously or fail. They can only communicate by sending messengers through Red's territory (messages can be captured/lost). No matter how many confirmations are sent, neither general can be certain the other received the last message and will attack. Formal result: It is provably impossible to achieve perfect agreement between two parties over an unreliable channel in a finite number of message exchanges. Lessons for distributed systems: 1. Perfect reliability is impossible: You cannot guarantee exactly-once delivery over an unreliable network. 2. Acknowledgments don't fully solve it: ACK itself can be lost. ACK of ACK also can be lost. Infinite regress. 3. Systems must accept uncertainty and design around it: • At-most-once: Don't retry (risk of non-delivery) • At-least-once: Retry with idempotency (risk of duplicates — handle with deduplication) • Exactly-once: Approximated via idempotent consumers + transactional producers (Kafka transactions), not truly guaranteed end-to-end 4. Timeouts are estimates: A timeout means "we don't know" — not "the operation failed." FLP impossibility: In an asynchronous system with even one faulty process, consensus is impossible — related theoretical result.

Core requirements: ACID transactions, idempotency, compliance (PCI DSS), exactly-once payment execution. Architecture: • Payment API: Accept payment requests, validate, generate idempotency key (client-provided) • Payment Service: Check idempotency store, if new → create pending payment in DB → call payment processor (Stripe, Braintree) • Idempotency Store: Redis (short-lived) + DB (permanent) keyed by client idempotency key → stored response • Ledger: Append-only double-entry bookkeeping (every debit has matching credit). Immutable transaction records. • Reconciliation: Nightly batch compares internal records with payment processor statements Security: Never store raw card numbers (PCI DSS). Tokenize via Stripe/Braintree. TLS everywhere. Field-level encryption for sensitive data. Failure handling: Payment processor call times out — status is UNKNOWN. Do NOT assume failure. Store as pending, query status via webhook or polling. Idempotency key prevents double charge on retry. Webhooks: Payment processors send async events (payment.succeeded, payment.failed). Verify signature, process idempotently. Audit: Every state change logged with timestamp and actor. Immutable audit trail for dispute resolution.

S — Single Responsibility Principle: A class should have only one reason to change. Each class handles one concern. Split classes that handle multiple unrelated concerns. O — Open/Closed Principle: Open for extension, closed for modification. Add new behavior by adding new code, not by changing existing code. Use abstraction, inheritance, composition. L — Liskov Substitution Principle: Subtypes must be substitutable for their base types without altering program correctness. If Square extends Rectangle and overrides setWidth, it violates LSP when code expects both dimensions to be independent. I — Interface Segregation Principle: Clients should not depend on interfaces they don't use. Prefer many small, specific interfaces over one large "fat" interface. D — Dependency Inversion Principle: High-level modules should not depend on low-level modules — both should depend on abstractions. Inject dependencies rather than creating them. Makes code testable and loosely coupled. Why they matter for system design: SOLID principles at class level naturally lead to modular, loosely coupled services at system level. Services that are single-purpose are easier to scale, deploy, and test independently.

Requirements: Return top-K suggestions as user types, < 100ms latency, support billions of queries. Data structure — Trie: Prefix tree where each node represents a character. Each node stores a sorted list of top-K completions weighted by historical query frequency. Queries traverse trie character by character — O(prefix length) lookup. Storage: For 5M unique terms, trie fits in memory (Redis or in-process). Pre-build offline, load into Redis hash or serve from in-memory trie in stateless service. Frequency computation: Real-time: Kafka pipeline counts search queries → aggregated in Flink → updates trie frequency weights. Batch: Nightly Spark job re-computes top-K per prefix from full query log. Ranking: Not just frequency — also freshness, personalization, trending topics, business rules (promoted terms). Caching: Cache top-K for common prefixes (a, ab, abc…). Invalidate on trie rebuild. CDN cache for anonymous users. API: GET /autocomplete?q=jav&limit=5 → ["java", "javascript", "java interview", ...] Alternative: Elasticsearch completion suggester (edge n-gram tokenizer) — simpler but less control over ranking. Redis ZRANGEBYLEX on a sorted set of terms also works for prefix scan.

Backpressure: When a fast producer sends data faster than a slow consumer can process it. Without backpressure handling, queues grow unboundedly until OOM or latency spikes. Strategies: 1. Block producer: Consumer signals producer to slow down (TCP flow control, Reactive Streams request model). Producer blocks when buffer full. Works in cooperative systems. 2. Drop messages: When buffer full, drop new messages. Acceptable for non-critical data (metrics, logs). Record drop count for monitoring. 3. Bound queues with rejection: Executor with bounded queue + rejection policy (CallerRunsPolicy in Java — caller thread does the work, slowing the producer naturally). 4. Reactive Streams (Project Reactor, RxJava): request(N) protocol — consumer explicitly requests N more items. Producer sends at most N. Operators like onBackpressureDrop, onBackpressureBuffer, onBackpressureLatest. 5. Scale consumers: Horizontal scaling. Add more consumer instances/partitions to match producer rate. 6. Rate limit producers: Throttle at ingestion point before the queue. Kafka backpressure: Consumer controls poll rate. If consumer is slow, lag grows. Alert on consumer lag. Scale consumer group or optimize processing.

Time-series database (TSDB): Optimized for storing and querying data points indexed by time. Each record is (timestamp, metric_name, tags, value). Why special databases: Time-series data has characteristics standard DBs handle poorly: write-heavy (millions of points/sec), mostly append-only, queries always include time range, old data can be compressed aggressively (downsampling), automatic retention policies. Optimizations: Columnar storage for high compression (same metric values are similar). Chunks of sequential timestamps. Delta encoding + Gorilla compression for timestamps and values. Automatic downsampling (1s → 1m → 1h as data ages). Popular TSDBs: • InfluxDB: Line protocol, Flux query language, built-in retention policies • Prometheus: Pull-based metrics scraping, PromQL, short retention (15 days default), pairs with Grafana • TimescaleDB: PostgreSQL extension — hypertables automatically partition by time, SQL queries still work • Clickhouse: Columnar OLAP, not specifically TSDB but excellent for time-series analytics at petabyte scale • OpenTSDB: Built on HBase for massive scale When to use: IoT sensor data, application metrics, financial tick data, monitoring, analytics. Not for: general-purpose CRUD, complex relational queries.

Circuit breaker: Wraps calls to external services. If failures exceed a threshold, "opens" the circuit — subsequent calls fail fast without attempting the remote call. After a timeout, enters "half-open" state to test if the service recovered. States: • CLOSED: Normal operation. Calls pass through. Track failures. If failures > threshold in window → open. • OPEN: Fail fast. Return fallback immediately. Start reset timer. • HALF_OPEN: Allow limited calls to probe recovery. If success → close. If failure → reopen. Key parameters: Failure rate threshold (e.g., 50%), minimum number of calls before evaluation, wait duration in open state, number of calls allowed in half-open state. Resilience4j implementation: ```java CircuitBreakerConfig config = CircuitBreakerConfig.custom() .failureRateThreshold(50) .waitDurationInOpenState(Duration.ofSeconds(30)) .build(); CircuitBreaker cb = CircuitBreakerRegistry.of(config).circuitBreaker("paymentService"); Supplier<String> decorated = CircuitBreaker.decorateSupplier(cb, this::callPayment); String result = Try.ofSupplier(decorated).recover(e -> fallback()).get(); ``` Fallback options: Cached response, default value, queue for later, graceful error message. Metrics: Monitor circuit state transitions, call success/failure rates, fallback activations.

Principles for safe migrations: 1. Never lock tables in production: Avoid ALTER TABLE that rewrites entire table (MySQL copies table → minutes of downtime). Use pt-online-schema-change or gh-ost for MySQL, or PostgreSQL's non-blocking alternatives. 2. Expand-contract pattern (parallel change): Phase 1 (expand): Add new column alongside old one — backward compatible. Phase 2: Dual-write to both. Phase 3: Backfill old data. Phase 4 (contract): Deploy code using only new column. Phase 5: Drop old column. 3. Always test migrations on production-size data copy: A migration that takes 1s on 1K rows may take hours on 100M rows. 4. Make migrations idempotent and reversible: Each migration has UP and DOWN. Tool: Flyway (sequential V1__init.sql), Liquibase (XML/YAML changesets). 5. Never add NOT NULL without a DEFAULT in one step: Add as nullable, backfill, then add constraint. 6. Monitor during migration: Watch replication lag, lock wait times, slow query log. 7. Have a rollback plan: Can you run the DOWN migration? Will it lose data? Test the rollback before deploying. 8. Separate schema migration from code deployment: Apply schema changes first, then deploy code that uses them.

CQRS (Command Query Responsibility Segregation): Separate the write model (commands) from the read model (queries). The same data store should not be optimized for both simultaneously. Write side (Command): Accepts commands (CreateOrder, UpdateStatus), validates, applies business rules, persists to write store, publishes events. Read side (Query): Listens to events from write side, updates denormalized projections optimized for specific queries. Can use a completely different data store (SQL write → Elasticsearch read). Why: Queries often need data from many entities joined together — expensive to compute at query time. Commands need strong consistency and validation. These needs conflict if using one model. Benefits: Scale reads and writes independently. Optimize read stores for specific access patterns. Multiple read models for different clients (mobile vs web). Event-driven updates to read side. Challenges: Eventual consistency — read model may lag behind write model. Increased complexity. Data duplication. Paired with Event Sourcing: Write side appends events. Read side replays events to build projections. Can rebuild any projection by replaying all events. Simple CQRS: Same DB, but separate service methods/classes for commands vs queries — no separate stores needed. Start here.

Defense in depth — multiple layers: Authentication: Verify identity. JWT (stateless — API verifies signature locally) or session tokens (stateful — check against session store). OAuth2/OIDC for third-party login. API keys for service-to-service. Authorization: Verify permissions. RBAC (role-based), ABAC (attribute-based), or scope-based (OAuth2 scopes). Enforce at service layer, not just gateway. Transport: TLS 1.2+ everywhere. HSTS header. Certificate pinning for mobile clients. Rate limiting: At API gateway — per user/IP/key. Prevents brute force, credential stuffing, DDoS. Input validation: Validate all input at boundary. SQL injection → parameterized queries. XSS → output encoding (for HTML responses). SSRF → whitelist outbound URLs. Secrets management: No credentials in code or config files. Use Vault, AWS Secrets Manager, Kubernetes secrets (encrypted). Rotate regularly. API Gateway: Central enforcement point — authentication, rate limiting, WAF (web application firewall). Logging & monitoring: Log all auth events, anomalies, access from unusual IPs. Alert on spike in 401/403 responses. Zero trust: Authenticate and authorize every service-to-service call, not just external clients. mTLS + service accounts.

Synchronous replication: Primary waits for acknowledgment from at least one replica before confirming the write to the client. Guarantees no data loss on primary failure — replica has the latest data. Cost: Added latency (network round trip to replica). If replica is slow or unreachable, writes stall. Availability tradeoff — primary must wait for replica. Use when: Financial transactions, user data where data loss is catastrophic. PostgreSQL synchronous_commit = on. Semi-synchronous in MySQL. Asynchronous replication: Primary confirms write to client immediately. Replica receives changes independently, with replication lag. Lag can range from milliseconds to seconds (or more under load). Cost: Potential data loss on primary failure — writes acknowledged but not yet replicated may be lost. Replicas may serve stale reads. Use when: Read replicas for scale (users read slightly stale data — acceptable), geographic replicas where latency to remote data center makes sync impractical. Most MySQL read replicas use async replication. Semi-synchronous: Write confirmed once at least one replica acknowledges receipt (not necessarily fsync). Balance between sync and async — reduces data loss window without full sync latency. Raft/Paxos: Consensus protocols that commit only when a majority of nodes acknowledge — effectively synchronous to quorum.

Requirements: Ingest 10M events/sec, process in near-real-time, support historical ad-hoc queries. Lambda architecture (or Kappa): • Speed layer: Kafka → Flink stream processor → Real-time aggregates in Redis/Druid. Answers "events in last 5 minutes." • Batch layer: Kafka → S3 (raw event store) → Spark batch jobs → Parquet files in S3 → Queryable via Athena/Presto. Complete, accurate historical analysis. • Serving layer: Combines speed + batch results. Kappa architecture (simpler): Single Kafka stream → Flink processes everything → Output to queryable store. Reprocess by replaying Kafka. Preferred for most modern systems. Storage: Raw events in S3 Parquet (columnar — 10× cheaper queries than row-based, 10× more compressible). Partition by date/hour for efficient time-range scans. OLAP engine: Druid or Clickhouse for sub-second analytics queries on billions of rows. Pre-aggregate common dimensions. Event schema: Use Apache Avro or Protobuf with schema registry. Compact, versioned, fast serialization. Sampling: For ultra-high volume (logs, trace spans), sample 1-10% for analytics. Use consistent hash sampling to preserve user-level journeys.

Chaos engineering: Deliberately injecting failures into a production (or production-like) system to discover weaknesses before they cause real incidents. "Break things on purpose to learn how to prevent them." Origin: Netflix Chaos Monkey (randomly terminates EC2 instances) evolved into Chaos Engineering discipline. Principles (from Chaos Engineering book): 1. Define a "steady state" — what normal looks like (error rate, latency, throughput) 2. Hypothesize that steady state continues during experiment 3. Introduce real-world variables (server crash, network latency, disk full, dependency outage) 4. Disprove the hypothesis by finding a degradation 5. Run experiments in production, but start small Failure types to inject: • Instance/pod termination (Chaos Monkey) • Network latency or packet loss between services • CPU/memory exhaustion • Dependency (database, external API) slowdown or outage • Clock skew Tools: Chaos Monkey (Netflix), Gremlin (commercial), LitmusChaos (Kubernetes), AWS Fault Injection Simulator. Game Days: Scheduled exercises where on-call team responds to injected failures. Builds muscle memory. Pre-requisites: Good observability, runbooks for common failures, automatic remediation where possible.

Connection pool: Pre-creates and reuses DB connections. Acquiring a new DB connection is expensive (TCP handshake, auth, SSL). Pooling amortizes this cost. HikariCP (Spring Boot default): Ultra-fast, minimal overhead, battle-tested. Key parameters: • maximumPoolSize: Maximum connections in pool. Too many → DB overwhelmed (DB has its own max_connections limit). Too few → requests queue waiting for connection. • minimumIdle: Minimum idle connections kept alive. Set equal to maximumPoolSize for fixed-size pool (HikariCP recommendation). • connectionTimeout: Max time to wait for a connection from pool before throwing exception (default 30s). • idleTimeout: How long idle connections are kept before being closed (default 10 min). • maxLifetime: Maximum lifetime of a connection (default 30 min). Rotate before DB kills it. Formula (HikariCP): connections = (core_count × 2) + effective_spindle_count. For 4 CPU cores, SSD: 4×2+1 = 9. Not a hard rule — benchmark for your workload. Symptoms of misconfiguration: • Too small: HikariCP connection timeout errors, requests queuing • Too large: DB CPU spikes, connection refused, context switching overhead Monitor: Pool size, active connections, idle connections, connection wait time (Micrometer metrics available).

Access control models: DAC (Discretionary AC): Resource owner grants permissions to others. File system permissions (chmod). Simple but decentralized — hard to audit. MAC (Mandatory AC): System enforces security labels. Military systems. Very rigid. RBAC (Role-Based AC): Users have roles; roles have permissions. User → Role → Permission. User may have multiple roles. Most common in enterprise software. Roles: Admin, Editor, Viewer. ABAC (Attribute-Based AC): Policies based on attributes of subject, resource, environment. "Allow if user.department = resource.department AND time = businessHours." More expressive than RBAC. Used in complex, fine-grained access scenarios. ReBAC (Relationship-Based AC): Access determined by relationships between entities. "User can edit document if user is member of owner group." Google Zanzibar model. Powers Google Drive sharing. Scales to trillions of relationships. Implementation: • DB schema: users, roles, user_roles, permissions, role_permissions tables • API: JWT claims carry role/scope. Service checks permission on each request. • Caching: Cache permission checks in Redis (user_id:resource:action → allow/deny) with short TTL. • Audit: Log every access decision (who, what, when, allow/deny). OpenFGA, OPA (Open Policy Agent), Casbin: Libraries for RBAC/ABAC policies.

Core challenge: Execute untrusted user code safely on your infrastructure. Security: This is the #1 concern. User code can attempt to: read files, make network calls, consume all CPU/memory, fork-bomb, escape the sandbox. Sandbox layer: Execute each submission in an isolated container (Docker, gVisor, Firecracker microVM). Network disabled inside container. Resource limits: CPU time (2s), memory (256MB), max processes (fork bomb prevention). Read-only filesystem (except /tmp). Non-root user inside container. Kill container after timeout. Architecture: 1. User submits code → API stores to DB, enqueues to Kafka/SQS 2. Execution worker pulls job, spins up container (from pre-warmed pool), runs code against test cases 3. Captures stdout/stderr, compares against expected output 4. Records result (AC, WA, TLE, MLE, RE) to DB 5. Pushes result to user via WebSocket or long-poll Container pool: Pre-warm language containers (Java, Python, Go) to reduce cold start. Return container to pool after use (or discard and get fresh one for security). Test case storage: Store test input/expected output in S3. Worker downloads per execution. Scaling: Workers are stateless — scale horizontally. Autoscale based on queue depth.

SLI (Service Level Indicator): A quantitative measure of service quality. The actual metric you observe. Examples: availability (% successful requests), latency (99th percentile response time), error rate (% of requests returning 5xx), throughput (requests/sec). SLO (Service Level Objective): An internal target for an SLI. Your engineering team's promise to itself. Examples: "99.9% of requests respond in < 200ms," "Error rate < 0.1%," "Availability > 99.95%." SLA (Service Level Agreement): A legal contract with customers. Usually less strict than your SLO (buffer). Defines remedies if breached (refunds, credits). Example: "We guarantee 99.9% uptime. If we fall below, customers receive 10% credit." Error budget: 100% - SLO = allowed downtime. 99.9% SLO = 0.1% error budget = 8.7 hours/year. If error budget is consumed, slow down feature releases and focus on reliability. Practice: Set SLOs tighter than SLA. Alert before breaching SLO. Review SLOs quarterly. Avoid vanity SLOs that don't correlate with user experience. Golden signals (Google SRE): Latency, Traffic, Errors, Saturation — monitor these four for any service.

End-to-end request flow (e-commerce order example): 1. Client sends POST /orders via HTTPS 2. DNS → CDN (static, skip) → Load Balancer (L7) selects a healthy instance 3. API Gateway: Authenticate JWT, check rate limit, route to Order Service 4. Order Service receives request: a. Validate input (schema, business rules) b. Call Inventory Service (sync gRPC) to check stock c. Call Product Service (sync) to get pricing d. Write order to PostgreSQL (ACID transaction) e. Publish OrderCreated event to Kafka 5. Downstream async consumers handle event: a. Payment Service: Charge customer, publish PaymentSucceeded/Failed b. Notification Service: Send confirmation email c. Analytics Service: Record order event d. Warehouse Service: Reserve inventory 6. Order Service returns 201 Created to API Gateway → Client Cross-cutting concerns: • Distributed tracing: trace-id propagated in headers across all calls (W3C TraceContext) • Circuit breakers on all sync calls • Structured logging with correlation ID • Timeout on every external call • Service discovery via Kubernetes DNS or Consul This illustrates sync-for-immediate-response + async-for-downstream-work.

Hot partition: When most traffic concentrates on a single partition (database shard, Kafka partition, cache key), overwhelming that partition while others are idle. Database sharding example: User table sharded by user_id first letter. Users starting with "A" are 5× more common → shard A is overloaded. Range-based sharding on sequential IDs → latest shard gets all writes. Solutions for database: • Hash-based sharding: Distribute based on hash(user_id) — distributes evenly • Composite shard key: Include random component or secondary attribute • Consistent hashing: Distributes evenly and minimizes rebalancing • Resharding: Split hot shard into multiple shards Kafka hot partition: Celebrity user event goes to the same partition (keyed by user_id). Other partitions idle. Solutions for Kafka: • Add random suffix to key for write-heavy producers: user_id + random(0,N) → spread across N partitions → aggregate at consumer • Pre-partition by category: Separate topics for celebrity vs normal users • Null key: Round-robin across all partitions (loses ordering guarantee) Cache hot key: Single Redis key (viral product, trending news) → single node overwhelmed. Solutions for cache: • Local application-level cache (L1) for hottest keys • Key replication: Copy hot key to multiple Redis keys with suffix, randomly select on read • Increase replication factor for hot keyspace • Read-through sharding across multiple Redis nodes

Multi-tenancy: Single software instance serving multiple customers (tenants), with data isolation between them. Isolation models: 1. Silo (separate DB per tenant): Complete isolation. Simple query (no tenant filter needed). Most expensive — O(N) DB instances. Best for enterprise customers needing compliance/data sovereignty. 2. Bridge (shared DB, separate schema): One schema per tenant in same DB. Schema = namespace. Good isolation, simpler ops than silo. Schema migrations must run per-tenant. 3. Pool (shared DB, shared tables): All tenants in same tables with tenant_id column. Most resource-efficient. Must include tenant_id in every query and every index. Risk: missing tenant filter = data leak. Best practices for pool model: • Row-Level Security (PostgreSQL RLS): DB enforces tenant_id filter automatically — can't accidentally miss it • Always include tenant_id in composite indexes: (tenant_id, created_at) not just (created_at) • Separate connection pools per tenant for noisy neighbor prevention • Tenant-aware caching: prefix all cache keys with tenant_id • Rate limit per tenant, not just per IP Deployment isolation: Kubernetes namespaces per tier. Dedicated node pools for premium tenants. Tenant onboarding: Automated provisioning pipeline. Schema migration on silo/bridge. Record creation on pool.

Tail latency: The latency experienced by a small percentage of requests — typically p99, p999, or p9999 (99th, 99.9th, 99.99th percentile). Average and median latencies can look healthy while tail latency is terrible. Why it matters: In a microservices system with 10 services, each with 99th percentile latency at 100ms, the probability that at least one call hits p99 is 1 - (0.99)^10 = 9.6%. Nearly 1 in 10 end-user requests is slow due to serial calls hitting someone's p99. Causes of high tail latency: • GC pauses (JVM Stop-the-World) • Kernel scheduling jitter • CPU throttling in containers (CFS bandwidth throttle) • Thread pool exhaustion — request queues in thread pool • Lock contention • Cold starts (first request after idle) • Connection pool starvation Solutions: • Hedged requests: Send same request to 2 instances simultaneously after a short wait. Take whichever responds first. Reduces tail latency at cost of slightly more load. • Timeout + retry with fresh instance: Give up on slow node, retry elsewhere • G1GC / ZGC: Low-pause GC collectors reduce GC tail latency • CPU pinning / reduced preemption for latency-critical services • Warm-up: Send synthetic traffic before real traffic to JIT-compile hot paths Measure: Always track p99 and p999 in SLOs, not just average.

Availability: The percentage of time a system is operational and able to process requests. Formula: Availability = Uptime / (Uptime + Downtime) 99.9% ("three nines") = 8.7 hours downtime/year 99.99% ("four nines") = 52 minutes downtime/year 99.999% ("five nines") = 5.25 minutes downtime/year Reliability: The probability that a system performs its required function correctly over a specified time period, without failure. Includes correctness of output, not just availability. A system can be available but unreliable: Service returns 200 OK but with wrong data. Cache returns stale data. Calculation produces incorrect results. A system can be reliable but not highly available: Runs perfectly but scheduled downtime for maintenance. Mean Time To Failure (MTTF): Average time between failures. Mean Time To Repair (MTTR): Average time to restore service after failure. Availability = MTTF / (MTTF + MTTR) Improving availability: Redundancy, auto-failover, load balancing, health checks, auto-scaling, chaos engineering to find failure modes. Improving reliability: Testing, idempotency, data validation, monotonic versioning, CRDTs, formal verification for critical systems.

Requirements: Sub-millisecond reads, globally distributed, high availability, eventual consistency acceptable. Architecture: Multi-region active-active cluster. Each region accepts reads and writes. Async replication between regions. Data model: Key → {value, version/timestamp, region, TTL}. Use last-write-wins (LWW) or CRDTs for conflict resolution. Replication: Write locally → replicate to other regions asynchronously. Region failure: other regions continue serving. Replication lag: typically 50-200ms between continents. Consistency options per read: • Local read: Read from nearest region. Fastest. May be stale. • Linearizable read: Route to primary region. Accurate but adds latency. • Read quorum: Wait for majority of regions to agree. Middle ground. Technology options: • DynamoDB Global Tables: Multi-region active-active. LWW conflict resolution. 5ms p99 reads. • Cassandra: Configure DC-aware replication, LOCAL_QUORUM consistency. • Redis Enterprise: Active-Active geo-distribution with CRDT-based conflict resolution. • CockroachDB: Distributed SQL, strong consistency, higher latency than eventual. GeoDNS / Anycast: Route clients to nearest region automatically. Partitioning: Consistent hashing across nodes within each region. Automatic rebalancing on node add/remove.

N+1 problem: Execute 1 query to fetch N records, then execute N additional queries to fetch related data for each record. 1+N queries total — scales linearly and kills DB performance. Example: Fetch 100 orders (1 query), then for each order fetch the user (100 queries) = 101 DB round trips instead of 2. SQL solutions: • JOIN: SELECT * FROM orders o JOIN users u ON u.id = o.user_id. Single query. • IN clause: Collect all user IDs from orders, then SELECT * FROM users WHERE id IN (id1, id2, ...). 2 queries. JPA/Hibernate solutions: • EAGER fetching: Fetch associations with JOIN automatically. Risks: always fetches even when not needed, cartesian product with multiple collections. • @EntityGraph: Specify exactly which associations to fetch eagerly per query. • @BatchSize: Hibernate fetches lazy associations in batches of N (fetch N associations in one query instead of N). • JOIN FETCH in JPQL: SELECT o FROM Order o JOIN FETCH o.user — explicit join. Detection tools: Hibernate statistics (show_sql, format_sql), p6spy, datasource-proxy (log + count queries per request). Alert if query count per request > threshold. General rule: Every API endpoint should execute O(1) queries, not O(N).

Core challenge: Prevent double booking while handling high concurrent search and booking traffic. Search: Property listings stored in Elasticsearch (search by location, price, amenities, dates). Geospatial search (geo_distance query). Filter by availability (check calendar table). Availability calendar: Table: availability(property_id, date, status). Status: available/booked/blocked. Booking flow: 1. User selects dates → check availability (read from DB, cache in Redis per property+dates) 2. User initiates booking → optimistic lock on availability rows 3. Payment authorization 4. On payment success: mark dates as booked in DB, charge payment, send notifications 5. On payment failure: release lock, dates remain available Preventing double booking: • Pessimistic lock: SELECT ... FOR UPDATE on availability rows. Serializes bookings per property. • Unique constraint: (property_id, date) with status=booked prevents two bookings for same date at DB level. • DBLOCK: Advisory lock on property_id during booking flow. Inventory: Unlike products, "stock" = calendar slots. Each slot is either available or not — natural idempotency. Pricing: Dynamic pricing engine (demand-based, season, local events) — separate read service, cached per property. Search consistency: Availability changes propagate to Elasticsearch via CDC or event bus (eventual consistency — acceptable for search).

Forward proxy: Sits in front of clients. Clients send requests to proxy, proxy forwards to external servers. Server sees proxy's IP, not the client's. Use cases: • Corporate firewall: Control which sites employees can access • Anonymity: Hide client IP (VPN, Tor) • Caching: Cache external content for internal users (reduce bandwidth) • Content filtering: Block categories of sites Examples: Squid proxy, corporate web filters, VPN clients. Reverse proxy: Sits in front of servers. Clients send requests to proxy, proxy routes to backend servers. Client sees proxy's IP, not the server's. Use cases: • Load balancing: Distribute requests across server pool • SSL termination: Handle HTTPS at proxy, HTTP to backend • Caching: Cache responses from backend servers (Nginx micro-caching) • Compression: gzip/brotli compression at proxy layer • Security: Hide backend server topology, WAF, rate limiting • A/B testing: Route traffic split to different versions Examples: Nginx, HAProxy, Cloudflare, AWS ALB, Traefik. Key distinction: Forward proxy serves the client's privacy/access needs. Reverse proxy serves the server operator's infrastructure needs.

Stateless service: Each request is independent. Service holds no memory of past requests. Any instance can handle any request. Session/user data lives in external store (DB, Redis, JWT token). Benefits of stateless: Horizontally scale by adding instances freely. Load balancer can route to any instance. Instance crash loses no session data. Deployments: replace instances without session loss. Auto-scaling is simple. Example: A REST API that authenticates via JWT (token carries user context). Any instance validates the JWT and processes the request. Stateful service: Service holds state in memory across requests. Specific client must always reach the same instance. Challenges: Scaling requires sticky sessions (client affinity at load balancer). Instance failure → state lost. Harder to deploy (drain connections, migrate state). Where stateful is necessary: WebSocket chat servers (connection state), gaming servers, stateful stream processors (Kafka Streams), leader election nodes, databases. Handling stateful services at scale: • Sticky sessions: Load balancer routes by session ID or cookie to same instance • Externalize state: Move state to Redis/DB, making service stateless • Stateful sets: Kubernetes StatefulSet provides stable identity and storage for stateful pods Design principle: Prefer stateless microservices. Isolate stateful components.

Approaches: Collaborative Filtering: "Users like you also liked X." Based on user-item interaction matrix. • User-based: Find similar users, recommend what they liked • Item-based: Find similar items to what user liked (Amazon's item-to-item CF) • Matrix Factorization (ALS, SVD): Decompose user-item matrix into latent factors. Scalable with Spark MLlib. Content-based filtering: Recommend items similar to what user has shown interest in. Based on item features (genre, tags, description embeddings). No cold-start for items with rich metadata. Hybrid: Combine collaborative + content-based. Netflix, Spotify use ensemble models. Deep Learning: Two-tower neural network (YouTube, Pinterest): User tower encodes user history → user embedding. Item tower encodes item features → item embedding. Dot product = relevance score. Train on clicks/purchases. Retrieval + Ranking: 1. Retrieval: Approximate Nearest Neighbor search (FAISS, ScaNN) to find top-1000 candidate items from embedding space in milliseconds 2. Ranking: Expensive ML model scores all 1000 candidates on detailed features → top-N Serving: Pre-compute recommendations for all users nightly (batch). Refresh in real-time for recent interactions. Store in Redis (userId → [itemId1, itemId2, ...]). Cold start: New user → popular items or onboarding survey. New item → content-based until enough interactions.

Read-your-writes (RYW): After a user writes data, subsequent reads by the same user will always reflect that write, even if reading from a replica that may not yet have the update. Problem without RYW: User updates profile picture → write goes to primary → reads load-balanced to replica → replica hasn't received the update yet → user sees old profile picture immediately after updating it. Confusing and frustrating user experience. Implementations: 1. Read from primary after write: After any write operation, route subsequent reads from that user to the primary for a short window (e.g., 1 minute). Simple but increases primary read load. 2. Track write timestamps: Client receives a timestamp/version token after write. Attach token to subsequent reads. Replica waits until it has replicated at least to that version before serving the read (or routes to primary). 3. Sticky sessions: Route all of a user's traffic to the same server (which reads from primary or its own consistent view). Session-based routing. 4. Client-side caching: Client remembers what it wrote and serves it from local cache for a window, regardless of what server returns. When to guarantee: User profile updates, settings changes, financial balances. Not always needed for global feeds or analytics where slight staleness is acceptable.

Requirements: Return suggestions in < 100ms as each character is typed. Personalized and trending suggestions. Approach 1 — Redis Sorted Set prefix scan: • For each searchable term, store all prefixes: for "java" → store "j", "ja", "jav", "java" in a sorted set with score = frequency • ZRANGEBYLEX key "[ja" "[ja\xff" LIMIT 0 5 returns all terms with prefix "ja" • Ultra-fast, in-memory, sub-millisecond. Good for autocomplete with known vocabulary. Approach 2 — Trie with top-K: • Build trie from query log. Each node stores top-K most frequent completions for that prefix. • Serve from in-memory trie (single-server can hold millions of terms). Refresh hourly from updated frequency data. • Optimal for fixed vocabulary (product names, known queries). Approach 3 — Elasticsearch completion suggester: • Define field as completion type. Add weights. ES uses FST (finite state transducer) for O(prefix length) lookup. • Good for open-vocabulary, full-featured search integration. Caching: CDN-cache top 1000 prefixes (short TTL). Client-side: debounce input (wait 150ms after keypress), deduplicate in-flight requests. Ranking signals: Global query frequency, user's personal history, trending queries (recency-weighted), geographic relevance.

gRPC is built on HTTP/2 and supports four communication patterns: 1. Unary: Client sends one request, server sends one response. Standard request-response like REST. Use for: most CRUD operations. rpc GetUser(UserRequest) returns (UserResponse); 2. Server streaming: Client sends one request, server sends a stream of responses. Use for: real-time feeds, large dataset pagination, live updates. rpc GetOrderUpdates(OrderId) returns (stream OrderStatus); 3. Client streaming: Client sends a stream of requests, server sends one response. Use for: file upload, batch data ingestion, aggregation of many inputs. rpc UploadChunks(stream FileChunk) returns (UploadResult); 4. Bidirectional streaming: Both client and server send streams independently. Use for: real-time chat, collaborative editing, live multiplayer games. rpc Chat(stream ChatMessage) returns (stream ChatMessage); HTTP/2 advantages enabling streaming: • Multiplexing: Multiple streams over one connection — no head-of-line blocking • Flow control per stream • Header compression (HPACK) • Binary framing — efficient for Protocol Buffers Implementation: Handle stream in a loop on both sides. Use stream.onNext(), stream.onCompleted(), stream.onError() in the observer pattern.

Direct server upload problems: Files can be gigabytes. Server memory and connection timeout issues. Single point of failure. Server bandwidth saturated. Multipart / chunked upload: 1. Client splits file into chunks (e.g., 5MB each) 2. Upload each chunk independently with chunk index 3. Server reassembles on completion or uses S3 multipart upload API Presigned URL approach (recommended): 1. Client requests presigned URL from your API 2. API generates S3 presigned PUT URL (valid 15 min) 3. Client uploads directly to S3 — bypasses your servers entirely 4. S3 notifies your API via S3 Event → Lambda/SQS when upload complete 5. API records metadata, triggers processing pipeline Benefits: Your servers handle no file bytes. S3 handles scale. Reduces your infrastructure cost significantly. Resumable uploads (Google Resumable Upload API pattern): 1. Initiate upload session → get upload URL and session ID 2. Upload chunks with byte range headers (Content-Range: bytes 0-4999999/50000000) 3. On network failure, query server for how many bytes received, resume from there Progress: Track upload progress via XHR/fetch ProgressEvent on the client. Server-side: chunk completion events. Post-upload processing: Virus scan (ClamAV), image resize, video transcoding — done async via worker queue, not in the upload request.

High write throughput challenges: DB becomes the bottleneck. Writes block reads. Replication lag increases. Disk I/O saturates. Strategies: 1. Write buffering / batching: Collect writes in memory and flush periodically. Trade: risk of data loss on crash. Use case: metrics, logs, analytics (not financial transactions). 2. Message queue as write buffer: Writes go to Kafka instantly (very fast). Consumers write to DB asynchronously at their own pace. Decouples write burst from DB capacity. 3. Write-optimized DB: Cassandra uses LSM tree (Log-Structured Merge tree) — writes always sequential (fast), reads merge multiple levels (slower). Optimized for write-heavy workloads. 4. Sharding: Distribute writes across multiple DB nodes. Each shard handles subset of data. 5. Denormalization: Avoid expensive JOIN updates. Duplicate data to make writes simpler (no cascading updates). 6. Async writes with eventual consistency: Write to cache (Redis), acknowledge to client, persist to DB asynchronously. Risk: data loss on cache failure. 7. Connection pooling: HikariCP to reuse DB connections efficiently. 8. Bulk inserts: INSERT ... VALUES (row1), (row2), ... instead of individual inserts. Order of magnitude faster. 9. Disable autocommit: Batch multiple writes in one transaction to reduce commit overhead.

Monolith deployment: Single deployable artifact (JAR, WAR, container). All modules deployed together. Atomic — either all changes deploy or none. Simple CI/CD — one pipeline, one artifact. Risks: Any change (even a small bug fix) requires full redeploy. One bug can take down the entire application. Large artifact = longer build and deploy times. Microservices deployment: Each service is an independent deployable unit. Services deployed on their own schedule. A bug in Service A doesn't affect Service B. Each team owns their pipeline. Challenges: • Coordination: When multiple services must change together (e.g., API contract change), deployment order matters. Consumer-driven contracts help. • Versioning: Old and new service versions may run simultaneously during rolling deploy — must maintain backward compatibility. • Environment parity: Each service needs its own staging environment. Much more infrastructure. Container orchestration (Kubernetes): Enables rolling updates, canary releases, health-based rollback for each service independently. Namespace per service or per team. CI/CD patterns: • GitOps: Kubernetes manifests in Git repo. ArgoCD/Flux syncs cluster to Git state. • Service mesh canary: Istio splits traffic 95/5 between versions, automatically promote or rollback based on error rate. Key: Microservices deployment complexity is real overhead — only justified when the team independence and scaling benefits outweigh it.

Disaster recovery (DR): Plan for recovering from catastrophic failures — data center outage, cloud region failure, accidental data deletion, ransomware. Key metrics: • RTO (Recovery Time Objective): How long can the business be down? (1 hour? 4 hours?) • RPO (Recovery Point Objective): How much data can be lost? (0 = no loss, 1 hour = up to 1 hour of data may be lost) Strategies (cost vs RTO/RPO tradeoff): 1. Backup and restore: Regular DB backups to S3 + cross-region replication. Lowest cost. Highest RTO (hours to restore). Acceptable for non-critical systems. 2. Pilot light: Core infrastructure running in DR region at minimal scale (DB replica running, app servers stopped). On disaster, start app servers, point DNS to DR. RTO: 10-30 minutes. 3. Warm standby: Scaled-down but fully functional copy running in DR region. Handles reduced load immediately. Scale up on disaster. RTO: minutes. 4. Hot standby / Active-active: Full traffic in both regions simultaneously. DNS failover on disaster. RTO: seconds. Most expensive. Requires data sync between regions. Implementation: Cross-region S3 replication. DB async replication to DR region. Infrastructure as code (Terraform) to rebuild environment quickly. Route53 health-based failover. Regular DR drills. Chaos testing: Simulate region failure regularly to validate RTO/RPO targets.

Thundering herd: When many processes/threads simultaneously wake up and compete for a resource, causing a burst of load that overwhelms the system. Common scenarios: 1. Cache expiry stampede: Popular cache key expires. Hundreds of requests simultaneously miss the cache, all go to DB, compute the same result, all write the same value back. DB sees 100× normal load for that key. Solutions: • Mutex/lock: Only one thread fetches from DB on cache miss. Others wait for the lock and then read the freshly populated cache value. • Probabilistic early expiration: Before TTL expires, randomly start refreshing the cache in the background. No simultaneous expiration. • Stale-while-revalidate: Return stale cached value immediately, refresh in background. • Jitter: Add random offset to TTL so keys don't all expire simultaneously. 2. Service restart: After a service restarts, all connection retries from clients happen simultaneously. Solutions: • Exponential backoff with jitter: Retry delay = base × 2^attempt + random(0, base). Spreads retries over time. • Circuit breaker: Prevents all retries from hammering recovering service. 3. Thread pool / epoll wakeup: Linux kernel's "accept() thundering herd" — multiple processes waiting on same socket wake on new connection. Solved in kernel 3.19 with SO_REUSEPORT.

Vector clock: A mechanism for tracking causal relationships between events in a distributed system. Determines whether event A happened before, after, or concurrently with event B — without a global clock. Structure: Each node maintains a vector V[n] where n = number of nodes. V[i] = number of events node i has processed. Rules: • Local event: Increment your own counter: V[self]++ • Send message: Attach current vector clock to message • Receive message: Take element-wise maximum of received clock and local clock, then increment own: V[i] = max(V_local[i], V_received[i]) for all i; V[self]++ Comparing events: • A happened-before B: if A.V[i] ≤ B.V[i] for all i and A.V[j] < B.V[j] for some j • Concurrent: neither happened-before the other (A.V[i] > B.V[i] for some i AND A.V[j] < B.V[j] for some j) Use cases: • Conflict detection: DynamoDB uses version vectors. Two concurrent writes that can't be merged → conflict, surface to application for resolution. • Cassandra: Uses timestamps (not true vector clocks) — LWW. Vector clocks give better causality tracking. • Distributed debugging: Understand causal ordering of events across nodes. Limitation: Vector grows with number of nodes. Dynamo uses dotted version vectors for compaction.

Monorepo: All projects, services, and libraries in a single version-controlled repository. Advantages: • Atomic commits across services: Change API contract in service A and update consumers B and C in one commit • Shared code: Common libraries (auth, logging, models) are easy to reference and update • Unified CI/CD: One toolchain, consistent versions • Easier refactoring: Move code between services, rename interfaces across the codebase in one PR • Dependency graph visible: See what depends on what Disadvantages: • Scale: Git operations slow with thousands of files. Need tools like Bazel, Turborepo, Nx for affected-only builds and caching. • CI: Full CI is slow — need incremental builds (only build/test changed services) • Access control: Harder to restrict access to specific services • Onboarding: Overwhelming for new engineers Polyrepo: Each service in its own repository. Advantages: • Clear ownership per repo. Granular access control. • Independent build times. Smaller repositories. Disadvantages: • Cross-service changes require multiple PRs, harder to coordinate • Dependency drift: Services use different versions of shared libraries • Discovery: Harder to find all services Tools for monorepo at scale: Bazel (Google), Buck (Meta), Nx, Turborepo, Pants. All support incremental builds and remote caching. Who uses monorepos: Google (Piper), Meta (Mercurial monorepo), Twitter, Airbnb, Stripe.

The fundamental challenge: Each microservice has its own database. Distributed transactions (2PC) are impractical. So how do you keep data consistent? Strategies: 1. Saga pattern: Sequence of local transactions with compensating transactions for failures. Eventual consistency. Best for multi-service workflows. 2. Outbox pattern: Write business record + event atomically to own DB. Message relay publishes event. Guarantees at-least-once delivery. 3. Idempotent consumers: Design every event consumer to safely process the same event multiple times (use event_id for deduplication). Handles Kafka redelivery. 4. Accept eventual consistency: Define which data can be "eventually consistent" (e.g., order count in user profile — slight lag OK) vs "strongly consistent" (e.g., account balance — must be exact). 5. Domain boundaries: Define service boundaries so most transactions stay within a single service. Cross-service transactions should be rare. Poor boundaries = constant distributed transaction pain. 6. Shared DB (anti-pattern for true microservices): Services share a DB for atomic transactions. Simple but coupling — teams can't change schema independently. 7. API composition: Query multiple services and merge results in application. For reads, eventual consistency is usually acceptable — stale reads are fine. 8. Conflict detection: Version numbers, ETags, optimistic locking for concurrent updates. Surface conflicts to application layer for resolution.

Batch processing: Process a bounded, finite dataset in bulk. Run periodically (nightly, hourly). High latency — results available only after full batch completes. High throughput — can optimize for bulk operations. Examples: Nightly billing calculation, daily report generation, weekly ML model retraining, ETL from OLTP to data warehouse. Tools: Apache Spark, Hadoop MapReduce, AWS Glue, Apache Beam in batch mode. Stream processing: Process an unbounded, continuously arriving data stream in real-time (or near-real-time). Low latency — results available seconds after events arrive. State is maintained between events (windowing, aggregations). Examples: Fraud detection, real-time analytics dashboards, recommendation updates, IoT sensor alerting, CDC propagation. Tools: Apache Flink, Kafka Streams, Apache Spark Streaming, Apache Beam (unified), Kinesis Data Analytics. Windowing in stream processing: • Tumbling window: Fixed, non-overlapping windows (events per minute) • Sliding window: Overlapping windows (events in last 5 minutes, updated every 1 minute) • Session window: Group events by inactivity gap (user session) Lambda architecture: Both batch and streaming. Batch for accuracy, streaming for low latency. Merge results in serving layer. High complexity. Kappa architecture: Streaming only. Reprocess historical data by replaying Kafka. Simpler but stream processor must handle reprocessing semantics.

Mobile and web clients have different constraints requiring different API design decisions. Mobile-specific challenges: • Limited and variable bandwidth: Binary protocols (gRPC/protobuf) or compressed JSON. Response field filtering: only return fields the client needs (GraphQL or sparse fieldsets). • Unreliable network: Retry logic with idempotency keys. Offline support: sync last-known state, apply delta updates. • Battery: Reduce polling — use WebSockets, SSE, or push notifications (APNs/FCM) instead. • App versions: Old app versions in production for months. APIs must support N-2 versions minimum. Never break backward compatibility. • Latency: Users expect < 200ms. Minimize round trips — aggregate multiple API calls into one (BFF pattern). Backend For Frontend (BFF) pattern: Separate API layer per client type (mobile BFF, web BFF). Mobile BFF aggregates calls, transforms, compresses for mobile constraints. Web BFF can return richer data. Each BFF team works independently without blocking the core services. GraphQL: Client specifies exactly the fields it needs. Reduces over-fetching. Single endpoint. Good for multiple different client needs (mobile = minimal fields, web = rich data). Tradeoffs: N+1 risks, complex caching, requires dataloader. Versioning: URL-based versioning (/api/v2) for major breaking changes. Additive changes are backward compatible.

Message broker: Middleware that receives messages from producers and routes them to consumers. Decouples producers from consumers in time, space, and semantics. Core functions: • Routing: Direct messages to correct consumers based on topic, queue, routing key • Buffering: Absorb traffic spikes — broker accepts bursts that consumers process at their own pace • Delivery guarantees: At-most-once, at-least-once, or exactly-once delivery depending on configuration • Persistence: Store messages durably until consumers acknowledge • Fan-out: One message delivered to multiple consumers (pub-sub) Event-driven patterns enabled by brokers: • Pub-Sub: OrderCreated event published to topic → Payment, Inventory, Notification services each consume independently • Event sourcing: All state changes as events in broker (Kafka as event log) • CQRS: Commands → write store events → broker → read projections updated • Saga: Broker orchestrates saga steps via events between services Kafka as event log: Persistent, replayable, ordered within partition. Multiple independent consumer groups. Compacted topics for latest-value-per-key semantics. RabbitMQ as message broker: Exchange routing (direct, fanout, topic, headers). Queue bindings. Messages deleted after ack. No replay by default. Broker guarantees durability (fsync), high availability (replication), and delivery tracking (consumer offset/ack).

Capacity planning: Estimate compute, storage, and network resources needed to handle projected load at acceptable performance. Step 1 — Define traffic characteristics: • Reads vs writes ratio (e.g., 100:1 read-heavy) • Peak QPS (estimate daily active users × actions/user/day ÷ seconds/day) • Data volume: messages/requests × average payload size • Growth rate: 2× per year? Traffic spikes (marketing events, seasonal)? Step 2 — Benchmark single-instance capacity: • What can one DB server handle? (PostgreSQL: ~10K simple queries/sec) • What can one app server handle? (depends on CPU, thread pool, I/O) • What is single Redis instance throughput? (~100K ops/sec) Step 3 — Calculate required instances: • instances = peak_QPS / single_instance_capacity × headroom_factor (2×) • Add buffer for failures (N+1 or N+2 redundancy) Step 4 — Storage estimation: • daily_data = requests/day × bytes/request • total = daily_data × retention_days × replication_factor • Add indexes (~2× for index overhead) Step 5 — Network bandwidth: • ingress = request_rate × avg_request_size • egress = response_rate × avg_response_size • Peak bandwidth = average × 3-5× for spikes Step 6 — Plan for scale: • What triggers adding capacity? (CPU > 70%, disk > 80%) • Auto-scaling rules vs manual provisioning • Shard/partition strategy when single-instance limit reached