🚕 اوبر چگونه نزدیک‌ترین راننده را در مقیاس بزرگ پیدا می‌کند؟

فرض کن در یک شهر بزرگ، هزاران یا حتی میلیون‌ها راننده و مسافر به‌صورت هم‌زمان در حال حرکت هستند.
یک مسافر درخواست سفر می‌دهد و سیستم باید خیلی سریع جواب بدهد:

کدام راننده را به این مسافر اختصاص بدهیم؟

در نگاه اول، جواب ساده است:

تمام راننده‌ها را بگیر
فاصله‌ی هرکدام تا مسافر را حساب کن
نزدیک‌ترین را انتخاب کن

اما این راه‌حل در مقیاس بزرگ، خیلی زود تبدیل به یک مشکل جدی می‌شود. 😅
❌ چرا بررسی همه‌ی راننده‌ها جواب خوبی نیست؟
فرض کن در یک شهر، ۱۰۰ هزار راننده‌ی آنلاین داریم.
اگر برای هر درخواست سفر، فاصله‌ی تمام ۱۰۰ هزار راننده را بررسی کنیم، هزینه‌ی هر درخواست تقریباً به تعداد کل راننده‌ها وابسته می‌شود.
حالا اگر هزاران درخواست در هر لحظه وارد شوند، سیستم باید دائماً:
موقعیت راننده‌ها را دریافت کند؛ فاصله‌ی آن‌ها را محاسبه کند؛ راننده‌های نامناسب را حذف کند؛
و در نهایت بهترین گزینه را انتخاب کند.
مشکل فقط تعداد راننده‌ها نیست.
موقعیت راننده‌ها هم ثابت نیست. هر چند لحظه ممکن است راننده:
چند خیابان جلوتر رفته باشد؛ سفر جدیدی قبول کرده باشد؛ آفلاین شده باشد؛
یا دیگر برای دریافت سفر در دسترس نباشد.
پس ما با یک Query ساده‌ی Database طرف نیستیم.
ما با ترکیبی از این مسائل روبه‌رو هستیم:

Geospatial Search
+
Real-Time Location Updates
+
Distributed Systems
+
Matching Optimization

🗺 ایده‌ی اول: نقشه را به Cell تقسیم کنیم
به‌جای اینکه تمام راننده‌ها را در یک لیست بزرگ نگه داریم، نقشه را به بخش‌های کوچک‌تر تقسیم می‌کنیم.
برای مثال:

+---------+---------+---------+
| Cell A  | Cell B  | Cell C  |
+---------+---------+---------+

حالا هر راننده در یک Cell قرار می‌گیرد.
وقتی مسافر در Cell E درخواست سفر می‌دهد، لازم نیست تمام راننده‌های شهر بررسی شوند.
ابتدا این بخش‌ها را بررسی می‌کنیم:

Cell E
Cell D
Cell F
و Cellهای نزدیک دیگر

این کار تعداد Candidateها را بسیار کمتر می‌کند.
اما یک سؤال مهم وجود دارد:
این Cellها را چطور بسازیم؟

⬡ ءH3؛ سیستم مکانی Uber

ءUber برای کارهای جغرافیایی خودش، سیستم H3 را توسعه داد و Open Source کرد. H3 مخفف این عبارت است:

Hexagonal Hierarchical Geospatial Index

یعنی یک سیستم Index مکانیِ سلسله‌مراتبی که جهان را به Cellهای شش‌ضلعی تقسیم می‌کند.
به‌جای اینکه فقط با Latitude و Longitude کار کنیم، مختصات را به یک شناسه‌ی مکانی تبدیل می‌کنیم.
مثلاً به‌صورت مفهومی:

Latitude: 35.7219
Longitude: 51.3347
        ↓
H3 Cell ID
        ↓
8a2a1072b59ffff

شناسه‌ی بالا صرفاً یک نمونه از فرمت H3 است، نه شناسه‌ی واقعی یک راننده.
در کد رسمی H3 نیز می‌توان مختصات جغرافیایی را به یک Cell تبدیل کرد:

latLngToCell(latitude, longitude, resolution)

🔎 هنگام درخواست سفر چه اتفاقی می‌افتد؟

فرض کن مسافر در Cell E قرار دارد.
سیستم می‌تواند ابتدا راننده‌های همین Cell را بررسی کند:

Search(Cell E)

اگر راننده‌ی مناسب پیدا نشد، جست‌وجو را به Cellهای اطراف گسترش می‌دهد:

Search(Cell E)
Search(Neighbors of E)
Search(Neighbors of Neighbors)

به این ترتیب، سیستم به‌جای بررسی تمام شهر، یک ناحیه‌ی محدود را بررسی می‌کند.
اما اینجا یک نکته‌ی مهم وجود دارد:
نزدیک‌ترین راننده الزاماً بهترین راننده نیست
فرض کن دو راننده داریم:

Driver A:
فاصله‌ی مستقیم: 800 متر
اما پشت رودخانه است

Driver B:
فاصله‌ی مستقیم: 1.2 کیلومتر
اما از مسیر مستقیم و خلوت می‌تواند برسد

از نظر فاصله‌ی هندسی: A بهتر است

اما از نظر زمان رسیدن: B ممکن است بهتر باشد
خود Uber نیز توضیح داده که در ابتدا Matching را با این سؤال انجام می‌داد:

چه کسی از همه نزدیک‌تر است؟

اما بعد مشخص شد که «نزدیک‌ترین» همیشه به معنی «سریع‌ترین برای رسیدن» نیست.
عواملی مثل:
ترافیک؛
پل‌ها و بزرگراه‌ها؛
رودخانه‌ها؛
خیابان‌های یک‌طرفه؛
مسیر واقعی رانندگی؛
و زمان رسیدن
می‌توانند نتیجه را تغییر دهند.
بنابراین فرآیند واقعی چیزی شبیه این است:

1. پیدا کردن راننده‌های مکانیِ نزدیک
2. حذف راننده‌های نامعتبر
3. تخمین زمان رسیدن
4. بررسی محدودیت‌ها و شرایط Matching
5. انتخاب Assignment مناسب