Khi bạn mở app gọi xe, hệ thống phải trả lời trong tích tắc: "tài xế nào đang ở gần bạn?". Ở quy mô Uber — hàng triệu tài xế đang di chuyển — cách ngây thơ (tính khoảng cách tới mọi tài xế mỗi truy vấn) là bất khả thi. Bài này không chỉ giải thích nguyên lý mà dựng thật một chỉ mục không gian trên Redis GEO, nạp nửa triệu tài xế và đo trực tiếp, rồi so với cách Uber tự xây thư viện H3 lục giác.

Bài toán: O(N) mỗi truy vấn là không khả thi

Cách hiển nhiên: với mỗi khách, duyệt danh sách tài xế, tính khoảng cách, giữ ai trong bán kính. Đó là O(N) mỗi truy vấn — với 1 triệu tài xế và hàng nghìn truy vấn/giây, là hàng tỷ phép tính khoảng cách mỗi giây, chưa kể tài xế liên tục cập nhật vị trí. Không co giãn.

Cách giải: gán mỗi vị trí vào một ô, và Redis GEO làm sẵn điều đó

Nguyên lý nền của mọi geospatial index (geohash, S2, H3): chia bề mặt thành ô, gán mỗi điểm vào ô chứa nó; truy vấn chỉ xét ô của khách và ô kề. Redis có sẵn kiểu GEO làm đúng việc này — bên trong nó mã hoá (lon, lat) thành một geohash 52-bit và lưu vào một sorted set, nên "tìm lân cận" trở thành quét một dải geohash gần nhau.

Nạp tài xế bằng GEOADD (thật):

redis-cli GEOADD drivers 106.700 10.776 "tx_ben_thanh"
redis-cli GEOADD drivers 106.705 10.780 "tx_gan"
# ... nạp thêm 500.000 tài xế ngẫu nhiên bằng pipeline ...
redis-cli ZCARD drivers          # -> 500004 (index chính là MỘT sorted set)

Tìm lân cận bằng GEOSEARCH — Redis lo phần chỉ mục không gian:

redis-cli GEOSEARCH drivers \
    FROMLONLAT 106.700 10.776 BYRADIUS 2 km \
    ASC COUNT 5 WITHDIST WITHCOORD

Ảnh chụp đoạn mã nền tối minh hoạ tìm tài xế gần thật bằng Redis GEO geohash tích hợp Uber dùng H3 lục giác Redis GEO dùng geohash cùng nguyên lý chỉ mục ô, một GEOADD nạp vị trí tài xế Redis lưu vào sorted set khoá bằng geohash 52-bit redis-cli GEOADD drivers 106.700 10.776 tx_ben_thanh redis-cli GEOADD drivers 106.705 10.780 tx_gan nạp thêm 500000 tài xế ngẫu nhiên bằng pipeline redis-cli ZCARD drivers trả 500004 index chính là 1 sorted set, hai GEOSEARCH tìm tài xế trong bán kính Redis lo phần chỉ mục không gian redis-cli GEOSEARCH drivers FROMLONLAT 106.700 10.776 BYRADIUS 2 km ASC COUNT 5 WITHDIST WITHCOORD không duyệt 500k tài xế Redis chỉ quét các ô geohash lân cận, ba GEODIST và GEOHASH khoảng cách thật cộng geohash nội bộ Redis dùng làm index redis-cli GEODIST drivers tx_ben_thanh tx_gan m khoảng cách mét redis-cli GEOHASH drivers tx_ben_thanh chuỗi geohash của điểm Redis GEO bằng geohash cộng sorted set Uber H3 thay ô vuông geohash bằng ô lục giác 6 ô kề cách đều tránh méo 41 phần trăm đường chéo cùng ý gán điểm vào ô

Hình 1: Dựng chỉ mục không gian thật bằng Redis GEO — GEOADD nạp điểm (lưu geohash vào sorted set), GEOSEARCH tìm lân cận, GEODIST/GEOHASH cho khoảng cách và geohash nội bộ. Cùng nguyên lý mà Uber H3 dùng, chỉ khác ô vuông vs lục giác.

Đo THẬT: nửa triệu tài xế trên một Redis

Ta nạp 500.004 tài xế vào một container Redis 7.4.11 và chạy truy vấn thật. GEOSEARCH bán kính 2km quanh Bến Thành trả về đúng các tài xế gần nhất, đã sắp theo khoảng cách:

tx_ben_thanh  0.0001 km  (106.6999993, 10.7760007)
d279959       0.0565 km  (106.7005143, 10.7760565)
d210741       0.0650 km  (106.6994682, 10.7762618)
d380203       0.0695 km  (106.6995165, 10.7764063)
d247456       0.0781 km  (106.7005196, 10.7764823)

Redis không duyệt 500k điểm — nó chỉ quét các ô geohash lân cận. Khoảng cách và geohash cũng có sẵn:

GEODIST drivers tx_ben_thanh tx_gan m  -> 704.5162  (mét)
GEOHASH drivers tx_ben_thanh           -> w3gvk18wf00  (geohash nội bộ)

Đo hiệu năng bằng redis-benchmark (thật) trên 500k tài xế:

$ redis-benchmark -n 20000 -q GEOSEARCH drivers FROMLONLAT ... BYRADIUS 1 km COUNT 20
13.368,98 requests/second, p50 = 3,639 msec
MEMORY USAGE drivers = 44.995.430 byte (~42 MB cho 500.000 tài xế)

Một Redis phục vụ ~13.368 truy vấn không gian/giây, p50 ~3,6ms, trên nửa triệu điểm, chỉ tốn ~42MB. Đây là con số Redis/benchmark tự báo — không phải mô phỏng. Với "tìm tài xế gần" thật, một Redis GEO đã đủ cho một thành phố.

