← all topics
System design field guide

Design the geo service.

From “who is nearby?” to a service you can explain under interview pressure. Worked designs for ride dispatch, dating, local search, and delivery.

Find
Cover cells, then check geometry
Filter
Freshness and product eligibility
Act
Rank, then reserve where required
Chapter 01

The geo service answers a candidate question

A geo service finds objects near a point or inside an area. It returns candidate IDs and location metadata. Product services decide which candidates are eligible and what action to take.

“Find nearby available drivers, remove stale locations, estimate pickup times for a shortlist, then reserve one driver atomically.”

That sentence describes four separate jobs. A spatial index handles the nearby part. It does not prevent double booking or calculate traffic-aware travel time.

Learn in 15 minutes

Read the problem types, index explanation, cell demo, and read/write paths. Then choose one product example.

Prepare for a deep dive

Continue through sharding, freshness, sizing, failures, and the interviewer questions. Change the calculator assumptions and defend your choices.

These are proposed interview architectures, not claims about the current internal systems of Uber, Tinder, Yelp, or Gopuff. All workload and performance numbers are labeled assumptions.

Chapter 02

First ask what “nearby” means

Product exampleGeo questionWhat changes the design
Uber-like dispatchWhich available drivers can reach this pickup soon?Frequent updates, freshness, road ETA, exclusive assignment.
Tinder-like discoveryWhich eligible profiles are within the chosen distance?Bilateral preferences, blocks, already-seen profiles, location privacy. Updates need not resemble live vehicle tracking.
Yelp-like searchWhich open restaurants match this query nearby?Mostly stable coordinates; text, category, rating, hours, and pagination matter.
Gopuff-like deliveryWhich facility can fulfill this address and basket?Service-area polygons, stock, preparation time, delivery capacity, and reservations. Closest facility may be ineligible.

Clarify radius versus top K, straight-line distance versus travel time, moving versus stationary objects, query/update rates, acceptable staleness, and geographic coverage. Ask whether approximate results are acceptable.

A radius query returns objects inside 3 km. A nearest-neighbor query asks for the closest 20 and may need to expand beyond 3 km. “Deliver in 20 minutes” is a routing and fulfillment constraint.

Chapter 03

The geometry you need to know

TermMeaning in the design
Latitude / longitudeLatitude is north/south, −90 to +90 degrees. Longitude is east/west, −180 to +180. Name fields explicitly so callers cannot swap them.
WGS84 / SRID 4326A common coordinate reference for GPS locations. Degrees are angles, not meters. Longitude degrees cover less ground near the poles.
Point / polygonA driver is a point. A delivery service area is a polygon, possibly with holes and multiple separate pieces.
GeocodingAddress to coordinates. Reverse geocoding maps coordinates to an address or place. Usually a separate provider or service with its own caching and quotas.
DistanceUse a geodesic library for Earth distances. Haversine approximates distance on a sphere. Road travel time needs a road graph and travel costs.
Accuracy / freshnessGPS is an estimate with uncertainty and a timestamp. A precise-looking coordinate may be inaccurate or several seconds old.

For a Vancouver example, latitude is 49.2827 and longitude is −123.1207. GeoJSON point arrays use longitude first. Redis GEOADD also takes longitude first. Keep internal APIs explicit with named fields.

At the antimeridian, +179.9° and −179.9° are close. A naive longitude interval can get this wrong. Use a tested spatial library, including for polar locations and polygon edges.

Redis coordinate ordering and supported latitude range
Chapter 04

Why a spatial index exists

Suppose you store 10 million restaurants. Calculating the distance to every restaurant for every search wastes work. A spatial index first excludes areas that cannot contain a match.

  1. Represent the search circle or polygon as a set of candidate regions.
  2. Read objects from those regions.
  3. Check each candidate against the actual distance or polygon.
  4. Apply product filters, rank, and return a page.

A cell is a geographic bucket with an ID. A server stores many buckets. Cells are not servers, and one cell does not require one database partition or machine. A directory or hash maps cell IDs to storage shards.

