نمایش نقاط پرتکرار برای مسافران اسنپ

توی این پست می‌خوام در مورد یک پروژه‌ی جالب و بسیار کاربردی که توی تیم نقشه پیاده سازی کردیم، توضیح بدم.

توی context اسنپ میشه به نقشه به عنوان ابزاری برای انتخاب مبدأ و مقصد سفر نگاه کرد. با این حساب، یک متریک خیلی خوب برای سنجش کیفیت سرویس‌ها می‌تونه «مدت زمان» تلاش کاربر برای فیکس کردن مبدأ و مقصد باشه: این مدت زمان هرچی کمتر باشه، بهتره! در نتیجه واضحه که ما دوست داریم سرویس‌های جدیدی داشته باشیم که به کاهش این زمان کمک کنن.

ایده‌ای که توی این پست مطرح می‌کنم، قابلیتی هست که نقاط پرتکرار هر کاربر رو به عنوان مبدأ و مقصد سفرها بهش پیشنهاد می‌ده. یعنی تاریخچه‌ی سفرهای کاربر رو طی چند هفته‌ی اخیر بررسی می‌کنه و می‌بینه چندین سفر به مقصد یک نقطه‌ی خاص داشته، یا از یک مکان زیاد درخواست اسنپ داده؛ پس «با احتمال زیادی» در آینده باز هم می‌خواد از/به اون نقطه سفر کنه؛ پس اون نقطه رو توی قسمت جدیدی که توی اپ اسنپ بهش اختصاص دادیم، به کاربر نمایش می‌دیم. پر واضحه که وقتی دسترسی کاربر به چنین نقاطی رو راحت می‌کنیم، زحمت پیدا کردن اون مکان رو برای کاربر کم می‌کنیم و در نتیجه متریک «زمان فیکس کردن» کاهش پیدا می‌کنه.

اسم این قابلیت (feature) جدید توی اپ رو گذاشتیم نقاط پرتکرار (Frequent Pins). البته قبل از این قابلیت دیگری هم داشتیم به نام نقاط مورد علاقه (Favorite Places). منتها فرق مهمی که این دو تا با هم دارن، اینه که کاربر نقاط «مورد علاقه»ش رو دستی توی اپلیکیشن وارد می‌کنه، ولی نقاط «پرتکرار» براش اتوماتیک تشخیص داده می‌شه؛ یعنی اگه کاربری حواسش نبود یا وقت نداشت که یک نقطه‌ی مهم مثل خونه و محل کارش رو توی نقاط مورد علاقه‌اش وارد کنه، ما این خلأ رو براش پر می‌کنیم. پس توی ادامه‌ی پست حواستون به تفاوت نقاط «پرتکرار» و «مورد علاقه» باشه که خدایی نکرده گمراه نشید. :)

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

حالا که احساس کردیم یک ایده‌ی قشنگ می‌تونه به بهبود متریک‌های ما بیانجامه، تلاش می‌کنیم تا به بهترین شکل پیاده سازی‌ش کنیم. طراحی کلی به این شکل هست:

۱. به ازای هر کاربر، همه‌ی سفرهای یک بازه‌ی مشخص (مثلاً یک ماه اخیر) و همه‌ی نقاط «مورد علاقه»شون رو از پایگاه داده بازخوانی می‌کنیم.

۲. لیستی از همه‌ی مبدأ و مقصدهای کاربر (همه‌ی پین‌های فیکس شده) رو از سفرهاش به دست میاریم و نقاط «مورد علاقه» رو از این لیست حذف می‌کنیم؛ چون نقاط «پرتکرار» قراره از روی این لیست محاسبه بشن، بنابراین نمی‌خوایم اگه یک نقطه مورد علاقه بین شون هست، مجدد جزو نقاط پرتکرار به کاربر پیشنهاد بشه.

۳. از روی این لیست و با استفاده از متدهای هوش مصنوعی لیستی از نقاط پرتکرار رو به دست میاریم که حدس می‌زنیم کاربر به احتمال زیاد در آینده باز هم سراغشون خواهد رفت.

۴. در نهایت این نقاط پرتکرار رو توی اپلیکیشن برای کاربر سرو می‌کنیم.

اما پیاده سازی این طراحی ما رو با چه چالش‌هایی مواجه می‌کنه؟ در ادامه می‌ریم سراغش.

