আমাদের ভিডিও হোমপেজ এখন প্রতিবার রিফ্রেশ করার সময় ২৪টি নতুন সুপারিশ (recommendations) দেখায়, যার কারণ হলো আমরা weighted reservoir sampling (A-Res)-এ স্থানান্তরিত হয়েছি। এই পরিবর্তনের ফলে “সবসময় একই গ্রিড” (same-grid-forever) সমস্যাটি দূর হয়েছে, যা আমাদের আগের স্কোর-ভিত্তিক ফিডে দেখা যেত।

কেন পুরনো পদ্ধতিটি অভিজ্ঞতা নষ্ট করছিল

প্রতি দুই ঘণ্টা অন্তর আমরা আটটি অঞ্চল থেকে সর্বশেষ ট্রেন্ডিং ভিডিওগুলো সংগ্রহ করি এবং ফলাফলগুলো একটি SQLite টেবিলে জমা করি। সহজ সমাধান ছিল পুরো সেটটিকে একটি রেলিভেন্স স্কোর (relevance score) অনুযায়ী সাজানো এবং ওপরের ২৪টি ভিডিও নেওয়া। এই পদ্ধতিটি নিশ্চিত করে যে সর্বোচ্চ স্কোরযুক্ত আইটেমগুলো প্রদর্শিত হবে, কিন্তু এটি এটাও নিশ্চিত করে যে সেগুলো সেখানেই থেকে যাবে। একটি মাত্র ভাইরাল ক্লিপ কয়েক দিন ধরে ১ নম্বর পজিশন দখল করে রাখতে পারে, ফলে ব্যবহারকারীরা প্রতিবার রিলোড করার সময় একই গ্রিড দেখতে পান।

একঘেয়ে অভিজ্ঞতার পাশাপাশি, প্রতিটি রিকোয়েস্টের জন্য পুরো টেবিলটি সর্ট করতে হলে SQLite-কে মেমরিতে একটি বড় অস্থায়ী স্ট্রাকচার লোড করতে হয়, যা অত্যন্ত অপচয়মূলক।

Weighted reservoir sampling আমাদের কী সুবিধা দেয়

Weighted reservoir sampling একসাথে দুটি সমস্যার সমাধান করে:

১. পক্ষপাতসহ সতেজতা (Freshness with bias) – প্রতিটি ভিডিও নির্বাচিত হওয়ার সম্ভাবনা তার ওয়েট (weight) বা ওজনের (যেমন: রেলিভেন্স স্কোর) সমানুপাতিক। যে ভিডিওর ওয়েট দ্বিগুণ, তার প্রদর্শিত হওয়ার সম্ভাবনাও দ্বিগুণ, তবে কোনো আইটেমের জন্য নির্দিষ্ট জায়গা নিশ্চিত নয়। ২. মেমরি দক্ষতা (Memory efficiency) – এই অ্যালগরিদমটি শুধুমাত্র k সংখ্যক আইটেমের একটি নির্দিষ্ট আকারের “রিজার্ভার” (reservoir) বজায় রাখে (আমাদের ফিডের জন্য k = ২৪)। এটি একটি মাত্র পাসে (single pass) স্ট্রিমটি প্রসেস করে, তাই কতগুলো ক্যান্ডিডেট আসুক না কেন, মেমরি খরচ O(k) হিসেবেই থাকে।

মূল ধারণাটি সহজ। আমরা যখন ইনকামিং রো (rows) গুলো স্ক্যান করি, তখন প্রতিটি আইটেমকে একটি র‍্যান্ডম কী (random key) প্রদান করি যা তার ওয়েটকে অন্তর্ভুক্ত করে, তারপর সর্বোচ্চ কী সম্পন্ন k সংখ্যক আইটেম সংরক্ষণ করি।

ব্যবহারিক প্রয়োগে অ্যালগরিদমটি

প্রতিটি ভিডিওর জন্য আমরা:

