--- title: 'Location-Based Service' source: 'https://academia.sh/en/courses/case-studies/location-based-service' course: 'Case Studies' language: en updated: '2026-08-23T07:01:24+00:00' license: 'CC BY-SA 4.0' --- # Location-Based Service The case of a query with no sortable key: comparing the proximity query against a flat scan, measuring on real data the candidate count a geohash scans, choosing cell size from the trade-off between candidate count and index lookups, and counting the results missed when a neighboring cell is not queried. In the previous case, finding a record was easy: given a series ID and a time range, the rows to read sat in one place, in order. This case removes that convenience. Records sit on a two-dimensional plane, and the question comes in the form "the ones near this point." Proximity has no sortable key: every way of sorting two dimensions along a single axis pushes some neighbors far apart, because two points that are adjacent on one axis can be far apart on the plane, and two points that are neighbors on the plane can be far apart on the axis. The solution is to divide the plane into cells and write a **geohash** into every record: records in the same cell carry the same key, and a **proximity query** scans the cells first, then the candidates inside each cell. The decision to be measured is cell size, and it carries a two-way trade-off: as the cell grows, the scanned candidate count rises; as the cell shrinks, the number of cells that must be queried rises. ## Constraints Functional requirement: registering a place, updating a moving object's location, returning the places within a given radius of a given point, and sorting the result by distance. Non-functional requirement, with numbers: the proximity query returns **all** records within the radius, the miss rate is **zero**; candidates scanned per query do not exceed **1000**; the design carries a peak of **1666.67** queries/s and **24,000** location updates/s. Scope narrowing: route finding, estimated time of arrival, map rendering, place ranking, and geographic projection transforms are not designed; because the region is small in this case, a planar approximation is used, and this is a model simplification. ## Assumptions | Code | Assumption | Value | Rationale | |---|---|---|---| | KT1 | registered place | 40,000,000 | total points in the service area | | KT2 | daily active user | 6,000,000 | those making proximity queries | | KT3 | queries per user per day | 8 | search and map navigation | | KT4 | peak multiplier | 3 | ratio of peak hour to daily average | | KT5 | place record | 320 bytes | name, location, category, hours | | KT6 | moving object | 120,000 | carriers whose location changes continuously | | KT7 | location update interval | 15 s | the carrier's report frequency | | KT8 | density in a residential area | 20 places/km² | the model region's average | | KT9 | cost of one cell search | 20 candidates | ratio of an index lookup to a row scan | | KT10 | proximity radius | 1 km | walking-distance query | KT9 is this case's decision-driving assumption: choosing cell size depends on how many row scans one index lookup is worth, and this ratio varies by storage engine. ## Scale ```js // location/scale.mjs — scale calculation derived from the KT table; all of it is arithmetic const KT = { place: 40_000_000, user: 6_000_000, query: 8, peak: 3, placeBytes: 320, moving: 120_000, updateS: 15, density: 20, radiusKm: 1, candidateBudget: 1000 }; const DAY = 86_400; const queryS = (KT.user * KT.query) / DAY; const updateS = KT.moving / KT.updateS; for (const [name, d] of [ ["peak proximity queries/s", queryS * KT.peak], ["peak location updates/s", updateS * KT.peak], ["update / query ratio", updateS / queryS], ["place data GB", (KT.place * KT.placeBytes) / 1e9], ["radius area km2", Math.PI * KT.radiusKm ** 2], ["expected places in area", Math.PI * KT.radiusKm ** 2 * KT.density], ]) console.log(name.padEnd(26) + d.toFixed(2).padStart(14)); const flat = queryS * KT.peak * KT.place; console.log(`\nflat scan: ${KT.place.toLocaleString("en-US")} records per query -> at peak ` + `${flat.toExponential(2)} records/s`); console.log(`with a candidate budget of ${KT.candidateBudget}, peak is ${(queryS * KT.peak * KT.candidateBudget) .toLocaleString("en-US", { maximumFractionDigits: 0 })} records/s (1/${KT.place / KT.candidateBudget} of a flat scan)`); ``` ``` peak proximity queries/s 1666.67 peak location updates/s 24000.00 update / query ratio 14.40 place data GB 12.80 radius area km2 3.14 expected places in area 62.83 flat scan: 40,000,000 records per query -> at peak 6.67e+10 records/s with a candidate budget of 1000, peak is 1,666,667 records/s (1/40000 of a flat scan) ``` These numbers are in the **calculation** class, and three of them determine the design. First, data volume is small in this case: 40,000,000 place records take up 12.80 GB, nothing next to the terabytes of the previous three cases. The weight here is not in data volume but in the **number of records touched per query**. A flat scan means reading 66.7 billion records per second at peak; if the candidate count is held at 1000, the same load drops to 1,666,667 records/s, that is, to one forty-thousandth. Second, writes dominate reads: location updates are 14.40 times the queries, at a peak of 24,000/s. Third, a query's real answer is 62.83 records on average; the candidate budget is sixteen times that number, meaning the design accepts a degree of waste from the outset. ## Candidate Count Cell size can only be defended against a real distribution, because points do not spread uniformly. The model below places 200,000 clustered points on a 100 × 100 km plane, writes the geohash into an index for five cell sizes, and asks the same 200 queries of all of them. ```js // location/spatial.mjs — candidate count scanned by a spatial key on real data via node:sqlite. // The region is modeled as a 100x100 km plane (a planar approximation for a small region); the // points are clustered, the generator is hand-written, and the seed is visible. The model is // written as what it is. import { DatabaseSync } from "node:sqlite"; const N = 200_000, EDGE = 100, R = 1, QUERIES = 200, SEED = 20260802, CLUSTERS = 20, SEARCH = 20; const CELL = [0.5, 1, 2, 4, 8]; // cell edge length, km let state = SEED; const rand = () => { state = (state * 1103515245 + 12345) % 2147483648; return state / 2147483648; }; const center = Array.from({ length: CLUSTERS }, () => [rand() * EDGE, rand() * EDGE]); function point() { // 60% around a cluster, 40% uniform if (rand() < 0.4) return [rand() * EDGE, rand() * EDGE]; const [mx, my] = center[Math.floor(rand() * CLUSTERS)]; const a = rand() * 2 * Math.PI, d = -Math.log(1 - rand()) * 3; return [Math.min(EDGE, Math.max(0, mx + d * Math.cos(a))), Math.min(EDGE, Math.max(0, my + d * Math.sin(a)))]; } const code = (x, y, c) => Math.floor(y / c) * 10_000 + Math.floor(x / c); const db = new DatabaseSync(":memory:"); db.exec(`CREATE TABLE place(id INTEGER PRIMARY KEY, x REAL, y REAL, ${CELL.map((_, i) => `h${i} INTEGER`).join(", ")}); ${CELL.map((_, i) => `CREATE INDEX place_h${i} ON place(h${i});`).join("\n")}`); db.exec("BEGIN"); const insert = db.prepare(`INSERT INTO place VALUES(?,?,?,${CELL.map(() => "?").join(",")})`); const points = []; for (let i = 0; i < N; i += 1) { const [x, y] = point(); points.push([x, y]); insert.run(i, x, y, ...CELL.map((c) => code(x, y, c))); } db.exec("COMMIT"); const queries = Array.from({ length: QUERIES }, point); const near = (q, x, y) => (x - q[0]) ** 2 + (y - q[1]) ** 2 <= R * R; let flatMatched = 0; // flat scan: the measure of correctness for (const q of queries) flatMatched += points.filter(([x, y]) => near(q, x, y)).length; console.log(`model: ${N} places, ${EDGE}x${EDGE} km, ${CLUSTERS} clusters, radius ${R} km, ` + `${QUERIES} queries, seed ${SEED}`); console.log(`flat scan: ${N} candidates per query, ${(flatMatched / QUERIES).toFixed(2)} matches\n`); console.log("cell km".padEnd(10) + "queried".padStart(12) + "candidates".padStart(12) + "hit rate".padStart(10) + "equivalent work".padStart(17) + "own cell".padStart(15) + "missed".padStart(11)); const WORK = {}; for (const c of CELL) { const i = CELL.indexOf(c), k = Math.ceil(R / c); let candidates = 0, matched = 0, cells = 0, own = 0; for (const q of queries) { const cx = Math.floor(q[0] / c), cy = Math.floor(q[1] / c), list = []; for (let dy = -k; dy <= k; dy += 1) for (let dx = -k; dx <= k; dx += 1) list.push((cy + dy) * 10_000 + cx + dx); cells += list.length; const s = db.prepare(`SELECT x, y FROM place WHERE h${i} IN (${list.map(() => "?").join(",")})`).all(...list); candidates += s.length; for (const r of s) if (near(q, r.x, r.y)) { matched += 1; if (Math.floor(r.y / c) === cy && Math.floor(r.x / c) === cx) own += 1; } } WORK[c] = [candidates / QUERIES, cells / QUERIES]; console.log(`${c}`.padEnd(10) + (cells / QUERIES).toFixed(0).padStart(12) + (candidates / QUERIES).toFixed(0).padStart(12) + `${((matched / candidates) * 100).toFixed(1)}%`.padStart(10) + (candidates / QUERIES + (cells / QUERIES) * SEARCH).toFixed(0).padStart(17) + (own / QUERIES).toFixed(2).padStart(15) + `${(((matched - own) / matched) * 100).toFixed(1)}%`.padStart(11)); } console.log(`\nmatch count is the same as the flat scan at every cell size (${(flatMatched / QUERIES).toFixed(2)}): ` + `neighboring cells are queried, so nothing is missed`); console.log(`equivalent work = candidates + queried cells x ${SEARCH} (KT9: the cost of one cell search)`); const [a1, h1] = WORK[0.5], [a2, h2] = WORK[1]; console.log(`point where 0.5 km and 1 km break even: one cell search = ${((a2 - a1) / (h1 - h2)).toFixed(2)} ` + `candidate scans; below this 0.5 km wins, above it 1 km wins`); ``` ``` model: 200000 places, 100x100 km, 20 clusters, radius 1 km, 200 queries, seed 20260802 flat scan: 200000 candidates per query, 443.95 matches cell km queried candidates hit rate equivalent work own cell missed 0.5 25 700 63.4% 1200 105.33 76.3% 1 9 864 51.4% 1044 181.41 59.1% 2 9 2123 20.9% 2303 322.27 27.4% 4 9 5251 8.5% 5431 381.24 14.1% 8 9 13611 3.3% 13791 415.85 6.3% match count is the same as the flat scan at every cell size (443.95): neighboring cells are queried, so nothing is missed equivalent work = candidates + queried cells x 20 (KT9: the cost of one cell search) point where 0.5 km and 1 km break even: one cell search = 10.25 candidate scans; below this 0.5 km wins, above it 1 km wins ``` These numbers are in the **measurement** class; the values depend on this run's seed and clustering parameters, the trend across columns does not. Because the model is clustered, 443.95 matches come out per query — seven times the 62.83 from the scale calculation, since queries are drawn from the same distribution as the points and cluster in dense regions. Three things follow. First, **the index does not break correctness:** match count equals the flat scan at every cell size, 443.95 — the geohash is a pre-filter, not an approximation; exact distance is computed separately for every candidate. Second, **the hit rate collapses with cell size:** 63.4 percent of scanned candidates are real matches at 0.5 km, only 3.3 percent at 8 km. The eight-kilometer cell scans 13,611 candidates; the 1000-candidate limit eliminates 2 km and above outright. Third, the shape of the trade-off: as the cell shrinks, candidates fall but queried cells rise — 25 cells and 700 candidates at 0.5 km, 9 cells and 864 candidates at 1 km. At KT9's ratio, equivalent work is 1200 versus 1044, and **1 km wins**. The break-even point can be written down too: the two sizes tie exactly when one cell search is worth 10.25 candidate scans — cheaper than that, 0.5 km wins; more expensive, 1 km does. The decision is a property of the storage engine, not of geography. ## Design The geohash is written into the record by **denormalization** (the Scaling the Data Layer course's Data Distribution topic) and an **index** is placed on it (the Databases curriculum's Relational Database Administration course, Index Types); together the two form the **spatial index**. The mechanics were established there — the only thing chosen here is the key's grain, 1 km. A category filter puts the key in a **composite index** instead (the same course, Composite and Partial Indexes): order (cell, category), since the cell is given by equality every query. The **sharding** key is not the geohash itself but its hash (the Data Distribution topic, Sharding). Sharding by the geohash directly would put every cell of a dense region on the same shard, turning the model's clustering straight into a hot shard; hash sharding spreads a query's 9 cells across different shards as nine parallel lookups — a latency cost paid because the peak 1666.67 queries must not pile up on one shard. A moving object's location lives in a separate **key–value store** (the same topic, Store Types): the key is the object ID, the value is the last location and cell. The 24,000 updates/s never touch the place table, since place records almost never change and sharing an index between the two workloads would tie its maintenance to the update rate. A place query's cell result is cached with **cache-aside** (the Cache Architecture topic); the staleness window is safe because places do not change, and moving objects never enter the cache. **Deliberately unused pattern: the materialized view.** Precomputing each cell's candidate list with its neighbors would reduce a query to one read, but every record would then appear in nine cells; the moving objects' 8000 updates/s become 72,000 writes, tripling the peak write rate for a gain of one index lookup. The second is the **claim check pattern** (the Resilience and Reliability course's Distributed Correctness topic): even in the worst case, the response body — 1000 filtered candidates at 320 bytes each — stays under a hundred kilobytes, so storing it and returning a claim check would only add a round trip. ## Eliminated Alternatives **Flat scan** satisfies the miss-rate limit perfectly with no index maintenance, but reads 40,000,000 records per query and rises to 66.7 billion records/s at peak — forty thousand times the candidate budget. A **coarse cell**, 8 km say, minimizes lookups (9 cells) but scans 13,611 candidates, thirteen times the 1000 limit; even 2 km, at 2123 candidates, is twice over. **Single-cell query** is the third alternative: one lookup instead of nine. The table's last two columns eliminate it: scanning only the query point's own cell at 1 km would find just 181.41 of the 443.95 matches, a **59.1 percent miss rate**. The rate falls as the cell grows (6.3 percent at 8 km) but never reaches zero, because the closer a query point sits to the cell's edge, the further the circle extends outside it. Single-cell query does not satisfy the miss-rate limit at any cell size; scanning the neighboring cells is not an optimization, it is a requirement. **Which limit changes and the alternative wins:** if the miss-rate limit were relaxed to "90 percent of results is enough," single-cell query at the 8 km cell would pass at 93.7 percent, and nine lookups would drop to one. ## Failure Behavior and What Is Given Up When a shard node goes down, some of a query's nine cells go unanswered. Two options exist, and the design picks the second: treat the incomplete answer as an error, or answer with the available cells and mark the result partial. The second is **graceful degradation** (the Resilience and Reliability course's Fault Isolation topic): its cost is measured — a missing cell violates the zero miss-rate limit, but a one-in-nine incomplete scan is far smaller than single-cell query's 59.1 percent miss rate. When the cache goes down, load lands directly on the index and the peak 1666.67 queries reach the store in full; this is why the candidate budget is set against peak rate, not response size. **What is given up:** 864 candidates are scanned per query, while the real answer is 443.95 records — a 51.4 percent hit rate, and the design accepts a scan that is roughly half wasted on every query. What this waste buys is a miss rate that stays at zero and a cell size that can be pinned to a single number. ## Summary - In this case volume is small (12.80 GB) but the query is expensive: a flat scan reads 66.7 billion records/s at peak, and a candidate budget of 1000 drops the same load to one forty-thousandth. - The geohash does not break correctness: match count equals a flat scan at every cell size (443.95), since the cell is a pre-filter and exact distance is computed separately for every candidate. - Candidate count grows fast with cell size: 700 at 0.5 km, 864 at 1 km, 13,611 at 8 km; the hit rate falls from 63.4 percent to 3.3 percent, and the 1000-candidate limit eliminates 2 km and above. - A small cell reduces candidates but increases cell count: 0.5 km is 25 cells and 700 candidates, 1 km is 9 cells and 864 candidates; equivalent work is 1200 versus 1044, and the two sizes break even when one cell search is worth 10.25 candidate scans. - Querying neighboring cells is not an optimization but a necessity: scanning only its own cell gives a 59.1 percent miss rate at 1 km, 6.3 percent at 8 km, and it does not reach zero at any size. ## Next Step The four cases in this topic stood on two sides of the same divide. The object storage service and the video service did the work **at write time**: the segment was placed, the bitrate ladder was produced, and reading only picked up what was ready. The metrics system and the location service did part of the work **at query time**: rollup was precomputed, yet the percentile question was answered at read time; the geohash was written in advance, yet the proximity query was rescanned every time. No case took on the two being needed **together in the same system**: if the same data had to be both fully processed in retrospect and answered within seconds of arriving, reconciling the two processing forms' results would be a separate design problem. The next lesson takes on that problem.