Case-Design-Proximity-Service

Case Study: Design a Proximity Service (Nearby Businesses)

“Mỗi ngày hàng trăm triệu người mở Google Maps hỏi: ‘Quán phở nào gần đây nhất?’ — Câu hỏi tưởng đơn giản, nhưng phía sau là một bài toán geospatial indexing phức tạp, nơi toán học gặp engineering ở quy mô hành tinh.”

Tags: system-design proximity-service geospatial geohash quadtree alex-xu case-study vol2 Student: Hieu Prerequisite: Tuan-02-Back-of-the-envelope · Tuan-06-Cache-Strategy · Tuan-07-Database-Sharding-Replication Lien quan: Tuan-05-Load-Balancer · Tuan-09-Rate-Limiter · Tuan-10-Consistent-Hashing · Tuan-13-Monitoring-Observability Reference: Alex Xu, System Design Interview — An Insider’s Guide, Volume 2 — Chapter 1: Proximity Service

---

1. Context & Why — Tại sao Proximity Service quan trọng?

1.1 Analogy — Bài toán đời thường

hãy tưởng tượng 2 tình huống hàng ngày:

Tình huống 1 — Google Maps: Bạn đang ở quận 1 TP.HCM, mở Google Maps và gõ “phở”. Trong vòng 0.5 giây, bản đồ hiện ra 20 quán phở gần nhất, sắp xếp theo khoảng cách. Phía sau cái “0.5 giây” đó là gì? Làm sao từ tọa độ GPS của bạn (10.7769, 106.7009), hệ thống tìm được 20 quán phở trong hàng trăm triệu địa điểm trên thế giới?

Tình huống 2 — Grab tìm tài xế: Bạn đặt Grab, app cần tìm tất cả tài xế trong bán kính 3km quanh vị trí của em. Nhưng tài xế di chuyển liên tục — vị trí của họ thay đổi mỗi 3-5 giây. Hệ thống phải trả lời câu hỏi “ai gần bạn nhất?” cho hàng triệu user đồng thời.

Cả hai tình huống này đều là bài toán Proximity Service — cho một tọa độ (latitude, longitude) và bán kính (radius), tìm tất cả các điểm (businesses, tài xế, bạn bè) trong vùng đó.

1.2 Tại sao bài toán này khó?

Vấn đề	Giải thích	Quy mô
Dữ liệu khổng lồ	200 triệu businesses trên toàn cầu	~200M records
Two-dimensional search	Không thể dùng B-tree index bình thường — latitude và longitude là 2 chiều độc lập	O(N) naive search
Read-heavy	Hàng trăm triệu user search đồng thời, nhưng businesses ít khi thay đổi	Read:Write ~ 1000:1
Low latency	User kỳ vọng kết quả trong < 500ms	p99 < 200ms
Global scale	User và businesses ở khắp thế giới, mỗi region có density khác nhau	Tokyo dense, Sahara sparse

1.3 Real-world Systems sử dụng Proximity Service

Company	Use Case	Scale
Google Maps / Places	Tìm nhà hàng, gas station, ATM	200M+ places
Uber / Grab	Tìm tài xế gần nhất	Millions of active drivers
Yelp	Tìm businesses theo category + location	~200M businesses
Facebook Nearby Friends	Tìm bạn bè đang ở gần	2B+ users
Tinder	Tìm người match trong bán kính	75M+ users
DoorDash	Tìm nhà hàng có delivery	390K+ merchants

---

Step 1 — Understand the Problem & Establish Design Scope

1.1 Clarifying Questions (Câu hỏi làm rõ)

Trong interview, luôn hỏi trước khi thiết kế. Đây là các câu hỏi quan trọng:

Câu hỏi	Trả lời	Ghi chú
User có thể chỉ định bán kính search?	Có — 0.5km, 1km, 2km, 5km, 20km	Default 5km
Radius tối đa là bao nhiêu?	20km	Giới hạn để tránh query quá rộng
Businesses có thể update thông tin?	Có — nhưng thay đổi phản ánh vào ngày hôm sau là chấp nhận được	Near real-time không bắt buộc
User có thể di chuyển và search đồng thời?	Có, nhưng không cần auto-refresh liên tục — chỉ khi user bấm search lại	Khác với Nearby Friends
Cần sắp xếp kết quả theo gì?	Khoảng cách, hoặc ranking/rating	Distance là primary
Business info gồm những gì?	Tên, địa chỉ, tọa độ, category, giờ mở cửa, rating, ảnh	Rich metadata

1.2 Functional Requirements (Yêu cầu chức năng)

• FR1: Cho tọa độ (lat, lng) và bán kính (radius), trả về danh sách businesses trong vùng đó
• FR2: Business owners có thể thêm/sửa/xóa thông tin business (CRUD)
• FR3: Users có thể xem chi tiết business (tên, địa chỉ, rating, giờ mở cửa, ảnh)
• FR4: Kết quả có thể lọc theo category (nhà hàng, cafe, gas station…)

1.3 Non-functional Requirements (Yêu cầu phi chức năng)

Yêu cầu	Mục tiêu	Giải thích
Low Latency	p99 < 200ms cho search	User kỳ vọng kết quả nhanh
High Availability	99.99% uptime	LBS là core feature của Maps
High Scalability	200M DAU, 100M businesses	Global scale
Eventual Consistency	Business updates có thể delay vài phút	Không cần real-time cho business info
Read-heavy	Read QPS >> Write QPS	Search nhiều hơn update

1.4 Capacity Estimation (Ước lượng năng lực)

Assumptions:

Thông số	Giá trị	Giải thích
DAU	200M	Quy mô Google Maps
Businesses	100M	Toàn cầu
Searches/user/day	5	Trung bình
Business updates/day	100K	Thêm/sửa/xóa

QPS Calculation — Search:

$$Totalsearches/day=200M\times 5=1Bsearches/day$$ $$SearchQP{S}_{avg}=\frac{1\times 10^9}{86,400}\approx 11,574searches/s\approx 12KQPS$$ $$SearchQP{S}_{peak}=12K\times 5=60KQPS$$

Nhận xét: 60K peak QPS cho read — đây là read-heavy system. Write QPS chỉ khoảng 1-2 QPS cho business updates. Tỷ lệ Read:Write ~ 60,000:1.

Write QPS — Business Updates:

$$WriteQP{S}_{avg}=\frac{100,000}{86,400}\approx 1.16writes/s$$

Write QPS cực thấp — hoàn toàn có thể handle bởi 1 primary database server.

Storage — Business Data:

$$Businessrecordsize\approx 1KB(metadata)+5KB(imagesrefs)=6KB$$ $$Totalbusinessstorage=100M\times 6KB=600GB$$

Storage — Geospatial Index:

$$Geospatialindexentry\approx 8bytes(business\_id)+8bytes(lat)+8bytes(lng)+12bytes(geohash)=36bytes$$ $$Totalgeospatialindex=100M\times 36bytes=3.6GB$$

Quan trọng: 3.6 GB geospatial index vừa đủ để load toàn bộ vào memory. Đây là insight then chốt — ta có thể build in-memory index (Quadtree) trên 1 server.

Cache Sizing:

$$Hotbusinesses(top20\%)=100M\times 20\%=20Mbusinesses$$ $$Cachesize=20M\times 6KB=120GB$$

