Top HLD Interview Questions

The choice between SQL (Relational) and NoSQL (Non-Relational) databases is not about which is "better," but rather which matches your system's data structure, query patterns, and scale constraints.

1. SQL Databases (e.g., PostgreSQL, MySQL)

• Data Structure: Strict tabular schema with defined relationships (Foreign Keys). Ideal for normalized data.
• Consistency: Strict ACID compliance by default. Best for financial ledgers and transactions where inconsistency causes immediate failure.
• Scaling: Primarily vertical (scaling CPU/RAM). Horizontal scaling requires master-replica reads or complex application-layer sharding.
• Queries: Powerful SQL engine supporting multi-table JOINs and complex analytical aggregations.

2. NoSQL Databases (e.g., MongoDB, DynamoDB, Cassandra)

• Data Structure: Schemaless or flexible models (Key-Value, Document, Wide-Column, Graph).
• Consistency: Eventual consistency models (BASE) optimized for ultra-high write throughput and partition tolerance.
• Scaling: Native horizontal scaling out-of-the-box via partition keys and auto-sharding.
• Queries: Key-value lookups or simple index searches. Multi-document JOINs are either unsupported or inefficient.

Scaling refers to increasing system capacity to handle higher request volumes, storage sizes, and concurrent connections.

Vertical Scaling (Scale Up)

Adding hardware resources (CPU, RAM, NVMe storage) to a single existing server instance.

• Pros: Simplicity. Zero network latency between nodes, simple programming model, transactions work natively.
• Cons: Hard hardware limits, exponential cost curve for high-end bare metal, single point of failure (SPOF).
• Best For: Early-stage applications, relational databases with low write traffic, and monolithic background workers.

Horizontal Scaling (Scale Out)

Adding more commodity servers to the resource pool and distributing load across them.

• Pros: Infinite scaling limits, elastic provisioning, high availability with no single point of failure.
• Cons: Distributed system complexity, data consistency challenges, load balancer dependencies, network latency overhead.
• Best For: High-traffic web servers, caching layers, distributed databases, and high-volume media processing.

These are three core optimization strategies to handle large volumes of database reads and writes. They operate at different levels of database management:

Unlike stateless HTTP requests, WebSockets are persistent, stateful TCP connections. A single client maintains an open connection with a specific server instance.

1. OS-Level Socket Limits (File Descriptors)

In Linux, every TCP connection is represented as a File Descriptor (FD). By default, the OS limits FDs per process.

• Increase limits by modifying /etc/security/limits.conf (nofile limit to 1,000,000).
• Optimize port allocations: A single IP can only connect to ~65,000 ports on a target IP. Attach multiple virtual IPs to the load balancer or WebSocket nodes to scale.

2. Load Balancing & Layer 4 Routing

• Use Layer 4 (TCP) HAProxy or Envoy load balancers to minimize CPU overhead compared to Layer 7 HTTP parsing.
• Enable WebSocket HTTP Upgrade headers during initial handshakes.

3. Inter-Server Communication (Pub/Sub Backplane)

When Client A (connected to Server 1) sends a message to Client B (connected to Server 2):

• Redis Pub/Sub or Kafka Backplane: Server 1 publishes the message to a central Redis channel.
• All WebSocket servers subscribe to this channel. Server 2 reads the message, identifies that Client B is local to it, and pushes the payload down Client B's TCP socket.

Authenticating users across independent microservices requires moving away from single-server memory sessions.

DynamoDB is a fully managed wide-column NoSQL database. Scaling seamlessly to petabytes requires understanding its partitioning and index architecture:

1. Primary Key: Partition Key (PK) & Sort Key (SK)

• Partition Key (Hash Key): Hashed by DynamoDB to route items to physical storage partitions. Even distribution prevents hot partitions.
• Sort Key (Range Key): Determines physical storage order within a partition, enabling range queries (begins_with, between).

2. Local Secondary Index (LSI)

• Shares the same Partition Key as the base table, but uses a different Sort Key.
• Shares read/write capacity units (RCU/WCU) with the base table.
• Supports Strongly Consistent and Eventual Consistent reads.
• Must be defined at table creation time.

3. Global Secondary Index (GSI)