১. একটি ইউনিফর্ম র‍্যান্ডম নম্বর u ∈ (0, 1) গ্রহণ করি। ২. একটি কী k = u^(1/weight) গণনা করি।
(ওয়েট যত বেশি হবে, প্রত্যাশিত কী-ও তত বড় হবে।) ৩. আইটেমটিকে একটি min-heap-এ প্রবেশ করাই যা বর্তমানের শীর্ষ k সংখ্যক কী সংরক্ষণ করে।
যদি heap-এর আকার k অতিক্রম করে, তবে আমরা ক্ষুদ্রতম কী-টি বাদ দিয়ে দিই।

যখন স্ট্রিম শেষ হয়, তখন heap-এ সেই ২৪টি ভিডিও থাকে যা আমরা প্রদর্শন করব।

ফ্লোটিং-পয়েন্ট লিমিটের সমস্যা সমাধান

যখন কোনো ভিডিওর ওয়েট অনেক বেশি হয়, তখন ডাবল-প্রিসিশন অ্যারিথমেটিকে u^(1/weight) এর মান ১.০ থেকে আলাদা করা অসম্ভব হয়ে পড়ে, যার ফলে অনেক ভারী আইটেম একই কী শেয়ার করে এবং র‍্যান্ডমনেস হারিয়ে ফেলে। এর সমাধান হলো লগ স্পেসে (log space) কাজ করা:

  • পাওয়ার এক্সপ্রেশনের পরিবর্তে log_key = log(u) / weight গণনা করি।

যেহেতু লগারিদম এক্সপোনেনশিয়েশনকে (exponentiation) গুণ আকারে রূপান্তরিত করে, তাই প্রিসিশন হারানোর ঝুঁকি ছাড়াই কী-গুলোর ক্রম বজায় থাকে। এই গণনায় অতিরিক্ত কোনো খরচ হয় না।

ইমপ্লিমেন্টেশন চেকলিস্ট

  • ডেটা স্ট্রাকচার: k আকারের একটি min-heap (priority queue) দক্ষতার সাথে বৃহত্তম কীগুলো বজায় রাখে (প্রতিটি ইনসার্শনের জন্য O(log k))।
  • নিউমেরিক টাইপ: u এবং লগ-ভিত্তিক কী-গুলোর জন্য 64-bit ফ্লোটিং-পয়েন্ট নম্বর ব্যবহার করুন; এগুলো সাধারণ ওয়েট রেঞ্জের জন্য পর্যাপ্ত প্রিসিশন প্রদান করে।
  • স্ট্যাটিস্টিক্যাল স্যানিটি চেক: একটি ছোট স্যাম্পল সেটের ওপর দ্রুত একটি Monte-Carlo টেস্ট চালান। যদি ওয়েট ১০-এর আইটেমগুলো ওয়েট ১-এর তুলনায় প্রায় দশ গুণ বেশিবার প্রদর্শিত হয়, তবে ইমপ্লিমেন্টেশনটি সঠিক।
  • সিঙ্গেল-পাস স্ট্রিমিং: অ্যালগরিদমটির আগে থেকে মোট ক্যান্ডিডেটের সংখ্যা জানার প্রয়োজন নেই, যা আমাদের SQLite কার্সারের সাথে সামঞ্জস্যপূর্ণ কারণ এটি একে একে রো (rows) প্রদান করে।

সারসংক্ষেপ

Weighted reservoir sampling একটি ভিডিও রিকমেন্ডেশন সার্ভিসকে তার হোমপেজ সতেজ রাখতে, রেলিভেন্স স্কোরকে সম্মান জানাতে এবং মেমরি খরচ কম রাখতে সাহায্য করে—তাও হাজার হাজার ক্যান্ডিডেটের ওপর মাত্র একটি পাসের মাধ্যমে। কী (key) গণনা লগ স্পেসে নিয়ে আসা এবং একটি min-heap ব্যবহারের মাধ্যমে এই পদ্ধতিটি নির্ভুল এবং পারফরম্যান্ট উভয়ই থাকে।