Sử dụng Redis cluster với vài node là đủ. Tham chiếu Tuan-06-Cache-Strategy.

Quadtree Memory Estimation (sẽ deep dive ở section 3):

$$Internalnodesize\approx 32bytes(4pointers+metadata)$$ $$Leafnodesize\approx 8bytes(business\_idpointer)\times avg100businesses=800bytes+32bytes=832bytes$$ $$Totalleafnodes\approx \frac{100M}{100}=1Mleaves$$ $$Totalinternalnodes\approx \frac{1M}{3}\approx 333Knodes$$ $$Quadtreememory\approx (333K\times 32)+(1M\times 832)\approx 10.6MB+832MB\approx 843MB$$

Aha Moment: Quadtree cho 100M businesses chỉ chiếm khoảng 843 MB RAM — thoải mái fit trong 1 server có 8 GB RAM. Đây là lý do nhiều hệ thống chọn Quadtree làm in-memory geospatial index.

Tóm tắt Estimation

Metric	Value
Search QPS (peak)	~60K/s
Write QPS (peak)	~5/s
Business data storage	~600 GB
Geospatial index size	~3.6 GB
Cache size (hot data)	~120 GB
Quadtree memory	~843 MB
Read:Write ratio	~60,000:1

---

Step 2 — High-Level Design

2.1 Kiến trúc tổng quan — 2 Service chính

Proximity Service bao gồm 2 loại service có đặc tính hoàn toàn khác nhau:

Service	Chức năng	Đặc tính	Scale strategy
LBS (Location-Based Service)	Nhận tọa độ + radius, trả về businesses gần nhất	Read-heavy, stateless, no write	Horizontal scaling, read replicas
Business Service	CRUD operations cho businesses	Write operations, low QPS	Single primary + replicas

Tại sao tách 2 service? Vì read và write có pattern hoàn toàn khác nhau:

• LBS: 60K QPS, stateless, cần low latency → scale horizontally, đặt sau Load Balancer
• Business Service: 5 QPS, stateful, cần consistency → single primary database

Principle: Tách read path và write path khi chúng có scale requirements khác nhau. Đây là CQRS (Command Query Responsibility Segregation) pattern — một dạng của Tuan-11-Microservices-Pattern.

2.2 High-Level Architecture Diagram

flowchart TB
    subgraph Clients
        Mobile["Mobile App"]
        Web["Web App"]
    end

    LB["Load Balancer<br/>→ [[Tuan-05-Load-Balancer]]"]

    subgraph "Read Path (LBS)"
        LBS1["LBS Instance 1"]
        LBS2["LBS Instance 2"]
        LBSN["LBS Instance N"]
    end

    subgraph "Write Path"
        BS["Business Service"]
    end

    subgraph "Data Layer"
        Primary["Primary DB<br/>PostgreSQL"]
        R1["Read Replica 1"]
        R2["Read Replica 2"]
        RN["Read Replica N"]
    end

    subgraph "Geospatial Index"
        GI["Geohash Index<br/>(in DB read replicas)"]
        QT["Quadtree<br/>(in-memory, per LBS instance)"]
    end

    subgraph "Cache Layer"
        RC["Redis Cluster<br/>Business data cache<br/>Geohash → business_ids cache"]
    end

    Mobile --> LB
    Web --> LB
    LB -->|"GET /nearby"| LBS1 & LBS2 & LBSN
    LB -->|"POST/PUT/DELETE /businesses"| BS

    LBS1 & LBS2 & LBSN --> RC
    LBS1 & LBS2 & LBSN --> R1 & R2 & RN
    LBS1 & LBS2 & LBSN -.-> QT

    BS --> Primary
    Primary -->|"Replication"| R1 & R2 & RN

    R1 & R2 & RN --> GI

    style LB fill:#42a5f5,color:#fff
    style RC fill:#ef5350,color:#fff
    style Primary fill:#66bb6a,color:#fff
    style QT fill:#ffa726,color:#000

2.3 API Design

Search Nearby Businesses:

Field	Type	Description
GET /v1/search/nearby
latitude	double	Vĩ độ của user (-90 đến 90)
longitude	double	Kinh độ của user (-180 đến 180)
radius	int	Bán kính search (meters). Default: 5000. Max: 20000
category	string	(Optional) Filter theo loại business
page_token	string	(Optional) Pagination token

Response:

Field	Type	Description
businesses	array	Danh sách businesses
businesses[].id	string	Business ID
businesses[].name	string	Tên business
businesses[].lat	double	Vĩ độ
businesses[].lng	double	Kinh độ
businesses[].distance	int	Khoảng cách (meters)
businesses[].rating	float	Rating trung bình
next_page_token	string	Token cho trang tiếp theo

Business CRUD:

Endpoint	Method	Description
/v1/businesses	POST	Tạo business mới
/v1/businesses/:id	GET	Xem chi tiết business
/v1/businesses/:id	PUT	Cập nhật business
/v1/businesses/:id	DELETE	Xóa business

2.4 Data Flow — Read vs Write

Read Flow (Search):

1. User gửi request GET /v1/search/nearby?lat=10.77&lng=106.70&radius=5000
2. Load Balancer route đến 1 trong N LBS instances
3. LBS tính geohash từ (lat, lng) và radius → xác định các geohash cells cần query
4. LBS check Redis cache: geohash_cells → list of business_ids
5. Nếu cache hit → lấy business details từ Business Data Cache
6. Nếu cache miss → query Read Replica (geospatial index table)
7. Tính khoảng cách chính xác, lọc businesses ngoài radius
8. Sắp xếp theo distance, trả về kết quả

Write Flow (Update Business):

1. Business owner gửi PUT /v1/businesses/123
2. Load Balancer route đến Business Service
3. Business Service update Primary DB
4. Primary DB replicate sang Read Replicas (async)
5. Cache invalidation: xóa cache entries liên quan
6. Nếu dùng Quadtree: rebuild scheduled (overnight hoặc mỗi vài giờ)

Trade-off: Business updates không phản ánh ngay lập tức trong search results. Delay có thể là vài phút (replication lag) đến vài giờ (quadtree rebuild). Đây là chấp nhận được vì businesses hiếm khi thay đổi vị trí.

---

Step 3 — Design Deep Dive

3.1 Bài toán cốt lõi: Geospatial Indexing

đây là phần khó nhất và quan trọng nhất của bài này. Bài toán cơ bản là:

Cho điểm P(lat, lng) và bán kính r, tìm tất cả businesses B sao cho distance(P, B) ⇐ r.

Cách naive — Two-dimensional search:

Cách đơn giản nhất: query trực tiếp trong database.

SELECT * FROM businesses
WHERE latitude BETWEEN 10.77 - delta AND 10.77 + delta
  AND longitude BETWEEN 106.70 - delta AND 106.70 + delta

Vấn đề: Ngay cả khi có index trên latitude VÀ index trên longitude, database phải:

1. Query index trên latitude → tập A (có thể hàng triệu records)
2. Query index trên longitude → tập B (có thể hàng triệu records)
3. Lấy giao (intersection) A ∩ B → rất chậm!

$$Timecomplexity=O(N_{lat})+O(N_{lng})+O(intersect)$$

Lý do: B-tree index chỉ hiệu quả cho 1 chiều. Khi có 2 chiều độc lập (lat, lng), không có B-tree nào có thể index cả 2 đồng thời một cách hiệu quả.

