Product Manager Portfolio
Back to questions

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

  • Related to Technical
  • For Internal Tools PM
  Google
  Amazon
Add Your Answer
Answers (2)

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

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:

  1. Make sure traffic/requests are distributed among next stage servers to avoid uneven resource utilization.
  2. 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.