Design a Proximity Service

This page is one interview loop in three rounds. All three rounds design the same system. Each round opens with the interviewer raising the scope, and the design from the round before has to evolve to meet it.

You can start at any round. Rounds 2 and 3 open with a "Where we left off" summary that catches you up.

Loop Opener: What Is a Proximity Service?

You Already Use One Every Day

Open a maps app and type "coffee". In a fraction of a second you get a list of cafés, nearest first, each with a distance, a rating and whether it's open. Food delivery, dating, real estate and ride-hailing apps all ask the same question millions of times a minute: what is near this point?

A proximity service answers it. It stores places (restaurants, shops, gas stations), each with a latitude and a longitude, and answers "places within r meters of (lat, lon), matching these filters".

A few words we'll use all page:

What Makes It Hard

• Databases index one dimension; closeness has two. A normal index sorts values on a line. "Near" means close in latitude and longitude at the same time.
• The world is unevenly filled. A block in Manhattan holds hundreds of places. A square kilometer of rural Montana may hold none. Any fixed grid is too fine in one place and too coarse in the other.
• The Earth is round. A degree of longitude is 111 km wide at the equator and zero at the poles. Grids have edges, and the ±180° line cuts the map in two.
• Reads dwarf writes. Places change a few times a year; searches never stop.

The Question the Whole Loop Answers

How do we turn "near me" into a fast index lookup that never misses a place just across a line?

The answer grows every round:

• Round 1: map 2-D onto 1-D cells, search the cell and its neighbors, then check exact distances. A spatial database does all of this for one city.
• Round 2: keep a complete cell index in memory, adapt the cell size to the density, and fix the edges (cell borders, the date line, the poles).
• Round 3: put the index close to users in several regions, add live signals and personal ranking, and keep user locations private.

---

Round 1 · Mid-level · "Nearby Coffee Shops for One City"

~35 min · SDE II (L5) · 1 region · 50,000 places · 100 searches/s peak · P99 < 200 ms · 99.9%

R1.1 Establish Design Scope

The interviewer says: "Design the backend for a city guide app. Users want to find coffee shops near them." Before drawing anything, we ask.

Out of scope for this round: other cities, ranking by rating, "open now", and search by name.

R1.2 Functional Requirements, Derived Step by Step

Not yet: worldwide coverage, ranking by rating, "open now", and search by name.

R1.3 Non-Functional Requirements: the Questions

We name each quality in words first; the numbers come in R1.7.

• Read-heavy. Searches outnumber edits by thousands to one. We should spend effort making reads cheap, even if writes get a bit more expensive.
• Latency. The list must feel instant while someone stands on a street corner.
• Freshness of edits. When an owner changes their hours, customers should see it soon. "Soon" is a number we'll pick.
• Never miss a nearby place. A café 20 m away that doesn't show up is the worst bug this product can have. Users notice it immediately and stop trusting the app. In our terms: recall inside the radius must be 100%.

R1.4 The API

Search nearby

httpCopy
GET /v1/places/nearby?lat=37.7740&lon=-122.4098&radius_m=1000&category=coffee&limit=20 HTTP/1.1
Host: api.cityguide.example

jsonCopy
{
  "places": [
    { "place_id": "p_48213", "name": "Mint Plaza Coffee", "category": "coffee",
      "lat": 37.7740, "lon": -122.40955, "distance_m": 22 },
    { "place_id": "p_10977", "name": "Sixth Street Roasters", "category": "coffee",
      "lat": 37.7781, "lon": -122.4129, "distance_m": 531 }
  ],
  "next_cursor": "c1.Gx7Qm2fLr8kPz0aT"
}

Why a cursor, and not page=2 or offset=20? With an offset, page 2 re-runs the search and skips the first 20 rows. If a new café opened in between, or the user walked 50 m and the phone sent a new position, the order shifts: one place shows up twice and another never appears. A cursor is an opaque token that remembers where page 1 ended: the original center and radius, and the last result's (distance, place_id). Page 2 asks for places strictly after that pair in the same order (keyset pagination), from the same center. The place_id breaks ties between two places at the same distance.

Place details

httpCopy
GET /v1/places/p_48213 HTTP/1.1

jsonCopy
{ "place_id": "p_48213", "name": "Mint Plaza Coffee", "category": "coffee",
  "lat": 37.7740, "lon": -122.40955, "address": "12 Mint Plaza, San Francisco, CA",
  "phone": "+14155550123", "hours": { "mon": [["07:00", "17:00"]] }, "version": 7 }

Owner create and update

httpCopy
POST /v1/places HTTP/1.1
Authorization: Bearer <owner token>
Content-Type: application/json

{ "name": "Mint Plaza Coffee", "category": "coffee", "lat": 37.7740, "lon": -122.40955,
  "address": "12 Mint Plaza, San Francisco, CA", "hours": { "mon": [["07:00", "17:00"]] } }

httpCopy
PATCH /v1/places/p_48213 HTTP/1.1
If-Match: "7"
Content-Type: application/json

{ "hours": { "mon": [["08:00", "16:00"]] } }

The update carries the version it was based on (If-Match). If someone else changed the place meanwhile, we return 412 Precondition Failed instead of silently overwriting their change.

Status codes

Recap

• Search: a point, a radius from 500 m to 5 km, a category; 20 results, nearest first, with a cursor.
• 50,000 static places in one city; rare owner edits.
• Recall inside the radius must be 100%.

R1.5 Design Evolution: From a Box Query to a Spatial Index

Each step is a problem, your turn to think, the answer, and what it costs us.

Step 1.0: The Baseline

A places table with lat and lon columns and a B-tree index on each. To search, we turn the circle into a box in degrees and filter:

sqlCopy
SELECT place_id, name, lat, lon
FROM places
WHERE category = 'coffee'
  AND lat BETWEEN 37.7650 AND 37.7830      -- 1 km north and south
  AND lon BETWEEN -122.4212 AND -122.3984; -- 1 km east and west, widened by 1/cos(latitude)

