Segment Engineering Blog

Ideas you will meet

Distributed Systems

Consensus, time, failure and the fundamentals of scale-out.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• Real-World Systems · 12 minDesign a maps and navigation serviceMap tiles, road graphs, route finding and live traffic: how an app draws the world and tells you the fastest way.Read hereClose

  The problem

  A maps service must:

  • Draw the map smoothly as you pan and zoom.
  • Find places (search, addresses).
  • Route: the best way from A to B by car, foot or transit.
  • Estimate arrival times using live traffic, and re-route when conditions change.

  Part 1: showing the map

  The world is too big to send at once. The standard answer is tiles.

  • The map is cut into a grid of small squares at each zoom level. Zoom 0 is one tile for the world; each level doubles the tiles along each side (4x the tiles).
  • A tile is addressed by zoom, x and y. The client works out which tiles cover the screen and requests just those.
  • Tiles are static files, so they are cached in the browser and on a CDN.
  • Raster tiles are pre-drawn images. Vector tiles carry the shapes and labels as data, and the client draws them. Vector tiles are smaller, scale smoothly, and allow styling and rotation.

  100%

  Figure SDA-RWS-03-1 · Map tiles, routing and traffic · © forcsguy.com

  100%

  Figure SDA-RWS-03-2 · Tiles multiply with every zoom level · © forcsguy.com

  Part 2: routing

  Roads become a graph: intersections are nodes, road segments are edges with a cost (distance, or better, travel time).

  • Dijkstra finds the cheapest path but explores too much of a continent-sized graph. A* adds a heuristic (straight-line distance) to head towards the goal.
  • Real systems precompute: they build a hierarchy where highways are shortcuts (such as contraction hierarchies), so a long route only searches a small part of the graph.
  • The graph is split into regions or tiles that are loaded as needed, and routing steps across boundaries.
  • Costs depend on mode (car, bike, walking), turn restrictions, tolls and one-way streets.

  100%

  Figure SDA-RWS-03-3 · A road network as a graph · © forcsguy.com

  Part 3: traffic and arrival times

  • Phones send anonymous location updates every few seconds. These flow through a stream and are matched to road segments (map matching).
  • An aggregator computes the current speed per segment, combined with historical speeds for the time of day and day of the week.
  • Route cost uses these speeds, so the fastest route changes through the day. ETA is the sum of segment times.
  • During navigation, the client reports progress; if a faster route appears or traffic changes, the server suggests re-routing.

  Search and places

  Place search is separate: an index of names and addresses (geocoding turns an address into coordinates; reverse geocoding does the opposite), plus a geospatial index for "near me" (next lesson).

  Scale and reliability

  • Map data changes slowly: rebuild tiles in batches, publish a new version, and invalidate CDN caches.
  • Tile traffic is huge and cacheable: serve it from the edge.
  • Routing and traffic are the CPU-heavy, latency-sensitive parts: keep the graph in memory, replicate by region.
  • Location data is sensitive: anonymise it, limit retention, and let users opt out.

  Real-world reading

  Related reading

  • Cloudflare Learning Center: What is a CDN?CloudflareDocumentation
  • YouTube ArchitectureHigh ScalabilityCase Studies
  • TAO: The power of the graphMeta Engineering · MetaCase Studies
  • Solving Remote Build Cache Misses (2 parts) at SoundCloudSoundCloud engineers · SoundCloudCase Studies

  Show 6 moreShow fewer

  • Memsniff: Robust Memcache Traffic Analyzer at BoxBox engineers · BoxCase Studies
  • AWS Networking BlogAmazon Web Services engineers · Amazon Web ServicesBlogs
  • CDN Services at SpotifySpotify engineers · SpotifyCase Studies
  • Estimating the Cache Efficiency using Big Data at AllegroAllegro engineers · AllegroCase Studies
  • Segment Engineering BlogSegment engineers · SegmentBlogs
  • Jane Street BlogJanestreet engineers · JanestreetBlogs

  Open this lesson with its quiz and exercise