వెయిటెడ్ రిజర్వాయర్ శాంప్లింగ్ (A-Res) కి మారడం వల్ల, మా వీడియో హోమ్పేజీ ఇప్పుడు ప్రతి రిఫ్రెష్పై 24 కొత్త సిఫార్సులను (recommendations) చూపుతోంది. ఈ మార్పు వల్ల మా పాత స్కోర్-సార్టెడ్ ఫీడ్లో ఉన్న “ఎప్పుడూ ఒకే గ్రిడ్” (same-grid-forever) సమస్య తొలగిపోయింది.
పాత విధానం ఎందుకు అనుభవాన్ని దెబ్బతీసింది
ప్రతి రెండు గంటలకు ఒకసారి మేము ఎనిమిది ప్రాంతాల నుండి తాజా ట్రెండింగ్ వీడియోలను సేకరించి, ఆ ఫలితాలను SQLite టేబుల్లోకి పంపిస్తాము. మొత్తం సెట్ను రిలెవెన్స్ స్కోర్ (relevance score) ఆధారంగా సార్ట్ చేసి, మొదటి 24 వీడియోలను తీసుకోవడం అనేది ఒక సాధారణ పరిష్కారం. ఆ పద్ధతి వల్ల అత్యధిక స్కోరు ఉన్న అంశాలు కనిపిస్తాయన్నది నిజమే, కానీ అవి అక్కడే ఉండిపోతాయని కూడా అది నిర్ధారిస్తుంది. ఒకే ఒక వైరల్ క్లిప్ రోజుల తరబడి మొదటి స్థానాన్ని ఆక్రమించవచ్చు, దీనివల్ల యూజర్లు ప్రతిసారి పేజీని రీలోడ్ చేసినప్పుడు ఒకే రకమైన గ్రిడ్ను చూస్తారు.
పాతబడిన అనుభవం (stale experience) మాత్రమే కాకుండా, ప్రతి రిక్వెస్ట్ కోసం మొత్తం టేబుల్ను సార్ట్ చేయడం వల్ల SQLite మెమరీలోకి ఒక పెద్ద తాత్కాలిక నిర్మాణాన్ని (temporary structure) లోడ్ చేయాల్సి వస్తుంది, ఇది వృధా అవుతుంది.
వెయిటెడ్ రిజర్వాయర్ శాంప్లింగ్ వల్ల కలిగే ప్రయోజనాలు
వెయిటెడ్ రిజర్వాయర్ శాంప్లింగ్ రెండు సమస్యలను ఒకేసారి పరిష్కరిస్తుంది:
- బయాస్తో కూడిన ఫ్రెష్నెస్ (Freshness with bias) – ప్రతి వీడియో ఎంపికయ్యే అవకాశం దాని వెయిట్ (ఉదాహరణకు, రిలెవెన్స్ స్కోర్) కి అనుగుణంగా ఉంటుంది. రెట్టింపు వెయిట్ ఉన్న వీడియో కనిపించే అవకాశం రెట్టింపు ఉంటుంది, కానీ ఏ అంశానికైనా స్థానం ఖచ్చితంగా ఉంటుందని చెప్పలేము.
- మెమరీ సామర్థ్యం (Memory efficiency) – ఈ అల్గారిథమ్ కేవలం k అంశాల యొక్క నిర్ణీత పరిమాణం కలిగిన “రిజర్వాయర్”ను మాత్రమే ఉంచుతుంది (మా ఫీడ్ కోసం k = 24). ఇది స్ట్రీమ్ను ఒకే పాస్లో ప్రాసెస్ చేస్తుంది, కాబట్టి ఎన్ని అభ్యర్థులు (candidates) వచ్చినా మెమరీ O(k) గానే ఉంటుంది.
దీని ప్రధాన ఉద్దేశ్యం సరళమైనది. వచ్చే రోస్ను (rows) స్కాన్ చేస్తున్నప్పుడు, మేము ప్రతి అంశానికి దాని వెయిట్ను కలిపి ఒక రాండమ్ కీని (random key) కేటాయిస్తాము, ఆపై అత్యధిక కీలు ఉన్న k అంశాలను ఉంచుతాము.
ఆచరణలో అల్గారిథమ్
ప్రతి వీడియో కోసం మేము:
- ఒక యూనిఫాం రాండమ్ నంబర్ను u ∈ (0, 1) నుండి తీసుకుంటాము.
- కీ k = u^(1/weight) ను లెక్కిస్తాము.
(వెయిట్ ఎంత ఎక్కువగా ఉంటే, ఆశించిన కీ అంత పెద్దదిగా ఉంటుంది.) - ప్రస్తుత టాప్ k కీలను నిల్వ చేసే min-heap లో ఆ అంశాన్ని చేరుస్తాము.
ఒకవేళ హీప్ పరిమాణం k కంటే ఎక్కువైతే, మేము అతి చిన్న కీని తొలగిస్తాము.
స్ట్రీమ్ ముగిసినప్పుడు, మేము ప్రదర్శించబోయే 24 వీడియోలు ఆ హీప్లో ఉంటాయి.
ఫ్లోటింగ్-పాయింట్ పరిమితులను ఎదుర్కోవడం
ఒక వీడియో వెయిట్ చాలా ఎక్కువగా ఉన్నప్పుడు, u^(1/weight) అనేది డబుల్-ప్రిసిషన్ అరిథమెటిక్లో 1.0 నుండి వేరు చేయలేనంత విలువకు చేరుకుంటుంది, దీనివల్ల అనేక భారీ అంశాలు ఒకే కీని కలిగి ఉండి రాండమ్నెస్ కోల్పోతాయి. దీనికి పరిష్కారం లాగ్ స్పేస్ (log space) లో పనిచేయడం:
- పవర్ ఎక్స్ప్రెషన్కు బదులుగా log_key = log(u) / weight ను లెక్కిస్తాము.
లాగరిథమ్స్ ఎక్స్పోనెన్సియేషన్ను మల్టిప్లికేషన్గా మారుస్తాయి కాబట్టి, ప్రిసిషన్ సమస్యలను నివారించడమే కాకుండా కీల క్రమం (ordering) కూడా దెబ్బతినదు. ఈ గణన వల్ల అదనపు ఖర్చు ఏమీ ఉండదు.
ఇంప్లిమెంటేషన్ చెక్లిస్ట్
- డేటా స్ట్రక్చర్ (Data structure): k పరిమాణం కలిగిన min-heap (priority queue) అతిపెద్ద కీలను సమర్థవంతంగా ఉంచుతుంది (ప్రతి ఇన్సర్షన్కు O(log k)).
- న్యూమరిక్ టైప్ (Numeric type): u మరియు లాగ్-ఆధారిత కీల కోసం 64-బిట్ ఫ్లోటింగ్-పాయింట్ నంబర్లను ఉపయోగించండి; ఇవి సాధారణ వెయిట్ రేంజ్లకు తగినంత ప్రిసిషన్ను అందిస్తాయి.
- స్టాటిస్టికల్ శానిటీ చెక్ (Statistical sanity check): చిన్న శాంపిల్ సెట్పై త్వరిత మోంటే-కార్లో (Monte-Carlo) పరీక్షను నిర్వహించండి. వెయిట్ 10 ఉన్న అంశాలు, వెయిట్ 1 ఉన్న అంశాల కంటే సుమారు పది రెట్లు ఎక్కువగా కనిపిస్తే, ఇంప్లిమెంటేషన్ సరిగ్గా ఉన్నట్లు లెక్క.
- సింగిల్-పాస్ స్ట్రీమింగ్ (Single-pass streaming): అల్గారిథమ్కు అభ్యర్థుల మొత్తం సంఖ్య ముందుగానే తెలియాల్సిన అవసరం లేదు, ఇది ఒక్కొక్క రోను ఇచ్చే మా SQLite కర్సర్తో సహజంగా సరిపోతుంది.
ముఖ్య అంశం (Takeaway)
వెయిటెడ్ రిజర్వాయర్ శాంప్లింగ్ వల్ల వీడియో రికమెండేషన్ సర్వీస్ తన హోమ్పేజీని ఫ్రెష్గా ఉంచుకోవచ్చు, రిలెవెన్స్ స్కోర్లను గౌరవించవచ్చు మరియు మెమరీ వినియోగాన్ని తక్కువగా ఉంచుకోవచ్చు—ఇవన్నీ వేల సంఖ్యలో ఉన్న అభ్యర్థులపై ఒకే ఒక పాస్ ద్వారా సాధ్యమవుతాయి. కీ గణనను లాగ్ స్పేస్లోకి మార్చడం మరియు min-heap ఉపయోగించడం ద్వారా, ఈ పద్ధతి ఖచ్చితంగా మరియు సమర్థవంతంగా పనిచేస్తుంది.