Location Intelligence Resources | Blog & Guides

Ideas you will meet

Geospatial

Geohash, quadtree, H3 and location search.

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 · 10 minDesign a nearby-places service (Yelp)Find restaurants within a few kilometres: geohashes, quadtrees and how to query a map efficiently.Read hereClose

  The problem

  Given a location and a radius, return nearby businesses, ranked and filtered (cuisine, open now, rating). It is read-heavy: millions of searches a day but few changes to the places themselves.

  Estimates: 200 million places at around 1 KB each is about 200 GB, which fits in memory across a few machines. Search traffic might be tens of thousands of queries per second at peak.

  Why not a simple range query

  WHERE lat BETWEEN a AND b AND lon BETWEEN c AND d works in a toy system, but an index serves one dimension well: it returns all rows in the latitude band (a strip around the world), then must filter by longitude. We need an index that understands two dimensions together.

  Idea 1: geohash

  A geohash converts a location into a short string by repeatedly halving the map: each extra character narrows the cell.

  • Locations in the same cell share a prefix, so a string-prefix index can find them.
  • A longer hash means a smaller cell (about 150 m on a side at 7 characters, roughly).
  • Border problem: nearby points can fall in neighbouring cells with different prefixes, so query the cell and its 8 neighbours, then filter by exact distance.

  100%

  Figure SDA-RWS-04-1 · Nearby search with geohash cells · © forcsguy.com

  100%

  Figure SDA-RWS-04-2 · Longer codes mean smaller cells · © forcsguy.com

  Idea 2: quadtree

  A quadtree is a tree where each node is a square region. If a region holds more than N places (say 100), it splits into four child squares, repeatedly. Leaves hold the places.

  • Dense areas (city centres) become deep and fine; sparse areas stay coarse.
  • To search, find the leaf containing the user, then widen to neighbouring leaves until you have enough places.
  • Built in memory, it is fast. Rebuild it periodically (for example nightly) or update incrementally as places change.

  Production systems often use S2 or H3: hierarchical cell systems on a sphere with good neighbour handling.

  100%

  Figure SDA-RWS-04-3 · Building a quadtree: split only where it is crowded · © forcsguy.com

  Architecture

  100%

  Figure SDA-RWS-04-4 · Nearby places architecture · © forcsguy.com

  • The search service looks up candidate place ids by cell, fetches details from a cache or database, filters, ranks and returns a page.
  • Writes (a business is added or moves) are rare. They go to the places database; an index builder refreshes the geo index, and it is fine if that is a few minutes behind.

  Rolling out a quadtree service

  A quadtree lives in each server's memory and is built at start-up. With hundreds of millions of places that can take minutes, during which the server cannot answer. Restarting every server at once would take the whole fleet down. Deploy to a small slice at a time so the rest keeps serving, and only move on when the slice is healthy.

  Scale

  • The index is small enough to replicate on every search node, which scales reads simply.
  • If it grew past one machine, shard by region (cell prefix), taking care with queries that cross shard borders.
  • Cache results for popular areas; most users search the same few hotspots.
  • Filters such as "open now" or cuisine can be applied after the geo lookup, or stored as extra index fields.

  Ranking and details

  Distance is only one signal. Combine rating, popularity, relevance to the query, and personalisation. Keep ranking in a separate step so you can improve it without touching the index.

  Real-world reading

  Related reading

  • H3: Uber's Hexagonal Hierarchical Spatial IndexUber Engineering · UberCase Studies
  • Location Intelligence Resources | Blog & GuidesFoursquare engineers · FoursquareBlogs
  • Optimizing CAL Report Hadoop MapReduce Jobs at eBayeBay engineers · eBayCase Studies
  • MongoDB: Shard KeysMongoDB · MongoDB Inc.Documentation

  Show 6 moreShow fewer

  • Grab EngineeringGrab engineers · GrabBlogs
  • PlanetScale BlogPlanetScale engineers · PlanetScaleBlogs
  • Cross Shard Transactions at 10 Million RPS at DropboxDropbox engineers · DropboxCase Studies
  • MapTiler Engineering BlogMapTiler engineers · MapTilerBlogs
  • Presto at GrabGrab engineers · GrabCase Studies
  • Small Improvements Engineering BlogSmall Improvements engineers · Small ImprovementsBlogs

  Open this lesson with its quiz and exercise

• Low-Level Design Practice · 11 minCab bookingRiders, drivers and trips: location-based matching, a trip lifecycle and swappable pricing and matching strategies.Read hereClose

  The problem

  Riders request a trip from A to B. The system finds a nearby available driver, the driver accepts, the trip happens, and the rider pays. Drivers go online and offline and move continuously.

  Entities

  100%

  Figure SDA-LLD-08-1 · Cab booking classes · © forcsguy.com

  The trip lifecycle

  100%

  Figure SDA-LLD-08-2 · Trip states · © forcsguy.com

  Matching

  100%

  Figure SDA-LLD-08-3 · Matching a request · © forcsguy.com

  interface MatchingStrategy { choose(req: Request, candidates: Driver[]): Driver | null }
  const nearest: MatchingStrategy = {
    choose: (req, ds) => ds.sort((a, b) => dist(a.loc, req.pickup) - dist(b.loc, req.pickup))[0] ?? null,
  };
  
  class TripService {
    request(rider: Rider, pickup: Point, dropoff: Point): Trip {
      const trip = new Trip(rider, pickup, dropoff);          // REQUESTED
      for (const d of this.locations.nearby(pickup, 3_000)) { // candidates
        if (d.tryClaim(trip.id)) return trip.offerTo(d);      // atomic: one trip per driver
      }
      return trip.cancel("no drivers");
    }
  }
  

  tryClaim is atomic so a driver cannot be offered two trips at once. The location lookup is a spatial index (geohash or quadtree; see the nearby-places lesson).

  Design notes

  • Pricing is a strategy (base, per km, per minute, surge) and the fare is stored on the trip when booked.
  • Live location updates are frequent and approximate; keep them in a fast store and do not write every point to the main database.
  • Notifications to rider and driver on each state change use the Observer pattern.
  • Edge cases: driver goes offline mid-offer, rider cancels after pickup, payment fails (retry, then flag the account).
  • Extensions: shared rides, scheduled rides, ratings, and driver incentives.

  Real-world reading

  Related reading

  • Akutan: Distributed Knowledge Graph Store at eBayeBay engineers · eBayCase Studies
  • Location Intelligence Resources | Blog & GuidesFoursquare engineers · FoursquareBlogs
  • Rate Limiting with NGINXNGINX · F5 / NGINXBlogs
  • TAO: Distributed Data Store for the Social Graph at FacebookFacebookPapers

  Show 6 moreShow fewer

  • TAO: Facebook’s distributed data store for the social graphUwaterlooPapers
  • Optimizing CAL Report Hadoop MapReduce Jobs at eBayeBay engineers · eBayCase Studies
  • Cloud Bouncer: Distributed Rate Limiting at YahooYahoo engineers · YahooCase Studies
  • Concourse: Generating Personalized Content Notifications in Near-Real-Time at LinkedInLinkedIn engineers · LinkedInCase Studies
  • Linux Foundation BlogLinux Foundation engineers · Linux FoundationBlogs
  • Gojek BlogGojek engineers · GojekBlogs

  Open this lesson with its quiz and exercise