Case-Design-Google-Maps

Case Study: Design Google Maps

“Ngày xưa, muốn đi từ Sài Gòn ra Hà Nội, ông bà phải trải bản đồ giấy ra sàn, dùng ngón tay đo theo quốc lộ 1A. Hôm nay, một cái chạm vào màn hình — Google Maps tính cho bạn đường nhanh nhất trong 0.5 giây. Đằng sau sự ‘đơn giản’ đó là một trong những hệ thống phức tạp nhất thế giới.”

Tags: system-design case-study google-maps navigation geo alex-xu-vol2 Student: Hieu Prerequisite: Tuan-02-Back-of-the-envelope · Tuan-03-Networking-DNS-CDN · Tuan-08-Message-Queue Lien quan: Case-Design-Proximity-Service · Tuan-07-Database-Sharding-Replication · Tuan-06-Cache-Strategy · Tuan-13-Monitoring-Observability · Tuan-14-AuthN-AuthZ-Security · Tuan-15-Data-Security-Encryption Reference: Alex Xu, System Design Interview Volume 2 — Chapter 2: Nearby Friends / Google Maps

---

Context & Why — Từ bản đồ giấy đến bản đồ số thông minh

Analogy: Mê cung thành phố

hãy tưởng tượng bạn đứng giữa một mê cung khổng lồ — mê cung đó chính là mạng lưới đường phố của một thành phố. Bản đồ giấy ngày xưa giống như bạn cầm một tấm ảnh chụp từ trên cao, rồi tự mình đo đường bằng mắt. Vấn đề là:

• Bản đồ giấy không biết traffic — bạn không biết đường nào đang kẹt xe
• Bản đồ giấy không cập nhật — con đường mới xây xong tháng trước chưa có trên bản đồ
• Bản đồ giấy không tính được ETA — bạn chỉ ước lượng bằng cảm giác
• Bản đồ giấy không zoom được — muốn xem chi tiết phải mua bản đồ tỉ lệ khác

Google Maps giải quyết tất cả những vấn đề này bằng cách số hóa toàn bộ bản đồ thế giới, chia nhỏ thành hàng tỉ tile nhỏ, và sử dụng algorithm để tìm đường nhanh nhất trong thời gian thực.

Tại sao bài này quan trọng?

Khía cạnh	Lý do
Geo-spatial data	Đây là nền tảng cho mọi ứng dụng location-based (Grab, Uber, delivery apps)
Scale khổng lồ	1 billion DAU, hàng chục triệu navigation requests/ngày
Real-time processing	Traffic data thay đổi mỗi giây, ETA phải cập nhật liên tục
Pre-computation	Không thể tính routing on-the-fly cho mọi request — cần pre-compute
CDN & Caching	Map tiles là bài toán CDN kinh điển — Tuan-03-Networking-DNS-CDN
Stream processing	Location updates từ hàng tỉ device — Tuan-08-Message-Queue

---

Step 1 — Understand the Problem & Establish Design Scope

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

Câu hỏi	Trả lời	Ghi chú
Hệ thống cần hỗ trợ những feature chính nào?	Map rendering, navigation (routing + ETA), location update	3 pillars chính
Scale bao lớn?	~1 Billion DAU	Quy mô Google-level
Cần hỗ trợ real-time traffic?	Có — traffic overlay trên map và ETA tính toán	Stream processing
Map data từ đâu?	Satellite imagery, street-level photography, user contributions, third-party data	Không thiết kế phần thu thập, chỉ dùng data có sẵn
Hỗ trợ bao nhiêu loại phương tiện?	Xe hơi, xe máy, đi bộ, xe đạp, transit (bus/tàu)	Mỗi loại có routing algorithm riêng
Offline support?	Có — download map tiles cho một region	Mobile-first concern
Turn-by-turn navigation?	Có — real-time voice guidance	Streaming direction updates
Search (geocoding)?	Có — tìm địa điểm bằng tên, địa chỉ	Geocoding + reverse geocoding

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

• FR1: Map Rendering — hiển thị bản đồ tại bất kỳ vị trí nào trên thế giới, hỗ trợ zoom in/out (21 zoom levels)
• FR2: Navigation/Routing — tìm đường đi ngắn nhất hoặc nhanh nhất giữa 2 điểm (hoặc nhiều điểm), tính ETA
• FR3: Location Update — nhận và lưu vị trí hiện tại của user (GPS coordinates) để phục vụ traffic và personalization
• FR4: Geocoding — chuyển đổi giữa địa chỉ text và tọa độ (lat/lng) và ngược lại
• FR5: Traffic Overlay — hiển thị tình trạng giao thông real-time trên bản đồ (xanh/vàng/đỏ)
• FR6: Alternative Routes — đề xuất 2-3 tuyến đường thay thế với ETA khác nhau
• FR7: Turn-by-turn Navigation — hướng dẫn chi tiết từng bước trong quá trình di chuyển

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
Availability	99.99%	Navigation là safety-critical — user đang lái xe trên cao tốc
Latency (Map)	Tile load < 200ms	User kỳ vọng bản đồ hiển thị gần như tức thì khi scroll/zoom
Latency (Routing)	Route calculation < 3s	Bao gồm tính toán trên server + network round trip
Scalability	1B DAU, 33M location updates/s peak	Xem phần Estimation bên dưới
Accuracy (ETA)	Sai lệch < 10% so với thực tế	ETA sai = user mất tin tưởng
Freshness (Traffic)	Cập nhật mỗi 30-60 giây	Traffic cũ 5 phút là vô nghĩa
Offline Support	Download map tiles cho offline use	Mobile users ở vùng yếu signal
Data Durability	99.999999999% (eleven 9s)	Map data là tài sản core — mất là mất tất cả

---

Step 2 — High-Level Design

2.1 Ba service chính

Google Maps có thể chia thành 3 service chính (theo Alex Xu):

Service	Nhiệm vụ	Input	Output
Location Service	Thu thập và lưu vị trí của user	GPS coordinates từ mobile client	Location history, real-time traffic data
Navigation Service	Tìm đường và tính ETA	Origin + Destination + preferences	Route (list of coordinates), ETA, turn-by-turn instructions
Map Rendering Service	Phục vụ map tiles cho client hiển thị	Tile coordinates (zoom level, x, y)	Image tiles hoặc vector tiles

Ngoài ra còn có các supporting services:

Service	Nhiệm vụ
Geocoding Service	Chuyển đổi địa chỉ ←> tọa độ
Traffic Service	Xử lý và aggregation traffic data real-time
ETA Service	Tính toán ETA dựa trên historical + real-time + ML
Search/POI Service	Tìm kiếm địa điểm (Points of Interest)

2.2 High-Level Architecture Diagram

graph TB
    subgraph Clients
        MobileApp["Mobile App<br/>(iOS/Android)"]
        WebApp["Web Browser"]
    end

    subgraph "API Gateway & Load Balancer"
        APIGW["API Gateway<br/>Rate Limiting, Auth, Routing"]
    end

    subgraph "Core Services"
        LocSvc["Location Service<br/>(Write-heavy)"]
        NavSvc["Navigation Service<br/>(Compute-heavy)"]
        MapSvc["Map Rendering Service<br/>(Read-heavy)"]
        GeoSvc["Geocoding Service"]
        TrafficSvc["Traffic Service"]
        ETASvc["ETA Service"]
        SearchSvc["Search/POI Service"]
    end

    subgraph "Data Layer"
        Kafka["Apache Kafka<br/>Location Stream"]
        LocDB["Location History DB<br/>(Cassandra/TimescaleDB)"]
        RoadGraph["Road Graph DB<br/>(Adjacency list, pre-computed)"]
        TileStorage["Tile Storage<br/>(Object Storage — S3)"]
        GeoDB["Geocoding DB<br/>(Elasticsearch)"]
        TrafficDB["Traffic DB<br/>(Time-series)"]
    end

    subgraph "CDN Layer"
        CDN["Tile CDN<br/>(CloudFront/Akamai)<br/>Global Edge PoPs"]
    end

    subgraph "ML Pipeline"
        MLPipeline["ML Model<br/>ETA Prediction<br/>Traffic Prediction"]
    end

    MobileApp --> APIGW
    WebApp --> APIGW
    MobileApp -->|"Tile requests"| CDN

    APIGW --> LocSvc
    APIGW --> NavSvc
    APIGW --> MapSvc
    APIGW --> GeoSvc
    APIGW --> SearchSvc

    LocSvc -->|"Publish location"| Kafka
    Kafka --> TrafficSvc
    Kafka --> LocDB
    TrafficSvc --> TrafficDB
    TrafficSvc --> MLPipeline

    NavSvc --> RoadGraph
    NavSvc --> ETASvc
    ETASvc --> TrafficDB
    ETASvc --> MLPipeline

    MapSvc --> TileStorage
    TileStorage --> CDN

    GeoSvc --> GeoDB
    SearchSvc --> GeoDB