Đây là lý do ta cần geospatial indexing — các kỹ thuật chuyên biệt để biến bài toán 2 chiều thành bài toán 1 chiều hoặc chia không gian thành các ô (cells) để thu hẹp phạm vi search.

3.2 Approach 1 — Evenly Divided Grid

Ý tưởng: Chia toàn bộ bản đồ thành các ô (cells) có kích thước bằng nhau. Mỗi business thuộc về đúng 1 cell. Khi search, chỉ cần tìm các businesses trong cell hiện tại và các cells lân cận.

Vấn đề nghiêm trọng:

Vấn đề	Giải thích
Distribution không đều	Tokyo có thể có 100,000 businesses trong 1 cell, nhưng Sahara có 0
Fixed granularity	Không thể adaptive — vùng đông đúc cần grid nhỏ hơn, vùng thưa cần grid lớn hơn
Quá nhiều empty cells	70% Trái Đất là nước → 70% cells rỗng
Edge cases	Business ở sát ranh giới cell → search cần check nhiều cells

Kết luận: Evenly divided grid không phù hợp cho dữ liệu phân bố không đều. Ta cần cách tiếp cận thông minh hơn.

3.3 Approach 2 — Geohash (Core Approach)

3.3.1 Geohash là gì?

Geohash là kỹ thuật biến tọa độ 2 chiều (lat, lng) thành 1 chuỗi string duy nhất bằng cách chia đôi xen kẽ (interleaving) latitude và longitude.

Quy trình encoding (simplified):

Bước 1 — Encode Longitude:

• Bắt đầu với khoảng [-180, 180]
• Chia đôi: nếu lng nằm bên trái ([-180, 0]) → bit 0, bên phải ([0, 180]) → bit 1
• Lặp lại, chia đôi tiếp khoảng được chọn
• Ví dụ: lng = 106.70 → [0, 180] → 1, [90, 180] → 1, [90, 135] → 1, [101.25, 112.5] → 1, …

Bước 2 — Encode Latitude:

• Tương tự, bắt đầu với [-90, 90]
• Ví dụ: lat = 10.77 → [0, 90] → 1, [0, 45] → 0, [0, 22.5] → 0, …

Bước 3 — Interleave Bits:

• Xen kẽ: bit lon[0], bit lat[0], bit lon[1], bit lat[1], …
• Kết quả là 1 chuỗi bits

Bước 4 — Encode thành Base32:

• Nhóm 5 bits → 1 ký tự Base32 (0-9, b-z loại trừ a, i, l, o)
• Ví dụ: tọa độ TP.HCM (10.7769, 106.7009) → geohash: w3gvk1

3.3.2 Precision Levels — Độ chính xác

Geohash Length	Cell Width	Cell Height	Sử dụng
1	5,009 km	4,992 km	Toàn bộ lục địa
2	1,252 km	624 km	Quốc gia nhỏ
3	156 km	156 km	Tỉnh / state
4	39.1 km	19.5 km	Thành phố lớn
5	4.89 km	4.89 km	Quận / district
6	1.22 km	0.61 km	Khu vực nhỏ — phù hợp cho proximity search
7	153 m	153 m	Đường phố
8	38.2 m	19.1 m	Tòa nhà
9	4.77 m	4.77 m	Phòng trong tòa nhà
12	3.7 cm	1.8 cm	Độ chính xác GPS max

Rule of thumb cho proximity search: Radius 5km → dùng geohash length 5 (cell ~4.89 km). Radius 1km → dùng geohash length 6 (cell ~1.22 km).

3.3.3 Mapping Radius to Geohash Precision

Radius	Geohash Precision	Giải thích
0.5 km	6	Cell 1.22km, cần check cell hiện tại + 8 neighbors
1 km	5	Cell 4.89km đủ cover
2 km	5	Cell 4.89km đủ cover
5 km	4	Cell 39.1km — đủ rộng, có thể trả về quá nhiều kết quả
20 km	4	Cell 39.1km cover được

Chiến lược thực tế: Chọn precision level sao cho cell size >= radius và query cell hiện tại + 8 cells lân cận (tổng cộng 9 cells). Điều này đảm bảo cover toàn bộ vùng tròn search.

3.3.4 Tính chất quan trọng của Geohash

Tính chất 1 — Shared prefix = Nearby (thường là đúng):

Hai điểm có geohash chia sẻ prefix càng dài → càng gần nhau.

Điểm A	Điểm B	Shared prefix	Khoảng cách xấp xỉ
w3gvk1	w3gvk9	w3gvk (5 chars)	< 5 km
w3gvk1	w3gvm2	w3gv (4 chars)	< 40 km
w3gvk1	w3h001	w3 (2 chars)	< 1,252 km

Tính chất 2 — Neighbor lookup:

Mỗi geohash cell có chính xác 8 neighbors (trên, dưới, trái, phải, 4 góc). Có thể tính neighbors bằng algorithm hiệu quả trong O(1).

3.3.5 Edge Cases — Những trường hợp đặc biệt

Edge Case 1 — Khác prefix nhưng rất gần (Boundary Problem):

┌──────────┬──────────┐
│          │          │
│  w3gvk   │  w3gvm   │
│          │          │
│        A ● ● B     │
│          │          │
└──────────┴──────────┘

Điểm A (w3gvk...) và B (w3gvm...) ở 2 cells khác nhau — prefix khác hoàn toàn từ ký tự thứ 5. Nhưng thực tế chúng chỉ cách nhau 50 mét!

Giải pháp: Luôn query cell hiện tại + 8 cells lân cận. Điều này đảm bảo không bỏ sót các businesses ở ranh giới cell.

Edge Case 2 — Cùng prefix nhưng xa (Rare case):

Do cách Hilbert/Z-curve map 2D → 1D, có những trường hợp 2 cells có cùng prefix nhưng không thực sự lân cận về mặt địa lý. Ví dụ: 2 cells ở 2 bên của đường ranh giới encoding.

Giải pháp: Sau khi lấy danh sách businesses từ geohash cells, luôn tính khoảng cách thực tế (Haversine formula) và lọc bỏ những businesses ngoài radius.

$$d=2r\arcsin \left(\sqrt{{\sin }^2\left(\frac{{\varphi }_2-{\varphi }_1}{2}\right)+\cos ({\varphi }_1)\cos ({\varphi }_2){\sin }^2\left(\frac{{\lambda }_2-{\lambda }_1}{2}\right)}\right)$$

Trong đó $r$ = bán kính Trái Đất (6,371 km), $\varphi$ = latitude (radians), $\lambda$ = longitude (radians).

Edge Case 3 — Không đủ businesses trong radius:

Khi search radius = 1km nhưng chỉ có 2 businesses, user có thể muốn xem thêm. Chiến lược mở rộng radius:

1. Search với geohash precision tương ứng radius ban đầu
2. Nếu kết quả < min_results (ví dụ: 10)
3. Giảm geohash precision 1 bậc (mở rộng vùng search ~4x)
4. Search lại
5. Lặp lại cho đến khi đủ kết quả hoặc đạt max_radius

3.4 Approach 3 — Quadtree (Adaptive Grid)

3.4.1 Quadtree là gì?

