← Chương trước: Phần 1: Thu thập GPS qua gRPC Streaming, MQTT & Kalman | Mục lục Series | Chương tiếp theo: Phần 3: Kiến trúc Event Streaming với Kafka & Flink →
Answer-first: Lập chỉ mục không gian (Geospatial Indexing) chuyển bài toán tìm kiếm O(N) thành O(1) bằng cách chia bản đồ thành lưới ô. Uber H3 (lục giác) vượt trội hơn Geohash và Google S2 về tính đồng nhất khoảng cách lân cận, kết hợp bộ đệm Redis GEO cho phép tra cứu tài xế dưới 5ms.
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 AI/Analytics | ❌ | ✅ Tích hợp mạnh mẽ với Data Lakes 2026 (Iceberg) |
Uber dùng cách 2 (Redis + H3) vì khả năng sharding và tích hợp sâu với Pricing Engine cùng hệ thống Predictive Dispatch hiện đại.
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.
🔗 Đọc thêm các chuyên đề liên quan:
- Kiến trúc Microservices Golang & DDD
- Triển khai Agentic AI Swarm trong Production với OpenClaw & LiteLLM
- Kiến trúc Microservices Golang gRPC: Protobuf, TLS & Middleware
← Chương trước: Phần 1: Thu thập GPS qua gRPC Streaming, MQTT & Kalman | Mục lục Series | Chương tiếp theo: Phần 3: Kiến trúc Event Streaming với Kafka & Flink →
❓ Câu Hỏi Thường Gặp (FAQ)
Q1: Phần 2 — Geospatial Indexing: H3, S2 Geometry & Redis GEO giải quyết vấn đề cốt lõi nào trong kiến trúc hệ thống?
Cách Uber chia bản đồ Trái Đất thành hàng tỉ ô lục giác bằng thuật toán H3, S2 Geometry và Redis GEO để tìm tài xế gần nhất trong nháy mắt.
Q2: Những lưu ý quan trọng nhất khi triển khai thực tế là gì?
Cần chú trọng phân tầng ranh giới trách nhiệm (bounded context), thiết lập cơ chế fallback dự phòng, và giám sát chặt chẽ qua metrics OpenTelemetry để phát hiện sớm các điểm nghẽn.
Q3: Làm sao để kiểm thử và đánh giá hiệu quả sau khi áp dụng?
Áp dụng kiểm thử tải (load test), benchmark độ trễ P95/P99 trước và sau triển khai, kết hợp tracing phân tán để xác minh tính ổn định dưới tải cao.