ออกแบบเวอร์ชันง่ายๆของ Google Maps - ระบบแผนที่ที่แสดงเส้นทาง การนำทาง และ ETA
บทนำ
บทนี้ออกแบบเวอร์ชันง่ายๆของ Google Maps Features หลัก:
- Location Update
- Navigation Service รวมถึง ETA
- Map Rendering
Map 101
Map Projections
กระบวนการแปลงจุดจาก 3D เป็น 2D เรียกว่า "Map Projection" Google Maps เลือก Web Mercator
Geohashing
ระบบ Encoding ที่เข้ารหัสพื้นที่ภูมิศาสตร์เป็นสตริงตัวอักษรและตัวเลข
Map Rendering
ใช้ Tiling - แทนที่จะRender แผนที่ทั้งหมดเป็นภาพใหญ่ ทำเป็น Tiles เล็กๆ
Road Data
Intersections แทนด้วย Nodes และถนนแทนด้วย Edges ใช้ Djikstra หรือ A* Algorithms
Services หลัก
Location Service
บันทึกอัปเดตสถานที่ผู้ใช้ ข้อมูลสามารถใช้ปรับปรุง ETA และ Traffic Data
Navigation Service
หาค่เส้นทางที่เร็วที่สุดระหว่าง A และ B
Map Rendering
แผนที่TilesถูกFetchตามความต้องการจากCDNตามGeohash
Shortest Path Algorithm
ใช้ A* Algorithm กับ Routing Tiles เพื่อหาเส้นทางที่เหมาะสมที่สุด
ETA Service
คำนวณเวลาโดยประมาณจากข้อมูล Traffic
เนื้อหานี้อ้างอิงจาก ByteByteGo - System Design Interview - An Insider's Guide