The service then computes each row's distance, drops rows outside the circle, sorts, and keeps 20.

For 50,000 places this works fine, and it's where every candidate should start. The weakness is in how the database uses the indexes.

Step 1.1: The Box Query Scans Too Much

Step 1.2: The Café 22 m Away Is Missing

Synthesizing vector architecture diagram...

The block of nine cells guarantees the café across the edge is a candidate; the distance filter throws away the corners of the block that are outside the circle.

Step 1.3: Which Cell Size?

Step 1.4: The Distances Are Wrong

Step 1.5: Or Just Use the Database's Spatial Index?

Round 1 Step Summary

R1.6 Architecture v1

Synthesizing vector architecture diagram...

Everything goes through one small API service. Searches and details read the Aurora reader; owner edits go to the writer. If the writer fails, Aurora promotes the reader, and the API reconnects through the cluster endpoint.

The table

sqlCopy
CREATE EXTENSION IF NOT EXISTS postgis;
CREATE EXTENSION IF NOT EXISTS btree_gist;

CREATE TABLE places (
    place_id    BIGINT PRIMARY KEY,
    name        TEXT        NOT NULL,
    category    TEXT        NOT NULL,
    location    GEOGRAPHY(Point, 4326) NOT NULL,   -- WGS-84 longitude/latitude
    address     TEXT        NOT NULL,
    phone       TEXT,
    hours       JSONB,                              -- weekly schedule
    owner_id    BIGINT      NOT NULL,
    version     INTEGER     NOT NULL DEFAULT 1,     -- bumped on every update
    updated_at  TIMESTAMPTZ NOT NULL DEFAULT now()
);

CREATE INDEX places_loc     ON places USING GIST (location);
CREATE INDEX places_cat_loc ON places USING GIST (category, location);

Tracing a search: "coffee within 1 km"

1. The app sends GET /v1/places/nearby?lat=37.7740&lon=-122.4098&radius_m=1000&category=coffee.
2. WAF checks the caller's rate; the ALB forwards to a task.
3. The task validates the input and runs the ST_DWithin query on the reader, ordered by (distance_m, place_id), limit 21 (one extra tells us whether a next page exists).
4. The reader walks the (category, location) GiST index, reads the few hundred matching rows, computes ellipsoidal distances, sorts and returns 21 rows.
5. The task returns 20, and a cursor built from the 20th row's distance and ID.

Tracing an edit: an owner changes Monday's hours

1. PATCH /v1/places/p_48213 with If-Match: "7".
2. The task runs UPDATE places SET hours = ..., version = 8, updated_at = now() WHERE place_id = 48213 AND version = 7 on the writer. Zero rows updated means someone else changed it: 412.
3. The response goes back to the owner, whose own app reads details from the writer for a minute afterward, so they see their own edit at once.
4. Other users may see the old hours for up to 30 s, until the details cache entry in each task expires. The reader itself is usually well under a second behind.

R1.7 Numbers

Targets

Traffic

Storage

The whole database fits in the memory of the smallest sensible instance, so searches never wait on disk.

Work per search. We assume the city covers about 400 km², so about 125 places per km². A 1 km circle is π × 1² ≈ 3.1 km²: about 390 places, of which coffee (say 5%) is about 20. A 5 km circle is 78.5 km²: about 9,800 places, about 490 coffee. With the (category, location) index, the database reads roughly the coffee places in the circle's box, not the whole city. We plan on 2 to 20 ms per query (an assumption to load-test), so 100 searches a second use well under one CPU.

Latency budget, search P99 (dependent steps add):

Monthly cost (us-east-1 on-demand list prices, 730 hours a month; check the AWS Pricing Calculator before quoting):

R1.8 Trade-Offs

Ways to index "near"

For Round 1, PostGIS wins: one query, correct everywhere, no code. The other rows matter when the data outgrows one database.

Precomputed cells vs query-time search. We could store each place's geohash in a column and look up the 9 cells by prefix, or let the GiST index find points at query time. Precomputed cells make reads simple key lookups (great for caches and key-value stores) but fix the cell size in advance. A query-time spatial index adapts to any radius and shape but needs a database that understands geometry. Round 1 uses query-time search; Round 2 precomputes.

R1.9 Failure Modes

R1.10 Pillar Check

R1.11 Round 1 Rubric and Follow-Ups

What a strong mid-level (L5) answer shows

• Explains why two 1-D indexes can't answer a 2-D question efficiently.
• Encodes a geohash by hand, and knows a shared prefix means a shared cell but not the converse.
• Searches the 3×3 block and filters by exact distance, and separates recall (the block) from precision (the filter).
• Picks the cell size from the radius and the latitude.
• Uses Haversine or ellipsoidal distance, never Pythagoras on degrees.
• Chooses PostGIS for one city, and says when it stops being enough.

Follow-up questions

1. "Why does the 3×3 block need the cell to be at least as big as the radius?" Answer: the user can stand in a corner of the center cell. The circle then reaches r past that corner in two directions. The neighbors are one cell deep, so they catch everything only if a cell is at least r tall and r wide. If r is bigger, part of the circle falls in the second ring of cells and those places are silently missed.