2.3 Request Flow — 3 luồng chính

Luồng 1: Map Rendering (User mở app, xem bản đồ)

1. Client tính toán cần tiles nào dựa trên viewport (vị trí + zoom level)
2. Kiểm tra local cache (mobile) hoặc browser cache (web)
3. Nếu cache miss → request tới CDN
4. Nếu CDN cache miss → request tới Map Rendering Service → lấy từ Tile Storage (S3)
5. CDN cache tile → trả về client
6. Client render tiles ghép lại thành bản đồ hoàn chỉnh

Luồng 2: Navigation (User bấm “Chỉ đường”)

1. Client gửi origin (vị trí hiện tại) + destination + preferences (xe hơi/đi bộ/…)
2. API Gateway route tới Navigation Service
3. Navigation Service gọi Geocoding Service (nếu user nhập địa chỉ text)
4. Navigation Service query Road Graph DB để tìm route
5. Navigation Service gọi ETA Service để tính thời gian cho mỗi route
6. ETA Service lấy traffic data real-time + historical patterns + ML prediction
7. Trả về 2-3 routes với ETA, khoảng cách, turn-by-turn instructions

Luồng 3: Location Update (Background, liên tục)

1. Mobile client thu thập GPS coordinates (mỗi 1-3 giây khi navigating, mỗi 15-30 giây khi idle)
2. Client batch nhiều data points lại → gửi 1 request mỗi 15-30 giây (tiết kiệm battery + bandwidth)
3. Location Service nhận batch → publish lên Kafka
4. Kafka consumers: (a) Lưu vào Location History DB, (b) Feed vào Traffic Service để tính real-time traffic

---

Step 3 — Deep Dive

3.1 Map Tiles — Chia bản đồ thành miếng ghép hình

Khái niệm Tile Pyramid

hãy tưởng tượng bạn có một bức ảnh vệ tinh chụp toàn bộ Trái Đất. Bức ảnh này có độ phân giải cực kỳ lớn — nếu in ra sẽ to bằng một sân bóng đá. Hiển thị nguyên bức ảnh này trên điện thoại là bất khả thi (quá nặng, quá lớn). Giải pháp: cắt nhỏ bức ảnh thành nhiều mảnh vuông (tiles), và chỉ load những mảnh mà user đang nhìn thấy.

21 Zoom Levels (từ 0 đến 20):

Zoom Level	Số tiles	Mỗi tile bao phủ	Sử dụng
0	1 tile (1x1)	Toàn bộ thế giới	Overview toàn cầu
1	4 tiles (2x2)	1/4 thế giới	Nhìn các lục địa
2	16 tiles (4x4)	1/16 thế giới	Nhìn các quốc gia lớn
3	64 tiles (8x8)	…	Nhìn nhóm quốc gia
…	…	…	…
10	~1 triệu tiles	~150m x 150m	Nhìn thành phố
15	~1 tỉ tiles	~5m x 5m	Nhìn khu phố, đường
20	~1 ngàn tỉ tiles	~0.15m x 0.15m	Nhìn chi tiết nhà, vỉa hè

Công thức tính số tiles tại mỗi zoom level:

$$Tile{s}_{zoom}=4^{zoom}=2^{zoom}\times 2^{zoom}$$

Ví dụ:

$$Tile{s}_{zoom=10}=4^{10}=1,048,576\approx 1Mtiles$$ $$Tile{s}_{zoom=20}=4^{20}=1,099,511,627,776\approx 1.1Ttiles$$

Tile Pyramid Diagram

graph TD
    subgraph "Tile Pyramid — Zoom Levels"
        Z0["Zoom 0<br/>1 tile<br/>Toan bo the gioi"]
        Z1["Zoom 1<br/>4 tiles (2x2)<br/>Cac luc dia"]
        Z2["Zoom 2<br/>16 tiles (4x4)<br/>Cac quoc gia"]
        Z10["Zoom 10<br/>~1M tiles<br/>Thanh pho"]
        Z15["Zoom 15<br/>~1B tiles<br/>Duong pho"]
        Z20["Zoom 20<br/>~1T tiles<br/>Chi tiet nha"]
    end

    Z0 -->|"Moi tile chia thanh 4"| Z1
    Z1 -->|"Moi tile chia thanh 4"| Z2
    Z2 -->|"..."| Z10
    Z10 -->|"..."| Z15
    Z15 -->|"..."| Z20

    style Z0 fill:#e1f5fe
    style Z1 fill:#b3e5fc
    style Z2 fill:#81d4fa
    style Z10 fill:#4fc3f7
    style Z15 fill:#29b6f6
    style Z20 fill:#0288d1

Vector Tiles vs Raster Tiles

Đặc điểm	Raster Tiles	Vector Tiles
Format	PNG/JPEG image	Protocol Buffers (binary data)
Kích thước	20-100 KB/tile	5-30 KB/tile (nhỏ hơn 3-5x)
Rendering	Server render sẵn → client chỉ hiển thị	Client render từ data (GPU-accelerated)
Zoom	Mờ khi zoom giữa 2 level (pixelated)	Mượt mà ở mọi mức zoom (smooth)
Customization	Không — ảnh đã render cố định	Có — client tự style (dark mode, highlight roads, etc.)
Offline size	Lớn	Nhỏ hơn nhiều
CPU client	Thấp (chỉ hiện ảnh)	Cao hơn (phải render)
Bandwidth	Lớn hơn	Tiết kiệm hơn

Xu hướng hiện tại: Google Maps, Apple Maps, Mapbox đều chuyển sang vector tiles. Lý do chính: bandwidth tiết kiệm + smooth zoom + dynamic styling (dark mode khi lái xe ban đêm).

Tại sao vector tiles thắng? hãy nghĩ thế này: raster tile giống như bạn chụp ảnh bản đồ rồi gửi qua. Vector tile giống như bạn gửi data (đường này ở đâu, nhà này hình gì, tên đường là gì) rồi để điện thoại tự vẽ. Gửi data nhẹ hơn gửi ảnh, và điện thoại ngày nay đủ mạnh để vẽ rất nhanh.

Tile Addressing — Cách xác định tile nào cần load

Mỗi tile được xác định bởi 3 tham số: (zoom, x, y)

• zoom: zoom level (0-20)
• x: column index (0 đến $2^{zoom}-1$)
• y: row index (0 đến $2^{zoom}-1$)

URL pattern:

https://tiles.maps.example.com/{zoom}/{x}/{y}.pbf

Ví dụ: https://tiles.maps.example.com/15/26177/15123.pbf — tile ở zoom 15, cột 26177, hàng 15123.

Client tính toán tiles cần hiển thị dựa trên:

1. Viewport (màn hình đang nhìn thấy phạm vi nào)
2. Zoom level hiện tại
3. Pre-fetch tiles xung quanh viewport (anticipatory loading)

---

3.2 Map Rendering — Từ tile đến bản đồ trên màn hình

Tile CDN Architecture

Map tiles là static content (ít thay đổi — chỉ cập nhật khi có road mới hoặc building mới). Đây là bài toán CDN kinh điển — tham khảo Tuan-03-Networking-DNS-CDN.

Multi-layer caching strategy:

Layer	Nơi lưu	Cache Duration	Hit Ratio (ước tính)
L1: Client Cache	Mobile app local storage / Browser cache	30 ngày (tiles ít thay đổi)	~70-80%
L2: CDN Edge	CloudFront/Akamai edge PoPs	7-30 ngày	~95-99% của requests còn lại
L3: CDN Origin Shield	Regional origin cache	30 ngày	~99% của requests còn lại
L4: Origin (S3)	Object storage	Permanent	100% (source of truth)

