# 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.

<!--
Guidance: How to use this template
- Decide first what moves: in this design the places are static and the
  searcher moves. If the indexed objects move every few seconds (drivers,
  couriers), use the Ride-Hailing Dispatch design instead; the write path is the
  hard part there, not the read path.
- Size the index (section 3) before choosing a store: if the whole index
  fits in one machine's memory, replicate it and do not shard it.
- Measure place density in your densest and emptiest areas; a fixed radius
  that works in a suburb returns tens of thousands of candidates downtown
  and nothing in the countryside (section 7.3).
- Keep the index comparison in 7.2 even if you already chose H3; reviewers
  and interviewers will ask about geohash and quadtrees.
-->

## Document control

<!-- Guidance: A design is a proposal until it is approved; record who decided and when. -->

| Field | Value |
|---|---|
| Document ID | [SDD-PROX-001] |
| System / feature | [Nearby places search] |
| Version | [0.1] |
| Status | [Draft / In review / Approved / Implemented / Superseded] |
| Owner | [@owner] |
| Author(s) | [@author] |
| Reviewers | [@reviewer-1], [@reviewer-2] |
| Last updated | YYYY-MM-DD |
| Classification | [Internal] |
| Difficulty | Intermediate |
| Spatial index and version | [H3 4.x, resolutions 7, 8 and 9] |
| Related | [Place catalogue service], [Search ranking design], [ADR: spatial index choice] |

### Approvals

| Role | Name | Decision | Date |
|---|---|---|---|
| Tech lead | [@name] | [Approved / Changes requested] | YYYY-MM-DD |
| Staff / principal engineer | [@name] | [Decision] | YYYY-MM-DD |
| SRE / operations | [@name] | [Decision] | YYYY-MM-DD |
| Privacy | [@name] | [Decision] | YYYY-MM-DD |
| Product (search experience) | [@name] | [Decision] | YYYY-MM-DD |

## Revision history

<!-- Guidance: Note what changed in the design, not the wording. -->

| Version | Date | Author | Change summary |
|---|---|---|---|
| 0.1 | YYYY-MM-DD | [@name] | First draft for design review |
| 0.2 | YYYY-MM-DD | [@name] | *Example:* Replaced fixed 2 km radius with density-based adaptive radius |
| 0.3 | YYYY-MM-DD | [@name] | *Example:* Moved index from a geo-enabled database to in-memory replicas |
| 1.0 | YYYY-MM-DD | [@name] | *Example:* Approved |

## Contents

<!-- Guidance: Keep aligned with the headings. -->