Quadtree là cấu trúc dữ liệu hình cây, trong đó mỗi node có thể có 0 hoặc 4 children. Nó tự động chia nhỏ vùng có nhiều businesses và giữ nguyên vùng ít businesses.

Nguyên tắc: Chia không gian 2D thành 4 phần. Nếu 1 phần có nhiều hơn K businesses (threshold, ví dụ K=100), tiếp tục chia phần đó thành 4. Lặp lại cho đến khi mỗi ô có ⇐ K businesses.

3.4.2 Quy trình Build Quadtree

Bắt đầu: Toàn bộ bản đồ là 1 node
  - Node chứa 5,000,000 businesses (> threshold 100) → SPLIT

Node chia thành 4 children:
  NW (Northwest): 1,200,000 businesses → SPLIT
  NE (Northeast): 2,500,000 businesses → SPLIT
  SW (Southwest): 800,000 businesses → SPLIT
  SE (Southeast): 500,000 businesses → SPLIT

Tiếp tục chia cho đến khi mỗi leaf node có <= 100 businesses

Đặc điểm quan trọng:

Đặc điểm	Giải thích
Adaptive	Vùng Tokyo (đông đúc) có cell nhỏ ~100m. Vùng Sahara có cell lớn ~1000km
In-memory	Toàn bộ tree nằm trong RAM — query cực nhanh
Build time	Build 1 lần khi server khởi động, hoặc rebuild định kỳ
Not easily shareable	Mỗi server giữ 1 bản copy của tree — không chia sẻ qua network

3.4.3 Quadtree Structure — Chi tiết Node

Internal Node (node có children):

Field	Size	Giải thích
Top-left coordinates	16 bytes	(lat, lng) góc trên trái
Bottom-right coordinates	16 bytes	(lat, lng) góc dưới phải
Pointer to NW child	8 bytes
Pointer to NE child	8 bytes
Pointer to SW child	8 bytes
Pointer to SE child	8 bytes
Total	64 bytes

Leaf Node (node chứa businesses):

Field	Size	Giải thích
Top-left coordinates	16 bytes	Ranh giới vùng
Bottom-right coordinates	16 bytes	Ranh giới vùng
List of business_ids	8 bytes x N	N ⇐ threshold (100)
Total	32 + 8N bytes	Với N=100: ~832 bytes

3.4.4 Memory Estimation (Chi tiết)

$$ThresholdK=100businessesperleaf$$ $$Totalleafnodes=\frac{100M}{100}=1Mleaves$$

Quadtree là full 4-ary tree. Tổng số internal nodes:

$$Internalnodes=\frac{leafnodes-1}{3}=\frac{1M-1}{3}\approx 333,333nodes$$ $$Memor{y}_{internal}=333,333\times 64bytes=21.3MB$$ $$Memor{y}_{leaves}=1M\times (32+8\times 100)bytes=1M\times 832bytes=832MB$$ $$TotalQuadtreememory=21.3MB+832MB\approx 853MB$$

Key insight: 853 MB — một server với 8 GB RAM có thể chứa thoải mái. Không cần distributed index! Đây là điều nhiều ứng viên interview không nhận ra.

3.4.5 Build Time Estimation

$$Buildtime\approx O(N\times {\log }_{4}N)\approx O(100M\times {\log }_{4}100M)$$ $${\log }_4(100M)\approx {\log }_4(10^8)\approx \frac{8}{{\log }_{10}4}\approx \frac{8}{0.602}\approx 13.3levels$$ $$Buildtime\approx 100M\times 13.3\approx 1.33Boperations$$

Với máy tính hiện đại xử lý ~1 billion operations/second, build time khoảng vài phút. Có thể chấp nhận cho startup time.

3.4.6 Quadtree Search Algorithm

Tìm businesses trong radius R từ điểm P(lat, lng):

1. Bắt đầu từ root node
2. Tìm leaf node chứa điểm P (traverse tree theo tọa độ)
3. Tính khoảng cách từ P đến mỗi business trong leaf node đó
4. Nếu vòng tròn (P, R) overlap với các neighboring cells:
   - Traverse lên parent, check các sibling nodes
   - Lặp lại cho đến khi vòng tròn được cover hoàn toàn
5. Lọc businesses có distance > R
6. Sắp xếp theo distance, trả về top N

$$Searchtime=O({\log }_{4}N+k)$$

Trong đó $k$ = số businesses trong vùng search. Với $N=100M$:

$$Searchtime=O(13.3+k)\approx O(k)choklớn$$

3.4.7 Update Strategy cho Quadtree

Vấn đề: Businesses thay đổi (thêm mới, đóng cửa, đổi địa chỉ) — làm sao update Quadtree?

Option 1 — Rebuild định kỳ (Recommended):

Aspect	Detail
Frequency	Mỗi vài giờ hoặc overnight
Process	Build quadtree mới từ database, swap với tree cũ (atomic swap)
Downtime	Zero — tree cũ vẫn serve requests trong khi tree mới đang build
Phù hợp khi	Business data thay đổi chậm (hàng ngày), không cần real-time

Option 2 — Incremental update:

Aspect	Detail
Process	Thêm/xóa business trực tiếp trong tree
Complexity	Cao — cần handle split/merge khi node vượt threshold
Phù hợp khi	Data thay đổi thường xuyên (ví dụ: driver locations trong Uber)

Cho bài toán Proximity Service (businesses), Option 1 là đủ vì businesses hiếm khi thay đổi vị trí.

3.5 Approach 4 — Google S2 Geometry Library

3.5.1 S2 là gì?

Google S2 là thư viện chuyên dụng do Google phát triển, sử dụng Hilbert curve để map bề mặt hình cầu (Trái Đất) thành các S2 cells.

Điểm khác biệt với Geohash:

Feature	Geohash	S2
Hình dạng cell	Hình chữ nhật trên bản đồ	Hình thoi (rhombus) trên hình cầu
Mô hình Trái Đất	Phẳng (flat projection)	Hình cầu (sphere)
Curve type	Z-order curve	Hilbert curve
Cell levels	1-12 (base32 chars)	0-30 (64-bit integer)
Độ chính xác	Tốt, có boundary issues	Tốt hơn — Hilbert curve bảo toàn locality tốt hơn
Region covering	Manual (9 cells)	Tự động — S2RegionCoverer tìm tối ưu cells

3.5.2 Hilbert Curve — Tại sao tốt hơn Z-curve?

Z-curve (Geohash) có vấn đề “jumps” — đôi khi 2 cells kề nhau trên bản đồ lại xa nhau trên Z-curve. Điều này gây ra các boundary issues.

Hilbert curve đảm bảo: 2 điểm gần nhau trên curve hầu như luôn gần nhau trong không gian 2D. Tính chất này gọi là locality-preserving — tốt hơn Z-curve đáng kể.

3.5.3 S2 trong thực tế

Company	Sử dụng S2 cho
Google Maps	Core geospatial indexing
Uber H3	Inspired by S2, dùng hexagonal cells
Foursquare	Place detection
MongoDB	2dsphere index sử dụng S2 internally

3.6 So sánh Geohash vs Quadtree vs S2

