صفحه اصلی ویدیوهای ما اکنون با هر بار بازنشانی (refresh)، مجموعه جدیدی از ۲۴ پیشنهاد را نمایش میدهد؛ این امر به لطف تغییر رویکرد به نمونهبرداری مخزنی وزندار (A-Res) میسر شده است. این تغییر، مشکل «شبکه همیشه یکسان» را که فید قبلی ما (که بر اساس امتیاز مرتب شده بود) با آن دستبهگریبان بود، از بین برد.
چرا رویکرد قدیمی تجربه کاربری را خراب میکرد
ما هر دو ساعت یکبار، آخرین ویدیوهای ترند را از هشت منطقه استخراج کرده و نتایج را در یک جدول SQLite میریزیم. راهکار ساده (naïve) این بود که کل مجموعه را بر اساس امتیاز مرتبط بودن (relevance score) مرتب کنیم و ۲۴ مورد اول را برداریم. این روش تضمین میکند که آیتمهایی با بالاترین امتیاز نمایش داده شوند، اما در عین حال تضمین میکند که آنها همانجا باقی بمانند. یک کلیپ وایرال میتواند روزها جایگاه اول را در اختیار بگیرد و کاربران با هر بار بارگذاری مجدد، شبکهای کاملاً یکسان را مشاهده میکنند.
فراتر از تجربه کاربری خستهکننده، مرتب کردن کل جدول برای هر درخواست، SQLite را مجبور میکند تا یک ساختار موقت بزرگ را در حافظه بارگذاری کند که باعث اتلاف منابع میشود.
نمونهبرداری مخزنی وزندار چه مزایایی برای ما دارد
نمونهبرداری مخزنی وزندار دو مشکل را همزمان حل میکند:
۱. تازگی همراه با سوگیری (bias) – شانس انتخاب هر ویدیو با وزن آن (مثلاً امتیاز مرتبط بودن) متناسب است. ویدیویی با وزن دو برابر، دو برابر بیشتر احتمال دارد که ظاهر شود، اما هیچ آیتمی جایگاه خود را تضمین نمیکند.
۲. بهینگی حافظه – این الگوریتم تنها یک «مخزن» با اندازه ثابت شامل k آیتم را نگه میدارد (k = 24 برای فید ما). این الگوریتم جریان داده را در یک مرحله (single pass) پردازش میکند، بنابراین میزان مصرف حافظه بدون توجه به تعداد کاندیداهای ورودی، در سطح O(k) باقی میماند.
ایده اصلی ساده است. همانطور که ردیفهای ورودی را اسکن میکنیم، به هر آیتم یک کلید تصادفی اختصاص میدهیم که وزن آن را نیز در خود جای داده است، سپس k آیتمی که بالاترین کلیدها را دارند، نگه میداریم.
الگوریتم در عمل
برای هر ویدیو ما:
۱. یک عدد تصادفی یکنواخت u ∈ (0, 1) استخراج میکنیم.
۲. یک کلید k = u^(1/weight) محاسبه میکنیم.
(هرچه وزن بالاتر باشد، کلید مورد انتظار بزرگتر خواهد بود.)
۳. آیتم را در یک min-heap که بالاترین k کلید فعلی را ذخیره میکند، وارد میکنیم.
اگر اندازه heap از k فراتر رفت، کوچکترین کلید را حذف میکنیم.
وقتی جریان داده تمام میشود، heap شامل همان ۲۴ ویدیویی است که نمایش خواهیم داد.
مقابله با محدودیتهای ممیز شناور (floating-point)
وقتی وزن یک ویدیو بسیار بزرگ باشد، u^(1/weight) در محاسبات با دقت مضاعف (double-precision) به مقداری تبدیل میشود که از 1.0 قابل تشخیص نیست؛ این امر باعث میشود بسیاری از آیتمهای سنگین، کلید یکسانی داشته باشند و تصادفی بودن از دست برود. راه حل، کار کردن در فضای لگاریتمی (log space) است:
- به جای عبارت توان،
log_key = log(u) / weightرا محاسبه کنید.
از آنجایی که لگاریتمها توانرسانی را به ضرب تبدیل میکنند، ترتیب کلیدها حفظ شده و در عین حال از افت دقت جلوگیری میشود. این محاسبه تقریباً هیچ هزینه اضافی ندارد.
چکلیست پیادهسازی
- ساختار داده: یک
min-heap(صف اولویت) با اندازهk، بزرگترین کلیدها را به شکلی کارآمد نگه میدارد (O(log k)برای هر درج). - نوع عددی: از اعداد ممیز شناور ۶۴ بیتی برای
uو کلیدهای مبتنی بر لگاریتم استفاده کنید؛ آنها دقت کافی را برای محدودههای معمول وزن فراهم میکنند. - بررسی صحت آماری: یک تست سریع مونتکارلو (Monte-Carlo) روی یک مجموعه نمونه کوچک اجرا کنید. اگر آیتمهایی با وزن ۱۰ تقریباً ده برابر بیشتر از آیتمهایی با وزن ۱ ظاهر شدند، پیادهسازی صحیح است.
- جریان تکمرحلهای (Single-pass streaming): الگوریتم نیازی ندارد از قبل تعداد کل کاندیداها را بداند، که این ویژگی به طور طبیعی با
cursorدر SQLite ما که ردیفها را یکییکی ارائه میدهد، سازگار است.
جمعبندی
نمونهبرداری مخزنی وزندار به سرویس پیشنهاد ویدیو اجازه میدهد تا صفحه اصلی خود را تازه نگه دارد، به امتیازهای مرتبط بودن احترام بگذارد و مصرف حافظه کمی داشته باشد؛ و تمام اینها تنها با یک بار پیمایش روی دهها هزار کاندیدا انجام میشود. با انتقال محاسبه کلید به فضای لگاریتمی و استفاده از یک min-heap ، این روش هم دقیق و هم با کارایی بالا باقی میماند.