आमच्या व्हिडिओ होमपेजवर आता प्रत्येक रिफ्रेशवर २४ शिफारसींचा (recommendations) एक नवीन संच दिसतो, याचे श्रेय 'weighted reservoir sampling (A-Res)' कडे वळल्यामुळे मिळाले आहे. या बदलामुळे "नेहमी तोच ग्रिड" (same-grid-forever) ही समस्या दूर झाली आहे, जी आमच्या पूर्वीच्या स्कोअर-सॉर्टेड फीडमध्ये येत होती.

जुना दृष्टिकोन अनुभव का बिघडवत होता

दर दोन तासांनी आम्ही आठ क्षेत्रांतील (regions) नवीनतम ट्रेंडिंग व्हिडिओ घेतो आणि ते निकाल एका SQLite टेबलमध्ये साठवतो. संपूर्ण संच—रिलेव्हन्स स्कोअरनुसार (relevance score)—सॉर्ट करणे आणि त्यातील टॉप २४ घेणे, हा एक साधा उपाय होता. ही पद्धत सर्वाधिक स्कोअर असलेले आयटम दिसण्याची खात्री देते, परंतु ते तिथेच राहतील याचीही खात्री देते. एखादा व्हायरल व्हिडिओ कित्येक दिवस पहिल्या क्रमांकावर राहू शकतो आणि वापरकर्त्यांना प्रत्येक वेळी रिलोड केल्यावर तोच ग्रिड दिसतो.

जुनाट अनुभवाव्यतिरिक्त, प्रत्येक विनंतीसाठी (request) संपूर्ण टेबल सॉर्ट केल्यामुळे SQLite ला मेमरीमध्ये एक मोठी तात्पुरती रचना (temporary structure) लोड करावी लागते, जे वाया जाणारे आहे.

Weighted reservoir sampling आपल्याला काय देते

Weighted reservoir sampling दोन समस्या एकाच वेळी सोडवते:

  1. बायससह ताजेपणा (Freshness with bias) – प्रत्येक व्हिडिओ निवडण्याची शक्यता त्याच्या वेटला (weight) प्रमाणात असते (उदा. relevance score). ज्या व्हिडिओचे वेट दुप्पट आहे, तो दिसण्याची शक्यता दुप्पट असते, परंतु कोणत्याही आयटमला जागा मिळण्याची खात्री नसते.
  2. मेमरी कार्यक्षमता (Memory efficiency) – हा अल्गोरिदम केवळ k आयटमचा (आमच्या फीडसाठी k = २४) एक ठराविक आकाराचा "रिझर्व्होअर" (reservoir) ठेवतो. तो स्ट्रीमवर एकाच वेळी प्रक्रिया करतो, त्यामुळे कितीही उमेदवार (candidates) आले तरी मेमरी O(k) राहते.

मूळ कल्पना सोपी आहे. जसे आपण येणाऱ्या रो (rows) स्कॅन करतो, तसे आपण प्रत्येक आयटमला एक रँडम की (random key) देतो ज्यामध्ये त्याचे वेट समाविष्ट असते, आणि नंतर सर्वाधिक की असलेले k आयटम राखून ठेवतो.

प्रत्यक्ष वापरातील अल्गोरिदम

प्रत्येक व्हिडिओसाठी आम्ही:

  1. एक युनिफॉर्म रँडम नंबर u ∈ (0, 1) निवडतो.
  2. की k = u^(1/weight) ची गणना करतो.
    (वेट जितके जास्त, तितकी अपेक्षित की मोठी असेल.)
  3. आयटम एका min-heap मध्ये टाकतो जो सध्याच्या टॉप k की साठवतो.
    जर हीपचा आकार k पेक्षा जास्त झाला, तर आम्ही सर्वात लहान की काढून टाकतो.

जेव्हा स्ट्रीम संपते, तेव्हा हीपमध्ये ते २४ व्हिडिओ असतात जे आम्ही प्रदर्शित करणार आहोत.

फ्लोटिंग-पॉइंट मर्यादा हाताळणे

जेव्हा व्हिडिओचे वेट खूप मोठे असते, तेव्हा u^(1/weight) ची किंमत double-precision arithmetic मध्ये 1.0 पासून वेगळी ओळखता न येण्याइतपत कमी होते, ज्यामुळे अनेक 'हेवी' आयटमची की एकसारखी होते आणि रँडमनेस (randomness) कमी होतो. याचे निराकरण 'log space' मध्ये काम करणे हे आहे:

  • पॉवर एक्सप्रेशनऐवजी log_key = log(u) / weight ची गणना करा.

कारण लॉगॅरिदममुळे घातांक (exponentiation) गुणाकारामध्ये रूपांतरित होतो, ज्यामुळे अचूकतेचा (precision) अभाव टाळत की (keys) चा क्रम कायम राहतो. या गणनेसाठी अतिरिक्त खर्च जवळजवळ शून्य आहे.

अंमलबजावणीसाठी चेकलिस्ट

  • डेटा स्ट्रक्चर (Data structure): k आकाराचा एक min-heap (priority queue) मोठ्या की कार्यक्षमतेने साठवतो (प्रत्येक इन्सर्शनसाठी O(log k)).
  • न्यूमेरिक टाईप (Numeric type): u आणि लॉग-आधारित की साठी 64-bit फ्लोटिंग-पॉइंट नंबर्स वापरा; ते सामान्य वेट रेंजसाठी पुरेशी अचूकता देतात.
  • सांख्यिकीय तपासणी (Statistical sanity check): एका लहान सॅम्पल सेटवर जलद Monte-Carlo टेस्ट चालवा. जर वेट १० असलेले आयटम वेट १ च्या तुलनेत साधारण दहा पट जास्त वेळा दिसत असतील, तर अंमलबजावणी बरोबर आहे.
  • सिंगल-पास स्ट्रीमिंग (Single-pass streaming): अल्गोरिदमला उमेदवारांच्या एकूण संख्येची आगाऊ माहिती असण्याची गरज नसते, जे आमच्या SQLite कर्सरशी नैसर्गिकरित्या जुळते जो एक-एक करून रो (rows) देतो.

निष्कर्ष

Weighted reservoir sampling मुळे व्हिडिओ शिफारस सेवा (recommendation service) तिची होमपेज ताजी ठेवू शकते, रिलेव्हन्स स्कोअरचा आदर करू शकते आणि मेमरीचा वापर कमी ठेवू शकते—तेही हजारो उमेदवारांवर केवळ एकाच वेळी प्रक्रिया करून. की (key) गणना लॉग स्पेसमध्ये हलवून आणि min-heap वापरून, ही पद्धत अचूक आणि कार्यक्षम दोन्ही राहते.