Lesson 52: Implementing the Search Loop

Module 4: The Matching Engine (Processor API)

A rider request just landed. You know their lat/lng. Somewhere in RocksDB there are thousands of available drivers. You’re about to iterate. Congratulations — so did the intern who wrote driverStore.all() last quarter, and they just walked 50,000 keys to find the one driver sitting 80 meters away in the same H3 cell.

Two milliseconds later the StreamThread is still in the iterator. The next 200 rider requests sit unprocessed. Your match latency chart is a cliff.

This is the search-loop problem. It’s not an H3 problem. It’s an index-and-expansion problem. And the fix is not a bigger block cache — it’s making sure the loop is already bounded by construction: prefix-keyed cells, ring-by-ring expansion, first hit returns.

Lesson 51 got you an inverted index and a gridDisk(origin, 1) neighborhood scan. That works for a demo. It does not work as a search loop.

gridDisk(k) returns the filled disk: the origin plus every ring out to k. At k=1 that’s 7 cells. At k=3 that’s 37. You pay for the outer rings even when the rider’s own cell already has an idle driver. You also tend to keep scanning after you’ve found someone, because “pick the closest in the whole disk” feels more correct than it is.

At 10 records in a demo, any scan “works.” At 3,000 rider events/sec across an 8-partition topic it decides whether MatchingApp stays under a millisecond or falls over walking RocksDB.

Two riders can wait. One cell can already have a driver. The danger in this lesson is not double-booking that driver (that’s Lesson 54). The danger is searching as if the store were a list.

Here’s what a senior dev who hasn’t run a dispatch search at scale will build:

// ❌ Naive: full-table scan, then pick nearest
DriverState best = null;
double bestDist = Double.MAX_VALUE;
try (var iter = driverStore.all()) {           // O(all drivers)
    while (iter.hasNext()) {
        var driver = DriverState.deserialize(iter.next());
        double d = haversine(rider, driver);
        if (d < bestDist) {
            bestDist = d;
            best = driver;
        }
    }
}
context.forward(new Record<>(riderId, match(best), timestamp));

Two failures are baked in. Both are invisible until load shows up.

Failure 1: all() is not a geo query. RocksDB’s default iterator walks keys in byte order. If your keys are driverId, that order has nothing to do with space. Every rider request touches every driver. At 50,000 active drivers and 250 rider events/sec/partition, you are doing 12.5 million key reads per second of search before you emit a single match.

Failure 2: filled-disk search never fail-fasts. Even with cell keys, dumping gridDisk(riderCell, 3) and scanning every cell equally means a ring-0 hit still pays for rings 1–3:

The TOCTOU of search is the gap between “we already had a candidate” and “we finished the neighborhood.” At 3,000 events/sec, that extra work is your p99.

A third failure shows up the moment someone “fixes” it with Redis GEORADIUS or a PostGIS call from process(): blocking I/O on the StreamThread. That thread is the poll loop. Don’t do it.