System Design - Distributed Systems, Load Balancing & High Availability Flashcards

Question 1

Consistent Hashing

Accepted Answer

A distributed hashing scheme that maps both servers and keys to a virtual ring (hash space $0$ to $2^{32}-1$).

- **Key Benefit**: Adding or removing a server node requires remapping only $K/n$ keys on average (where $K$ is the number of keys and $n$ is the number of servers).
- **Virtual Nodes**: Uses multiple virtual positions per physical server to ensure uniform data distribution and prevent hotspots.

Question 2

Load Balancing Algorithms

Accepted Answer

- **Round Robin**: Distributes requests sequentially across servers.
- **Weighted Round Robin**: Routes traffic based on assigned server capacity/weight.
- **Least Connections**: Directs traffic to the server with the fewest active connections (ideal for long sessions).
- **IP Hash**: Maps client IP to a server using a hash function, ensuring session persistence (sticky sessions).

Question 3

Layer 4 vs. Layer 7 Load Balancing

Accepted Answer

- **Layer 4 (Transport Layer)**: Routes traffic based on IP address and TCP/UDP ports without inspecting packet payloads. Highly efficient and fast (e.g., HAProxy in TCP mode).
- **Layer 7 (Application Layer)**: Routes traffic based on application data such as HTTP headers, cookies, or URL paths. Enables smart routing, SSL termination, and content-based caching (e.g., NGINX, AWS ALB).

Question 4

Database Replication: Primary-Replica vs. Multi-Primary

Accepted Answer

- **Primary-Replica (Master-Slave)**: Writes go to the primary node and are replicated to read-only replicas. Solves read scalability but write capacity remains limited to the primary.
- **Multi-Primary (Master-Master)**: Multiple nodes accept write operations. Improves write availability, but requires complex conflict resolution algorithms (e.g., Vector Clocks, Last-Write-Wins).

Question 5

Database Sharding

Accepted Answer

A horizontal partitioning technique where a single database dataset is split across multiple separate database instances using a **Shard Key**.

- **Pros**: Handles massive write/read throughput beyond a single server's limits.
- **Cons**: High complexity; makes cross-shard joins, distributed transactions, and dynamic re-sharding difficult.

Question 6

Cache-Aside (Lazy Loading)

Accepted Answer

1. Application checks the cache for data.
2. If **Cache Hit**: Returns data directly.
3. If **Cache Miss**: Reads data from the database, writes it to the cache, and returns it to the client.

- **Pros**: Cache only contains requested data; handles cache node failures gracefully.
- **Cons**: Cache miss penalty on initial read; potential data staleness if DB writes bypass the cache.

Question 7

Write-Through vs. Write-Back (Write-Behind) Cache

Accepted Answer

- **Write-Through**: Data is written simultaneously to both the cache and the underlying database. Guarantees consistency and durability, but increases write latency.
- **Write-Back (Write-Behind)**: Data is written immediately to the cache, and asynchronously flushed to the database at defined intervals.
  - *Pros*: Extremely low write latency and high throughput.
  - *Cons*: Risk of data loss if the cache node crashes before flushing to storage.

Question 8

Content Delivery Network (CDN): Pull vs. Push

Accepted Answer

- **Pull CDN**: Cache servers fetch content from the origin server on-demand when a user requests it for the first time. Low setup effort; efficient for high-traffic sites.
- **Push CDN**: Origin server actively uploads new or updated content directly to CDN edge nodes before requests arrive. Ideal for static, infrequently changing assets or critical system updates.

Question 9

Token Bucket Rate Limiting

Accepted Answer

Tokens are added to a bucket of capacity $B$ at a constant fill rate $R$ tokens/sec.
- Each incoming request consumes $N$ tokens.
- If enough tokens are present, the request is processed; otherwise, it is dropped or delayed.

- **Key Feature**: Allows temporary bursts of traffic up to the bucket capacity $B$ while maintaining a fixed long-term average rate.

Question 10

Leaky Bucket Rate Limiting

Accepted Answer

Requests enter a FIFO queue (the bucket) of capacity $C$. The bucket processes and dispatches requests at a smooth, constant rate $R$.

- If the queue overflows, incoming requests are rejected.
- **Key Feature**: Smooths out traffic spikes into a continuous steady outflow; removes traffic burstiness.

Question 11

Message Queues: Apache Kafka vs. RabbitMQ

Accepted Answer

