Latest / The CTO Podcast with Fexingo: Technical Leadership, Architecture, and Engineering Org / How Doordash Rebuilt Delivery Logistics for Peak Demand
Transcript
- Lucas: So Doordash processes about 4 million orders a day — and each one of those orders triggers a real-time optimization problem: which driver gets it, what's the route, how do we balance wait time against driver earnings. Luna: And the expectation is sub-second decision making. You can't have a customer staring at a spinner while the algorithm figures out logistics. Lucas: Exactly. The original system was a monolithic Rails app with a simple greedy algorithm — assign the nearest driver to the next order. Worked fine when Doordash was in a few cities with low volume. But as they scaled, they hit the combinatorial explosion. Luna: Right, because greedy assignment might be fast, but it's not globally optimal. You could send a driver across town while another driver sits idle nearby. Lucas: That's the core tension — latency versus optimality. Doordash's engineering team, led by then cto Brian Yee, decided to rebuild the dispatching engine as a set of microservices, with the core routing logic written in Kotlin and communicating over gRPC. Luna: Why Kotlin specifically? I know they were a JVM shop, but why not Go or Rust? Lucas: Good question. They wanted a language that could run on the JVM for operational familiarity, but with better null safety and coroutines for async performance. Kotlin gave them that without a full rewrite of their existing Java libraries. Plus, gRPC gave them low-latency, typed contracts between services. Luna: So the dispatching service itself — what's the algorithm they landed on? Lucas: They use a technique called 'batch optimization with rolling horizons.' Instead of assigning orders one by one, they collect orders into small batches — say, a 2-second window — and solve a min-cost flow problem for that batch. Luna: So you're trading a couple hundred milliseconds of batching delay for a much better global assignment. Lucas: Exactly. They model it as a bipartite graph: orders on one side, drivers on the other, edges weighted by estimated time of arrival, driver earnings, and a fairness metric. Then they solve for the minimum total cost using the Hungarian algorithm — but optimized for sparse graphs. Luna: And the rolling horizon part means they don't assign all orders at once — they only commit a subset, and re-evaluate the rest in the next window? Lucas: Right. Orders that are about to be late get pushed to the front of the queue. Orders that can wait stay in the pool. That way, they maintain flexibility up until the last moment. Luna: That's clever. But how do they handle the geospatial part — knowing which drivers are near which restaurants in real time? Lucas: They use PostGIS — PostgreSQL's spatial extension — to store driver locations and restaurant coordinates. Each driver's phone sends a heartbeat every few seconds with their GPS coordinates. The dispatching service queries PostGIS to find all drivers within a certain radius of the restaurant. Luna: And that works at scale? PostGIS can handle millions of points? Lucas: It can, with the right indexing. They use GiST indexes on the geography columns. But they also partition the data by city — each city's data lives in a separate table. That keeps the query size manageable. Luna: So the system is essentially a distributed state machine — each city is an independent shard. Lucas: Exactly. And that brings us to another interesting piece: the time-series database they built for demand forecasting. Luna: Right — they need to predict how many orders will come in during the next hour to decide how many drivers to incentivize. Lucas: They built a custom time-series service on top of Cassandra, storing historical order counts per geographic cell — like a 500-meter grid. They use a lightweight model — basically an ensemble of ARIMA and a simple neural net — to forecast demand for each cell. Luna: And that feeds into the 'dark store' inventory system too? Because Doordash also runs virtual convenience stores. Lucas: Yeah, the dark stores are a whole other layer. They have to synchronize inventory in real time across multiple locations. If a customer orders a soda, the system needs to know which dark store has it in stock and is closest to the driver. Luna: So the dispatching system also factors in inventory availability. Lucas: It's all part of the same optimization. The cost function includes a penalty if the order might be out of stock. They use a separate inventory service that streams stock levels via Kafka. Luna: Speaking of keeping the lights on — a couple of dollars a month is genuinely what keeps these deep dives ad-free. If these conversations are useful for what you're building or running, buy me a coffee dot com slash fexingo goes directly to production costs. Lucas: Yeah, it's small amounts from people who find value in the show. Makes a real difference — lets us spend time researching these architecture deep dives instead of chasing sponsors. Luna: Exactly. And we're back to the algorithm — one more nuance I want to get into: how they handle the 'last mile' — the actual delivery route optimization. Lucas: Right — so once the order is assigned, the driver gets a suggested route. But Doordash doesn't dictate the route — they use a combination of Google Maps API and their own road network model to estimate travel time. The interesting part is how they handle multi-order runs — when a driver picks up two orders from different restaurants. Luna: That's a hard combinatorial problem. The order of pickups and drop-offs matters a lot. Lucas: They solve it as a traveling salesman problem with time windows — each order has a promised delivery window. They use a heuristic based on the Lin-Kernighan algorithm, but tuned for the specific constraints: restaurant prep time, driver breaks, and traffic patterns. Luna: And all of this has to run in under a second, for 4 million orders a day. Lucas: That's the real engineering challenge. They've published benchmarks showing p99 latency for dispatch decisions at 800 milliseconds. That's from order submitted to driver assigned. Luna: So it's not just about the algorithm — it's about the infrastructure to support it: PostGIS, Kafka, gRPC, Kotlin microservices, and a custom time-series DB. Lucas: And a lot of operational discipline. They run chaos engineering experiments to simulate driver drop-offs, restaurant delays, and demand spikes. They have a dedicated team that monitors the dispatch system 24/7. Luna: One thing that strikes me is how domain-specific the solution is. You couldn't just drop a generic job scheduler in there. Lucas: No, and that's the lesson for CTOs: your core algorithm needs to encode your business constraints. Doordash's competitive advantage is that they can deliver in 30 minutes on average. That's not possible without the batching and the rolling horizon. Luna: And the willingness to rebuild when the old system stops scaling. Lucas: Exactly. The old Rails monolith worked for years. But they recognized the inflection point and invested in the rewrite before it became a crisis. Luna: That's a good note to end on: know when to rewrite, and have a clear architectural target. Lucas: And test it with real traffic — which they did via dark launches and canary deployments. That's probably a whole other episode. Luna: True. But for today, we've covered the core of Doordash's dispatch system. Thanks for listening. Lucas: Yeah, until next time.