Learn

Architecture & pattern guides

Read the idea, build it on a Grid, prove it in a challenge. Short, practical guides — illustrated with RodGrid's own nodes — on system design, design patterns, flow modeling, and how to get the most out of the app.

All articles

Geospatial indexing & proximity search

"What's near me?" needs a spatial index: cells such as geohash, S2 or H3 turn a 2D radius into a few 1D lookups. Why one cell is never enough, how moving objects change cells, and what to do when one cell gets crowded.

A box on the map that the index cannot see

WHERE lat BETWEEN 38.7112 AND 38.7166 AND lng BETWEEN -9.1429 AND -9.1359, with an index on (lat, lng), is the query almost everyone writes first for "scooters within 300 metres of me". Here it belongs to a scooter-sharing app in Lisbon: the box goes around the phone that asks, and the haversine formula trims it to a circle. In the pilot, with a few hundred scooters, nobody notices. As the fleet grows into thousands, the query slows down, though the answer is still a dozen scooters.

The index explains why. A B-tree on (lat, lng) sorts by latitude first, so it jumps straight to the rows in the right latitude range, but within that range the longitudes are in no useful order. It reads every scooter in a strip 600 metres tall that crosses the whole city and, in fact, circles the planet, and throws almost all of them away. Two separate indexes help little: one returns that east-west strip, the other a north-south one, and the database intersects two large sets to find a small one.

"Within 300 metres" constrains latitude and longitude together, and a spatial index is built for that. The approach this article follows cuts the map into cells and gives each cell a name that sorts, so finding what is near becomes looking up a few cells. (A database with a spatial index type, PostGIS for example, can answer the radius query directly with a tree over rectangles; cells are what work on a key-value store and spread across shards.)

Names that get longer as cells get smaller

Geohash is the classic scheme. Halve the world's longitude range and write 0 for the west half or 1 for the east; halve the latitude range and write 0 for south or 1 for north; keep alternating, each bit halving the cell again, and spell every five bits as one base-32 character. Lisbon's old centre lies in the cell eycs0p. In Lisbon a six-character cell is about 950 metres east to west by 600 metres north to south.

A longer name is a smaller cell inside the shorter one. Store each scooter, with its coordinates, under its geohash followed by its ID in an ordered key space and one range scan over the prefix eycs0p returns every scooter in that cell. Points close to each other usually share a long prefix, and that word decides the next section.

The scooter fifty metres away

Near Rossio square, two scooters fifty metres apart sit on either side of a cell edge: one in eycs0p, the other in eyckpz. They share three characters out of six. At the biggest edges, the equator or the prime meridian, two points a metre apart share none. A user standing near the edge of a cell has scooters a few steps away in the next cell, and a query that reads only the user's own cell does not see them.

So a radius query does not stop at the user's own cell. It picks a precision whose cells are at least as large as the radius in both directions, six characters for 300 metres in Lisbon, and reads the user's cell plus its eight neighbours. Every scooter within the radius is then somewhere in that 3 × 3 block. The block also holds scooters well beyond 300 metres, in its corners and along its sides, so the last step computes the real distance for each candidate and drops the rest. Bigger cells mean fewer lookups and more candidates to discard; smaller cells, more lookups for the same circle.

Nearby query via cell lookup

The proximity service reads nine cells and filters by real distance; the location service moves scooters between cells as their reports arrive.

Scooters do not stay in their cells

A scooter being ridden reports its position every few seconds. Each report is a write to the cell → members store, often Redis held in memory, not a new database row: within the same cell it updates the entry, and across a cell edge it removes the scooter from the old cell and adds it to the new one. Those two writes belong together, in one transaction or one script, which Redis Cluster allows only when both keys hash to the same slot; where the store cannot update both keys atomically, for a moment the scooter can be in neither cell, or in both, and the query drops duplicate IDs.

A scooter whose battery dies stops reporting, so its entry needs a way out: an expiry, or a last-seen time that queries filter on, the heartbeat-and-TTL idea from Presence & ephemeral state. Redis also has a built-in geo type, a sorted set scored by geohash with radius search on top, and its members cannot expire one by one, so stale scooters still need the last-seen filter. And keep the raw pings out of the main database: location updates are a firehose (High-write ingestion), and only the history someone needs is persisted, in batches, to storage built for it.

Match night at the stadium

When a football match ends at the Estádio da Luz, tens of thousands of people query the same few cells, and every read and every scooter's update lands on the keys of whichever shard holds them. Splitting the hot cell into finer cells, or spreading one cell's members over several keys that a query reads together, spreads its updates and data over more keys, which helps once those keys sit on different shards; each query still reads most of them, so the read side is a hot-key problem like any other, handled in Sharding & partitioning.

Cells that suit the whole planet

One precision does not suit every place either: the cell that holds twenty scooters downtown holds none at the edge of the city. Geohash cells are also rectangles in degrees, so they get narrower toward the poles, and a cell's eight neighbours are not all the same distance from its centre. Hierarchical cells keep the idea of named cells at many sizes, with better geometry, though each scheme has its own cell IDs rather than a text prefix. S2, from Google, divides the sphere into square-ish cells, four children to each parent. H3, from Uber, covers the planet with hexagons (plus twelve pentagons at each resolution), and a hexagon's six neighbours all sit at about the same distance from its centre, so "the ring around me" is one clean step. Both work at many resolutions, so a dense downtown can use small cells and the outskirts large ones. All of it measures straight-line nearness; distance along real roads is Route planning on road graphs.

Where the lookup gets tested

The Nearby Places Challenge is the radius search at a high read rate, and two parts of the design decide it: the edge that reads a cell and its neighbours before filtering by real distance, and the path that keeps the cells current when a place opens, closes or moves. Nearby Friends keeps the moving-object half and narrows it to friends: positions fan out over per-friend channels into a location store with TTLs, so the radius check runs against each friend's last position and no cell sweep over everyone is needed.

Practice this