We Finally Made It: How We Stabilized Our Real-Time Driver Matching Engine

Months of engineering, tuning and chasing race conditions, in a few minutes of reading. H3 hexagons, Redis, haversine and atomic locks: everything we learned matching passengers to the nearest driver in a fraction of a second.

10 min read

After months of engineering, tuning and chasing race conditions, our real-time driver matching engine is stable.

If you've never built one, that sentence probably sounds smaller than it is. A passenger taps "Request ride". Somewhere nearby, a dozen drivers are moving through traffic, each phone reporting its position every few seconds. In a fraction of a second, we have to decide which one of them gets the trip, and make sure no other passenger gets that same driver at the same moment.

Finding the nearest available driver in milliseconds is where things get complicated.

Getting here took research papers and late-night whiteboard sessions, implementations we threw away, load tests that fell over, and bugs that only showed up when two requests landed within the same few milliseconds. It took us months. It should take you about ten minutes to read.

So here we are, breaking it down for you. This essay is part of our engineering series, and it's everything we wish someone had told us on day one. If you're building anything that matches people to things that move, our hope is simple: skip the months we spent and start where we ended up.

The biggest lesson first, because it's the one we learned the hard way: finding the nearest driver is the easy part. Matching is a concurrency problem disguised as a search problem.

Why "find the closest driver" breaks

The naive version goes like this. Load every online driver, compute the distance from each one to the passenger, sort, and pick the first.

It works perfectly in a demo with ten drivers. It falls apart in a real city for three reasons.

It doesn't scale. Comparing every request against every driver means work that grows with the size of the fleet, on every single request, at exactly the moments when demand is highest. Rush hour is when you can least afford to be slow.

The world moves while you think. A driver's position is already slightly out of date by the time you read it. A driver who was available when you started the search may have accepted another trip, switched off the app or lost signal by the time you finish.

Two passengers can want the same driver at the same moment. This is the one that hurts. Two requests arrive a few milliseconds apart from neighbouring streets. Both searches see the same driver as the closest available one. Both assign that driver. One passenger gets a ride; the other gets a driver who is never coming.

Our matching engine is built in three layers, one for each of those problems: H3 and Redis to make the search small, haversine to rank what's left, and atomic Redis locks to make sure a driver can only be claimed once.

Layer one: shrinking the world with H3

The fastest search is the one you never have to run. Before we measure any distances, we throw away almost every driver in the city.

To do that, we use H3, the open-source geospatial index created at Uber. H3 covers the entire planet in a grid of hexagons, at sixteen resolutions, from cells the size of countries down to cells smaller than a square metre. Every point on Earth belongs to exactly one hexagon at each resolution, and each hexagon has a short ID.

Every time a driver's phone reports its location, we convert it into an H3 cell and record the driver in a Redis set for that cell. When the driver crosses into a new hexagon, we move them from the old set to the new one. Redis keeps the whole index in memory, so reading it takes microseconds.

When a passenger requests a ride, we don't ask "where are all the drivers?". We ask a much smaller question: "who is in this hexagon, and the ones around it?"

import { latLngToCell, gridDisk } from "h3-js";

// Simplified for this article.
async function findCandidates(lat: number, lng: number, vehicleType: string) {
  const origin = latLngToCell(lat, lng, RESOLUTION);

  // Widen the search one ring of hexagons at a time until we find drivers.
  for (let k = 0; k <= MAX_RINGS; k++) {
    const cells = gridDisk(origin, k);
    const ids = await redis.sunion(
      ...cells.map((cell) => `drivers:${vehicleType}:${cell}`),
    );
    if (ids.length > 0) return ids;
  }

  return [];
}

We search outwards ring by ring. Ring zero is the passenger's own hexagon. Ring one adds the six hexagons around it, ring two the twelve around those, and so on, until we find enough drivers or reach the edge of what counts as "nearby". A request in a busy commercial district usually finds candidates immediately. A request on the edge of town widens until it does.

Why hexagons, and not squares

This is where people usually ask why we didn't use a simple square grid, or a geohash.

A square has two kinds of neighbours: four that share an edge, and four that only touch at a corner and sit noticeably further away. A hexagon has six neighbours, and they're all the same distance from the centre. When you expand a search ring by ring, hexagons grow in something close to a circle, which is what "nearby" actually means. Squares grow in a diamond or a box, with distorted corners.

The more important reason is less mathematical. H3 gives the whole company one vocabulary for space. The same hexagon ID that powers matching also lets us count supply and demand in a neighbourhood, colour the heatmaps in the Twende Simulation Engine, and compare one part of a city with another. A spatial index that only your matching service understands is a missed opportunity.

Redis has built-in geo commands that can answer "who is within 2 km of this point?" directly, and for many products they're the right call. We chose H3 because we wanted the cell, not just the query.

Layer two: ranking with haversine

H3 gives us a short list. Now we need an order.

For each candidate we compute the distance to the passenger using the haversine formula, which calculates the great-circle distance between two points on a sphere from their latitude and longitude:

const EARTH_RADIUS_M = 6_371_000;