• Defines a completely new Partition Key and Sort Key.
• Spans across all partitions with no size limits.
• Requires dedicated provisioned RCU/WCU. If GSI writes throttle, parent table writes throttle too.
• Supports Eventual Consistency only due to asynchronous replication.

No single database engine fits all data patterns. High-scale architecture decouples storage based on throughput, query model, and consistency needs:

When a business transaction spans service boundaries (e.g., Order Service → Inventory Service → Payment Service), local DB transactions cannot guarantee atomicity.

1. Two-Phase Commit (2PC)

• Prepare Phase: Coordinator asks participant DBs if they can commit. Participants lock records and reply Yes/No.
• Commit Phase: If all reply Yes, coordinator issues Commit; otherwise Abort.
• Drawback: 2PC is a blocking protocol. If the coordinator fails mid-process, resources remain locked indefinitely.

2. Saga Pattern (Eventual Consistency)

Executes a sequence of independent local transactions. Each service commits locally and publishes an event.

• Compensating Transactions: If a step fails (e.g., Payment declined), the Saga controller executes reverse compensating actions (e.g., release reserved inventory).
• Choreography: Decentralized services listen to event queues. Simple, but hard to trace.
• Orchestration: Central Saga coordinator manages flow and failure recovery explicitly.

Traditional hashing (hash(key) % N) fails when node count $N$ changes: nearly 100% of keys hash to new servers, invalidating caches and crashing backends.

1. The Hash Ring

• Maps both server IP addresses and item keys onto a shared circular hash space ($0$ to $2^{32}-1$).
• To route a key: locate its position on the ring and move clockwise to the first server node encountered.

2. Node Additions & Removals

• Adding a new Node X only re-allocates keys located between Node X and its immediate counter-clockwise neighbor.
• Only $1/N$ of keys are relocated during node changes.

3. Virtual Nodes (V-Nodes)

• Prevents hotspots by mapping each physical server to 100-200 virtual positions (ServerA-1, ServerA-2) on the ring.
• Ensures uniform load distribution across heterogeneous hardware.

Rate limiters protect downstream APIs from denial-of-service, abuse, and resource exhaustion.

1. Core Algorithms

• Token Bucket: Bucket holds $N$ tokens refilling at rate $R$. Requests consume 1 token. Supports traffic bursts.
• Sliding Window Log: Stores timestamps of user requests in Redis Sorted Sets. Accurately counts requests in rolling window, but higher memory usage.
• Sliding Window Counter: Approximates requests by combining current fixed window count with weighted previous window count. Highly memory efficient.

2. Distributed Scaling & Race Conditions

To prevent race conditions when multiple API gateways check and update counters concurrently:

• Redis Cluster + Lua Scripts: Execute rate limit checks and counter increments in atomic Lua scripts inside Redis. This guarantees execution atomicity without network lock overhead.
• Local Gateway In-Memory Batching: Gateways enforce soft limits locally and sync counter deltas asynchronously to Redis.

A Cache Stampede occurs when a popular cache key expires, causing thousands of concurrent read requests to miss the cache and hit the database simultaneously.

Mitigation Strategies

1. Mutex Locking (Single-Flight Pattern):

When a cache miss occurs, the application acquires a distributed lock (via Redis Redlock). Only the thread holding the lock queries the DB to refresh the cache. Other requests wait brief milliseconds and read the updated cache.

1. Probabilistic Early Expiration (XFetch Algorithm):

As a key approaches expiration, a probability formula determines whether a read request should trigger a background cache refresh before the key officially dies.

1. Logical Expiry with Background Refresh:

Set cache keys to never expire physically in Redis. Store a logical timestamp inside the cached object. When the logical expiry passes, serve stale data immediately while dispatching an async worker to update the cache.

Single database auto-increment keys create severe write bottlenecks and single points of failure in distributed architectures.

Twitter Snowflake 64-Bit Structure

• 1 Bit (Unused): Reserved sign bit (always 0).
• 41 Bits (Timestamp): Milliseconds since custom epoch (~69 years lifespan).
• 5 Bits (Datacenter ID): Up to 32 datacenters.
• 5 Bits (Worker Node ID): Up to 32 worker nodes per datacenter.
• 12 Bits (Sequence Number): Up to 4,096 IDs per millisecond per node.