Key insight: Với 4 layers này, chỉ khoảng 0.01-0.1% tổng request thực sự chạm tới origin storage. Đây là lý do tại sao map rendering có thể phục vụ hàng tỉ request/ngày mà chỉ cần vài chục origin servers.

Tính toán cache hit ratio tổng thể:

$$Mis{s}_{total}=(1-Hi{t}_{L1})\times (1-Hi{t}_{L2})\times (1-Hi{t}_{L3})$$ $$Mis{s}_{total}=(1-0.75)\times (1-0.97)\times (1-0.99)=0.25\times 0.03\times 0.01=0.000075$$ $$Hi{t}_{total}=1-0.000075=99.9925\%$$

Chỉ 7.5 trong 100,000 requests thực sự phải lấy tile từ origin. Đây là sức mạnh của multi-layer caching.

Progressive Loading

Khi user zoom từ level 10 xuống level 15, bản đồ không đổi tức thì — nó progressive load:

1. Hiển thị tiles cũ (level 10) đang có trong cache — upscale (phóng to, hơi mờ)
2. Request tiles mới (level 15) từ CDN
3. Khi tiles mới về → fade-in thay thế tiles cũ → bản đồ sắc nét dần

Kỹ thuật này gọi là “show stale, fetch fresh” — user luôn nhìn thấy gì đó thay vì màn hình trắng, tạo cảm giác instant response.

Tile Pre-rendering Pipeline

Map tiles được pre-render offline (không render on-the-fly khi user request):

graph LR
    RawData["Raw Map Data<br/>(Roads, Buildings,<br/>POIs, Terrain)"]
    Pipeline["Tile Rendering Pipeline<br/>(Batch processing)"]
    TileStore["Tile Storage<br/>(S3 / GCS)"]
    CDN["CDN<br/>Global Distribution"]
    Client["Client<br/>Mobile / Web"]

    RawData -->|"Nightly batch +<br/>incremental updates"| Pipeline
    Pipeline -->|"Pre-rendered tiles<br/>21 zoom levels"| TileStore
    TileStore -->|"Origin"| CDN
    CDN -->|"Edge cache"| Client

Khi nào re-render tiles?

• Scheduled: Mỗi tuần hoặc mỗi tháng — cập nhật roads mới, buildings mới
• Incremental: Chỉ re-render tiles bị ảnh hưởng bởi thay đổi (không render lại toàn bộ)
• Priority: Khu vực đông dân (thành phố lớn) re-render thường xuyên hơn khu vực hoang vũ

---

3.3 Location Service — Thu thập vị trí từ hàng tỉ device

Bài toán

Mỗi giây, hàng triệu device gửi vị trí của mình (latitude, longitude, timestamp, speed, heading) về server. Đây là write-heavy workload với volume cực lớn.

Batching Strategy

Gửi GPS coordinates mỗi giây là lãng phí (tốn battery, tốn bandwidth, server không cần độ chi tiết). Thay vào đó:

Trạng thái user	Tần suất gửi	Lý do
Đang navigate (lái xe)	Batch mỗi 15 giây (gồm 15 data points)	Cần độ chính xác cao để cập nhật traffic
App mở nhưng không navigate	Batch mỗi 30 giây (gồm 5-10 data points)	Tiết kiệm battery, vẫn cập nhật traffic
App chạy background	Batch mỗi 5 phút hoặc không gửi	Tối ưu battery
App đóng	Không gửi	Không cần

Payload của một batch:

Field	Type	Size	Mô tả
user_id	string	16 bytes	Anonymized ID
timestamps[]	int64 array	8 bytes x N	Unix timestamp mỗi data point
latitudes[]	double array	8 bytes x N	Vĩ độ
longitudes[]	double array	8 bytes x N	Kinh độ
speeds[]	float array	4 bytes x N	Tốc độ (m/s)
headings[]	float array	4 bytes x N	Hướng di chuyển (0-360 độ)
accuracy	float	4 bytes	Độ chính xác GPS (mét)
transport_mode	enum	1 byte	Car, bike, walk, etc.

Với N = 15 data points, payload khoảng 700 bytes — rất nhẹ.

Ingestion Pipeline

graph LR
    subgraph "Millions of Devices"
        D1["Device 1"]
        D2["Device 2"]
        DN["Device N"]
    end

    subgraph "Ingestion Layer"
        LB["Load Balancer"]
        LS1["Location Service<br/>Instance 1"]
        LS2["Location Service<br/>Instance 2"]
        LSN["Location Service<br/>Instance N"]
    end

    subgraph "Message Queue"
        K["Apache Kafka<br/>Partitioned by<br/>geo-region"]
    end

    subgraph "Consumers"
        C1["Traffic Aggregator<br/>(Real-time)"]
        C2["Location History<br/>Writer (Batch)"]
        C3["ML Feature<br/>Pipeline"]
    end

    subgraph "Storage"
        TSDB["Location History<br/>Cassandra / TimescaleDB"]
        TrafficStore["Traffic Store<br/>Redis + Time-series DB"]
    end

    D1 --> LB
    D2 --> LB
    DN --> LB
    LB --> LS1
    LB --> LS2
    LB --> LSN
    LS1 --> K
    LS2 --> K
    LSN --> K
    K --> C1
    K --> C2
    K --> C3
    C1 --> TrafficStore
    C2 --> TSDB

Tại sao dùng Kafka? (Tham khảo Tuan-08-Message-Queue)

Lý do	Giải thích
Decouple	Location Service chỉ cần ghi vào Kafka — không cần biết ai sẽ đọc
Buffer	Nếu Traffic Aggregator bị chậm, Kafka giữ data — không mất
Multiple consumers	Cùng một location event được đọc bởi Traffic Aggregator, History Writer, ML Pipeline — fan-out
Partitioning	Partition theo geo-region → các consumer xử lý song song
Throughput	Kafka xử lý được hàng triệu events/giây trên một cluster — phù hợp với 33M updates/s
Durability	Data được replicate, không mất khi node chết

Location History Storage

Lựa chọn database: Cassandra hoặc TimescaleDB

Tiêu chí	Cassandra	TimescaleDB
Data model	Wide-column	Relational (PostgreSQL extension)
Write throughput	Cực cao (hàng triệu writes/s)	Cao (trăm nghìn writes/s)
Time-series query	Cần thiết kế schema cẩn thận	Built-in time-series functions
Compression	Tốt (50-70%)	Rất tốt (90%+ với columnar compression)
Scale	Horizontal (thêm node)	Horizontal (distributed hypertables)

Schema (Cassandra):

Column	Type	Mô tả
user_id	UUID	Partition key — phân tán data theo user
timestamp	TIMESTAMP	Clustering key — sắp xếp theo thời gian
lat	DOUBLE	Vĩ độ
lng	DOUBLE	Kinh độ
speed	FLOAT	Tốc độ
heading	FLOAT	Hướng
accuracy	FLOAT	Độ chính xác GPS

Partition key = user_id → tất cả location history của 1 user nằm trên cùng partition → query “lịch sử di chuyển của user X trong 7 ngày qua” chỉ cần đọc 1 partition.

TTL (Time-to-Live): Location history chỉ giữ 30-90 ngày → tự động xóa data cũ → tiết kiệm storage.

---

3.4 Navigation/Routing — Tìm đường trong mê cung

Đây là trái tim của Google Maps — và cũng là phần phức tạp nhất.

Road Network là một Weighted Graph

toàn bộ mạng lưới đường giao thông có thể biểu diễn như một đồ thị có trọng số (weighted graph):

Khái niệm đồ thị	Tương ứng trong bản đồ
Node (đỉnh)	Giao lộ (intersection), điểm uốn của đường
Edge (cạnh)	Đoạn đường nối 2 giao lộ
Weight (trọng số)	Thời gian di chuyển (tính bằng giây/phút), KHÔNG phải khoảng cách

