حالت تاریک
فصل ۳ — نقشهٔ گوگل (Google Maps)
خلاصهٔ تحلیلی — این متن چکیدهٔ مفاهیم فصل به زبان فارسی است، نه ترجمهٔ واژهبهواژه.
طراحی نسخهٔ سادهشدهای از Google Maps با ۱ میلیارد کاربر روزانه. سه قابلیت محوری: بهروزرسانی مکان کاربر، سرویس ناوبری همراه با ETA و رندر نقشه. دادهٔ خام جادهها (چند ترابایت) از منابع بیرونی در دسترس فرض میشود؛ ترافیک و حالتهای مختلف سفر باید پشتیبانی شوند.
نیازمندیهای غیرکارکردی: دقت (مسیر اشتباه ممنوع)، رندر روان نقشه، مصرف کم دیتا و باتری موبایل، دسترسپذیری و مقیاسپذیری.
مبانی نقشه (Map 101)
- سیستم مختصات: عرض جغرافیایی (شمال-جنوب) و طول جغرافیایی (شرق-غرب).
- تصویرسازی (Map Projection): تبدیل کرهٔ سهبعدی به صفحهٔ دوبعدی؛ همهٔ روشها هندسه را کمی تحریف میکنند. گوگل از Web Mercator استفاده میکند.
- Geocoding: تبدیل آدرس متنی به مختصات (و معکوس آن reverse geocoding).
- Geohashing: تقسیم بازگشتی سطح زمین به سلولها و کدگذاری هر سلول با یک رشتهٔ کوتاه — پایهٔ tiling نقشه.
- Tiling در رندر: بهجای یک تصویر غولآسا، جهان به تایلهای ۲۵۶×۲۵۶ پیکسلی شکسته میشود و برای هر سطح زوم (۲۱ سطح) مجموعهٔ تایل جداگانهای هست؛ کلاینت فقط تایلهای محدودهٔ دید خودش را دانلود میکند.
- تایلهای مسیریابی (routing tiles): الگوریتمهای مسیریابی (گونههای Dijkstra و A*) روی گراف کار میکنند — تقاطعها گره و جادهها یال. نگهداشتن گراف کل جهان در حافظه ناممکن است؛ پس شبکهٔ جادهها هم مثل نقشه tile میشود: هر تایل گراف کوچکِ محدودهٔ خودش + ارجاع به تایلهای متصل. سه سطح جزئیات وجود دارد: خیابانهای محلی، جادههای شریانی، و بزرگراههای بینشهری؛ یالهایی بین سطوح (مثل ورودی بزرگراه) تایلها را به هم میدوزند. تفاوت با تایل نقشه: تایل نقشه تصویر PNG است، تایل مسیریابی فایل باینری دادهٔ جاده.
برآورد سرانگشتی
- ذخیرهسازی تایلهای نقشه: سطح زوم ۲۱ ≈ ۴٫۴ تریلیون تایل × ~۱۰۰ کیلوبایت ≈ ۴۴۰ پتابایت؛ چون ~۹۰٪ سطح زمین خالی و بسیار فشردهشدنی است، ~۵۰ پتابایت. هر سطح پایینتر یکچهارم میشود؛ سری هندسی ← جمع کل ≈ ۱۰۰ پتابایت.
- QPS: با ۵ میلیارد دقیقه ناوبری در روز، ارسال GPS هر ثانیه یعنی ۳ میلیون QPS؛ با دستهبندی (batch) در کلاینت هر ۱۵ ثانیه به ~۲۰۰ هزار میرسد و پیک (×۵) ≈ ۱ میلیون.
گام ۲ — طراحی سطح بالا
سرویس مکان
کلاینت هر ثانیه مکان را ثبت اما هر ۱۵ ثانیه دستهای ارسال میکند (صرفهجویی چشمگیر در ترافیک و باتری). این جریان داده هم برای ترافیک زنده و ETA دقیقتر به کار میرود و هم برای بهبود تدریجی نقشه (کشف جادههای جدید/بسته). دیتابیس write-heavy و مقیاسپذیر مثل Cassandra + انتشار در Kafka برای مصرفکنندگان پاییندستی. پروتکل: HTTP با keep-alive کافی است (POST /v1/locations با آرایهای از سهتاییهای مکان-زمان).
سرویس ناوبری
GET /v1/nav?origin=...&destination=... — کمی تأخیر قابل تحمل است، اما دقت حیاتی است. پاسخ شامل مسافت، زمان، polyline مسیر و دستورالعملهاست.
رندر نقشه
دو گزینه: تولید تایل بهصورت پویا (بار سنگین سرور و غیرقابل کش) در برابر تایلهای ایستا و از پیش تولیدشده بر اساس شبکهٔ geohash که از CDN سرو میشوند — گزینهٔ دوم برنده است؛ تایل ایستا فوقالعاده cacheable است و از نزدیکترین POP به کاربر میرسد.
- مصرف دیتا: با سرعت ۳۰km/h و تایلهای ۲۰۰×۲۰۰ متری ~۱۰۰ کیلوبایتی، ~۷۵ مگابایت در ساعت (بدون کش کلاینت که در عمل خیلی کمتر میشود).
- بار CDN: ~۶۲٬۵۰۰ مگابایت بر ثانیه که بین ~۲۰۰ POP پخش میشود.
- URL تایل: کلاینت میتواند خودش از مکان+زوم geohash بسازد، اما این الگوریتم در همهٔ کلاینتها hardcode میشود و تغییرش پرریسک است؛ گزینهٔ جایگزین یک map tile service واسط است که ۹ URL (تایل جاری + ۸ همسایه) را برمیگرداند — مبادلهٔ انعطاف عملیاتی در برابر یک hop اضافه.
گام ۳ — بررسی عمیق
مدل داده
- تایلهای مسیریابی: خروجی یک pipeline آفلاین دورهای (routing tile processing service). ذخیره در object storage (مثل S3) بهصورت adjacency list سریالشدهٔ باینری، سازماندهی با geohash و کش تهاجمی در سرویس مسیریابی — دیتابیس برای این داده گران و بیفایده است.
- مکان کاربر: Cassandra با کلید
(user_id, timestamp)— پارتیشن با user_id و مرتبسازی با timestamp، پس «آخرین مکان کاربر» و «بازهٔ زمانی یک کاربر» هر دو سریعاند. طبق CAP، دسترسپذیری و تحمل پارتیشن بر سازگاری اولویت دارند چون مکان بهسرعت کهنه میشود. - Geocoding: خواندن پرتکرار/نوشتن کم ← key-value مثل Redis.
- تصاویر از پیش محاسبهشده: روی CDN با پشتوانهٔ cloud storage.
مسیر دادههای مکان
علاوه بر ذخیره در دیتابیس، جریان مکان به Kafka میرود و مصرفکنندهها مستقل کار میکنند: traffic update service دیتابیس ترافیک زنده را بهروز میکند، routing tile processing service جادههای جدید/بسته را در تایلها اعمال میکند، و سرویسهای ML/شخصیسازی/analytics هم از همان جریان تغذیه میشوند.
رندر — بهینهسازی وکتور
با WebGL میتوان بهجای تصویر، دادهٔ وکتوری (مسیرها و چندضلعیها) فرستاد: فشردهسازی بسیار بهتر و تجربهٔ زوم نرمتر (بدون تار شدن تصویر raster).
سرویس ناوبری — اجزا
- Geocoding service: تبدیل مبدأ/مقصد به مختصات.
- Route planner: هماهنگکنندهٔ کل جریان.
- Shortest-path service: اجرای A* روی تایلهای مسیریابی: مختصات ← geohash ← بارگیری تایل مبدأ، پیمایش گراف و بارگیری تدریجی تایلهای همسایه (و تایلهای درشتتر برای مسیرهای طولانی از طریق یالهای بینسطحی) تا یافتن k مسیر برتر. چون ساختار جادهها بهندرت عوض میشود، کش مسیرها مؤثر است. ترافیک در این مرحله لحاظ نمیشود.
- ETA service: برای هر مسیر کاندید، با ML و دادهٔ ترافیک زنده + تاریخی زمان تخمین میزند؛ چالش واقعی پیشبینی ترافیکِ ۱۰-۲۰ دقیقهٔ بعد است.
- Ranker: اعمال فیلترهای کاربر (پرهیز از عوارضی/بزرگراه) و مرتبسازی از سریعترین به کندترین.
ETA تطبیقی و تغییر مسیر
باید کاربرانِ در حال ناوبری را رهگیری و هنگام تغییر ترافیک بهروزرسانی کرد. راهحل ساده — نگهداری فهرست تایلهای مسیر هر کاربر و اسکن همهٔ ردیفها هنگام حادثهٔ ترافیکی — هزینهٔ O(n×m) دارد. راهحل بهتر: برای هر کاربر، سلسلهمراتب تایلها را نگه دارید (تایل جاری، ابرتایل آن، و بازگشتی تا تایلی که مقصد را هم در بر بگیرد)؛ آنگاه بررسی تأثیر حادثه به یک آزمون عضویت ساده تقلیل مییابد و بیشتر کاربران سریع رد میشوند. برای بازگشت به مسیر قبلی پس از رفع ترافیک، ETA همهٔ مسیرهای ممکن دورهای بازمحاسبه و در صورت یافتن مسیر سریعتر به کاربر اطلاع داده میشود.
پروتکل push سرور به کلاینت: push notification موبایل (payload خیلی کوچک، بدون پشتیبانی وب) و long polling رد میشوند؛ بین SSE و WebSocket، WebSocket به دلیل ارتباط دوطرفه ترجیح دارد.
نکات کلیدی فصل
- ایدهٔ tiling هم برای تصویر نقشه و هم برای گراف جادهها به کار میرود؛ بارگیری تدریجی تایلها کلید مهار حافظه در مسیریابی است.
- دستهبندی بهروزرسانیها در کلاینت (batching) سادهترین و مؤثرترین اهرم کاهش QPS و مصرف باتری است.
- محتوای ایستا + CDN همیشه بر تولید پویا برتری دارد، مگر اینکه واقعاً پویا بودن لازم باشد.
- یک جریان رویداد (Kafka) اجازه میدهد چند مصرفکنندهٔ مستقل از یک دادهٔ واحد ارزشهای متفاوت بسازند.
- ساختارهای سلسلهمراتبی (تایلهای چندسطحی) جستوجوی «چه کسی تحت تأثیر است» را از اسکن خطی به آزمون عضویت تبدیل میکنند.
یادداشتهای مترجم
- اصطلاحات tile، geohash، ETA، polyline و CDN لاتین حفظ شدهاند؛ «routing tile» را «تایل مسیریابی» ترجمه کردهایم.