Key Architectural Advantages

• Zero Network Coordination: Nodes generate unique IDs locally without calling a centralized master service.
• Naturally Time-Sorted: Leading timestamp bits ensure IDs sort chronologically, preserving B-Tree index insert efficiency.
• High Throughput: A cluster of 1,024 nodes can generate over 4 million IDs per millisecond.

Apache Kafka scales throughput by splitting topics into append-only commit log segments called Partitions.

1. Partition Routing & Ordering

• Messages with the same partition key (e.g., user_id) route to the exact same partition.
• Kafka guarantees strict message ordering only within a single partition.

2. Consumer Group Scaling

• A Consumer Group is a cluster of workers co-operating to process topic messages.
• Each partition is assigned to exactly one consumer worker within a consumer group.
• Max Concurrency Limit: If a topic has 4 partitions and you launch 6 consumers in a group, 2 consumers will sit idle. To scale consumers, increase partition count.

3. Delivery Guarantees

• At-Most-Once: Commit offset before processing. Fast, but messages are lost if worker crashes.
• At-Least-Once: Commit offset after processing. Messages are re-delivered on failure; requires downstream handlers to be idempotent.
• Exactly-Once: Combines idempotent producers and transactional consumer offset commits.

Real-time applications require choosing between client-initiated pull mechanisms and server-initiated push streams.

A Hot Partition occurs when data or requests distribute unevenly, overloading a single partition node. For example, a celebrity user with 80 million followers posting a update.

1. Hybrid Fan-Out Architecture

• Fan-Out on Write (Push): Prepend posts to every follower's inbox cache. Excellent for standard users (fast read latency), but fails for celebrities (writing 80M entries crashes workers).
• Fan-Out on Read (Pull): Timelines are computed at query time by pulling posts from followed accounts. Saves write operations, but makes reads slow.
• Hybrid Pattern: Use Push for standard users (<10k followers). For celebrities, do not fan out on write. Instead, when followers load feeds, pull celebrity posts on-the-fly and merge them into the cached inbox.

2. Shard Key Salting

Append a random suffix to high-cardinality keys (CELEB_POST_1, CELEB_POST_2) to distribute write load across 10 distinct physical partitions, aggregating them during reads.

The CAP Theorem proves that during a network partition (P), a distributed system must choose between Availability (A) and Consistency (C).

The PACELC Theorem Extension

PACELC extends CAP by incorporating normal operating conditions when no network partition exists:

• If Partition (P): Choose between Availability (A) vs. Consistency (C).
• Else (E): Choose between Latency (L) vs. Consistency (C).

System Classifications

• PA/EL (DynamoDB, Cassandra): Prioritizes Availability during partitions and low Latency during normal operations. Reads may return stale data briefly.
• PC/EC (Spanner, Relational DBs): Prioritizes Consistency at all times. Will reject writes/reads or wait for global consensus before returning.

Databases store records differently on disk based on whether their workload is write-heavy or read-heavy.

B-Tree (Read-Optimized: PostgreSQL, MySQL)

• Organizes data in self-balancing multi-way trees on disk.
• Updates pages in-place via random disk I/O.
• Pros: Lightning-fast point lookups ($O(\log N)$) and range queries.
• Cons: High write amplification due to page rewrites.

LSM-Tree (Write-Optimized: Cassandra, RocksDB)

• Appends all writes sequentially to an in-memory buffer (MemTable) and Write-Ahead Log (WAL).
• Flushes MemTable periodically to immutable sorted disk files (SSTables). Background threads compact duplicate keys.
• Pros: Ultra-fast write speeds via sequential disk appends.
• Cons: Read path requires searching multiple SSTables using Bloom Filters.

When a service experiences transient outages or load spikes, naive retries immediately trigger cascading failures.

1. Exponential Backoff

Increase wait times exponentially between successive retries: delay = min(base * (2 ^ attempt), max_delay)

2. Adding Jitter (Random Noise)

If 5,000 requests fail simultaneously (e.g. network blip), exponential backoff will still cause all 5,000 clients to retry at the exact same millisecond. Adding Full Jitter randomizes retry times: delay_with_jitter = random(0, delay)