پردازش داده‌های حجیم

بار پردازشی زیاد محاسبه‌ی نقاط پرتکرار برای چندین میلیون کاربر فعال اسنپ اولین چالشیه که توجه هرکسی رو به خودش جلب می‌کنه. این حجم پردازش اگه بخواد با راه حل‌های دم دستی مثل حلقه‌ی for :) انجام بشه، اولاً خیلی طول می‌کشه، ثانیا مقیاس پذیر نیست؛ یعنی اگه فرضاً کاربرهای اسنپ دو برابر بشه، یا بخوایم توی الگوریتم‌مون کوچکترین تغییری ایجاد کنیم، مثلا آدرس هر نقطه‌ی پرتکرار رو هم کنار مختصات جغرافیایی‌ش ذخیره کنیم، ممکنه طول پردازش به سادگی از بیشترین حد قابل قبول بیشتر بشه! مثلا فرض کنید بخوایم هر شب نقاط پرتکرار رو حساب کنیم، ولی کل پردازش سه روز طول بکشه.

راه حل شناخته شده‌ی این مشکل «پردازش موازی» هست. محاسبه‌ی نقاط پرتکرار برای هر کاربر می‌تونه به طور کاملاً مستقل انجام بشه. پس خیلی بهتره که به جای یک پردازشگر سری که محاسبات رو برای هر کاربر تک به تک انجام می‌ده، از ۱۰ تا پردازشگر موازی استفاده کنیم. با این کار منابع مصرفی‌مون مثل حافظه و CPU ده برابر می‌شه، اما در ازاش سرعت هم ۱۰ برابر می‌شه. پس پردازش موازی یک tradeoff بین منابع مصرفی و زمانه.

حالا از چه روشی برای پیاده سازی این پردازش موازی استفاده کنیم؟ می‌تونیم سیستم رو multi-thread یا multi-process پیاده سازی کنیم. اگه بخوایم از راحتی docker container ها برای توسعه و deployment هم بهره ببریم، میشه آرایه‌ای از container ها رو بالا آورد که پین‌های هر کاربر رو از یک سیستم stream processor مثل Kafka یا RabbitMQ و به کمک الگوی طراحی معماری Publish-Subscribe دریافت می‌کنن. اما ما به دنبال ساده ترین راهیم! یکی از framework های محبوب در حوزه‌ی Big Data و پردازش‌های حجیم Spark هست که در زبان‌های برنامه نویسی Java, Scala و Python می‌تونید ازش استفاده کنید. خیلی ساده بخوام توضیح بدم، Spark همه‌ی کارهای زیرساختی داده‌های حجیم رو خودش انجام میده و فقط کافیه بهش بگیم که چی می‌خوایم.

اجازه بدید بیشتر راجع به Spark صحبت کنم. فرض کنید لیستی از هر نوع اطلاعاتی که دوست دارید، توی حافظه (RAM) یا در یک پایگاه داده موجوده و می‌خواید روی هر عضو این لیست پردازشی انجام بدید؛ مثلاً همه‌ی عناصر رو با هم جمع کنید، یا بشمرید ببینید توی چند تا سطر از یک رمان ۱۰۰۰ صفحه‌ای کلمه‌ی مشخصی به کار رفته. مادامی که پردازش مورد نظر شما به واحدهای اجرا شونده‌ی موازی قابل افراز باشه، می‌تونید از طریق واسط‌های برنامه نویسی اسپارک آنالیز مورد نظرتون رو پیاده سازی کنید. حالا این کد می‌تونه روی یک زیرساخت کلاستر (مثلا Kubernetes) اجرا بشه، به این صورت که اول یک driver node و بعد به تعدادی که از قبل براش configure شده (مثلا ۱۰ تا) executor node بالا میاد. بعد اسپارک اطلاعات رو تبدیل می‌کنه به داده ساختاری به نام Resilient Distributed Dataset یا به طور خلاصه RDD و سپس از طریق driver این RDD رو «توزیع» می‌کنه روی executor ها تا هر کدوم پردازش‌های لازم رو انجام بدن و نتیجه رو برگردونن به driver. در نهایت هم driver جمع بندی می‌کنه و تمام!

تشخیص نقاط پرتکرار

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

