I built Uber's backend. Then one driver got 59 riders

Part 1 left the location service at three pods behind HAProxy, sharing driver positions through Redis pub/sub, with an autoscaler that took it to 10,000 drivers. Every test there had a few hundred riders. This post adds the riders: thousands of them in a city the size of Istanbul, and then a hundred of them asking for a car in the same second. Two different problems show up, one about work that grows too fast and one about two steps that should have been one.

The code, manifests and k6 scripts are on GitHub: huseyinbabal/uber-system-design. One image runs every step; environment variables switch between them.

Results at a glance

The expected number is easy to check. 10,000 drivers are spread over a box of 0.4° latitude by 0.5° longitude, about 44 × 42 km or 1,870 km². A 2 km circle covers 12.6 km², so a rider should see about 10,000 × 12.6 / 1,870 ≈ 67 drivers. The geo index run hits that average exactly.

The setup

Same kind cluster and HAProxy ingress as part 1, with three changes: the autoscaler is removed so three pods have to carry the load, each pod gets 512 MiB instead of 256 MiB (the test is about CPU now, not memory), and the image is v2:

docker build -t location-service:v2 app
kind load docker-image location-service:v2 --name uber
kubectl delete hpa location-service --ignore-not-found
kubectl apply -f k8s/redis.yaml -f k8s/app.yaml
kubectl set image deploy/location-service app=location-service:v2
kubectl set resources deploy/location-service --requests=cpu=500m,memory=512Mi --limits=cpu=500m,memory=512Mi
kubectl set env deploy/location-service REDIS_ADDR=redis:6379 GEO=0 LOCK=0
kubectl scale deploy/location-service --replicas=3

The new k6 script, k6/city.js, has two scenarios. Drivers ramp to MAX over one minute and send a position every 4 seconds. Riders start after that and ramp to RIDERS over three minutes, each holding one WebSocket that should get a push every second:

ulimit -n 65000
MAX=10000 RIDERS=6000 k6 run k6/city.js

1. 6,000 riders against a full scan

With GEO=0 each pod keeps every driver in a map (filled by the Redis pub/sub subscriber from part 1), and each rider’s ticker calls this once a second:

for _, d := range drivers {
	if d.At > cutoff && distanceKm(lat, lng, d.Lat, d.Lng) <= km {
		out = append(out, d)
	}
}

The cost is drivers × riders haversine calls per second: 10,000 × 6,000 = 60 million, split across three pods. On top of that every pod decodes every position from pub/sub, 10,000 / 4 s = 2,500 JSON messages a second, regardless of how many pods there are.

Nothing crashes. k9s near the end of the run:

NAME                              READY STATUS   RESTARTS CPU MEM %CPU/L %MEM/L
location-service-c4f966c56-kcwg4  1/1   Running         0 500 308    100     60
location-service-c4f966c56-mwpm5  1/1   Running         0 501 303    100     59
location-service-c4f966c56-nrhzj  1/1   Running         0 500 301    100     58
redis-75c7d7d78c-mlm9f            1/1   Running         0  33  23    n/a    n/aoutput

A CPU-limited pod does not die, it gets throttled. Positions queue up behind the distance loops, and the scan drops any driver whose last position is older than 15 seconds, so drivers vanish from the map while their apps are working fine. The k6 summary:

rider_drivers_seen...: avg=33.607692 p(50)=28  p(95)=73       max=102
rider_update_gap.....: avg=1s        p(50)=1s  p(95)=1.49s    max=6.1s
ws_connect_failed....: 0.00%  0 out of 16000output

Half the drivers missing, a median of 28 instead of 67, and riders waiting up to six seconds for an update. Adding pods would help for a while, but the scan grows with drivers × riders. A city twice as busy means four times the work.

2. Geohash in one page

A rider needs the drivers within 2 km, which is a tiny part of the city. The fix is an index that can answer “what is near this point” without looking at everything. Redis uses a geohash for that.

A geohash interleaves two binary searches. Split the longitude range [-180, 180] in half: a point in the upper half gets a 1, the lower half a 0. Then split the latitude range [-90, 90] the same way for the next bit, then longitude again, and so on. Each bit halves the box the point is in. For the centre of Istanbul (41.015, 28.98) the first ten bits are:

