Tìm địa điểm quanh đây
Hiểu đề
Yêu cầu chức năng
- Người dùng có thể tìm địa điểm quanh vị trí hiện tại hoặc một khu vực trên bản đồ, trong bán kính chọn được
- Người dùng có thể lọc theo danh mục, từ khóa, mức giá, đang mở cửa và điểm tối thiểu
- Người dùng có thể xem chi tiết địa điểm: thông tin, ảnh, điểm trung bình, danh sách review
- Người dùng có thể viết review gồm điểm 1-5, nội dung và ảnh; mỗi người một review cho một địa điểm
- Chủ quán có thể thêm và sửa thông tin địa điểm (qua kiểm duyệt)
Yêu cầu phi chức năng
- Tìm quanh đây p95 < 200 ms
- Đọc gấp khoảng 400 lần ghi: 20 triệu request so với 50.000 review mỗi ngày ở 1 triệu DAU
- Review mới hiện ngay với người viết, có mặt trong kết quả tìm kiếm và điểm trung bình trong ≤ 1 phút
- Giờ trưa và tối tải gấp 5 lần trung bình
- Độ sẵn sàng 99,9%; ảnh review không bao giờ mất
Ngoài phạm vi: Đặt bàn, đặt món, giao hàng; Bản đồ và chỉ đường (dùng Google Maps / Mapbox / OpenStreetMap); Quảng cáo trả tiền để lên đầu kết quả; Nhắn tin giữa khách và quán.
Thực thể và API
| Method | Endpoint | Ghi chú |
|---|---|---|
| GET | /v1/places/search?lat=&lng=&radius=2000&q=&category=&price_max=&open_now=&min_rating=&cursor= | Tìm quanh đây, trả 20 địa điểm kèm khoảng cách, điểm, ảnh thumbnail. |
| GET | /v1/places/{id} | Chi tiết địa điểm. Cache ở Redis và CDN ngắn hạn. |
| GET | /v1/places/{id}/reviews?sort=new|top&cursor= | Danh sách review phân trang theo cursor. |
| POST | /v1/places/{id}/reviews | Viết hoặc sửa review: {rating, text, photoIds[]}. Header Idempotency-Key. |
| POST | /v1/uploads | Xin presigned URL để client tải ảnh thẳng lên S3. |
| POST | /v1/places | Chủ quán thêm địa điểm, trạng thái PENDING chờ kiểm duyệt. |
Thiết kế tổng thể
Đi lần lượt từng yêu cầu chức năng. Mục tiêu ở đây là chạy đúng, việc tối ưu để dành cho phần đào sâu.
1) Người dùng có thể tìm địa điểm quanh đây theo bộ lọc
Tọa độ người dùng được đổi thành một vùng tìm kiếm, index không gian trả về các địa điểm nằm trong vùng, sau đó lọc theo điều kiện và sắp theo khoảng cách kết hợp điểm. Khu vực đông người được cache theo ô lưới.
- 1Client gửi GET /v1/places/search?lat=10.776&lng=106.700&radius=2000&q=bún bò&open_now=true
- 2API tính ô geohash của vị trí, xem cache Redis cho (ô, bộ lọc chuẩn hóa)
- 3Cache trượt thì hỏi index không gian (PostGIS ST_DWithin ở mức nhỏ, Elasticsearch geo_distance ở mức lớn) kèm điều kiện lọc
- 4Tính khoảng cách chính xác tới người dùng, sắp theo điểm tổng hợp, cắt 20 kết quả
- 5Trả danh sách, ảnh thumbnail lấy từ CDN
Nguồn: Grokking Modern System Design · ch.29 Design a Proximity Service (Yelp) ↗ · mục "Searching" và "Search using a QuadTree" ; Chưa có nguồn trong thư viện: PostGIS và Elasticsearch geo_distance không có trong sách thư viện, chỉ nêu khái niệm
2) Người dùng có thể xem chi tiết địa điểm và review
Trang chi tiết được đọc rất nhiều và ít đổi, nên cache theo place_id. Review phân trang theo cursor, sắp mới nhất hoặc hữu ích nhất.
- 1Client gọi GET /v1/places/{id}
- 2API đọc Redis (hash place:{id}), trượt thì đọc DB replica rồi ghi lại cache TTL 10 phút
- 3Điểm trung bình = rating_sum / review_count lấy sẵn trên hàng place, không tính lại từ bảng review
- 4Client gọi /reviews?cursor= khi cuộn, ảnh tải qua CDN
Nguồn: Grokking Modern System Design · ch.29 Design a Proximity Service (Yelp) ↗ · mục "Evaluation" (cache địa điểm phổ biến) ; Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "Writing policies" và "Cache invalidation" (TTL)
3) Người dùng có thể viết review kèm ảnh
Ảnh đi thẳng lên S3 bằng presigned URL. Review và việc cộng dồn điểm nằm trong cùng một transaction nên điểm trung bình luôn khớp với bảng review. Cập nhật index tìm kiếm và cache đi sau qua outbox.
- 1Client xin presigned URL, tải ảnh lên S3, nhận photoIds
- 2POST /reviews: trong 1 transaction INSERT review (UNIQUE place_id, user_id) và UPDATE places SET rating_sum = rating_sum + ?, review_count = review_count + 1
- 3Cùng transaction ghi outbox review_created
- 4Worker đọc outbox: xóa cache place:{id}, cập nhật rating trong index tìm kiếm, resize ảnh, chạy lọc spam
Nguồn: Microservices Patterns ↗ (.zip) · ch.3 · §3.3.7 Transactional messaging ; Grokking Modern System Design · ch.20 Blob Store ↗ · mục "Detailed design" và "Stream a file"
Hạ tầng theo quy mô
Cùng một sản phẩm, ba mức người dùng. Chọn từng mức để xem sơ đồ, phép tính và cấu hình server thay đổi thế nào.
Ứng dụng review quán ăn cho một thành phố. Hai instance Node, một Postgres có PostGIS, ảnh trên S3 qua CDN. Tìm quanh đây là một câu ST_DWithin trên index GiST.
Ước lượng
- Request: 10.000 × 20 / 86.400 ≈ 2,3 req/s, giờ trưa ×10 ≈ 23 req/s
- API: ceil(23 / (1.000 × 0,6)) = 1 → lấy tối thiểu 2 instance để dự phòng
- Địa điểm: 50.000 × 1.296 B (số liệu Grokking ch.29) ≈ 65 MB
- Review: 10.000 × 0,05 = 500 review/ngày × 537 B ≈ 269 KB/ngày ≈ 98 MB/năm
- Ảnh: 500 ảnh/ngày × 500 KB = 250 MB/ngày ≈ 91 GB/năm trên S3
Nguồn con số: Grokking Modern System Design · ch.5 Back-of-the-envelope Calculations ↗ · mục "Standard numbers to remember" và "Requests estimation" ; Grokking Modern System Design · ch.29 Design a Proximity Service (Yelp) ↗ · mục "Storage estimation" (1.296 B mỗi địa điểm, 537 B mỗi review) ; Quy tắc ước lượng của khoá học · /hoc/chon-server
Bảng hạ tầng
| Thành phần | Chọn | Số lượng | Cấu hình | Vì sao |
|---|---|---|---|---|
| API | Node.js (NestJS), Docker trên Cloud Run | 2 | 2 vCPU · 4 GB RAM | 23 req/s đỉnh chỉ cần 1 instance, chạy 2 để không chết khi 1 cái lỗi. |
| Database | PostgreSQL managed + PostGIS | 1 | 2 vCPU · 8 GB · 50 GB SSD | Cả địa điểm và review chưa tới 1 GB; index GiST trả ST_DWithin trên 50.000 điểm trong vài ms. |
| Lưu ảnh | S3 / GCS, presigned URL | 1 bucket | ≈ 91 GB/năm | Ảnh không bao giờ nằm trong DB; client tải thẳng lên bucket. |
| Resize ảnh | Lambda / Cloud Function dùng sharp | theo sự kiện | 1 GB RAM | 500 ảnh/ngày, chạy khi có file mới, không cần server thường trực. |
| CDN | Cloudflare / CloudFront | 1 | Cache ảnh và thumbnail | Danh sách kết quả có 20 thumbnail, CDN giúp tải nhanh và rẻ. |
| Bản đồ | Mapbox / Google Maps SDK / OpenStreetMap | 1 | Dịch vụ bên ngoài | Hiển thị bản đồ và ghim quán phía client, không tự làm. |
- Điểm xuất phát: một API, một Postgres có PostGIS, ảnh trên S3
- Điểm trung bình cộng dồn trên hàng place ngay từ đầu
- Tìm theo tên bằng unaccent + pg_trgm, chưa cần hệ thống tìm kiếm riêng
Khi mở ra cả nước với 2 triệu địa điểm và giờ trưa hơn 1.000 req/s, Postgres vừa gánh tìm kiếm có nhiều bộ lọc vừa gánh ghi review, còn các ô trung tâm bị hỏi lặp lại liên tục. Cần cache theo ô và một index tìm kiếm riêng.
Cấu hình và chi phí là ước lượng để học và trình bày trong phỏng vấn. Xem cách tính ở bài Chọn server.
So sánh nhanh ba mức
| Thành phần | Mức 1 | Mức 2 | Mức 3 |
|---|---|---|---|
| Người dùng | 10.000 DAU, 50.000 địa điểm trong một thành phố | 1 triệu DAU, 2 triệu địa điểm cả nước | 60 triệu DAU, 500 triệu địa điểm toàn cầu (số liệu Grokking ch.29) |
| Chi phí | ≈ 50–150 USD/tháng (ước lượng, chưa tính phí API bản đồ) | ≈ 3.000–6.000 USD/tháng (ước lượng, phần lớn là OpenSearch và CDN) | ≈ 80.000–200.000 USD/tháng (ước lượng, CDN và lưu trữ ảnh chiếm phần lớn) |
| API | Node.js (NestJS), Docker trên Cloud Run 2 × 2 vCPU · 4 GB RAM | Node.js (NestJS), container autoscale 2–4 (autoscale) × 2 vCPU · 4 GB RAM | Node.js trên Kubernetes, HPA 70 pod (chia 3 region) × 2 vCPU · 4 GB mỗi pod |
| Database | PostgreSQL managed + PostGIS 1 × 2 vCPU · 8 GB · 50 GB SSD | PostgreSQL managed (HA) + PostGIS 1 primary + 1 read replica × 4 vCPU · 16 GB · 200 GB SSD | PostgreSQL + PostGIS phân tán (Citus), shard theo place_id 4 shard × (1 primary + 1 replica) × 8 vCPU · 64 GB · 1 TB SSD |
| Lưu ảnh | S3 / GCS, presigned URL 1 bucket × ≈ 91 GB/năm | S3 / GCS 1 bucket × ≈ 9 TB/năm | S3 nhân bản đa region, resize bằng Lambda multi-region × 3 triệu ảnh × 500 KB = 1,5 TB/ngày ≈ 548 TB/năm |
| Resize ảnh | Lambda / Cloud Function dùng sharp theo sự kiện × 1 GB RAM | Chưa cần | Chưa cần |
| CDN | Cloudflare / CloudFront 1 × Cache ảnh và thumbnail | Cloudflare / CloudFront 1 × ≈ 18 TB/tháng, cache trang quán 60 s | Chưa cần |
| Bản đồ | Mapbox / Google Maps SDK / OpenStreetMap 1 × Dịch vụ bên ngoài | Chưa cần | Chưa cần |
| Redis | Chưa cần | ElastiCache / Memorystore 1 primary + 1 replica × 2 vCPU · 8 GB | Chưa cần |
| Search | Chưa cần | OpenSearch Service: geo_point, analyzer bỏ dấu 3 node × 8 vCPU · 32 GB · 100 GB SSD | OpenSearch, shard theo vùng (routing theo tiền tố geohash) 15 node (5 mỗi region) × 8 vCPU · 32 GB · 500 GB SSD |
| Queue | Chưa cần | Outbox + SQS / Pub/Sub 1 × Managed, có dead-letter queue | Chưa cần |
| Worker | Chưa cần | Node.js consumer 2 × 1 vCPU · 2 GB RAM | Consumer Kafka trên Kubernetes + job đối soát điểm hằng đêm 6 pod × 2 vCPU · 4 GB mỗi pod |
| Edge | Chưa cần | Chưa cần | GeoDNS + CDN đa region (CloudFront / Cloudflare) 3 region × 60.000.000 × 20 × 30 KB ≈ 36 TB ảnh/ngày |
| Redis Cluster | Chưa cần | Chưa cần | ElastiCache Redis Cluster mỗi region 3 shard × (1 primary + 1 replica) × 4 vCPU · 32 GB mỗi node |
| Kafka | Chưa cần | Chưa cần | MSK / Confluent 3 broker × Topic place_events, review_events, RF 3 |
Đào sâu
Mỗi câu hỏi đi từ cách đơn giản đến cách người phỏng vấn mong đợi ở cấp senior.
1) Tìm các địa điểm trong bán kính 2 km quanh người dùng thế nào cho nhanh?
DB chỉ dùng được một index: lấy mọi địa điểm cùng dải vĩ độ (cả một vệt ngang qua nhiều tỉnh) rồi lọc kinh độ, sau đó tính khoảng cách cho từng hàng. Grokking ch.29 nêu đây là cách ngây thơ đầu tiên.
Đánh đổi: Chạy được với vài chục nghìn điểm, chậm dần theo số điểm trên cùng dải vĩ độ.
Nguồn: Grokking Modern System Design · ch.29 Design a Proximity Service (Yelp) ↗ · Points to Ponder trong mục "Searching" (bảng places với index lat/long)
Geohash biến (lat, lng) thành chuỗi, hai điểm gần nhau thường có chung tiền tố. Độ dài 6 ký tự ứng với ô khoảng 1,2 × 0,6 km. Tìm bằng index B-tree thường hoặc Redis GEO trên 9 ô rồi lọc khoảng cách chính xác. Dễ dùng làm key cache và key shard.
Đánh đổi: Ô cố định: trung tâm Quận 1 một ô có hàng nghìn quán, ngoại thành một ô gần như trống, phải tự đổi độ dài tiền tố.
⚠ Chưa có nguồn trong thư viện: geohash không có trong sách thư viện; chỉ phần ô lưới chia bản đồ có ở Grokking ch.29 mục "Searching"
Chia bản đồ thành 4 ô, ô nào quá 500 địa điểm thì chia tiếp, nên chỗ đông có ô nhỏ, chỗ thưa có ô lớn. 500 triệu điểm × 24 B ≈ 12 GB, vừa RAM một server, nhân bản ra nhiều server để đỡ đọc và dựng lại từ DB khi khởi động.
Đánh đổi: Phải tự viết, tự phân phối và đồng bộ cây khi thêm hoặc sửa địa điểm; khởi động lại mất thời gian dựng cây.
Nguồn: Grokking Modern System Design · ch.29 Design a Proximity Service (Yelp) ↗ · mục "Searching" và "Search using a QuadTree" ; Grokking Modern System Design · ch.29 ↗ · mục "Storage space estimation for QuadTrees" (12 GB, 500 điểm mỗi ô lá)
PostGIS với index GiST (cây R-tree) xử lý ST_DWithin trên vài triệu điểm trong vài ms, đúng nguồn sự thật nên không cần đồng bộ. Khi cần kết hợp từ khóa tiếng Việt, nhiều bộ lọc và chấm điểm, dùng Elasticsearch geo_point (cây BKD) đồng bộ qua outbox. Geohash vẫn dùng làm key cache và key định tuyến theo vùng.
Đánh đổi: Elasticsearch thêm độ trễ đồng bộ vài giây và một cụm phải vận hành; chỉ đáng khi PostGIS không còn đủ.
Nguồn: Chưa có nguồn trong thư viện: PostGIS GiST và Elasticsearch geo_point không có trong sách thư viện ; MongoDB: The Definitive Guide 2e ↗ (.zip) · ch.6 · mục "Geospatial Indexing" (khái niệm index không gian)
2) Điểm trung bình và số review phải đúng khi nhiều người review cùng lúc
AVG trên quán có 50.000 review là quét 50.000 hàng cho mỗi lượt xem. Còn đọc-tính-ghi ở app thì hai review cùng lúc đọc cùng một giá trị cũ, một lượt cộng bị mất.
Đánh đổi: Cách đầu đúng nhưng chậm; cách sau nhanh nhưng sai lệch dần không phát hiện được.
⚠ Chưa có nguồn trong thư viện: AVG so với cột cộng dồn là kiến thức DB chung, thư viện chưa có đoạn tương ứng
UPDATE places SET rating_sum = rating_sum + 5, review_count = review_count + 1 là phép cộng nguyên tử nên không mất lượt. Điểm hiển thị = rating_sum / review_count. Sửa review thì cộng phần chênh lệch, xóa thì trừ.
Đánh đổi: Hàng của quán bị khóa ngắn mỗi lần review; quán viral có thể có hàng đợi khóa, và index tìm kiếm vẫn cần cập nhật riêng.
Nguồn: Microservices Patterns ↗ (.zip) · ch.6 · §6.1.3 Handling concurrent updates using optimistic locking
Giữ cộng dồn trong transaction (review và place cùng shard place_id nên vẫn là transaction cục bộ). Index tìm kiếm và cache nhận điểm mới qua outbox, trễ vài giây. Job hằng đêm tính lại từ bảng review để sửa mọi lệch do bug. Khi xếp hạng dùng điểm Bayesian (trộn với điểm trung bình toàn hệ thống theo số review) để quán 1 review 5 sao không vượt quán 2.000 review 4,6 sao. Review bị đánh dấu spam không được cộng.
Đánh đổi: Điểm hiển thị và điểm xếp hạng là hai con số khác nhau, cần giải thích rõ với chủ quán; job đối soát tốn tài nguyên ban đêm.
Nguồn: Microservices Patterns ↗ (.zip) · ch.3 · §3.3.7 Transactional messaging ; Chưa có nguồn trong thư viện: điểm Bayesian không có trong sách thư viện
3) Tìm "bún bò" gần đây, đang mở cửa, giá dưới 50k, từ 4 sao: lọc và xếp hạng thế nào?
Ở Quận 1, bán kính 2 km có thể trả về 5.000 địa điểm, API phải kéo hết về rồi lọc từng điều kiện và tìm chữ "bún bò" bằng includes.
Đánh đổi: Dễ viết nhưng tốn băng thông DB, chậm và không xử lý được gõ không dấu.
⚠ Chưa có nguồn trong thư viện: lọc trong code so với trong DB là nhận định chung
Một câu SQL kết hợp ST_DWithin, category, price_level, điều kiện giờ mở cửa và tìm tên bỏ dấu. Với vài triệu địa điểm vẫn trả trong vài chục ms.
Đánh đổi: Kết hợp nhiều bộ lọc với chấm điểm theo khoảng cách và độ phổ biến trong SQL khó tối ưu và khó đọc.
Nguồn: Seven Databases in Seven Weeks ↗ (.zip) · ch.2 PostgreSQL · §2.4 Day 3: Full-Text and Multidimensions (pg_trgm, fuzzystrmatch) ; Chưa có nguồn trong thư viện: unaccent không có trong sách
Điều kiện cứng (bán kính, category, giá, rating) đặt trong filter để Elasticsearch cache bitset và không tính điểm. "Đang mở cửa" lưu thành các khoảng phút trong tuần (ví dụ thứ 2 6:00-14:00 thành 360-840) và lọc bằng range. Điểm cuối cùng = khớp chữ × decay theo khoảng cách × điểm Bayesian × độ phổ biến. Dữ liệu đồng bộ từ Postgres qua outbox.
Đánh đổi: Kết quả trễ vài giây so với DB và thêm một cụm để vận hành; múi giờ và ngày lễ làm logic giờ mở cửa phức tạp.
Nguồn: Grokking Modern System Design · ch.21 Distributed Search ↗ · mục "Inverted index" ; Chưa có nguồn trong thư viện: Elasticsearch function_score, filter cache không có trong sách
4) Cache khu vực đông người tìm thế nào khi mỗi người đứng một tọa độ khác nhau?
Hai người cách nhau 5 m đã có tọa độ khác nhau, nên tỷ lệ trúng cache gần như bằng 0.
Đánh đổi: Tốn RAM mà không giảm tải.
Nguồn: Grokking Modern System Design · ch.29 Design a Proximity Service (Yelp) ↗ · mục "Finalized design" và "Evaluation" (cache địa điểm phổ biến)
Mọi người trong cùng ô dùng chung một kết quả. API lấy 9 ô quanh vị trí rồi tính lại khoảng cách chính xác và sắp xếp. Bộ lọc được chuẩn hóa (sắp xếp tham số, làm tròn giá) để giảm số tổ hợp.
Đánh đổi: Số tổ hợp bộ lọc × số ô vẫn lớn; kết quả cũ tối đa 5 phút.
Nguồn: Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "Cache invalidation" (TTL) ; Chưa có nguồn trong thư viện: geohash không có trong sách
Lớp 1 cache danh sách place_id và tọa độ của mỗi (ô geohash, category), không phụ thuộc vị trí chính xác hay bộ lọc phụ; API lọc giá, giờ mở cửa và tính khoảng cách trên vài trăm phần tử trong RAM. Lớp 2 cache chi tiết place theo id, xóa khi có sự kiện review hoặc sửa thông tin. Làm nóng trước các ô đông lúc 10:30 và 17:30 (Grokking ch.29 cũng cache địa điểm phổ biến). Trang chi tiết quán cache thêm ở CDN 60 s.
Đánh đổi: Logic lọc nằm ở hai nơi (index và API) phải giữ giống nhau; cần đo tỷ lệ trúng để chọn độ dài geohash.
Nguồn: Grokking Modern System Design · ch.29 ↗ · mục "Finalized design" (cache) ; Grokking Modern System Design · ch.11 Content Delivery Network (CDN) ↗ · mục "Content caching strategies in CDN"
Trong phỏng vấn
- “Tôi bắt đầu bằng PostGIS vì nó là nguồn sự thật và đủ nhanh tới vài triệu điểm; chỉ thêm Elasticsearch khi bộ lọc và tìm chữ phức tạp.”
- “Geohash là công cụ tôi dùng cho key cache và định tuyến theo vùng, còn tìm chính xác vẫn tính khoảng cách thật.”
- “Điểm trung bình được cộng dồn trong cùng transaction với review, rồi đẩy ra index qua outbox và đối soát hằng đêm.”
- “Hệ thống đọc gấp hàng trăm lần ghi nên cache theo ô và CDN cho ảnh mang lại nhiều nhất.”
- Dùng hai index B-tree cho lat và lng rồi nghĩ là đã có index không gian.
- Cache theo tọa độ chính xác của người dùng.
- Tính AVG(rating) mỗi lần xem hoặc đọc-tính-ghi điểm ở tầng app.
- Quên ô lân cận khi dùng geohash: người đứng sát biên ô bỏ lỡ quán cách 100 m.
Đọc thêm
Sách trong thư viện của bạn. Số chương có thể lệch nhẹ so với bản PDF.