Beranda video kami kini menampilkan set baru berisi 24 rekomendasi setiap kali halaman dimuat ulang, berkat peralihan ke weighted reservoir sampling (A-Res). Perubahan ini menghilangkan masalah “grid yang itu-itu saja” yang menghantui umpan (feed) berbasis pengurutan skor kami sebelumnya.

Mengapa pendekatan lama merusak pengalaman pengguna

Setiap dua jam, kami mengambil video tren terbaru dari delapan wilayah dan memasukkan hasilnya ke dalam tabel SQLite. Solusi naifnya adalah mengurutkan seluruh set—berdasarkan skor relevansi—dan mengambil 24 teratas. Metode tersebut menjamin item dengan skor tertinggi akan muncul, tetapi juga menjamin item tersebut akan terus berada di sana. Satu klip viral dapat mendominasi posisi 1 selama berhari-hari, dan pengguna melihat grid yang identik setiap kali mereka memuat ulang halaman.

Selain pengalaman yang membosankan, mengurutkan seluruh tabel untuk setiap permintaan memaksa SQLite memuat struktur sementara yang besar ke dalam memori, yang mana sangat boros.

Apa yang diberikan oleh weighted reservoir sampling kepada kita

Weighted reservoir sampling menyelesaikan dua masalah sekaligus:

  1. Kesegaran dengan bias – peluang setiap video untuk dipilih sebanding dengan bobotnya (misalnya, skor relevansi). Video dengan bobot dua kali lipat memiliki kemungkinan dua kali lebih besar untuk muncul, tetapi tidak ada item yang dijamin mendapatkan tempat.
  2. Efisiensi memori – algoritma ini hanya menyimpan “reservoir” berukuran tetap sebanyak k item (k = 24 untuk umpan kami). Algoritma ini memproses aliran data dalam satu kali jalan (single pass), sehingga penggunaan memori tetap O(k) tidak peduli berapa banyak kandidat yang masuk.

Ide utamanya sederhana. Saat kami memindai baris-baris yang masuk, kami menetapkan kunci acak pada setiap item yang menggabungkan bobotnya, lalu mempertahankan k item dengan kunci tertinggi.

Algoritma dalam praktiknya

Untuk setiap video, kita:

  1. Mengambil angka acak seragam u ∈ (0, 1).
  2. Menghitung kunci k = u^(1/weight).
    (Semakin tinggi bobotnya, semakin besar kunci yang diharapkan.)
  3. Memasukkan item ke dalam min-heap yang menyimpan k kunci teratas saat ini.
    Jika heap melebihi ukuran k, kita buang kunci terkecil.

Ketika aliran data berakhir, heap tersebut berisi 24 video yang akan kami tampilkan.

Menangani batasan floating-point

Ketika bobot video sangat besar, u^(1/weight) menyusut menjadi nilai yang tidak dapat dibedakan dari 1.0 dalam aritmetika presisi ganda (double-precision), menyebabkan banyak item dengan bobot besar berbagi kunci yang sama dan kehilangan keacakan. Solusinya adalah bekerja dalam ruang log (log space):

  • Hitung log_key = log(u) / weight alih-alih menggunakan ekspresi pangkat.

Karena logaritma mengubah eksponensial menjadi perkalian, urutan kunci tetap terjaga sambil menghindari penurunan presisi yang drastis. Perhitungannya hampir tidak memerlukan biaya tambahan.

Daftar periksa implementasi

  • Struktur data: sebuah min-heap (priority queue) berukuran k menyimpan kunci terbesar secara efisien (O(log k) per penyisipan).
  • Tipe numerik: gunakan angka floating-point 64-bit untuk u dan kunci berbasis log; angka tersebut memberikan presisi yang cukup untuk rentang bobot tipikal.
  • Pemeriksaan kewarasan statistik: jalankan tes Monte-Carlo cepat pada set sampel kecil. Jika item dengan bobot 10 muncul kira-kira sepuluh kali lebih sering daripada bobot 1, maka implementasinya sudah benar.
  • Streaming satu kali jalan (single-pass): algoritma ini tidak perlu mengetahui jumlah total kandidat sebelumnya, yang sangat cocok dengan kursor SQLite kami yang menghasilkan baris satu per satu.

Kesimpulan

Weighted reservoir sampling memungkinkan layanan rekomendasi video menjaga kesegaran berandanya, menghormati skor relevansi, dan tetap hemat memori—semuanya hanya dengan satu kali jalan melalui puluhan ribu kandidat. Dengan memindahkan perhitungan kunci ke dalam ruang log dan menggunakan min-heap, metode ini tetap presisi sekaligus berperforma tinggi.