How do you choose between SQL and NoSQL databases?

Choose SQL (PostgreSQL, MySQL) for structured data requiring ACID transactions, complex JOINs, and strict schema enforcement. Choose NoSQL (MongoDB, DynamoDB, Cassandra) for flexible schemas, massive horizontal scale, high write throughput, and eventual consistency workloads.

When should you choose Vertical Scaling vs Horizontal Scaling?

Start with vertical scaling (adding CPU/RAM to one server) for simplicity. Transition to horizontal scaling (adding more servers) when hardware limits are reached, cost curves become prohibitive, or high availability is required. Horizontal scaling introduces distributed system complexity.

What is the difference between Sharding, Partitioning, and Indexing?

Indexing speeds up read queries within a single table using B-Tree or Hash structures. Partitioning splits a single table into logical physical chunks within one database instance. Sharding distributes rows across multiple distinct database servers using a shard key, scaling write throughput and storage.

How do you scale WebSockets to millions of concurrent connections?

Increase Linux file descriptor limits, use Layer 4 load balancing with sticky sessions, and implement a Redis Pub/Sub backplane so any WebSocket server can relay messages to clients connected to other servers. Pattern: Client → HAProxy → WS Servers ↔ Redis Pub/Sub.

What is the difference between LSI and GSI in DynamoDB?

A Local Secondary Index (LSI) shares the same partition key as the base table but uses a different sort key. It is limited to 10GB per item collection and supports strong consistency. A Global Secondary Index (GSI) uses a completely different partition key, spans all partitions, supports only eventual consistency, and has its own dedicated throughput capacity.

Which database should I use for transactions, user profiles, logs, and analytics?

Use PostgreSQL for financial transactions (ACID compliance). Use MongoDB for user profiles (flexible JSON). Use Cassandra for logs and high-throughput writes (LSM tree). Use Apache Druid for real-time analytics (columnar storage). Use Elasticsearch for search and catalog (inverted index). Use Redis for sessions and caching (in-memory).

How does Consistent Hashing work?

Consistent hashing maps both servers and keys onto a circular ring. A key routes clockwise to the nearest server. When a node is added or removed, only 1/N keys need to migrate (vs nearly 100% in modulo hashing). Virtual nodes (100-200 per server) ensure even distribution and prevent hotspots.

How do you design a distributed rate limiter?

Use a Token Bucket algorithm for burst-friendly limiting. For distributed enforcement across multiple API gateway instances, use Redis with Lua scripts to atomically evaluate and increment counters, preventing race conditions (dirty reads) where concurrent requests could bypass the limit.

How do you design an elastic search-as-you-type autocomplete system (Tries vs. Inverted Indexes)? — System Design Interview Answer & Trade-offs

Architectural Breakdown & AnalysisFAANG Aligned

Search autocomplete (query auto-suggestion) powers Google, Amazon, and YouTube search bars. As a user types each character (e.g., "sys"), the system must return the top 5 to 10 most relevant, trending suggestions within sub-30 milliseconds before the user types the next letter.\n\n### 1. Data Structure Choice: The Prefix Trie\nA standard relational database LIKE 'sys%' query scans millions of rows and collapses under high concurrency. The optimal data structure is a Prefix Trie (Prefix Tree):\n* Each node in the Trie represents a character.\n* A path from the root to a node spells out a search prefix.\n* Leaf nodes store the full search query and its historical search frequency score.\n\n### 2. The Critical Optimization: Cached Top-K at Each Node\nTraversing down the Trie to find prefix "sys" and then searching all descending subtrees to sort by frequency is $O(\text{all sub-queries})$, which is too slow.\n* Production Solution: Store the Top-K (e.g., Top 5) highest-scoring queries directly inside each Trie node during offline indexing.\n* Query Complexity: Finding suggestions drops to $O(L)$ where $L$ is the length of the typed prefix (typically 3 to 15 characters), completely independent of total database size!\n\n### 3. Distributed Sharding & Scaling the Trie\nWith hundreds of millions of search terms, a Trie exceeds single-machine RAM (20 GB to 100 GB):\n* Sharding by First Letter (Naive): Sharding by a-z produces massive hotspots on popular letters like s or c.\n* Sharding by Hash of Prefix: Partition based on hash(prefix) % N to balance load evenly across worker nodes.\n* Aggressive Edge Caching: 80% of searches follow the Pareto distribution (the same top 20% queries). Cache top autocomplete payloads in CDN edge nodes (Cloudflare/CloudFront) with a 1-hour TTL.\n\n### Key Architectural Comparison\n| Autocomplete Engine | Latency | Memory Footprint | Typo Tolerance | Update Overhead |

:---	:---	:---	:---	:---
Inverted Index (Elasticsearch)	20ms - 50ms	High (Lucene segments)	Excellent (Fuzzy Levenshtein matching)	Dynamic near real-time updates
Relational SQL (`LIKE`)	> 200ms	Minimal	None	Instant

How do you design an elastic search-as-you-type autocomplete system (Tries vs. Inverted Indexes)?

Continue Learning on Being SDE