Vấn đề: Tại sao không chỉ chọn tài xế gần nhất?
Bản năng đầu tiên khi thiết kế matching: ghép mỗi khách hàng với tài xế gần nhất. Nhưng cách tiếp cận Greedy này gây tổn thất lớn ở quy mô hệ thống:
Ví dụ: 3 khách (R1, R2, R3) và 3 tài xế (D1, D2, D3)
Greedy Matching (tài xế gần nhất):
R1 ← D1 (ETA 2 phút) ✓
R2 ← D3 (ETA 8 phút) ← D2 đã bị R1 "lấy mất" dù D2 gần R2 hơn
R3 ← D2 (ETA 10 phút) ← Kết quả tệ
Tổng ETA: 2 + 8 + 10 = 20 phút
Optimal Matching (tối ưu toàn cục):
R1 ← D2 (ETA 3 phút)
R2 ← D1 (ETA 3 phút)
R3 ← D3 (ETA 4 phút)
Tổng ETA: 3 + 3 + 4 = 10 phút ← Tốt hơn 50%!
Uber gọi bài toán này là Global Optimization — tìm cách phân công sao cho tổng ETA của toàn bộ hệ thống là nhỏ nhất, chứ không phải ETA của từng cặp riêng lẻ.
DISCO — Dispatch Optimization
DISCO (Dispatch Optimization) là hệ thống matching của Uber, chịu trách nhiệm ghép hàng triệu ride requests với tài xế mỗi ngày.
Kiến trúc tổng thể
┌─────────────────┐ ┌─────────────────┐
│ Rider App │ │ Driver App │
│ "Đặt xe" │ │ GPS, Status │
└────────┬────────┘ └────────┬────────┘
│ │
▼ ▼
┌─────────────────┐ ┌─────────────────┐
│ Demand Service │ │ Supply Service │
│ (Ride Requests)│ │ (Driver Pool) │
└────────┬────────┘ └────────┬────────┘
│ │
└──────────┬────────────┘
▼
┌─────────────────────┐
│ DISCO Engine │
│ │
│ 1. Candidate Filter │ ← S2/H3 Geospatial Query
│ 2. ETA Calculator │ ← Routing Service
│ 3. Batch Optimizer │ ← Hungarian Algorithm
│ 4. Dispatch │ ← RAMEN Push
└─────────────────────┘
Bước 1: Candidate Filtering (Lọc ứng viên)
Khi một ride request đến, DISCO không kiểm tra tất cả tài xế. Nó dùng S2 Cell ID (hoặc H3) của vị trí khách hàng để nhanh chóng thu hẹp danh sách:
Input: Rider location → S2 Cell Level 12
Action: Tìm tất cả S2 cells lân cận (covering circle bán kính ~3km)
Query: Redis/Memory → Lấy danh sách drivers trong các cells đó
Filters:
✓ Status = AVAILABLE (không đang chở khách)
✓ Vehicle type phù hợp (Car, Bike, SUV...)
✓ Capacity đủ (nếu đi nhóm)
✓ Không bị block bởi rider
Output: ~10-30 candidate drivers
Bước 2: ETA Calculation (Tính thời gian đến)
Khoảng cách đường chim bay vô nghĩa trong thực tế — 500m đường chim bay có thể là 3km đường thực (qua cầu, vòng ngã tư, đường một chiều).
Candidate drivers: [D1, D2, D3, D4, D5]
Rider position: R1
Routing Service tính ETA thực tế dựa trên:
- Mạng lưới đường bộ số hóa (road graph)
- Dữ liệu giao thông real-time (traffic data)
- Đường một chiều, cầu vượt, hầm chui
- Giờ cao điểm / lịch sử giao thông
Results:
D1: 800m crow-fly → 2.3km road → ETA 4 phút (đường kẹt)
D2: 1.2km crow-fly → 1.5km road → ETA 3 phút (đường thoáng) ← Tốt hơn!
D3: 600m crow-fly → 3.8km road → ETA 7 phút (phải vòng cầu)
Uber phát triển DeepETA — model deep learning dự đoán ETA chính xác hơn routing engine truyền thống bằng cách học từ hàng tỉ chuyến đi lịch sử.
Bước 3: Batched Matching (Ghép theo lô)
Đây là bước quan trọng nhất và phức tạp nhất. Thay vì xử lý từng request riêng lẻ, DISCO gom request trong một cửa sổ thời gian ngắn (vài giây) rồi giải bài toán phân công tối ưu cho cả lô.
Batching Window: 2 giây
Trong 2 giây, nhận được:
Ride Requests: [R1, R2, R3, R4, R5]
Available Drivers: [D1, D2, D3, D4, D5, D6, D7]
Xây dựng Cost Matrix (ETA giữa mỗi cặp rider-driver):
D1 D2 D3 D4 D5 D6 D7
R1 [ 3 5 8 2 7 9 4 ]
R2 [ 6 2 4 7 3 5 8 ]
R3 [ 4 7 3 5 6 2 9 ]
R4 [ 8 4 6 3 5 7 2 ]
R5 [ 5 6 2 8 4 3 7 ]
Bài toán: Tìm phân công 1-1 sao cho tổng cost nhỏ nhất
→ Hungarian Algorithm (hoặc Auction Algorithm)
Hungarian Algorithm (Thuật toán Hungary)
Đây là thuật toán kinh điển để giải bài toán phân công (Assignment Problem) với độ phức tạp O(n³):
Input: Cost Matrix N×M (N riders, M drivers, M ≥ N)
Output: Phân công 1-1 tối ưu
Kết quả tối ưu:
R1 ← D4 (ETA 2 phút)
R2 ← D2 (ETA 2 phút)
R3 ← D6 (ETA 2 phút)
R4 ← D7 (ETA 2 phút)
R5 ← D3 (ETA 2 phút)
Tổng ETA: 10 phút (so với Greedy có thể là 20+ phút)
Ringpop — Distributed Coordination
DISCO chạy trên nhiều server. Làm sao đảm bảo hai server DISCO khác nhau không cùng ghép cùng một tài xế cho hai khách khác nhau?
Uber phát triển Ringpop — thư viện consistent hashing dựa trên giao thức SWIM (gossip protocol):
Ringpop Hash Ring:
Server A ────── Server B ────── Server C ────── Server A
│ │ │
▼ ▼ ▼
Riders & Riders & Riders &
Drivers Drivers Drivers
in Zone 1 in Zone 2 in Zone 3
Mỗi S2 Cell được hash vào một server DISCO cụ thể.
→ Tất cả requests và drivers trong cùng khu vực
được xử lý bởi CÙNG MỘT server DISCO.
→ Không có xung đột (conflict) khi phân công.
SWIM Protocol: Mỗi node DISCO định kỳ “ping” các node khác để kiểm tra sống/chết. Nếu một node chết, ring tự động rebalance — các S2 cells của node chết được chuyển sang node lân cận trong ring.
Fault Tolerance: State Digest
Vấn đề: Nếu một data center của Uber bị sập giữa chừng, tất cả các cuốc xe đang chạy (in-flight trips) sẽ bị mất trạng thái?
Giải pháp thông minh của Uber: Encrypted State Digest — DISCO định kỳ đẩy trạng thái cuốc xe (đã mã hóa) xuống lưu trên chính điện thoại của tài xế.
Luồng bình thường:
DISCO Server ◄──── state ────► Driver Phone
(Source of truth) (Backup copy)
Khi data center sập:
1. DISCO Server mới khởi động
2. Driver phones kết nối lại
3. DISCO yêu cầu driver phones gửi lại state digest
4. DISCO giải mã và khôi phục trạng thái tất cả trips đang chạy
5. Hệ thống tiếp tục hoạt động mà không mất cuốc nào
Grab’s Approach: Fulfilment Platform + DispatchGym
Grab không dùng DISCO nhưng có hệ thống tương đương:
Fulfilment Platform
Ban đầu, mỗi vertical (ride-hailing, food delivery, express) có matching engine riêng. Grab đã gom lại thành một Fulfilment Platform thống nhất quản lý việc ghép đơn cho tất cả verticals.
DispatchGym — Reinforcement Learning
Grab phát triển DispatchGym — framework cho phép data scientists huấn luyện model Reinforcement Learning (RL) để tối ưu hoá các hyperparameter của thuật toán dispatch (ví dụ: bán kính tìm kiếm tối ưu, thời gian chờ batch, trọng số ETA vs rating) trong môi trường mô phỏng trước khi deploy lên production.
DispatchGym Loop:
1. Simulated Environment (dữ liệu lịch sử replay)
2. RL Agent chọn actions (tuning hyperparameters)
3. Environment trả về reward (tổng ETA giảm, acceptance rate tăng)
4. Agent học và cải thiện
5. Khi reward ổn định → Deploy lên production (A/B test)
Metrics quan trọng của Matching Engine
| Metric | Ý nghĩa | Mục tiêu |
|---|---|---|
| P50/P99 Matching Latency | Thời gian từ lúc nhận request đến lúc dispatch | < 2 giây (P99) |
| Acceptance Rate | % tài xế nhận cuốc khi được offer | > 85% |
| ETA Accuracy | Sai số giữa ETA dự đoán và thực tế | < 20% |
| Match Rate | % request được ghép thành công | > 95% |
| Total Wait Time | Tổng thời gian khách chờ (rider + driver di chuyển) | Minimize |
Tiếp theo, chúng ta sẽ tìm hiểu cơ chế Surge Pricing — hệ thống tính giá linh hoạt dựa trên tỷ lệ cung cầu real-time. Đọc tiếp Phần 5 — Surge Pricing: Tính giá động theo cung cầu thời gian thực.