हमारे वीडियो होमपेज पर अब हर रिफ्रेश पर 24 नए सुझाव (recommendations) दिखाई देते हैं, और यह weighted reservoir sampling (A-Res) पर स्विच करने की वजह से संभव हुआ है। इस बदलाव ने "हमेशा एक जैसा ग्रिड" (same-grid-forever) वाली समस्या को खत्म कर दिया है, जो हमारे पहले के स्कोर-आधारित फीड में बनी रहती थी।

पुराना तरीका अनुभव को क्यों खराब कर रहा था

हर दो घंटे में हम आठ क्षेत्रों से नवीनतम ट्रेंडिंग वीडियो निकालते हैं और परिणामों को एक SQLite टेबल में डाल देते हैं। इसका सरल समाधान पूरे सेट को—relevance score के आधार पर—सॉर्ट करना और शीर्ष 24 वीडियो लेना था। यह तरीका सुनिश्चित करता है कि उच्चतम स्कोर वाले आइटम दिखाई दें, लेकिन यह यह भी सुनिश्चित करता है कि वे वहीं बने रहें। एक अकेला वायरल क्लिप कई दिनों तक पोजीशन 1 पर छाया रह सकता है, और उपयोगकर्ता जब भी पेज रीलोड करते हैं, उन्हें बिल्कुल एक जैसा ग्रिड दिखाई देता है।

पुराने अनुभव के अलावा, हर रिक्वेस्ट के लिए पूरी टेबल को सॉर्ट करने से SQLite को मेमोरी में एक बड़ा अस्थायी स्ट्रक्चर लोड करने के लिए मजबूर होना पड़ता है, जो संसाधनों की बर्बादी है।

Weighted reservoir sampling हमें क्या देता है

Weighted reservoir sampling दो समस्याओं को एक साथ हल करता है:

  1. बायस के साथ फ्रेशनेस (Freshness with bias) – प्रत्येक वीडियो के चुने जाने की संभावना उसके वेट (weight) के समानुपाती होती है (जैसे, relevance score)। दोगुना वेट वाले वीडियो के दिखने की संभावना दोगुनी होती है, लेकिन किसी भी आइटम के लिए जगह की गारंटी नहीं होती।
  2. मेमोरी दक्षता (Memory efficiency) – यह एल्गोरिदम केवल k आइटमों का एक निश्चित आकार का "रिजर्वायर" (reservoir) रखता है (हमारे फीड के लिए k = 24)। यह स्ट्रीम को सिंगल पास (single pass) में प्रोसेस करता है, इसलिए उम्मीदवारों (candidates) की संख्या चाहे कितनी भी हो, मेमोरी O(k) ही रहती है।

इसका मूल विचार सरल है। जैसे-जैसे हम आने वाली पंक्तियों (rows) को स्कैन करते हैं, हम प्रत्येक आइटम को एक रैंडम की (random key) देते हैं जिसमें उसका वेट शामिल होता है, और फिर उच्चतम की (keys) वाले k आइटमों को रखते हैं।

व्यवहार में एल्गोरिदम

प्रत्येक वीडियो के लिए हम:

  1. एक यूनिफॉर्म रैंडम नंबर u ∈ (0, 1) चुनें।
  2. एक की (key) k = u^(1/weight) की गणना करें।
    (वेट जितना अधिक होगा, अपेक्षित की उतनी ही बड़ी होगी।)
  3. आइटम को एक min-heap में डालें जो वर्तमान शीर्ष k की (keys) को स्टोर करता है।
    यदि हीप (heap) का आकार k से अधिक हो जाता है, तो हम सबसे छोटी की को हटा देते हैं।

जब स्ट्रीम समाप्त होती है, तो हीप में वे 24 वीडियो होते हैं जिन्हें हम प्रदर्शित करेंगे।

फ्लोटिंग-पॉइंट सीमाओं से निपटना

जब किसी वीडियो का वेट बहुत अधिक होता है, तो u^(1/weight) का मान double-precision arithmetic में 1.0 से अलग नहीं रह जाता, जिससे कई भारी आइटम एक ही की (key) साझा करने लगते हैं और रैंडमनेस खत्म हो जाती है। इसका समाधान लॉग स्पेस (log space) में काम करना है:

  • पावर एक्सप्रेशन के बजाय log_key = log(u) / weight की गणना करें।

चूंकि लॉगैरिदम एक्सपोनेंटिएशन (exponentiation) को गुणा (multiplication) में बदल देते हैं, इसलिए प्रिसिजन (precision) की समस्या से बचते हुए की (keys) का क्रम सुरक्षित रहता है। इस गणना में अतिरिक्त लागत लगभग शून्य है।

इम्प्लीमेंटेशन चेकलिस्ट

  • डेटा स्ट्रक्चर: आकार k का एक min-heap (priority queue) कुशलतापूर्वक सबसे बड़ी की (keys) को रखता है (प्रति इंसर्शन O(log k))।
  • न्यूमेरिक टाइप: u और लॉग-आधारित की (keys) के लिए 64-bit फ्लोटिंग-पॉइंट नंबरों का उपयोग करें; वे सामान्य वेट रेंज के लिए पर्याप्त प्रिसिजन प्रदान करते हैं।
  • सांख्यिकीय सैनिटी चेक (Statistical sanity check): एक छोटे सैंपल सेट पर त्वरित मोंटे-कार्लो (Monte-Carlo) टेस्ट चलाएं। यदि वेट 10 वाले आइटम, वेट 1 वाले आइटम की तुलना में लगभग दस गुना अधिक बार दिखाई देते हैं, तो इम्प्लीमेंटेशन सही है।
  • सिंगल-पास स्ट्रीमिंग: एल्गोरिदम को उम्मीदवारों की कुल संख्या पहले से जानने की आवश्यकता नहीं होती है, जो हमारे SQLite कर्सर के साथ स्वाभाविक रूप से फिट बैठता है जो एक-एक करके पंक्तियाँ (rows) देता है।

निष्कर्ष

Weighted reservoir sampling एक वीडियो रिकमेंडेशन सर्विस को अपने होमपेज को फ्रेश रखने, relevance scores का सम्मान करने और मेमोरी-लाइट रहने में मदद करता है—वह भी हजारों उम्मीदवारों पर केवल एक सिंगल पास के साथ। की (key) की गणना को लॉग स्पेस में ले जाकर और min-heap का उपयोग करके, यह तरीका सटीक और परफॉर्मेंट दोनों बना रहता है।