Tại sao weight là thời gian, không phải khoảng cách? Vì user muốn đến nhanh nhất, không phải ngắn nhất. Đường cao tốc 50km có thể nhanh hơn đường tắt 10km nếu đường tắt kẹt xe.

Quy mô của road graph:

Thông số	Giá trị ước tính
Số node (intersections) toàn cầu	~500 triệu
Số edge (road segments) toàn cầu	~1 tỉ
Average edges per node	~4 (mỗi giao lộ thường có 3-5 nhánh)
Data size (adjacency list)	~100 GB (compressed)

Tiến hóa của Routing Algorithm

Giai đoạn 1: Dijkstra’s Algorithm

• Tìm đường ngắn nhất từ 1 điểm đến tất cả các điểm khác
• Độ phức tạp: $O((V+E)\log V)$ với priority queue
• Vấn đề: Với 500M nodes, Dijkstra duyệt qua hàng triệu nodes trước khi tìm được đường — quá chậm cho real-time (có thể mất vài giây)

Giai đoạn 2: A Algorithm*

• Cải tiến Dijkstra bằng heuristic — ưu tiên duyệt nodes theo hướng về đích
• Heuristic: Khoảng cách đường chim bay (haversine distance) từ node hiện tại đến đích
• Nhanh hơn Dijkstra ~2-5x vì loại bỏ nhiều nodes không cần thiết
• Vấn đề: Vẫn chậm khi route dài (Sài Gòn → Hà Nội) vì graph quá lớn

Giai đoạn 3: Contraction Hierarchies (CH) — Pre-computation là chìa khóa

Đây là breakthrough giúp Google Maps tìm đường trong milliseconds thay vì seconds.

Ý tưởng cốt lõi: Pre-compute “shortcuts” trong graph.

Bước	Mô tả	Analogy
1. Xếp hạng nodes	Mỗi node được gán một “importance level” — giao lộ lớn quan trọng hơn giao lộ nhỏ	Quốc lộ quan trọng hơn hẻm
2. Contract nodes	Bắt đầu từ node ít quan trọng nhất, “loại bỏ” nó và thêm shortcut edges nối các node lân cận	Loại bỏ các hẻm nhỏ, thêm shortcut “từ giao lộ A đến giao lộ C, mất 5 phút”
3. Xây hierarchy	Sau khi contract hết, ta có một hierarchy graph — level thấp là đường nhỏ, level cao là đường lớn	Giống như bản đồ chỉ có quốc lộ + cao tốc
4. Query	Tìm đường = search từ origin lên hierarchy + search từ destination lên hierarchy → gặp nhau ở giữa	”Lật xe ra đường lớn gần nhất → đi đường lớn → rẽ vào đường nhỏ gần đích”

Hiệu quả:

$$\text{Dijkstra treˆn toaˋn graph: }O(V\log V)\approx \text{millions of nodes explored}$$ $$\text{Contraction Hierarchies query: }O(\text{hundreds of nodes explored})\approx \text{< 1ms}$$

Aha Moment: Pre-computation là lý do Google Maps trả lời route gần như tức thì. Việc contract graph mất vài giờ để tính (chạy offline), nhưng mỗi query chỉ mất < 1 millisecond. Trade-off kinh điển: offline compute time ↔ online query speed.

Nhưng pre-computation có vấn đề: Khi traffic thay đổi (kẹt xe), edge weights thay đổi → pre-computed shortcuts không còn chính xác. Giải pháp: Routing Tiles (xem bên dưới).

Routing Tiles — Partition Road Graph

Thay vì lưu toàn bộ road graph trong 1 cục, Google chia graph thành nhiều routing tiles (tương tự map tiles nhưng cho road data):

Level	Tile bao phủ	Chứa gì	Sử dụng
Level 0 (Local)	~1km x 1km	Đường nhỏ, hẻm, ngõ	Routing trong phạm vi khu phố
Level 1 (Regional)	~10km x 10km	Đường chính, tỉnh lộ	Routing trong thành phố
Level 2 (Country)	~100km x 100km	Quốc lộ, cao tốc	Routing liên tỉnh
Level 3 (Global)	~1000km x 1000km	Cao tốc quốc tế	Routing quốc tế

Routing algorithm với tiles:

1. Origin nằm trong tile A (local level) → load tile A
2. Destination nằm trong tile B (local level) → load tile B
3. Tìm đường trong tile A từ origin đến boundary của tile
4. Tìm đường giữa boundaries bằng higher-level tiles (regional/country)
5. Tìm đường trong tile B từ boundary đến destination
6. Ghép 3 đoạn lại → route hoàn chỉnh

Lợi ích:

• Chỉ cần load vài routing tiles thay vì toàn bộ graph → tiết kiệm memory
• Có thể cache routing tiles tại CDN edge
• Có thể cập nhật traffic cho từng tile độc lập (không cần re-compute toàn bộ)

Routing Algorithm Flow

graph TD
    Start["User request:<br/>Origin → Destination"]
    Geocode["Geocode dia chi<br/>(neu can)"]
    FindTiles["Xac dinh routing tiles<br/>chua Origin va Destination"]
    LoadTiles["Load routing tiles<br/>(local + regional + country)"]
    LocalO["Tim duong trong<br/>local tile cua Origin"]
    Regional["Tim duong qua<br/>regional/country tiles"]
    LocalD["Tim duong trong<br/>local tile cua Destination"]
    Merge["Ghep 3 doan<br/>thanh route hoan chinh"]
    Traffic["Overlay real-time<br/>traffic data"]
    ETA["Tinh ETA cho route"]
    AltRoutes["Tinh 2-3 alternative routes"]
    Response["Tra ve routes + ETA<br/>+ turn-by-turn instructions"]

    Start --> Geocode
    Geocode --> FindTiles
    FindTiles --> LoadTiles
    LoadTiles --> LocalO
    LoadTiles --> Regional
    LoadTiles --> LocalD
    LocalO --> Merge
    Regional --> Merge
    LocalD --> Merge
    Merge --> Traffic
    Traffic --> ETA
    ETA --> AltRoutes
    AltRoutes --> Response

Real-time Traffic Overlay

Pre-computed routes dựa trên static weights (tốc độ giới hạn của đường). Nhưng thực tế, traffic thay đổi mỗi phút. Giải pháp:

1. Pre-compute routes với static weights (Contraction Hierarchies)
2. Overlay real-time traffic data lên route:
   • Mỗi road segment có một traffic factor (1.0 = thông thoáng, 2.0 = chậm gấp đôi, 5.0 = kẹt nặng)
   • Nhân static travel time với traffic factor → adjusted travel time

$$Tim{e}_{adjusted}(edge)=Tim{e}_{static}(edge)\times TrafficFactor(edge)$$

3. Nếu traffic làm route hiện tại chậm hơn alternative → re-route (tính lại route)

Alternative Routes

Google Maps thường hiển thị 2-3 routes. Cách tạo alternative routes:

Phương pháp	Mô tả
Penalty method	Sau khi tìm route tốt nhất, tăng weight của các edges trong route đó, rồi tìm lại → được route khác
Plateau method	Tìm các đoạn đường “plateau” (đoạn mà route tốt nhất và alternative đều đi qua) → buộc route alternative đi đường khác ở phần còn lại
k-shortest paths	Tìm k đường ngắn nhất trong graph (thường k = 3)

Mỗi alternative route được lọc để đảm bảo:

• Khác biệt ít nhất 30% so với route chính (không muốn 2 routes gần giống nhau)
• ETA không quá 50% lớn hơn route nhanh nhất (không đề xuất đường quá chậm)
• Không đi qua những đoạn nguy hiểm hoặc bị cấm

---

3.5 Geocoding & Reverse Geocoding

Geocoding: Địa chỉ → Tọa độ

Input	Output	Ví dụ
Địa chỉ text	Latitude, Longitude	”227 Nguyen Van Cu, Q5, HCM” → (10.7594, 106.6815)

Cách hoạt động:

1. Parsing: Tách địa chỉ thành các thành phần (số nhà, tên đường, quận, thành phố)
2. Standardization: Chuẩn hóa viết tắt (“Q5” → “Quận 5”, “HCM” → “Hồ Chí Minh”)
3. Lookup: Tìm trong geocoding database (Elasticsearch với geo-index)
4. Interpolation: Nếu địa chỉ chính xác không có trong DB → nội suy vị trí giữa 2 địa chỉ đã biết

