Lesson 51: The K-Ring Algorithm — Inverted Index Search in RocksDB

A rider opens the app in SoMa, San Francisco. Their GPS resolves to H3 cell 8928308280fffff at resolution 9 (≈105m edge length, ≈0.1 km²). There are zero available drivers in that exact cell right now — the nearest driver is two blocks over, sitting in cell 89283082807ffff. Your matching engine returns nothing. The rider sees a spinner. They close the app.

This is the empty-cell problem, and it is not an edge case. At any given second, the majority of H3 resolution-9 cells in a city are empty. You cannot match on exact cell identity. You need K-Ring search — expand outward ring by ring until you find candidates, then rank by actual distance.

The algorithm is simple. The implementation at 3,000+ events/second is not.

A standard developer, coming from a CRUD background, models the driver state naturally: keyed by driver ID.

KTable<String, DriverLocation>  // key = "driver-uuid-abc123"

When a rider request arrives at H3 cell C, they compute the k=1 ring — 7 cells — then scan the entire KTable to find drivers whose currentCell is in that set:

This is O(N) where N is total active drivers. At 10,000 drivers and 3,000 rider requests/second:

• 30 million comparisons/second on a single StreamThread

• Each driverStore.all() call forces a RocksDB iterator over every SSTable segment

• The process-latency-max metric spikes to 800ms+

• Kafka consumer group falls behind; records-lag-max grows unbounded

• The StreamThread watchdog triggers a rebalance — your topology restarts mid-match

The root cause is a key design mismatch. The natural primary key (driverId) is wrong for your access pattern. You never ask “give me the location of driver X” during matching. You ask “give me all available drivers in cells {C₀, C₁, C₂, C₃, C₄, C₅, C₆}”. Your key structure must answer that question in O(1) prefix reads.