Design Case Studies · Lesson 09

Design: Maps API

A Maps API serves billions of requests per day yet most of those requests are for the same tiles. The secret isn't raw compute power — it's recognising which parts of the problem are read-only and cache-perfect, and which parts require real computation every time.

1 · Requirements

An interviewer says: "Design the Maps API that powers a ride-sharing app, a local business directory, and an embedded map widget." Before reaching for endpoints, translate that into concrete, measurable requirements.

Two requirements that look similar but are architecturally very different: tile serving and geocoding. Tiles are static images that never change once rendered — you cache them once and serve them forever. Geocoding requires a live query against a structured address database and has much lower cache hit rates. Routing requires running a shortest-path algorithm on a graph that changes hourly with traffic data. These three workloads get different infrastructure.

2 · Design decisions

2a. Spatial indexing with geohash

Imagine folding a world map in half east-west, then north-south, then east-west again — each fold divides the world into smaller and smaller cells. Geohash does exactly this, encoding the resulting cell as a base-32 string. The string "9q8yy" means: starting from the full world, follow the fifth fold (east), the seventeenth fold (north), the eighth fold (east)... and so on for five characters, landing on a roughly 4.9 km × 4.9 km cell near Mountain View, California.

The critical property: cells that share a long common prefix are geographically close. "9q8ya" and "9q8yb" are neighbours. This makes geohash useful for two things simultaneously:

• Proximity queries: to find all restaurants near a point, compute the point's geohash, then query for records whose geohash starts with the same 5–6 character prefix, plus the eight adjacent cells (neighbours). No trigonometry required — just string prefix matching.
• Sharding: assign each geohash prefix to a database shard. Shard "9q8" handles all of the Bay Area. Queries are routed to a single shard with no cross-shard joins for regional lookups.

One edge case matters: a query point near the edge of a cell may be closer to records in a neighbouring cell than to records in the same cell. The fix is always to query the 8 surrounding cells in addition to the cell containing the point. This is cheap — nine prefix scans on an indexed column.

2b. Quadtree tiles and the zoom/x/y coordinate system

The tiling system works like a quadtree: at zoom level 0, the entire world is one 256×256 pixel tile. At zoom level 1, that one tile splits into four (2×2 grid). At zoom level 14, there are 2¹⁴ × 2¹⁴ = 268 million tiles. Each tile is uniquely identified by {z}/{x}/{y} — zoom, column, row.

The essential property is that a given tile's content never changes once rendered. Tile 14/2621/6339 always shows the same streets, the same parks, the same coastline. This makes tiles perfectly immutable and therefore perfectly cacheable. See Caching (rel-07) for why immutability is the property that allows indefinite TTLs.

2c. CDN-first tile serving

Because tiles are immutable, the tile origin server's only job is to generate and store them. The CDN handles 99.9%+ of traffic. A client requesting tile 14/2621/6339.png asks the nearest CDN edge node. On a hit, the response returns in under 10 ms from the edge — no origin involved. On a miss, the edge fetches from origin, caches with a one-year TTL, and returns. Origin load is tiny: only cold tiles (new zoom areas, newly rendered updates) ever reach it.

The critical design constraint: never put query parameters in tile URLs. A URL like /tiles/14/2621/6339.png?style=night&lang=en creates a different cache key for every style+language combination, multiplying cache misses by orders of magnitude. Instead, bake style into the path: /tiles/night/14/2621/6339.png. The path is deterministic and every CDN edge worldwide uses the same cache key.

2d. Separate infrastructure per workload

Routing and geocoding share nothing with tile serving. They run on separate clusters behind the same API gateway:

2e. Per-API-key rate limiting

Every API call except tile serving must carry an API key. The key maps to a quota — for example, 10,000 requests/day on the free tier. A token-bucket counter in Redis tracks usage per key, resetting at midnight UTC. When the bucket empties, the gateway returns 429 Too Many Requests with a Retry-After header showing the seconds until quota reset. See Rate Limiting (rel-03) for the full token-bucket implementation pattern.

Tile requests are different: tiles are served from CDN without authentication (public URLs). Billing for tile usage happens by counting API-key-authenticated "session" or "map load" initialisations, not per individual tile.

3 · The API model

Geocoding — address to coordinates