function haversine(lat1: number, lng1: number, lat2: number, lng2: number) {
  const toRad = (deg: number) => (deg * Math.PI) / 180;
  const dLat = toRad(lat2 - lat1);
  const dLng = toRad(lng2 - lng1);

  const a =
    Math.sin(dLat / 2) ** 2 +
    Math.cos(toRad(lat1)) * Math.cos(toRad(lat2)) * Math.sin(dLng / 2) ** 2;

  return 2 * EARTH_RADIUS_M * Math.asin(Math.sqrt(a));
}

It's cheap, it's predictable, and on a short list it runs in a blink.

Haversine is wrong, and we use it anyway

We want to be honest about this, because it's the kind of shortcut engineering articles often gloss over.

Haversine measures distance as the crow flies, and passengers don't travel by crow. Two drivers can both be 600 metres away, one on a straight road and one on the far side of a river, a market or a hill with a single road around it. Haversine says they're equally close. The passenger waiting at the pickup point knows better.

We accept that trade-off deliberately. Calculating real road routes for every candidate on every request costs time and money, and most of the time the straight-line ranking and the road ranking agree. Where they disagree, the gap is a matter of a minute or two, not a different side of the city.

Our view is that you should be precise exactly where precision changes the outcome, and cheap everywhere else. Haversine is the cheap, good-enough filter. Road-aware ETAs are the precision layer, and in secondary cities, where the road network has a lot of dead ends and few alternative routes, that's the layer we expect to matter more over time.

Layer three: claiming a driver exactly once

Now the part that took the longest.

Search and ranking can tell you who the best driver is. They can't stop two requests from reaching the same answer at the same moment. Everything we've described so far reads shared state, and a read is only true at the instant you make it.

The fix is to make claiming a driver an atomic operation: one that either fully succeeds or fully fails, with no moment in between where someone else can sneak in. We do it with a Redis lock:

// Claim the driver only if nobody else holds them.
const claimed = await redis.set(
  `lock:driver:${driverId}`,
  requestId,
  "PX", LOCK_TTL_MS, // expire automatically if we crash
  "NX",              // only set if the key doesn't already exist
);

if (claimed !== "OK") {
  // Someone else got there first: move on to the next candidate.
}

NX means "only set this key if it doesn't exist yet". Redis runs the command atomically, so if two requests try to claim the same driver at the same instant, exactly one gets OK and the other gets nothing. The loser doesn't wait or retry the same driver. It moves straight on to the next one on its list.

PX gives the lock an expiry. If the server that claimed a driver crashes halfway through the match, the driver isn't frozen forever. The lock disappears on its own and the driver goes back into the pool.

Releasing the lock is a decision too. You must only release a lock you still own. If your lock has already expired and another request has claimed the same driver, a blind DEL would release their lock. So we compare and delete in a single atomic step, using a small Lua script that Redis runs without interruption:

if redis.call("GET", KEYS[1]) == ARGV[1] then
  return redis.call("DEL", KEYS[1])
end
return 0

Where the passenger meets the lock

None of this is invisible to drivers. When a ride request reaches a driver's phone, the driver has a short window to accept it. If two drivers react to overlapping offers, or an offer expires as a driver taps "Accept", the lock decides. The driver who loses sees a message in the app: "Too late! This request has expired or was assigned to someone else."

That message is the concurrency layer, surfaced as honestly as we can. We would much rather tell a driver they missed a trip than send two drivers to one passenger, or one driver to two.

A lock is not a guarantee

One more opinion, for the engineers reading this.

A Redis lock is excellent at stopping two requests doing the same work at the same time. On its own, it isn't a proof of correctness. Clocks drift, networks pause and processes stall. A lock can expire while the process that held it still thinks it owns the driver.

The lesson we took from chasing race conditions: treat the lock as the fast path, not the final word. The step that actually commits a trip should check, at the moment of writing, that the driver is still available and still yours. Correctness comes from layers that each assume the one before them can fail.

What "a fraction of a second" actually buys

Put together, a match looks like this:

  1. The passenger's location becomes an H3 cell.
  2. We expand ring by ring through Redis until we have nearby drivers of the right vehicle type: car, XL or boda.
  3. We rank them by haversine distance.
  4. We try to claim the best one atomically. If the claim fails, we move to the next.
  5. The claimed driver receives the request and has a short window to accept it.

All of this happens in a fraction of a second, and it stays correct when many passengers request rides at once, which is the only time it really matters.

Speed in matching isn't vanity. Every second a passenger waits at the roadside with no confirmation is a second they spend wondering whether to flag down the first moto that passes. In cities where safe, reliable transport can't be taken for granted, a fast and correct match is the first promise we keep on every trip.

Our opinion, stated plainly

If you're building a marketplace that matches people to anything that moves, such as rides, deliveries or field workers, here's what we'd tell you:

  1. Shrink the problem before you solve it. A good spatial index turns "search the city" into "search the neighbourhood".
  2. Pick a spatial index the whole company can speak. We picked H3 for matching, and got analytics, heatmaps and simulation almost for free.
  3. Be precise only where precision changes the outcome. Haversine to rank, routing where the roads disagree.
  4. Design for the race, not the demo. If two requests can collide, they will, and usually during your busiest hour.

We aren't just building a ride-hailing app. We're building the infrastructure for safe, electric, reliable mobility in African cities. A matching engine that gets a passenger to the right driver, quickly and only once, is where all of that begins.

Ready to ride with Twende?

Join the waitlist and be among the first to experience safer, fairer transport in African cities.

Related posts