An ordinary B-tree on latitude and longitude does not automatically become a two-dimensional nearest-neighbor index. A database spatial index or a deliberate cell-based access pattern is what avoids the broad scan.

Chapter 05

Choose the index and storage separately

ApproachWhat it gives youTradeoff / good use
GeohashEncodes a location into a hierarchical rectangular cell ID. Longer prefixes describe smaller areas.Easy prefix-based indexing. Nearby points can sit across prefix boundaries. Cover every intersecting cell; a single prefix or fixed eight neighbors is not a universal radius search.
H3Hierarchical mostly hexagonal cells, with pentagons. Useful for neighborhood aggregation and spatial grouping.Cell area varies. Grid steps are not kilometers. Parent/child logical hierarchy has approximate geometric containment. Good for heatmaps and candidate grouping.
S2Hierarchical quadrilateral cells on a sphere and region coverings.Useful for global geometry and conservative region covers. Cover precision trades the number of cells against extra candidates.
QuadtreeRecursively divides dense areas into smaller regions.Adapts to density. Moving objects and split/merge coordination add work in a distributed implementation.
R-tree / database spatial indexGroups spatial bounds so queries can prune large portions of the data.Useful for points and shapes. Let a database own index maintenance when possible. PostGIS commonly uses GiST spatial indexes.

Geohash, H3, and S2 are indexing schemes or libraries. They do not supply storage, replicas, failover, authentication, or transactions. You can store their cell IDs in a database or use them in a custom in-memory index.

For an interview, choose one and explain its boundary handling. Listing all five without a read path is weaker than explaining one correctly.

References: H3 hierarchy, S2 cells and coverings, PostGIS indexed radius queries.

Chapter 06

See why the neighboring cells matter

Move the search point near a boundary. A nearby result can live in a different cell. Selecting intersecting cells collects candidates; the circle test removes candidates outside the radius.

Search circle and candidate cellsAn illustrative flat 10 by 6 kilometer region. Adjust controls to see selected cells, candidates, and missed matches.

Green circles = returned matches. Orange X marks = true matches missed. Hollow circles = extra candidates rejected by distance. Gray dots = unqueried points. Shaded cells = queried cells. This is a local square-grid teaching model, not an H3 implementation. Points and search results are limited to this displayed region.

Smaller cells reduce irrelevant candidates but increase cell lookups and movement across boundaries. Larger cells reduce lookups but return more candidates. The choice depends on local density and query radii, not a universal precision setting.

Chapter 07

Correctness at the edge

A correct candidate cover includes every cell that could contain a match. Extra candidates are acceptable because you filter them later. Missing a cell can silently hide a nearby driver.

  • A cell's center outside the query circle does not prove that the whole cell is outside it.
  • A polygon fill based only on cell centers can miss boundary overlaps. Choose an overlap/covering operation or conservatively expand and verify it.
  • An H3 grid disk returns cells by graph distance. Choosing k from an average edge length is not a proof that a radius is covered everywhere.
  • At regional shard borders, route to all intersecting regions. A city name is not a geometric boundary guarantee.

For exact nearest K, continue searching until a distance lower bound for every unvisited region exceeds the current Kth-best distance. “Stop when we have 20 candidates” is an approximate strategy. For product ranking that mixes distance and relevance, be explicit about the bounded candidate pool.

H3 grid traversal · S2 covering examples

Chapter 08

Start with an existing database when it fits

ToolUseful starting pointWhat you still own
PostgreSQL + PostGISPlaces, service-area polygons, exact geometry checks, relational filters.Indexes, query plans, replicas and capacity. Benchmark before replacing it with a custom distributed system.
Redis GEOA fast point-radius index for active nearby objects.Regional keys/shards, freshness metadata, cleanup, durability/rebuild, and cross-key query merging. A single large GEO key is owned by one Redis Cluster hash slot.
Elasticsearch / OpenSearchText search plus category filters and geo filtering for places.Index synchronization, refresh lag, shard sizing, ranking, and source-of-truth records.
Cell index on Cassandra / DynamoDBA geo access pattern built on a scalable key-value or wide-column store.Cell cover, hot buckets, pagination, movement cleanup, and fanout. Hashing entity_id alone does not support nearby reads.

