Tìm kiếm gần (proximity search)

Proximity search là gì và mô hình cốt lõi

Proximity search trả lời câu hỏi "cho tôi các đối tượng nằm trong bán kính R quanh điểm (lat, lng)", thường kèm sắp xếp theo khoảng cách và giới hạn số kết quả. Đối tượng có thể là nhà hàng, cây ATM, tài xế đang rảnh hay shipper đang giao hàng.

Cách ngây thơ là lưu lat, lng vào hai cột rồi viết:

SELECT id FROM places
WHERE lat BETWEEN :lat - 0.05 AND :lat + 0.05
  AND lng BETWEEN :lng - 0.05 AND :lng + 0.05;

Câu này chạy được với vài chục nghìn dòng. Với hàng trăm triệu dòng thì không ổn: index B-tree trên lat chỉ thu hẹp được một chiều. Database lấy ra mọi điểm trong dải vĩ độ (một dải chạy vòng quanh trái đất) rồi mới lọc tiếp theo kinh độ. Sách MongoDB cũng lưu ý truy vấn có hai khoảng (range) gần như luôn buộc dùng kế hoạch kém hiệu quả, và ở bản sách mỗi truy vấn chỉ dùng được một index.¹ Yelp trong Grokking cũng bắt đầu từ cách lưu lat/long vào bảng rồi chỉ ra điểm yếu: vùng đông dân có quá nhiều địa điểm, vùng thưa lại phải mở rộng bán kính.²

Ý tưởng chung của mọi giải pháp: biến không gian hai chiều thành các ô (cell) có mã định danh, sao cho các điểm gần nhau thường có mã giống nhau hoặc nằm trong vài ô lân cận. Khi đó câu hỏi "gần tôi" trở thành "lấy các điểm thuộc ô của tôi và các ô xung quanh", một phép tra cứu theo key mà index thông thường làm rất tốt. Grokking Yelp làm đúng như vậy: chia bản đồ thành các segment, chỉ tìm trong vài segment gần nhất, rồi tính khoảng cách từ điểm tìm tới từng địa điểm ứng viên để hiển thị cho người dùng.² Seven Databases mô tả index 2d của MongoDB là một dạng geohash giúp tìm nhanh các giá trị lân cận.³

Có hai nhóm cách chia ô:

• Lưới cố định: geohash, S2, H3. Ô có kích thước định trước theo cấp độ (level, resolution). Mã ô tính được từ tọa độ bằng một hàm thuần, không cần trạng thái.⁴ Phiên bản đầu của Yelp trong Grokking cũng là lưới cố định (segment 5 × 5 dặm), và cách này bị chê vì mật độ địa điểm không đều.²
• Chia theo mật độ: quadtree, R-tree, k-d tree. Vùng đông điểm được chia nhỏ hơn vùng thưa. Cây phải được xây và cập nhật khi dữ liệu thay đổi.⁵

Các cách chia không gian

Geohash

Geohash xen kẽ các bit của kinh độ và vĩ độ (chia đôi khoảng giá trị liên tục), rồi mã hóa base32, mỗi ký tự mang 5 bit. Chuỗi càng dài, ô càng nhỏ. Hai điểm có chung tiền tố dài thì nằm trong cùng một ô lớn.

Ưu điểm lớn nhất: geohash là một chuỗi, nên lưu được ở bất kỳ đâu có index chuỗi (Postgres, DynamoDB, Cassandra, Redis). Truy vấn theo tiền tố LIKE 'w3gv%' dùng được B-tree.⁶

Nhược điểm cần nhớ là vấn đề biên. Hai điểm cách nhau 10 m nhưng nằm hai bên ranh giới ô có thể có geohash khác nhau từ ký tự đầu. Vì vậy truy vấn luôn lấy ô hiện tại cộng 8 ô lân cận (tổng 9 ô), rồi lọc lại bằng khoảng cách thật. Ngoài ra ô geohash không đều: càng xa xích đạo, ô càng hẹp theo chiều ngang.⁶

Quadtree

Quadtree bắt đầu bằng một ô bao toàn bản đồ. Khi một ô chứa quá N điểm (Grokking dùng ví dụ 500 địa điểm mỗi lá), ô đó chia thành 4 ô con. Kết quả: trung tâm Quận 1 có các ô rất nhỏ, vùng ven biển có ô rất lớn, nhưng mỗi lá chứa số điểm tương đương. Truy vấn đi từ gốc xuống lá chứa tọa độ người dùng, rồi mở rộng sang lá lân cận (nối với nhau bằng danh sách liên kết đôi, hoặc đi lên nút cha rồi xuống nút anh em) cho tới khi đủ kết quả.⁵

