ہماری ویڈیو ہوم پیج اب ہر ریفریش پر 24 نئی سفارشات (recommendations) دکھاتی ہے، جس کی وجہ weighted reservoir sampling (A-Res) پر منتقلی ہے۔ اس تبدیلی نے "ہمیشہ ایک جیسی گرڈ" (same-grid-forever) کے مسئلے کو ختم کر دیا ہے جو ہمارے پہلے والے اسکور پر مبنی فیڈ (score-sorted feed) میں درپیش تھا۔
پرانا طریقہ کار تجربے کو کیوں خراب کر رہا تھا
ہر دو گھنٹے بعد ہم آٹھ علاقوں سے تازہ ترین ٹرینڈنگ ویڈیوز نکالتے ہیں اور نتائج کو SQLite ٹیبل میں ڈال دیتے ہیں۔ سادہ سا حل یہ تھا کہ پورے سیٹ کو—relevance score کے ذریعے—ترتیب (sort) دیا جائے اور ٹاپ 24 ویڈیوز لے لی جائیں۔ یہ طریقہ اس بات کی ضمانت دیتا ہے کہ سب سے زیادہ اسکور والی چیزیں نظر آئیں گی، لیکن یہ اس بات کی بھی ضمانت دیتا ہے کہ وہ وہیں رہیں گی۔ ایک ہی وائرل کلپ کئی دنوں تک پوزیشن 1 پر حاوی رہ سکتا ہے، اور صارفین جب بھی ری لوڈ کرتے ہیں انہیں بالکل ایک جیسی گرڈ نظر آتی ہے۔
پرانے اور اکتا دینے والے تجربے کے علاوہ، ہر درخواست کے لیے پوری ٹیبل کو ترتیب دینے سے SQLite کو میموری میں ایک بڑا عارضی ڈھانچہ (temporary structure) لوڈ کرنا پڑتا ہے، جو کہ فضول ہے۔
Weighted reservoir sampling ہمیں کیا فراہم کرتی ہے
Weighted reservoir sampling دو مسائل کو ایک ساتھ حل کرتی ہے:
- بایاس کے ساتھ تازگی (Freshness with bias) – ہر ویڈیو کے منتخب ہونے کا امکان اس کے وزن (weight) کے تناسب سے ہوتا ہے (مثلاً relevance score)۔ جس ویڈیو کا وزن دگنا ہو اس کے نظر آنے کا امکان بھی دگنا ہوتا ہے، لیکن کسی بھی آئٹم کی جگہ یقینی نہیں ہوتی۔
- میموری کی کارکردگی (Memory efficiency) – یہ الگورتھم صرف k آئٹمز کا ایک مقررہ سائز کا "ریزروائر" (reservoir) رکھتا ہے (ہمارے فیڈ کے لیے k = 24)۔ یہ اسٹریم کو ایک ہی بار (single pass) میں پروسیس کرتا ہے، اس لیے امیدواروں (candidates) کی تعداد چاہے جتنی بھی ہو، میموری O(k) ہی رہتی ہے۔
اس کا بنیادی تصور سادہ ہے۔ جیسے جیسے ہم آنے والی روز (rows) کو اسکین کرتے ہیں، ہم ہر آئٹم کو ایک رینڈم کی (random key) دیتے ہیں جس میں اس کا وزن شامل ہوتا ہے، پھر ہم سب سے زیادہ کی (key) والے k آئٹمز کو برقرار رکھتے ہیں۔
عملی طور پر الگورتھم
ہر ویڈیو کے لیے ہم:
- ایک یونیفارم رینڈم نمبر
u ∈ (0, 1)نکالتے ہیں۔ - ایک کی (key) کا حساب لگاتے ہیں
k = u^(1/weight)۔
(وزن جتنا زیادہ ہوگا، متوقع کی (key) اتنی ہی بڑی ہوگی۔) - آئٹم کو ایک min-heap میں ڈالتے ہیں جو موجودہ ٹاپ k کیز (keys) کو محفوظ رکھتا ہے۔
اگر ہیپ (heap) کا سائز k سے بڑھ جائے، تو ہم سب سے چھوٹی کی (key) کو نکال دیتے ہیں۔
جب اسٹریم ختم ہو جاتی ہے، تو ہیپ میں وہ 24 ویڈیوز ہوتی ہیں جو ہم دکھائیں گے۔
فلوٹنگ پوائنٹ کی حدود سے نمٹنا
جب کسی ویڈیو کا وزن بہت زیادہ ہو، تو u^(1/weight) کی قیمت ڈبل پریسیژن (double-precision) حساب کتاب میں 1.0 سے الگ نہیں پہچانی جا سکتی، جس کی وجہ سے بہت سے بھاری آئٹمز ایک ہی کی (key) شیئر کرنے لگتے ہیں اور رینڈم نیس (randomness) ختم ہو جاتی ہے۔ اس کا حل لاگ سپیس (log space) میں کام کرنا ہے:
- پاور ایکسپریشن کے بجائے
log_key = log(u) / weightکا حساب لگائیں۔
چونکہ لاگتھم (logarithms) ایکسپونینشی ایشن (exponentiation) کو ضرب (multiplication) میں بدل دیتے ہیں، اس لیے پریسیژن کے گرنے سے بچتے ہوئے کیز (keys) کی ترتیب برقرار رہتی ہے۔ اس حساب کتاب میں اضافی طور پر تقریباً کچھ بھی خرچ نہیں ہوتا۔
امپلیمنٹیشن چیک لسٹ
- ڈیٹا اسٹرکچر (Data structure): سائز k کا ایک min-heap (priority queue) بڑی سے بڑی کیز کو مؤثر طریقے سے محفوظ رکھتا ہے (فی انسرشن O(log k))۔
- نمیرک ٹائپ (Numeric type):
uاور لاگ پر مبنی کیز کے لیے 64-bit فلوٹنگ پوائنٹ نمبرز استعمال کریں؛ یہ عام وزن کی حد کے لیے کافی پریسیژن فراہم کرتے ہیں۔ - اعداد و شمار کا معائنہ (Statistical sanity check): ایک چھوٹے سیمپل سیٹ پر فوری مونٹی کارلو (Monte-Carlo) ٹیسٹ چلائیں۔ اگر وزن 10 والے آئٹمز، وزن 1 والے آئٹمز کے مقابلے میں تقریباً دس گنا زیادہ نظر آتے ہیں، تو امپلیمنٹیشن درست ہے۔
- سنگل پاس اسٹریمنگ (Single-pass streaming): الگورتھم کو پہلے سے امیدواروں کی کل تعداد جاننے کی ضرورت نہیں ہوتی، جو ہمارے SQLite کرسر (cursor) کے ساتھ قدرتی طور پر مطابقت رکھتا ہے جو ایک ایک کر کے روز (rows) فراہم کرتا ہے۔
خلاصہ
Weighted reservoir sampling ایک ویڈیو ریکمنڈیشن سروس کو اپنی ہوم پیج کو تازہ رکھنے، relevance scores کا احترام کرنے، اور میموری کے لحاظ سے ہلکا رہنے میں مدد دیتی ہے—وہ بھی ہزاروں امیدواروں پر صرف ایک بار گزر (single pass) کے ذریعے ۔ کی (key) کے حساب کو لاگ سپیس میں منتقل کر کے اور min-heap کا استعمال کر کے، یہ طریقہ کار درست اور کارکردگی کے لحاظ سے بہترین رہتا ہے۔