برنامه نویس شی گرا

شروع

داستان در سال 2015 با پروژه پایانی توسعه دهنده موبایل ما شروع شد. موضوع پروژه "سامانه سرویس تاکسی" بود. در این برنامه ماشینها بصورت متحرک بودند. شبیه شکل زیر

بنظرمان رسید که این برنامه را میتوانیم روی صفحه کاربران اجرا نماییم بطوریکه بتوانند مسیر حرکت رانندگان را ببینند. نخسیتن چالش فقدان داده کافی بود. در ابتدا شروع به دریافت مکان هر راننده در دوره های زمانی 15 ثانیه ای کردیم. ما نمیتوانستیم دوره زمانی را کاهش دهیم زیرا وقتی که برنامه موبایل راننده داده ها را به ما ارسال میکرد، سفارش فعلی، سفارش بعدی و آلارم های باز را دریافت میکرد. آلارم ها شبیه دکمه کمک بودند. وقتی راننده ای آن را فشار میدهد بقیه راننده ها به کمک او می آیند. اگر ما دوره بروزرسانی را کاهش می دادیم ترافیک بیشتری به سوی سیستم ما روانه می شد و مطمئن نبودیم که بتوانیم چنین حجم ترافیکی را اداره نماییم.

اولین گامها

اولین تلاش ما ساده و البته کمی احمقانه :) بود. تقاضا را ارسال کن مکان را ذخیره کن تقاضای بعدی را انجام بده و ماشین را حرکت بده همانطور که میتوانید حدس بزنید این روش مشکلاتی داشت. ما نمیتوانیستم ماشین را به درستی حرکت دهیم و ماشین از بین جنگلها، دشتها و مزارع و … حرکت میکرد. در شکل زیر حاصل کار را مشاهده میکنید:

به عنوان راه حل، از ماشین مسیریابی OpenStreetMap برای ساختن مسیرها استفاده کردیم و الگوریتم ما بهتر شد. ما همان نرخ بروزرسانی 15 ثانیه ای قبلی را داشتیم.

یک تقاضا فرستاده میشود مختصات مکانی ذخیره می شود مختصات ذخیره شده به پس زمینه ارسال میگردد مسیر از طریق OSRM ساخته میشود. مسیر ساخته شده به برنامه مشتری فرستاده میشود و مکان نما را به حرکت در می آورد.

به نظر میرسد که حالا دیگر کار میکند، اما به مشکل جدیدی برخورد کردیم و آن مشکل راههای یک طرفه بود.

برای مثال، راننده در تقاطع در نقطه قرمز رنگ میماند ولی دستگاه او دقت پایینی داشت و مختصات نقطه روبروی او در آنطرف تقاطع را نشان می دهد. در برنامه مشتری ما این مختصات را دریافت و ذخیره میکنیم و به برنامه پس زمینه میفرستیم. OSRM یک مسیر برای ما می سازد و آن را به برنامه بر میگرداند. حرکت مکان نما مضحک به نظر میرسد زیرا خیلی سریع مسیر طولانی را طی میکند.

ما این مشکل را با یک راه حل ساده حل کردیم. ما کوتاهترین فاصله بین دو نقطه را حساب میکردیم و در صورتیکه کمتر از 20 متر بود برای آن مسیری تعریف نمیکردیم. با این روش بعد از چند روز آزمایش، تصمیم گرفتیم که سیستم را منتشر نماییم و بازخورد آن در بین مشتریان را ببینیم. همانطور که میدانید ما در دنیایی ایده آل زندگی نمی کنیم بنابراین تصمیم گرفتیم که به دور دوم را شروع کنیم. زیرا چندین چیز نیاز به بهبود داشت. اولین چیز یک محاسبه کننده هزینه گردش بود. همه محاسبات در سمت راننده انجام می پذیرفت. بنابراین در منابع سرور صرفه جویی میشد. ولی از جنبه دیگر ما فقط یک نقطه اتکا داشتیم و آن برنامه موبایل راننده بود. ما نیاز داشتیم تا داده ها را کپی کنیم و در سرور ذخیره نماییم.