import random
import time

def call_with_retry(api_func, max_attempts=5):
    for attempt in range(max_attempts):
        try:
            return api_func()
        except Exception as e:
            if attempt == max_attempts - 1:
                raise e
            backoff = min(30, 0.5 * (2 ** attempt))
            jittered_delay = random.uniform(0, backoff)
            time.sleep(jittered_delay)

SQL LIKE '%keyword%' queries cause full table scans that fail at scale. Elasticsearch uses an Inverted Index for instant fuzzy searches and faceted filtering.

1. Inverted Index Mechanics

A dictionary mapping every unique word to the specific document IDs containing it. Searching "Wireless Noise Canceling Headphones" intersects candidate lists in milliseconds.

2. Sharding & Replica Distribution

• Primary Shards: Document collections are partitioned across primary shards (hash(_id) % primary_shards).
• Replica Shards: Read-only copies of primary shards. Replicas scale concurrent search queries horizontally and guarantee failover.

An API Gateway acts as the single secure entry point for all client requests into internal microservices.

Core Edge Responsibilities

1. SSL/TLS Termination: Decrypts HTTPS at the gateway edge, passing unencrypted HTTP/TCP internally to reduce CPU load on microservices.
2. Reverse Proxy & Routing: Maps external URI paths (/api/v1/orders) to internal service IPs using Service Discovery (Eureka/Consul).
3. Cross-Cutting Concerns: Enforces central rate limiting, CORS headers, security payload sanitization, and request tracing headers (X-Request-ID).

When cache memory is exhausted, an eviction policy decides which keys to remove to free space for new entries.

1. Least Recently Used (LRU)

Evicts keys that haven't been read or written to for the longest time.

• Pros: Simple, effective for temporal access patterns.
• Cons: A one-time sequential scan can evict hot keys from cache memory.

2. Least Frequently Used (LFU)

Evicts keys with the lowest total access frequency counter.

• Pros: Keeps frequently accessed keys cached regardless of recent access gaps.
• Cons: Historical hot keys remain cached even after their popularity fades.

3. Adaptive Replacement Cache (ARC)

Dynamically tunes balance between LRU and LFU using ghost lists.

• Pros: Outperforms LRU and LFU across mixed workloads.
• Cons: Higher memory overhead and patent licensing constraints.

When a downstream microservice is slow or failing, continuing to send requests exhausts caller thread pools, crashing caller services.

Circuit Breaker States

1. CLOSED (Normal Operation):

Requests pass through. Failure counts are tracked in a sliding window.

1. OPEN (Tripped Failure State):

If error rate exceeds threshold (e.g. 50%), circuit trips to OPEN. Requests fail immediately with a fallback response without calling downstream.

1. HALF-OPEN (Trial Probe State):

After a sleep window (e.g. 30s), limited trial requests are allowed through. If successful, circuit resets to CLOSED; if failed, returns to OPEN.

{
  "slidingWindowSize": 100,
  "failureRateThreshold": 50.0,
  "waitDurationInOpenState": "30s"
}

Database replication distributes copies of data across nodes for high availability and read scaling.

1. Master-Replica (Leader-Follower)

• Writes execute exclusively on the Master node.
• Master streams write logs to Replica nodes for read processing.
• Trade-off: Simple, scales reads easily, but Master is a write SPOF and replicas face replication lag.

2. Multi-Master (Leader-Leader)

• Multiple nodes accept writes concurrently.
• Trade-off: High write availability across regions, but requires complex write conflict resolution.

3. Leaderless (Quorum-Based: Cassandra)

• Any node accepts writes and reads. Quorum consensus determines success.
• Quorum Formula: $R + W > N$ (where $R$ = read quorum, $W$ = write quorum, $N$ = total replicas). Guarantees strongly consistent reads.

Content Delivery Networks (Cloudflare, Fastly, AWS CloudFront) move content closer to global end users.

1. Anycast Routing

Multiple CDN edge servers across the globe share the exact same IP address. BGP routing automatically sends client TCP packets to the geographically closest POP server.

2. Edge Caching Mechanics

