Load Balancing Google.com Front Ends: Server Selection Strategies and Data Structures

You are asked to design a simple load balancer for Google.com: the component that receives incoming user requests and distributes them across a pool of front-end servers. Explain how it would choose a server for each request, and which data structures it would need to make that choice quickly. ### Clarifying Questions - Where does this load balancer sit: in front of the web servers inside one data center, or at the global level, deciding which data center serves a user? - Are requests stateless, or must a user's requests keep reaching the same server? - Do all front-end servers have the same capacity, or can some machines take more load than others? - How quickly must the balancer react when a server fails or comes back? ### Part 1 — Choosing a server for each request Propose one or more strategies the load balancer can use to pick a server, and explain how it learns which servers are healthy and how busy they are. ```hint Start with the simplest policy Begin with the most basic policy that works. What does it get wrong once servers differ in capacity or some requests take much longer than others, and what extra information would the balancer need to fix that? ``` #### What This Part Should Cover - At least two selection strategies and the situations each fits - How health and load information reaches the balancer, and how stale it can be - What happens when a server fails, recovers or is added ### Part 2 — Data structures behind the choice For each strategy, describe the state the load balancer keeps in memory and the data structure that holds it, including the cost of picking a server and of updating that state. ```hint Count the operations Picking a server happens on every request, while a health or load update happens far less often. Which structure makes the frequent operation cheap without making the rare one expensive? ``` #### What This Part Should Cover - A named data structure per strategy and what it stores - Time complexity of selecting a server and of applying an update - How the structure copes with servers being removed or added and with many requests arriving at once ### What a Strong Answer Covers - Clear placement of the load balancer and its two jobs: spreading load and steering traffic away from failures - Strategies suited to very high traffic, with the trade-off between simplicity and load awareness made explicit - Data structures with correct costs on the per-request path - Keeping the load balancer itself from becoming a single point of failure - What users experience (latency, errors) and how you would tell the design is working ### Follow-up Questions - How would you keep a user's requests on the same server, and what happens to that user when the server goes down? - The load balancer itself fails or becomes the bottleneck. How do you scale it and remove the single point of failure? - How would a user be routed to a nearby data center before any of this per-server balancing happens?