System Design - Distributed Systems & Scalability Flashcards

Question 1

What is the CAP Theorem and why must distributed systems make trade-offs?

Accepted Answer

The CAP Theorem states that a distributed data store can simultaneously provide at most two of three guarantees:
- **Consistency (C)**: Every read receives the most recent write or an error.
- **Availability (A)**: Every non-failing node returns a non-error response (without guarantee of latest data).
- **Partition Tolerance (P)**: System continues operating despite network dropped/delayed messages.

Since network partitions ($P$) are inevitable in real-world systems, distributed databases must choose between Consistency ($CP$) or Availability ($AP$) during network disruptions.

Question 2

What is the PACELC Theorem and how does it extend CAP?

Accepted Answer

PACELC extends CAP by describing system trade-offs during normal execution (when no network partition exists):

- **If Partition (P)**: Choose between **Availability (A)** or **Consistency (C)**.
- **Else (E)**: Choose between **Latency (L)** or **Consistency (C)**.

*Example*: DynamoDB is $PA/EL$ (favors availability and low latency), whereas MongoDB is $PC/EC$ (favors consistency under both partition and normal conditions).

Question 3

Compare Horizontal Scaling (Scaling Out) vs. Vertical Scaling (Scaling Up).

Accepted Answer

- **Vertical Scaling (Scale Up)**: Adding hardware power (CPU, RAM) to a single machine. Simpler architecture, but limited by physical hardware limits and creates a single point of failure (SPOF).
- **Horizontal Scaling (Scale Out)**: Adding more machine nodes to a resource pool. Offers near-unlimited scalability and high fault tolerance, but introduces complexity with network latency, data partitioning, and consistency management.

Question 4

How does Consistent Hashing work and why is it critical for distributed caching?

Accepted Answer

Consistent Hashing maps both keys and nodes to a logical ring using a uniform hash function (e.g., `hash(key) % 2^32`). A key is assigned to the first node encountered moving clockwise.

**Key Advantage**: When adding or removing a node, only $K/n$ keys need to be remapped on average (where $K$ is total keys and $n$ is total nodes). **Virtual nodes** are used to distribute keys uniformly across physical hardware and prevent hotspots.

Question 5

What is Database Sharding and what main challenges does it introduce?

Accepted Answer

Sharding is horizontally partitioning data across multiple database instances using a **Shard Key** (e.g., `user_id`).

**Pros**: Scalable write throughput, increased memory/disk capacity.
**Challenges**:
- **Cross-shard JOINs**: Extremely slow and complex.
- **Hotspotting**: Poor shard key choice leads to unbalanced traffic on a single shard.
- **Resharding Complexity**: Re-balancing data as storage needs grow is operationally difficult.

Question 6

What causes Replication Lag and how can read-after-write inconsistencies be prevented?

Accepted Answer

Replication lag occurs in asynchronous primary-replica database setups when write updates delay reaching replica nodes, leading to stale reads.

**Mitigation Strategies**:
- Read critical user writes directly from the **Primary Node** (e.g., user reading their own updated profile).
- Enforce **Strong Quorum Consistency** ($R + W > N$).
- Route reads to replicas only after a minimum timestamp/log offset has been reached.

Question 7

Explain the Cache-Aside (Lazy Loading) pattern workflow.

Accepted Answer

1. Application checks the cache for requested data.
2. **Cache Hit**: Data is returned immediately to the client.
3. **Cache Miss**: Application queries the primary database, populates the cache with the fetched result, and returns data to client.

**Pros**: Cache only contains requested data; cache node failures don't crash the system (falls back to DB).
**Cons**: Initial cache miss penalty; risk of stale cache if DB updates bypass invalidation.

Question 8

Compare Write-Through and Write-Back (Write-Behind) caching strategies.

Accepted Answer

- **Write-Through**: Application writes to cache, and the cache *synchronously* writes to the DB before returning success. Low write performance, but ensures zero stale cache reads.
- **Write-Back**: Application writes to cache, which acknowledges immediately. The cache *asynchronously* flushes batched writes to DB. Provides ultra-low write latency, but risks data loss if cache nodes crash before flushing.

Question 9

What are the common Redis Memory Eviction Policies?

Accepted Answer

- `volatile-lru` / `allkeys-lru`: Evicts Least Recently Used keys.
- `volatile-lfu` / `allkeys-lfu`: Evicts Least Frequently Used keys (tracks access frequency).
- `volatile-ttl`: Evicts keys with the shortest time-to-live.
- `noeviction`: Returns error on writes when memory limit is reached (useful when Redis acts as a primary database).

Question 10

Compare Layer 4 (L4) and Layer 7 (L7) Load Balancing.

Accepted Answer

- **Layer 4 (Transport)**: Routes network packets based on IP address and TCP/UDP ports without reading application payloads. Highly performant and lightweight.
- **Layer 7 (Application)**: Inspects HTTP headers, cookies, and URL paths. Enables smart routing (e.g., routing `/api/v1/auth` to Auth microservice), SSL termination, and rate limiting, but consumes higher CPU.

Question 11

How do Message Queues provide Decoupling and Backpressure handling?

Accepted Answer

- **Decoupling**: Producer and Consumer services interact via messages asynchronously, eliminating direct runtime dependency.
- **Backpressure / Buffering**: During high traffic spikes, the queue holds incoming messages without overloading worker nodes. Consumers process messages at their own maximum manageable rate, preventing cascading system failures.

Question 12

Compare Apache Kafka and RabbitMQ in terms of design and consumer patterns.

Accepted Answer

- **RabbitMQ**: Traditional AMQP message broker. Uses **Push-based** delivery, queue-centric routing exchanges, per-message acknowledgments, and deletes messages upon consumption.
- **Kafka**: Distributed append-only transaction log stream platform. Uses **Pull-based** consumption, partition-ordered message retention based on TTL, and replayable log offsets. Ideal for high-throughput stream processing.

Question 13

How does the Token Bucket rate limiting algorithm work?

Accepted Answer

A bucket holds up to $b$ tokens (capacity) and is replenished at a constant rate of $r$ tokens per second.

- Each incoming API request requires 1 token.
- If tokens $\ge 1$, the request is processed and 1 token is consumed.
- If tokens $= 0$, the request is dropped with HTTP `429 Too Many Requests`.

**Advantage**: Easily handles bursty traffic while enforcing a smooth long-term average rate.

Question 14

What is the Sliding Window Log rate limiting algorithm and its main drawback?

Accepted Answer

Stores a timestamp log (e.g., Redis `ZSET`) for every request within a window $T$.

1. On new request, delete all timestamps older than $(now - T)$.
2. Count remaining log entries.
3. If count < limit, append current timestamp and allow request; otherwise block.

**Drawback**: High memory utilization, as timestamps for *every single request* must be retained in memory.

Question 15

How is Strong Consistency enforced using Distributed Quorums ($N, W, R$)?

Accepted Answer

Given $N$ total replicas:
- $W$ = Number of replicas that must confirm a write.
- $R$ = Number of replicas queried on a read.

To achieve **Strong Consistency**, the system must satisfy:
$$W + R > N$$

This ensures that the read set and write set overlap by at least one replica containing the latest version of data.

Question 16

What is Idempotency in distributed APIs and how is it implemented?

Accepted Answer

An API operation is **idempotent** if making multiple identical requests yields the same system state as a single request.

**Implementation**:
Clients send a unique `Idempotency-Key` (UUID) in the request header. The server logs the key in Redis/Database upon first processing. Subsequent retries with the same key bypass re-execution and return the cached result.

Question 17

What is Two-Phase Commit (2PC) and why is it avoided in modern microservices?

Accepted Answer

2PC is an atomic consensus protocol for distributed transactions consisting of:
1. **Prepare Phase**: Coordinator asks all nodes if they are ready to commit.
2. **Commit Phase**: If all vote 'Yes', coordinator sends commit command.

**Avoided because**: It is a **blocking protocol** that holds database locks across network boundaries, causing extreme latency, low throughput, and SPOF vulnerabilities on the coordinator.

Question 18

How does the SAGA Pattern manage distributed microservice transactions?

Accepted Answer

SAGA breaks a global transaction into a sequence of individual local transactions across services.

- Each service completes its transaction and emits an event.
- If a step fails, the SAGA executes a series of **Compensating Transactions** in reverse order to undo prior changes.
- Implemented via **Choreography** (services react to event buses) or **Orchestration** (central coordinator manages step order).

Question 19

What is the Gossip Protocol and where is it used?

Accepted Answer

A decentralized peer-to-peer communication mechanism where nodes periodically share cluster state info with a random subset of neighboring nodes.

- Information spreads exponentially like an epidemic.
- **Use Cases**: Node discovery, health checks, cluster topology updates, and failure detection in masterless distributed systems (e.g., Apache Cassandra, Consul).

Question 20

How do Heartbeating and Failure Detectors prevent false node failure declarations?

Accepted Answer

Nodes periodically transmit a lightweight signal (heartbeat) to cluster peers or a central orchestrator.

To prevent false positives caused by temporary network spikes or GC pauses, systems use randomized dynamic timeouts or **$\Phi$-Accrual Failure Detectors**, which estimate the probability of node failure on a continuous scale rather than a binary dead/alive state.

System Design - Distributed Systems & Scalability

Cards in this deck

Related Flashcard Sets

Series 7 Exam - Options Strategies & Municipal Securities

Neuroscience - Action Potentials & Synaptic Transmission

USMLE Step 1 - Cardiovascular Physiology & Pathology

MIT 6.033 - Computer System Engineering