Bird
Raised Fist0

Load Balancing Algorithms - Round Robin, Least Connections, IP Hash, Weighted

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Load Balancing Algorithms - Round Robin, Least Connections, IP Hash, Weighted
Design and evaluate load balancing algorithms with scale and failure modes in mind
mediumLoad BalancersFreq: common
⚙️
Functional Requirements
  • Distribute incoming client requests evenly across backend servers
  • Support multiple load balancing algorithms: Round Robin, Least Connections, IP Hash, Weighted
  • Maintain session affinity when required (sticky sessions) using IP Hash or cookies
  • Provide health checks to detect and exclude unhealthy backend servers
  • Allow dynamic weight adjustment for Weighted load balancing
  • Expose metrics for monitoring load distribution and server health
📊
Non-Functional Requirements
  • Handle peak write QPS of approximately 925K requests/sec (derived from 2B DAU × 40 req/user/day)
  • Achieve 99.99% availability with failover within 100ms
  • Maintain request routing latency under 5ms P99 at load balancer layer
  • Support horizontal scaling to 10,000+ backend servers
  • Ensure consistent routing decisions under concurrent updates to backend pool
❓
Clarifying Questions to Ask
  • What is the expected number of backend servers to balance across?
  • Are sticky sessions mandatory or optional for all algorithms?
  • How frequently do backend server health states change?
  • Is the load balancer stateful or stateless?
  • What is the expected request size and protocol (HTTP, TCP)?
  • Are weight adjustments manual or automated based on metrics?
Out of Scope
✗ Design of backend application servers or their scaling
✗ Detailed network infrastructure (e.g., BGP, DNS) beyond load balancer scope
✗ Security features like DDoS mitigation or TLS termination
✗ Client-side retry or fallback logic
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user generates 40 requests per day on average
  • Average request size is 100 bytes
  • Backend server pool size is 10,000 servers
⚡
QPS Calculation
write qps2,000,000,000 × 40 / 86400 ≈ 925,926 requests/sec
peak write qpsAssuming 2× peak factor: 925,926 × 2 ≈ 1,851,852 requests/sec
read qpsAssuming read requests are 3× write: 925,926 × 3 ≈ 2,777,778 requests/sec
💾
Storage Estimate
daily storage bytes925,926 req/sec × 100 bytes × 86400 sec ≈ 8 TB/day
retention days7
total storage with replication8 TB × 7 days × 3 replicas = 168 TB
🖥️
Server Estimate
load balancer nodesAssuming each LB node handles 50K req/sec, need 1,851,852 / 50,000 ≈ 38 nodes
health check workersAssuming 1 worker per 500 servers, 10,000 / 500 = 20 workers
🏗️
Architecture Diagram
Architecture Diagram
          +----------------------+
          |   Client Requests    |
          +----------+-----------+
                     |
          +----------v-----------+
          |  Load Balancer Layer |
          | (Round Robin, Least  |
          |  Connections, IP Hash|
          |  Weighted Algorithms)|
          +----------+-----------+
                     |
          +----------v-----------+
          | Backend Server Pool  |
          |  (10,000 servers)    |
          +----------+-----------+
                     |
          +----------v-----------+
          | Health Check Service |
          +----------------------+
🧩
Components
Load Balancer Layer
Receives client requests and routes them to backend servers using selected algorithms
Why thisEnvoy Proxy supports multiple load balancing algorithms natively with low latency and high throughput
Why notNginx lacks native support for weighted least connections at scale and requires complex config reloads
Health Check Service
Periodically probes backend servers to update their health status for routing decisions
Why thisConsul Health Checks provide distributed, consistent health status with TTL and event-driven updates
Why notSimple cron-based scripts do not scale or provide real-time health status at 10,000 servers
Backend Server Pool
Hosts application instances receiving routed requests
Why thisStateless microservices allow horizontal scaling and easy load balancing
Why notStateful servers require session replication, complicating load balancing and scaling
Configuration Store
Stores backend server metadata, weights, and algorithm configurations
Why thisEtcd provides strongly consistent distributed key-value store with watch APIs for dynamic config updates
Why notZooKeeper has higher latency and operational complexity at this scale
Metrics & Monitoring
Collects load balancer and backend metrics for health and performance monitoring
Why thisPrometheus integrates with Envoy and Consul for real-time metrics and alerting
Why notCustom logging solutions lack scalability and real-time alerting capabilities
🔄
Data Flow
1
Client → Load Balancer Layer
Client sends request to load balancer IP
Load balancer receives request and selects algorithm based on config
2
Load Balancer Layer → Configuration Store
Load balancer fetches backend server list and weights
Uses Etcd watch API to get real-time updates
3
Load Balancer Layer → Health Check Service
Checks backend server health status
Excludes unhealthy servers from routing
4
Load Balancer Layer → Backend Server Pool
Routes request using selected algorithm (e.g., Round Robin, Least Connections)
Ensures session affinity if IP Hash or weighted algorithm is selected
5
Backend Server Pool → Client
Processes request and sends response back
Response latency monitored for SLA adherence
6
Health Check Service → Configuration Store
Updates health status of backend servers
Triggers load balancer to refresh routing tables
7
Metrics & Monitoring → Operations Dashboard
Streams metrics for load distribution and errors
Alerts on anomalies or backend failures

