Design a simple load balancer for Google.com. What data structures would you use?

Question

Design a simple load balancer for Google.com. What data structures would you use?

Asked at Google over a year ago

8.3k views

Asked at

8.3k views

How to answer Technical questions

Interview Guide

Top Technical interview questions

Imagine you're the product manager for Facebook Marketplace. Since many sellers don't mark items as sold, what existing functionality and metrics could you use to determine whether an item has likely sold?7 answers | 20.9k views
What happens when you enter a URL in your browser?6 answers | 10.8k views
How would you determine how to rank posts in the newsfeed?4 answers | 3.3k views
See Technical PM Interview Questions

Invite members
Invite by email

Add another

antx · Answer 1 · 2020-10-29T07:10:00+0000

Why do we need a load balancer?

High availability
Even distribution
Less stress on the nodes
Healthy system

"Simple load balancer" - The simplest load balancer strategy would be round robin and least connection used.

Since @hjc explained on round-robin, I have taken the least connection

How does it work?

The least connection strategy, checks which server is free based on the number of active connections the server is serving.
The server will be notified about this information through a health check/notifying mechanism like regular ping or pull model to see the active connection

Data Structure Used:

Round robin kind a uses linked-list
The least connection algorithm can use a combination of.
- Hashmap which will store the server id, number of connection
- The heap sort data structure can be used to identify the root node
  - The max heap will store the server with the least connection
  - The min heap will store the server with a max open connection
  - This is anyways in sorted order, so we could identify the server that can handle the request

In reality, there is a combination of strategy, ideally by load balancer (to distribute traffic across network) and CDN to distribute content based on geography for faster response time solves the availability problem

hjc · Answer 2 · 2020-09-03T05:36:37+0000

An interesting technical question. I'd answer something like this.

Assuming the load balancer will sit between user's browser and Google's front end servers.

Load balancer has 2 major purposes:

Make sure traffic/requests are distributed among next stage servers to avoid uneven resource utilization.
Dynamically respond to changes in server availability.

With this in mind, Load balancer can implement different load balancing strategy. For example:

Round Robin
Least Traffic first
Least Utilization first

For Round Robin, the load balancer will maintain following data:

List of Available Servers
Index for the next server

Every time the load balancer receives a new request, it will allocate it to a server pointed to by the index, and move the index to point to the next server in the list.

If a server becomes unavailable, it will be removed from the list of available servers

For Least traffic first, the load balancer will maintain below data structure:

List of Available Servers, and the corresponding network bandwith usage %
The bandwidth usage are reported from the servers to load balancer through regular handshake.

Every time the load balancer receives a new request, it will allocate it to the server from the list, which has the lowest bandwidth usage %.

Data structure for the Least Utilization First is similar to the Least Traffic First, while the % of network bandwidth utilization will be replaced by the % of Memory/CPU Usage.