Grokking ước tính cho Yelp với 500 triệu địa điểm: mỗi địa điểm lưu PlaceID, lat, lng (3 × 8 B), tổng khoảng 12 GB, cộng phần node trong khoảng 10,67 MB, tổng cỡ 12,01 GB. Sách kết luận một server giữ được toàn bộ cây, và ta nhân bản cây ra nhiều server (leader nhận ghi, follower phục vụ đọc) để tăng tính sẵn sàng và chia tải đọc; key-value store giúp dựng lại cây khi mất.⁷⁸

Điểm yếu của quadtree là cập nhật. Grokking Uber chỉ ra: khi tài xế đổi vị trí phải tìm ô cũ, xóa khỏi đó, chuyển sang ô đúng, và có thể phải chia lại ô nếu vượt giới hạn. Việc này tốn thời gian khi mọi tài xế cập nhật mỗi 4 giây.⁹

S2 và H3

S2 (Google) chiếu trái đất lên các mặt của một khối lập phương, rồi đánh số các ô theo đường cong Hilbert. Đường cong Hilbert giữ tính lân cận tốt hơn geohash: các ô gần nhau trên bản đồ thường có id gần nhau, nên một vùng tròn được phủ bằng vài dải id liên tục.⁴

H3 (Uber) chia trái đất thành các ô lục giác theo nhiều độ phân giải. Lục giác có ưu điểm là 6 ô lân cận đều cách tâm một khoảng như nhau, không có láng giềng "chéo góc" như ô vuông. Điều này tiện cho tính toán cung cầu theo khu vực, ví dụ giá động khi mưa ở một khu.⁴

Data model và API của các công cụ phổ biến

Trong phỏng vấn, bạn hiếm khi phải tự cài quadtree. Ba công cụ sau bao phủ phần lớn tình huống.

Redis GEO

Redis lưu điểm GEO trong một sorted set, score là geohash của tọa độ. Vì vậy mọi lệnh sorted set đều dùng được, và một lệnh tìm theo bán kính chỉ là vài lần quét dải score.¹⁰ Sorted set (ZSET) là cấu trúc có member duy nhất kèm score dạng số thực, truy cập được theo member hoặc theo thứ tự score.¹¹

Lệnh đầu chạy mỗi khi tài xế gửi vị trí (4 giây một lần). Lệnh sau tìm 20 tài xế gần nhất trong 2 km.

GEOADD drivers:hcm 106.7009 10.7769 driver:812
GEOSEARCH drivers:hcm FROMLONLAT 106.7020 10.7750 BYRADIUS 2 km ASC COUNT 20 WITHDIST

Redis GEO không tự xóa điểm cũ. Nếu tài xế tắt app, điểm vẫn còn đó, vì Redis chỉ cho hết hạn cả key chứ không hết hạn từng phần tử trong ZSET; Redis in Action vì lý do này dùng ZSET kèm timestamp.¹² Cách hay dùng: giữ thêm một sorted set drivers:lastseen với score là timestamp, định kỳ ZRANGEBYSCORE để tìm tài xế im lặng quá 30 giây và ZREM họ khỏi cả hai set.

PostGIS

PostGIS là extension của PostgreSQL. Kiểu geography tính khoảng cách trên mặt cầu theo mét, index GiST (dựa trên R-tree) hỗ trợ cả lọc bán kính lẫn tìm k láng giềng gần nhất.¹³ Seven Databases minh họa cùng ý tưởng với extension cube của Postgres: điểm là vector n chiều, tìm láng giềng gần nhất bằng cách thu hẹp về một hình hộp bao quanh điểm rồi mới tính khoảng cách, thay vì tính cho mọi dòng.¹⁴

CREATE TABLE places (
  id bigint PRIMARY KEY,
  name text,
  category text,
  rating numeric(2,1),
  geom geography(Point, 4326)
);
CREATE INDEX places_geom_idx ON places USING gist (geom);

SELECT id, name, ST_Distance(geom, :me) AS meters
FROM places
WHERE category = 'pho'
  AND ST_DWithin(geom, :me, 2000)
ORDER BY geom <-> :me
LIMIT 20;

Điểm mạnh của PostGIS là kết hợp điều kiện không gian với mọi điều kiện SQL khác (category, giờ mở cửa, rating) trong một truy vấn, có transaction và join.

Elasticsearch geo_point

Elasticsearch có kiểu geo_point. Lợi thế: ghép lọc địa lý với full-text search và chấm điểm. Ví dụ "bún bò" gần tôi, ưu tiên quán rating cao và gần hơn.¹⁵ Grokking Distributed Search mô tả inverted index là nền của full-text search.¹⁶