1. [Overview](#1-overview)
2. [Requirements](#2-requirements)
3. [Capacity estimation](#3-capacity-estimation)
4. [API design](#4-api-design)
5. [Data model](#5-data-model)
6. [High-level design](#6-high-level-design)
7. [Detailed design](#7-detailed-design)
8. [Scalability and performance](#8-scalability-and-performance)
9. [Reliability, security and operations](#9-reliability-security-and-operations)
10. [Trade-offs and alternatives](#10-trade-offs-and-alternatives)
11. [Delivery plan and risks](#11-delivery-plan-and-risks)
12. [Appendices](#12-appendices)

## 1. Overview

<!-- Guidance: One page that a busy reviewer can read alone: problem, proposed solution in a paragraph, and the decisions that need their attention. -->

### 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

| ID | Question | Recommended option | Section |
|---|---|---|---|
| Q-01 | *Example:* Which spatial index? | H3 cells at resolutions 7, 8 and 9 | 7.2, 10 |
| Q-02 | *Example:* Shard or replicate the index? | Replicate the full index to every search node | 3.3, 7.5 |
| Q-03 | *Example:* Fixed or adaptive radius? | Adaptive by density, capped at about 3 000 candidates | 7.3 |
| Q-04 | *Example:* How fresh must the index be? | Changes visible within 60 s; closures within 5 min | 7.5 |
| [Q-nn] | [Question] | [Option] | [Section] |

### 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.

| Minutes | Cover | Output on the whiteboard |
|---|---|---|
| 0 to 5 | Scope: search nearby places, view a place, owners edit places; below-the-line items (2.3) | Three functional requirements, read-heavy note |
| 5 to 10 | Estimates: peak searches per second, read to write ratio, index size (section 3) | "Index fits in memory, so replicate" consequence |
| 10 to 15 | Interface: `GET /v1/search/nearby` and the place endpoints (section 4) | One request, one response |
| 15 to 25 | High-level design: search service with in-memory index, place service with database, change stream (section 6) | One diagram |
| 25 to 40 | One deep dive: the spatial index (default, 7.2), or adaptive radius (7.3), or keeping the index fresh (7.5) | Options, choice, reason |
| 40 to 45 | Failures (stale index, hot area), the 10x row in section 10 | Two failure rows |

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

<!-- Guidance: Split core requirements from below-the-line items so the design stays focused. Non-functional targets need numbers and a way to measure them. -->

### 2.1 Core functional requirements

| ID | Requirement | Priority |
|---|---|---|
| FR-01 | *Example:* Return places within a radius of a point, default 2 km, maximum 25 km | Must |
| FR-02 | *Example:* Filter by category and "open now"; return 20 results per page | Must |
| FR-03 | *Example:* Rank by a blend of distance, rating and relevance | Must |
| FR-04 | *Example:* Show place details (name, address, hours, photos, rating) | Must |
| FR-05 | *Example:* Owners add, edit and close places; changes appear in search within 60 s | Must |
| FR-06 | *Example:* Expand the radius automatically when too few results are found | Should |
| FR-07 | *Example:* Search inside a map viewport (bounding box) as well as a radius | Should |
| [FR-nn] | [Requirement] | [Must / Should / Could] |

### 2.2 Non-functional requirements

| ID | Quality | Target | Measured as |
|---|---|---|---|
| NFR-01 | Latency | *Example:* p99 at or below 150 ms server side for nearby search | Service timing |
| NFR-02 | Availability | *Example:* 99.95% monthly for search; place edits may degrade first | Synthetic probes per region |
| NFR-03 | Freshness | *Example:* 99% of edits searchable within 60 s | Edit-to-visible probe |
| NFR-04 | Throughput | *Example:* 17 400 searches/s globally at peak | Load test |
| NFR-05 | Result quality | *Example:* At least 5 results for 95% of queries outside wilderness areas | Offline replay of query logs |
| NFR-06 | Privacy | *Example:* Precise searcher location never stored in logs | Log review, automated scanner |
| [NFR-nn] | [Quality] | [Target] | [Measurement] |

### 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

<!-- Guidance: Back-of-the-envelope numbers decide the shape of the design. Show inputs, formulas and results; round generously and say which way you rounded. -->

### 3.1 Assumptions

| Input | Symbol | Value | Source |
|---|---|---|---|
| Places in the catalogue | $P$ | *Example:* 200 million | Catalogue count x growth |
| Daily active users | $D$ | *Example:* 100 million | Product analytics |
| Nearby searches per user per day | $s$ | *Example:* 5 | Product analytics |
| Peak to average ratio | $f$ | *Example:* 3 | Hourly traffic curve |
| Share of places changed per day | $c$ | *Example:* 0.5% | Catalogue audit log |
| Place record size in the catalogue | $r$ | *Example:* 1 KiB (1 024 B) | Schema estimate |
| Searches one index node serves | $q$ | *Example:* 4 000/s | Benchmark on target instance |
| Share of peak in the busiest region | $g$ | *Example:* 50% | Traffic by region |

### 3.2 Request rates

$$
Q_{avg} = \frac{D \times s}{86\,400} = \frac{10^{8} \times 5}{86\,400} \approx 5\,787 \ \text{searches/s}, \qquad Q_{peak} = 3 \times 5\,787 \approx 17\,361 \ \text{searches/s}
$$

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:

$$
M = P \times (32 + 3 \times 8 \times 2) = 2 \times 10^{8} \times 80 \ \text{B} = 16 \ \text{GB}
$$

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.

$$
N = \frac{8\,681}{4\,000} \times 1.5 \approx 3.3 \Rightarrow 4 \ \text{nodes, plus 1 spare for a zone loss} = 5 \ \text{nodes}
$$

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

### 3.5 Summary

| Quantity | Estimate | Design consequence |
|---|---|---|
| Searches | ~17 400/s peak globally, ~8 700/s in the busiest region | Stateless search nodes behind a load balancer |
| Writes | ~11.6 place changes/s | Asynchronous index updates through a change stream |
| Read to write ratio | ~500 to 1 | Optimise and cache the read path; index can lag by seconds |
| Index size | ~16 GB | Full copy per node, replicate instead of shard |
| Catalogue | ~205 GB | Sharded database, separate from search |
| Search nodes | 5 in the busiest region | Add replicas, not shards, as traffic grows |

## 4. API design

<!-- Guidance: Define the contract first: resources, methods, request and response shapes, errors, idempotency, pagination, rate limits and versioning. Use RFC 9457 problem details for errors. -->

### 4.1 Endpoints

| Method and path | Purpose | Notes |
|---|---|---|
| `GET /v1/search/nearby?lat=&lng=&radius_m=&category=&open_now=&cursor=` | Nearby search | Radius optional; service may widen it (FR-06) |
| `GET /v1/search/box?min_lat=&min_lng=&max_lat=&max_lng=&category=` | Viewport search | Used when the user pans the map |
| `GET /v1/places/{place_id}` | Place details | Served from the catalogue with a cache |
| `POST /v1/places` | Create a place | Owner or moderator; returns `place_id` |
| `PATCH /v1/places/{place_id}` | Edit a place | `If-Match` with the record version |
| `DELETE /v1/places/{place_id}` | Close a place | Soft delete; removed from search within 5 min |

### 4.2 Request and response example

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

```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

| Case | Status | Body |
|---|---|---|
| Latitude outside -90 to 90 or longitude outside -180 to 180 | 400 | Problem details, `invalid-coordinates` |
| Radius above 25 km | 400 | Problem details with the maximum |
| Too many requests | 429 | `Retry-After`, see `system-design/design-rate-limiter` |
| Index node not ready (loading snapshot) | 503 | Load balancer removes the node until ready |

## 5. Data model

<!-- Guidance: Choose storage by access pattern, not by habit. Show entities, keys, partitioning and the queries each store must answer. -->

### 5.1 Entities

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

```mermaid
erDiagram
  PLACE {
    string place_id PK
    string name
    float lat
    float lng
    string category
    float rating
    string hours
    string status
    int version
  }
  CELL_ENTRY {
    string h3_cell PK
    string place_id PK
    int resolution
  }
  CELL_COUNT {
    string h3_cell_res7 PK
    int place_count
  }
  CHANGE_EVENT {
    bigint offset PK
    string place_id FK
    string op
    int version
  }
  PLACE ||--|{ CELL_ENTRY : "indexed as"
  PLACE ||--o{ CHANGE_EVENT : "changed by"
  CELL_COUNT ||--o{ CELL_ENTRY : "summarises"
```

### 5.2 Storage choices

| Data | Store | Key | Main queries | Why |
|---|---|---|---|---|
| Places (source of truth) | *Example:* Sharded relational database | `place_id`, sharded by hash of `place_id` | Read and update one place | Transactions on edits, ordinary backups |
| Search index | In-memory maps in every search node | H3 cell ID to list of place IDs, at resolutions 7, 8, 9 | All places in a set of cells | 16 GB fits in memory; no network hop |
| Place summaries for ranking | In-memory array in every search node | Dense integer per place | Coordinates, category, rating, hours | Cache-friendly scan of candidates |
| Density map | In-memory map | H3 resolution 7 cell to place count | Choose radius and resolution | Tiny, rebuilt with each snapshot |
| Change stream | *Example:* Log-based message queue | `place_id` partition key | Apply edits in order per place | Ordered per place, replayable |
| Index snapshots | Object storage | Snapshot version | Load a new node quickly | Faster than rebuilding from the database |

### 5.3 Access patterns

| Access pattern | Frequency | Key or index that serves it | Partition key rationale |
|---|---|---|---|
| Find places near a point | ~17 400/s peak | `gridDisk` of the cell containing the point, then cell lists | No partitioning: every node holds the full index, so any node answers any query |
| Find places in a viewport | ~10% of searches | Cells covering the box at a resolution chosen from the box size | Same full index |
| Decide radius and resolution | Every search | Density map keyed by resolution 7 cell | Small enough to replicate everywhere |
| Read place details | Every result click | `place_id` in the catalogue, behind a cache | Hash of `place_id` spreads load evenly |
| Edit a place | ~11.6/s | `place_id` row, then change event | Change stream partitioned by `place_id` keeps per-place order |
| Rebuild the index | Daily snapshot | Full scan of the catalogue | Offline job, never on the request path |

## 6. High-level design

<!-- Guidance: One diagram that shows every component on the request paths and where state lives. Name components by responsibility. -->

```mermaid
flowchart LR
  client([Client app]) --> lb[Load balancer]
  lb --> search[Search service nodes]
  search --> idx[(In-memory H3 index, full copy per node)]
  client --> places[Place service]
  places --> db[(Place database)]
  places --> cdc[[Change stream]]
  cdc --> search
  db --> snap[Snapshot builder]
  snap --> obj[(Object storage snapshots)]
  obj --> search
  places --> cache[(Place detail cache)]
```

| Component | Responsibility | Scales by |
|---|---|---|
| Search service | Pick radius and resolution, read cells, filter, rank | Replicas per region |
| In-memory index | Cell lists, place summaries, density map | Memory per node (16 GB now) |
| Place service | CRUD on places, validation, emit change events | Stateless replicas |
| Place database | Source of truth | Shards by `place_id` |
| Change stream | Ordered edits per place | Partitions |
| Snapshot builder | Daily full index build and density map | Batch job |
| Place detail cache | Hot place records | Cache nodes |

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

<!-- Guidance: Go deep on the parts that are new, risky or contested. Show the sequence of calls and the failure behaviour of each step. -->

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

| Deep dive | Options considered | Choice | Reason | Section |
|---|---|---|---|---|
| Spatial index | Lat/lng B-tree, geohash, quadtree, S2, H3 | H3 at resolutions 7, 8, 9 | Uniform neighbour distance, fixed cell sets, mature library | 7.2 |
| Search radius | Fixed radius, expanding rings, density-based | Density-based with expansion | Bounded work downtown, results in the countryside | 7.3 |
| Ranking | Distance only, rating only, blended score | Blended score on a bounded candidate set | Matches user intent; cost bounded by 7.3 | 7.4 |
| Index freshness | Rebuild nightly, query the database, stream changes | Stream changes plus daily snapshot | Edits visible in seconds; fast node start | 7.5 |

### 7.1 Distance

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

$$
d = 2 R_{E} \arcsin\left(\sqrt{\sin^{2}\frac{\Delta\varphi}{2} + \cos\varphi_{1}\cos\varphi_{2}\sin^{2}\frac{\Delta\lambda}{2}}\right)
$$

*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

| Index | Cell shape and key | Neighbour search | Strengths | Weaknesses |
|---|---|---|---|---|
| B-tree on latitude and longitude | None | Range on one column, filter the other | No new concepts | Scans a whole band of the planet; slow at scale |
| Geohash | Rectangles; base32 string, prefix = parent | Cell plus 8 neighbours | Sortable string, works in any key-value store | Cell sizes vary with latitude; neighbours at two distances; edge effects at prefix boundaries |
| Quadtree | Squares split when full | Tree walk | Adapts to density automatically | In-memory tree to build and rebalance; harder to distribute |
| S2 | Quadrilateral cells on a cube, 64-bit ID on a Hilbert curve, levels 0 to 30 | Region coverer returns a cell union | Cell IDs keep locality; precise coverings | Squares, so neighbour distances differ |
| H3 | Hexagons (12 pentagons per resolution), 64-bit ID, resolutions 0 to 15 | `gridDisk(cell, k)` returns $1 + 3k(k+1)$ cells | All six neighbours at one distance; simple rings | Children do not tile the parent exactly; pentagons need care |

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

| Geohash length | Cell width at equator | Cell height | Width at latitude 40 degrees |
|---|---|---|---|
| 4 | ~39.1 km | ~19.4 km | ~30.0 km |
| 5 | ~4.89 km | ~4.86 km | ~3.75 km |
| 6 | ~1.22 km | ~0.61 km | ~0.94 km |
| 7 | ~153 m | ~152 m | ~117 m |

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):

| Resolution | Average hexagon area | Average edge length | Role in this design |
|---|---|---|---|
| 7 | 5.161 km² | 1.406 km | Rural searches and the density map |
| 8 | 0.737 km² | 0.531 km | Default suburban search |
| 9 | 0.105 km² | 0.201 km | Dense city centres |

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:

$$
k = \left\lceil \frac{R + e}{d} - \frac{1}{2} \right\rceil, \qquad \text{cells} = 1 + 3k(k+1)
$$

| Area type | Example density | Radius | Resolution | Rings $k$ | Cells read | Area read | Area read / circle area | Expected candidates |
|---|---|---|---|---|---|---|---|---|
| *Example:* Dense centre | 1 500 places/km² | 0.5 km | 9 | 2 | 19 | 2.00 km² | 2.55 | ~3 000 |
| *Example:* Suburb | 100 places/km² | 2 km | 8 | 3 | 37 | 27.3 km² | 2.17 | ~2 700 |
| *Example:* Rural | 5 places/km² | 5 km | 7 | 3 | 37 | 191 km² | 2.43 | ~950 |

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).

```mermaid
sequenceDiagram
  participant C as Client
  participant S as Search node
  participant D as Density map
  participant I as Cell index
  C->>S: nearby(lat, lng, radius 2 km, cafe)
  S->>D: count in resolution 7 cell
  D-->>S: dense, about 1 500 per km2
  S->>S: choose resolution 9, radius 0.5 km, k = 2
  S->>I: read 19 cells
  I-->>S: about 3 000 place IDs
  S->>S: filter category and hours, haversine, rank
  alt at least 20 results
    S-->>C: top 20, effective radius 500 m
  else fewer than 20
    S->>I: read next ring
    I-->>S: more place IDs
    S-->>C: top results, widened radius
  end
```

### 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

<!-- Guidance: Show how the design meets the numbers in section 3 and where it will break first. -->

| Concern | Approach | Limit before redesign |
|---|---|---|
| Search rate | Stateless replicas with a full index each | *Example:* about 4 000 searches/s per node; add nodes linearly |
| Index size | Compact summaries, three cell lists | *Example:* about 40 GB, past which memory per node gets costly; then shard by region (10) |
| Dense areas | Adaptive radius caps candidates at about 3 000 | Very dense venues (stadium, mall) need resolution 10 |
| Hot areas (events) | Cache results per (resolution 9 cell, category, page) for 30 s | Personalised ranking defeats the cache |
| Edit bursts (bulk import) | Stream throttled; snapshot rebuild for imports over 1 million places | Import window planned with operations |

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

| Step | Budget |
|---|---|
| Parse, authenticate, rate limit | 5 ms |
| Density lookup and ring selection | 1 ms |
| Read up to 37 cell lists | 5 ms |
| Filter, haversine, rank about 3 000 candidates | 10 ms |
| Fetch display fields for 20 results from cache | 20 ms |
| Serialise and respond | 5 ms |
| Headroom (garbage collection, network) | 104 ms |

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

<!-- Guidance: Name the failure modes with their blast radius and recovery time, the threats, and the signals operators watch. Each mitigation should be testable. -->

### 9.1 Failure modes

| Component | Failure | Detection | Blast radius | Mitigation | RTO |
|---|---|---|---|---|---|
| Search node | Crash or out of memory | Health check, load balancer | Requests in flight on one node | Other replicas serve; spare node per region | *Example:* 30 s |
| Change stream | Consumer lag or outage | Lag metric per node | Edits not visible; search still works on slightly stale data | Alert at 60 s lag; nodes keep serving; replay on recovery | *Example:* 15 min |
| Place database | Primary failover | Error rate on writes | Place edits and details for one shard | Search unaffected; details served from cache | *Example:* 60 s |
| Snapshot | Corrupt or missing snapshot | Checksum and place-count check before load | New nodes cannot start | Keep the last 7 snapshots; fall back to the previous one plus longer replay | *Example:* 1 h |
| Density map | Stale after a big import | Result-count monitor by area | Too many or too few candidates in one area | Rebuild density map with the import; expansion loop still finds results | *Example:* 1 day |
| Whole region | Region loss | Global health checks | Users in that region | DNS steering to the next region; every region has the full index | *Example:* 5 min |
| [Component] | [Failure] | [Signal] | [Scope] | [Mitigation] | [Time] |

### 9.2 Security and privacy

| Threat or duty | Control |
|---|---|
| Searcher location is personal data in many jurisdictions | Round coordinates in logs and cache keys (4.2); keep raw coordinates only in memory for the request |
| Scraping the whole catalogue through tiled searches | Per-key and per-IP rate limits; anomaly detection on grid-like query patterns |
| Fake or malicious place edits | Ownership verification, moderation queue for name and location changes |
| Revealing a private home location (home-based businesses) | Owners can hide the exact address; search returns a rounded location |
| [Threat] | [Control] |

### 9.3 Observability

| Signal | Metric or log | Alert threshold |
|---|---|---|
| Latency | p99 per region | Above 150 ms for 10 min |
| Empty results | Share of queries with zero results by area type | Doubling vs. 7-day baseline |
| Candidates per query | p99 candidate count | Above 5 000 |
| Index lag | Seconds behind the change stream per node | Above 60 s |
| Node memory | Heap use | Above 80% |

### 9.4 Cost estimate

| Item | Unit cost | Quantity | Monthly cost |
|---|---|---|---|
| Search nodes (64 GB memory) | [$/node-month] | *Example:* 5 in the busiest region, 3 in each other region | [$] |
| Place database | [$/month] | [Shards x replicas] | [$] |
| Change stream | [$/month] | [Partitions] | [$] |
| Snapshot storage | [$/GB-month] | *Example:* 7 x 16 GB per region | [$] |
| **Total** | | | **[$]** |

## 10. Trade-offs and alternatives

<!-- Guidance: For each major decision list the options, what each costs and why you chose one. Reviewers will propose the alternatives anyway; answer them here. -->

| Decision | Options | Chosen | Why | What we give up |
|---|---|---|---|---|
| Spatial index | Geohash; quadtree; S2; H3 | H3 | Rings with one neighbour distance, fixed cell sets per resolution | A library dependency; pentagon edge cases |
| Index placement | Geo-enabled database; Redis GEO; in-process memory | In-process memory | No network hop; 16 GB fits one node | Each node must load 16 GB at start |
| Replicate or shard | Shard by region or cell; full replica | Full replica | Any node answers any query; no scatter-gather | Memory cost grows with every replica |
| Radius | Fixed; adaptive | Adaptive by density | Bounded work and non-empty results | Users see a different effective radius |
| Freshness | Query the database; nightly rebuild; stream | Stream plus snapshot | Seconds of lag, fast recovery | Two paths to keep consistent |
| What changes at 10x / 0.1x | 10x (about 174 000 searches/s, 2 billion places): about 33 nodes in the busiest region by the 3.4 formula, and an index near 160 GB, so shard by continent or by resolution 3 cell and route queries by location, with cross-shard reads only near shard borders. 0.1x (about 1 700 searches/s): one node per region plus a spare, or a geo-enabled database with a geohash or GiST index is enough and simpler to run | Review at each doubling of places or traffic | Index size, not query rate, forces sharding first | [Note] |
| [Decision] | [Options] | [Chosen] | [Why] | [Cost] |

## 11. Delivery plan and risks

<!-- Guidance: How the design reaches production safely, and what could stop it. -->

### 11.1 Milestones

| Milestone | Scope | Exit criterion | Target date |
|---|---|---|---|
| M1 | Snapshot builder and in-memory index, shadow traffic | Shadow results overlap current results at 90% for the top 10 | YYYY-MM-DD |
| M2 | Change stream and freshness probe | 99% of edits visible within 60 s for 14 days | YYYY-MM-DD |
| M3 | Adaptive radius and ranking, 10% of traffic | Empty-result rate and p99 latency at or better than baseline | YYYY-MM-DD |
| M4 | All traffic, old database query retired | Database CPU from search under 5% | YYYY-MM-DD |

### 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

| ID | Risk | Likelihood | Impact | Mitigation | Owner |
|---|---|---|---|---|---|
| R-01 | *Example:* Ranking change lowers click-through | Medium | High | A/B test with click and conversion metrics before M4 | [@name] |
| R-02 | *Example:* Node start too slow during scale-out | Medium | Medium | Pre-warmed spare per region; snapshot in the same region | [@name] |
| R-03 | *Example:* Location data in logs breaches privacy policy | Low | High | Rounding at the edge, log scanner in CI | [@name] |
| [R-nn] | [Risk] | [L / M / H] | [L / M / H] | [Mitigation] | [@name] |

## 12. Appendices

<!-- Guidance: Supporting detail, glossary and open questions. -->

### 12.1 Open questions

| ID | Question | Owner | Due |
|---|---|---|---|
| OQ-01 | *Example:* Do we need indoor or multi-floor search for malls? | [@name] | YYYY-MM-DD |
| OQ-02 | *Example:* Should "open now" use the searcher's or the place's time zone near borders? | [@name] | YYYY-MM-DD |
| [OQ-nn] | [Question] | [@name] | YYYY-MM-DD |

### 12.2 Glossary

| Term | Meaning |
|---|---|
| Geohash | Base32 string built by interleaving longitude and latitude bits; a shared prefix means a shared parent rectangle |
| H3 | Hexagonal hierarchical grid with 16 resolutions (0 to 15) and 64-bit cell IDs |
| `gridDisk` | H3 function that returns all cells within $k$ steps of a cell |
| S2 | Hierarchical grid of quadrilateral cells on a cube projection, numbered along a Hilbert curve |
| Quadtree | Tree that splits a square into four children when it holds too many points |
| Haversine | Great-circle distance formula on a sphere |
| Effective radius | The radius the service actually searched after density adaptation |
| [Term] | [Meaning] |

### 12.3 References

| Reference | Use |
|---|---|
| H3 documentation, ["Tables of Cell Statistics Across Resolutions"](https://h3geo.org/docs/core-library/restable/) (h3geo.org, library 4.x) | Cell areas and edge lengths in 7.2 and 7.3 |
| H3 documentation, ["Grid traversal functions"](https://h3geo.org/docs/api/traversal) | `gridDisk`, ring sizes, pentagon note |
| Redis documentation, ["GEOADD"](https://redis.io/docs/latest/commands/geoadd/) | Geohash in a sorted set, 0.5% distance error, 7.6 |
| S2 Geometry, ["S2 Cell Hierarchy"](https://s2geometry.io/devguide/s2cell_hierarchy.html) | S2 levels, Hilbert curve IDs, region coverer, 7.6 |
| RFC 9457 Problem Details for HTTP APIs | Error bodies in 4.3 |
| Ride-Hailing Dispatch System Design (`system-design/design-ride-matching`) | Moving objects on the same H3 grid |
| Maps and Navigation System Design (`system-design/design-maps-navigation`) | Routing and travel-time ranking |
| Distributed Cache System Design (`system-design/design-distributed-cache`) | Place detail cache |
| CDC Pipeline System Design (`system-design/design-cdc-pipeline`) | Change stream from the place database |
| Back-of-Envelope Estimation and Capacity Model (`system-design/back-of-envelope-estimation`) | Method for section 3 |

## 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.