• Static Caching: Edge POPs cache images, JS/CSS bundles, and video segments using Cache-Control: public, max-age=31536000.
• Dynamic Acceleration: For un-cacheable APIs, CDNs maintain persistent warmed TCP/TLS connections to origin servers, bypassing slow BGP handshakes.

3. Origin Shielding

Inserts a secondary caching tier between edge POPs and origin DBs, protecting backends during global cache purges.

Distributed locks prevent race conditions when background workers attempt to execute non-idempotent operations simultaneously.

1. Redis Redlock Algorithm

• Worker requests locks from $N$ independent Redis instances with a short TTL.
• Lock is granted if acquired from a majority ($N/2 + 1$) of nodes within lock validity duration.
• Trade-off: Extremely fast, but sensitive to system clock drifts across nodes.

2. ZooKeeper / Etcd Consensus Locks

• Worker creates an Ephemeral Sequential Node in ZooKeeper.
• The worker holding the lowest sequence number owns the lock. Other workers watch the previous node for deletion.
• Trade-off: Strongly consistent (CP in CAP), immune to clock drift, but incurs higher node latency.

Microservice communication protocols directly impact CPU utilization, network bandwidth, and API schema governance.

Why gRPC Excels Internally

• Strict Type Safety: Strongly-typed .proto schema files generate client/server code automatically.
• HTTP/2 Multiplexing: Thousands of concurrent RPC calls share a single TCP connection stream.

Building a system to push millions of mobile/web notifications per minute requires decoupled asynchronous processing pipelines.

Architecture Flow

1. API Ingestion: Accepts notification triggers, assigns priority queues (Transactional vs. Promotional).
2. User Device Registry: Resolves user IDs to device tokens (iOS APNs / Android FCM tokens) using a partitioned DB.
3. Message Fan-Out Queue (Kafka): Pushes message payloads to Kafka topic partitions distributed by device token hash.
4. Worker Clusters: Async workers batch requests to Apple APNs and Google FCM HTTP/2 push endpoints.

Traditional file systems crash when storing billions of large media assets or unstructured log files.

1. Separation of Metadata and Data

• Metadata Tier: Stores file names, permissions, and block mapping locations in a fast in-memory key-value database.
• Block Storage Tier: Splits files into fixed chunks (e.g., 128 MB blocks) stored on commodity storage nodes.

2. Erasure Coding vs 3x Replication

• 3x Replication: Copies every data block across 3 physical racks. Fast, but incurs 200% storage overhead.
• Erasure Coding (Reed-Solomon 8+4): Splits data into 8 data blocks + 4 parity blocks. Can recover from 4 node failures with only 50% storage overhead.

Load balancers operate at different OSI layers, balancing packet processing speed against application routing intelligence.

Layer 4 Load Balancing (Transport Layer)

• Routes TCP/UDP packets without reading application payloads.
• Pros: Blazing fast throughput, minimal CPU usage, handles high connection counts.
• Cons: Cannot inspect HTTP headers, cookies, or URL paths. No smart routing.

Layer 7 Load Balancing (Application Layer)

• Terminates TLS, parses HTTP headers, cookies, and JSON URIs.
• Pros: Intelligent path routing (/api/v1/orders → Order Pods), header rewrite, gRPC balancing.
• Cons: Higher CPU overhead due to packet decryption and HTTP parsing.

Public clients (React SPAs, Mobile Apps) cannot securely store Client Secrets. Standard Authorization Code Grant exposes them to interception attacks.

How PKCE Prevents Interception

1. Code Verifier Generation: App generates a random high-entropy string (code_verifier).
2. Code Challenge Creation: App hashes the verifier using SHA-256 (code_challenge = Base64(SHA256(code_verifier))).
3. Authorization Request: Client sends user to Auth Server with code_challenge and code_challenge_method=S256.
4. Token Exchange: When Auth Server returns the authorization_code, the app sends the original code_verifier. Auth Server hashes it and verifies match before issuing JWT tokens.

Selecting the correct cache update flow is critical to prevent data drift between cache keys and underlying databases.

1. Cache-Aside (Lazy Loading)

• Read: App queries cache. On miss, app reads DB and populates cache.
• Write: App writes directly to DB, then invalidates/deletes the cache key.
• Pros: Resilient to cache crashes. Only requested data is cached.