Ảnh chụp bảng kết quả chạy thật trên Redis 7.4.11 500004 tài xế trong GEO index output thật, GEOSEARCH lân cận 2km quanh Bến Thành 5 gần nhất WITHDIST km cộng WITHCOORD tx_ben_thanh 0.0001 km d279959 0.0565 km d210741 0.0650 km d380203 0.0695 km d247456 0.0781 km Redis trả đúng các tài xế gần nhất đã sắp theo khoảng cách không duyệt 500k điểm, GEODIST cộng GEOHASH thật GEODIST drivers tx_ben_thanh tx_gan m trả 704.5162 mét GEOHASH drivers tx_ben_thanh trả w3gvk18wf00 geohash nội bộ, benchmark thật redis-benchmark GEOSEARCH trên 500k tài xế redis-benchmark n 20000 q GEOSEARCH 13368,98 requests per second p50 bằng 3,639 msec MEMORY USAGE drivers bằng 44995430 byte khoảng 42 MB cho 500000 tài xế một Redis phục vụ khoảng 13k truy vấn không gian mỗi giây trên nửa triệu điểm, Uber làm gì thêm với H3 nguồn blog kỹ thuật Uber lục giác H3 chia Trái Đất thành ô lục giác icosahedron 122 ô gốc 12 ngũ giác đều hơn 6 ô kề cách đều tránh méo 41 phần trăm đường chéo lưới vuông geohash nhiều mức 16 độ phân giải res 8 khoảng 0,74 km2 mỗi ô chia 7 ô con phân cấp

Hình 2: Chạy thật trên Redis — GEOSEARCH trả lân cận đã sắp theo khoảng cách (không duyệt 500k điểm), GEODIST 704,5m, GEOHASH w3gvk18wf00; redis-benchmark ~13.368 truy vấn/giây p50 3,6ms, index ~42MB. Kèm cách Uber H3 dùng ô lục giác.

Vì sao Uber tự xây H3 (lục giác) thay vì dùng geohash

Redis GEO dùng geohash (ô vuông). Uber tự xây H3 — lưới lục giác phân cấp — rồi mã nguồn mở. Theo blog kỹ thuật Uber, lý do:

  • Khoảng cách tới các ô kề đều nhau. Ô vuông có 4 hàng xóm cạnh (gần) và 4 hàng xóm góc (xa hơn ~41%) — méo theo hướng. Lục giác có 6 hàng xóm cách đều, nên tìm bán kính và gộp không gian không lệch hướng.
  • Phân cấp đa độ phân giải. H3 có 16 mức; res 8 mỗi ô ~0,74 km²; một ô chia thành 7 ô con — nhìn cùng dữ liệu ở nhiều mức (thành phố → khu phố → góc đường).
  • Một lưới cho mọi bài toán. Cùng hệ ô phục vụ ghép tài xế, surge pricing, heatmap nhu cầu, dự báo — mọi phân tích không gian nói chung một "ngôn ngữ ô".

Nói cách khác: Redis GEO đủ cho tìm lân cận; Uber cần thêm phân tích không gian đa mức chính xác nên phải có H3. Cả hai chung một nguyên lý gốc — gán điểm vào ô — mà demo Redis ở trên minh hoạ trực tiếp.

Đánh đổi cần cân nhắc

Cỡ ô/bán kính là đánh đổi. Bán kính lớn thì GEOSEARCH phải quét nhiều ô geohash hơn (chậm hơn); dữ liệu dày thì mỗi ô nhiều ứng viên. Với H3, chọn resolution (mức ô) là quyết định tương tự — phải khớp bán kính tìm điển hình, đo trên phân bố thật.

Vị trí luôn động — chi phí cập nhật cũng đáng kể. Tài xế di chuyển nên phải GEOADD lại liên tục (Redis xử lý cập nhật tốt, nhưng lưu lượng ghi là thật). Ở quy mô toàn cầu, đây là một dòng dữ liệu lớn cần shard theo vùng — một Redis một thành phố như demo, không phải một Redis cho cả thế giới.

Redis GEO vs cơ sở dữ liệu không gian. Nếu bạn cần truy vấn không gian phức tạp (đa giác, join không gian, bền vững) thì PostGIS mạnh hơn. Redis GEO thắng ở tốc độ tìm lân cận đơn giản trong bộ nhớ — đúng nhu cầu ghép tài xế thời gian thực, chưa chắc là nhu cầu của bạn.

Ba ý mang về

  1. "Tìm cái gì gần tôi" ở quy mô lớn không được là O(N): gán mỗi vị trí vào một ô (geohash/H3) rồi chỉ xét ô lân cận — Redis GEO làm sẵn điều này, đo thật phục vụ ~13.368 truy vấn/giây (p50 3,6ms) trên 500k tài xế chỉ với ~42MB.
  2. Chỉ mục không gian là công cụ có sẵn, không phải thứ phải tự viết: GEOADD/GEOSEARCH/GEODIST của Redis (dựa trên geohash + sorted set) trả lân cận đã sắp theo khoảng cách — dựng một chỉ mục thật chỉ vài lệnh.
  3. Uber tự xây H3 vì cần hơn "tìm lân cận": ô lục giác cho khoảng cách tới ô kề đều nhau (tránh méo ~41% của lưới vuông) và phân cấp đa độ phân giải, phục vụ ghép tài xế + surge + heatmap trên một lưới — nhưng cùng nguyên lý gán-điểm-vào-ô mà Redis GEO minh hoạ.

Nguồn

Phần sau ta sang bài toán dựng dòng thời gian (feed) như Twitter/X — cũng dựng thật trên Redis: fanout khi ghi hay khi đọc, và vì sao "người nổi tiếng" phá vỡ giải pháp ngây thơ.