Users send a request to a hostname. Something has to decide which of Google's many datacenters, and which machine inside it, handles the request. This chapter covers the first half of that journey, from the user to a datacenter, which is the domain of DNS and of the network-level load balancer. Chapter 20 continues inside the datacenter.

The recurring theme is that there is no one best place to load-balance: each layer has information the others lack, so Google balances at several layers and accepts that each will be imperfect.

In one minute

• The question is "how do we direct user traffic" and the honest answer is "it depends": a search request wants the nearest datacenter for latency, a video upload wants a link with spare bandwidth even if it is further.
• Power isn't the answer: you cannot solve it with one big machine, because a single machine is a single point of failure and the load exceeds any one box.
• DNS load balancing is the first layer: the authoritative server returns different A records to different clients. Limits: the recursive resolver, not the user, is what the DNS server sees, so geolocation is approximate; the response is cached for its TTL so changes propagate slowly; and clients may ignore TTLs or pick a random record.
• Mitigations: use EDNS0 client subnet when available, keep TTLs low enough to rebalance, and accept that DNS is a coarse tool whose job is to pick a nearby, healthy region.
• The virtual IP (VIP) layer: a datacenter's address is a VIP owned by a network load balancer, which spreads incoming packets across many backend machines.
• The network load balancer needs every packet of a connection to go to the same backend. Consistent hashing on the connection tuple does this with minimal disruption when backends change.
• Returning packets: Direct Server Return has the backend reply to the client directly; Google uses packet encapsulation (GRE) so backends can live in any subnet, at the cost of a smaller effective MTU.
• The result: DNS picks a region, the VIP spreads load within it, and the next chapter's RPC-level balancing picks a task.

Power isn't the answer

A naive approach is one giant machine with a lot of bandwidth. It fails because the load exceeds any machine, because it concentrates risk, and because it still does not solve where in the world the request should go. The problem has to be handled by many devices at several levels, each making a local decision.

Defining "optimal" is itself hard. It depends on the problem (minimise latency for interactive, maximise throughput for bulk), on the current state (which datacenters are healthy, which are full), and on the kind of traffic. The chapter takes two examples: Search optimises for latency so it should go to the nearest datacenter with spare capacity; YouTube uploads optimise for throughput and can tolerate distance.

Load balancing using DNS

Before a client can connect it resolves a name, so DNS is the first opportunity to steer it. The simplest version returns multiple records and lets the client pick, which balances roughly but gives no control. A smarter authoritative server returns records based on where the query came from and on the health of each site.

Three problems. The server sees the recursive resolver, not the end user, and resolvers can be far from their users or shared across a whole ISP. Caching means the answer is reused for the TTL, so a site that becomes unhealthy keeps receiving traffic until caches expire; Google compensates by keeping TTLs short and by sizing each site to absorb the extra. Finally, clients and intermediate resolvers do not always respect TTLs or record order. Google's authoritative servers use information about resolver locations and the EDNS0 client subnet extension to improve the guess, and treat DNS as the layer that picks a reasonable region, not the layer that balances precisely.

Load balancing at the virtual IP address

A VIP is an address that is not bound to one network interface but is announced by a network load balancer. Clients connect to the VIP; the balancer forwards each packet to one of many backend machines. The main requirement is that all packets of a connection go to the same backend, because TCP state lives there.

The simple approach, a table of connections to backends, needs state per connection and must be replicated if the balancer itself is to be highly available. The better approach is consistent hashing: hash the connection tuple to pick a backend in a way that, when a backend is added or removed, only the connections mapped to that backend move. Combined with a small connection table for the transition period, this keeps the balancer mostly stateless.

For the return path, the backend can reply directly to the client with the VIP as the source address (Direct Server Return), which avoids sending responses through the balancer. The trouble is that the backend then has to be on the same network segment. Google instead encapsulates forwarded packets in GRE, so the backend can be anywhere and sees the original packet; the cost is encapsulation overhead and a reduced MTU, which Google handles with jumbo frames inside the datacenter.

Putting the layers together

By the time a packet is inside a datacenter, DNS has chosen the region based on proximity and health, and the network load balancer has chosen a machine using consistent hashing. Neither knows anything about the application or about the load on individual tasks. That is the job of the RPC-level balancing described next.