2. Write-Through

• App writes to Cache. Cache synchronously updates DB before returning success.
• Pros: High consistency, read hits guaranteed.
• Cons: Higher write latency.

3. Write-Back (Write-Behind)

• App writes to Cache. Cache acknowledges immediately and writes to DB asynchronously in background batches.
• Pros: Ultra-high write throughput.
• Cons: Risk of data loss if cache node crashes before flushing to DB.

A Service Mesh offloads networking logic (retries, mTLS, telemetry) from application code into infrastructure sidecar proxies.

Architecture Layers

• Data Plane (Envoy Sidecars): Runs as a sidecar container alongside every app pod, intercepting all inbound and outbound network traffic.
• Control Plane (Istio / Linkerd): Central controller that translates config rules and distributes mTLS certificates to proxies.

Key Capabilities

• Automatic mTLS: Encrypts service-to-service communication transparently without code changes.
• Traffic Shifting: Enables canary deployments by splitting traffic percentages (e.g. 90% v1, 10% v2).
• Distributed Tracing: Injects standard tracing headers (x-request-id, x-b3-traceid) across call graphs.

Monitoring systems process millions of time-series data points per second for real-time alerting and historical dashboards.

Architecture Components

1. Data Collection (Pull vs Push): Prometheus pulls metrics from /metrics HTTP endpoints. Datadog agent pushes metrics via UDP/StatsD.
2. Time-Series DB Engine (TSDB): Stores timestamps, metric names, and labels using delta-of-delta compression.
3. Aggregations & Downsampling: Background jobs aggregate raw second-level metrics into 1-minute and 1-hour rollups, moving cold metrics to object storage.

Opening a new database TCP connection per request takes 30-100ms. Connection pools maintain pre-allocated database connections for instant reuse.

Pool Sizing Mechanics

Counterintuitively, smaller connection pools often yield better performance than massive pools due to reduced CPU context switching and disk lock contention.

PostgreSQL Recommended Formula

connections = (CPU_cores * 2) + effective_spindle_count

# HikariCP Configuration
maximumPoolSize: 10
minimumIdle: 10
idleTimeout: 600000
connectionTimeout: 30000

Network retries can cause clients to submit payment requests multiple times. Idempotency guarantees that executing an operation multiple times yields the exact same result as executing it once.

Step-by-Step Implementation

1. Client Generation: Client generates a unique UUID Idempotency-Key header for the transaction request.
2. Gateway Lock Check: API Gateway attempts to acquire a Redis lock for idempotency_key.
3. If key exists and status is PROCESSING, return HTTP 409 Conflict or wait.
4. If key exists and status is COMPLETED, return the cached payment response payload immediately.
5. Execute & Store: Process payment, record transaction in DB, save response payload in Redis with 24h TTL, and release lock.

Choosing the right real-time mechanism depends on directionality, network environments, and connection lifecycle requirements.

1. Long Polling

• Client requests data, server holds connection open until update arrives or timeout occurs.
• Best For: Fallback environments with strict corporate HTTP proxies blocking WebSockets.

2. Server-Sent Events (SSE)

• Single persistent HTTP/2 connection. Server streams text/event data to client continuously.
• Pros: Built-in auto-reconnect, native HTTP/2 support, zero custom proxy configuration.
• Best For: AI chat response streaming (ChatGPT), live stock charts, notification feeds.

3. WebSockets

• Full-duplex persistent TCP connection for instant bi-directional messaging.
• Best For: Real-time multiplayer games, collaborative canvas editors, live chat rooms.

In microservice architectures, a single user click triggers calls across dozens of services. Distributed tracing tracks request execution paths across boundaries.

Context Propagation Headers (W3C Trace Context)

Services inject HTTP headers into downstream RPC requests:

• traceparent: 00-4bf92f3577b34da6a3ce929d0e0e4736-00f067aa0ba902b7-01
• Trace ID (`4bf9...`): Unique identifier shared across the entire call graph.
• Span ID (`00f0...`): Unique identifier for an individual operation within a service.

Head-Based vs Tail-Based Sampling

