വെയിറ്റഡ് റിസർവോയർ സാമ്പിളിംഗിലേക്ക് (weighted reservoir sampling - A-Res) മാറിയതിലൂടെ, ഞങ്ങളുടെ വീഡിയോ ഹോംപേജിൽ ഓരോ തവണ റിഫ്രഷ് ചെയ്യുമ്പോഴും പുതിയ 24 ശുപാർശകൾ (recommendations) കാണിക്കുന്നു. മുൻപ് സ്കോർ അടിസ്ഥാനമാക്കി ക്രമീകരിച്ചിരുന്ന ഫീഡിൽ ഉണ്ടായിരുന്ന “എപ്പോഴും ഒരേ ഗ്രിഡ്” (same-grid-forever) എന്ന പ്രശ്നം ഈ മാറ്റത്തിലൂടെ പരിഹരിക്കപ്പെട്ടു.
പഴയ രീതി അനുഭവം തകരാൻ കാരണമായത് എന്തുകൊണ്ട്
ഓരോ രണ്ട് മണിക്കൂർ കൂടുമ്പോഴും ഞങ്ങൾ എട്ട് റീജിയനുകളിൽ നിന്നുള്ള ഏറ്റവും പുതിയ ട്രെൻഡിംഗ് വീഡിയോകൾ ശേഖരിക്കുകയും അവ ഒരു SQLite ടേബിളിലേക്ക് മാറ്റുകയും ചെയ്യുന്നു. മുഴുവൻ സെറ്റും ഒരു റിലവൻസ് സ്കോർ (relevance score) ഉപയോഗിച്ച് ക്രമീകരിക്കുകയും അതിൽ നിന്ന് ആദ്യത്തെ 24 എണ്ണം എടുക്കുകയും ചെയ്യുക എന്നതായിരുന്നു ലളിതമായ പരിഹാരം. ഈ രീതി ഉയർന്ന സ്കോറുള്ളവ വരുന്നുണ്ടെന്ന് ഉറപ്പാക്കുന്നുണ്ടെങ്കിലും, അവ അവിടെത്തന്നെ തുടരുന്നുവെന്നും ഇത് ഉറപ്പാക്കുന്നു. ഒരു വൈറൽ വീഡിയോ ദിവസങ്ങളോളം ഒന്നാം സ്ഥാനത്ത് തന്നെ തുടരാൻ ഇത് കാരണമാവുകയും, ഉപയോക്താക്കൾ ഓരോ തവണ റീലോഡ് ചെയ്യുമ്പോഴും ഒരേ ഗ്രിഡ് തന്നെ കാണേണ്ടി വരികയും ചെയ്യുന്നു.
ആവർത്തന സ്വഭാവമുള്ള ഈ അനുഭവം കൂടാതെ, ഓരോ റിക്വസ്റ്റിനും മുഴുവൻ ടേബിളും സോർട്ട് ചെയ്യുന്നത് SQLite വലിയൊരു താൽക്കാലിക ഘടന മെമ്മറിയിലേക്ക് ലോഡ് ചെയ്യാൻ നിർബന്ധിതമാക്കുന്നു, ഇത് വിഭവങ്ങളുടെ പാഴാക്കലിന് കാരണമാകുന്നു.
വെയിറ്റഡ് റിസർവോയർ സാമ്പിളിംഗ് നമുക്ക് നൽകുന്നത് എന്താണ്
വെയിറ്റഡ് റിസർവോയർ സാമ്പിളിംഗ് രണ്ട് പ്രശ്നങ്ങൾ ഒരേസമയം പരിഹരിക്കുന്നു:
- ബയസ് ഉള്ള പുതുമ (Freshness with bias) – ഓരോ വീഡിയോയും തിരഞ്ഞെടുക്കപ്പെടാനുള്ള സാധ്യത അതിന്റെ വെയിറ്റിന് (ഉദാഹരണത്തിന്, റിലവൻസ് സ്കോർ) ആനുപാതികമാണ്. ഇരട്ടി വെയിറ്റുള്ള ഒരു വീഡിയോ തിരഞ്ഞെടുക്കപ്പെടാൻ ഇരട്ടി സാധ്യതയുണ്ട്, എന്നാൽ ഒരു ഐറ്റത്തിനും സ്ഥാനം ഉറപ്പില്ല.
- മെമ്മറി കാര്യക്ഷമത (Memory efficiency) – ഈ അൽഗോരിതം k എണ്ണമുള്ള (ഞങ്ങളുടെ ഫീഡിന് k = 24) ഒരു നിശ്ചിത വലുപ്പമുള്ള “റിസർവോയർ” (reservoir) മാത്രമേ സൂക്ഷിക്കുന്നുള്ളൂ. ഇത് ഡാറ്റാ സ്ട്രീമിനെ ഒറ്റ പാസ്സിലൂടെ (single pass) പ്രോസസ്സ് ചെയ്യുന്നു, അതിനാൽ എത്ര കാൻഡിഡേറ്റുകൾ വന്നാലും മെമ്മറി ഉപയോഗം O(k) ആയി നിലനിൽക്കുന്നു.
ഇതിന്റെ അടിസ്ഥാന ആശയം ലളിതമാണ്. വരുന്ന വരികൾ (rows) പരിശോധിക്കുമ്പോൾ, ഓരോ ഐറ്റത്തിനും അതിന്റെ വെയിറ്റ് ഉൾക്കൊള്ളുന്ന ഒരു റാൻഡം കീ (random key) നൽകുന്നു, തുടർന്ന് ഏറ്റവും ഉയർന്ന കീകളുള്ള k ഐറ്റങ്ങളെ മാത്രം നിലനിർത്തുന്നു.
പ്രായോഗികമായ അൽഗോരിതം
ഓരോ വീഡിയോയ്ക്കും ഞങ്ങൾ ചെയ്യുന്നത്:
- ഒരു യൂണിഫോം റാൻഡം നമ്പർ
u ∈ (0, 1)എടുക്കുന്നു. - ഒരു കീ
k = u^(1/weight)കണക്കാക്കുന്നു.
(വെയിറ്റ് കൂടുന്തോറും കീയുടെ മൂല്യം കൂടാൻ സാധ്യതയുണ്ട്.) - നിലവിലെ ഏറ്റവും ഉയർന്ന k കീകൾ സൂക്ഷിക്കുന്ന ഒരു മിൻ-ഹീപ്പിലേക്ക് (min-heap) ഐറ്റം ചേർക്കുന്നു.
ഹീപ്പിന്റെ വലിപ്പം k കവിയുകയാണെങ്കിൽ, ഏറ്റവും ചെറിയ കീ ഒഴിവാക്കുന്നു.
സ്ട്രീം അവസാനിക്കുമ്പോൾ, ഞങ്ങൾ പ്രദർശിപ്പിക്കേണ്ട 24 വീഡിയോകൾ ഹീപ്പിൽ ഉണ്ടാകും.
ഫ്ലോട്ടിംഗ്-പോയിന്റ് പരിമിതികൾ കൈകാര്യം ചെയ്യുമ്പോൾ
ഒരു വീഡിയോയുടെ വെയിറ്റ് വളരെ വലുതാകുമ്പോൾ, ഡബിൾ-പ്രസിഷൻ അരിത്മെറ്റിക് (double-precision arithmetic) അനുസരിച്ച് u^(1/weight) എന്നത് 1.0-ൽ നിന്ന് തിരിച്ചറിയാൻ കഴിയാത്ത വിധം മാറുന്നു. ഇത് ഉയർന്ന വെയിറ്റുള്ള പല ഐറ്റങ്ങളും ഒരേ കീ പങ്കിടാനും റാൻഡംനെസ്സ് നഷ്ടപ്പെടാനും കാരണമാകുന്നു. ഇതിനുള്ള പരിഹാരം ലോഗ് സ്പേസിൽ (log space) പ്രവർത്തിക്കുക എന്നതാണ്:
- പവർ എക്സ്പ്രഷന് പകരം
log_key = log(u) / weightകണക്കാക്കുക.
ലോഗരിതം എക്സ്പോണൻഷ്യേഷനെ ഗുണനമാക്കി മാറ്റുന്നതിനാൽ, പ്രിസിഷൻ നഷ്ടപ്പെടാതെ തന്നെ കീകുകളുടെ ക്രമം നിലനിർത്താൻ സാധിക്കുന്നു. ഈ കണക്കുകൂട്ടലിന് അധികമായി വലിയ ചിലവൊന്നുമില്ല.
ഇംപ്ലിമെന്റേഷൻ ചെക്ക്ലിസ്റ്റ്
- ഡാറ്റാ സ്ട്രക്ചർ (Data structure): k വലിപ്പമുള്ള ഒരു മിൻ-ഹീപ്പ് (min-heap/priority queue) ഏറ്റവും വലിയ കീകൾ കാര്യക്ഷമമായി സൂക്ഷിക്കുന്നു (ഓരോ ഇൻസെർഷനും O(log k)).
- ന്യൂമെറിക് ടൈപ്പ് (Numeric type):
u-വിനും ലോഗ് അധിഷ്ഠിത കീകൾക്കുമായി 64-ബിറ്റ് ഫ്ലോട്ടിംഗ്-പോയിന്റ് നമ്പറുകൾ ഉപയോഗിക്കുക; ഇവ സാധാരണ വെയിറ്റ് പരിധികളിൽ ആവശ്യമായ പ്രിസിഷൻ നൽകുന്നു. - സ്റ്റാറ്റിസ്റ്റിക്കൽ സാനിറ്റി ചെക്ക് (Statistical sanity check): ഒരു ചെറിയ സാമ്പിൾ സെറ്റിൽ വേഗത്തിലുള്ള ഒരു മോണ്ടെ-കാർലോ ടെസ്റ്റ് (Monte-Carlo test) നടത്തുക. വെയിറ്റ് 10 ഉള്ള ഐറ്റങ്ങൾ വെയിറ്റ് 1 ഉള്ളവയെ അപേക്ഷിച്ച് ഏകദേശം പത്തിരട്ടി തവണ പ്രത്യക്ഷപ്പെടുന്നുണ്ടെങ്കിൽ ഇംപ്ലിമെന്റേഷൻ ശരിയാണ്.
- സിംഗിൾ-പാസ് സ്ട്രീമിംഗ് (Single-pass streaming): അൽഗോരിത്തിന് കാൻഡിഡേറ്റുകളുടെ ആകെ എണ്ണം മുൻകൂട്ടി അറിയേണ്ടതില്ല, ഇത് ഓരോ വരികളായി നൽകുന്ന ഞങ്ങളുടെ SQLite കർസറുമായി (cursor) സ്വാഭാവികമായി യോജിക്കുന്നു.
ചുരുക്കത്തിൽ
വെയിറ്റഡ് റിസർവോയർ സാമ്പിളിംഗ് ഉപയോഗിക്കുന്നതിലൂടെ ഒരു വീഡിയോ റെക്കമെൻഡേഷൻ സർവീസിന് അതിന്റെ ഹോംപേജ് പുതുമയോടെ നിലനിർത്താനും, റിലവൻസ് സ്കോറുകൾ മാനിക്കാനും, മെമ്മറി ഉപയോഗം കുറയ്ക്കാനും സാധിക്കുന്നു—ഇതെല്ലാം പതിനായിരക്കണക്കിന് കാൻഡിഡേറ്റുകളെ ഒറ്റ പാസ്സിലൂടെ പരിശോധിച്ചുകൊണ്ട് തന്നെ ചെയ്യാം. കീ കണക്കുകൂട്ടൽ ലോഗ് സ്പേസിലേക്ക് മാറ്റുന്നതിലൂടെയും മിൻ-ഹീപ്പ് ഉപയോഗിക്കുന്നതിലൂടെയും ഈ രീതി കൃത്യതയും മികച്ച പ്രകടനവും (performance) ഉറപ്പാക്കുന്നു.