2. بعلاوه ما فهمیدیم که زمان 15 ثانیه زیاد است و خیلی از کاربران متوجه این ویژگی جدید روی برنامه نمیشوند زیرا ماشین شروع به حرکت کرده است و 15 ثانیه بعد صفحه نمایش داده میشود. من نمیدانم چندین نفر هستند که میتوانند 15 ثانیه به صفحه نمایش خیره شوند بدون اینکه اتفاقی روی آن بیفتد. 3. و مشکلات باز هم بیشتر، این بار در ماژول GPS روی سیستم راننده. مشکلات جی پی اس مربوط به ابزار سمت راننده میشدند. 4. و سرانجام ما میخواستیم ماشین روی صفحه حرکت کند.

پس ما مشکلاتی داشتیم که می بایست حل میشد: شروع به جمع آوری مسیرهای بیشتری از رانندگان میکردیم. ماشینهای متحرک را روی صفحه اصلی نمایش میدادیم. هزینه متوسط سفر را در سمت سرور ذخیره میکردیم. ارسال داده های موبایلی را کاهش میدادیم هر مسیر را در یک ثانیه دریافت میکردیم.

میخواهم نکاتی را در مورد کاهش داده های ارسالی از طریق موبایل بگویم. ما نیاز به این امر داشتیم زیرا در کشور ما کارمزد تاکسی ها بسیار پایین است. ما از تاکسی مثل یک وسیله حمل و نقل عمومی استفاده میکنیم. برای مثال، شما میتوانید از یک طرف شهر به آن طرف شهر فقط با 2 یورو سفر کنید. مثل مترو در پاریس. همچنین هزینه اینترنت در اینجا بسیار بالاست. اگر ما در هر ثانیه 100 بایت صرفه جویی میکردیم مثل این بود که 2 هزار دلار در مقیاس یک شرکت صرفه جویی کرده ایم. چه اطلاعاتی با مسیر ارسال میشدند؟ مکان راننده ( طول و عرض جغرافیایی ) اطلاعات کاربری راننده از لحظه ورود به سیستم اطلاعات سفارش ها ( شماره سفارش و هزینه سفر )

هدف ما این بود که هر بسته اطلاعات باید کمتر از 100 بایت باشد. در ابتدا به پروتکلهای ارتباطی نگاه کردیم تا این مشکل را حل نماییم: همانطور که می بینید پروتکلهای زیر را درنظر گرفتیم: HTTP WebSockets TCP UDP

پروتکل ایده آل ما UDP بود زیرا فقط دیتاگرام ارسال میکردیم نیاز به گارانتی ارسال داده نداشتیم کمینه بودن کار در داده ها صرفه جویی زیادی میشد فقط 20 بایت سربار داشتیم در شبکه های موبایلی کشور ما بلاک نمیشود. برای سریال کردن داده ها به فناوریهای زیر نگاه انداختیم:

JSON MsgPack Protobuf

ما Protocol buffers را انتخاب کردیم زیرا برای داده های کوچک خیلی پربازده بود.

همانطور که می بینید نزدیکترین رقیبش دوبرابر سنگین تر است. در کل ما به چه رسیدیم؟ 42 بایت ضمیمه 20+ بایت هدرهای IP 62 بایت در هر مسیر سود اما به هر حال وقتی داده ها را دریافت میکنیم باید آنها را در جایی ذخیره نماییم. این طور نیست؟

ذخیره داده ها

ما باید داده های زیر را ذخیره میکردیم: اطلاعات راننده شماره تاکسی جهت جستجو در برنامه موبایلی مشتریان شماره سفارش و هزینه سفر آخرین مکان برای جستجو آخرین N موقعیت برای ساختن مسیر