2. "Why not cache search results by the exact (lat, lon)?" Answer: two users a meter apart send different coordinates, so the cache would almost never hit. If we cache, the key must be a cell (and the query's other parameters), not a raw coordinate. Round 2 does exactly that, and recomputes distances per user.

3. "A user searches at 89.9°N. What happens?" Answer: with PostGIS geography, the query is correct: it's just a distance on the ellipsoid. With hand-built geohash cells, the cells near the pole are thin slivers and the circle covers every longitude, so the 3×3 block is wrong. We'd treat it as a polar cap: all longitudes above a latitude. It's rare, and Round 2 handles it.

Interview gotchas from this round's wrong answers

---

Round 2 · Senior · "200M Places Worldwide, 100M Daily Users"

~40 min · Senior SDE (L6) · 1 region, 3 AZs · 58,000 searches/s peak · 200M places · search P99 < 30 ms · edits visible in 30 s · 99.99%

R2.0 Where We Left Off

This is what the candidate says aloud in the first 60 seconds of Round 2. If you're starting here, it's everything you need from Round 1.

Round 1 in 60 seconds. "We built nearby search for one city: 50,000 places, about 100 searches a second at peak, radii from 500 m to 5 km, 20 results nearest first with a cursor. We learned why two 1-D indexes can't answer a 2-D question, and how a geohash maps 2-D to 1-D: interleave longitude and latitude bits and write them in Base32, so a shared prefix means a shared cell. Because a user can stand next to a cell edge, we search the cell and its 8 neighbors and then filter by exact distance: the 3×3 block gives recall, the filter gives precision, and the block only covers the circle if a cell is at least the radius tall and wide at that latitude. We measure distance with Haversine, never Pythagoras on degrees. Then we noticed PostGIS does all of this for one city: a geography column, a GiST index and ST_DWithin. So v1 is an API on three Fargate tasks over an Aurora PostgreSQL writer and reader with PostGIS, with a 30-second details cache. About $540 a month. Open costs: every search runs on the database, and one fixed cell size can't fit both a dense and an empty area."

Architecture v1, compact

Synthesizing vector architecture diagram...

Round 1 in one picture: the database is the spatial index, and every search reaches it.

Round 1 step summary

Open costs: the database carries every search; fixed precision; no ranking beyond distance.

R2.1 The Scope Raise

Interviewer: "The app went global. We now list 200 million places worldwide and have 100 million daily users, each searching about five times a day. Dinner time is brutal. People want the best places, not just the nearest, and they want to hide places that are closed right now. Owners complain that their changes take too long to show up. And we have users in Fiji and in Norway's far north who report odd results."

Scope change

The "Not yet" list from R1.2 comes back: worldwide coverage, ranking by rating and "open now" are now in scope. Search by name stays out; it belongs to a separate text-search system.

R2.2 What Breaks in the Round 1 Design

The order we fix it in: take reads off the database first (2.1), because every later fix lives in the new read path. Then density (2.2), ranking and filters (2.3), edges (2.4), hot spots (2.5) and freshness (2.6). Sizing comes in R2.6.

R2.3 New Requirements and API Additions

Search, with sorting and filters

httpCopy
GET /v1/places/nearby?lat=40.7549&lon=-73.9840&category=coffee&sort=distance&open_now=true&min_rating=4.0&limit=20 HTTP/1.1
Host: api.places.example

• sort=distance (nearest first) or sort=quality (best first, within the radius).
• radius_m is now optional, from 100 m to 20 km. Without it, the service chooses a radius from the local density and widens it until it has enough results or reaches 20 km.
• open_now uses the place's own time zone. min_rating and price filter on stored values.

jsonCopy
{
  "places": [
    { "place_id": "p_7730192", "name": "Bryant Park Espresso", "category": "coffee",
      "lat": 40.7536, "lon": -73.9832, "distance_m": 158, "rating": 4.5, "review_count": 812,
      "open_now": true, "open_until_local": "20:00",
      "why": ["158 m away", "4.5 stars from 812 reviews", "open until 20:00"] }
  ],
  "search": { "radius_used_m": 400, "sort": "distance", "exhausted": false },
  "next_cursor": "c2.Hq9Zr4LwX1bV"
}

• why explains each result in plain words: the distance, the rating and its number of reviews, and why it passed the filters. Users trust a ranking they can read, and support staff can answer "why is this first?".
• radius_used_m says how far we looked. exhausted: true means we reached 20 km and there are no more results, so the app can say "no more gas stations within 20 km" instead of an unexplained short list.

Owner edits. The same PATCH with If-Match. The promise: within 30 seconds of a 200 OK, every search and details view shows the change.

Details are now served through a CDN (step 2.6) with Cache-Control: max-age=0, s-maxage=15: browsers and apps don't cache, and the CDN caches for at most 15 seconds.

"Open now" rules.

• Hours are stored in local time per weekday, for example fri: [["18:00", "02:00"]]. An interval that crosses midnight belongs to the day it starts, so at 01:00 on Saturday we also check Friday's intervals.
• "Now" is computed in the place's IANA time zone (for example America/New_York), using the time-zone database, so daylight-saving changes are handled for us.
• Special days (holidays) override the weekly schedule for that date.

R2.4 Design Evolution: An Index That Fits the World

Step 2.1: The Database Can't Serve 58,000 Searches a Second

Synthesizing vector architecture diagram...

Writes flow one way: database, log, topic, updater, index. The search service only reads the index, so it never waits on the database.

Primitives: Distributed Cache Patterns and Eviction · Change Data Capture and the Outbox Pattern

Drill: The dual-write that broke search consistency (the dual-write failure and "CDC versus polling an outbox" are answered in the paragraph "Why CDC" above)

Step 2.2: Manhattan Returns 5,000 Candidates; Montana Returns None

Primitive: Geospatial Indexing: Geohash, Quadtree and S2

Step 2.3: Rank by Quality, Filter by "Open Now"

Step 2.4: Users in Fiji See Half the Results

Synthesizing vector architecture diagram...

Only the box needs splitting; the distance formula already works across the line.

Step 2.5: Times Square on New Year's Eve

Drill: The ride-hailing hotspot on New Year's Eve (why one fixed precision fails under a thousandfold density difference is step 2.2; why not query GEORADIUS directly instead of our own index, and the in-memory S2 or quadtree alternative, are the note in step 2.1 and the last paragraph above)

Step 2.6: The Owner Fixed Their Hours, but Search Still Shows the Old Ones

Drill: The product page that melted Redis (the cold-cache stampede and "why not cache forever" are the two bullets above)

Round 2 Step Summary

R2.5 Architecture v2

Synthesizing vector architecture diagram...

Searches go straight to the regional load balancer and never touch Aurora. Details go through CloudFront to a small service that reads Aurora readers. Owner edits go to the writer, and flow back into Valkey through the log, the topic and the updater.

Tracing a dense-city search: "nearest open coffee" at (40.7549, −73.9840)

Synthesizing vector architecture diagram...

Two dependent round trips to Valkey. The next request from the same precision-7 cell within 10 s reuses the cached candidates and only recomputes distances.

Tracing a sparse-area search: "nearest gas station" near Jordan, Montana (47.32, −106.91)

1. The density map says 0.02 gas stations per km² here, so the starting radius is 25.2 km, capped at 20 km.
2. At 47.5°N, a precision-4 cell is 19.4 km tall and 26.4 km wide. It's shorter than 20 km, so no 3×3 block works; we list every precision-4 cell touching the 40 km × 40 km box: at most 4 rows × 3 columns = 12.
3. One pipeline of 12 ZRANGE reads; most keys don't exist, which means "no gas stations in that cell". We get 5 members.
4. Exact distance keeps 3 within 20 km. We fetch 3 cards and return them with radius_used_m: 20000, exhausted: true.

Tracing an owner edit: Friday closing time 22:00 → 18:00

1. PATCH /v1/places/p_7730192 with If-Match: "41" reaches the place management API.
2. UPDATE places SET hours = ..., version = 42 WHERE place_id = 7730192 AND version = 41 commits on the writer.
3. Within about a second (at most 5 s by alarm), Debezium publishes the old and new rows to the topic, keyed by the place ID.
4. The updater sees the location and categories are unchanged, so the index members don't change (hours aren't in them). It writes card version 42, because the stored card is version 41.
5. New searches show "open until 18:00" at once; hot cells within their 10 s cache TTL. The details page shows it after at most 15 s of CDN caching, since the details service reads the reader directly.

Losing a whole shard. Each shard has a primary and two replicas in different AZs, and ElastiCache promotes a replica if the primary fails. Replication is asynchronous, so a promotion can lose the last few milliseconds of writes. After any failover, the updater replays the topic from 10 minutes before the failover, in order; because it applies each place's events in order, replaying a window ends in the right state. If all three nodes of a shard were lost at once, its slots would come back empty, and a missing key would wrongly mean "no places". So we keep one small canary key per hash slot (16,384 keys, with names chosen so one lands in each slot). A checker reads them every 5 seconds; if any is missing, it publishes the list of lost slots to the search tasks, which send searches touching those slots to PostGIS under a rate limit while a bulk job reloads the slots from Aurora. After the reload, the updater replays the topic from before the reload began, and the checker restores the canaries last.

R2.6 Numbers and Cost

Traffic

We plan every component for 58,000 searches a second of traffic. The fleet's capacity is higher, because it must still carry that peak after losing an AZ; that headroom is capacity, not a second traffic number.

Storage in Aurora

Aurora keeps six copies of the data across three AZs, but the storage price already covers them: we pay once for 540 GB, not three or six times.

The Valkey index

A sanity check against the rough "hot set" estimate: about 500,000 busy urban precision-6 cells × 150 place IDs × 16 bytes ≈ 1.2 GB of IDs serve most searches. Our index is much bigger because it is complete (every place, three or four precisions, per category) and carries coordinates and ratings in each entry. That's the price of never falling back to the database, and it still fits in a few nodes. The cards are the 60 GB of summaries (200M × 300 B), kept for every place rather than a 1.5 KB summary for the top 20%, so no search ever misses.

Valkey nodes. We use cache.r7g.2xlarge nodes (8 vCPU, 52.82 GiB). ElastiCache reserves 25% of memory by default, and we fill the rest to 80%: 56.7 GB × 0.75 × 0.8 ≈ 34 GB of data per shard. Memory alone needs 152 ÷ 34 ≈ 4.5 shards. Throughput:

• Commands per search (assumptions): a distance search reads 9 to 12 keys and about 40 cards, about 52 commands; a quality search reads 20 to 50 keys and about 60 cards, about 90. With half of each, about 71; with 30% of searches answered from task candidate caches, about 50 per search.
• At peak: 58,000 × 50 ≈ 2.9M commands a second, at a planning figure of 400,000 pipelined commands a second per node (an assumption to load-test).

We run 6 shards × 3 nodes (a primary and two replicas, one per AZ) = 18 nodes. Losing an AZ leaves 12 nodes: 12 × 400,000 = 4.8M, so 60% busy. Memory per shard is 152 ÷ 6 ≈ 25 GB, with room for about two years of growth before we reshard online.

Why AZ-local reads matter for cost. An average search moves about 26 KB from Valkey (about 14 KB of index entries and 12 KB of cards). At 5,787 searches a second × 70% not cached × 26 KB ≈ 105 MB/s, a month is about 277 TB. If two-thirds of it crossed AZs at $0.02/GB ($0.01 each way), that's about $3,700 a month; with a copy of every shard in every AZ, reads stay in the task's AZ and that line disappears.

Search fleet. We plan 500 searches a second per vCPU (an assumption). If one AZ is lost, the other two must carry 58,000, so each AZ needs 29,000 ÷ 1,000 = 29 tasks of 2 vCPU: 87 tasks at peak. Traffic averages a tenth of peak, and the fleet scales with it; we assume a monthly average of 36 tasks (12 per AZ, never below that).

Aurora. The search path doesn't read Aurora. Details do: 23,150/s at peak, of which about half miss CloudFront's 15-second cache (an assumption for a long-tail catalog), so about 11,600 primary-key reads a second. At a planning figure of 10,000 a second per db.r6g.2xlarge reader, three readers (one per AZ) carry it with one AZ lost: 5,800 each. Plus the writer: 4 instances. RDS Proxy pools the connections.

Bandwidth. A search response is about 8 KB of JSON, about 3 KB compressed (an assumption). Average egress: 5,787 × 3 KB ≈ 17.4 MB/s; over a 30.4-day month (2,626,560 s), about 45.6 TB. Details through CloudFront: 2,315/s × 2 KB ≈ 4.6 MB/s, about 12.2 TB a month. Requests per month: searches 5,787 × 2,626,560 ≈ 15.2 billion; details 2,315 × 2,626,560 ≈ 6.08 billion.

Latency budget, search P99 (at our load balancer; dependent steps add):

Availability. 99.99% of a 30.4-day month is 43,776 min × 0.0001 ≈ 4.4 minutes. Search depends on the ALB, the tasks and Valkey, all spread across three AZs, and not on Aurora; an Aurora failover (typically under a minute) affects only details misses and edits.

Security edge. AWS WAF bills $0.60 per million requests: 21.3 billion requests a month would cost about $12,800. AWS Shield Advanced costs $3,000 a month (one-year commitment) plus a data-transfer fee ($0.05/GB for load balancers and $0.025/GB for CloudFront, for the first 100 TB), and it covers AWS WAF request charges for the resources it protects, up to 50 billion requests a month. That's $3,000 + 45,600 GB × $0.05 + 12,200 GB × $0.025 ≈ $5,590, and it adds DDoS response help. We choose Shield Advanced.

Monthly cost (us-east-1 on-demand list prices, 730 hours a month):

The biggest lines are the index (Valkey, about $9.2K) and the edge (CloudFront, Shield and data transfer, about $16.6K). The database, which Round 1 was built around, is now about $4K. At 15 billion searches a month, that's about $2.30 per million searches.

R2.7 Trade-Offs

Spatial index at this scale

Geohash is not the most elegant grid. S2 covers a circle more tightly and handles the sphere for us; H3's equal-distance rings suit aggregation. We chose geohash because it's simple to explain, the prefix and precision table are easy to reason about, and the in-memory index hides its waste. Moving to S2 would change the cell function, not the architecture.

Valkey index vs OpenSearch. Amazon OpenSearch Service can index a geo_point field, filter with geo_distance, and rank with a function score in one query, with filters and text search built in. At 58,000 queries a second it needs a large cluster, and P99 under 30 ms would be hard with scoring on every query. We keep OpenSearch as the answer for name and text search, and use the Valkey index for "near me".

Precomputed vs query-time ranking. Precomputed scores in the sorted sets make "best within 1 km" a few ZRANGE calls; the cost is approximate ranking at the rim and a recompute when reviews change. Query-time ranking of every candidate is exact but reads everything in dense areas. Round 3 adds a personal re-rank on top of the precomputed candidates.

CloudFront for details. It costs about $7.1K a month, mostly per-request fees. Serving details straight from the load balancer would cost about $1K in egress, but would double the Aurora reads and lose edge TLS termination for far-away users. We keep it, and revisit it in Round 3 when the per-request fee grows.

R2.8 Failure Modes

Primitive: Circuit Breaker, Bulkhead and Fault Tolerance

R2.9 Production Gotchas

R2.10 Pillar Check

R2.11 Round 2 Rubric and Follow-Ups

What a strong senior (L6) answer shows

• Takes the database off the read path, and explains why a complete index is safer than a cache-aside cell cache (empty vs missing keys, partial records, refill races).
• Feeds the index by CDC with ordering per place, and explains dual writes and why log reading beats polling.
• Adapts the radius and precision to density, and proves the distance search is exact.
• Ranks with a Bayesian score, knows where top-K per cell is exact and where it's approximate.
• Handles the date line and the poles explicitly.
• Caches per cell but computes per user, and adds up every delay in the freshness budget.

Follow-up questions

1. "Why store coordinates inside each sorted-set member instead of just place IDs?" Answer: so we can compute exact distances and apply rating and price filters before fetching any card. In Midtown a search reads about 760 members but fetches only about 40 cards. With bare IDs we'd fetch 760 cards (about 230 KB) per search, which at 58,000 searches a second is over 13 GB/s of cache traffic.

2. "The updater crashes after adding a place to its new cell but before removing it from the old one. What does a user see?" Answer: for a moment the place is in both cells. Both members carry their own coordinates, and results are de-duplicated by place ID, so at worst the old position's member passes the distance filter once. When the updater restarts, it re-reads the event from its last committed offset and removes the old member. Applying each place's events in order makes the replay converge.

3. "How would you know the index silently lost some places?" Answer: three signals. Canary keys catch lost slots within seconds. The daily reconciliation compares sampled Aurora rows with members and cards. And the empty-result rate per area, compared with the density map, catches areas that suddenly return nothing.

Interview gotchas from this round's wrong answers

---

Round 3 · Architect · "Global, Fresh, Personalized, and Multi-Region"

~45 min · Principal (L7) · 4 regions · 300,000 searches/s summed over regional peaks · 400M places · search P99 < 50 ms in every region · 99.99% per region

R3.0 Where We Left Off

Round 2 in 60 seconds. "We serve 200 million places and 58,000 searches a second at peak from one region, with search P99 under 30 ms. Aurora PostgreSQL with PostGIS is the source of truth but is off the search path. A complete index lives in ElastiCache for Valkey: sorted sets per geohash precision, cell and category, whose members carry each place's ID, coordinates, rating and price, scored by a Bayesian quality score, plus a 300-byte card per place. Debezium reads Aurora's log into MSK, and an updater applies each place's changes in order, so a missing key means 'no places', never 'not loaded'. A density map picks the starting radius, the radius and latitude pick the precision, and the search widens until it has 20 results or reaches 20 km; distance search is exact, quality search is exact inside the circle and approximate at the rim. We split boxes at ±180° and send polar caps to PostGIS. A per-cell candidate cache in each task, with single-flight, absorbs hot spots while each user still gets exact distances. Edits show within 17 seconds in search and 16 on details, under the 30-second promise. About $34.9K a month. Open costs: one region serves the world, the data is static, everyone gets the same ranking, and raw coordinates sit in our request logs."

Architecture v2, compact

Synthesizing vector architecture diagram...

Round 2 in one picture: search reads only the in-memory index; the database feeds it through its own log.

Round 2 step summary

Open costs: a single region; no live data; one ranking for all; precise locations in logs.

R3.1 The Scope Raise

Interviewer: "We're now the default places app on four continents. 400 million places and 400 million daily users. Users in Tokyo and Sydney say we're slow. Product wants a 'busy right now' indicator, built from anonymous phone counts, and results personalized to each user's taste. Legal reminds us that precise location is sensitive personal data in many countries. And each region must keep serving if another region goes down."

Scope change

R3.2 What Breaks in the Round 2 Design

R3.3 New Requirements and API Additions

Search moves into a request body, so the position never appears in a URL, and therefore never in access logs:

httpCopy
POST /v1/places:search HTTP/1.1
Host: api.places.example
Content-Type: application/json
X-Taste-Profile: tp1.AAECAwQF...<signed, expires 2027-03-02T08:00Z>

{
  "lat": 35.6938, "lon": 139.7034,
  "category": "ramen", "sort": "quality", "radius_m": 1000, "open_now": true,
  "personalize": true
}

jsonCopy
{
  "places": [
    { "place_id": "p_90331877", "name": "Menya Kaze", "distance_m": 412, "rating": 4.4,
      "busy": { "level": "busier_than_usual", "as_of": "2027-03-01T12:10:00Z" },
      "why": ["412 m away", "4.4 stars from 1,203 reviews", "matches ramen you liked"],
      "sources": [{ "name": "Owner", "fields": ["hours"] }, { "name": "Provider B", "fields": ["name", "address"] }],
      "attribution": "Some data © Provider B" }
  ],
  "search": { "radius_used_m": 1000, "personalized": true, "served_by": "ap-northeast-1" }
}

• personalize: false is the opt-out, per request. The account-level opt-out also stops the app from sending a profile at all.
• X-Taste-Profile carries the user's taste as a short vector (step 3.3), signed by our profile job and valid for 24 hours. The user's profile travels with the request; no region has to look it up.
• busy is a level ("quieter than usual", "usual", "busier than usual") and its time, never a count.
• sources and attribution record where each field came from, because some licensed data must be credited or can't be shown everywhere.
• Accounts gain a data_region: where that user's personal data (profile, history, taste vector) is stored and processed.

A presence endpoint for "busy now", anonymous by design:

httpCopy
POST /v1/presence HTTP/1.1
Content-Type: application/json

{ "place_id": "p_90331877", "visit_token": "vt_3kq9...", "window": "2027-03-01T12:05Z" }

No account, no coordinates: the phone decides on its own that it's inside a place it already knows from recent results. The visit_token is random, changes every day, and is never linked to the account; it only lets us count one phone once per window.

R3.4 Design Evolution: Going Global Without Losing the Plot

Step 3.1: Serve Locally Worldwide

Synthesizing vector architecture diagram...

Each region owns its area and keeps a warm copy of its buddy's. Halo copies between neighbors (for example Europe and South Asia) are left out of the picture.

Primitives: Database Sharding and Partition Keys · Cloud Disaster Recovery and Multi-Region Active-Active

Step 3.2: Show How Busy a Place Is Right Now

Synthesizing vector architecture diagram...

The only thing that leaves the stream is a coarse level for places with at least 10 distinct visitors.

Primitive: Message Queues vs Event Streams

Step 3.3: Personal Ranking Within 50 ms

Step 3.4: User Locations Are Sensitive

Step 3.5: Place Data Comes From Many Sources

Step 3.6: A Region Is Down

Round 3 Step Summary

R3.5 Global Architecture

Synthesizing vector architecture diagram...

One region's stack. Its home places live in Aurora and flow into Valkey through the log; presence events flow into the same Valkey as busy levels. Dotted lines leave the region: change topics and the database copy go to the buddy, and far-away searches go to their owning region.

Tracing a search in Tokyo: "best ramen within 1 km, open now, personalized" at (35.6938, 139.7034)

Synthesizing vector architecture diagram...

The same two round trips as Round 2, plus the busy hashes in the second one and a sub-2 ms re-rank. The coordinates arrive in the body and are never logged; the search log gets xn775, category and result count.

Tracing a busy-now update

1. A phone that opted in has been inside Menya Kaze for 5 minutes. It sends POST /v1/presence with the place ID, today's random token and the window 12:05.
2. The ingest service checks the device-integrity token and a rate limit per visit_token, then puts the event into Kinesis with the place ID as the partition key.
3. At 12:10, Flink's 15-minute window (11:55 to 12:10) holds 23 distinct tokens for this place. The usual count for Monday 21:00 local time (12:00 UTC) is 14, so the level is "busier than usual".
4. Flink writes HSET busy:xn775 p_90331877 "busier|2027-03-01T12:10Z".
5. Searches from 12:10 show the level; searches after 12:30 ignore it unless a newer window has replaced it.

Tracing a region failover: ap-southeast-1 fails at 09:00 UTC

Synthesizing vector architecture diagram...

Search recovers in a few minutes without anyone acting. Users land wherever latency routing sends them, and any region that isn't the buddy forwards the failed region's cells to it. Edits wait, and only an operator turns the buddy's database copy into a writer.

R3.6 Numbers and Cost

Traffic

The 300,000 is the sum of the four regional peaks, which is what we must provision, since each region is sized for its own peak. The four peaks happen at different hours, so the whole world's traffic at any one moment is lower.

Places and memory per region. Each place costs about 830 bytes in Valkey: 390 B of index entries (4.875 entries at 80 B, from Round 2), 370 B of card, and 64 B of embedding. Each region holds its home places, its halo (2%) and its buddy's places:

Busy hashes add little: at most one short field per place with a signal.

Valkey capacity. About 55 commands per search: Round 2's 50 plus about 5 busy-hash reads (the re-rank uses cards we already fetch). Planning figure: 400,000 commands a second per cache.r7g.2xlarge node. Each region must carry (a) its own peak after losing an AZ, and (b) its own load plus its buddy's peak during a regional failover (we don't plan for both at once).

The shares of each region's peak during the buddy's peak (half, 20%, 90%) are assumptions from the time-zone offsets. Memory per shard is 22 to 29 GB, under the 34 GB we allow. Singapore runs 1.5 times the nodes its own traffic needs (it needs 12, runs 18), because its buddy peaks at almost the same time: the cost of pairing regions an hour apart.

Search fleet. Re-ranking adds CPU, so we plan 400 searches a second per vCPU, 800 per 2-vCPU task. Each AZ must carry half the region's peak:

During a regional failover the buddy's fleet scales out on Fargate within minutes; tasks are cheap to add, unlike Valkey memory, which is why Valkey is the part sized ahead.

Details and Aurora. Details views: 400M × 2 = 800M a day, 9,259/s average, 92,600/s summed peak; half miss CloudFront. us-east-1's origin peak is 35% × 92,600 × 50% ≈ 16,200/s; with three readers at 10,000/s each, losing one AZ leaves two at 8,100/s. Each region runs a writer and three readers for its home cluster, plus a two-instance Aurora Global Database secondary for its buddy: 6 db.r6g.2xlarge per region. Aurora storage: 1.5 KB × 1.8 per place, home plus buddy copy: 2 × 400M × 2.7 KB ≈ 2.2 TB in total.

Live signals. 20% of users opt in (assumption): 80M phones × 4 visits a day = 320M events a day, 3,704/s on average. Peaks for presence are flatter than for search (people are in places all day), so we plan 3× each region's average: us-east-1 3,889/s → 5 Kinesis shards (1,000 records/s each, plus one spare); 16 shards in total. Flink: about 16 processing units across the four regions.

Latency budget, search P99 at the regional ALB:

Forwarded searches add the backbone round trip (for example about 230 ms Tokyo to Frankfurt) and are reported separately.

Egress. Responses grow to about 3.5 KB compressed. A 30.4-day month is 2,626,560 s.

Security edge. Requests a month: searches 2.6B × 30.4 ≈ 79.0B, details 800M × 30.4 ≈ 24.3B, presence 320M × 30.4 ≈ 9.7B: about 113 billion. Shield Advanced covers WAF request fees up to 50 billion a month per payer account; the other 63 billion cost $0.60 per million: about $37.8K. Shield's data-transfer fee is tiered: load balancers 100 TB × $0.05 + 176.7 TB × $0.04 = $12,070; CloudFront 48.6 TB × $0.025 ≈ $1,220; plus the $3,000 subscription: about $16.3K.

Monthly cost. Prices outside us-east-1 are higher. We use each region's list price for Valkey nodes (about +20% in Frankfurt, Tokyo and Singapore) and Aurora instances (about +21%), and assume +15% in eu-central-1 and +25% in the two Asia-Pacific regions for Fargate and the smaller lines (check the calculator per region).

The edge (data transfer, CloudFront, Shield and WAF) is about $111.1K, 49% of the bill. The index is 21%, and the database 11%. At 79 billion searches a month, that's about $2.85 per million searches, a little more than Round 2's $2.30 because of the buddy copies, the busy pipeline and WAF requests past the covered 50 billion.

R3.7 Trade-Offs

Geographic ownership vs a copy of everything everywhere

We chose ownership because 95% of searches are near the user, and it halves the memory. If trip planning grew to a large share of searches, a full-copy tier for the index only (not the databases) would be the next step.

Live-signal threshold vs coverage. A minimum of 10 distinct phones protects individuals and filters noise, but only busy places ever get a level; small cafés never do. Lowering the threshold covers more places and reveals more about fewer people. We start at 10 and publish relative levels only; raising coverage means more opted-in users, not a lower threshold.

Personalization vs latency. Re-ranking 50 candidates with a small model costs 2 ms; re-ranking 500 with a large model could lift relevance a little and would cost tens of milliseconds and much more CPU. The profile in the request avoids a lookup entirely, at the price of a 24-hour-old profile. We accept both.

Closing the loop on CloudFront. At this scale CloudFront's per-request fee ($29.2K) is one of the biggest lines. The alternative is serving details from each regional stack: about $4K of egress plus doubled Aurora reads (roughly 12 more readers, about $11K), so about $18K a month cheaper, with regional stacks now close to users anyway. The other levers are a spend commitment with AWS that lowers CloudFront and WAF prices, and smaller responses. We would measure the CDN's real hit ratio first; if it's near our 50% assumption, moving details to the regional stacks wins.

What changed from Round 1. Round 1 answered "near me" with one database query. Round 3 answers it with four regions of in-memory indexes that the database feeds but never serves from. The idea at the core didn't change: cells that map 2-D to 1-D, a neighbor search that never misses across an edge, and exact distance to decide.

R3.8 Failure Modes

R3.9 Runbook and Incident Response

Golden signals, per region OPS 8 · REL 6

Hotspot procedure REL 7

1. Identify the hot cells: top keys by read rate on the busiest shard, and the top cache keys in the search tasks.
2. Confirm the candidate cache is hitting for those cells; if not, check for a query parameter that breaks the cache key (a client sending unrounded radii, for example).
3. If one shard is still hot, add copies of the hottest keys under suffixed names on other shards, and turn on random selection for them.
4. For announced events (New Year's Eve, a stadium final), pre-scale the search fleet in that region the hour before.

Regional failover procedure REL 13

1. Confirm it's the region: several services and AWS health signals agree. Route 53 moves users on its own; confirm every region's partition map now marks the failed region's cells as owned by the buddy, so the other regions forward those searches.
2. Watch the buddy: search P99, Valkey CPU, fleet scaling. Shed personalization first if the buddy is short of capacity.
3. If the outage lasts more than an hour and edits matter: set the failed region's writer flag to "fenced", then promote the Aurora secondary in the buddy (command 5). Point the place API for those cells at it. Then start a Debezium connector on the promoted cluster (a new replication slot and a fresh snapshot of those cells), feeding the buddy's updater; without it, edits written to the promoted cluster never reach the index and stay invisible in search.
4. When the region returns: it rejoins as a secondary, catches up, and a planned switchover (command 6) moves its places back.

Go deeper: CLI playbook

Plain commands an on-call engineer runs one at a time. Replace names and ARNs with real ones.

textCopy
# 1. Alarms firing for the places service in a region
aws cloudwatch describe-alarms --region ap-northeast-1 --state-value ALARM --alarm-name-prefix places-

# 2. Health check status for a regional search endpoint
aws route53 get-health-check-status --health-check-id 1a2b3c4d-5e6f-7a8b-9c0d-1e2f3a4b5c6d

# 3. State of a region's Valkey index cluster
aws elasticache describe-replication-groups --region ap-northeast-1 --replication-group-id places-index

# 4. Emergency scale-out of the search fleet
aws ecs update-service --region ap-northeast-1 --cluster places --service search --desired-count 200

# 5. Unplanned promotion of the buddy's Aurora secondary (can lose the replication lag)
aws rds failover-global-cluster --global-cluster-identifier places-sea --target-db-cluster-identifier arn:aws:rds:ap-northeast-1:111122223333:cluster:places-sea-apne1 --allow-data-loss

# 6. Planned switchover back once the region is healthy (waits for replication)
aws rds switchover-global-cluster --global-cluster-identifier places-sea --target-db-cluster-identifier arn:aws:rds:ap-southeast-1:111122223333:cluster:places-sea-apse1

# 7. The presence stream's shape and retention
aws kinesis describe-stream-summary --region ap-northeast-1 --stream-name presence-events

# 8. State of the busy-now Flink application
aws kinesisanalyticsv2 describe-application --region ap-northeast-1 --application-name busy-now

# 9. State of the cross-region copy of the buddy's change topic
aws kafka describe-replicator --region ap-northeast-1 --replicator-arn arn:aws:kafka:ap-northeast-1:111122223333:replicator/sea-to-apne1/1a2b3c4d-5e6f-7a8b-9c0d-1e2f3a4b5c6d-2

Audit query (read-only, on a reader): places whose index card version lags the database are found by the reconciliation job; this query lists the rows it samples.

sqlCopy
SELECT place_id, version, updated_at
FROM places TABLESAMPLE SYSTEM (0.01)
WHERE updated_at < now() - interval '1 minute';

R3.10 Pillar Check

R3.11 Round 3 Rubric and Follow-Ups

What an architect (L7) answer adds over L6

• Places data by geography, routes by the searched point, and handles borders with halos.
• Plans region failure with a warm buddy, sizes capacity for the pair's overlapping peaks, and doesn't promise more nines than DNS failover allows.
• Builds live signals that are anonymous by construction: no account, no coordinates, distinct counts, a minimum count and relative levels.
• Personalizes with retrieval then re-ranking, and keeps profiles out of every region by sending them with the request.
• Finds every place a location can leak (URLs, access logs, traces, analytics) and closes each one.
• Treats place data as merged from sources with field-level priority and licenses.
• Sees that the edge, not the index, is half the bill, and names the levers.

Follow-up questions

1. "A user stands in Strasbourg, right at the France-Germany border, and both are in eu-central-1. What about a user at the US-Mexico border?" Answer: both sides of both borders belong to the same home region, so nothing special happens. Region borders are drawn in the partition map by us, through oceans and sparse areas where possible. Where a border does cut through populated land, the halo covers it: each region indexes places up to 20 km beyond its border, the maximum radius.

2. "Why not send exact counts for busy-now? More useful." Answer: an exact small count can identify people ("the one visitor at 7 am is my neighbor"), and a count is only meaningful against the place's size, which users don't know. A level relative to the usual for that hour answers the real question ("will it be crowded?") and reveals less.

3. "Your 99.99% per region: what does a regional outage do to it?" Answer: 99.99% of a month is 4.4 minutes. A DNS failover takes about 1.5 to 3 minutes for most clients, so one regional failover a month uses most of that region's budget. That's why we promise 99.99% per region and not 99.999% (5.26 minutes a year): a single failover would spend the year's budget.

Interview gotchas from this round's wrong answers

---

Loop Closer: Interview Strategy for All Three Rounds

How to Run Each 60-Minute Round

For how to spend a single 45-minute round, see the 45-minute interview blueprint.

The Two Sentences That Matter Most

• Opening any round: "Databases index one dimension and closeness has two, so I'll map positions to cells, search the user's cell and its neighbors with cells at least as big as the radius at that latitude, and let an exact distance decide: the cells give recall, the distance gives precision."
• When scale arrives: "I'll keep the spatial database as the source of truth and serve reads from a complete in-memory cell index fed by its change log, so a missing key means 'nothing here', and I'll let density choose the radius so Manhattan and Montana both do bounded work."

Well-Architected Review Sheet

Interviewers rarely ask "which pillar is this?". They ask the pillar's question in plain words. Rehearse one sentence per row.

Rubric Across Levels