SyntaxShelf
DSA

System Design Basics

Interview Prep · 8 entries

Scalability Concepts

syntax
Vertical scaling: bigger machine (more CPU/RAM)
Horizontal scaling: more machines (distributed)

Stateless services scale horizontally easily.
Stateful services need careful data partitioning.
example
// Key principles:
// 1. Identify bottleneck: CPU-bound? I/O-bound? Memory-bound?
// 2. Scale reads: caching, read replicas, CDN
// 3. Scale writes: sharding, message queues, async processing
// 4. Scale storage: partitioning, object storage, tiered storage

// Quick estimation:
// 1 million users × 10 requests/day = ~100 requests/second
// 1 KB per request = ~100 KB/s = ~8.6 GB/day
// Plan for 10x peak: ~1000 requests/second
output
Horizontal > Vertical for long-term scaling

Note Start simple, scale when needed. In interviews, show you can estimate back-of-the-envelope numbers: daily active users, requests per second, storage needs. Mention trade-offs: horizontal scaling adds complexity (load balancing, distributed state) but has no ceiling like vertical scaling.

scalabilityhorizontal scalingvertical scalingsystem designcapacity planning

Load Balancing

syntax
Distributes traffic across multiple servers.
Strategies:
- Round robin: rotate through servers
- Least connections: send to least busy
- IP hash: consistent routing per client
- Weighted: more traffic to stronger servers
example
// Architecture:
// Client → Load Balancer → Server 1
//                        → Server 2
//                        → Server 3

// Layer 4 (TCP): fast, routes by IP/port
// Layer 7 (HTTP): smarter, can route by URL/headers/cookies

// Health checks: LB periodically pings servers
// If server fails health check → removed from rotation
// When it recovers → added back
output
Load balancers enable horizontal scaling and high availability.

Note In interviews, mention: single point of failure risk → use redundant LBs (active-passive pair). Session stickiness (sticky sessions) can solve stateful server issues but reduces flexibility. Modern cloud: AWS ALB/NLB, GCP Load Balancer handle this automatically.

load balancerround robintraffic distributionsystem design LBhigh availability

Caching

syntax
Store frequently accessed data in fast storage (memory).
Layers: browser cache → CDN → application cache → database cache

Patterns:
- Cache-aside: app checks cache first, loads from DB on miss
- Write-through: write to cache and DB simultaneously
- Write-back: write to cache, async flush to DB
example
// Cache-aside pattern (most common):
// 1. App receives request
// 2. Check cache (Redis/Memcached)
// 3. Cache HIT → return cached data
// 4. Cache MISS → query database → store in cache → return

// Eviction policies:
// LRU: remove least recently used (most common)
// LFU: remove least frequently used
// TTL: expire after fixed time

// Cache invalidation strategies:
// 1. TTL-based: set expiry, eventually consistent
// 2. Event-based: invalidate on write
// 3. Version-based: cache key includes version number
output
Cache hit: ~1ms | Database query: ~10-100ms | 10-100x speedup

Note Cache invalidation is one of the two hard problems in CS (along with naming things). Always discuss: cache stampede (many misses at once → thundering herd), consistency vs performance trade-off, and cold start (empty cache after deploy). Redis is the go-to answer for distributed caching.

cachingRediscache asidecache invalidationCDNsystem design cache

Database Sharding

syntax
Split a large database into smaller pieces (shards), each on a separate server.
Sharding key: determines which shard stores each record.

Types:
- Range-based: shard by ID ranges
- Hash-based: hash(key) % num_shards
- Geographic: shard by region
example
// Hash-based sharding:
// shard_id = hash(user_id) % num_shards
// User 12345 → hash(12345) % 4 → shard 2

// Example with 4 shards:
// Shard 0: users where hash(id) % 4 = 0
// Shard 1: users where hash(id) % 4 = 1
// Shard 2: users where hash(id) % 4 = 2
// Shard 3: users where hash(id) % 4 = 3

// Consistent hashing: minimizes data movement when adding/removing shards
// Instead of hash % N, map keys and shards to a ring
output
Sharding enables databases to handle billions of rows.

Note Trade-offs: cross-shard queries are expensive, joins across shards are very difficult, rebalancing shards is painful. Choose sharding key carefully — it should distribute data evenly and align with your most common access pattern. Mention consistent hashing to impress — it minimizes data migration when topology changes.

database shardingpartitioningconsistent hashinghorizontal database scaling

CAP Theorem

syntax
In a distributed system, you can only guarantee 2 of 3:
- Consistency: every read gets the most recent write
- Availability: every request gets a response
- Partition tolerance: system works despite network failures

Since partitions are inevitable, the real choice is C vs A during a partition.
example
// CP systems (consistency over availability):
// - Bank transactions: must be consistent
// - Examples: HBase, MongoDB (with majority write concern)
// - During partition: some requests may fail