فناوریهای مورد استفاده Percona: برای ذخیره همه داده ها. ما راننده ها، سفارشات و همه چیز دیگر را در آن ذخیره کردیم. 2.Redis: به عنوان یک حافظه کلید-مقدار برای اهداف کش کردن 3. Elasticsearch: برای داده های مکانی As mentioned above we have 600 online drivers and using these storages to save data seems non-expedient. So we need geo index همانطور که در بالا تاکید کردیم ما 600 راننده آنلاین داشتیم و از این حافظه ها برای ذخیره داده ها نا مناسب بنظر میرسیدند. بنابراین ما نیاز به geo index داشتیم.

ما دو نوع geo-index را بررسی کردیم: 1.KD-tree 2. R-tree برای geo-index ما ضروریاتی داشتیم: نیاز بود که N نزدیکترین نقطه را جستجو نماییم نیاز به یک درخت متوازن داشتیم که بهترین جستجو را در بدترین سناریو انجام دهد.

KD-tree

KD-tree با نیازهای ما متناسب نبود. زیرا نا متوازن بود و فقط میتوانست که یک نزدیکترین نقطه را جستجو نماید. ما میتوانستیم نزدیکترین k همسایگی را روی Kd-tree پیاده سازی کنیم ولی نمی خواستیم چرخ را دوباره اختراع نماییم علی الخصوص وقتی R-tree مشکل ما را حل میکرد. R-tree R-tree متوازن است و میتوانیم N نزدیکترین نقطه را روی آن جستجو نماییم.

می توانید برای زبان برنامه نویسی Go آنرا از آدرس زیر دانلود نمایید.https://github.com/dhconnelly/rtreego. همچنین ما به یک مکانیزم انقضا نیاز داشتیم چون برخی رانندگان باید حذف میشدند و اطلاعات واقعی به کاربران نشان داده میشد. برای مثال، راننده ای که 900 ثانیه آفلاین بوده باید حذف میشد. همچنین به ساختار داده LRU برای ذخیره آخرین مکانها نیاز داشتیم. به خاطر این که حافظه را با N آیتم مقداردهی اولیه کردیم وقتی خواستیم آیتم جدید اضافه کنیم آیتمی که اخیرا کمترین استفاده از آن شده بود را حذف نمودیم و سپس آیتم جدید را اضافه نمودیم. بنابراین ساختار حافظه ما بصورت زیر بود: تمام داده ها را در حافظه ذخیره کردیم. از R-tree برای جستجوی نزدیکترین راننده استفاده کردیم از دو نگاشت برای ذخیره کردن راننده ها و جستجو بوسیله شماره ماشین یا اطلاعات راننده استفاده کردیم.

الگوریتم نهایی

الگوریتم نهایی ما برای سیستم پس زمینه به صورت زیر در آمد: داده ها با UDP ارسال و دریافت میشود سعی میشود اطلاعات راننده از حافظه دریافت شود. اگر موجود نباشد از redis دریافت میشود داده ها چک و اعتبارسنجی می شوند راننده در حافظه ذخیره میشود. اگر موجود نباشد LRU مقداردهی میشود R-tree بروزرسانی میشود نقاط دسترسی HTTP

از این نقاط برای تجمیع این سیستم با سیستم شرکت استفاده کردیم: نزدیکترین راننده ها را برمیگردانند راننده را از حافظه بوسیله شماره تاکسی یا راننده حذف میکند اطلاعاتی در مورد مسیر سفر میدهد اطلاعاتی در مورد راننده میدهد

به عنوان مثال میتوانید به کد زیر نگاهی بیاندازید. https://github.com/maddevsio/openfreecab-storage.

این کد بسیار ساده است اما بسیاری از ویژگیهایی که شرح داده شد در آن پیاده سازی شده است.

منبع : How we built a backend system for Uber-like map with animated cars on it using Go