Proximity Service System Design Template

System Design: [Proximity service name]

Reference design for a proximity service: "find businesses or places near me", ranked by distance, rating and relevance, for a read-heavy catalogue of [200 million] places. It compares geohash, quadtree, Google S2 and Uber H3 (H3 library 4.x, cell statistics from h3geo.org) as the spatial index, sizes an in-memory index that is replicated rather than sharded, and covers adaptive search radius, ranking, write propagation and the failure behaviour of each component. It follows the structure of the System Design Document template, adds a 45-minute interview path, access-pattern and failure-mode tables and a cited "How real systems do it" box, and is pre-filled with a worked design to adapt. Replace every [bracketed] value and every row marked Example; values marked Example are assumptions, not benchmarks.

Document control

Approvals

Revision history

Contents

1. Overview
2. Requirements
3. Capacity estimation
4. API design
5. Data model
6. High-level design
7. Detailed design
8. Scalability and performance
9. Reliability, security and operations
10. Trade-offs and alternatives
11. Delivery plan and risks
12. Appendices

1. Overview

1.1 Problem statement

[Example: The current "near me" search runs a bounding-box query on the place table in a relational database. At the evening peak the query takes over 900 ms in dense city centres, returns up to 40 000 rows that are then sorted in the application, and the primary database is saturated by search traffic that should never touch it. Rural users often get empty results because the radius is fixed.]

1.2 Proposed solution

[Example: A search service answers nearby queries from an in-memory spatial index that maps H3 cells to place IDs at three resolutions. The index holds about 16 GB for 200 million places, so every search node keeps a full copy and nodes scale out by replication. A query picks a resolution and ring count from the local place density, reads the cells, filters by category and opening hours, computes exact distances and ranks the top results. The place catalogue stays the source of truth; changes flow to the index through a change stream and are visible within one minute.]

1.3 Decisions requested from reviewers

1.4 45-minute interview path

Use this order when the document serves an interview or a short design review. The written sections below are the long form of each step.

Start the default deep dive with the naive answer, a two-dimensional range query on latitude and longitude, and show why it is slow: a B-tree index on latitude alone returns a whole horizontal band of the planet. Then show how geohash turns two dimensions into one sortable key, why neighbouring cells are needed at cell edges, and why hexagonal cells keep all neighbours at one distance.

2. Requirements

2.1 Core functional requirements

2.2 Non-functional requirements

2.3 Below the line (out of scope)

Name these explicitly so reviewers and interviewers do not pull the design toward them.

• [Example: tracking moving objects such as drivers or couriers (see system-design/design-ride-matching)]
• [Example: turn-by-turn routing and travel-time ranking (see system-design/design-maps-navigation)]
• [Example: full-text search over reviews and menus (see system-design/design-full-text-search)]
• [Example: review writing, photo upload and moderation]
• [Item deferred, with the release that will take it]

3. Capacity estimation

3.1 Assumptions

3.2 Request rates

Place changes: $P \times c = 2 \times 10^{8} \times 0.005 = 10^{6}$ per day, about 11.6 per second. The read to write ratio is about 5 787 / 11.6, or 500 to 1, so the design optimises the read path and accepts a slower, asynchronous write path into the index.

3.3 Storage and index size

Catalogue: $2 \times 10^{8} \times 1\,024 \ \text{B} \approx 205 \ \text{GB}$, which fits a sharded relational or document store with ordinary replicas.

Search index per place: a compact record (latitude, longitude, category bits, rating, hours bitmap) of 32 bytes, plus the place ID in three cell lists (resolutions 7, 8 and 9) at 8 bytes each, doubled for hash-map and list overhead:

Consequence: the whole index fits in the memory of one ordinary 64 GB server, so every search node holds a full copy and the service scales by adding replicas. There is no scatter-gather across shards on the hot path.

3.4 Search nodes

Busiest region peak: $g \times Q_{peak} = 0.5 \times 17\,361 \approx 8\,681$ searches/s.

The factor 1.5 keeps headroom for uneven load and garbage-collection pauses.

3.5 Summary

4. API design

4.1 Endpoints

4.2 Request and response example

GET /v1/search/nearby?lat=40.4168&lng=-3.7038&radius_m=2000&category=cafe&open_now=true HTTP/1.1
Accept: application/json

{"query": {"lat": 40.417, "lng": -3.704, "requested_radius_m": 2000, "effective_radius_m": 500, "resolution": 9}, "results": [{"place_id": "pl_7Hq2", "name": "Example Coffee Corner", "distance_m": 140, "rating": 4.6, "open_now": true, "category": "cafe"}, {"place_id": "pl_9Xa1", "name": "Example Bakery and Cafe", "distance_m": 310, "rating": 4.4, "open_now": true, "category": "cafe"}], "next_cursor": "c_2f9a", "index_version": "2026-10-30T09:14:05Z"}

The response echoes the effective radius so the client can show "results within 500 m" when the service narrowed a dense query (7.3). Coordinates in the echo are rounded to three decimals (about 110 m of latitude) so logs and caches do not hold precise user locations (9.2).

4.3 Errors and limits

5. Data model

5.1 Entities

