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.