Address Interpolation (Nội suy địa chỉ):

Nếu DB có:

• Số 221 Nguyen Van Cu → tọa độ A
• Số 231 Nguyen Van Cu → tọa độ B

Thì số 227 ≈ vị trí (227 - 221) / (231 - 221) = 60% từ A đến B

$$La{t}_{227}=La{t}_{221}+0.6\times (La{t}_{231}-La{t}_{221})$$ $$Ln{g}_{227}=Ln{g}_{221}+0.6\times (Ln{g}_{231}-Ln{g}_{221})$$

Reverse Geocoding: Tọa độ → Địa chỉ

Input	Output	Ví dụ
Latitude, Longitude	Địa chỉ text	(10.7594, 106.6815) → “227 Nguyen Van Cu, Quan 5, TP.HCM”

Cách hoạt động:

1. Tìm road segment gần nhất với tọa độ (nearest-neighbor search bằng spatial index — R-tree hoặc geohash)
2. Project điểm lên road segment → tìm vị trí chính xác trên đường
3. Interpolation ngược → ước tính số nhà
4. Trả về địa chỉ đầy đủ

Database: Elasticsearch với geo_point và geo_shape types, hoặc PostgreSQL + PostGIS extension.

---

3.6 Traffic Data — Mạch máu của bản đồ

Nguồn dữ liệu traffic

Nguồn	Mô tả	Độ tin cậy	Latency
User GPS data	Vị trí + tốc độ của hàng triệu user đang đi trên đường	Cao (số lượng lớn → trung bình chính xác)	Real-time (30-60s delay)
Historical patterns	Dữ liệu giao thông lịch sử theo giờ/ngày/mùa	Cao cho patterns lặp lại	N/A (offline)
Government sensors	Camera giao thông, vòng từ (induction loops)	Rất cao nhưng coverage thấp	Near real-time
Third-party data	Data từ taxi companies, ride-hailing, logistics	Trung bình	Near real-time
Events	Tai nạn, sửa đường, sự kiện lớn, thời tiết	Biến động	Reported manually hoặc ML-detected

Real-time Traffic Processing Pipeline

1. Ingest: Nhận location updates từ Kafka (33M updates/s peak)
2. Map-match: Snap GPS coordinates lên road segments (GPS có sai số 5-15m → cần xác định user đang trên đường nào)
3. Speed calculation: Tính tốc độ trung bình trên mỗi road segment trong window 2-5 phút
4. Aggregation: Gom nhóm theo road segment → tính tốc độ trung bình, density
5. Traffic level: So sánh tốc độ thực tế với tốc độ giới hạn → xác định traffic level

$$TrafficFactor=\frac{FreeFlowSpeed}{CurrentSpeed}$$

Traffic Factor	Màu	Nghĩa
1.0 - 1.3	Xanh lá	Thông thoáng
1.3 - 2.0	Vàng/Cam	Chậm
2.0 - 5.0	Đỏ	Kẹt xe
> 5.0	Đỏ đậm	Kẹt nặng

Map-Matching — Bài toán không hề đơn giản

GPS coordinates có sai số (5-15m trong thành phố, lớn hơn trong khu vực nhiều tòa nhà cao tầng). Bài toán: xác định user đang trên đường nào?

Tình huống khó	Vấn đề
2 đường song song cách 10m	GPS không đủ chính xác để phân biệt
Đường trên cầu và đường bên dưới	Cùng tọa độ lat/lng nhưng khác độ cao
User ở giao lộ	Đang trên đường nào trong 4 đường?
GPS nhảy (urban canyon)	Tòa nhà cao phản xạ GPS signal

Giải pháp: Hidden Markov Model (HMM) — xem xét chuỗi các GPS points liên tiếp, không chỉ 1 point độc lập. Nếu 10 points trước đều trên đường A, thì point hiện tại có xác suất cao cũng trên đường A (dù GPS nhảy sang gần đường B).

---

3.7 Adaptive ETA — Tính thời gian đến chính xác

ETA (Estimated Time of Arrival) là metric quan trọng nhất của navigation. User đánh giá Google Maps dựa trên ETA có chính xác không.

3 nguồn dữ liệu cho ETA

Nguồn	Mô tả	Ưu điểm	Nhược điểm
Historical data	Trung bình thời gian đi qua road segment X vào thứ 2, 8:00 AM	Ổn định, phù hợp patterns lặp lại	Không biết tai nạn bất ngờ
Real-time traffic	Tốc độ hiện tại trên road segment X	Phản ánh tình hình ngay lúc này	Chỉ biết hiện tại, không dự đoán tương lai
ML Prediction	Model dự đoán traffic 15-30-60 phút tới	Dự đoán trước — ETA tính cho đường bạn sẽ đi qua trong tương lai	Cần data + compute lớn

ML Model cho ETA Prediction

Feature	Mô tả
Time features	Giờ, thứ, tháng, ngày lễ, ngày thường
Current traffic	Tốc độ hiện tại trên route và các road segments xung quanh
Historical traffic	Trung bình tốc độ của cùng giờ/thứ/mùa trong 12 tháng qua
Weather	Mưa, sương mù, bão → ảnh hưởng tốc độ
Events	Concert, trận bóng đá, hỗ trợ → ảnh hưởng traffic
Road attributes	Số làn, tốc độ giới hạn, có traffic light không
Segment sequence	Các road segments nối tiếp nhau trên route → model học dependencies

Output: ETA prediction cho mỗi road segment trên route → cộng lại = tổng ETA.

$$ET{A}_{total}=\sum _{i=1}^{N}ET{A}_{predicted}(segmen{t}_i)$$

Google báo cáo ETA accuracy: sai lệch trung bình khoảng 5-8% so với thực tế — cực kỳ chính xác cho một hệ thống phục vụ hàng tỉ requests.

ETA Update trong quá trình navigate

Khi user đang lái xe, ETA được cập nhật liên tục (mỗi 30-60 giây):

1. Hệ thống biết vị trí hiện tại của user (từ location updates)
2. Tính lại ETA cho phần đường còn lại (không phải toàn bộ route)
3. Nếu traffic thay đổi đáng kể → có thể re-route (đề xuất đường khác)

---

Capacity Estimation (Ước lượng dung lượng)

Assumptions (Giả thiết)

Thông số	Giá trị	Ghi chú
DAU	1 Billion (1B)	Google Maps scale
Users đồng thời gửi location updates	10% DAU = 100M	Không phải ai cũng mở app cùng lúc
Location update interval	30 giây/batch	Trung bình (navigate: 15s, idle: 30s)
Navigation requests/user/day	2	Trung bình (đi làm + về nhà)
Map tile requests/user/session	50 tiles	Scroll + zoom trung bình
Sessions/user/day	3	Mở app 3 lần/ngày
Peak multiplier	3x	Giờ cao điểm sáng + chiều

Location Update QPS

$$LocationQP{S}_{avg}=\frac{100Musers}{30s}=3,333,333updates/s\approx 3.3Mupdates/s$$ $$LocationQP{S}_{peak}=3.3M\times 3=10Mupdates/s$$

Lưu ý: Con số 33M/s (1B users / 30s) là theoretical maximum nếu tất cả user gửi cùng lúc. Thực tế, chỉ 10% DAU active tại một thời điểm → 10M peak.

Bandwidth cho location updates:

$$Payloa{d}_{avg}=700bytes/batch$$ $$Bandwidt{h}_{peak}=10M\times 700bytes=7GB/s=56Gbps$$

Con số 56 Gbps là rất lớn — cần nhiều server và Kafka cluster để xử lý.

Navigation QPS

$$Navigationrequests/day=1B\times 2=2Brequests/day$$ $$NavigationQP{S}_{avg}=\frac{2B}{86,400}\approx 23,148requests/s\approx 23K/s$$ $$NavigationQP{S}_{peak}=23K\times 3=69K/s\approx 70K/s$$

Map Tile QPS

$$Tilerequests/day=1B\times 3sessions\times 50tiles=150Btilerequests/day$$ $$TileQP{S}_{avg}=\frac{150B}{86,400}\approx 1,736,111/s\approx 1.7M/s$$ $$TileQP{S}_{peak}=1.7M\times 3=5.1M/s$$