My starting choice for a Yelp-like design is a database/search engine with a geo index. For an Uber-like deep dive, a regionally sharded active-location index is worth discussing because updates and freshness dominate.

Redis GEOSEARCH · Elasticsearch geo queries

Chapter 09

A concrete nearby search in PostGIS

This illustrative query finds up to 20 restaurants within 3,000 meters of Vancouver's example coordinate. It uses a geography column so the radius is in meters. The GiST index reduces candidates; distance orders the eligible rows.

nearby-restaurants.sql · readable offlineCREATE TABLE places ( id bigint PRIMARY KEY, name text NOT NULL, category text NOT NULL, location geography(Point, 4326) NOT NULL ); CREATE INDEX places_location_idx ON places USING gist (location); WITH query_point AS ( SELECT ST_SetSRID(ST_MakePoint(-123.1207, 49.2827), 4326) ::geography AS location ) SELECT p.id, p.name, ST_Distance(p.location, q.location) AS distance_m FROM places p CROSS JOIN query_point q WHERE p.category = 'restaurant' AND ST_DWithin(p.location, q.location, 3000) ORDER BY distance_m, p.id LIMIT 20;

At production scale, inspect the execution plan and test the actual density and filter selectivity. Calculating distance and sorting all radius matches can still be expensive in a dense area. Consider supported nearest-neighbor index operations when that becomes the bottleneck.

ST_DWithin · ST_Distance

Chapter 10

The records behind a custom geo service

RecordExample fieldsPurpose
LatestLocation keyed by entity_idlat, lon, accuracy_m, session_epoch, sequence, received_at, observed_at, cell_idLatest accepted state. Reject old updates using a server-issued session epoch and increasing sequence, rather than trusting device time alone.
CellMembers keyed by region + cell + bucketentity_id, location_version; optionally copied coordinatesFind candidate IDs by area. A busy cell can use several deterministic hash buckets.
Eligibility / availabilitydriver status, vehicle type, user blocks, facility stockProduct-owned state. Some filters can be copied for speed; authoritative checks remain necessary for actions.
Location event streamentity_id, version, location, timestampsOptional ingestion buffer, replay and derived analytics. Retention is separate from latest-location state.

Example membership key: region / cell_id / hash(entity_id) % B. A query enumerates the covered cells and all B buckets for each cell. A directory maps these logical keys to physical shards.

With Redis GEO, a regional GEO key can already hold coordinates and perform distance filtering. You do not need to recreate a cell-members table unless your chosen sharding scheme needs it. A global entity profile remains separate from the active geo index.

Chapter 11

Write path: a driver moves across a cell boundary

  1. The app sends entity ID, latitude, longitude, accuracy, session epoch, sequence, and observation time. Authenticate the entity and validate the location.
  2. Route updates for that entity to one logical owner, or use conditional writes to reject versions older than the latest accepted version.
  3. Update the latest accepted location and publish an ordered membership update. Within the same cell, refresh location/freshness without unnecessary remove/add operations.
  4. On a cell change, add the versioned membership to the new cell, then remove the older membership from the previous cell. Make retries idempotent.
  5. Queries deduplicate IDs and validate freshness/version against current state. Sweep obsolete memberships and replay failed updates.

Add-before-remove reduces membership gaps, but a latest-state write and a cross-shard membership change are not automatically atomic. Search may temporarily miss a moving object or find it in both cells. Define the allowed indexing lag; use a serialized owner plus durable outbox/replay, and a bounded transition/overlap strategy if stronger coverage is required.

Never let an old cleanup task blindly remove a newer membership after a driver returns to the same cell. Delete only the expected old version. A stale event must not resurrect an expired or offline driver.