Tiêu chí	Geohash	Quadtree	S2
Độ phức tạp implement	Thấp — chỉ là string operation	Trung bình — cần build tree	Cao — cần S2 library
Storage	Trong database (column)	In-memory trên mỗi server	Trong database (column)
Update	Update database record	Rebuild tree	Update database record
Adaptive density	Không — fixed grid size	Có — tự động chia nhỏ vùng đông đúc	Có — S2RegionCoverer
Precision control	12 levels (base32)	Vô hạn (chia cho đến khi đủ)	31 levels (0-30)
Boundary issues	Có — cần query 8 neighbors	Ít — tree structure handle tự nhiên	Ít nhất — Hilbert curve
Distributed	Dễ — geohash là string, index bình thường	Khó — tree phải ở 1 server	Dễ — S2 cell ID là integer
Database support	Redis, PostgreSQL, MySQL, DynamoDB	Phải tự implement	MongoDB (native), PostgreSQL (extension)
Phù hợp cho	Hầu hết use cases, đơn giản	Dataset lớn, cần adaptive, in-memory ok	Google-scale, hình cầu chính xác

Recommendation cho interview: Chọn Geohash làm primary approach (dễ giải thích, database support tốt). Nhắc đến Quadtree như alternative khi interviewer hỏi về adaptive density. Nhắc đến S2 để show depth of knowledge.

3.7 Database Schema Design

3.7.1 Business Table

Column	Type	Description	Index
business_id	UUID (PK)	ID duy nhất	Primary Key
name	VARCHAR(255)	Tên business	Full-text index
address	TEXT	Địa chỉ
city	VARCHAR(100)	Thành phố
country	VARCHAR(2)	Mã quốc gia (ISO 3166)
latitude	DOUBLE	Vĩ độ
longitude	DOUBLE	Kinh độ
category	VARCHAR(50)	Loại business	Index
rating	DECIMAL(2,1)	Rating trung bình
phone	VARCHAR(20)	Số điện thoại
hours	JSONB	Giờ mở cửa
photos	JSONB	URLs ảnh
created_at	TIMESTAMP
updated_at	TIMESTAMP		Index

3.7.2 Geospatial Index Table (Geohash approach)

Column	Type	Description	Index
geohash	VARCHAR(12)	Geohash của business	Primary prefix index
business_id	UUID	FK to business table
latitude	DOUBLE	Để tính khoảng cách chính xác
longitude	DOUBLE	Để tính khoảng cách chính xác

Index Strategy: Tạo compound index trên (geohash, business_id). Khi query, dùng prefix search:

-- Tìm businesses trong geohash cell "w3gvk" và các neighbors
WHERE geohash LIKE 'w3gvk%'
   OR geohash LIKE 'w3gvm%'
   OR geohash LIKE 'w3gvj%'
   ... (tổng 9 cells)

Optimization: Thay vì 9 queries riêng biệt, dùng IN clause hoặc UNION ALL để batch thành 1 query.

3.7.3 Database Architecture — Read Replicas

flowchart LR
    subgraph "Write Path"
        BS["Business Service"]
        Primary["Primary DB<br/>PostgreSQL"]
    end

    subgraph "Read Path"
        LBS["LBS Instances"]
        R1["Read Replica 1<br/>US-West"]
        R2["Read Replica 2<br/>US-East"]
        R3["Read Replica 3<br/>EU-West"]
        R4["Read Replica 4<br/>AP-Southeast"]
    end

    BS --> Primary
    Primary -->|"Async Replication"| R1 & R2 & R3 & R4
    LBS --> R1 & R2 & R3 & R4

    style Primary fill:#66bb6a,color:#fff
    style R1 fill:#42a5f5,color:#fff
    style R2 fill:#42a5f5,color:#fff
    style R3 fill:#42a5f5,color:#fff
    style R4 fill:#42a5f5,color:#fff

Tại sao Read Replicas theo region? Vì LBS là read-heavy (60K QPS peak). Mỗi region có read replicas riêng → giảm latency (user ở Singapore query replica ở Singapore, không phải đi qua US). Tham chiếu Tuan-07-Database-Sharding-Replication.

3.8 Caching Strategy

3.8.1 Cache Architecture

Sử dụng 2 lớp cache:

Cache Layer 1 — Geohash to Business IDs:

Key	Value	TTL	Giải thích
geo:w3gvk:restaurant	[id1, id2, id3, ...]	1 hour	Danh sách business IDs trong geohash cell + category
geo:w3gvk:*	[id1, id2, ...]	1 hour	Tất cả businesses trong cell (không filter category)

Cache Layer 2 — Business Details:

Key	Value	TTL	Giải thích
biz:uuid-123	{name, lat, lng, rating, ...}	24 hours	Chi tiết business

3.8.2 Cache Flow

Search request: lat=10.77, lng=106.70, radius=5000, category=restaurant

1. Tính geohash: w3gvk (precision 5)
2. Tính 8 neighbors: w3gvm, w3gvj, w3gvh, w3gvs, w3gvt, w3gve, w3gv7, w3gv6
3. Với mỗi geohash cell:
   a. Check Redis: GET geo:w3gvk:restaurant
   b. Cache HIT → nhận list business_ids
   c. Cache MISS → query Read Replica → set cache
4. Merge tất cả business_ids từ 9 cells
5. Với mỗi business_id:
   a. Check Redis: GET biz:uuid-123
   b. Cache HIT → nhận business details
   c. Cache MISS → query Read Replica → set cache
6. Tính distance, filter, sort, return

3.8.3 Cache Invalidation

Event	Action	Lý do
Business update (name, hours, rating)	Invalidate biz:{id}	Chi tiết thay đổi
Business move (lat/lng thay đổi)	Invalidate biz:{id} + geo:{old_hash}:* + geo:{new_hash}:*	Vị trí thay đổi → geohash cell thay đổi
Business deleted	Invalidate biz:{id} + geo:{hash}:*	Xóa khỏi tất cả cache
TTL expiry	Tự động	Safety net

Tham chiếu Tuan-06-Cache-Strategy cho các pattern cache invalidation chi tiết.

3.9 Scaling Strategy

3.9.1 LBS — Stateless Horizontal Scaling

LBS instances là stateless (không giữ state nào). Mỗi request có thể được xử lý bởi bất kỳ instance nào.

$$LBSinstancesneeded=\frac{QP{S}_{peak}}{QP{S}_{perinstance}}$$ $$=\frac{60,000}{2,000}=30instances(vớim\tilde{\hat{o}}iinstancehandle2KQPS)$$

Đặt sau Load Balancer (Tuan-05-Load-Balancer), sử dụng round-robin hoặc least-connections.

Nếu dùng Quadtree: Mỗi LBS instance giữ 1 bản copy của Quadtree trong memory. Khi scale thêm instance → instance mới build Quadtree từ database khi khởi động (vài phút). Sau đó serve requests bình thường.

3.9.2 Database — Read Replicas per Region

Region	Read Replicas	Lý do
US-West	3	California, tech hub
US-East	3	New York, Washington DC
EU-West	2	London, Paris
AP-Southeast	3	Singapore, TP.HCM, Jakarta — high density
AP-Northeast	2	Tokyo, Seoul

$$Totalreadreplicas=13$$ $$QP{S}_{perreplica}=\frac{60K}{13}\approx 4,615QPS$$

PostgreSQL có thể handle 10K+ simple reads/s → 4.6K QPS per replica là thoải mái.

3.9.3 Cache — Redis Cluster

$$Cachenodes=\frac{120GB}{16GBpernode}=8Redisnodes$$

