Тепер наша головна сторінка з відео щоразу після оновлення показує новий набір із 24 рекомендацій завдяки переходу на зважену резервуарну вибірку (weighted reservoir sampling, A-Res). Ця зміна усунула проблему «вічної сітки», яка була характерною для нашої попередньої стрічки, відсортованої за балами.

Чому старий підхід псував враження від користування

Кожні дві години ми збираємо останні трендові відео з восьми регіонів і записуємо результати в таблицю SQLite. Наївним рішенням було відсортувати весь набір за показником релевантності та взяти топ-24. Цей метод гарантує появу елементів із найвищими балами, але він також гарантує, що вони залишатимуться там назавжди. Один вірусний ролик може домінувати на першій позиції днями, і користувачі бачитимуть ідентичну сітку щоразу, коли оновлюють сторінку.

Окрім того, що контент стає неактуальним, сортування всієї таблиці для кожного запиту змушує SQLite завантажувати велику тимчасову структуру в пам'ять, що є неефективним використанням ресурсів.

Що нам дає зважена резервуарна вибірка

Зважена резервуарна вибірка вирішує дві проблеми одночасно:

  1. Свіжість із урахуванням ваги — шанс вибору кожного відео пропорційний його вазі (наприклад, балу релевантності). Відео з удвічі більшою вагою має вдвічі вищий шанс з'явитися, але жоден елемент не має гарантованого місця.
  2. Ефективність використання пам'яті — алгоритм зберігає лише «резервуар» фіксованого розміру з $k$ елементів ($k = 24$ для нашої стрічки). Він обробляє потік за один прохід, тому використання пам'яті залишається на рівні $O(k)$ незалежно від кількості кандидатів.

Основна ідея проста. Під час сканування вхідних рядків ми присвоюємо кожному елементу випадковий ключ, який враховує його вагу, а потім залишаємо $k$ елементів із найбільшими ключами.

Алгоритм на практиці

Для кожного відео ми:

  1. Генеруємо рівномірне випадкове число $u \in (0, 1)$.
  2. Обчислюємо ключ $k = u^{1/\text{weight}}$.
    (Чим вища вага, тим більшим є очікуваний ключ.)
  3. Вставляємо елемент у min-heap (мінімальну купу), яка зберігає поточні $k$ найбільших ключів.
    Якщо розмір купи перевищує $k$, ми видаляємо найменший ключ.

Коли потік завершується, купа містить 24 відео, які ми відобразимо.

Робота з обмеженнями чисел із плаваючою комою

Коли вага відео дуже велика, $u^{1/\text{weight}}$ зводиться до значення, яке в арифметиці з подвійною точністю неможливо відрізнити від $1.0$. Це призводить до того, що багато «важких» елементів отримують однаковий ключ, і випадковість втрачається. Вихід — працювати в логарифмічному просторі:

  • Обчислюємо $\text{log_key} = \log(u) / \text{weight}$ замість виразу зі степенем.

Оскільки логарифми перетворюють піднесення до степеня на множення, порядок ключів зберігається, а «прірва точності» уникається. Ці обчислення практично не потребують додаткових ресурсів.

Контрольний список для впровадження

  • Структура даних: min-heap (черга з пріоритетом) розміром $k$ ефективно зберігає найбільші ключі ($O(\log k)$ на кожну вставку).
  • Числовий тип: використовуйте 64-бітні числа з плаваючою комою для $u$ та ключів на основі логарифмів; вони забезпечують достатню точність для типових діапазонів ваг.
  • Статистична перевірка: проведіть швидкий тест Монте-Карло на невеликій вибірці. Якщо елементи з вагою 10 з'являються приблизно в десять разів частіше, ніж елементи з вагою 1, то реалізація правильна.
  • Потокова обробка за один прохід: алгоритму не потрібно знати загальну кількість кандидатів заздалегідь, що ідеально підходить для нашого курсору SQLite, який видає рядки по одному.

Підсумок

Зважена резервуарна вибірка дозволяє сервісу рекомендацій відео підтримувати свіжість головної сторінки, враховувати показники релевантності та не перевантажувати пам'ять — і все це за один прохід по десятках тисяч кандидатів. Перенесення обчислення ключів у логарифмічний простір та використання min-heap дозволяють методу залишатися точним і продуктивним.