Practice

(1/5)
1. A high-throughput messaging system must decouple 1 million writes per second from fan-out delivery to thousands of clients. Which component best handles this decoupling to ensure durability and scalability?
easy
A. Use a distributed log system like Kafka partitioned by conversation ID
B. Use a relational database with row-level locking to queue messages
C. Use Redis as an in-memory queue with TTL for message expiration
D. Use direct synchronous HTTP calls from sender to all recipients

Solution

  1. Step 1: Identify the decoupling requirement

    Relational DB with row-level locking (Use a relational database with row-level locking to queue messages) cannot handle 1M writes/sec due to locking and durability overhead. Redis (Use Redis as an in-memory queue with TTL for message expiration) lacks durability guarantees and TTL causes message loss risk. Direct synchronous calls (Use direct synchronous HTTP calls from sender to all recipients) block sender and don't scale.

  2. Step 2: Evaluate Kafka's suitability

    Kafka partitions by conversation ID ensure ordering and durability, enabling scalable fan-out with consumer groups.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Kafka partitions -> durable, scalable decoupling [check]
Hint: Distributed logs decouple writes and fan-out reliably [check]
Common Mistakes:
2. A web crawler must efficiently avoid re-crawling the same URLs too frequently while ensuring freshness. Which component best handles URL scheduling and politeness constraints?
easy
A. Implement a URL Frontier with priority queues and politeness policies
B. Use a distributed key-value store to store page content for freshness checks
C. Rely on the PageRank component to prioritize URLs for crawling
D. Use a message queue to distribute URLs randomly among crawler workers

Solution

  1. Step 1: Identify URL scheduling role

    The URL Frontier manages which URLs to crawl next, enforcing politeness and freshness constraints.

  2. Step 2: Evaluate other components

    PageRank ranks pages post-crawl, not for scheduling. Distributed KV stores hold content but don't schedule. Random distribution ignores politeness.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    URL Frontier enforces crawl politeness and freshness [check]
Hint: URL Frontier schedules URLs with politeness [check]
Common Mistakes:
3. In the DNS resolution chain, at step 4 the recursive DNS server receives a referral response from the root server pointing to a TLD server. What state does the recursive server enter immediately after receiving this referral?
easy
A. It caches the referral to the TLD server and initiates a query to the TLD server
B. It discards the referral and retries querying the root server
C. It caches the IP address of the root server and returns it to the client
D. It forwards the referral directly to the client without caching

Solution

  1. Step 1: Understand recursive server behavior on referral

    When the recursive DNS server receives a referral from the root server, it caches the referral information (the TLD server's IP) and then queries the TLD server itself.

  2. Step 2: Eliminate incorrect states

    It does not cache the root server IP (already known), nor does it discard the referral or forward it directly to the client. The recursive server handles the full resolution chain transparently.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Recursive server caches referral and queries next server [check]
Hint: Recursive server caches referrals and queries next hop [check]
Common Mistakes:
4. For a search system with highly skewed term distributions and frequent query updates, which scoring approach is better and why?
medium
A. Use classic TF-IDF because it is simpler and faster to compute
B. Use raw term frequency only to avoid overhead of inverse document frequency
C. Use BM25 because it handles term saturation and document length normalization better
D. Use a vector space model with cosine similarity ignoring term frequency

Solution

  1. Step 1: Analyze term distribution and query update needs

    Skewed term distributions cause TF-IDF to overweight rare terms excessively; frequent updates require robust scoring.

  2. Step 2: Evaluate scoring methods

    BM25 accounts for term frequency saturation and normalizes by document length, improving relevance in skewed data; TF-IDF and raw TF lack these refinements; vector space ignoring TF loses relevance signals.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    BM25 handles skew and length normalization better than TF-IDF [check]
Hint: BM25 normalizes length and term saturation better than TF-IDF [check]
Common Mistakes:
5. At 10x scale, which component in an object storage system is most likely to fail first and why?
hard
A. The object storage data nodes, because they cannot handle the increased network bandwidth.
B. The metadata/index service, because it maintains a global namespace and becomes a bottleneck under massive concurrent requests.
C. The client-side caching layer, because it runs out of memory with large object counts.
D. The underlying block storage devices, because they have limited IOPS.

Solution

  1. Step 1: Identify scaling bottlenecks in object storage

    Object storage separates data and metadata; metadata/index service manages global namespace and object lookup.

  2. Step 2: Analyze impact of 10x scale

    Metadata service faces massive concurrent requests and metadata updates, becoming a centralized bottleneck before data nodes or storage devices.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Metadata service bottlenecks first at massive scale [check]
Hint: Metadata service bottlenecks first at massive object scale [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard