← all topics Dating geo board · say it in this order 1 Problem2 Entities + API 3 High-level design4 Deep dives 5 Final + levelsreset

Design the geolocation half of Tinder or Bumble

10M daily users · 2,300 location writes a second · 1,200 deck builds a second · Hello Interview flow, board rules, one idea per line
SAY THIS SENTENCE FIRST

"The interesting thing about dating geo is that almost nothing about it is a hard real-time problem. A location fifteen minutes old is perfectly good, because nobody's dating radius moves in fifteen minutes, and that single fact makes the write path lossy, unordered and cheap. What is actually hard is three things: density varies by four orders of magnitude so a fixed radius is wrong at both ends, a circle is not a cell so the index over-fetches and then measures, and exact distance is a coordinate, which means the number that makes the product work is also the number that can find someone's apartment."

STEP 1 OF 5

Understanding the problem

5 min

Functional Requirements

  1. A user's location should follow them as they move, without draining the battery.
    • A user can set their location to another city (travel mode), and it replaces the device's location until it expires.
  2. A user should get a deck of nearby candidates that respects their distance preference.
  3. The distance shown should be useful to a dater and useless to a stalker.
  4. It should work in Manhattan and in rural Montana without two different systems.

Below the line (out of scope):

  • Swipes and mutual matching. It is a like write plus a reciprocal check, it is cheap, and it never touches geo. Cutting it explicitly is what buys the time to go deep on the part that was actually asked about.
  • Recommendation ranking and the ML behind who appears first. Geo produces the candidate SET; ranking orders it, and that is a different hour.
  • Chat, photo storage and moderation, payments and boosts.

Non-Functional Requirements

Do the scale math first, because it shows where the simple design breaks
  • About 2,300 location writes, 1,200 deck builds and 11,500 swipes a second. The three rates are not close to each other.
    • Inputs: 10M daily users, each making about 20 location writes, 10 app opens and 100 swipes a day, over 86,400 seconds a day.
    • Location writes: about 2,300 a second. Small.
    • Deck builds: about 1,200 a second. This is the only expensive read in the system.
    • Swipes: about 11,500 a second, ten times the deck rate, so a swipe cannot afford any geo work.
    • The shape of the answer falls out of that: the expensive thing happens 1,200 times a second, so it can afford to be clever.
  • Manhattan is about 28,000 people per square kilometre. Rural Montana is about 1.8. That is four orders of magnitude.
    • A 5 km circle covers 78 square kilometres either way: about 2.2M people in one and about 140 in the other.
    • One fixed radius therefore returns a crowd you throw away, or an empty product. Both are failures.
  1. A location fifteen minutes old is fine, and that staleness tolerance is what the whole design spends.
    • Nobody's set of plausible dates changes because they walked three blocks.
    • So the write path can lose updates, reorder them, and lag, and none of it matters. That is unusual and it should be stated as a decision rather than assumed.
    • The contrast worth drawing: a ride-hailing app needs your position to the second, which is why its design looks nothing like this one even though both are "geospatial".
  2. Population density spans four orders of magnitude, so one fixed radius cannot serve both city and countryside. It is the requirement people forget, and it is the one that breaks naive designs.
  3. Deck latency p99 under about 300 ms. It is the app-open path, so it is the product's first impression and there is nothing to hide it behind.
  4. Precise distance is a coordinate in disguise, so distance precision is a safety requirement. Safety is a functional requirement wearing a non-functional hat, and dating apps have been trilaterated in the wild. The precision of the number is a safety decision, not a UX preference.
  5. Consistency requirements are close to nil, and saying so is worth a sentence: there is no correctness problem if two users see slightly different distances, or if someone appears in a deck moments after going offline.
DONE WHEN: the interviewer has heard "fifteen minutes stale is fine" and "density spans four orders of magnitude". Those two license the cheap write path and the adaptive read.
STEP 2 OF 5

Entities + API

5 min

Defining the Core Entities

  • User is the profile plus the preferences that bound every query: maxDistanceKm, age range, and discoverable. The discoverable flag is load-bearing, because turning it off has to remove someone from the index rather than filter them at read time.
  • Location is the latest fix only, overwritten on every write: userId, lat, lon, cellId, lastSeenAt. No history is kept, and the coordinate never leaves the server.
    • Storing a location trail is a product decision nobody asked for and a liability everybody inherits. If it is not needed, not keeping it is the design.
  • GeoIndex entry is the index itself: cellId to a set of user ids. That is the whole structure, and it is small: 10M users at a few tens of bytes is under a gigabyte.
  • Deck is the list of candidates a user swipes through: userId to an ordered list of candidate ids.
  • ExclusionSet is who this user has already seen. It grows forever and is checked on every deck build, which makes it a real data-structure decision rather than a footnote.

API or System Interface

POST   /v1/location            // { lat, lon, accuracy } -> 204, no body

GET    /v1/deck?cursor=         // -> { candidates: [ { userId, photos, bio,
                               //        distance: "under 2 km" } ], cursor }

PUT    /v1/preferences         // { maxDistanceKm, ageRange, discoverable }
POST   /v1/travel              // { cityId } -> sets an explicit location, in scope as a constraint
  • The location write returns 204 with no body, because nothing reads its own write. That is a design statement: there is nothing useful to return, and an empty response keeps the cheapest call in the system cheap.
  • The deck returns a DISTANCE STRING, not a number. "under 2 km" cannot be trilaterated; "1.2 km" can. Making it a string in the response shape means no client, no analytics event and no debug view can accidentally leak precision later.
  • No endpoint anywhere returns another user's latitude and longitude. Say it as an invariant, because the leak is usually not the main endpoint: it is a debug field, an analytics payload, or a photo's EXIF data.
  • The deck is cursor-paginated, not offset-paginated, because the underlying candidate set is changing under you and an offset would skip and repeat people.
  • Preferences are a write, not a query parameter, so the deck builder reads them from the user rather than being handed them at read time.
DONE WHEN: you have said "204, nothing reads its own write" and "distance is a string, on purpose".
STEP 3 OF 5

High-level design

10 min, end to end, no dives yet

1) Location follows the user

Location in: a fire-and-forget write that moves a user between cells MobileClient sends a location fix to LocationService as the user moves, and LocationService answers 204 with no body. LocationService then moves the user between cells in GeoIndex and overwrites the latest fix in UserState. Notes below show what one write carries and how travel mode uses the same write. Location in: a fire-and-forget write that moves a user between cells the new fix overwrites the old one: no trail is kept, and the coordinate never leaves the server. MobileClient sends a fix asthe user moves LocationService fire and forget, returns 204nothing reads its own write GeoIndex cellId -> set of userIds UserState latest fix only: lat, lon,cellId, lastSeenAt 1. MobileClient sends a fixas the user moves 2. LocationService answers 204with no body, because nothingreads its own write 3. LocationService moves theuser out of the old celland into the new one 4. LocationService overwritesthe latest fix and lastSeenAt what one write actually is: POST /v1/location (no read path){"lat":40.7411,"lon":-73.9897,"accuracy":20}204 No Contentcell = cellId(lat, lon) travel mode is the same write: POST /v1/travel{"cityId":"nyc"}the cell comes from the city the user picked,not from the device a dropped or out-of-order update costs nothing: the next one replaces it, and a location 15 minutes old is fine.
  • The client sends a fix as the user moves. How often the phone reports, and on what signal, sets both the battery cost and the write rate; the dive on moving users settles it.
  • The write is fire and forget. 204, no body, no read-your-writes, no ordering guarantee. If two updates arrive out of order the loser is a location from four minutes ago, which is inside the staleness budget anyway.
  • All the service does is move a user between cells and stamp lastSeenAt. The new fix overwrites the old one; no trail is kept.
  • Travel mode is the same cell write, with the cell taken from the city the user picked (POST /v1/travel) instead of from the device.

2) The index: cells, not radii

The index: a nearby query is a prefix read A schematic grid shows one parent cell with the prefix dr5r, split into child cells. The user sits near its right edge, and a prefix read returns everyone inside the parent cell. The user's distance preference is a circle that crosses the cell edge, and one person inside the circle sits in the next cell with a different prefix. On the right, DeckBuilder asks GeoIndex for every user under the prefix and GeoIndex returns their userIds. The index: a nearby query is a prefix read everyone whose cell shares a prefix with mine, at a cell size about as wide as my distance preference. prefix dr5r: one read returns everyone in here dr5x me inside my circle, butunder dr5x, so theprefix read misses them the circle is my distance preference; the cell is a square DeckBuilder needs the users near me GeoIndex cellId -> set of userIds 1. DeckBuilder asks forevery user underthe prefix dr5r 2. GeoIndex returnstheir userIds two places this simple read will strain, for the dive on finding nearby users: the square is not the circle, and a cell edge can split two people standing side by side.
  • The index is a map from cell id to a set of user ids. Geohash, S2 or H3 all give you the same shape; what matters is that a cell id is a prefix-comparable key, so "everyone near here" becomes a set of key lookups rather than a scan.
  • A nearby query is a prefix read: everyone whose cell shares a prefix with the user's own, at a cell size about as wide as their distance preference.
  • A cell is a square while the distance preference is a circle, and two people forty metres apart across a cell line share no prefix; the dive on finding nearby users handles both.

3) Building the deck

Building the deck: one page of candidates per request MobileClient asks DeckBuilder for a deck page with a cursor. DeckBuilder reads the user's preferences from User, reads nearby users from GeoIndex with the prefix read, and reads the user's ExclusionSet, then returns about twenty candidates and a cursor. The same query runs in Manhattan and in rural Montana, with the user's distance preference as the radius. Building the deck: one page of candidates per request the same query everywhere, with the user's distance preference as the radius. MobileClient shows the cards,asks for the next page DeckBuilder filters by age rangeand already seen User maxDistanceKm, ageRange,discoverable GeoIndex cellId -> set of userIds ExclusionSet who this userhas already seen 1. MobileClient asks forGET /v1/deck?cursor= 5. DeckBuilder returns abouttwenty candidates and a cursor 2. DeckBuilder readsthe user's preferences 3. DeckBuilder readsnearby users 4. DeckBuilder reads whothe user has already seen each swipe adds that candidate to the ExclusionSet, so nobody is shown twice. where this strains: the same radius holds a crowd in Manhattan and can come back empty in Montana (the density dive),and every page is another spatial query (the dive on the deck).
  • The deck builder makes a page of candidates on each request.
    • It reads the user's preferences, reads nearby users from the index, and drops anyone in the user's ExclusionSet or outside their age range.
    • It returns about twenty candidates and a cursor, and the client asks for the next page as the user swipes.
    • Each swipe adds that candidate to the ExclusionSet, so nobody is shown twice.
  • The same query runs in Manhattan and in rural Montana, with the user's distance preference as the radius. One system, as the requirement asks.
  • That radius holds a crowd in Manhattan and can come back empty in Montana; the density dive handles it.
  • Every page is another spatial query, so a heavy swiper keeps the index busy; the dive on the deck handles it.

4) The distance on each card

The distance on each card: computed on the server, returned as a string MobileClient asks DeckBuilder for a deck page. DeckBuilder computes each candidate's distance on the server, rounds it, and returns it as a string such as under 2 km. A code box shows what one candidate carries, and a second box lists what no response ever carries: another user's latitude and longitude. The distance on each card: computed on the server, returned as a string a dater needs to know roughly how far; they never need two decimal places. MobileClient shows the distanceit is given DeckBuilder computes each distanceand rounds it to a string 1. MobileClient asks forGET /v1/deck?cursor= 2. DeckBuilder returns eachcandidate with a distance string what each candidate carries: { "userId": "u_8812", "photos": [...], "bio": "...", "distance": "under 2 km" } what no response ever carries: another user's latitude and longitude,in the deck, a debug field or an analytics event where this strains: whether a rounded distance holds up against someone who can move and ask again is the trilateration dive.
  • The deck builder computes each candidate's distance on the server and returns it as a string such as "under 2 km". No response carries a coordinate.
  • Precision is the vulnerability, not the distance itself. A dater needs to know roughly how far; they never need two decimal places.
  • Whether a rounded distance holds up against someone who can move and ask again is the trilateration dive.
DONE WHEN: all four requirements have a path, and you have said out loud where this simple design strains: cell lines, density, a spatial query per page, and a distance someone could work backwards from.
STEP 4 OF 5

Potential deep dives

~20 min, interviewer steers
TRIGGER: "how do you find people nearby" / "what index"

1) What actually answers "who is near me"?

CELLS AS KEYS · OVER-FETCH THEN MEASURE · ALWAYS THE NEIGHBOURS
Bad Solution: a bounding box in SQL
  • WHERE lat BETWEEN ? AND ? AND lon BETWEEN ? AND ?
    • A B-tree on latitude and a B-tree on longitude cannot be used together: the database picks one, gets a band across the planet, and filters the rest by hand.
    • At 10M rows and 1,200 queries a second that is a scan per query and the database falls over.
    • It is also wrong at the poles and across the antimeridian, which is a smaller problem but the same root cause: latitude and longitude are not a plane.
Good Solution: geohash prefixes, or Redis GEO
  • Encode the position as a geohash and match on a prefix, which is exactly what Redis GEO does with a sorted set underneath. This genuinely works and it is the right family of answer.
    • Two gaps, and an interviewer will find both. A prefix match silently misses the neighbouring cells, so people forty metres apart never meet.
    • And the cell size is fixed globally, which is the density problem: one level cannot serve Manhattan and Montana.
Great Solution: a covering set of cells, plus neighbours, plus an exact filter
  • Turn the circle into a covering set of cell ids and read the union. S2 and H3 both do this properly; H3's hexagons have the pleasant property that all six neighbours are equidistant, which removes a class of corner cases.
  • Always include the eight surrounding cells, or two users either side of a cell line never see each other. This is the boundary bug, it is invisible in testing because your test users are never forty metres apart across a line, and it is the single most common defect in this design.
  • Then filter by exact haversine distance on each candidate's stored latitude and longitude, so the index only has to return a superset. Haversine on a few hundred candidates is microseconds, so the index only has to be a good superset, never a precise answer.
  • Keep the whole index in memory, because 10M users at about 32 bytes each (cell id, user id, latitude, longitude) is about 320 MB, well under a gigabyte. At that size this is a Redis-shaped problem, not a database-shaped one. That number is what makes the rest of the design affordable.
  • Shard by cell prefix so a region's users live together and a query touches one shard. The natural consequence is that dense regions get hot shards, which is the next dive rather than a surprise.
  • Cell size is the tuning knob: coarser cells over-fetch more with fewer lookups, finer cells waste less but read more neighbours. Pick per density rather than globally, which the density dive does.
  • Choose the cell level coarser than your GPS error. An urban fix can be 50 metres off, so indexing at 10-metre precision is inventing accuracy the input never had.
The index: a circle is not a cell, and the boundary catches everyone A schematic cell grid shows the 5 km query circle around one user, the cells it touches, and the eight neighbouring cells that must also be queried, since two users 40 m apart can sit in different cells. The same query as a pipeline: CellCover lists the cell ids, GeoIndex returns every user in them, DistanceFilter keeps only those inside the circle, and DeckBuilder ranks the survivors. The index: a circle is not a cell, and the boundary catches everyone cover the query circle with cells, over-fetch, then filter by true distance. my cell 5 km me 40 m apart. differentcells, no shared prefix,and a naive prefix queryreturns one and not theother. the query:everyone within 5 km the 8 neighbours you MUST also query shaded: the cells the circle overlaps, so the candidates are a superset.that is the point: over-fetch cheaply, then measure exactly. drawn schematically: a real level-13 cell is about 1 km across,so a 5 km circle covers dozens. density varies by 4 orders of magnitude: a square kilometre holdsabout 380 candidates in Manhattan, 0.025 in rural Montana. the same query, as a pipeline: CellCover picks the covering cellsplus the 8 neighbours GeoIndex cellId -> set of userIds DistanceFilter exact haversine, candidates onlydrops the corners the circlenever reached DeckBuilder ranks whatever survived 1. CellCover turns a circle and aradius into a list of cell ids 2. GeoIndex returns every usersitting in those cells 3. DistanceFilter measures eachcandidate exactly and drops theones outside the circle the not-so-happy paths: the boundary bug is the one everybody ships once: two people on opposite sides of a cell line are neighbours in the world and strangers in the index.a coarser cell means more over-fetch and fewer queries; a finer cell means less waste and more neighbours. that tradeoff is the whole tuning knob.
TRIGGER: "what about a rural user" / "Manhattan vs a small town"

2) Density that spans four orders of magnitude

TARGET A COUNT, NOT A RADIUS · STEP OUT BY LEVEL · CAP IT AND SAY SO
Bad Solution: one radius for everybody
  • Query 5 km, ship it.
    • Manhattan returns tens of thousands of candidates you immediately throw away, and the deck build blows its latency budget sorting people nobody will see.
    • Montana returns two, then one, then none. The product is empty and the user leaves.
    • The same query is simultaneously too expensive and useless, which is a good sign the parameter is the wrong one.
Good Solution: let the user pick the radius
  • Expose a distance slider and honour it. Necessary as a product feature, and it does help the rural case.
    • But it makes the user solve an engineering problem: nobody knows whether to ask for 50 km or 200 km, and they will drag it around until something appears.
    • It also does not bound the work: a rural user dragging to 500 km issues exactly the enormous query you were trying to avoid.
Great Solution: the radius is an output, and the level is the lever
  • The query asks for about three hundred candidates, and the radius is whatever it takes to find them. Start at a level sized for local density, and step out one level at a time until the count is met.
  • Each step out to the next coarser cell level covers roughly four times the area, so it converges in a handful of lookups even from a very sparse start. Manhattan is satisfied at the first level with roughly 380 candidates in a single square kilometre; Montana needs about 12,000 square kilometres for the same 300, which is six or seven steps and a radius near 60 km.
    • The 380 comes from the implied dater rate of about 1.4 percent. Rural Montana holds about 0.025 candidates per square kilometre.
    • Six or seven lookups is still cheap. The point is that the SAME loop serves both, not that both finish quickly.
  • Store an estimated density per cell so the build starts at the right level rather than discovering it. The estimate comes from the index itself. That turns the common case into a single lookup instead of a walk.
  • The user's slider becomes a filter, not the query. They cap how far they will travel; the system decides how far it must look to fill a deck.
  • Cap the expansion, and past the cap show "nobody nearby" rather than a distant match. "There is nobody nearby right now" is a better answer than someone three states away presented as local, and it is also what stops one lonely user issuing a continental query.
  • Hot shards are the consequence and they need naming: a dense city's cells are read constantly, so those shards get read replicas. It is a read-only, cacheable, small dataset, which is the easiest kind of hotspot to fix.
Manhattan and Montana are the same query and must not be the same radius Two 20 km squares with the same 5 km circle: Manhattan returns a crowd, rural Montana returns about 2 active daters. The fix asks for a count: AppOpen asks DeckBuilder for a deck, DeckBuilder queries GeoIndex at the smallest cell level, steps out a level while the count is short. A table shows where each city clears 300 candidates. Manhattan and Montana are the same query and must not be the same radius population density spans four orders of magnitude. a fixed radius is wrong at both ends. Manhattan, about 28,000 people per km2 5 km you one dot is roughly 90,000 people a 5 km circle covers 78 km2and about 2.2M peopleroughly 30,000 of them are active datersthe query returns a crowd youthen have to throw away rural Montana, about 1.8 people per km2 5 km you one dot is roughly 90 people the same 5 km circle coversabout 140 peopleroughly 2 are active datersthe query returns an empty product One fixed radiuscannot serve both. Query for a TARGET COUNT,not for a distance. both squares are 20 km across.both circles are the same 5 km radius. the dots sketch the density; theycannot share a scale, since the twodiffer by about 15,000 to 1. the fix: ask for a COUNT, and let the radius fall out of it 1 AppOpen asks DeckBuilder for a deck,not for a radius 2 DeckBuilder queries the smallest cell levelthat might hold enough people 3 DeckBuilder steps out one level and retrieswhen the count is short AppOpen DeckBuilder expands until it has ~300 candidatesone cell level at a time GeoIndex cellId -> active user idsone sorted set per cell 1 2 3 one level out is 4x the area. these four are drawn to scale: level 7, where Montana finally getsclose, is 64 times the area of theL10 square drawn here. it does notfit on this page, which is the point. L13 1.3 km2 L12 5.1 km2 L11 20 km2 L10 81 km2 cell level      cell area    active daters, Manhattan    active daters, Montana level 13          1.3 km2                         490                      0.03 level 12          5.1 km2                       1,940                      0.13 level 11           20 km2                       7,760                       0.5 level 10           81 km2                      31,000                         2   ...                 ...                         ...                       ... level 7         5,200 km2                           -                       133 level 6        20,800 km2                           -                       530 green rows are where the search can stop Manhattan clears 300 at the very first level it tries.Montana needs about 12,000 km2, a radius near 60 km: six or seven levelsout (seven on these average areas), or the cap, whichever comes first. S2 cell areas vary by about 2x across the sphere: these are averages, not guarantees. the not-so-happy paths: - a user in the middle of the ocean or the desert simply has no deck. say so honestly rather than widening forever.- the cap matters: without a maximum radius a lonely user eventually queries a continent.
TRIGGER: "how often does the phone report" / "what about battery"

3) Moving users, and how little you need to know

SIGNIFICANT CHANGE, NOT A TIMER · STALENESS IS THE BUDGET · AGE OUT THE GHOSTS
Bad Solution: stream the GPS
  • Subscribe to location updates and post each one.
    • 10M devices at one hertz is 10M writes a second, which is four thousand times the traffic the product actually needs.
    • It is also the fastest way to get uninstalled: continuous GPS is one of the few things a user can feel in their battery.
Good Solution: throttle to a fixed interval
  • Send a fix every five minutes while the app is open. Much better, and it is where most designs land.
    • It still writes constantly for the large majority of users who have not moved at all.
    • And it stops entirely when the app is backgrounded, which is exactly when someone commutes across town.
Great Solution: let the OS decide, and spend the staleness budget deliberately
  • Fifteen minutes of location lag is invisible to the product, and that staleness budget is what buys a lossy, unordered, cheap write path.
  • Use the OS significant-change API, which wakes the app only when the user has genuinely moved, a few hundred metres. It uses cell towers and wifi rather than GPS, at a tiny fraction of the power.
    • The goal on this path is to make the write count smaller, not to serve a large count faster.
  • Only write when the CELL changes, which the client can decide for itself. Moving within a cell changes nothing in the index, so the write is pure waste.
  • Age out users who stop appearing. Someone dormant for thirty days is removed from the index, which keeps the ghost problem from quietly widening everyone's radius. A stale index is worse than a small one.
  • Accept a sudden 3,000 km jump, but flag it to the safety systems, because the user may be spoofing rather than on a plane.
TRIGGER: "can someone find where I live" / "is distance safe"

4) Trilateration, and why jitter is not the answer

THREE QUERIES IS AN ADDRESS · SNAP BEFORE MEASURING · DETERMINISTIC, NEVER RANDOM
Bad Solution: return the exact distance
  • "1.2 km away" is friendly and precise.
    • Spoof your GPS to position A and read the distance. Move to B, read again. Then C. Three circles intersect at one point, and that point is a home address.
    • This is not hypothetical: it has been demonstrated against real dating apps more than once, and the fix each time was to stop returning precision.
    • Returning coordinates directly is the same bug with fewer steps, and it has shipped too, usually in an API response the client never displayed.
Good Solution: round the distance, or add noise
  • Round to the nearest kilometre, or add a small random offset. Both feel like they should work.
    • Rounding alone still leaks: sample from many positions and the boundaries where the rounded value flips trace out the true circle.
    • Random noise is worse, because it is defeated by repetition. Query fifty times, take the mean, and the noise cancels while the signal stays.
    • The flaw in both is the same: the attacker controls the number of samples, so anything that varies per query averages out.
Great Solution: quantize the position deterministically, before you measure
  • Snap both users' stored coordinates to their grid cell centres and compute the distance from those centres. The output is now a property of the cell pair, not of the true positions.
  • Determinism is the whole point: the same pair always produces the same answer, so repeated sampling reveals nothing new. Averaging has nothing to average.
  • Report a distance bucket such as "under 2 km", not a number, and widen the buckets with distance. Close up, one-kilometre steps; far away, ten-kilometre steps, because far-away precision has no product value and identical privacy cost.
  • Make the distance field a string in the API type, so no client, analytics event or debug endpoint can leak a float later. That makes it structural rather than a rule people remember. Strip EXIF from photos for the same reason.
  • Do not sort the deck by true distance, because the ORDER re-encodes the precision you just removed. Sort within a bucket by something else.
  • Say what it costs. The product is slightly worse, the safety property is worth it, and there is a floor below which you should simply refuse to be precise regardless of what the design team wants.
Exact distance is a coordinate: giving distance without giving away location An attacker spoofs three positions, reads a precise distance from each, and the three circles meet at the victim's home. The fix: DistanceService snaps both users to their 1 km cell centres before measuring and returns a distance bucket, so more queries return the same three numbers. Random jitter does not help, and no endpoint returns another user's coordinates. Exact distance is a coordinate: giving distance without giving away location this is a real, documented attack on real dating apps, not a theoretical one. spoof your own position three times, read the distance each time, intersect the circles. A reads 1.200 km B reads 1.602 km C reads 2.101 km the victim's home address the attack, in three requests: - move to A, ask for the distance: 1.200 km- move to B, ask again: 1.602 km- move to C, ask again: 2.101 km three circles, one intersection. two circles already narrow it to two points.the third picks one of them.a fourth would just be a free check. what the API returns today GET /v1/deck{ "userId": "u_8812","distance": 1.2 } the attacker never needs the app to tell them aposition. they only need it to be honest about adistance, and to let them choose their own. the three spoofed requests A 40.75623, -73.99175 -> 1.200 kmB 40.75825, -73.96444 -> 1.602 kmC 40.73120, -73.97783 -> 2.101 kmfive decimal places is about one metre. 1 km the picture above is drawn to this scale. distance alone, reported precisely enough, IS a location. three queries is all it takes. the fix: quantize the INPUT, not the output about 1 km2 of ambiguity, and it does not shrink with more queries A 2 - 3 km B 3 - 4 km C 4 - 5 km each cell is 1 km across. the dot in the middle of the cell isits centre; the red dot is the real person. the attacker comes back with threefresh spoofed positions: every position inside one cell reportsthe same distance to every other cell.more queries return the same threenumbers, so they add no information. distance buckets widen as they grow: 0 10 20 60 km 1 km steps up close, 10 km steps far away. DistanceService snaps to the grid BEFORE it measuresthe same pair always yields the same bucket what the API returns after the fix GET /v1/deck{ "userId": "u_8812","distance": "under 2 km" } Random jitter does NOT fix this. Query fiftytimes and average the noise away. Thequantization has to be deterministic. No endpoint ever returns another user'slatitude and longitude. Not to the client,not in an analytics event, not in a debugfield. 1 2 1 DistanceService snaps both stored coordinates to theircell centres before it computes anything 2 DistanceService returns a bucket, never a number withmetres in it the not-so-happy paths: - the product cost is real: 'under 2 km' is a worse experience than '1.2 km'. it is the right trade and you should say so out loud.- distance buckets widen as they grow: 1 km steps up close, 10 km steps far away, because precision far away has no product value and the same privacy cost.
TRIGGER: "what happens on a swipe" / "how does the deck stay fresh"

5) The deck, and why swiping is free

PRECOMPUTE ON OPEN · SWIPES NEVER QUERY GEO · THE EXCLUSION SET IS THE REAL PROBLEM
Bad Solution: query on every swipe
  • Fetch the next candidate when the user swipes.
    • 11,500 swipes a second becomes 11,500 spatial queries a second, ten times the deck rate, for a result that has not changed since the last one.
    • It also puts a network round trip in the animation, which is the one place in this product where latency is actually felt.
Good Solution: page the results
  • Fetch twenty at a time and refill in the background. Right instinct, and it fixes the animation.
    • The refill still lands mid-session, so a heavy swiper generates a steady stream of spatial queries anyway.
    • And paging over a set that is changing underneath you repeats and skips people unless the cursor is stable.
Great Solution: build a deck, then forget geo exists
  • Build about a hundred candidates when the app opens and cache the list with a 30 minute TTL. Every swipe reads from it, so the swipe path has no spatial work in it at all.
  • 11,500 swipes a second collapse onto 1,200 deck builds a second, which is why the rate asymmetry matters: the expensive thing now happens an order of magnitude less often than the cheap thing.
  • The exclusion set of users already seen is the part that is genuinely hard, and a compressed bitmap is the structure for it.
    • It only grows, it is consulted on every build, and a heavy user has tens of thousands of entries.
    • A compressed bitmap of user ids keeps it to kilobytes and turns the check into a fast intersection rather than tens of thousands of lookups.
    • A Bloom filter is the tempting alternative and is the wrong trade here: a false positive silently hides a real person forever, and the user can never discover it.
  • Rebuild when the deck runs low, the TTL expires, the user changes their filters, or they move to a new cell. Those are the triggers that actually matter. Not on a timer.
  • Accept that the deck is a snapshot. Someone may go offline, change their preferences or swipe you first while they sit in your cached deck. None of that is a correctness problem, and pretending it is leads to a much more expensive design for no product gain.

Three more dives, briefly

  • Travel mode, where the user sets a location explicitly, breaks the assumption that location follows the device.
    • An explicitly set location is just another cell write, so the index does not care. What changes is that lastSeenAt and the cell no longer agree with the device, so any safety heuristic built on "did they teleport" has to know the difference.
    • It also has to expire, or a user is discoverable in a city they left months ago.
    • The interesting consequence: a user can be in two markets' decks in one day, which matters for anything that reasons about a local population.
  • Naive geo breaks at borders, oceans and the antimeridian, where longitude wraps at 180 degrees.
    • A user in a border city has half their candidate population in another country, another language and another legal regime. The index does not care and the product very much does.
    • Longitude wraps at 180 degrees, so a circle spanning it becomes two ranges. Cell-based indexes handle this natively, which is one more reason not to hand-roll bounding boxes.
    • Distance on a sphere is not distance on a plane. At dating distances the error is small, but the poles and the wrap are where the flat approximation stops being harmless.
  • Live location would remove the staleness budget, and with it most of what makes this design cheap. It is the question that reframes everything.
    • A "who is here right now" feature removes the staleness budget, and with it the lossy write path, the cached deck and most of the reason this design is cheap.
    • That is the honest answer to why this looks nothing like a ride-hailing system: not because the geometry is different, but because the freshness requirement is.
    • It also raises the safety stakes sharply, since real-time presence is a much more dangerous signal than an approximate distance.
DONE WHEN: you have opened two or three dives properly, and the staleness budget has been used as a REASON at least twice rather than restated as a fact.
FLASHCARDS · THE FIVE HARDEST PROBESshow all (interview mode)
Two users are 40 metres apart on opposite sides of a cell boundary. What happens?
  • With a naive prefix match, nothing: they share no cell prefix, so neither ever appears in the other's deck.
  • This is the single most common defect in this design, and it is invisible in testing because test users are never 40 metres apart across a line.
  • The fix is to always query the eight neighbouring cells as well as the centre one, so the covering set is a superset of the circle.
  • Then filter exactly with haversine on the few hundred candidates, which is microseconds, so the index only ever has to be a good superset.
  • Hexagonal cells reduce the corner cases because all six neighbours are equidistant, which is a real reason to prefer H3 over a square grid.
Manhattan and rural Montana, same query. What breaks?
  • Density spans four orders of magnitude: about 28,000 people per square kilometre against about 1.8.
  • A 5 km circle is 78 square kilometres either way, so it holds about 2.2M people in one and about 140 in the other.
  • So a fixed radius returns tens of thousands of candidates you throw away, or an empty product. Both are failures of the same parameter.
  • Query for a target count of a few hundred instead, and step out one cell level at a time until it is met. Each level is roughly 4x the area.
  • Manhattan is done at the first level, about 380 candidates in a square kilometre. Montana needs roughly 12,000 square kilometres for 300, so six or seven levels and a radius near 60 km. Same loop, very different answer.
  • Store an estimated density per cell so the common case starts at the right level rather than walking to it.
  • Cap the expansion, and past the cap say "nobody nearby" rather than presenting someone three states away as local.
How does a stalker turn "1.2 km away" into a home address, and how do you stop it?
  • Spoof your own position three times, read the distance each time, and intersect the three circles. They meet at one point.
  • Three queries is all it takes, and it has been demonstrated against real dating apps more than once.
  • Rounding alone still leaks, because sampling many positions traces out the boundary where the rounded value flips.
  • Random jitter is worse: the attacker controls the sample count, so averaging fifty queries cancels the noise and leaves the signal.
  • The fix is deterministic quantization BEFORE measuring: snap both users to a cell centre, compute from there, so the same pair always returns the same answer and repetition reveals nothing.
  • Report a bucket as a string, widen buckets with distance, never return lat/lon from any endpoint, and do not sort the deck by true distance, because the ordering re-encodes what you just removed.
How often does the phone report its location, and what happens if you get that wrong?
  • Only on significant change, and only when the cell actually changes. Moving within a cell changes nothing in the index, so that write is pure waste.
  • Get it wrong in the expensive direction and a 1 Hz GPS loop on 10M devices is 10M writes a second and a battery the user can feel draining. They uninstall before the index notices.
  • Get it wrong in the cheap direction and only-on-foreground misses the commute across town, which is exactly the movement that matters.
  • The budget being spent is staleness: fifteen minutes of lag is invisible to a dating product, and that is what makes the write path lossy, unordered and cheap.
  • Age out anyone dormant for thirty days, or ghosts quietly widen everyone's radius while never replying.
A user swipes 100 times in two minutes. How many spatial queries is that?
  • Zero. The deck of about a hundred candidates was built when the app opened and cached with a TTL.
  • That is the whole reason the rates are shaped the way they are: 11,500 swipes a second collapse onto about 1,200 deck builds a second.
  • Querying per swipe would put a network round trip inside the animation, which is the one place in this product where latency is actually felt.
  • The deck rebuilds on real triggers: running low, TTL expiry, a filter change, or moving far enough to change cells. Never on a timer.
  • The genuinely hard part is the exclusion set of already-seen users: it only grows, so use a compressed bitmap, and not a Bloom filter, because a false positive hides a real person forever and nobody can discover it.
  • The deck is a snapshot and that is fine: someone going offline or changing filters mid-deck is not a correctness problem.
STEP 5 OF 5

Final design + what is expected at each level

wrap

Final Design

Dating app geolocation: cheap writes, over-fetching reads, and a distance you cannot triangulate Ingest: MobileClient sends a fix only when the OS says the user moved, and LocationService answers 204, moves the user between cells in GeoIndex and writes UserState. Index: AgeOutJob removes dormant users, and CellCover reads every user in the covering cells. Deck: DeckBuilder asks CellCover for cells, has DistanceFilter trim the candidates, steps out a level when short, removes ExclusionSet users and caches the deck that SwipeService serves. Safety: DistanceService snaps both users to a grid and the card carries only a DistanceBucket. Dating app geolocation: cheap writes, over-fetching reads, and a distance you cannot triangulate 10M daily users. 2,300 location writes a second, 1,200 deck builds a second, 11,500 swipes a second that never touch geo at all. INGEST make the write rate smaller, not faster INDEX cells, not radii DECK the only expensive read SAFETY the number that can locate someone MobileClient significant-change API,not a GPS loop LocationService fire and forget, 204nothing reads its own write UserState latest fix: lat, lon, cellId,lastSeenAt, discoverable 1. MobileClient sends a fixonly when the OS says theuser moved into a new cell overwrites the latest fix nothing here reads before it writes:no compare, no version, no order. Adropped fix is within the 15 min budget. what one location write carries: POST /v1/location{ "lat": 49.2827, "lon": -123.1207, "accuracy": 20 } only the latest fix is kept, overwritten on everywrite, and the coordinate never leaves the server. GeoIndex cellId -> set of userIdssharded by cell prefix AgeOutJob drops users not seenin 30 daysa stale index is worsethan a small one CellCover circle to cell ids,plus the 8 neighbours 2. LocationServiceanswers 204 and movesthe user between cells 3. AgeOutJob removes userswho stopped opening the app 6. CellCover readsevery user sittingin those cells the dot is one user, the circle isthe radius they asked for.CellCover turns that circle into9 cell ids;GeoIndex is read whole,then DistanceFilter trims. DeckBuilder targets ~300 candidatessteps out a cell level when short DistanceFilter exact haversine on thestored lat and lon ExclusionSet already swiped or blockedroaring bitmap per user DeckCache about 100 candidates, 30 min TTL SwipeService 11,500/sec, reads the cached decknever queries geo 4. MobileClient asksfor a deck when the appopens, about 1,200times a second 5. DeckBuilder asks CellCover whichcells cover the user's radius about 300 candidatesfrom the cells 8. DistanceFilter measuresthe candidates exactly anddrops the ones outsidethe circle 9. DeckBuilderremoves everyone theuser has alreadyswiped 7. DeckBuilder stepsout one cell level whenthe count comes backshort 10. DeckBuilder cachesthe deck so the nexthundred swipes costnothing 11. SwipeService servesswipes straight fromthe cache the read budget: 1,200 deck builds/sec x ~300 candidates = 360K rows/sec scanned,11,500 swipes/sec x 0 geo reads = the swipe path is free. DistanceService snaps to the grid BEFORE measuringdeterministic, never jittered DistanceBucket 'under 2 km', never '1.2 km' NoRawCoordinates no endpoint returns another user's lat/lonnot in debug, not in analytics snaps both stored fixesto cell centres first 12. DistanceService snaps bothusers to a grid before itreports any distance leaves the bucket as the onlygeo field on the wire the card shows the bucket,never the number what a profile card carries: { "userId": 4471, "distance": "under 2 km" }never: { "lat": 49.28, "lon": -123.12 } A location 15 minutes old is fine, which is what makes the write path lossy, unordered and cheap. The deck is the only readthat costs anything, and it is cached before the swiping starts.Exact distance is a coordinate: three spoofed positions and three precise distances locate a home address, so the grid snapis a safety control and not a rounding convenience.
  • The client sends a fix only when the OS reports real movement, and only when that movement crosses a cell, so the write count is small by construction rather than by throttling.
  • The location service answers 204, moves the user between cells, stamps lastSeenAt, and keeps no coordinate history.
  • The index is cell id to a set of user ids, under a gigabyte for 10M users, sharded by cell prefix with read replicas on the dense shards.
  • A deck build covers the circle with cells including the eight neighbours, steps out a level when the count is short, filters exactly by haversine, removes the already-seen bitmap, and caches about a hundred candidates.
  • Swipes read the cached deck, so the highest-rate operation in the product does no spatial work at all.
  • Every distance is computed from grid-snapped positions and returned as a bucketed string, and no endpoint returns another user's coordinates.
  • The invariant worth closing on: a location fifteen minutes old is good enough, and that single tolerance is what pays for the cheap write path, the cached deck and the coarse index. The two things it does not pay for are density and safety, which are the two dives worth having.

What is Expected at Each Level

  • Mid:
    • Reaches a geohash or Redis GEO index and a query by radius, which is a working answer.
    • Separates the location write from the candidate read.
    • Usually misses the neighbour-cell boundary bug entirely.
    • Usually treats distance as a display detail rather than a safety property.
  • Senior:
    • Handles the boundary correctly and filters exactly after over-fetching.
    • Notices the density problem and adapts the radius or the cell level to it.
    • Caches the deck so the swipe path does no spatial work, and can say why that ratio matters.
    • Throttles location updates deliberately and can defend the interval.
    • Rounds the distance rather than returning it exactly, though may not see that rounding and random noise both still leak to repeated queries.
  • Staff:
    • Leads with the staleness tolerance and uses it as the reason for at least three separate decisions rather than mentioning it once.
    • Reframes the query from a radius to a target count, and knows the cell level is the lever rather than the circle.
    • Raises trilateration unprompted, and knows why jitter fails where deterministic quantization works.
    • Catches the second-order leak: sorting the deck by true distance re-encodes the precision that bucketing removed.
    • Picks the exclusion-set structure on the right grounds, rejecting a Bloom filter because a false positive is invisible and permanent.
    • Names what the design does not do: the deck is a stale snapshot, ghosts need ageing out, and a live-presence feature would invalidate most of the cheapness.
DONE WHEN: you can point at the final diagram and say, in one breath, fifteen minutes stale is fine, cells not radii, always the neighbours, target a count not a distance, and snap before you measure.