Sử dụng Redis Cluster với sharding theo geohash prefix. Tất cả keys với geohash bắt đầu “w3” (Vietnam) sẽ ở cùng shard → locality tốt cho cache.

---

Query Flow — End to End

sequenceDiagram
    participant U as User (Mobile)
    participant LB as Load Balancer
    participant LBS as LBS Instance
    participant Cache as Redis Cache
    participant DB as Read Replica

    U->>LB: GET /v1/search/nearby<br/>lat=10.77, lng=106.70, radius=5000

    LB->>LBS: Route to LBS Instance

    Note over LBS: 1. Tính geohash: w3gvk (precision 5)
    Note over LBS: 2. Tính 8 neighbors

    loop Cho mỗi 9 geohash cells
        LBS->>Cache: GET geo:w3gvk:*
        alt Cache HIT
            Cache-->>LBS: [business_id_1, business_id_2, ...]
        else Cache MISS
            LBS->>DB: SELECT business_id FROM geo_index<br/>WHERE geohash LIKE 'w3gvk%'
            DB-->>LBS: [business_id_1, business_id_2, ...]
            LBS->>Cache: SET geo:w3gvk:* (TTL 1h)
        end
    end

    Note over LBS: 3. Merge business_ids từ 9 cells

    loop Cho mỗi business_id
        LBS->>Cache: GET biz:{id}
        alt Cache HIT
            Cache-->>LBS: {name, lat, lng, rating, ...}
        else Cache MISS
            LBS->>DB: SELECT * FROM businesses<br/>WHERE id = ?
            DB-->>LBS: {name, lat, lng, rating, ...}
            LBS->>Cache: SET biz:{id} (TTL 24h)
        end
    end

    Note over LBS: 4. Tính Haversine distance
    Note over LBS: 5. Filter distance > radius
    Note over LBS: 6. Sort by distance

    LBS-->>LB: {businesses: [...], next_page_token: ...}
    LB-->>U: 200 OK

---

Geohash Grid Visualization

graph TB
    subgraph "Geohash Grid — TP.HCM Area (Precision 5)"
        subgraph row1[""]
            C1["w3gv6<br/>0 biz"]
            C2["w3gv7<br/>12 biz"]
            C3["w3gve<br/>5 biz"]
        end
        subgraph row2[""]
            C4["w3gvj<br/>45 biz"]
            C5["w3gvk<br/>●USER<br/>78 biz"]
            C6["w3gvm<br/>23 biz"]
        end
        subgraph row3[""]
            C7["w3gvh<br/>8 biz"]
            C8["w3gvs<br/>156 biz"]
            C9["w3gvt<br/>34 biz"]
        end
    end

    style C5 fill:#ff9800,color:#000,stroke:#e65100,stroke-width:3px
    style C4 fill:#c8e6c9
    style C6 fill:#c8e6c9
    style C8 fill:#c8e6c9
    style C2 fill:#c8e6c9
    style C1 fill:#e8eaf6
    style C3 fill:#e8eaf6
    style C7 fill:#e8eaf6
    style C9 fill:#e8eaf6

User ở cell w3gvk. Hệ thống query cell này + 8 neighbors (tổng 9 cells, 361 businesses). Sau đó tính khoảng cách thực và lọc.

---

Quadtree Structure Visualization

graph TD
    Root["ROOT<br/>Toàn bộ bản đồ<br/>100M businesses"]

    Root --> NW["NW<br/>North America<br/>25M biz"]
    Root --> NE["NE<br/>Europe + Africa<br/>20M biz"]
    Root --> SW["SW<br/>South America<br/>5M biz"]
    Root --> SE["SE<br/>Asia + Oceania<br/>50M biz"]

    SE --> SE_NW["SE-NW<br/>East Asia<br/>20M biz"]
    SE --> SE_NE["SE-NE<br/>Pacific<br/>2M biz"]
    SE --> SE_SW["SE-SW<br/>Southeast Asia<br/>18M biz"]
    SE --> SE_SE["SE-SE<br/>Oceania<br/>10M biz"]

    SE_SW --> VN1["VN-North<br/>Ha Noi area<br/>500K biz"]
    SE_SW --> VN2["VN-South<br/>TP.HCM area<br/>800K biz"]
    SE_SW --> TH["Thailand<br/>1.2M biz"]
    SE_SW --> ID["Indonesia<br/>2M biz"]

    VN2 --> D1["Quan 1<br/>5K biz"]
    VN2 --> D2["Quan 7<br/>3K biz"]
    VN2 --> D3["Thu Duc<br/>2K biz"]
    VN2 --> D4["Binh Thanh<br/>4K biz"]

    D1 --> L1["Block A<br/>95 biz ✓"]
    D1 --> L2["Block B<br/>78 biz ✓"]
    D1 --> L3["Block C<br/>88 biz ✓"]
    D1 --> L4["Block D<br/>62 biz ✓"]

    style Root fill:#e53935,color:#fff
    style SE fill:#ff9800,color:#000
    style SE_SW fill:#ffc107,color:#000
    style VN2 fill:#66bb6a,color:#fff
    style D1 fill:#42a5f5,color:#fff
    style L1 fill:#a5d6a7,stroke:#388e3c
    style L2 fill:#a5d6a7,stroke:#388e3c
    style L3 fill:#a5d6a7,stroke:#388e3c
    style L4 fill:#a5d6a7,stroke:#388e3c

Leaf nodes (màu xanh lá) chứa ⇐ 100 businesses. Vùng đông đúc (Quận 1 TP.HCM) có cells nhỏ. Vùng thưa (Pacific Ocean) có cells lớn. Đây là sức mạnh của adaptive grid.

---

4. Security

4.1 Location Privacy — Bảo vệ vị trí người dùng

Mối đe dọa	Giải pháp	Chi tiết
Location fuzzing	Làm mờ tọa độ GPS trước khi log	Thêm noise ±100-500m vào tọa độ trước khi lưu vào analytics/logs. User thực nhận kết quả chính xác, nhưng server logs chỉ lưu vị trí xấp xỉ
Aggregation	Chỉ lưu aggregated data	Thay vì log “User A ở tọa độ X lúc 14:00”, log “50 users search khu vực geohash w3gvk lúc 14:00-15:00”
Retention policy	Xóa location data sau thời gian nhất định	Raw GPS coordinates xóa sau 30 ngày. Chỉ giữ aggregated stats
User consent	Hỏi quyền trước khi truy cập GPS	Mobile OS (iOS/Android) bắt buộc hỏi permission. Backend phải tôn trọng “While Using” vs “Always”
Encryption in transit	TLS 1.3 cho mọi request	Tọa độ truyền qua HTTPS, không bao giờ HTTP

4.2 Rate Limiting on Location Queries

Tier	Limit	Lý do
Per user	30 requests/minute	Người bình thường search ~5 lần/phút max
Per IP	100 requests/minute	Cho shared networks (co-working spaces)
Per API key (business)	1,000 requests/minute	Cho third-party integrations
Burst allowance	2x limit trong 10 giây	Cho phép burst ngắn khi user scroll bản đồ nhanh

Sử dụng Token Bucket algorithm. Tham chiếu Tuan-09-Rate-Limiter.

4.3 Chống Data Scraping từ Đối thủ

Mối đe dọa: Đối thủ có thể viết bot để scrape toàn bộ danh sách businesses và tọa độ từ API.