{
  "query": {
    "bool": {
      "must": { "match": { "name": "bún bò" } },
      "filter": { "geo_distance": { "distance": "3km", "location": { "lat": 10.7769, "lon": 106.7009 } } }
    }
  },
  "sort": [{ "_geo_distance": { "location": { "lat": 10.7769, "lon": 106.7009 }, "order": "asc" } }]
}

MongoDB 2dsphere

MongoDB có index 2dsphere cho bản đồ mặt cầu (điểm, đường, đa giác theo GeoJSON) và 2d cho mặt phẳng. Có ba nhóm truy vấn: giao nhau, nằm trong, và gần ($near, luôn trả kết quả từ gần tới xa). Có thể ghép index địa lý với trường thường, ví dụ tags + location, để lọc "pizza" trong một khu.¹⁷

Con số và sizing

Các con số dưới đây là ước tính để nói trong phỏng vấn (giả định của khoá học), cần đo lại với dữ liệu thật.

Ví dụ 1: tài xế xe ôm công nghệ

• 300.000 tài xế online lúc cao điểm, gửi vị trí mỗi 4 giây.
• Ghi: 300.000 / 4 = 75.000 cập nhật/s. Chu kỳ 4 giây lấy từ Grokking Uber.⁹
• Đọc: 20.000 lượt đặt xe/phút lúc cao điểm, mỗi lượt vài lần tìm kiếm khi mở rộng bán kính, khoảng 1.000 truy vấn/s.
• RAM Redis: 300.000 × (key 20 B + member 30 B + ~100 B overhead) × 1,3 ≈ 60 MB. Rất nhỏ. Hệ số 1,3 và các số liệu đầu vào là quy tắc ước lượng của khoá học.¹⁸

Dung lượng không phải vấn đề. Vấn đề là thông lượng ghi. Redis in Action nêu Redis làm được khoảng 100.000 thao tác mỗi giây trên phần cứng gần đây, nên 75.000 cập nhật/s cộng thao tác dọn dẹp đã chạm ngưỡng.¹⁹ Cách giải: shard theo thành phố (drivers:hn, drivers:hcm, drivers:dn), mỗi key nằm trên node riêng. Thành phố quá lớn thì chia tiếp theo geohash cấp 4 hoặc 5. Chia theo vùng như vậy có rủi ro điểm nóng mà Grokking Yelp cũng nêu khi phân vùng theo region.²⁰

Ví dụ 2: tìm địa điểm kiểu Yelp

• 200 triệu địa điểm, mỗi ngày thêm hoặc sửa khoảng 100.000 (giả định của khoá học; Grokking Yelp dùng 500 triệu địa điểm).⁷
• Ghi: khoảng 1 lần/s. Gần như bằng không.
• Đọc: 100 triệu DAU × 5 lần tìm/ngày / 86.400 ≈ 5.800 QPS trung bình, cao điểm ×3 ≈ 17.000 QPS.
• Dữ liệu chỉ mục: 200 triệu × 24 B ≈ 4,8 GB cho phần tọa độ (24 B = PlaceID, lat, lng, mỗi trường 8 B, theo Grokking Yelp).⁷ Thông tin chi tiết (tên, ảnh, review) nằm ở database khác.

Ở đây bài toán là đọc. Postgres + PostGIS với vài read replica có thể đủ (ước lượng, cần load test). Cộng thêm cache theo ô (key = geohash cấp 5 + category) vì nhiều người ở cùng khu vực hỏi cùng một câu; Grokking Yelp cũng dùng cache cho địa điểm phổ biến.²⁰ Tỷ lệ cache hit cao vì địa điểm gần như không đổi.

Chọn công cụ: nhiều ghi hay nhiều đọc

Đây là câu hỏi quyết định thiết kế. Hãy hỏi người phỏng vấn đối tượng thay đổi vị trí thường xuyên đến đâu trước khi chọn.

Dữ liệu ghi liên tục (tài xế, shipper, người chạy bộ). Chọn cấu trúc mà cập nhật một điểm có chi phí O(log n) và không cần tái cấu trúc: Redis GEO, hoặc hash table driverId → cellId cộng một tập điểm cho mỗi cell. Grokking ch.30 mô tả đúng cách tách này: một hash table nhận vị trí mới mỗi 4 giây, còn quadtree chỉ được làm mới mỗi 10 đến 15 giây. Người dùng thấy vị trí trễ vài giây, đổi lại hệ thống tốn ít tài nguyên và thời gian hơn. Sách cũng nêu giá trị trong hash table (đặt trong Redis) được chép sang kho bền mỗi 10 đến 15 giây.⁹