Nhưng nhờ multi-layer caching (99.99% cache hit), chỉ ~500/s thực sự chạm origin. CDN xử lý phần lớn.

Storage Estimation

Map Tile Storage

$$Totaltile{s}_{alllevels}=\sum _{z=0}^{20}{4}^z=\frac{4^{21}-1}{4-1}\approx 1.47\times 10^{12}\approx 1.5Ttiles$$

Nhưng không phải tất cả tiles đều có data (70% Trái Đất là biển, sa mạc, rừng không cần tiles chi tiết):

$$Activetiles\approx 1.5T\times 10\%=150Btiles$$ $$Avgtilesize(vector)=15KB$$ $$Totaltilestorage=150B\times 15KB=2.25PB\approx 2.3PB$$

Location History Storage

$$Locationevents/day=3.3M/s\times 86,400=285Bevents/day$$ $$Eventsize=50bytes(compressed)$$ $$Storage/day=285B\times 50bytes=14.25TB/day$$ $$Storage/month(30dayretention)=14.25\times 30=427.5TB\approx 430TB$$

Road Graph Storage

$$Nodes=500M,Edges=1B$$ $$Nodesize=16bytes(lat+lng)$$ $$Edgesize=32bytes(from+to+weight+metadata)$$ $$Graphsize=500M\times 16+1B\times 32=8GB+32GB=40GB(raw)$$ $$WithContractionHierarchiesoverhead(2x)=80GB$$

Road graph chỉ 80 GB — đủ nhỏ để load vào RAM của một cluster nhỏ. Đây là lý do routing có thể rất nhanh.

Tổng hợp Storage

Data	Size	Ghi chú
Map tiles (all zoom levels)	~2.3 PB	Lớn nhất, lưu trên object storage + CDN
Location history (30 ngày)	~430 TB	Time-series, TTL 30 ngày
Road graph + CH	~80 GB	Nhỏ, có thể in-memory
Geocoding index	~50 GB	Elasticsearch cluster
Traffic data (7 ngày)	~10 TB	Time-series, TTL 7 ngày
Tổng	~2.8 PB	Map tiles chiếm ~80%

---

Security — Bảo vệ dữ liệu vị trí

4.1 Location Data Privacy — Vấn đề nghiêm trọng nhất

Vị trí của user là dữ liệu nhạy cảm bậc nhất — biết vị trí là biết nhà, chỗ làm việc, thói quen đi lại, mối quan hệ cá nhân.

Mối đe dọa	Mô tả	Giải pháp
Data breach	Hacker lấy được location history của user	Encryption at rest (AES-256), encryption in transit (TLS 1.3)
Internal abuse	Nhân viên truy cập data user	Access control nghiêm ngặt, audit log, least-privilege, data masking
Government request	Chính phủ yêu cầu data vị trí	Legal team review, chỉ cung cấp khi có lệnh tòa, minimization (chỉ cung cấp data cần thiết)
Third-party sharing	Bán data vị trí cho advertiser	Anonymization, aggregation (chỉ chia sẻ aggregate traffic, không chia sẻ individual location)

4.2 Anonymization of Traffic Data

Khi sử dụng GPS data để tính traffic, cần anonymize để không thể truy nguồn về individual user:

Kỹ thuật	Mô tả
K-anonymity	Chỉ hiển thị traffic data khi có ít nhất K users trên road segment (thường K >= 5) — không thể identify individual
Differential privacy	Thêm noise vào aggregate data — kết quả tổng thể vẫn chính xác nhưng không thể suy ra individual
Data aggregation	Chỉ lưu aggregate speed/density per road segment, không lưu “user X đi qua điểm Y lúc Z”
Ephemeral IDs	Thay user_id bằng random session ID, rotate mỗi session → không liên kết được sessions
Geo-fencing sensitive areas	Không thu thập chi tiết location gần bệnh viện, trụ sở tôn giáo, cơ sở quân sự

4.3 Fake GPS Injection Prevention

Một số user dùng app giả lập GPS (mock location) để gian lận (ví dụ: tài xế Grab giả vị trí). Cách ngăn chặn:

Kỹ thuật	Mô tả
Sensor fusion	So sánh GPS với accelerometer, gyroscope, cell tower triangulation — nếu GPS nói user đang chạy 60 km/h nhưng accelerometer không rung → fake
Movement pattern analysis	GPS teleport (vị trí nhảy đột ngột 10km) → flag suspicious
Speed consistency	Tốc độ thay đổi quá nhanh (0 → 200 km/h trong 1 giây) → không hợp lý
Cell tower cross-reference	Vị trí GPS phải gần cell tower đang kết nối
Device attestation	Android SafetyNet / iOS DeviceCheck — xác minh device không bị root/jailbreak

4.4 Rate Limiting

Endpoint	Rate Limit	Lý do
Location update	10 requests/phút/user	Ngăn spam location (1 batch mỗi 15-30s là đủ)
Navigation request	30 requests/phút/user	Ngăn automated scraping routes
Tile request	1000 requests/phút/user	Ngăn bot download toàn bộ map data
Geocoding	60 requests/phút/user	Ngăn batch geocoding (dịch vụ trả phí riêng)

Tham khảo Tuan-09-Rate-Limiter cho chi tiết implementation.

4.5 Data Retention Policies

Dữ liệu	Retention	Lý do
Raw GPS location	30 ngày	Chỉ cần cho traffic analysis, sau đó aggregate và xóa raw
Aggregated traffic	2 năm	Historical patterns cho ML model
User search history	90 ngày (hoặc user xóa)	Personalization, GDPR right to delete
Navigation history	90 ngày (hoặc user xóa)	Trip history feature
Map tiles	Vĩnh viễn (cập nhật theo version)	Core asset
Anonymized analytics	5 năm	Business intelligence

4.6 Compliance

Regulation	Yêu cầu	Ảnh hưởng
GDPR (EU)	Right to access, right to delete, data minimization	User có thể download hoặc xóa tất cả location data
CCPA (California)	Tương tự GDPR cho California residents	Opt-out of data sale
LGPD (Brazil)	Tương tự GDPR cho Brazil	Cần consent rõ ràng
PDPA (Vietnam/Thailand)	Luật bảo vệ dữ liệu cá nhân	Cần consent, data localization có thể yêu cầu

---

DevOps — Monitoring & Observability

Tham khảo Tuan-13-Monitoring-Observability cho nền tảng. Dưới đây là các metrics đặc thù cho Google Maps.

5.1 Location Ingestion Pipeline Monitoring

Metric	Mục tiêu	Alert khi
Kafka consumer lag	< 10 giây	> 30 giây (data cũ quá, traffic không real-time)
Location update throughput	3-10M events/s	< 1M events/s (có vấn đề ở ingestion) hoặc > 15M events/s (bất thường, có thể là attack)
Failed location updates	< 0.1%	> 1%
Map-matching accuracy	> 95% GPS points matched thành công	< 90%
Kafka partition skew	Even distribution	Một partition có > 2x trung bình

5.2 Routing Performance Monitoring

Metric	Mục tiêu	Alert khi
Route calculation latency (p50)	< 200ms	> 500ms
Route calculation latency (p99)	< 2s	> 5s
Routing success rate	> 99.9%	< 99.5% (không tìm được route)
Contraction Hierarchies freshness	< 24 giờ từ lần rebuild cuối	> 48 giờ
Routing tile cache hit ratio	> 90%	< 80%
Alternative routes generated	>= 2 routes cho 95% requests	< 2 routes cho > 10% requests

5.3 Tile CDN Monitoring

Metric	Mục tiêu	Alert khi
CDN cache hit ratio	> 99%	< 95% (cache invalidation sai?)
Tile latency (CDN edge, p50)	< 50ms	> 100ms
Tile latency (origin, p50)	< 200ms	> 500ms
404 rate (missing tiles)	< 0.01%	> 0.1% (tile generation pipeline bị lỗi)
Tile freshness	< 7 ngày từ lần render cuối	> 30 ngày cho khu vực thành phố
Bandwidth cost	Budget-based	> 120% budget

