- Reservoir sampling adalah teknik yang unik dan efisien untuk mengambil sampel acak secara adil saat ukuran data tidak diketahui
- Teknik ini digunakan di berbagai bidang seperti pengumpulan log real-time karena dapat secara efisien menyelesaikan situasi yang tidak didukung oleh metode tradisional
- Ide intinya adalah memperbarui ruang penyimpanan dengan probabilitas 1/n setiap kali elemen baru muncul, sehingga semua elemen memiliki peluang yang sama untuk dipilih
- Saat memilih beberapa sampel, probabilitasnya diperluas menjadi k/n, lalu sampel yang sudah ada diganti secara acak sesuai probabilitas tersebut
- Algoritme ini menjamin sampling yang adil dengan penggunaan memori yang kecil, serta meningkatkan efisiensi dan keandalan pemrosesan real-time
Konsep dan Kebutuhan Reservoir Sampling
- Reservoir sampling adalah teknik yang efisien untuk mengekstrak sampel secara adil dari kumpulan data yang ukuran totalnya tidak diketahui
- Dalam kasus umum, jika ukuran data diketahui, memilih indeks acak adalah cara yang efektif, tetapi jika ukurannya tidak diketahui, metode seperti ini tidak dapat digunakan
- Pada data besar yang datang secara linear (misalnya stream log), penggunaan memori harus dibatasi, sambil tetap memastikan setiap data memiliki probabilitas yang sama untuk dipilih
Sampling Saat Ukuran Diketahui
- Pada himpunan berukuran terbatas (misalnya 10 kartu), metode shuffle dengan mengacak semua item lalu memilih sejumlah yang diinginkan dari depan cocok untuk menjamin keadilan
- Dengan memanfaatkan struktur array di komputer, kita dapat langsung memilih indeks acak untuk mengekstrak sampel dengan cepat
- Namun, untuk jutaan data atau stream dengan ukuran yang tidak diketahui, cara ini tidak efisien
Sampling Saat Ukuran Tidak Diketahui: Masalah dan Kebutuhan
- Di dunia nyata, sering ada situasi di mana data diterima satu per satu secara berurutan, hanya 1 item yang bisa disimpan, dan data yang sudah lewat tidak bisa diakses kembali
- Dalam sistem pengumpulan log, lonjakan trafik mendadak dapat terjadi, sehingga ada kebutuhan untuk hanya mengirim sebagian data melalui sampling guna mencegah server overload
- Memilih beberapa item pertama secara sembarang tidak memberi semua item peluang yang sama, sehingga menimbulkan masalah kurangnya keadilan
Prinsip Algoritme Reservoir Sampling
- Setiap kali data masuk, hitung jumlah n dari data yang telah diterima sejauh ini, lalu pilih data baru dengan probabilitas 1/n
- Data pertama selalu dipilih, lalu setiap data baru berikutnya menggantikan data lama dengan probabilitas yang makin kecil, sehingga probabilitas pemilihan yang sama tetap terjaga
- Hingga akhir, peluang bahwa data mana pun menjadi data yang tersimpan adalah seragam di seluruh populasi
- Ini bukan sekadar lempar koin, melainkan pendekatan dengan probabilitas 1/n untuk menjamin kesempatan yang adil bagi semua data
Intuisi Matematis (Penjelasan dengan Contoh Kartu)
- Data ke-1: pasti dipilih (probabilitas 1/1)
- Data ke-2: dipilih dengan probabilitas 1/2, sementara data lama hanya bertahan dengan probabilitas 50%
- Data ke-3: data baru dipilih dengan probabilitas 1/3, sedangkan peluang bertahan data lama terakumulasi sebesar nilai komplemennya
- Jika digeneralisasi, saat memasukkan hingga data ke-n, semua data selalu memiliki probabilitas 1/n
Perluasan untuk Memilih Beberapa Sampel (k-out-of-n)
- Untuk mengambil k sampel, data baru dipilih dengan probabilitas k/n, dan jika terpilih, satu item dari item yang saat ini tersimpan diganti secara acak
- Dengan cara ini juga, semua item yang tersimpan akan memiliki probabilitas yang sama untuk tetap menjadi sampel
- Dengan hanya menggunakan memori tetap (sebesar k), beberapa sampel dapat diambil secara adil bahkan dari stream data yang besar
Pemanfaatan Reservoir Sampling dalam Layanan Pengumpulan Log
- Dari log yang masuk setiap detik, hanya maksimum k buah (misalnya 5) yang dipilih dengan teknik reservoir sampling, lalu hanya sampel tersebut yang dikirim ke server
- Saat datanya sedikit, semua log akan terkirim tanpa kehilangan; bahkan saat trafik melonjak, jumlah pengiriman tidak akan melebihi k sehingga stabilitas layanan dapat dijamin
- Dengan mengirim sampel secara berkala, memang ada sedikit delay dalam real-time, tetapi secara keseluruhan hal ini membantu menjaga stabilitas dan efisiensi biaya
Aplikasi Tambahan dan Referensi
- Jika sebagian data (misalnya log error) lebih penting, kita bisa memakai variasi weighted reservoir sampling yang menerapkan bobot
- Konsep yang lebih mendalam tersedia di sumber eksternal seperti Wikipedia, tetapi prinsip dasarnya tetap menjaga keadilan
Kesimpulan
- Reservoir sampling adalah algoritme yang sangat elegan dan praktis untuk melakukan sampling secara adil dan efisien memori pada stream data dengan ukuran yang tidak diketahui
- Dalam pemrosesan data real-time, keunggulan seperti kecepatan, konsistensi, dan penggunaan sumber daya yang rendah membuatnya sangat bernilai di banyak bidang
1 komentar
Komentar Hacker News
Saat saya masih kecil dan tinggal di pedesaan, seorang teman ayah saya setiap tahun harus secara profesional mengukur populasi ptarmigan di pegunungan
Caranya dengan mengikuti rute yang sudah ditentukan dan setiap selang waktu tertentu mengejutkan burung agar terbang lalu menghitung jumlahnya
Angka itu kemudian diserahkan ke kantor yang bertanggung jawab, dan kantor tersebut memperkirakan total populasi berdasarkan angka itu
Pada suatu tahun, karena orang itu sedang berada di luar negeri, ia menjelaskan metodenya secara rinci kepada temannya dan menitipkan tugas itu
Namun ketika hari survei yang sebenarnya tiba, temannya itu malah lupa begitu saja, dan karena repot akhirnya hanya mengirim angka yang kira-kira masuk akal
Tahun berikutnya, halaman depan koran lokal memuat judul “kenaikan populasi ptarmigan yang memecahkan rekor”
Perubahan drastis seperti itu menjadi berita karena angka tersebut dipakai sebagai dasar untuk menentukan izin berburu. Temannya tidak memikirkan hal itu
Dulu saat mengerjakan sistem reservasi untuk resor ski besar, saya harus menyelesaikan laporan statistik resmi untuk pelaporan ke pemerintah, seperti guest-night
Karena waktu mepet dan saya bekerja semalaman, data statistik tahun itu sangat berbeda dari nilai sebenarnya
Halo! o/
Saya penulis artikel ini. Pertanyaan atau masukan sangat saya sambut
Kode untuk semua posting tersedia dengan lisensi MIT di https://github.com/samwho/visualisations. Silakan dipakai sesuka hati
Menurut saya ini posting yang sangat bagus
Ada arah optimasi lain untuk reservoir sampling: alih-alih mengambil bilangan acak untuk setiap item guna mengecek apakah perlu diganti, kita bisa mengambil jumlah lompatan dari distribusi Geometric
Ini menarik untuk kasus seperti tape drive, saat kita bisa melewati banyak item dengan murah (panjang tape belum diketahui sebelumnya, tetapi selama melompati item sistem sebagian besar bisa dibiarkan dalam mode tidur)
Untuk mengambil k sampel dari n item, kira-kira hanya diperlukan sampling dan skip sebanyak O(k * log(n/k))
Konsep lain yang saya suka adalah memberi prioritas acak pada setiap kartu saat datang lalu mempertahankan k teratas
Masalah terkait di sini adalah bagaimana memilih hanya k item teratas dari stream dengan panjang tak diketahui dalam O(n) waktu dan O(k) ruang.
Masukkan semuanya ke buffer tak terurut berukuran 2*k, dan ketika penuh gunakan randomized quickselect atau median-of-medians untuk menyisakan hanya k teratas
Jika proses ini dilakukan untuk n item, totalnya memerlukan waktu O(n)
Teknik terkait lain yang juga menarik adalah rendezvous hashing
Dan untuk alias method, tulisan di https://www.keithschwarz.com/darts-dice-coins/ juga membantu
Saya penasaran apakah metode ini bisa dipakai secara bertingkat
Misalnya, jika layanan saya melakukan reservoir sampling, dan layanan pengumpul log juga melakukan reservoir sampling, apakah hasilnya akan setara dengan hanya memakai layanan pengumpul log sekali saja?
Saya sangat menyukai animasi dan penjelasannya
Terutama interaksi seperti mengocok grafik 100 kali dan sebagainya sangat mengesankan
Awalnya saya agak bingung karena dari pembahasan memilih 3 kartu dari 10 atau 436.234 kartu, tiba-tiba berpindah ke contoh melihat satu kartu pada satu waktu lalu memilih 1 kartu
Menurut saya akan lebih mudah dipahami bila ada satu pemisah bagian di sekitar bagian “Sekarang mari kita lempar kurvanya!”
Pada titik itu kita sekarang mengasumsikan hanya memegang 1 kartu, dan bahkan tidak tahu ukuran dek
Saya sangat suka desain situsnya
Interaksi, karakter anjing, font dan warna, serta tata letak keseluruhannya semuanya bagus
Seluruh blog ini terasa seperti harta karun
Senang sekali bisa menemukannya
Saya suka grafiknya
Hanya saja saya belum yakin apakah metode ini sepenuhnya sah secara statistik. Semua log dalam suatu periode memang dipilih dengan probabilitas yang sama, tetapi saya khawatir log yang muncul pada ‘periode lambat’ justru jadi terlalu terwakili dalam statistik keseluruhan
Misalnya, jika ingin mengetahui endpoint mana di seluruh sistem yang paling banyak memakai CPU untuk dioptimalkan, bukankah log dari endpoint yang sesekali mengalami lonjakan traffic bisa kurang terwakili, sehingga endpoint yang sebenarnya paling banyak dipakai tidak dievaluasi dengan tepat?
Atau untuk perencanaan kapasitas per layanan juga, layanan dengan traffic burst tampaknya akan kurang terwakili
Saya penasaran penggunaan apa yang paling cocok untuk reservoir sampling, dan jenis analisis statistik apa yang bisa dilakukan dengan metode ini
Artikel yang sangat bagus; matematika atau statistika seharusnya diajarkan seperti ini agar menyenangkan untuk dipelajari
Saya merasakan nuansa yang mirip dengan https://distill.pub/
Kalimat “Sometimes the hand of fate must be forced” sangat membekas
Saya sangat suka gaya interaktifnya
Menurut saya desain situs dan cara mengajarnya benar-benar indah. Terima kasih
Saya penasaran apakah blog ini punya RSS feed
Ini posting yang sangat jelas dan ilustrasinya juga bagus
Sebagai pengembangan yang lebih lanjut, ada juga algoritme yang menghitung berapa banyak item yang harus dilewati sekaligus alih-alih memakai metode dasar
Penjelasan rinci di https://richardstartin.github.io/posts/reservoir-sampling layak dibaca
Artikel dan penjelasannya bagus
Untuk pengumpulan log nyata, saya sarankan mencoba berbagai pendekatan lebih dulu dan menjadikan fairness sebagai pilihan terakhir
Misalnya, beri prioritas pada log dan buang dulu log dengan priority rendah (verbosity tinggi)
Untuk log yang secara semantik mewakili satu aktivitas, kurangi log repetitif di tengah dan simpan hanya awal, akhir, dan perubahan status penting
Jika log yang mirip/duplikat diagregasikan dan disimpan dalam bentuk ringkasan, total volume juga berkurang dan lebih baik untuk melihat tren
Belakangan ini saya banyak mempelajari observability, dan metode yang disebutkan itu adalah pendekatan campuran head/tail sampling.
Penjelasan terkait ada di https://docs.honeycomb.io/manage-data-volume/sample/
Artikel ini juga membahas bagian itu
Sebenarnya yang penting bukan membuang semua log berprioritas rendah, melainkan membatasinya dengan konsep ‘anggaran’
Jumlah total log sendiri juga bisa dibatasi dengan anggaran tingkat atas yang terpisah
Reservoir sampling juga bisa menangani batasan seperti ini dengan baik
Artikel dan penjelasannya bagus
Di makalah Vitter, “Algorithm R” dijelaskan, dan itu adalah metode reservoir sampling.
Bisa merujuk ke https://www.cs.umd.edu/~samir/498/vitter.pdf
Makalah Vitter yang lebih lama, https://dl.acm.org/doi/10.1145/358105.893, mengutip Knuth TAOCP volume 2, tetapi Knuth juga tidak memberikan sumber yang jelas
Sangat rapi dijelaskan, dan jika penasaran dengan weighted reservoir sampling, ada penjelasan di https://gregable.com/2007/10/reservoir-sampling.html
Ada juga cara yang mudah diterapkan ke lingkungan terdistribusi dengan map-reduce, serta metode yang sangat sederhana berupa memasangkan nilai acak ke setiap item lalu mempertahankan Top N
Metode dasar yang mengambil prioritas tiap item dengan POW(RANDOM(), 1.0 / weight) lalu memilih Top N punya masalah kestabilan numerik saat weight sangat besar atau sangat kecil
Selain itu, sampel hasilnya mungkin juga tidak cukup mencerminkan distribusi populasi aslinya. Kecenderungan ini terutama kuat ketika total weight terkonsentrasi pada sedikit item
Meski begitu, dalam kebanyakan situasi ini tetap pendekatan yang cukup baik
Penjelasan lebih rinci ada di https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html
Membaca artikel ini mengingatkan saya pada metode yang digunakan Sekutu untuk memperkirakan produksi tank Jerman dari nomor seri pada Perang Dunia II
Saat itu personel lapangan memperkirakan jumlah produksi sekitar 5 kali lebih tinggi dari kenyataannya, sedangkan metode nomor seri memiliki akurasi di atas 90%
Postingan yang luar biasa, dan visualisasinya juga benar-benar hebat
Dalam layanan nyata, kami memakai variasi serupa untuk memperkirakan nilai percentile yang berubah-ubah secara real-time dari stream yang sangat besar
Nilai percentile kadang berubah, tetapi biasanya tetap sama selama sangat banyak pengulangan. Data dasarnya bersifat quasi-stationary
Dengan cadangan splay tree, ini bisa diestimasi dalam waktu amortized O(1), meski dibanding metode lain rentang error terhadap penggunaan RAM lebih lebar
Probabilitas penggantian juga bisa disesuaikan untuk mengurangi ‘half-life’ data, yaitu membuat estimasi lebih bias ke data yang lebih baru
Dari sudut pandang data science, jumlah data itu sendiri membawa informasi penting, jadi menurut saya rasio sampling harus selalu dicatat bersama datanya
Misalnya jika tingkat sampling 10%, catat angka 10 pada tiap sampel agar total hitungan, jumlah, rata-rata, dan sebagainya bisa dipulihkan dan diestimasi dengan benar
Post ini menunjukkan dengan baik trade-off dalam pengumpulan telemetry (trace, log, metrics)
Bidang analisis data seperti ini punya hambatan masuk yang tinggi dan sering diabaikan oleh banyak developer
Bahkan jika datanya tampak sama, grafik yang diamati bisa benar-benar berbeda tergantung bagaimana sampling dilakukan, dan banyak orang mengabaikan hal ini