System Design

Google Maps has about a billion daily active users, covers 99% of the world, and takes in something like 25 million updates a day.

We’re going to build a simplified version. Three features:

1. Location updates — the client reporting where you are
2. Navigation — a route from A to B, with an ETA
3. Map rendering — the actual map on your screen

Each one turns out to be a different kind of problem. Rendering is a storage and CDN economics problem. Navigation is a graph algorithms problem, and the graph is far too large to hold in memory. Location updates are a write throughput problem — a million per second at peak.

In the last chapter we found restaurants near you. This one looks almost identical — find friends near you — and it is a completely different problem.

Restaurants do not move. A restaurant’s location is written once and read a billion times, which is why that design could precompute an index, cache it globally, and rebuild it overnight.

People move. Every user is emitting a new location every thirty seconds, and every one of those updates has to reach a few hundred other people right now. The index is obsolete before you finish building it.

You open Yelp and tap restaurants near me.

Under a second later, you have a ranked list. Somewhere behind that tap, a system just searched 200 million businesses, found the handful within 500 metres of you, sorted them by distance, and shipped them back — while doing the same thing for a few thousand other people that second.

The obvious implementation is a WHERE clause on latitude and longitude. It does not work, and why it does not work is one of the more interesting failures in system design: the query is perfectly indexable in each dimension separately, and that turns out to be useless.

Twenty-eight designs down. So — what now?

The usual answer is a list of engineering blogs. Here is one, further down the page. But a list on its own will not make you better, and it is worth being honest about why.

Try this. Think of the last engineering post you read. Can you say what problem the team had, what number it broke at, and what the fix cost them?

You have a 4 GB video file in your Drive folder. You change its title — a few dozen bytes near the start.

How many bytes should cross the network?

The naive answer is 4 GB. The right answer is a few hundred kilobytes, and getting from one to the other is what this chapter is about. Everything else — the API servers, the metadata database, the notification service — is machinery you have already seen. The distinctive problems here are three:

Every previous chapter optimised for latency, throughput or correctness. This one optimises for money, and that changes which answers are right.

Do the estimate before anything else. Five million daily users watching five videos of 300 MB each, served from a CDN at roughly $0.02/GB:

5,000,000 users x 5 videos x 0.3 GB x $0.02 = $150,000 per day

Fifty-five million dollars a year, in bandwidth alone. No database, no compute, no salaries — just moving bytes to viewers. That single number outweighs every other cost in the system, and it means a design that is elegant but bandwidth-hungry is simply a worse design.

Autocomplete looks like a lookup. Type a prefix, return matching strings, sort by popularity. A LIKE 'tr%' query and an ORDER BY.

Two facts destroy that:

It runs on every keystroke. Not once per search — once per character. Typing “dinner” issues six requests. Across 10 million users that is roughly 24,000 queries per second for a feature nobody considers a feature.

The budget is about 100 milliseconds. Facebook’s typeahead team put the threshold there: slower and the suggestions visibly lag your typing, which feels worse than having none at all. That budget covers the network round trip, so the server has perhaps a few tens of milliseconds.

The news feed we built last chapter can be seconds stale and nobody notices. Chat inverts every one of those assumptions.

A message that arrives thirty seconds late is a broken product. A message that arrives twice is a visible bug. A message that arrives out of order makes a conversation nonsensical — the reply shows up before the question. And unlike a feed, where the user pulls, the server must push, to a client that may be behind a firewall, on a train, or asleep.

Every social product has the same question at its centre, and it has exactly two answers:

Do you build a user’s feed when someone posts, or when that user opens the app?

That is it. Everything else — the caches, the queues, the graph database — follows from which side you pick. And the reason this is a great interview question is that both answers are wrong, in ways that only become visible when you do the arithmetic.

Sending a notification is one HTTP call to Apple or Google. That is the entire mechanism, and you can demo it in five minutes.

The system design question is not about that call. It is about what happens when you make it sixteen million times a day, to devices that may have been wiped, through providers that fail in ways you do not control, for users who will uninstall your app if you get it wrong.