Biện pháp	Chi tiết
API key required	Mỗi client cần API key. Revoke key nếu phát hiện scraping pattern
Pagination limit	Tối đa 20 results per page, tối đa 100 pages per session
Honeypot businesses	Chèn fake businesses (chỉ visible qua API, không hiện trên UI). Nếu đối thủ hiển thị honeypot → có bằng chứng scraping
Request pattern analysis	Phát hiện: systematic grid scanning (search mỗi 1km trên toàn thành phố), unusual QPS, sequential page requests
CAPTCHA	Trigger CAPTCHA sau 50 searches liên tiếp không có user interaction
Response watermarking	Chèn metadata ẩn vào response (user ID, timestamp) để trace nguồn leak

4.4 GDPR Compliance cho Location Data

Yêu cầu GDPR	Implementation
Right to be forgotten	User yêu cầu xóa → xóa tất cả location history, search history, cached data
Data portability	Export location history dạng JSON/CSV khi user yêu cầu
Purpose limitation	Location data chỉ dùng cho search nearby — không bán cho third-party advertising
Data minimization	Chỉ lưu tọa độ khi cần thiết. Không lưu location history cho tính năng search (chỉ cần real-time)
Consent	Explicit opt-in cho location tracking. Granular permissions: “Chỉ khi đang dùng app”
Data Processing Agreement	Với cloud provider (AWS/GCP) — đảm bảo data ở region phù hợp (EU data ở EU region)

---

5. DevOps & Monitoring

5.1 Key Metrics to Monitor

5.1.1 Search Latency by Region

Metric	Alert Threshold	Dashboard
search_latency_p50 by region	> 50ms	Time series, group by region
search_latency_p99 by region	> 200ms	Time series, group by region
search_latency_p99 global	> 500ms	Single number, red/green
search_error_rate	> 0.1%	Percentage gauge

Tại sao by region? Vì latency phụ thuộc vào: khoảng cách đến read replica, business density (vùng đông đúc trả về nhiều kết quả hơn → chậm hơn), và cache hit ratio.

5.1.2 Cache Performance

Metric	Alert Threshold	Ý nghĩa
cache_hit_ratio_geo (geohash → business_ids)	< 90%	Cache không hiệu quả → check TTL, check nếu có geohash precision thay đổi
cache_hit_ratio_biz (business details)	< 95%	Business data ít thay đổi, cache hit phải cao
cache_eviction_rate	> 1000/s	Redis hết memory → cần thêm node
cache_latency_p99	> 5ms	Redis chậm → check network, check memory fragmentation

Cache Hit Ratio by Geohash Precision:

Precision	Expected Hit Ratio	Giải thích
4 (39km cells)	98%+	Cell lớn → nhiều user search cùng cell → cache warm
5 (4.9km cells)	95%+	Phổ biến nhất — balance giữa granularity và cache efficiency
6 (1.2km cells)	85-90%	Cell nhỏ → nhiều cells → cache cold cho cells ít search
7 (153m cells)	70-80%	Quá granular cho proximity search → không khuyến nghị

5.1.3 Database Replication Lag

Metric	Alert Threshold	Impact
replication_lag_seconds per replica	> 30s	Business updates chậm hiển thị
replication_lag_seconds max	> 300s (5 min)	Cần investigate — replica có thể bị stuck
replica_connections	< expected	Replica bị disconnect → data stale

Tham chiếu Tuan-07-Database-Sharding-Replication cho chi tiết về replication monitoring.

5.1.4 Quadtree Health (nếu sử dụng)

Metric	Alert Threshold	Ý nghĩa
quadtree_build_time_seconds	> 600 (10 min)	Build chậm → data tăng hoặc server chậm
quadtree_memory_bytes	> 2 GB	Tree lớn bất thường → check data quality
quadtree_last_build_timestamp	> 6 hours ago	Quadtree outdated → trigger rebuild
quadtree_max_depth	> 20	Có thể có dữ liệu bất thường (nhiều businesses cùng tọa độ)

5.2 Deployment Strategy

Aspect	Strategy	Lý do
LBS instances	Rolling update	Stateless → có thể update từng instance
Quadtree rebuild	Blue-green	Build tree mới, swap khi xong. Zero downtime
Database schema migration	Online DDL (pt-online-schema-change)	Không lock table
Cache warming	Pre-warm after deploy	Script query top geohash cells để warm cache
Canary deployment	5% traffic trước	Phát hiện vấn đề sớm trước khi rollout 100%

5.3 Alerting Rules

Alert	Condition	Severity	Action
High search latency	p99 > 500ms for 5 min	P1	On-call investigate, check DB/cache
Cache cluster down	> 1 node unreachable for 2 min	P1	Auto-failover, page on-call
Replication lag high	> 5 min for any replica	P2	Check replica health, network
Quadtree build failed	Build process crashed	P2	Serve với tree cũ, investigate
Error rate spike	> 1% for 3 min	P1	Check recent deploy, rollback if needed
Scraping detected	> 500 sequential searches from 1 IP	P3	Auto rate limit, review

Tham chiếu Tuan-13-Monitoring-Observability cho alerting best practices.

---

6. Aha Moments & Pitfalls

6.1 Aha Moments — Những điều bất ngờ

Aha 1: Geohash Boundary Problem

Vấn đề: Hai quán phở cách nhau 50m nhưng ở 2 geohash cells khác nhau. Nếu chỉ query 1 cell → bỏ sót kết quả.

Giải pháp: Luôn query 9 cells (cell hiện tại + 8 neighbors). Chi phí: 9x queries thay vì 1x. Nhưng với cache, chi phí này giảm đáng kể.

Tủi interview: Nếu interviewer hỏi “geohash có vấn đề gì?”, PHẢI nhắc đến boundary problem và giải pháp 9-cell query. Đây là điểm phân biệt ứng viên trung bình và ứng viên tốt.

Aha 2: Quadtree fit trong 1 server

100 triệu businesses, quadtree chỉ chiếm ~853 MB RAM. Một server có 16 GB RAM đủ sức giữ cả tree. Không cần distributed index.

Ý nghĩa: Khi interviewer gợi ý “làm sao distribute quadtree across servers?”, câu trả lời đúng là: không cần distribute. Mỗi LBS server giữ 1 bản copy. Scale bằng cách thêm server (mỗi server có full copy).

So sánh với B-tree: Nếu dùng B-tree trong database, index cho 100M records có thể chiếm 10-20 GB (vì B-tree có overhead lớn hơn). Quadtree tiết kiệm memory hơn đáng kể cho geospatial data.

Aha 3: Radius không map 1-1 với Geohash Precision

Không có công thức chính xác: radius = X → geohash precision = Y. Phải chọn precision sao cho cell size >= radius, rồi query 9 cells.

Ví dụ: Radius 2km. Cell precision 6 = 1.22km (nhỏ hơn radius) → không đủ. Cell precision 5 = 4.89km (lớn hơn radius) → OK, nhưng trả về nhiều kết quả thừa. Giải pháp: dùng precision 5, query 9 cells, rồi filter bằng Haversine distance.

Aha 4: Write path và Read path hoàn toàn tách biệt

Proximity Service là một trong những case study rõ ràng nhất của CQRS pattern. Write QPS = 1-5, Read QPS = 60,000. Scale chung sẽ lãng phí tài nguyên.