# Forward geocode: address string → lat/lng
GET /v1/geocode?q=1600+Amphitheatre+Parkway%2C+Mountain+View%2C+CA&key=YOUR_API_KEY

# Response 200
{
  "status": "OK",
  "results": [
    {
      "place_id": "ChIJ2eUgeAK6j4ARbn5u_wAGqWA",
      "formatted_address": "1600 Amphitheatre Pkwy, Mountain View, CA 94043, USA",
      "geometry": {
        "location": { "lat": 37.4224, "lng": -122.0840 },
        "location_type": "ROOFTOP",
        "viewport": {
          "northeast": { "lat": 37.4237, "lng": -122.0827 },
          "southwest": { "lat": 37.4211, "lng": -122.0853 }
        }
      },
      "types": ["street_address"]
    }
  ]
}

Reverse geocoding — coordinates to address

# Reverse geocode: lat/lng → nearest address
GET /v1/geocode/reverse?lat=37.4224&lng=-122.0840&key=YOUR_API_KEY

# Response 200
{
  "status": "OK",
  "results": [
    {
      "place_id": "ChIJ2eUgeAK6j4ARbn5u_wAGqWA",
      "formatted_address": "1600 Amphitheatre Pkwy, Mountain View, CA 94043, USA",
      "geometry": {
        "location": { "lat": 37.4224, "lng": -122.0840 }
      },
      "address_components": [
        { "long_name": "1600",            "types": ["street_number"] },
        { "long_name": "Amphitheatre Pkwy", "types": ["route"] },
        { "long_name": "Mountain View",     "types": ["locality"] },
        { "long_name": "CA",               "types": ["administrative_area_level_1"] }
      ]
    }
  ]
}

Directions — routing between two points

# Driving directions: Mountain View → San Francisco
GET /v1/directions?from=37.4224,-122.0840&to=37.7749,-122.4194&mode=driving&key=YOUR_API_KEY

# Response 200
{
  "status": "OK",
  "routes": [
    {
      "summary": "US-101 N",
      "duration_seconds": 2460,
      "distance_meters": 55200,
      "polyline": "encoded_polyline_string_here",
      "legs": [
        {
          "steps": [
            {
              "instruction": "Head north on Amphitheatre Pkwy toward Charleston Rd",
              "distance_meters": 340,
              "duration_seconds": 42,
              "start_location": { "lat": 37.4224, "lng": -122.0840 },
              "maneuver": "straight"
            },
            {
              "instruction": "Merge onto US-101 N",
              "distance_meters": 47800,
              "duration_seconds": 2100,
              "maneuver": "merge"
            }
          ]
        }
      ]
    }
  ]
}

Nearby search — places within a radius

# Find restaurants within 500 m of a point
GET /v1/places/nearby?lat=37.4224&lng=-122.0840&radius=500&type=restaurant&key=YOUR_API_KEY

# Response 200
{
  "status": "OK",
  "next_page_token": "CqQCmgEAAA...",
  "results": [
    {
      "place_id": "ChIJN1t_tDeuEmsRUsoyG83frY4",
      "name": "The Creamery",
      "vicinity": "1600 Shoreline Blvd, Mountain View",
      "geometry": {
        "location": { "lat": 37.4219, "lng": -122.0831 }
      },
      "rating": 4.3,
      "distance_meters": 118,
      "opening_hours": { "open_now": true },
      "types": ["restaurant", "food", "establishment"]
    }
  ]
}

Tile serving — rasterised map tiles

# Tile request — no API key; served from CDN edge
# z=14, x=2621, y=6339 → downtown Mountain View at street level
GET /v1/tiles/14/2621/6339.png

# Response 200 — binary PNG from CDN edge (<10 ms on cache hit)
# Headers:
Cache-Control: public, max-age=31536000, immutable
Content-Type: image/png
X-Cache: HIT
X-CDN-Pop: sjc-edge-07

# On a CDN miss, origin generates and stores the tile, then returns it.
# The origin adds the same Cache-Control header so the edge caches it
# for every subsequent request.

4 · Evaluation & latency budget

Tile cache hit ratio