• Head-Based Sampling: Decides to sample a trace at the initial API Gateway. Efficient, but might miss rare errors.
• Tail-Based Sampling: Collects all spans first, sampling 100% of traces containing HTTP 5xx errors or latency anomalies.

Active-Active multi-region deployments run live application stacks in two or more geographic regions simultaneously.

Recovery Metrics

• RPO (Recovery Point Objective): Maximum acceptable data loss duration during failover.
• RTO (Recovery Time Objective): Maximum acceptable system downtime duration.

Architecture Challenges

1. Global Traffic Routing: Use Route53 / Cloudflare Latency-Based DNS to route users to the nearest healthy region.
2. Cross-Region Replication: Replicate database writes asynchronously across regions. Set up Conflict-Free Replicated Data Types (CRDTs) or last-write-wins to resolve write collisions.
3. Split-Brain Mitigation: Deploy a third tie-breaker quorum region to prevent both regions from declaring master status independently.

Designing a URL shortener requires handling high read-to-write ratios (100:1) with sub-10ms redirection latencies.

1. Short Key Generation: Base62 Encoding

Convert an auto-incrementing 64-bit integer ID into a 7-character string using Base62 ([a-z, A-Z, 0-9]): $62^7 \approx 3.52 \text{ trillion unique URLs}$

2. Preventing Counter Bottlenecks

Instead of hitting a central DB counter per request, pre-allocate ranges of IDs (e.g. Node 1 gets IDs 1–1,000,000, Node 2 gets 1,000,001–2,000,000) to key generator instances.

3. Redirection Flow & Caching

• HTTP 301 (Permanent Redirect): Browser caches redirection locally. Reduces server load, but hides click analytics.
• HTTP 302 (Found / Temporary): Every click hits the URL shortener service, updating analytics counters while reading destination URLs from Redis.

A Bloom Filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set.

Key Properties

• No False Negatives: If the Bloom Filter returns False, the item definitely does not exist in the database.
• Possible False Positives: If it returns True, the item probably exists in the database.

How It Works

1. Consists of a bit array of $m$ bits initialized to 0 and $k$ independent hash functions.
2. When adding an item, hash it $k$ times and set the bit positions to 1.
3. To query an item, check if all $k$ bit positions are 1. If any bit is 0, skip the database lookup completely.

Crawling billions of web pages requires managing distributed URL queues, respecting site rates, and eliminating duplicate pages.

Architecture Components

1. URL Frontier: Priority queue managing URLs to crawl, split by host domain to enforce politeness delays (e.g. 1s between requests to the same domain).
2. DNS Resolver Cache: Caches domain IP lookups locally to eliminate DNS resolution latency bottlenecks.
3. Fetcher Workers: Async HTTP workers fetching web pages concurrently.
4. Deduplication Engine (SimHash): Computes fingerprint hashes of HTML content to detect near-duplicate pages before indexing.

Event Sourcing and CQRS decouple write domain business logic from complex query reporting models.

1. Event Sourcing

• Instead of storing current state in a DB table row, store an immutable sequence of state-changing events (OrderCreated, PaymentReceived, OrderShipped).
• Current state is reconstructed by replaying events sequentially.
• Pros: Complete audit log, time-travel debugging.
• Cons: Event schema evolution complexity and slow state rebuilds without periodic snapshots.

2. CQRS

• Separates write operations (Commands) from read operations (Queries).
• Writes hit a normalized OLTP DB; changes stream via Kafka to populate an optimized read-model DB (e.g., Elasticsearch).

Rate limiters protect infrastructure using different traffic shaping algorithms.

Algorithm Choice Guidelines

• Use Token Bucket for general API rate limiting where brief user bursts are acceptable.
• Use Leaky Bucket when downstream services require smooth, non-bursty ingress rates.

A Deadlock occurs when two or more database transactions hold locks on records that the other transactions need, creating a circular wait state.

Deadlock Scenario

• Tx A locks Row 1, requests lock on Row 2.
• Tx B locks Row 2, requests lock on Row 1.
• Neither transaction can proceed.

Resolution Strategies

1. Wait-For Graph Detection: DB engine maintains a directed graph of transactions waiting for locks. If a cycle is detected, the engine aborts the victim transaction with a lower execution cost.
2. Lock Timeout: Aborts any transaction that waits longer than lock_timeout (e.g. 5s).