Suggested interview assumptions: updates every 5 seconds while active; locations older than 15 seconds are excluded. These are product choices to validate, not GPS or Redis defaults.

Redis GEO members have no automatic per-member TTL. Store freshness separately, filter stale results at read time, and remove old members with a sweeper. Expiring the whole GEO key would expire every member together.

Chapter 12

Read path: find drivers near a pickup

  1. Validate the pickup, radius, result limit, and filters. Apply request limits.
  2. Compute a conservative cell cover and locate the owning shards.
  3. Query those shards in parallel within a deadline. Return candidate IDs with version and location metadata.
  4. Deduplicate, reject stale locations, apply vehicle/availability filters, and verify geodesic distance.
  5. Estimate road pickup times for a bounded shortlist. Rank by the product's objective.
  6. Dispatch attempts to reserve a driver using an atomic state transition. If the reservation loses a race, try another candidate.

Geo lookup can tolerate bounded staleness. Driver reservation cannot tolerate assigning the same driver to two active rides. Keep that invariant in an authoritative dispatch state machine with idempotent request IDs and expiring offers.

Limit results after eligibility and freshness checks, or overfetch and continue. Fetching 20 nearby IDs and then discarding 19 blocked/stale/busy candidates can produce a misleading “no results” response.

For paginated discovery, bind the cursor to the origin, filters, radius, and ranking version. Use a deterministic tie-breaker such as entity ID. For moving data, either snapshot a candidate list for the session or accept and document changes across pages.

Chapter 13

Distance is not ETA

A driver 500 meters away across a river may take longer than a driver 2 km away on the same road. Use straight-line distance to reduce the candidate set, then a routing engine to estimate travel time.

A routing engine models intersections and road segments as a graph with costs. One-way roads, turn restrictions, transportation mode, closures, and traffic affect the answer. Algorithms such as A* and preprocessed routing techniques help; an interview usually needs the service boundary more than the algorithm internals.

Use a matrix request to estimate many candidate-to-pickup travel times. Batching saves request overhead, but the number of source/destination pairs still drives work and may drive provider billing. Map matching aligns noisy GPS traces with roads; it is separate from geocoding.

An isochrone is the area reachable within a travel-time budget. It can help model delivery coverage, but inventory and fulfillment capacity still need separate checks. Cache route estimates with a bounded age and appropriate origin/destination precision.

OSRM route, table, and map-matching APIs

Chapter 14

Scale regions, then deal with hot cells

Route requests to a nearby serving region. Inside it, shard the geo index by geographic cells or cell groups. Group related cells when it reduces network fanout, but track actual load so downtown does not overwhelm one node.

ProblemLeverCost
Dense stadium or airportSplit cells into finer resolution, or bucket one cell by entity hash.More fanout. Fine cells help geographic density but may not split a crowd at nearly the same coordinate. Hash buckets do.
Sparse countrysideUse larger regions or expand the search radius in bounded steps.More candidates and higher latency; declare maximum radius and deadline.
Read-heavy place searchCache candidate IDs, add read replicas, coalesce identical requests.Invalidate or age results. Exact origin and filter differences still need checks.
Very high location update rateAdaptive update intervals, coalesce superseded updates, batch transport.Reduced precision/freshness. Dropping intermediate positions is suitable for latest-state search, not automatically for billing, safety, or history.
Shard migrationVersion the routing directory; copy state, catch up updates, cut over, then remove old state.Temporary duplicate reads/writes. Readers must know the migration state and deduplicate.

A city may need many shards. A small region may share a shard with others. Avoid assuming one city equals one server.

For a cross-region journey, hand off the entity with a versioned ownership epoch. Queries near borders may read both sides. Async replicas can serve discovery, while dispatch ownership must prevent conflicting reservations across regions.

Do not cache a user-specific Tinder feed by cell alone. Cache shared candidates, then apply private preferences and blocks for each viewer. Recheck stock and capacity at checkout for delivery.

