System DesignBài toán cốt lõi: với một điểm đón, tìm nhanh các tài xế trống trong bán kính + ghép một-một, trong khi hàng triệu tài xế liên tục báo vị trí.
Đánh chỉ mục không gian (geo-index):
- Không thể quét toàn bộ tài xế. Chia bản đồ thành ô lưới rồi truy vấn các ô quanh điểm đón.
- Kỹ thuật: Geohash (mã hóa lat/long thành chuỗi tiền tố; tiền tố chung ⇒ gần nhau) hoặc Uber H3 (lưới lục giác, khoảng cách giữa các ô đồng đều hơn ô vuông), hoặc QuadTree chia thích ứng theo mật độ.
- Lưu cell_id → {danh sách tài xế} trong Redis để tra cận kề O(số ô lân cận).
Cập nhật vị trí real-time:
- Tài xế gửi vị trí mỗi ~4s qua kết nối bền (WebSocket). Ghi vào in-memory store (Redis), không phải DB chính — write rate khổng lồ, dữ liệu sống ngắn.
- Khi tài xế đổi ô → cập nhật chỉ mục ô cũ/mới.
Ghép chuyến (matching):
- Lấy ứng viên trong vài ô quanh điểm đón → xếp hạng theo ETA thực (theo đường, không phải đường chim bay) → gửi offer.
- Xử lý race condition: một tài xế không bị gán hai chuyến → dùng lock/atomic trên trạng thái tài xế.
Hình dung: chia thành phố thành các ô bàn cờ; chỉ hỏi vài ô quanh khách thay vì gọi điện cả thành phố.
Lưu ý: tách dịch vụ location (ghi nhiều, eventual) khỏi dịch vụ trip (giao dịch, cần consistency); ETA dùng routing engine riêng.
Core problem: given a pickup point, quickly find idle drivers within a radius and match one-to-one, while millions of drivers continuously report location.
Spatial indexing (geo-index):
- You can't scan all drivers. Divide the map into grid cells and query cells around the pickup.
- Techniques: Geohash (encode lat/long into a prefix string; shared prefix ⇒ nearby) or Uber H3 (hexagonal grid, more uniform inter-cell distance than squares), or a QuadTree that adapts to density.
- Store cell_id → {driver list} in Redis for O(neighbor cells) proximity lookups.
Real-time location updates:
- Drivers send location every ~4s over a persistent connection (WebSocket). Write to an in-memory store (Redis), not the main DB — the write rate is huge and the data is short-lived.
- When a driver changes cells → update the old/new cell index.
Matching:
- Pull candidates from cells around the pickup → rank by real ETA (road-based, not straight-line) → send offers.
- Handle the race condition: one driver must not get two trips → lock/atomic on driver state.
Picture: split the city into a chessboard; only ask a few squares around the rider instead of calling the whole city.
Note: separate the location service (write-heavy, eventual) from the trip service (transactional, needs consistency); ETA uses a dedicated routing engine.