Bài toán: Tìm kim trong đống rơm
Khi bạn bấm “Đặt xe” trên Grab, hệ thống phải tìm tài xế phù hợp nhất trong bán kính vài km. Nhưng hệ thống đang theo dõi hàng triệu tài xế đồng thời. Cách tiếp cận ngây thơ — tính khoảng cách từ bạn tới mọi tài xế — là bất khả thi:
Cách ngây thơ (Brute Force):
SELECT * FROM drivers
WHERE ST_Distance(driver_location, rider_location) < 2000 -- 2km
ORDER BY ST_Distance(driver_location, rider_location)
Với 5 triệu tài xế → 5 triệu phép tính khoảng cách
Latency: hàng giây → Không chấp nhận được
Giải pháp: Chia bản đồ thành lưới (Spatial Indexing) để thu hẹp không gian tìm kiếm từ hàng triệu xuống vài chục.
Phương pháp 1: Geohash
Geohash mã hóa tọa độ (latitude, longitude) thành một chuỗi ký tự. Chuỗi càng dài, ô vuông càng nhỏ và chính xác:
Tọa độ: 10.7769, 106.7009 (Quận 1, TP.HCM)
Geohash: w3gvk1 (ô ~1.2km × 0.6km)
w3gvk1e (ô ~153m × 153m)
w3gvk1e7 (ô ~38m × 19m)
Đặc tính quan trọng: Prefix sharing
w3gvk1e ← Các ô có chung prefix nằm gần nhau
w3gvk1f
w3gvk1g
Ưu điểm
- Đơn giản, dễ hiểu.
- Database-friendly: có thể dùng LIKE query (
WHERE geohash LIKE 'w3gvk1%'). - Redis hỗ trợ native (
GEOADD,GEOSEARCH).
Nhược điểm nghiêm trọng: Edge Problem
Geohash chia bản đồ thành các ô vuông. Hai điểm nằm sát nhau nhưng ở hai cạnh biên của hai ô vuông khác nhau sẽ có prefix hoàn toàn khác — hệ thống không tìm thấy tài xế dù họ chỉ cách bạn 50 mét.
┌──────────┬──────────┐
│ │ │
│ w3gvk1 │ w3gvk3 │ ← Hai ô khác prefix hoàn toàn
│ │ │
│ ●──────────○ │ ← Rất gần nhau nhưng ở hai ô khác nhau
│ │ │
└──────────┴──────────┘
Cách giải quyết: Luôn tìm kiếm ô hiện tại + 8 ô lân cận (3x3 grid). Nhưng điều này tạo ra nhiều false positives ở các góc.
Phương pháp 2: H3 — Lưới Lục giác của Uber
Uber tự phát triển H3 (Hexagonal Hierarchical Spatial Index) để giải quyết mọi hạn chế của Geohash. Đây là hệ thống lập chỉ mục không gian mã nguồn mở, chia toàn bộ bề mặt Trái Đất thành các ô hình lục giác (hexagon).
Tại sao lục giác tốt hơn ô vuông?
Ô vuông (Geohash): Ô lục giác (H3):
┌────┬────┬────┐ ╱╲ ╱╲
│ │ │ │ ╱ ╲╱ ╲
│ d │ ? │ │ │ d ││ d │
│ │ │ │ ╲ ╱╲ ╱
├────┼────┼────┤ ╲╱ ╲╱
│ d │ ● │ │ ╱╲ ● ╱╲
│ │ │ │ │ d ││ d │
├────┼────┼────┤ ╲ ╱╲ ╱
│ │ │ │ ╲╱ ╲╱
└────┴────┴────┘ ╱╲ ╱╲
│ d ││ d │
d = khoảng cách tới ● ╲ ╱╲ ╱
╲╱ ╲╱
Ô vuông: 4 ô lân cận gần (cạnh) Ô lục giác: 6 ô lân cận
4 ô lân cận xa (góc) tất cả đều CÙNG khoảng cách!
→ Khoảng cách không đều → Khoảng cách đồng nhất
Đẳng cự (Equidistant): Mọi ô lân cận của lục giác đều cách tâm một khoảng bằng nhau. Với ô vuông, ô ở góc xa hơn ô ở cạnh √2 lần (~1.41 lần). Sự bất đồng đều này tạo ra lệch trong thuật toán tìm kiếm.
16 Cấp độ phân giải (Resolutions)
H3 hỗ trợ 16 cấp phân giải, từ cấp 0 (bao phủ cả lục địa) đến cấp 15 (vài mét vuông):
| Resolution | Diện tích trung bình | Dùng cho |
|---|---|---|
| 0 | ~4.357.449 km² | Cấp lục địa |
| 4 | ~1.770 km² | Cấp tỉnh/thành phố |
| 7 | ~5.16 km² | Surge Pricing zone |
| 8 | ~0.74 km² | Tìm kiếm tài xế (phổ biến) |
| 9 | ~0.105 km² | Matching chính xác |
| 12 | ~0.003 km² | Street-level |
Uber dùng Resolution 7-9 cho phần lớn nghiệp vụ: tìm tài xế, tính surge pricing, và phân tích cung-cầu.
K-Ring — Tìm kiếm lân cận
K-Ring là tập hợp tất cả các ô trong phạm vi K bước từ ô trung tâm:
K=0 (chỉ ô trung tâm): K=1 (ô trung tâm + 6 lân cận):
╱╲ ╱╲ ╱╲
╱ ╲ ╱ ╲╱ ╲
│ ● │ │ ││ │
╲ ╱ ╲ ╱╲ ╱
╲╱ ╲╱ ╲╱
╱╲ ● ╱╲
1 ô │ ││ │
╲ ╱╲ ╱
╲╱ ╲╱
7 ô
K=2: 19 ô K=3: 37 ô
Thuật toán tìm tài xế:
- Chuyển tọa độ khách hàng thành H3 index (resolution 8).
- Tính K-Ring(1) → 7 ô lục giác.
- Tìm tất cả tài xế đang ở trong 7 ô này từ Redis.
- Nếu không đủ → mở rộng K-Ring(2) → 19 ô.
- Sắp xếp theo ETA thực tế (không chỉ khoảng cách đường chim bay).
Code ví dụ (Go)
import "github.com/uber/h3-go/v4"
// Chuyển tọa độ thành H3 index
func findNearbyDrivers(riderLat, riderLng float64, radius int) []string {
// Resolution 8: mỗi ô ~0.74 km²
riderCell := h3.LatLngToCell(h3.LatLng{Lat: riderLat, Lng: riderLng}, 8)
// K-Ring: lấy tất cả ô trong bán kính K bước
searchCells := h3.GridDisk(riderCell, radius)
var driverIDs []string
for _, cell := range searchCells {
// Tra cứu Redis: key = H3 cell, value = danh sách driver IDs
cellKey := fmt.Sprintf("drivers:h3:%s", cell.String())
ids := redisClient.SMembers(ctx, cellKey).Val()
driverIDs = append(driverIDs, ids...)
}
return driverIDs
}
Phương pháp 3: Google S2 Geometry
S2 (do Google phát triển) cũng được Uber sử dụng trong hệ thống DISCO (Matching Engine). S2 chia bề mặt Trái Đất thành các ô vuông theo hình chiếu lên hình lập phương (Hilbert Curve).
Đặc điểm:
- Mỗi ô được biểu diễn bằng một 64-bit integer → nhanh hơn khi so sánh, hashing, sharding.
- 30 cấp độ phân giải.
- Google Maps, Foursquare, MongoDB Geospatial đều dùng S2.
import "github.com/golang/geo/s2"
// S2: Tìm tất cả cell bao phủ bán kính 2km từ điểm
func getCoveringCells(lat, lng float64, radiusM float64) []s2.CellID {
center := s2.PointFromLatLng(s2.LatLngFromDegrees(lat, lng))
cap := s2.CapFromCenterAngle(center, s2.Angle(radiusM/6371000.0))
coverer := &s2.RegionCoverer{
MinLevel: 14,
MaxLevel: 16,
MaxCells: 20,
}
return coverer.Covering(cap)
}
Lưu trữ vị trí: Redis GEO
Toàn bộ vị trí tài xế online được lưu trong RAM (Redis) vì tốc độ truy vấn < 1ms. Không dùng database truyền thống vì quá chậm cho 1.25 triệu write/s.
Cách 1: Redis GEO (Built-in)
-- Thêm/cập nhật vị trí tài xế
GEOADD drivers:active 106.7009 10.7769 "driver:abc123"
-- Tìm tài xế trong bán kính 2km
GEOSEARCH drivers:active FROMLONLAT 106.7009 10.7769 BYRADIUS 2 km ASC COUNT 20
-- Kết quả: ["driver:abc123", "driver:def456", ...]
Cách 2: Redis SET + H3 Index (Uber’s approach)
-- Mỗi H3 cell là một Redis SET chứa driver IDs
SADD drivers:h3:882a100d6dfffff "driver:abc123"
SADD drivers:h3:882a100d6dfffff "driver:def456"
-- Khi driver di chuyển sang cell mới:
SREM drivers:h3:882a100d6dfffff "driver:abc123" -- Xóa khỏi cell cũ
SADD drivers:h3:882a100d71fffff "driver:abc123" -- Thêm vào cell mới
-- TTL để tự dọn driver offline:
-- Kết hợp SET + EXPIRE hoặc dùng Sorted Set với timestamp
So sánh hai cách tiếp cận
| Đặc điểm | Redis GEO | Redis SET + H3 |
|---|---|---|
| Tìm kiếm bán kính | ✅ Built-in GEOSEARCH | ❌ Phải tự tính K-Ring |
| Sharding | ❌ Khó shard (1 key chứa tất cả) | ✅ Mỗi H3 cell là 1 key riêng → dễ shard |
| Scale | ~vài triệu | ~hàng chục triệu |
| Tích hợp Surge/Analytics | ❌ | ✅ Đếm driver/cell → tính cung cầu ngay |
Uber dùng cách 2 (Redis + H3) vì khả năng sharding và tích hợp với Pricing Engine tốt hơn.
Consistent Hashing — Phân tán dữ liệu GEO
Khi một thành phố lớn như TP.HCM có 200.000 tài xế online, một Redis node không đủ RAM. Giải pháp: Consistent Hashing để phân tán các H3 cell ra nhiều Redis node:
H3 Cell "882a100d6dfffff" → hash() → Node A
H3 Cell "882a100d71fffff" → hash() → Node B
H3 Cell "882a100d73fffff" → hash() → Node A
Các ô lân cận (K-Ring) có thể nằm trên nhiều node khác nhau
→ Query K-Ring = scatter-gather từ nhiều nodes
Tiếp theo, chúng ta sẽ đi vào xương sống của toàn bộ hệ thống — Apache Kafka — nơi mọi sự kiện GPS, đặt xe, nhận cuốc đều đi qua. Đọc tiếp Phần 3 — Event Streaming: Xương sống Apache Kafka & Flink.