Chapter 15

Napkin math that follows the workload

Size writes and searches independently. A million online drivers is not a million location updates each second.

AssumptionCalculationResult
1,000,000 active entities, update every 5 s1,000,000 ÷ 5200,000 updates/s
200 bytes per update payload200,000 × 20040 MB/s logical payload ingress
Keep every update for one day40 MB/s × 86,4003.456 TB/day before compression, replication, or envelope overhead
500 bytes of effective latest-state/index memory per entity1,000,000 × 500500 MB per logical copy, excluding headroom and other state
50,000 searches/s × 12 cells50,000 × 12600,000 cell lookups/s
40 candidate entries/cell50,000 × 12 × 4024 million candidate entries examined/s
Route 20 candidates per search50,000 × 201 million route pairs/s if every search does routing

The route-pair count can dominate the design. A map refresh should not necessarily trigger a fresh dispatch-quality ETA for every marker. Rate-limit routing, cache estimates, and reserve detailed routing for the relevant workflow.

For a machine-count estimate, assume a benchmarked shard primary handles 20,000 accepted updates/s under the target read mix and freshness SLO. At 70% utilization, 200,000 ÷ 14,000 rounds to 15 primary shards. Two followers per shard means 45 shard copies, not automatically 45 physical machines.

That is a hypothetical write-capacity floor. Read CPU, network, memory, skew, replicas, and failover may require more capacity. The benchmark must include the intended replication and membership work. Do not multiply by RF again if that overhead is already in the measured primary throughput.

Change the assumptions

Decimal MB/TB. Primary count only checks updates. Cells and candidate counts are averages you supply; larger radii and dense neighborhoods change them. No universal geo-server QPS is assumed.

Chapter 16

Four interview designs

Choose a product to see the proposed components and the failure that matters most.

Chapter 17

Geofences and delivery zones

For “Can this facility serve this address?”, store a versioned service-area polygon. Use its spatial bounds or a cell cover to find candidate facilities, then run a point-in-polygon check. Define whether an address on the edge counts as inside. PostGIS ST_Covers includes the boundary.

Service areas can overlap. Choose among eligible facilities using inventory, preparation time, road ETA, capacity, and business rules. At order placement, recheck eligibility and atomically reserve the required stock. The geo index cannot promise inventory.

For enter/exit notifications, GPS jitter can repeatedly cross a boundary. Add hysteresis or dwell time, remember the entity's prior geofence state, and deduplicate notifications by transition/version. Delayed or out-of-order samples should not produce a fresh false transition.

Large polygons may touch many cells. Store them at suitable cover levels or use a spatial database instead of duplicating a polygon into millions of fine buckets.

PostGIS boundary-inclusive containment

Chapter 18

Failures you should be ready to discuss

FailureResponse
GPS disappears / app disconnectsExclude records past the freshness cutoff. Cleanup reclaims space later; it does not decide whether a stale driver is eligible.
Update arrives out of orderCompare session epoch and sequence. Reject the older version and preserve newer membership.
Ingestion falls behindMeasure observation-to-searchable lag. Coalesce eligible latest-state updates; backpressure producers and reduce nonessential work. A queue buffers a spike but adds freshness delay.
One query shard times outReturn partial results only if the product permits it, with a completeness indicator. Do not call a partial response “the nearest” or “no providers exist.”
Geo shard is lostFail over to a replica or rebuild from snapshot and ordered updates. For ephemeral live positions, fresh heartbeats help recovery; measure the gap.
Routing provider failsUse an explicitly approximate distance-based fallback for browsing. Avoid promising an exact pickup/delivery time.
Two riders select the same driverConditional reservation in dispatch state. One succeeds; the other retries.
Bad coordinates or spoofingCheck valid ranges, accuracy, sequence, and plausible movement. Add risk controls for actions that depend on location. GPS remains a trust boundary.

