Location-Based Service

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

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

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