Think of tile popularity as a long tail: zoom levels 10–16 covering major cities account for roughly 80% of all tile requests, and those tiles are requested millions of times each. CDN cache hit ratios above 99.9% are achievable because the same 256×256 pixel square is served identically to every client in every country. Zoom levels 18–20 (building detail, very narrow streets) are requested far less often and may have lower hit ratios, but they're a small fraction of traffic.

Geocoding cache hit ratio

Geocoding is not as cache-friendly as tiles, but it is still substantially cacheable. The address "1600 Amphitheatre Parkway, Mountain View, CA" is queried millions of times by users searching for Google's campus. Common addresses, business names, and landmarks benefit from a Redis LRU cache with a 24-hour TTL. Expect 60–75% cache hit ratios for a geocoder serving a major metropolitan area.

Routing latency breakdown

Routing is the most computationally expensive workload. A naive on-demand Dijkstra or A* search on a full country road graph can take 500 ms – 2 seconds. Production routing engines use two optimisations:

• Contraction hierarchies (CH): pre-process the road graph to create "shortcut edges" that skip unimportant intermediate nodes. A CH-accelerated A* delivers country-scale routing in 5–50 ms on modern hardware.
• Popular O-D pair caching: cache the full route result in Redis for origin-destination pairs that appear frequently (e.g., airport → city centre). Cache key: geohash(origin, 4chars):geohash(dest, 4chars):mode. TTL: 5–15 minutes (traffic data changes).

Back-of-envelope: tile origin load

Google Maps reportedly handles approximately 25 million tile requests per minute at peak. With a 99.9% CDN cache hit ratio:

• CDN edges absorb: 25,000,000 × 0.999 = 24,975,000 req/min
• Origin receives: 25,000,000 × 0.001 = 25,000 req/min (~417 RPS)

417 RPS on origin is trivially served by a small cluster of tile servers — far simpler than the reverse-proxy and caching layer that precedes it. This is the core insight: the hard part of Maps at scale is not computation, it is cache design.

Under the hood: the core mechanism

Geospatial indexing is the mechanism that makes nearby-search fast. Three approaches are in widespread use — geohash, quadtree, and Google S2 cells — and they all solve the same problem: turning a two-dimensional lat/lng into a one-dimensional key so that a standard database index can answer "what is near X?" with a prefix or range scan rather than computing distances to every row.

How geohash encodes a coordinate

Geohash encodes latitude and longitude by interleaving their binary representations and then base-32-encoding the result. The algorithm, step by step for the point (37.4224, −122.0840):

Step 1 — Encode latitude into 15 bits by repeated bisection of [-90, 90]
Range      [  -90,   90]  midpoint= 0    →  37.4224 ≥ 0   → bit 1
Range      [    0,   90]  midpoint=45    →  37.4224 < 45  → bit 0
Range      [    0,   45]  midpoint=22.5  →  37.4224 ≥ 22.5→ bit 1
Range      [ 22.5,   45]  midpoint=33.75 →  37.4224 ≥ 33.75→ bit 1
Range      [33.75,  45]   midpoint=39.375→  37.4224 < 39.375→ bit 0
...                        (continue for 15 total bits)
lat bits = 1 0 1 1 0 ...

Step 2 — Encode longitude into 15 bits by repeated bisection of [-180, 180]
Range      [ -180,  180]  midpoint= 0    → -122.084 < 0   → bit 0
Range      [ -180,    0]  midpoint=-90   → -122.084 < -90 → bit 0
Range      [ -180,  -90]  midpoint=-135  → -122.084 ≥ -135→ bit 1
...
lng bits = 0 0 1 ...

Step 3 — Interleave: lng bit, lat bit, lng bit, lat bit, ...
Interleaved: 0 1 0 0 0 1 1 1 0 ...  (30 bits total for 5-char geohash)

Step 4 — Group into 5-bit chunks and map each to base-32 alphabet
base-32 alphabet: 0123456789bcdefghjkmnpqrstuvwxyz
chunk 0 = 01001 = 9
chunk 1 = 00111 = q
chunk 2 = 10000 = 8
chunk 3 = 11010 = y
chunk 4 = 10100 = y
Geohash = "9q8yy"  ← the ~4.9 km × 4.9 km cell containing Mountain View, CA

The precision table maps string length to approximate cell size:

Why shared prefix = geographic proximity