Track p50/p95/p99 lookup latency, update-to-searchable lag, stale candidate fraction, candidate count per query, shard skew, query fanout, routing latency, and reservation conflicts. Validate spatial recall by comparing sampled queries against a brute-force reference on a small snapshot, including boundary cases.

Chapter 19

Location privacy belongs in the design

Collect the precision and history the product needs. A public nearby endpoint should not expose a person's exact live coordinates. Tinder-like discovery can return coarse distance bands and profile IDs; authorized ride participants may need more precise trip tracking.

Repeated queries from different origins can reveal someone’s location even when each response shows only a distance. Rate limits, coarse output, restricted query origins, and access controls help reduce this exposure. Avoid putting precise locations into ordinary logs and traces.

Separate live location from long-term history. Give each a retention and deletion policy. Scope who can read it, encrypt stored/transmitted data, and propagate deletions to indexes, caches, and derived systems.

Chapter 20

A 45-minute interview path

TimeWhat to cover
0–5 minutesClarify product semantics, active entities, update intervals, radius/top K, freshness, and geographic scope.
5–10 minutesCompute update QPS, search QPS, candidate fanout, and latest state versus history storage.
10–20 minutesDraw API, ingestion, active geo index, profile/eligibility store, and product action service. Explain a read and a write.
20–35 minutesDeep dive on cell coverage, cross-cell updates, hot regions, stale data, and product-specific correctness.
35–45 minutesDiscuss failover, observability, privacy, and tradeoffs. State the limits of approximate search.

A two-minute explanation you can practice

“I’ll separate location discovery from dispatch. Drivers publish versioned locations every five seconds. With one million active drivers, that is 200,000 updates per second. A regional geo index stores active positions and freshness metadata. A pickup query covers all intersecting cells, reads candidates, removes stale or ineligible drivers, and checks distance. We estimate road ETA for a shortlist. Dispatch reserves a driver atomically, so stale search results cannot double book them. We shard hot areas, handle cross-cell moves with versioned updates, and monitor indexing lag. Long-term location history uses separate storage and retention.”

For Yelp, replace frequent driver updates with place-data indexing and emphasize text relevance. For Tinder, emphasize preferences and privacy. For Gopuff, emphasize service areas, stock, and fulfillment time.

Chapter 21

Check your understanding

Why not query only the same geohash?

A nearby point can be across a cell boundary. Cover all intersecting cells, then verify distance.

Does H3 give me a database?

No. It supplies geographic cell IDs and operations. Storage, shard routing, replication, and recovery are separate.

Can we just use Redis GEO?

Yes for suitable point-search workloads. Decide how keys are sharded, how cross-region queries merge, how stale members are filtered, and how data recovers.

Does nearest mean fastest?

No. Road access and traffic change travel time. Use geo distance to generate candidates and routing for the shortlist.

What if the stadium cell is too hot?

Finer cells can spread a geographically distributed crowd. If entities still share one tiny area, hash-bucket the cell and query each bucket.

Why store latest location and history separately?

Latest-state size depends on active entities. History grows with updates per second times retention. Each needs a different freshness and storage policy.

Can I stop once I find K objects?

Only if approximation is acceptable, or unvisited regions have a lower distance bound beyond the current Kth result. Product filters can also require fetching more.

Does Kafka reduce update throughput?

It buffers and transports updates. It reduces downstream work only if you deliberately coalesce or aggregate events whose intermediate states can be dropped.

Where is strong consistency needed?

Reservations and ownership transitions need explicit invariants. Discovery can often tolerate a defined indexing delay.

What should I memorize?

Candidate cover → exact geometry check → eligibility → ranking → authoritative action. Also update QPS = active entities / update interval.

Chapter 22

References and scope

The designs and sizing exercises are teaching examples. Product limits and API behavior below come from primary documentation checked for this guide. Code is illustrative and has not been executed against a database.

The interactive map uses synthetic coordinates and points. It requests no location permission and sends no data. All core text and exercises work offline. Optional SQL syntax highlighting loads from a CDN; the SQL remains readable without it.