bit:   1  2  3  4  5  6  7  8  9  10
axis:  lo la lo la lo la lo la lo la
value: 1  1  0  0  0  1  1  1  0  1output

Grouped in fives and written in base 32 (0123456789bcdefghjkmnpqrstuvwxyz) that is sx, and the full 11-character hash is sxk976w9dyn. Fewer characters means a bigger box:

Nearby points usually share a prefix: a point a few hundred metres north-east of the centre, (41.02, 28.99), starts with sxk97 too (sxk97e), and the stadium in the ride test, about 19 km away, is sxk3…. “Usually” matters: two points on either side of a cell border can have different prefixes even when they are metres apart, which is why a proximity search always looks at the neighbouring cells as well.

Internally a geo set is a sorted set, and each member’s score is its position encoded as a 52-bit geohash. GEOADD writes it, GEOHASH shows it as the 11-character string, and GEOSEARCH turns a radius into the few score ranges that cover the centre cell and its neighbours, reads only those, and then filters by the exact distance. The documented cost is O(N + log(M)), with N the members in the grid-aligned bounding box around the circle and M the members inside the circle, so it depends on how crowded the area is, not on the size of the city.

kubectl exec deploy/redis -- redis-cli GEOADD demo 28.98 41.015 centre
kubectl exec deploy/redis -- redis-cli GEOHASH demo centre
kubectl exec deploy/redis -- redis-cli GEOSEARCH demo FROMLONLAT 28.98 41.015 BYRADIUS 2 km WITHDIST

Note the argument order: longitude first, then latitude, in every GEO command.

3. The geo index in the code

With GEO=1 the in-memory driver map goes unused. The driver handler writes to one sorted set, and removes the driver when the connection closes:

if geo {
	// the driver went offline: take them off the map
	defer rdb.ZRem(context.Background(), "drivers", id)
}
// ... for each message:
rdb.GeoAdd(ctx, "drivers", &redis.GeoLocation{Name: id, Longitude: l.Lng, Latitude: l.Lat})

ZRem works because a geo set is an ordinary sorted set; there is no GEODEL. The rider side asks Redis instead of walking a map:

func nearbyGeo(lat, lng, km float64) []Location {
	res, _ := rdb.GeoSearchLocation(context.Background(), "drivers", &redis.GeoSearchLocationQuery{
		GeoSearchQuery: redis.GeoSearchQuery{Longitude: lng, Latitude: lat, Radius: km, RadiusUnit: "km"},
		WithCoord:      true,
	}).Result()
	out := make([]Location, 0, len(res))
	for _, d := range res {
		out = append(out, Location{Driver: d.Name, Lat: d.Latitude, Lng: d.Longitude})
	}
	return out
}

No pub/sub subscriber runs in this mode, so the 2,500 messages a second per pod are gone too. One thing this version gives up is the 15-second staleness check: a driver stays in the set until their connection closes. A production version would also store a timestamp (for example in a second sorted set scored by time) and trim old entries.

Run the same test:

kubectl exec deploy/redis -- redis-cli FLUSHALL
kubectl set env deploy/location-service GEO=1
MAX=10000 RIDERS=6000 k6 run k6/city.js

NAME                              READY STATUS   RESTARTS CPU MEM %CPU/L %MEM/L
location-service-8c58744cb-tjbjj  1/1   Running         0 360 309     72     60
location-service-8c58744cb-hfwfp  1/1   Running         0 353 297     70     58
location-service-8c58744cb-pfn82  1/1   Running         0 346 293     69     57
redis-75c7d7d78c-mlm9f            1/1   Running         0 316  17    n/a    n/aoutput

rider_drivers_seen...: avg=67.039041 p(50)=67       p(95)=81     max=99
rider_update_gap.....: avg=1s        p(50)=1s       p(95)=1s     max=1.11s
ws_connect_failed....: 0.00%  0 out of 16000output

The pods still use about 70% of their CPU limit, since they still encode and send 6,000 pushes a second, but the map is full and the updates are on time. The searching moved to Redis, which used about a third of a core for 6,000 searches and 2,500 writes a second.