// AP systems (availability over consistency):
// - Social media feeds: slightly stale data is OK
// - Examples: Cassandra, DynamoDB
// - During partition: may serve stale data

// Real-world: most systems mix both
// Critical data (payments) → strong consistency
// Non-critical data (user profile pic) → eventual consistency
output
In practice: choose between consistency and availability during network partitions.

Note Saying 'I would choose CP' or 'AP' without context is a red flag. Instead, discuss WHICH parts of the system need which guarantee. Payment processing needs CP. A news feed can tolerate AP. Mention 'eventual consistency' — most modern distributed databases use it.

CAP theoremconsistency availabilitydistributed systemseventual consistencypartition tolerance

REST vs GraphQL

syntax
REST:
- Resource-based URLs: /users/123
- Fixed response shape per endpoint
- Multiple endpoints for related data

GraphQL:
- Single endpoint, query specifies shape
- Client requests exactly what it needs
- Reduces over/under-fetching
example
// REST:
// GET /users/123        → full user object
// GET /users/123/posts  → all posts
// Problem: 2 requests, might get unused fields

// GraphQL:
// POST /graphql
// query {
//   user(id: 123) {
//     name
//     posts(limit: 5) {
//       title
//     }
//   }
// }
// → exactly the fields requested, single request

// When to use REST:
// - Simple CRUD APIs, caching is important (HTTP caching)
// - Public APIs, broad adoption

// When to use GraphQL:
// - Mobile apps (bandwidth-sensitive)
// - Complex data relationships
// - Multiple client types needing different data shapes
output
REST: simpler, cacheable | GraphQL: flexible, efficient data fetching

Note Neither is universally better. REST is simpler to cache (GET requests are cacheable by URL). GraphQL can cause N+1 query problems on the backend if not careful (use DataLoader pattern). In interviews, discuss trade-offs rather than picking a winner. Most companies use REST unless they have specific needs for GraphQL.

REST vs GraphQLAPI designover-fetchingunder-fetchingsystem design API

Message Queues

syntax
Decouple producers from consumers. Producer sends messages to queue, consumer processes them asynchronously.

Use cases:
- Async task processing (email sending, image resizing)
- Rate limiting / traffic smoothing
- Decoupling microservices

Examples: RabbitMQ, Apache Kafka, AWS SQS
example
// Without queue:
// User request → Process image → Respond (slow, 5 seconds)

// With queue:
// User request → Enqueue 'process image' → Respond immediately (50ms)
// Background worker → Dequeue → Process image → Update status

// Kafka vs SQS:
// Kafka: ordered, replayable, high throughput, log-based
// SQS: simple, managed, at-least-once delivery, auto-scaling

// Key concepts:
// At-least-once: message may be delivered multiple times
// At-most-once: message may be lost but never duplicated
// Exactly-once: hardest to achieve, often app-level idempotency
output
Queues enable async processing, better reliability, and decoupled services.

Note In interviews, mention idempotency: since messages can be delivered multiple times, consumers should handle duplicates safely. Dead letter queues (DLQ) capture messages that fail processing repeatedly. Kafka is the go-to answer for event streaming; SQS/RabbitMQ for simple task queues.

message queueKafkaasync processingdecouplingproducer consumer

Rate Limiting

syntax
Restrict how many requests a client can make in a time window.
Protects services from abuse, ensures fair usage.

Algorithms:
1. Fixed window: count requests per time window
2. Sliding window: smoother, avoids burst at window boundary
3. Token bucket: tokens refill at fixed rate, each request costs a token
4. Leaky bucket: requests processed at fixed rate, excess queued
example
// Token bucket pseudocode:
// bucket has 'tokens' (max capacity), refill rate
// On request:
//   refill tokens based on elapsed time
//   if tokens >= 1:
//     tokens -= 1
//     allow request
//   else:
//     reject (429 Too Many Requests)

// Example: 100 requests/minute, burst of 10
// capacity = 10, refill rate = 100/60 ≈ 1.67 tokens/sec

// Where to implement:
// API Gateway level (centralized)
// Application level (per-service)
// Client-side (self-throttling)

// Distributed rate limiting:
// Use Redis INCR + EXPIRE for shared counter across instances
output
Rate limiting: protect services, ensure fairness, prevent abuse.

Note Token bucket is the most common answer in interviews — it allows bursts while maintaining an average rate. For distributed systems, use Redis as a shared counter (INCR + EXPIRE atomic operation). Return 429 status code with Retry-After header. Rate limiting is commonly asked in system design interviews for URL shortener, API gateway, and chat systems.

rate limitingtoken bucketthrottlingAPI protection429 too many requests