எங்களது வீடியோ முகப்புப் பக்கம் (homepage) இப்போது ஒவ்வொரு முறை புதுப்பிக்கும் போதும் (refresh) 24 புதிய பரிந்துரைகளைக் காட்டுகிறது. இதற்கு 'weighted reservoir sampling (A-Res)' முறைக்கு மாறியதே காரணம். இந்த மாற்றமானது, எங்களது முந்தைய ஸ்கோர் அடிப்படையில் வரிசைப்படுத்தப்பட்ட (score-sorted) பீடில் இருந்த "எப்போதும் ஒரே மாதிரியான கட்டம்" (same-grid-forever) என்ற சிக்கலை நீக்கியுள்ளது.

பழைய அணுகுமுறை ஏன் அனுபவத்தைக் கெடுத்தது

ஒவ்வொரு இரண்டு மணிநேரத்திற்கும் எங்களது எட்டுப் பகுதிகளிலிருந்து (regions) சமீபத்திய டிரெண்டிங் வீடியோக்களைப் பெற்று, அந்த முடிவுகளை ஒரு SQLite அட்டவணையில் சேமிக்கிறோம். முழுத் தொகுப்பையும் ஒரு பொருத்தத் தன்மையின் அடிப்படையில் (relevance score) வரிசைப்படுத்தி, அதில் முதல் 24 வீடியோக்களை எடுப்பதே எளிமையான தீர்வாக இருந்தது. அந்த முறை அதிக ஸ்கோர் கொண்ட வீடியோக்கள் வருவதை உறுதி செய்தாலும், அவை அங்கேயே தொடர்ந்து இருப்பதை உறுதி செய்துவிடுகிறது. ஒரு வைரல் வீடியோ பல நாட்களுக்கு முதல் இடத்தையே ஆக்கிரமிக்கக்கூடும், இதனால் பயனர்கள் ஒவ்வொரு முறை ரீலோட் செய்யும் போதும் ஒரே மாதிரியான கட்டத்தையே பார்க்க நேரிடுகிறது.

இந்தத் தேய்ந்து போன அனுபவத்தைத் தாண்டி, ஒவ்வொரு கோரிக்கைக்கும் (request) முழு அட்டவணையையும் வரிசைப்படுத்துவது, SQLite ஒரு பெரிய தற்காலிக அமைப்பை நினைவகத்தில் (memory) ஏற்ற வேண்டிய கட்டாயத்தை ஏற்படுத்துகிறது, இது வீணான செயலாகும்.

Weighted reservoir sampling நமக்கு எதை வழங்குகிறது

Weighted reservoir sampling ஒரே நேரத்தில் இரண்டு சிக்கல்களைத் தீர்க்கிறது:

  1. சார்புத் தன்மையுடன் கூடிய புத்துணர்ச்சி (Freshness with bias) – ஒவ்வொரு வீடியோவும் தேர்ந்தெடுக்கப்படுவதற்கான வாய்ப்பு அதன் எடையைப் (weight - எ.கா. relevance score) பொறுத்து அமையும். இருமடங்கு எடை கொண்ட வீடியோ இருமடங்கு வாய்ப்புடன் தோன்றும், ஆனால் எந்த ஒரு வீடியோவும் கண்டிப்பாகத் தேர்ந்தெடுக்கப்படும் என்று சொல்ல முடியாது.
  2. நினைவகத் திறன் (Memory efficiency) – இந்த அல்காரிதம் 'k' எண்ணிக்கையிலான உருப்படிகளைக் கொண்ட ஒரு குறிப்பிட்ட அளவுள்ள "reservoir"-ஐ மட்டுமே வைத்திருக்கும் (எங்களது பீடிற்கு k = 24). இது தரவு ஓட்டத்தை (stream) ஒரே ஒரு முறை மட்டுமே ஆய்வு செய்வதால், எத்தனை வீடியோக்கள் வந்தாலும் நினைவகப் பயன்பாடு O(k) என்ற நிலையிலேயே இருக்கும்.

இதன் அடிப்படை யோசனை எளிமையானது. வரும் வரிசைகளை (rows) ஆய்வு செய்யும் போது, ஒவ்வொரு உருப்படிக்கும் அதன் எடையைக் கணக்கில் கொண்ட ஒரு ரேண்டம் கீயை (random key) வழங்குகிறோம், பின்னர் அதிகபட்ச கீகளைக் கொண்ட k உருப்படிகளை மட்டும் வைத்துக் கொள்கிறோம்.

நடைமுறை அல்காரிதம்