برای این که بفهمیم بهترین predictor نقاط پرتکرار چیه، می‌تونیم مدل‌های مختلف Machine Learning رو طراحی و ارزیابی کنیم. مدلی که ما در نهایت استفاده کردیم، DBSCAN در کتابخانه‌ی Scikit Learn پایتون هست که جزو الگوریتم‌های خوشه‌بندی (Clustering) از دسته‌ی الگوریتم‌های یادگیری بدون ناظر (Unsupervised Learning) هست. DBSCAN مبدأ و مقصدهای کاربر رو دریافت می‌کنه و می‌بینه کجاها چگالی یا تراکم نقطه‌ها زیاده تا میانگین اون نقاط رو به عنوان یک نقطه‌ی پرتکرار به ما معرفی کنه. مرز بین دسته‌ها هم با مناطق کم تراکم مشخص می‌شن. ما برای DBSCAN حداقل تعداد پین‌های لازم برای یک دسته رو برابر ۲ و حداکثر فاصله‌ی بین دو پین رو برای این که به عنوان همسایگی هم شناخته بشن، حدود ۱۰۰ متر تعیین کردیم.

شاید براتون سؤال بشه که چرا به جای DBSCAN از الگوریتم معروفی مثل K-Means استفاده نکردیم؟ باید بگم که K-Means دو تا ویژگی داره که به درد مورد ما نمی‌خورد: اول این که «تعداد» دسته‌ها حین یادگیری به دست نمیاد و باید از قبل به صورت یک hyperparameter براش تعیین بشه، ولی اتفاقاً ما می‌خوایم تعداد دسته‌ها حین یادگیری به دست بیاد؛ دوم هم این که دسته‌های K-Means الزاما شبیه چندضلعی‌های محدب ساخته می‌شن، ولی DBSCAN چون به «تراکم» توجه می‌کنه و نه فقط «فاصله»، کاری به توپولوژی دسته‌ها نداره و می‌تونن هر شکل دلخواهی داشته باشند.

توضیحش سخت شد، بهتره از تصاویر کمک بگیریم؛ از قدیم گفتن یک تصویر بهتر از هزار کلمه است! توی تصاویر ۳ و ۴ می‌تونید خروجی دسته بندی الگوریتم‌های DBSCAN و K-Means رو با هم مقایسه کنید. بیاین فرض کنیم هر کدوم از دسته‌های DBSCAN یک کوچه یا خیابون هستند و شما در یک ماه گذشته در نقاط مختلف این کوچه‌ها مبدأ و مقصد انتخاب کردید. حالا فکر کنم با من موافق باشید که مرکز دسته‌های DBSCAN نماینده‌های بهتری برای نقاط پرتکرار هستن، تا مرکز دسته‌های K-Means که انگار بعضی از کوچه‌ها رو با هم قاطی کرده.

ریلیز نهایی

حالا که پیاده سازی سمت بک اند و پردازش‌ها رو مفصل براتون توضیح دادم، وقتشه که اپلیکیشن اسنپ یه آپدیت بده و از این قابلیت جذاب رونمایی کنه! روشی که برای انتشار (release) نهایی یک قابلیت برای کاربر نهایی (end user) مرسومه، A/B Testing نام داره. این تست همون طور که از اسمش پیداست، کاربرهای اپ رو به دو دسته‌ی آ و ب تقسیم می‌کنه (به ترتیب مثلا شامل ۹۰٪ و ۱۰٪ کاربرها) و قابلیت رو سمت سرور فقط برای دسته‌ی ب فعال می‌کنه.

مزیت این روش اینه که از اونجایی که یک قابلیت جدید احتمال داره اونقدری که ما فکرش رو می‌کردیم، خوب از آب در نیاد و تجربه‌ی کاربری ناخوشایندی رو رقم بزنه، در نتیجه بهتره که بی گدار به آب نزنیم و گام به گام کاربرا رو باهاش آشنا کنیم. به مرور اگه احساس کردیم قابلیت جدید حال کاربرها رو بهتر می‌کنه، سهم دسته‌ی ب رو زیاد می‌کنیم تا این که نهایتا به ۱۰۰٪ برسه و اون موقع ریلیز نهایی می‌شه.

آمار و متریک‌ها

