حالت تاریک
فصل ۱ — سرویس مجاورت (Proximity Service)
خلاصهٔ تحلیلی — این متن چکیدهٔ مفاهیم فصل به زبان فارسی است، نه ترجمهٔ واژهبهواژه.
سرویس مجاورت زیربنای قابلیتهایی مثل «رستورانهای نزدیک من» در Yelp یا «نزدیکترین پمپبنزینها» در Google Maps است: با گرفتن مختصات کاربر و یک شعاع، کسبوکارهای اطراف را برمیگرداند.
گام ۱ — تعیین محدودهٔ مسئله
با پرسش از مصاحبهگر، دامنهٔ طراحی به این شکل مشخص میشود:
- جستوجو فقط در شعاع انتخابی کاربر (۰٫۵، ۱، ۲، ۵ یا ۲۰ کیلومتر) انجام میشود.
- صاحبان کسبوکار میتوانند کسبوکار اضافه/ویرایش/حذف کنند، اما لازم نیست تغییرات real-time دیده شوند (توافق: از روز بعد اثر میکند).
- کاربر میتواند جزئیات یک کسبوکار را ببیند.
نیازمندیهای غیرکارکردی: تأخیر کم، حریم خصوصی دادههای مکانی (GDPR/CCPA)، و دسترسپذیری و مقیاسپذیری بالا برای ساعات اوج در مناطق پرتراکم.
برآورد سرانگشتی: با ۱۰۰ میلیون کاربر فعال روزانه و ۲۰۰ میلیون کسبوکار، اگر هر کاربر روزی ۵ جستوجو انجام دهد، QPS جستوجو حدود ۵٬۰۰۰ است (ثانیههای شبانهروز ≈ ۱۰⁵).
گام ۲ — طراحی سطح بالا
طراحی API
GET /v1/search/nearbyبا پارامترهایlatitude،longitudeوradius(پیشفرض ۵۰۰۰ متر) — پاسخ شامل تعداد نتایج و آرایهای از business objectها.- CRUD کسبوکار:
GET/POST/PUT/DELETE /v1/businesses[/:id]. - صفحهٔ جزئیات معمولاً با یک فراخوانی جداگانه پر میشود؛ صفحهبندی (pagination) هم ارزش اشاره دارد.
مدل داده
سیستم بهشدت read-heavy است (جستوجو و مشاهدهٔ جزئیات پرتکرار؛ نوشتن کمتکرار)، پس پایگاه دادهٔ رابطهای مثل MySQL انتخاب مناسبی است. دو جدول کلیدی: جدول business (اطلاعات کامل با کلید business_id) و جدول ایندکس جغرافیایی (geo index).
اجزای سطح بالا
- Load balancer: ترافیک را بر اساس مسیر URL بین سرویسها توزیع میکند.
- سرویس LBS: هستهٔ سیستم؛ stateless و فقط-خواندنی با QPS بالا، پس مقیاسپذیری افقی ساده است.
- سرویس Business: نوشتنهای کمحجمِ صاحبان کسبوکار + خواندنهای پرحجم مشتریان.
- کلاستر پایگاه داده: الگوی primary-replica؛ نوشتن روی primary و خواندن از replicaها. ناسازگاری کوتاه ناشی از تأخیر replication پذیرفتنی است چون دادهها real-time نیستند.
الگوریتمهای یافتن کسبوکارهای نزدیک
نکتهٔ مصاحبه: بهجای نام بردن از دیتابیسهای آماده (Redis GEO، PostGIS)، سازوکار ایندکس جغرافیایی را توضیح دهید.
- جستوجوی دوبعدی (naive): کوئری بازهای روی طول و عرض جغرافیایی. حتی با ایندکس روی هر دو ستون کارآمد نیست، چون اشتراک دو مجموعهٔ بزرگ از هر بعد پرهزینه است.
- شبکهٔ یکنواخت: تقسیم نقشه به سلولهای هماندازه. مشکل: توزیع کسبوکارها یکنواخت نیست (منهتن در برابر اقیانوس) و یافتن سلولهای همسایه هم ساده نیست.
- Geohash: داده دوبعدی را به رشتهٔ یکبعدی base32 تبدیل میکند؛ با هر بیت، جهان بازگشتی به چهار قسمت تقسیم میشود. ۱۲ سطح دقت دارد؛ برای این مسئله طول ۴ تا ۶ کافی است (مثلاً شعاع ۵۰۰ متر ← طول ۶). ویژگی کلیدی: پیشوند مشترک طولانیتر یعنی نزدیکی بیشتر — اما عکس آن صادق نیست:
- مسئلهٔ مرزی ۱: دو نقطهٔ نزدیک در دو سوی خط استوا یا نصفالنهار مبدأ ممکن است هیچ پیشوند مشترکی نداشته باشند؛ پس کوئری سادهٔ
LIKE 'prefix%'کافی نیست. - مسئلهٔ مرزی ۲: دو نقطه با پیشوند مشترک طولانی ممکن است در دو سلول متفاوت باشند.
- راهحل: همیشه سلول فعلی + ۸ همسایه را کوئری بزنید (محاسبهٔ همسایهها O(1) است).
- کمبود نتیجه: با حذف تدریجی رقم آخر geohash، سطح دقت را کم و محدودهٔ جستوجو را بزرگتر کنید.
- مسئلهٔ مرزی ۱: دو نقطهٔ نزدیک در دو سوی خط استوا یا نصفالنهار مبدأ ممکن است هیچ پیشوند مشترکی نداشته باشند؛ پس کوئری سادهٔ
- Quadtree: ساختار دادهٔ درون-حافظهای (نه دیتابیس) که فضا را بازگشتی به چهار ربع تقسیم میکند تا هر برگ حداکثر مثلاً ۱۰۰ کسبوکار داشته باشد؛ روی هر سرور LBS هنگام راهاندازی ساخته میشود. برآورد حافظه برای ۲۰۰ میلیون کسبوکار ≈ ۱٫۷۱ گیگابایت (۲ میلیون برگ × ۸۳۲ بایت + حدود ۰٫۶۷ میلیون گرهٔ داخلی × ۶۴ بایت) — بهراحتی در یک سرور جا میشود، اما برای پاسخگویی به حجم خواندن به چند سرور نیاز است.
- ملاحظات عملیاتی: ساخت درخت چند دقیقه طول میکشد؛ استقرار نسخهٔ جدید باید تدریجی باشد تا کلاستر یکجا از سرویس خارج نشود. بهروزرسانی درخت هم یا شبانه بازسازی میشود (با پذیرش دادهٔ کمی کهنه) یا on-the-fly با قفلگذاری که پیادهسازی را بهشدت پیچیده میکند.
- Google S2: کره را با منحنی هیلبرت (space-filling) به ایندکس یکبعدی نگاشت میکند؛ نقاط نزدیک روی منحنی در فضای واقعی هم نزدیکاند. برای geofencing و پوشش ناحیههای دلخواه با سطوح متغیر (Region Cover) عالی است، اما توضیحش در مصاحبه دشوار است.
مقایسهٔ geohash و quadtree:
| معیار | Geohash | Quadtree |
|---|---|---|
| پیادهسازی | ساده، بدون ساخت درخت | نیازمند ساخت درخت |
| نوع کوئری | شعاع مشخص | k-نزدیکترین (اندازهٔ محدوده خودکار تنظیم میشود) |
| اندازهٔ سلول | ثابت در هر سطح | پویا بر اساس تراکم |
| بهروزرسانی ایندکس | حذف/درج یک سطر ساده | پیمایش درخت + قفلگذاری + rebalancing |
توصیهٔ کتاب برای مصاحبه: geohash یا quadtree را انتخاب کنید؛ نمونههای صنعتی: geohash در Bing Maps/Redis/MongoDB/Lyft، quadtree در Yext، هر دو در Elasticsearch، و S2 در Google Maps و Tinder.
گام ۳ — بررسی عمیق
مقیاسدهی پایگاه داده
- جدول business: شاردینگ بر اساس
business_idتا بار یکنواخت توزیع شود. - جدول geo index: دو گزینهٔ ساختار — (۱) هر geohash یک سطر با آرایهٔ JSON از IDها، (۲) هر جفت (geohash، business_id) یک سطر. گزینهٔ ۲ توصیه میشود چون درج/حذف بدون قفل و بدون اسکن آرایه انجام میشود.
- نکتهٔ ضدکلیشه: قبل از شاردینگ، اندازهٔ واقعی داده را بسنجید. کل ایندکس جغرافیایی (~۱٫۷ گیگابایت) در working set یک سرور مدرن جا میشود؛ گلوگاه CPU/پهنای باند خواندن است، پس read replica سادهتر و بهتر از شاردینگ است.
کش
کش هم بدیهی نیست: داده کوچک و کوئریها I/O-bound نیستند، پس ابتدا نیازش را بسنجید. اگر لازم شد:
- کلید کش: مختصات خام کاربر کلید بدی است (نویز GPS و جابهجایی جزئی)؛ geohash کلید پایداری است چون تغییرات کوچک مکان به همان سلول نگاشت میشود.
- دو نوع داده:
geohash ← فهرست business_id های سلولوbusiness_id ← شیء کسبوکار. برای سه دقت ۴، ۵ و ۶ جداگانه کش میشود؛ کل حافظه ≈ ۵ گیگابایت (۸ بایت × ۲۰۰ میلیون × ۳). کش شبانه (مطابق توافق «اثر از روز بعد») بهروزرسانی میشود.
Region و Availability Zone
استقرار چند-region کاربران را به سرورها نزدیکتر میکند، بار مناطق پرتراکم (ژاپن/کره) را پخش میکند و امکان رعایت قوانین محلی نگهداری داده (data residency) را با مسیریابی DNS فراهم میکند.
فیلتر نتایج (پرسش تکمیلی)
چون تعداد نتایج هر سلول کوچک است، کافی است اول IDها را برگردانید، اشیاء را hydrate کنید و سپس بر اساس ساعت کار یا نوع کسبوکار در حافظه فیلتر کنید.
جریان نهایی جستوجو
۱) کلاینت مختصات و شعاع را میفرستد ← ۲) load balancer به LBS ← ۳) LBS طول geohash متناظر شعاع را تعیین میکند ← ۴) geohash فعلی + ۸ همسایه ← ۵) واکشی موازی business_id ها از کش Redis «Geohash» ← ۶) hydrate از کش «Business info»، محاسبهٔ فاصله، رتبهبندی و بازگشت نتیجه.
نکات کلیدی فصل
- برای دادهٔ جغرافیایی، مسئلهٔ اصلی «تبدیل جستوجوی دوبعدی به یکبعدی» است؛ geohash و quadtree دو راهحل استاندارد صنعتاند.
- در geohash همیشه همسایهها را هم کوئری بزنید؛ پیشوند مشترک شرط لازم نزدیکی نیست.
- قبل از شاردینگ یا افزودن کش، اندازهٔ واقعی داده و گلوگاه واقعی (CPU/شبکه در برابر I/O) را برآورد کنید.
- ساختارهای in-memory مثل quadtree هزینهٔ عملیاتی دارند: زمان ساخت هنگام استقرار و پیچیدگی بهروزرسانی همزمان.
یادداشتهای مترجم
- «Proximity Service» را «سرویس مجاورت» ترجمه کردهایم؛ اصطلاحات فنی مثل geohash، quadtree و LBS به همان شکل لاتین حفظ شدهاند.