Aha 5: Geohash là string → dùng được với mọi database

Geohash chỉ là 1 chuỗi string (ví dụ: “w3gvk1”). Có thể lưu trong bất kỳ database nào có string index: PostgreSQL, MySQL, DynamoDB, Redis, Cassandra. Không cần database đặc biệt.

6.2 Pitfalls — Những sai lầm phổ biến

Pitfall 1: Dùng two-dimensional search trực tiếp

“SELECT WHERE lat BETWEEN … AND lng BETWEEN …” — chậm O(N) vì database không thể dùng cả 2 index cùng lúc hiệu quả.

Fix: Dùng geospatial index (geohash, quadtree, hoặc PostGIS).

Pitfall 2: Chỉ query 1 geohash cell

Bỏ qua boundary problem → mất kết quả ở ranh giới cell. Đây là lỗi nghiêm trọng nhất khi implement geohash search.

Fix: Luôn query cell hiện tại + 8 neighbors.

Pitfall 3: Không tính Haversine distance sau khi query

Geohash query trả về hình vuông (hoặc hình chữ nhật). Nhưng user search theo vòng tròn (radius). Các businesses ở góc của hình vuông có thể nằm ngoài vòng tròn nhưng vẫn được trả về.

Fix: Sau khi lấy kết quả từ geohash cells, PHẢI tính Haversine distance và lọc bỏ businesses ngoài radius.

Pitfall 4: Overcomplicate distributed Quadtree

Nhiều ứng viên cố gắng distribute quadtree across servers. Không cần thiết — 853 MB fit trong 1 server. Complexity của distributed tree không đáng.

Fix: Mỗi server giữ full copy. Scale bằng cách thêm servers.

Pitfall 5: Quên cache invalidation khi business di chuyển

Khi business thay đổi tọa độ (ví dụ: food truck), geohash thay đổi. Nếu không invalidate cache cũ → user ở vị trí cũ vẫn thấy business đó, user ở vị trí mới không thấy.

Fix: Invalidate cache ở CẢ HAI geohash cũ và mới khi business update tọa độ.

Pitfall 6: Dùng geohash precision quá cao

Precision 7 (153m cells) nghe có vẻ “chính xác hơn”. Nhưng cell nhỏ → cần query nhiều cells hơn để cover radius → nhiều queries hơn → chậm hơn. Và cache hit ratio giảm vì quá nhiều distinct cells.

Fix: Chọn precision phù hợp với radius. Thường là precision 4-6 cho hầu hết use cases.

---

7. Summary — Tóm tắt Decision Framework

7.1 Khi nào dùng Geohash?

Tình huống	Recommendation
Database có sẵn (PostgreSQL, MySQL)	Geohash — chỉ cần thêm 1 column
Cần distributed index	Geohash — string column, dùng được với sharding
Team nhỏ, cần ship nhanh	Geohash — đơn giản nhất
Data thay đổi thường xuyên	Geohash — update record là xong

7.2 Khi nào dùng Quadtree?

Tình huống	Recommendation
Cần adaptive density	Quadtree — tự động chia nhỏ vùng đông đúc
Query in-memory là chấp nhận	Quadtree — cực nhanh, O(log N)
Data ít thay đổi (businesses)	Quadtree — rebuild định kỳ là đủ
Single region deployment	Quadtree — không cần distribute

7.3 Khi nào dùng S2?

Tình huống	Recommendation
Cần độ chính xác hình cầu	S2 — tốt nhất cho bài toán toàn cầu
Google-scale	S2 — proven at Google
MongoDB ecosystem	S2 — native support (2dsphere)
Complex region queries	S2 — S2RegionCoverer tối ưu

---

8. Further Reading & Internal Links

Kiến thức nền tảng liên quan

Topic	Link	Áp dụng trong Proximity Service
Cache Strategy	Tuan-06-Cache-Strategy	Geohash cache, business data cache, invalidation patterns
Database Sharding & Replication	Tuan-07-Database-Sharding-Replication	Read replicas per region, replication lag monitoring
Load Balancer	Tuan-05-Load-Balancer	Distribute traffic across stateless LBS instances
Rate Limiter	Tuan-09-Rate-Limiter	Chống scraping, protect LBS từ traffic spikes
Monitoring	Tuan-13-Monitoring-Observability	Search latency, cache hit ratio, replication lag alerts
Back-of-envelope	Tuan-02-Back-of-the-envelope	QPS, storage, memory estimation
Microservices Pattern	Tuan-11-Microservices-Pattern	CQRS — tách Read (LBS) và Write (Business Service)

So sánh với các Case Study khác

Case Study	Điểm tương đồng	Điểm khác biệt
Tuan-16-Design-URL-Shortener	Read-heavy, caching quan trọng	URL shortener không có geospatial component
Tuan-18-Design-News-Feed	Fan-out pattern, caching	News Feed là social graph, không phải location
Tuan-20-Design-Key-Value-Store	In-memory data structures, partitioning	KV Store là general purpose, Proximity là domain-specific

---

9. Interview Cheat Sheet

Bước 1 — Hỏi Clarifying Questions (2-3 phút)

• Scale: bao nhiêu businesses? bao nhiêu DAU?
• Radius: user có chọn radius không? Max radius?
• Real-time: business updates cần hiển thị ngay không?
• Features: search only? hay cả CRUD businesses?

Bước 2 — High-level Design (5-7 phút)

• Vẽ 2 services: LBS (read) + Business Service (write)
• Vẽ database: Primary + Read Replicas
• Nhắc CQRS pattern
• Vẽ cache layer (Redis)

Bước 3 — Deep Dive (15-20 phút)

• Giải thích geohash: encoding, precision levels, 9-cell query
• Nhắc boundary problem và giải pháp
• Quadtree như alternative: adaptive, in-memory, 853 MB
• Database schema: business table + geospatial index table
• Caching: 2-layer (geohash → IDs, ID → details)

Bước 4 — Wrap Up (3-5 phút)

• Scaling: LBS stateless → horizontal, DB read replicas per region
• Monitoring: search latency, cache hit ratio, replication lag
• Security: location privacy, rate limiting, anti-scraping

Câu hỏi interviewer thường hỏi

Câu hỏi	Cách trả lời
”Geohash vs Quadtree?”	Geohash: distributed, database-friendly. Quadtree: adaptive, in-memory, faster query. Chọn theo use case
”Geohash có vấn đề gì?”	Boundary problem — 2 điểm gần nhau nhưng khác cell. Fix: query 9 cells
”Quadtree có scale không?“	100M businesses chỉ 853 MB — mỗi server giữ full copy. Scale horizontal
”Làm sao handle business updates?”	CQRS: write vào Primary, async replicate. Quadtree rebuild định kỳ. Cache invalidation
”Làm sao giảm latency?”	Cache (2-layer), read replicas per region, geohash precision tuning

---

“Proximity Service là bài toán tuyệt vời để hiểu geospatial indexing — nền tảng của mọi ứng dụng location-based. Khi bạn hiểu cách biến bài toán 2 chiều thành 1 chiều (geohash) hoặc chia không gian thông minh (quadtree), bạn có thể áp dụng cho bất kỳ bài toán location nào: tìm tài xế, tìm bạn bè, tìm nhà hàng, hay tìm bất kỳ thứ gì trên bản đồ.”