Core principles and theory that underlie distributed computing systems. Includes understanding trade offs between consistency, availability, and partition tolerance, common consistency models such as eventual and strong consistency, replication and sharding strategies, load balancing and data partitioning, consensus algorithms and their guarantees, scalability and fault tolerance patterns, and how these concepts apply to infrastructure components such as databases, caches, service meshes, and load balancers. Candidates are expected to explain design choices, common failure modes, and how fundamental concepts influence architecture decisions for resilient and scalable systems.
HardTechnical
69 practiced
Describe gossip protocols for cluster membership and state dissemination. Design a gossip-based membership service for a 10k-node cluster: outline message formats, anti-entropy rounds, failure detection heuristics, convergence guarantees, and bandwidth-control mechanisms to keep traffic bounded while maintaining timely convergence.
Sample Answer
**Overview**Gossip protocols use periodic, randomized peer-to-peer exchanges to spread membership and state with probabilistic guarantees. For a 10k-node cluster choose epidemic anti-entropy + SWIM-style failure detection for low overhead and fast convergence.**Message formats**- Ping message: { type: "ping", src, seq, timestamp }- Ack: { type: "ack", src, seq }- Indirect ping: { type: "indirect", target, via, timeout }- Gossip digest: { type: "gossip", src, seq, vector<entry> } - entry: { node_id, incarnation, status (alive/suspect/faulty), last_update_ts }- Optional bloom filter for membership summary to reduce payload for large digests.**Anti-entropy rounds**- Each round (200–500ms): pick k = 3 random peers (fanout) and exchange digests.- On mismatch, request delta entries; merge by latest incarnation and timestamp.- Rounds use exponential backoff for nodes with stable state to reduce chatter.**Failure detection heuristics**- SWIM-style direct ping; on no response, launch m = 3 indirect pings via random helpers.- Use incarnation numbers to avoid false-positive reintroductions.- Mark suspect after one failed probe; mark faulty if suspect persists for T_suspect (e.g., 3×probe interval) or confirmed by majority of probes.**Convergence guarantees**- With fanout k and rounds r, expected coverage ~ O(log_k N). For N=10k and k=3, ~log_3(10000) ≈ 9 rounds → choose round interval 300ms → full spread ~3s with high probability.- Anti-entropy ensures eventual consistency: periodic full-delta exchange corrects missing updates.**Bandwidth-control**- Limit gossip payload: send only deltas since last seq; cap entries per message (e.g., 50 entries).- Use bloom filters + probabilistic sampling to summarize large sets.- Adaptive round interval: increase interval for nodes with stable membership; decrease when churn detected.- Rate-limit per-peer bytes/sec and implement jitter in scheduling to avoid synchronization.**Practical notes for full-stack implementation**- Expose HTTP/WS health endpoints for operator queries; persist local membership state in lightweight store (LevelDB/Redis) for restart.- Add metrics (gossip messages/sec, convergence time, false positives) and toggles for fanout and intervals to tune in staging.
HardTechnical
60 practiced
Explain how you would design for linearizability (single-copy semantics) in a distributed key-value store used by your full-stack app. Describe mechanisms required (replicated logs, leader-based writes, quorum reads/writes), the impact on latency, and performance optimizations (read leases, leader hints) you might employ.
Sample Answer
**Design goal — linearizability (single‑copy semantics)** Serve client reads/writes as if there’s one authoritative copy: each completed operation appears instantaneous and globally ordered.**Core mechanisms** - Replicated log + leader: use leader-based replication (Raft/Paxos). Leader serializes writes into a replicated log; entries are applied in order to state machine (KV store). - Quorum reads/writes: writes require majority (W > N/2) to commit; reads use quorum (R + W > N) to ensure reading latest committed value. - Lease-based leader: leader holds a time-limited lease to safely serve reads without contacting quorum each time.**Example flow** - Client POST /kv key->value to leader → leader appends log entry, replicates to followers, waits for majority ACK → responds. - Client GET /kv read from leader (fast) or follower (must verify freshness via quorum or leader hint).**Latency & trade-offs** - Strong linearizability increases write and some read latency (writes pay network RTTs to majority). Reads can be slow if forced to consult quorum. - Trade-off: consistency vs latency/availability (CP in CAP).**Optimizations** - Read leases: leader grants short lease so followers reject serving stale reads; leader serves fast local reads without quorum while lease valid. - Leader hints / sticky routing: clients route reads to known leader to avoid extra validation RTTs. - Read index (Raft): followers use leader’s monotonic index to serve linearizable reads with fewer round trips. - Batching and pipelining replication to amortize RTTs; use fast networks/placement to reduce cross‑datacenter latency.**Operational considerations** - Lease clock skew bounds, lease expiration safety, and election latency must be tuned. Monitor leader churn, tail latency, and choose quorum size for required durability vs latency.
EasyTechnical
66 practiced
Explain the CAP theorem for distributed systems and give three concrete examples (e.g., web session store, shopping cart, CDN cache) where you would prioritize each pair of guarantees (CP, AP, CA). For each example, state the trade-offs you accept, why that choice fits the use case, and the common failure modes that drive the decision.
Sample Answer
**What CAP says (brief)** CAP: in a distributed system under a network Partition (P), you can choose either Consistency (C) or Availability (A) — you cannot guarantee both. When no partition exists, systems can appear CA, CP, or AP in practice, but designs are judged by behavior during partitions.**Example 1 — CP: Web session store with single-source authoritative sessions** - Choice: Consistency + Partition-tolerance (e.g., Redis Sentinel with quorum reads/writes). - Trade-offs: May reject requests or block during leader election (reduced availability) to avoid stale session data. - Why fit: User sessions must be correct (avoid conflicting login state, billing). - Failure modes: Network partitions or leader failure -> clients see errors or 503s until election completes.**Example 2 — AP: CDN cache / static asset cache** - Choice: Availability + Partition-tolerance (eventual consistency, e.g., edge caches, TTLs). - Trade-offs: Serve stale content during partitions; updates propagate eventually. - Why fit: Low latency and high availability matter more than absolutely fresh assets. - Failure modes: Cache staleness after origin change, cache stampede on origin failure; mitigate with short TTLs, cache invalidation.**Example 3 — CA (practical): Internal config store in tightly-coupled datacenter** - Choice: Consistency + Availability when P is unlikely (single-datacenter, no geo partitions). - Trade-offs: Less tolerant of network splits across sites — not partition-resilient across regions. - Why fit: Configuration reads/writes need immediate correctness and low latency within same datacenter. - Failure modes: If a partition occurs (rare), system can violate CAP assumptions—either degrade availability or risk inconsistency; mitigate by replication within LAN and automated failover.Notes for a full-stack role: pick the model per feature — user-facing flows favor availability and UX; critical business writes favor consistency.
HardSystem Design
62 practiced
Design a plan to adopt a service mesh (e.g., Istio) for a full-stack application. Describe the benefits (mTLS, retries, observability), migration steps, sidecar resource impact, failure modes introduced by the control plane, and strategies for progressive rollout, testing, and rollback.
Sample Answer
**Clarify goals & constraints**- Goal: add Istio to improve security (mTLS), reliability (retries/circuit breakers), and observability without breaking UX.- Constraints: k8s cluster size, resource budget, CI/CD integration, compliance requirements.**Benefits**- mTLS: automatic pod-to-pod encryption and identity-based auth; removes app-level TLS plumbing.- Retries/Timeouts/Circuit Breakers: declarative resiliency policies reducing duplicate client logic.- Observability: distributed tracing, metrics and logs (Envoy + Mixer/Telemetry) with minimal app changes.**Migration plan (phased)**1. Prep: install Istio in a non-prod namespace, enable sidecar injection, deploy telemetry stack (Prometheus/Grafana/Jaeger).2. Select pilot services: pick low-risk backend services and an internal frontend API.3. Mutual TLS in PERMISSIVE mode: verify traffic works and collect telemetry.4. Apply routing policies (retries, timeouts) and test behavior.5. Enforce STRICT mTLS for tested namespaces.6. Expand iteratively, then enable mesh-wide policies (RBAC, rate-limiting).**Sidecar resource impact**- Each pod gains an Envoy (~50–150MB memory, CPU share). Account in HPA and request/limit sizing; use vertical pod autoscaler and node autoscaling. For many small pods consider shared gateways or lighter alternatives.**Control-plane failure modes**- Pilot/istiod outage: new sidecars may fail to get config; existing proxies continue with cached config but dynamic updates stop.- API server coupling: misconfigured CRDs can disrupt routing.- Mitigations: HA control plane, fallback configs, short-lived rollout windows, health probes for istiod, circuit breakers at app-level.**Progressive rollout, testing & rollback**- Canary by namespace: enable sidecar injection for a small percentage of namespaces/pods.- Traffic shifting: use VirtualService to route X% to meshed version; monitor latency, error rate, resource usage.- Automated tests: e2e tests for API, contract tests for frontend integration, load tests for error budgets.- Observability gates: define SLO thresholds (latency p50/p95, error rate) that must pass before expanding.- Rollback: revert VirtualService traffic, disable injection for next deploy, or scale down Istio components. Use CI/CD pipeline with feature flags and automation to rollback on threshold breaches.**Notes for full-stack dev**- Minimal app changes: propagate trace headers; add health/readiness to avoid sidecar killing.- Watch CORS and client TLS expectations when switching mTLS modes.- Start with backend services first, then frontend-facing services after verifying observability and policies.
HardSystem Design
62 practiced
Design a multi-region architecture for a global full-stack application that requires low-latency reads worldwide but strong consistency for user profile updates. Define data placement, read routing, write serialization strategy, and how you would surface degraded behavior during region failures. Assume 100M users and a 99.99% availability goal; discuss trade-offs like latency vs consistency and possible architectures (single-writable-region, multi-master with conflict resolution, geo-consensus).
Sample Answer
**Clarify requirements & constraints**- 100M users, global low-latency reads, strong consistency for user profile updates, 99.99% availability, detect/surface degraded behaviour.**High-level approach**- Use geo-distributed read replicas for low-latency reads + a strong-consistency write substrate for profile updates. Prefer single-writable-region (primary) with geo-consensus fallback for strict consistency and simplicity.**Data placement**- Global read replicas (cache tier + read-only DB replicas) in each region containing user's profile shard(s) propagated via fast replication.- A single primary writable region for account/profile writes; partition users by consistent hashing to distribute load across primaries (or colocate per-region primaries for subsets if needed).**Read routing**- Route reads to nearest regional read cache/replica (CDN/edge + Redis/Memcached + read-replica DB).- Use time-to-live & version tags (ETag) to ensure clients can detect stale data for sensitive flows.**Write serialization strategy**- All profile writes go to the user's primary writable region. Use Paxos/Raft (managed geo-consensus) for leader election and commit across replicas if you need synchronous durability; otherwise, use single-writer with async replication and synchronous ack from primary only.- Use per-user optimistic concurrency using version numbers / CAS to prevent lost updates.- For multi-master option: require CRDTs or last-writer-wins with vector clocks—complex and risky for profiles.**Failure & degraded-behaviour surfacing**- If primary region unavailable: failover using automated geo-consensus to elect new writer (controlled, with.health checks). During failover surface UI banners: “Profile edits temporarily delayed — reads may be stale.” Expose metrics: replication lag, write-latency, failover state via health endpoints and SLO dashboards, client-side fallbacks (queue writes locally and retry with exponential backoff for non-critical updates).- For read-only partial failures: serve cached reads with TTL and indicate staleness only when necessary.**Trade-offs**- Single-writable-region: simpler, strong consistency, lower conflict risk, but higher write latency for remote users and failover complexity.- Multi-master: lower write latency but complex conflict resolution and weaker guarantees.- Geo-consensus: strong consistency and controlled failover but higher commit latency; use for critical profile writes only.**Metrics & SLOs**- Monitor 99.99% availability, replication lag <100ms target, write RTO for failover <60s, user-visible staleness rate.This design balances low-latency global reads with strong, predictable consistency for profile updates while providing clear surfaced behavior during region failures.
Unlock Full Question Bank
Get access to hundreds of Distributed Systems Fundamentals interview questions and detailed answers.