5.4 ETA Accuracy Monitoring

Metric	Mục tiêu	Alert khi
ETA error (median)	< 8%	> 15%
ETA error (p95)	< 25%	> 40%
ETA under-estimate rate	< 30%	> 50% (user đến trễ → trải nghiệm xấu)
ML model staleness	< 24 giờ từ lần retrain cuối	> 48 giờ

5.5 Overall System Health Dashboard

Category	Key Metrics
Availability	Service uptime per component, error rate (5xx), circuit breaker trips
Latency	p50/p95/p99 cho mỗi service (location, routing, tiles, geocoding)
Throughput	QPS cho mỗi service, Kafka throughput, CDN bandwidth
Saturation	CPU/Memory/Disk cho mỗi cluster, Kafka partition fill rate
Business metrics	DAU, navigation starts/completions, search queries, user ratings

5.6 Alerting Hierarchy

Level	Mô tả	Ví dụ	Response time
P0 — Critical	Core feature bị down	Navigation không hoạt động, Kafka cluster down	< 5 phút
P1 — High	Performance degradation nghiêm trọng	Routing latency p99 > 10s, ETA sai > 30%	< 15 phút
P2 — Medium	Degradation nhẹ	CDN cache hit < 95%, location lag > 1 phút	< 1 giờ
P3 — Low	Cosmetic hoặc non-critical	Tile render pipeline chậm, analytics delay	< 24 giờ

---

Mermaid Diagrams — Tổng hợp

Overall System Architecture (Chi tiết)

graph TB
    subgraph "Client Layer"
        Mobile["Mobile Client<br/>iOS / Android"]
        Web["Web Client<br/>Browser"]
    end

    subgraph "Edge Layer"
        CDN["Tile CDN<br/>Global Edge PoPs<br/>99%+ cache hit"]
        APIGW["API Gateway<br/>Auth · Rate Limit · Route"]
    end

    subgraph "Application Layer"
        direction TB
        LocSvc["Location Service<br/>Write: 10M/s peak"]
        NavSvc["Navigation Service<br/>Read: 70K/s peak"]
        MapSvc["Map Rendering<br/>Tile metadata"]
        GeoSvc["Geocoding Service<br/>Address ↔ LatLng"]
        TrafficSvc["Traffic Aggregator<br/>Stream processing"]
        ETASvc["ETA Service<br/>ML-powered"]
    end

    subgraph "Message Queue"
        Kafka["Apache Kafka<br/>Location Events<br/>Partitioned by geo-region"]
    end

    subgraph "Storage Layer"
        S3["Object Storage (S3)<br/>Map Tiles — 2.3 PB"]
        Cassandra["Cassandra<br/>Location History — 430 TB"]
        TSDB["Time-series DB<br/>Traffic Data — 10 TB"]
        Graph["Road Graph (In-memory)<br/>+ Contraction Hierarchies<br/>80 GB"]
        ES["Elasticsearch<br/>Geocoding Index<br/>50 GB"]
        Redis["Redis Cluster<br/>Real-time traffic cache"]
    end

    subgraph "ML Platform"
        ETAModel["ETA Prediction Model"]
        TrafficModel["Traffic Prediction Model"]
        FeatureStore["Feature Store"]
    end

    Mobile -->|"Tile requests"| CDN
    Web -->|"Tile requests"| CDN
    Mobile --> APIGW
    Web --> APIGW
    CDN -->|"Cache miss"| S3

    APIGW --> LocSvc
    APIGW --> NavSvc
    APIGW --> GeoSvc

    LocSvc --> Kafka
    Kafka --> TrafficSvc
    Kafka --> Cassandra

    TrafficSvc --> TSDB
    TrafficSvc --> Redis
    TrafficSvc --> FeatureStore

    NavSvc --> Graph
    NavSvc --> ETASvc
    NavSvc --> GeoSvc

    ETASvc --> Redis
    ETASvc --> TSDB
    ETASvc --> ETAModel

    ETAModel --> FeatureStore
    TrafficModel --> FeatureStore

    GeoSvc --> ES
    MapSvc --> S3

Map Tile Pyramid (Visual)

graph TD
    subgraph "Tile Pyramid"
        L0["Level 0: 1 tile<br/>🌍 Toan cau<br/>~100 KB"]
        L5["Level 5: 1,024 tiles<br/>Cac quoc gia<br/>~10 MB total"]
        L10["Level 10: ~1M tiles<br/>Thanh pho<br/>~15 GB total"]
        L15["Level 15: ~1B tiles<br/>Duong pho<br/>~15 TB total"]
        L20["Level 20: ~1T tiles<br/>Chi tiet nha<br/>~2.3 PB total"]
    end

    L0 -->|"x4 moi level"| L5
    L5 -->|"x1024"| L10
    L10 -->|"x1024"| L15
    L15 -->|"x1024"| L20

    subgraph "Caching Strategy"
        Client["Client Cache<br/>~70-80% hit"]
        Edge["CDN Edge<br/>~97% hit"]
        Origin["Origin S3<br/>Source of truth"]
    end

    L20 -.->|"Served via"| Origin
    Origin -->|"Cached at"| Edge
    Edge -->|"Cached at"| Client

Location Update Pipeline (Chi tiết)

sequenceDiagram
    participant Device as Mobile Device
    participant LB as Load Balancer
    participant LS as Location Service
    participant K as Kafka
    participant TA as Traffic Aggregator
    participant HW as History Writer
    participant ML as ML Pipeline
    participant Redis as Redis (Traffic Cache)
    participant Cass as Cassandra (History)

    Note over Device: Thu thap GPS moi 1-3s
    Note over Device: Batch 15 data points

    Device->>LB: POST /location/batch (700 bytes)
    LB->>LS: Forward request
    LS->>LS: Validate + enrich data
    LS->>K: Publish to "location-events" topic
    LS-->>Device: 202 Accepted

    par Consumer Group 1
        K->>TA: Consume location events
        TA->>TA: Map-match GPS → road segments
        TA->>TA: Calculate speed per segment
        TA->>Redis: Update real-time traffic
    and Consumer Group 2
        K->>HW: Consume location events
        HW->>Cass: Write location history (TTL 30d)
    and Consumer Group 3
        K->>ML: Consume for feature engineering
        ML->>ML: Update feature store
    end

Navigation Request Flow (Chi tiết)

sequenceDiagram
    participant Client as Mobile Client
    participant APIGW as API Gateway
    participant Nav as Navigation Service
    participant Geo as Geocoding Service
    participant Graph as Road Graph (Memory)
    participant ETA as ETA Service
    participant Traffic as Traffic Cache (Redis)
    participant MLModel as ML Model

    Client->>APIGW: GET /route?origin=A&dest=B&mode=driving
    APIGW->>APIGW: Auth + Rate Limit
    APIGW->>Nav: Forward request

    Nav->>Geo: Geocode "A" → (lat1, lng1)
    Nav->>Geo: Geocode "B" → (lat2, lng2)
    Geo-->>Nav: Coordinates

    Nav->>Graph: Find route via Contraction Hierarchies
    Graph-->>Nav: Primary route (list of road segments)

    Nav->>Graph: Find 2 alternative routes
    Graph-->>Nav: Alt routes

    loop For each route
        Nav->>ETA: Calculate ETA for route
        ETA->>Traffic: Get real-time traffic per segment
        Traffic-->>ETA: Traffic factors
        ETA->>MLModel: Predict segment travel times
        MLModel-->>ETA: Predicted times
        ETA->>ETA: Combine: historical + real-time + ML
        ETA-->>Nav: ETA + traffic-adjusted times
    end

    Nav->>Nav: Rank routes by ETA
    Nav->>Nav: Generate turn-by-turn instructions
    Nav-->>APIGW: 3 routes + ETAs + instructions
    APIGW-->>Client: Response (< 3s total)

---

Aha Moments & Pitfalls

Aha Moments — Những insight quan trọng

