Sketch Lab

Masalahnya

Hampir semua backend engineer pernah mendengar Bloom filter, Count-Min sketch, dan HyperLogLog. Sedikit yang yakin memakainya. Struktur data ini menjawab pertanyaan tentang data yang sangat besar dengan memori yang kecil dan tetap: database yang melewatkan pembacaan disk, CDN yang menghitung pengunjung unik, atau stream processor yang mencari item paling sering muncul. Makalahnya padat, dan kebanyakan tulisan blog menyederhanakan satu hal yang paling penting. Galatnya hanya ke satu arah dan bisa dihitung sebelumnya. Jawaban "tidak" dari Bloom filter itu pasti. Jawaban "ya"-nya hanya kemungkinan.

Tidak ada yang mau memakai struktur perkiraan yang tidak bisa diperiksa. Saya membangun Sketch Lab untuk dua kelompok: engineer yang perlu menentukan ukuran struktur ini untuk sistem produksi, dan engineer yang perlu melihatnya bekerja sebelum memercayainya.

Yang saya bangun

Jawaban pasti berjalan di samping jawaban perkiraan

Setiap stream diproses oleh sketch dan oleh set atau map biasa yang pasti pada saat yang sama. Halaman menandai setiap false positive begitu terjadi, lengkap dengan item dan slot yang bertabrakan. Kontrol utamanya adalah slider memori. Geser memori ke bawah, dan dua kurva bergerak bersama: galat yang diprediksi rumus dan galat yang diukur dari stream.

Memori diukur dalam byte yang sebenarnya

Perbandingan dengan struktur pasti hanya bermakna kalau angkanya benar. Karena itu setiap angka memori adalah ukuran array yang dialokasikan sebenarnya, bukan hasil rumus yang disajikan sebagai pengukuran. Kalkulator menerima jumlah item dan target galat, lalu mengembalikan ukuran, rumus, dan memorinya dalam byte. Layar inilah yang membuatnya bisa dipakai untuk pekerjaan sehari-hari.

Hash dan strukturnya saya tulis sendiri

Keempat struktur dibuat dari makalah aslinya: Bloom (1970), Count-Min (2005), HyperLogLog (2007), dan Cuckoo filter yang mendukung penghapusan. Fungsi hash-nya juga saya tulis sendiri. Setiap jaminan galat mengandaikan hash yang baik, dan hash yang buruk merusak semuanya tanpa suara. Tes hash berjalan paling awal di pipeline build, dan tidak ada yang berjalan kalau tes itu gagal.

Jaminan dan peluang diuji terpisah

"Bloom filter tidak pernah menjawab tidak untuk item yang sudah dimasukkan" adalah aturan, dan saya mengujinya tanpa toleransi. "Tingkat galat tetap di dalam batas prediksi" adalah peluang, diuji dengan seed tetap, banyak percobaan, dan toleransi yang ditulis jelas. Pemisahan ini mencegah orang menambahkan kelonggaran pada aturan yang tidak boleh longgar. Setiap percobaan memakai seed, jadi masukan yang sama memberi hasil yang sama di mesin mana pun.

Saat tes gagal, modelnya yang saya perbaiki

Satu tes gagal dengan galat sekitar 2.500 kali angka di buku teks. Saya menelusurinya ke efek struktural dari metode hash-nya, yang muncul saat filter diberi memori jauh lebih besar dari yang dibutuhkan. Saya menambahkan suku yang hilang ke model dan tidak menyentuh toleransinya. Pemeriksaan berikutnya menunjukkan Cuckoo filter ini memakai memori lebih besar daripada Bloom filter di setiap tingkat galat. Jadi halaman menawarkannya untuk fitur penghapusan, tanpa klaim soal hemat memori.

Hasilnya

Sketch Lab sudah live, terbuka untuk umum, tersedia dalam bahasa Inggris dan Indonesia, dan bisa dipakai offline setelah dimuat pertama kali. Isinya empat struktur ditambah pembanding pasti, pengecekan penggabungan sketch, serta stream seragam, miring, adversarial, dan teks. Setiap pengaturan bisa dibagikan sebagai link. Semua milestone di rencana selesai, termasuk Cuckoo filter yang opsional. Saya membangunnya dalam satu hari, 6 Agustus 2026, dengan tiga dependensi runtime. Ini alat belajar, bukan library produksi, dan memang itu rencananya sejak awal.