ஒவ்வொரு வீடியோவிற்கும் நாம்:

  1. ஒரு சீரான ரேண்டம் எண்ணை u ∈ (0, 1) என எடுக்கவும்.
  2. ஒரு கீயை k = u^(1/weight) என கணக்கிடவும்.
    (எடை அதிகமாக இருந்தால், எதிர்பார்க்கப்படும் கீயும் அதிகமாக இருக்கும்.)
  3. தற்போதைய முதல் k கீகளைச் சேமிக்கும் ஒரு min-heap-இல் அந்த உருப்படியைச் சேர்க்கவும்.
    ஒருவேளை heap-இன் அளவு k-ஐத் தாண்டினால், மிகச்சிறிய கீயை நீக்கிவிடவும்.

தரவு ஓட்டம் முடிந்ததும், நாம் காண்பிக்க வேண்டிய 24 வீடியோக்கள் அந்த heap-இல் இருக்கும்.

மிதப்புப் புள்ளி (floating-point) வரம்புகளைக் கையாளுதல்

ஒரு வீடியோவின் எடை மிக அதிகமாக இருக்கும்போது, double-precision கணக்கீட்டில் u^(1/weight) என்பது 1.0-லிருந்து வேறுபடுத்த முடியாத ஒரு மதிப்பிற்குச் சுருங்கிவிடும். இதனால் அதிக எடை கொண்ட பல உருப்படிகள் ஒரே மாதிரியான கீயைப் பெற்று, அதன் ரேண்டம் தன்மையை இழக்கின்றன. இதற்குத் தீர்வு 'log space'-இல் செயல்படுவதுதான்:

  • அடுக்குத் தொடருக்குப் பதிலாக log_key = log(u) / weight என கணக்கிடவும்.

லாக்ரிதம்கள் (logarithms) அடுக்குச் செயல்பாட்டைப் பெருக்கலாக மாற்றுவதால், துல்லியத்தன்மை குறைவதைத் தவிர்ப்பதுடன், கீகளின் வரிசையும் மாறாமல் பாதுகாக்கப்படுகிறது. இந்த கணக்கீட்டிற்கு கூடுதல் செலவு ஏதும் இல்லை.

செயல்படுத்தும் சரிபார்ப்புப் பட்டியல்

  • தரவு அமைப்பு (Data structure): அளவு k கொண்ட ஒரு min-heap (priority queue), மிகப்பெரிய கீகளைத் திறம்பட வைத்திருக்கும் (ஒவ்வொரு சேர்க்கைக்கும் O(log k)).
  • எண் வகை (Numeric type): u மற்றும் log-அடிப்படையிலான கீகளுக்கு 64-bit மிதப்புப் புள்ளி எண்களைப் பயன்படுத்தவும்; இவை பொதுவான எடை வரம்புகளுக்குப் போதுமான துல்லியத்தை வழங்கும்.
  • புள்ளிவிவரச் சரிபார்ப்பு (Statistical sanity check): ஒரு சிறிய மாதிரித் தொகுப்பில் (sample set) விரைவான Monte-Carlo சோதனையைச் செய்யவும். எடை 10 கொண்ட உருப்படிகள், எடை 1 கொண்ட உருப்படிகளை விட ஏறத்தாழ பத்து மடங்கு அடிக்கடி தோன்றினால், செயல்படுத்தல் சரியானது என்று அர்த்தம்.
  • ஒற்றை-முறை தரவு ஓட்டம் (Single-pass streaming): அல்காரிதத்திற்குத் தேவையான மொத்த உருப்படிகளின் எண்ணிக்கை முன்னரே தெரிய வேண்டிய அவசியமில்லை, இது வரிசைகளை ஒவ்வொன்றாக வழங்கும் எங்களது SQLite cursor-உடன் இயல்பாகப் பொருந்துகிறது.

சுருக்கம்

Weighted reservoir sampling ஒரு வீடியோ பரிந்துரைச் சேவையை அதன் முகப்புப் பக்கத்தைப் புத்துணர்ச்சியுடன் வைத்திருக்கவும், பொருத்தத் தன்மையின் மதிப்புகளை (relevance scores) மதிக்கவும் மற்றும் நினைவகப் பயன்பாட்டைக் குறைவாக வைத்திருக்கவும் அனுமதிக்கிறது—இவை அனைத்தும் பல்லாயிரக்கணக்கான உருப்படிகளை ஒரே ஒரு முறை ஆய்வு செய்வதன் மூலம் சாத்தியமாகிறது. கீ கணக்கீட்டை log space-க்கு மாற்றுவதன் மூலமும், min-heap பயன்படுத்துவதன் மூலமும், இந்த முறை துல்லியமாகவும் மற்றும் திறமையாகவும் (performant) உள்ளது.