Because each character of the geohash encodes one more bisection, two strings that share a length-5 prefix fall within the same 4.9 km × 4.9 km parent cell. Two strings that share only a length-3 prefix ("9q8") fall within the same ~156 km × 156 km grandparent cell. The prefix is a spatial containment relationship encoded as a string, which is exactly what a B-tree index can scan efficiently.

The boundary problem and the 9-cell fix

A query point near the edge of its geohash cell may be closer to records in adjacent cells than to records in its own cell. If you query only the centre cell, you silently miss nearby records that happen to fall in a neighbouring cell. The standard fix is to always query the centre cell plus all 8 surrounding cells (Moore neighbourhood). This over-selects: some returned records will be outside the actual radius. A Haversine post-filter culls those:

-- The Haversine formula gives true great-circle distance between two lat/lng points
-- Used as a post-filter AFTER the geohash index scan retrieves the candidate set
haversine(lat1, lng1, lat2, lng2) =
  2 × R × arcsin(
    sqrt(
      sin²((lat2−lat1)/2) + cos(lat1) × cos(lat2) × sin²((lng2−lng1)/2)
    )
  )
  where R = 6,371,000 m (Earth's mean radius)

Worked nearby-search trace

Finding all coffee shops within 800 m of (37.4224, −122.0840):

Operating & debugging it

The maps system has three independent serving paths — tiles, geocoding, routing — that fail in distinct ways. Here are the signals and fixes for each.

Key metrics to monitor

Diagnosing a slow nearby-search query

# Step 1 — Client API call
GET /v1/places/nearby?lat=37.4224&lng=-122.0840&radius=2000&type=gas_station&key=YOUR_API_KEY

# Step 2 — Geohash precision for 2 km radius
# Geohash precision table (approximate cell dimensions):
#   5 chars → ~4.9 km × 4.9 km  ← too coarse for 2 km radius
#   6 chars → ~1.2 km × 0.6 km  ← good fit; 2 km search uses 5-char prefix
# Use 5-char geohash of query point → expand to 9 cells (centre + 8 neighbours)
# This ensures the 2 km radius is fully covered even at cell edges

query_hash = geohash.encode(37.4224, -122.0840, precision=5)  # "9q8yy"
neighbours = geohash.neighbours(query_hash)               # 8 surrounding cells
cells = [query_hash] + neighbours                        # 9 cells total

# Step 3 — What happens at a cell boundary
# A gas station at lat/lng just inside a neighbouring cell IS included
# because we always query all 9 cells. The post-filter by Haversine distance
# removes any records that fall in a neighbouring cell but are actually
# more than 2000 m away (i.e. the corner of the cell is within 2 km
# but not all of it is). Geohash gives the candidate set; Haversine filters it.

# Step 4 — Database query
# places table has columns: place_id, name, type, lat, lng, geohash5 (indexed)
SELECT place_id, name, lat, lng,
       haversine(lat, lng, 37.4224, -122.0840) AS distance_meters
FROM   places
WHERE  geohash5 IN ('9q8yy', '9q8yz', '9q8yw', ...-- 9 cells)
  AND  type = 'gas_station'
HAVING distance_meters <= 2000
ORDER BY distance_meters ASC
LIMIT 20;

# Step 5 — Response shape
{
  "status": "OK",           # or "ZERO_RESULTS" if no gas stations found
  "results": [
    {
      "place_id":         "ChIJabc...",
      "name":            "Shell - Amphitheatre Pkwy",
      "geometry": { "location": { "lat": 37.4218, "lng": -122.0835 } },
      "distance_meters":  87,
      "opening_hours":   { "open_now": true },
      "types":           ["gas_station", "establishment"]
    }
  ]
}

# Zero results case:
{ "status": "ZERO_RESULTS", "results": [] }
# HTTP status is still 200 — ZERO_RESULTS is a valid, successful response.

Sources & further reading

• Google Maps Platform — Official API documentation
• Wikipedia — Geohash: encoding, precision table, neighbour algorithms
• Uber H3 — Hierarchical hexagonal spatial indexing (alternative to geohash)
• OpenStreetMap — Slippy Map tile names: z/x/y coordinate system explained
• Mapbox Tilesets — Vector tile specification and serving guide