4. A concert ends

The second feature is booking. /ride finds the nearest drivers and claims the first free one:

near, _ := rdb.GeoSearch(ctx, "drivers", &redis.GeoSearchQuery{
	Longitude: lng, Latitude: lat, Radius: 3, RadiusUnit: "km", Sort: "ASC", Count: 100,
}).Result()
for _, d := range near {
	if claim(ctx, d, rider) {
		rdb.RPush(ctx, "rides", d)
		// respond with the driver
		return
	}
}

The first version of claim reads, then writes:

if rdb.Exists(ctx, "ride:"+driver).Val() == 0 {
	rdb.Set(ctx, "ride:"+driver, rider, 10*time.Second)
	return true
}
return false

Each command is atomic on its own, but the pair is not. Between EXISTS and SET, another request on any of the three pods can run its own EXISTS for the same driver, also see nothing, and also win. With one request at a time that window never matters. With everyone at a stadium asking at once, they all start from the same point, get the same sorted list, and race for the same first driver.

k6/rides.js keeps 100 virtual users waiting until a shared timestamp and then sends every request in the same instant. Drivers have to be online first:

MAX=10000 RIDERS=1 DRAMP=40s RAMP=10m k6 run --quiet k6/city.js   # terminal 1
N=100 k6 run k6/rides.js                                         # terminal 2
kubectl exec deploy/redis -- redis-cli LRANGE rides 0 -1 | sort | uniq -c | sort -rn | head -5
kubectl exec deploy/redis -- redis-cli LRANGE rides 0 -1 | sort | uniq -d | wc -l

checks_succeeded...: 100.00% 100 out of 100
http_req_duration..: avg=20.55ms p(95)=24.1ms max=24.57ms

  59 d-5159
  20 d-5264
   5 d-1476
   4 d-3073
   3 d-9847

       7output

Every request reported success, which is the dangerous part: nothing in the logs or the HTTP status says anything went wrong. Only counting the rides shows one driver holding 59 of them and seven drivers double-booked.

5. SET NX

The fix is to make the check and the write one command. SET key value NX EX 10 sets the key only if it does not exist and returns whether it did. Redis executes commands one at a time, so of all the concurrent SET NX calls for the same driver exactly one gets OK:

func claim(ctx context.Context, driver, rider string) bool {
	if lock {
		// one atomic step: only the first rider gets the key
		ok, _ := rdb.SetNX(ctx, "ride:"+driver, rider, 10*time.Second).Result()
		return ok
	}
	// ...
}

A rider who loses moves to the next driver in the sorted list. The 10 second expiry keeps a claim from blocking a driver forever if the request dies halfway; in a real app the driver accepting would turn the claim into a trip record.

kubectl set env deploy/location-service LOCK=1
kubectl exec deploy/redis -- redis-cli DEL rides
N=100 k6 run k6/rides.js
kubectl exec deploy/redis -- redis-cli LRANGE rides 0 -1 | sort | uniq -d | wc -l

checks_succeeded...: 100.00% 100 out of 100
http_req_duration..: avg=33.79ms p(95)=47.12ms max=47.82ms

       0output

100 rides, no driver twice. Requests got slower, 34 ms instead of 21 ms on average. A rider who loses a claim now goes on to the next driver, so many requests make several round trips to Redis where the broken version made one.

A single-instance SET NX is enough here because all claims go to one Redis. Locks that must survive a Redis failover need more care; the Redis documentation discusses the trade-offs under distributed locks.

Where it stands

Drivers write positions into one geo set, riders search only the cells around them, and a ride claim is a single atomic command. All three now depend on that one Redis instance: positions, searches and bookings stop together if it goes down, which is where part 3 picks up.

Clean up

kind delete cluster --name uber

Sources

• Project on GitHub: huseyinbabal/uber-system-design
• Redis: Geospatial indexing
• Redis: GEOSEARCH
• Redis: GEOHASH
• Redis: SET (NX, EX options)
• Redis: Distributed locks with Redis
• Geohash (Wikipedia), cell sizes by length
• k6: WebSockets (k6/websockets)