Banding & merge
Dua struktur ini, yang dibangun terpisah, bisa digabungkan menjadi satu — dan hasilnya persis struktur yang akan Anda dapat kalau kedua stream itu diberikan ke satu mesin saja.
Di mana ini benar-benar dipakai
Inilah yang membuatnya berguna dalam skala besar. Seratus server masing-masing menyimpan sketch sendiri dan tidak pernah saling bicara; di akhir jam, satu mesin menggabungkan seluruh seratusnya menjadi satu jawaban yang mencakup semua request, dalam satu lintasan, tanpa membaca ulang data aslinya.
Jaminannya
Diverifikasi terhadap struktur yang dibangun dari stream yang disambung
Cara kerjanya
Stream yang sama melalui setiap struktur, dan merge yang membuat semuanya berguna lintas mesin yang tidak pernah saling bicara.
Merge
Dua sketch dibangun dari stream berbeda, lalu di-union. Bloom filter di-OR; HyperLogLog mengambil maksimum per register; Count-Min sketch dijumlahkan.
Bloom filter
Stream A
4,643
Stream B
7,374
Hasil merge
10,941
Memory
4.0 KiB
diukur dari typed array
Terverifikasi
✓
identik byte demi byte dengan struktur yang dibangun dari A + B
Count-Min sketch
Stream A
4,000
Stream B
4,000
Hasil merge
8,000
Memory
10.0 KiB
diukur dari typed array
Terverifikasi
✓
identik byte demi byte dengan struktur yang dibangun dari A + B
HyperLogLog
Stream A
836
Stream B
1,376
Hasil merge
2,208
Memory
4.0 KiB
diukur dari typed array
Terverifikasi
✓
identik byte demi byte dengan struktur yang dibangun dari A + B
Union bekerja. Intersection tidak.
Meng-OR dua filter menghasilkan filter yang identik bit demi bit dengan yang akan Anda bangun dari kedua stream — sudah diverifikasi di atas. AND tampak seperti trik yang sama pada arah sebaliknya. Ternyata tidak, dan pemeriksaan yang lolos untuk union gagal di sini.
AND sama dengan filter yang dibangun dari intersection sebenarnya
✗
tidak
Item yang benar-benar ada di keduanya
778
Bit yang menyala oleh AND
4,352
Bit yang menyala oleh yang sebenarnya
4,310
ε dari AND
0
ε jika Anda membangunnya
0
Mengapa ia terlalu banyak menerima
AND mempertahankan setiap bit yang dinyalakan oleh item mana pun di satu filter dan kebetulan dinyalakan oleh item lain di filter satunya. Bit-bit itu tidak pernah ditaruh di sana oleh anggota intersection, dan tidak ada yang membedakannya dari bit yang memang begitu. Jadi hasilnya membawa lebih banyak bit menyala daripada filter yang dibangun dari intersection, dan lebih sering menjawab “mungkin ada” — Anda tidak mendapatkan ε yang seharusnya, dan tidak ada operasi pada kedua filter ini yang bisa memulihkan selisihnya.
Satu hal yang BUKAN masalahnya: menanyakan item dari kedua stream itu sendiri menunjukkan error rate di bawah ε satu filter, dan itu benar, bukan cacat — item yang ada di tepat satu himpunan hanya perlu diterima filter satunya secara kebetulan, dan itu memang ε menurut definisinya. Biayanya muncul pada item yang tidak ada di kedua stream, dan itulah yang diukur di sini.
Satu item, keempat strukturnya
Ini bukan empat algoritma. Ini satu pasang hash dan satu penurunan, dibaca dengan empat cara berbeda — h₁ dan h₂ yang sama yang memilih slot Bloom juga memilih kolom Count-Min, register HyperLogLog, dan bucket Cuckoo.
Melewati ukuran yang Anda rencanakan
Memory tetap, item terus bertambah. Kedua struktur diukur untuk 8,000 item; sumbunya berjalan sampai 40,000. Tidak ada di sini yang mengubah memory — hanya seberapa banyak yang Anda masukkan ke dalamnya.
Cuckoo filter — tidak ada merge lossless
Satu-satunya struktur di sini yang tidak bisa melakukannya. Bloom di-OR, HyperLogLog mengambil maksimum, Count-Min dijumlahkan — masing-masing satu lintasan atas array-nya dan selalu berhasil. Cuckoo filter tidak punya operasi seperti itu: entry berada di salah satu dari dua bucket, jadi merge berarti memasukkannya ulang satu per satu, dan itu bisa ditolak. Dua filter setengah penuh tidak muat ke dalam satu filter berukuran sama — terukur di sini 180 dari 600 entry ditolak.
Cardinality union
Stream A — distinct
836
Stream B — distinct
1,387
Hasil merge — Exact
2,223
Kedua stream sengaja tumpang tindih. Merge yang menghitung ganda akan terlihat di sini.
Hasil merge — Estimasi
2,208
-0.66%
Bloom dan HyperLogLog di-merge sebagai union himpunan, jadi menggabungkan sebuah struktur dengan dirinya sendiri tidak mengubah apa pun. Count-Min di-merge sebagai penjumlahan, jadi ia berubah — asimetri itu nyata, dan perlu diketahui sebelum Anda me-merge shard yang sama dua kali.