The place record is the source of truth; cell entries and counts are derived from it and can always be rebuilt.

5.2 Storage choices

5.3 Access patterns

6. High-level design

Read path: client, load balancer, any search node, local memory, response. Write path: client, place service, database commit, change event, every search node applies the change. The two paths share no synchronous dependency, so a database incident does not stop search (9.1).

7. Detailed design

The deep dives in this section, each with options, choice and reason:

7.1 Distance

Exact distance uses the haversine formula on a sphere of radius $R_{E} = 6\,371 \ \text{km}$:

Example: from (40.000, -3.000) to (40.010, -3.010) the distance is about 1.40 km. The spherical model is accurate to well under 1% for search ranking; Redis documents up to 0.5% worst-case error for the same model.

7.2 Spatial index options

Geohash cell sizes, computed from bits per character (5 bits per character, alternating longitude and latitude):

H3 cell sizes used here, from the H3 cell statistics table (average hexagon area and edge; H3 states that edge lengths for resolutions 7 and finer are extrapolated):

Choice: H3. Every place is indexed at three resolutions at write time (three cell lists, 3.3), so a query never converts between resolutions. Geohash remains a valid choice when the index must live in a key-value store that only supports prefix or range scans.

7.3 Adaptive radius and ring count

For edge length $e$, the distance between neighbouring cell centres is $d = \sqrt{3}\,e$. A conservative number of rings that covers radius $R$ from any point in the origin cell is:

A fixed 2 km radius at resolution 8 in the dense centre would read 27.3 km² x 1 500, about 41 000 candidates, which breaks the latency budget. So the service reads the place count of the resolution 7 cell around the query point, picks the row whose expected candidates stay under about 3 000, and if fewer than 20 results survive the filters it widens by one ring at a time up to the 25 km cap. The response reports the effective radius (4.2).

7.4 Filtering and ranking

1. Read candidate IDs from the chosen cells.
2. Drop candidates that fail the category bitmask or the hours bitmap for the local time of the place.
3. Compute haversine distance only for survivors; drop those beyond the effective radius (cells overshoot the circle by the ratio in 7.3).
4. Score: Example: $score = 0.5 \cdot (1 - d/R) + 0.3 \cdot rating/5 + 0.2 \cdot relevance$, where relevance comes from the query category match.
5. Keep the top 20 with a bounded heap; the cursor encodes the last score and place ID so the next page is stable.

Ranking 3 000 candidates is a few hundred microseconds of CPU, well inside the latency budget in section 8.

7.5 Index freshness and node start

• Change stream: every committed edit emits an event with the place version. Each search node consumes all partitions and applies an event only if its version is newer than the one it holds, so replays and duplicates are harmless.
• Moves: an edit that changes coordinates removes the place from its old cells and adds it to the new ones at all three resolutions.
• Closures: a closed place is removed from the cell lists; the place record is kept for history.
• Snapshots: a daily job builds the full index from the database, records the stream offset it reflects and writes it to object storage. A new node loads the snapshot (16 GB) and then replays the stream from that offset; it reports ready only when its lag is under 60 s.

7.6 How real systems do it

How real systems do it (paraphrased, not copied). The Redis documentation for GEOADD explains that a Redis geospatial index is an ordinary sorted set: latitude and longitude bits are interleaved into a 52-bit geohash integer that is stored as the member's score, which a double can hold exactly. A radius or box query covers the shape with the centre area and its eight neighbours, turns each into a score range by dropping low-order bits, and discards members outside the shape. Distances use the haversine formula on a spherical Earth, which the documentation says can be off by up to 0.5%. This is the geohash row of 7.2 in production form. The S2 Geometry documentation describes the other family: 31 cell levels numbered along a Hilbert curve so nearby cells get nearby 64-bit IDs, and a region coverer that approximates any shape with a small union of cells (8 by default). The H3 documentation publishes the cell statistics used in 7.2 and 7.3. Read the originals in 12.3; this box keeps only the general idea.

8. Scalability and performance

Latency budget for nearby search (target p99 150 ms server side):

At the busiest region peak, 8 681 searches/s x up to 37 cells is about 321 000 in-memory cell reads per second spread over 5 nodes, which is trivial for local hash maps.

9. Reliability, security and operations

9.1 Failure modes

9.2 Security and privacy

9.3 Observability

9.4 Cost estimate

10. Trade-offs and alternatives

11. Delivery plan and risks

11.1 Milestones

11.2 Rollout and rollback

[Example: Traffic shifts by percentage with a feature flag per region. Rollback routes traffic back to the database query path, which stays available until M4 plus 30 days.]

11.3 Risks

12. Appendices

12.1 Open questions

12.2 Glossary

12.3 References

Standard and licence note

Based on common industry practice for geospatial search and on the public documentation of H3 (Apache 2.0 licensed library, documentation version 4.x), S2 Geometry and Redis cited in 12.3. Cell statistics are quoted as published on h3geo.org in October 2026, where edge lengths for resolutions 7 and finer are extrapolated; check the current tables before relying on them. The documentation pages are paraphrased in 7.6 only; no text, figures or code were copied, and all capacity numbers here are illustrative examples. Original text written for this collection. Template licence: MIT.