- **RabbitMQ**: Traditional AMQP broker using smart brokers and dumb consumers. Delivers messages to individual queues, supports complex routing, and deletes messages after consumer acknowledgment.
- **Apache Kafka**: High-throughput distributed commit log. Uses dumb brokers and smart consumers. Messages are immutable, persistent, partitioned, and can be replayed by multiple consumer groups reading at distinct offsets.

Question 12

Two-Phase Commit (2PC)

Accepted Answer

An atomic distributed transaction protocol consisting of two phases:
1. **Prepare Phase**: Coordinator asks all participating nodes if they are ready to commit.
2. **Commit Phase**: If all nodes vote 'Yes', the coordinator issues a global `COMMIT`. If any node votes 'No', it issues a global `ABORT`.

- **Drawback**: Blocking protocol; vulnerable to single point of failure if the coordinator crashes during execution.

Question 13

Saga Pattern

Accepted Answer

A design pattern for managing distributed transactions across microservices as a sequence of local transactions.
- Every local transaction updates its own service's database.
- If a local step fails, the Saga executes a series of **Compensating Transactions** in reverse order to undo changes.
- **Implementation Modes**: **Choreography** (event-driven coordination) or **Orchestration** (central coordinator service).

Question 14

Bloom Filter

Accepted Answer

A space-efficient probabilistic data structure used to test set membership.
- **Guarantees**: Can definitively tell if an element is **not** in the set (0% False Negatives), but can return **False Positives**.
- Uses an array of $m$ bits and $k$ independent hash functions.
- Common uses: Preventing expensive database queries for non-existent keys (e.g., in Cassandra, HBase).

Question 15

Gossip Protocol

Accepted Answer

A decentralized peer-to-peer communication protocol where nodes periodically exchange membership and state information with a few randomly selected neighbor nodes.
- **Characteristics**: Highly fault-tolerant, scalable, and eventually consistent.
- Widely used for cluster topology management and failure detection in systems like Apache Cassandra and Consul.

Question 16

Idempotency in Distributed Systems

Accepted Answer

An operation is **idempotent** if executing it multiple times produces the exact same side-effects as executing it once:
$$f(f(x)) = f(x)$$

- Critical for handling retries over unreliable networks.
- **Implementation**: API clients pass a unique `Idempotency-Key` header; the server records processed keys in a fast datastore (e.g., Redis) to skip duplicate executions.

Question 17

Heartbeating and Service Discovery

Accepted Answer

- **Service Discovery**: Dynamic lookup registry (e.g., Eureka, Consul, ZooKeeper) where microservices auto-register their IP addresses and ports.
- **Heartbeating**: Periodic health checks (`PING` or HTTP `/health`) sent from services to the registry. If a node misses consecutive heartbeats, it is removed from active load balancing pools.

Question 18

CAP Theorem

Accepted Answer

States that a distributed data store can simultaneously provide at most two out 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.
- **Partition Tolerance (P)**: The system continues to operate despite network node dropouts or delays.

In real-world distributed systems, network partitions are inevitable, so systems must choose between **CP** (Consistency/Partition Tolerance) or **AP** ( Availability/Partition Tolerance).

Question 19

PACELC Theorem

Accepted Answer

An extension of the CAP theorem. It states that **If there is a Partition (P)**, a system must trade off **Availability (A)** vs **Consistency (C)**; **Else (E)**, when the system is running normally without partitions, it must trade off **Latency (L)** vs **Consistency (C)**.

*Examples:* DynamoDB is PA/EL; MongoDB is PC/EC.

Question 20

Horizontal vs. Vertical Scaling

Accepted Answer

- **Vertical Scaling (Scale-Up)**: Adding more power (CPU, RAM, Storage) to an existing machine. Limited by hardware caps and introduces a single point of failure (SPOF).
- **Horizontal Scaling (Scale-Out)**: Adding more machines to the pool. Offers infinite scalability and fault tolerance, but increases network complexity and requires load balancing.

System Design - Distributed Systems, Load Balancing & High Availability

Cards in this deck

Related Flashcard Sets

TypeScript - Advanced Type Systems, Generics & Design Patterns

Harvard ECON1011 - Intermediate Microeconomics: Game Theory & Market Structures

MIT 18.03 - Differential Equations: Ordinary Differential Equations, Laplace & Fourier

CPA Exam FAR - Financial Accounting & Reporting: US GAAP & Revenue Recognition