Dữ liệu chủ yếu để đọc (nhà hàng, cửa hàng, khách sạn). Chọn cấu trúc tối ưu cho truy vấn phức tạp: PostGIS nếu cần lọc nhiều điều kiện có cấu trúc, Elasticsearch nếu có tìm theo từ khóa và xếp hạng, quadtree trong RAM nếu tải đọc cực lớn và bạn muốn tự kiểm soát. Việc xây lại index mất vài phút hay vài giờ không sao vì dữ liệu ít đổi (Grokking Yelp cập nhật segment mỗi tháng vì địa điểm mới hiếm).²¹

Đánh giá các công cụ trong bảng trên (ngoài các điểm đã dẫn) là nhận định tổng hợp.²²

Vận hành ở quy mô nhỏ và lớn

Giai đoạn nhỏ (một thành phố, vài nghìn tài xế, vài trăm nghìn địa điểm). Một Postgres có PostGIS lo được cả hai việc. Một Redis managed nhỏ cho vị trí realtime. Chi phí vài chục USD mỗi tháng (ước tính, cần kiểm tra giá hiện hành). Không cần S2 hay H3.²²

Giai đoạn vừa (nhiều thành phố). Shard vị trí realtime theo thành phố (chia theo vùng là một dạng key-range sharding²³). Mỗi thành phố là một key hoặc một nhóm key trên Redis Cluster. Địa điểm: Postgres primary + 2 đến 3 read replica, cache kết quả theo ô trong Redis với TTL vài phút. Nếu có tìm theo tên, đồng bộ dữ liệu sang Elasticsearch qua change data capture; Microservices Patterns mô tả đúng mẫu này: một service subscribe sự kiện và cập nhật database thiết kế cho truy vấn địa lý.²⁴

Giai đoạn lớn (cả nước hoặc nhiều quốc gia).

• Dispatch tài xế tách thành dịch vụ riêng, giữ vị trí trong RAM theo vùng H3 hoặc S2, mỗi instance phụ trách một tập cell. Vị trí đi qua Kafka để các dịch vụ khác (ETA, giá động, lưu lịch sử chuyến) đọc độc lập.
• Lịch sử vị trí lưu ở kho rẻ hơn (Cassandra, time-series database, object storage), không nằm trong Redis.
• Địa điểm dùng Elasticsearch nhiều shard hoặc quadtree service riêng có replica, như Grokking ch.29 mô tả: các QuadTree server giữ cây trong RAM, một aggregator gom kết quả, và cây được dựng lại từ key-value store khi server chết.²¹

Vài điểm vận hành hay bị bỏ qua:

• Dọn điểm cũ. Redis GEO không có TTL cho từng member. Phải có job dọn hoặc dùng key theo phút rồi để key cũ hết hạn.¹²
• Điểm nóng. Sân bay Tân Sơn Nhất lúc 23h có hàng nghìn tài xế trong vài ô. Shard theo ô cố định sẽ dồn tải vào một node. Cân nhắc chia nhỏ ô ở khu vực đó (quadtree tự chia khi vượt 500 điểm⁵) hoặc cache kết quả vài giây.
• Mở rộng bán kính. Nếu bán kính 1 km không có kết quả, tăng lên 2 km rồi 5 km. Giới hạn số lần mở rộng để tránh truy vấn quét cả thành phố. Grokking Yelp nêu đúng nhu cầu mở rộng bán kính ở vùng thưa.²

Điểm nói trong phỏng vấn

1. Hỏi tỷ lệ ghi đọc trước. "Đối tượng có di chuyển không, cập nhật mấy giây một lần?" Câu trả lời quyết định bạn đi hướng Redis GEO trong RAM hay index trên đĩa.
2. Giải thích tại sao index thường không đủ. B-tree chỉ thu hẹp một chiều. Cần biến hai chiều thành một chiều (geohash, S2) hoặc dùng cây không gian (R-tree, quadtree).
3. Nhắc vấn đề biên. Luôn truy vấn ô hiện tại và các ô lân cận, sau đó lọc lại bằng khoảng cách thật.
4. Tính số. Ghi = số đối tượng / chu kỳ cập nhật. Với 300.000 tài xế, 4 giây một lần là 75.000 ghi/s, vượt dần khả năng một node Redis, nên shard theo thành phố.
5. Tách vị trí hiện tại và lịch sử. Vị trí hiện tại ở RAM, lịch sử ở kho rẻ, nối với nhau qua Kafka.
6. Nêu trade-off độ tươi. Chấp nhận vị trí trễ vài giây để giảm tải, như cách Grokking cập nhật quadtree mỗi 15 giây thay vì 4 giây.⁹