ما ابتدای هر هفته این سرویس رو روی بستر Spark اجرا می‌کنیم. اجراش بیش از ۱۰ ساعت طول می‌کشه (بیشتر این زمان به خاطر محاسبه آدرس برای هر نقطه‌ی پرتکراره) و برای بیش از ۱۳ میلیون کاربر فعال اسنپ، حدود ۱۰ میلیون نقطه پرتکرار به دست میاد.

و اما ببینیم متریک‌ها چطور تغییر کردند؟

ما برای مانیتور کردن کاربران از سرویس آنالیتیکز AppMetrica استفاده می‌کنیم. کار با اپ‌متریکا به این صورته که برای هر رفتار کاربر در اپلیکیشن که می‌خوایم ازش مطلع بشیم، مثل مشاهده‌ی صفحه اول نقشه، کلیک روی نقاط «مورد علاقه»، نقاط «پرتکرار» و ... اصطلاحاً یک رویداد (event) در پنل مدیریتی اپ‌متریکا تعریف می‌کنیم و در مواقع لازم از سمت کلاینت اون رویداد رو ارسال می‌کنیم. این رویدادها در طول روز از تمامی کاربران اسنپ دریافت و در سرور اپ‌متریکا ذخیره و تجمیع می‌شن.

حالا می‌تونیم با تحلیل انبوه رویدادهای ذخیره شده، متریک‌های جذاب و متنوعی رو استخراج کنیم که در این جا به طور خلاصه به ۲ تا از مهم ترین اون‌ها اشاره می‌کنم:

1. مدت زمانی که طول می‌کشه تا کاربر مبدأ یا مقصد رو تعیین کنه. (فاصله‌ی زمانی بین ارسال رویدادهای «نمایش صفحه» تا «انتخاب پین»)
2. نسبت میزان استفاده از نقاط «پرتکرار» به «نقاط مورد علاقه». (مقایسه تعداد رویدادهای کلیک نقاط پرتکرار و مورد علاقه.)

سرتون رو درد نیارم! برای کاربرهایی که این قابلیت براشون فعال شده بود، متریک اول ۷٪ بهبود پیدا کرد و متریک دوم در فاز مبدأ و مقصد به ترتیب ۶۴٪ و ۴۰٪ گزارش شد که نسبت قابل ملاحظه‌ای بود و در نتیجه پروژه‌ی نقاط پرتکرار تبدیل به یکی از موفق ترین پروژه‌های تیم نقشه شد.

کارهای بیشتر

چطور می‌تونیم این پروژه رو باز هم بهتر کنیم؟ راه‌های مختلفی ممکنه به ذهن برسه.

برای مثال، حالا که فهمیدیم نقاط پرتکرار این قدر کاربرد دارند، چرا تبدیل به نقاط مورد علاقه‌ی کاربر نشن؟ این طوری همیشه توی اپ برای کاربر ذخیره باقی می‌مونن؛ و فرضاً اگه مدتی سفرهای کاربر به اون نقطه کمتر شد، پیشنهاد اون نقطه حذف نمی‌شه و همیشه می‌تونه به فاصله‌ی یک کلیک اون نقطه رو انتخاب کنه. پس می‌تونیم این قابلیت رو سمت کلاینت پیاده سازی کنیم که کاربر بتونه نقاط پرتکرارش رو تبدیل به نقاط مورد علاقه‌ش بکنه.

کار دیگه‌ای که میشه انجام داد، امتحان مدل‌های متنوع‌تر یادگیری ماشین برای این پروژه است. مثلا در این پروژه ما فقط از DBSCAN استفاده کردیم، در حالی که مدل‌های Ensemble با کنار هم قرار دادن چند مدل ضعیف‌تر می‌تونن یک مدل پیش‌بینی کننده‌ی قوی رو ایجاد کنن. خوبه که تلاش کنیم دقت پیش‌بینی مدل رو با امتحان مدل‌های مختلف یا تنظیم hyperparameter ها بیشتر کنیم.

پایان!

ممنون که پست رو تا انتها خوندید. خوشحال می‌شم که این پست رو لایک کنید و اگه نظر یا سؤالی دارید، توی کامنت‌ها با من در میون بگذارید. در ضمن، اگه حس می‌کنین از پروژه‌هایی شبیه به این خوشتون میاد و در نتیجه علاقه دارید به تیم ما ملحق بشید، خوشحال می‌شیم که رزومه‌هاتون رو از طریق آدرس engineering@snapp.cab برای ما ارسال کنید.