Redis achieves sub-millisecond latencies by storing all data in memory and using an asynchronous single-threaded event loop.

1. Single-Threaded Event Loop (I/O Multiplexing)

Uses Linux epoll system calls to process thousands of client socket requests sequentially on a single CPU core without lock contention or context switching.

2. Incremental Hash Resizing (Rehash)

When Redis hash tables expand, dict entries migrate incrementally across background requests to avoid blocking the main event thread.

3. Persistence Modes

• RDB (Snapshotting): Point-in-time binary snapshot saved to disk at configured intervals.
• AOF (Append-Only File): Logs every write command sequentially. Recovered by replaying log records.

Deploying code updates safely requires balancing release speed against outage risks.

1. Blue-Green Deployment

• Maintains two identical production environments (Blue = active live, Green = new version).
• Switch router traffic to Green instantly.
• Pros: Instant rollback by switching router back to Blue.
• Cons: Doubles infrastructure costs.

2. Canary Deployment

• Routes a small percentage of live traffic (e.g., 5%) to the new version. Monitors error rates before expanding to 100%.
• Pros: Minimizes blast radius of bugs.
• Cons: Requires complex router traffic management.

3. Rolling Deployment

• Updates instances incrementally (e.g., 25% at a time) within the cluster.
• Pros: Zero extra infrastructure cost.
• Cons: Slow rollbacks if bugs appear late in the rollout.

Protecting user credentials and sensitive PII data requires multiple layers of cryptographic defense.

1. Password Hashing (Argon2id / bcrypt)

Never store plaintext passwords or plain MD5/SHA256 hashes. Use salted, adaptive memory-hard algorithms like Argon2id or bcrypt with a work factor $\ge 12$ to prevent GPU brute-force attacks.

2. Envelope Encryption for PII Data

• Data Encryption Key (DEK): Encrypts sensitive database column data locally.
• Key Encryption Key (KEK): Stored securely in HSM / AWS KMS to encrypt the DEK.

# Hashing passwords securely
import bcrypt

hashed_password = bcrypt.hashpw(password.encode('utf-8'), bcrypt.gensalt(rounds=12))

Searching for nearby restaurants or drivers using standard 2D SQL WHERE lat BETWEEN x AND y queries causes full table scans at scale.

1. Geohash Indexing

• Converts 2D latitude and longitude coordinates into a 1D string hash (e.g., 9q9hv).
• Characters share common prefixes for geographically close locations. Shorter prefixes denote larger bounding boxes.

2. Google S2 Geometry

• Maps Earth onto a 3D cube decomposed into hierarchical cells (Level 0 to 30).
• Provides uniform cell area shapes without Geohash edge-boundary anomalies.

3. QuadTree Spatial Index

In-memory tree where every parent node splits into 4 sub-quadrants when node item counts exceed threshold capacity.

Allowing multiple microservices to read and write directly to a shared relational database breaks microservice autonomy.

Drawbacks of Shared Databases

1. Tight Schema Coupling: Modifying a table column in Service A breaks queries in Service B, forcing coordinated deployments.
2. Resource Lock Contention: High write queries in Order Service consume CPU and lock tables needed by User Service.
3. Loss of Polyglot Persistence: Forces all services to use the same database engine regardless of data access model suitability.

Database-Per-Service Pattern

Each microservice owns its private database. Other services access data exclusively via published REST/gRPC APIs or asynchronous domain events.

Real-time collaborative editors allow multiple users to edit the exact same document concurrently without conflicts or lost edits.

1. Operational Transformation (OT: Google Docs)

• Relies on a central server to transform and sequence edit operations.
• If User A inserts "X" at index 2 while User B deletes at index 1, the server transforms User A's operation index to 1 before broadcasting.
• Pros: Minimal memory footprint per operation.
• Cons: Extremely complex server transformation algorithms.

2. CRDTs (Conflict-Free Replicated Data Types: Figma / Notion)

• Mathematical data structures that converge automatically to the exact same state across peer nodes without requiring a central server.
• Pros: Supports offline editing and peer-to-peer synchronization natively.
• Cons: Higher memory overhead due to unique operation identifier tombstones.