Các bài liên quan: Redis cho chi tiết sorted set, Sharding cho cách chia theo vùng, Database index cho lý do B-tree không đủ với dữ liệu hai chiều.

Nguồn trích dẫn

1. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.5 Indexing · mục "Using Compound Indexes" (truy vấn hai khoảng) và "OR queries" (một index mỗi truy vấn, theo bản sách). ↩

2. Grokking Modern System Design · ch.29 Design Yelp · mục "Searching", "Searching using segments". ↩ ↩² ↩³ ↩⁴

3. Seven Databases in Seven Weeks (file .zip, tải về giải nén) · ch.5 MongoDB · Day 3 · mục "GeoSpatial Queries" (index 2d dạng geohash). ↩

4. Chưa có nguồn trong thư viện: thư viện không có sách về S2, H3 hay lưới cố định; chỉ nêu khái niệm cơ bản, không đưa số liệu sản phẩm. ↩ ↩² ↩³

5. Grokking Modern System Design · ch.29 Design Yelp · mục "Dynamic segments", "Searching using a QuadTree" (tách nút khi vượt 500 địa điểm, nối láng giềng bằng danh sách liên kết đôi). ↩ ↩² ↩³

6. Chưa có nguồn trong thư viện: thư viện không có sách giải thích chi tiết geohash (chỉ Seven Databases nhắc geohash ở mức khái niệm); các ý về ô lân cận và kích thước ô là kiến thức chung, cần kiểm chứng. ↩ ↩²

7. Grokking Modern System Design · ch.29 Design Yelp · mục "Storage space estimation for QuadTrees" (500 triệu địa điểm, 12 GB, 10,67 MB). ↩ ↩² ↩³

8. Grokking Modern System Design · ch.29 Design Yelp · mục "Ensuring availability" (nhân bản QuadTree, leader-follower, dựng lại từ key-value store). ↩

9. Grokking Modern System Design · ch.30 Design Uber · mục "Detailed Design of Uber" · "QuadTree map service" và "Cache" (hash table 4 giây, QuadTree 10–15 giây). ↩ ↩² ↩³ ↩⁴

10. Chưa có nguồn trong thư viện: Redis in Action là bản cũ chưa có các lệnh GEO; chỉ nêu cách dùng cơ bản. ↩

11. Redis in Action · ch.1 · §1.2.5 Sorted sets in Redis (tr. 13–14). ↩

12. Redis in Action · ch.3 · §3.7.3 Expiring keys (tr. 61). ↩ ↩²

13. Chưa có nguồn trong thư viện: thư viện không có sách về PostGIS hay index GiST/R-tree cho địa lý; chỉ nêu khái niệm cơ bản. ↩

14. Seven Databases in Seven Weeks (file .zip, tải về giải nén) · ch.2 PostgreSQL · Day 3 · mục "Genres as a Multidimensional Hypercube" (cube, nearest-neighbor, bounding cube). ↩

15. Chưa có nguồn trong thư viện: thư viện không có sách về geo_point của Elasticsearch; chỉ nêu khái niệm cơ bản. ↩

16. Grokking Modern System Design · ch.21 Distributed Search · mục "Inverted index". ↩

17. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.6 Special Index and Collection Types · mục "Geospatial Indexing", "Types of Geospatial Queries", "Compound Geospatial Indexes" (tr. 120–122). ↩

18. Quy tắc ước lượng của khoá học · bài Chọn server. ↩

19. Redis in Action · ch.6 · §6.2.2 Simple locks (tr. 120). ↩

20. Grokking Modern System Design · ch.29 Design Yelp · mục "Data partitioning" (chia theo region gặp điểm nóng, chọn chia theo PlaceID, cache địa điểm phổ biến). ↩ ↩²

21. Grokking Modern System Design · ch.29 Design Yelp · mục "Design" · "Components" và "Workflow" (segments producer, QuadTree servers, aggregators, key-value store; cập nhật segment mỗi tháng). ↩ ↩²

22. Chưa có nguồn trong thư viện: so sánh điểm mạnh yếu giữa các công cụ địa lý, hành vi vacuum của Postgres và chi phí vận hành là nhận định tổng hợp, cần kiểm chứng. ↩ ↩²

23. Grokking Modern System Design · ch.9 Databases · mục "Sharding" (key-range based sharding). ↩

24. Microservices Patterns (file .zip, tải về giải nén) · ch.7 · §7.2 Using the CQRS pattern (ví dụ Available Restaurants Service). ↩