#	Insight	Giải thích
1	Pre-computation là chìa khóa của routing	Contraction Hierarchies mất vài giờ để build offline, nhưng mỗi query chỉ mất < 1ms. Đây là trade-off kinh điển: offline compute ↔ online speed. Không có pre-computation, Google Maps không thể phục vụ 70K routing requests/s.
2	Tile caching tiết kiệm 99%+ compute	Nhờ multi-layer caching (client → CDN edge → origin shield → S3), chỉ 0.01% requests chạm origin. Map rendering service thực ra chỉ phục vụ pre-rendering pipeline, không phải user requests trực tiếp.
3	Location data volume là massive	10M updates/s, 14 TB/ngày, 430 TB/tháng — chỉ riêng location data. Cần Kafka để buffer, Cassandra/TimescaleDB để lưu, và TTL để tự động xóa data cũ. Không thể dùng traditional RDBMS.
4	Real-time traffic đòi hỏi stream processing	Traffic data phải được xử lý trong giây, không phải phút. Cần Kafka + stream processing framework (Flink/Spark Streaming). Batch processing (chạy mỗi 5 phút) là quá chậm.
5	ETA accuracy cần ML	Simple formula (khoảng cách / tốc độ giới hạn) cho ETA sai 30-50%. Cần combine historical patterns + real-time traffic + ML prediction để đạt sai số < 10%.
6	Road graph nhỏ bất ngờ	Toàn bộ road graph toàn cầu chỉ ~80 GB — đủ nhỏ để load vào RAM. Đây là lý do routing cực nhanh: không cần disk I/O.
7	Map-matching không đơn giản	GPS có sai số 5-15m. Ở thành phố (nhiều tòa nhà), sai số còn lớn hơn. Cần HMM (Hidden Markov Model) để xác định user đang trên đường nào — chỉ GPS point đơn lẻ là không đủ.
8	Vector tiles là tương lai	Nhỏ hơn 3-5x so với raster, smooth zoom, dynamic styling (dark mode) — tất cả các map providers lớn đều chuyển sang vector tiles. Client cần GPU nhưng smartphones hiện đại đủ mạnh.

Common Pitfalls — Các lỗi thường gặp khi thiết kế

#	Pitfall	Tại sao sai	Cách đúng
1	Tính route on-the-fly bằng Dijkstra	O(V log V) với 500M nodes = vài giây/request. Không scale với 70K QPS	Dùng Contraction Hierarchies (pre-computed), query < 1ms
2	Render tiles on-the-fly	5M tile requests/s peak — không server farm nào render kịp	Pre-render offline + CDN caching
3	Gửi GPS mỗi giây từ client	Tốn battery, tốn bandwidth, server bị overwhelm	Batch mỗi 15-30 giây, 15 data points/batch
4	Dùng RDBMS cho location history	14 TB/ngày writes, 10M writes/s — PostgreSQL không chịu nổi	Dùng Cassandra hoặc TimescaleDB (write-optimized)
5	Bỏ qua map-matching	GPS “227 Nguyen Van Cu” nhưng thực tế user đang trên đường bên cạnh → traffic data sai	Dùng HMM-based map-matching trước khi xử lý traffic
6	Không partition road graph	Load 80 GB graph mỗi lần routing request → chậm, tốn memory	Dùng routing tiles — chỉ load tiles liên quan
7	ETA chỉ dùng tốc độ hiện tại	Traffic sẽ thay đổi trong 30 phút tới — route dài cần dự đoán tương lai	Combine historical + real-time + ML prediction
8	Lưu raw GPS data vĩnh viễn	430 TB/tháng → 5 PB/năm → không thể lưu mãi	TTL 30-90 ngày, aggregate rồi xóa raw
9	Không anonymize traffic data	Vi phạm privacy — có thể truy nguồn user từ traffic patterns	K-anonymity, differential privacy, ephemeral IDs
10	Không có offline support	User mất signal trong hầm, ở nông thôn → bản đồ trắng	Cho phép download tiles + routing data cho offline use

So sánh với các bài khác đã học

Khái niệm	Ở Google Maps	Ở bài đã học
CDN	Tile CDN — 99%+ cache hit	Tuan-03-Networking-DNS-CDN — lý thuyết CDN
Message Queue	Kafka cho location ingestion — 10M events/s, fan-out 3 consumers	Tuan-08-Message-Queue — lý thuyết message queue
Stream Processing	Traffic aggregation real-time từ location events	Chưa học chi tiết — nhưng là extension của Tuan-08-Message-Queue
Geo-spatial	Road graph, routing tiles, map tiles, geocoding	Case-Design-Proximity-Service — geohash, spatial index
Pre-computation	Contraction Hierarchies, tile pre-rendering	Khái niệm mới — rất quan trọng cho interview
Time-series data	Location history, traffic data	Tương tự log data trong Tuan-13-Monitoring-Observability
Privacy	Location anonymization, GDPR compliance	Tuan-15-Data-Security-Encryption — encryption, data protection

---

Câu hỏi tự kiểm tra

Level 1 — Recall (Nhớ lại)

1. Google Maps có mấy zoom level? Mỗi level tăng bao nhiêu tiles so với level trước?
2. Ba service chính của Google Maps là gì?
3. Tại sao weight của road graph là thời gian, không phải khoảng cách?
4. Contraction Hierarchies pre-compute gì?
5. Tần suất gửi location update khi user đang navigate là bao nhiêu?

Level 2 — Understanding (Hiểu)

6. Giải thích tại sao vector tiles tốt hơn raster tiles cho mobile.
7. Tại sao cần multi-layer caching (client → CDN → origin) cho map tiles?
8. Map-matching là gì và tại sao cần dùng HMM thay vì nearest-road?
9. Tại sao ETA cần cả 3 nguồn (historical + real-time + ML) thay vì chỉ 1?
10. Tại sao location history dùng Cassandra thay vì PostgreSQL?

Level 3 — Application (Vận dụng)

11. Nếu CDN cache hit giảm từ 99% xuống 90%, ảnh hưởng gì đến origin? Tính QPS mới ở origin.
12. Nếu GPS accuracy giảm (do urban canyon), hệ thống nào bị ảnh hưởng và cách xử lý?
13. Thiết kế data retention policy cho một ứng dụng ride-hailing (Grab) sử dụng hệ thống này.
14. Nếu cần hỗ trợ “avoid toll roads” và “avoid highways”, thay đổi gì trong routing?
15. Tính storage cần thiết nếu tăng retention từ 30 ngày lên 90 ngày cho location history.

---

Tổng kết — What to Remember for Interview

1-minute Pitch (Nếu chỉ có 1 phút)

“Google Maps gồm 3 services chính: Location Service (thu thập GPS từ users qua Kafka, 10M events/s), Map Rendering (pre-rendered tiles phục vụ qua CDN, 99%+ cache hit), và Navigation (road graph với Contraction Hierarchies cho < 1ms query, overlay real-time traffic, ML-powered ETA). Key insight: pre-computation ở cả map tiles lẫn routing là lý do hệ thống có thể phục vụ 1B DAU.”

Checklist khi vẽ diagram

• Client → CDN (tiles) và Client → API Gateway (navigation, location)
• Location Service → Kafka → 3 consumers (traffic, history, ML)
• Navigation Service → Road Graph (in-memory) + ETA Service
• ETA Service → Traffic Cache (Redis) + ML Model
• Multi-layer caching cho tiles (Client → CDN → Origin Shield → S3)
• Geocoding Service (Elasticsearch) cho address ↔ coordinates

3 điều interviewer muốn nghe

1. Pre-computation: “Contraction Hierarchies giúp routing query < 1ms thay vì vài giây. Tiles được pre-render offline và cache ở CDN.”
2. Scale numbers: “10M location updates/s, 70K routing requests/s, 5M tile requests/s (nhưng 99%+ served by CDN).”
3. Real-time traffic: “User GPS data → Kafka → stream processing → real-time traffic overlay → adaptive ETA với ML.”

---

• bài này dài nhưng mỗi phần đều quan trọng. Google Maps là một trong những hệ thống phức tạp nhất — nó kết hợp CDN, stream processing, graph algorithms, ML, và geo-spatial data. Hiểu bài này, bạn sẽ có nền tảng vững cho bất kỳ bài toán location-based nào trong interview.*

Next: Case-Design-Proximity-Service — Proximity Service (geohash, quadtree) là nền tảng cho location-based search mà Google Maps sử dụng.