Filter CUCKOO vs BLOOM, dari perspektif Gopher

Pada artikel ini, saya mencoba menerapkan dan menguji efisiensi filter kukuk di atas filter mekar. (Baca posting sebelumnya di Chord DHT, menerapkan tabel hash yang didistribusikan di Golang)

pengantar

Struktur data probabilistik sangat berguna, terutama saat memproses set data besar. Sebagian besar waktu, saat bekerja di sisi data hal, orang ingin melakukan sederhana "adalah item tidak ada" atau "adalah item sudah ada" permintaan sambil memproses data waktu nyata. Katakanlah Anda ingin menjawab pertanyaan secara real time, seperti jumlah ips unik, ips paling sering, jika iklan telah ditayangkan kepada pengguna, menggunakan struktur data probabilistik menyediakan cara yang efisien ruang untuk menjawab pertanyaan ini. Pendekatan tipikal untuk pertanyaan semacam itu adalah dengan menggunakan HashMap atau HashTable, atau menyimpannya dengan beberapa cache eksternal (seperti redis), tetapi masalahnya ada pada dataset besar, struktur data sederhana ini tidak dapat masuk ke dalam memori. Di sinilah struktur data probabilistik berperan karena keunggulan ruang dan waktu mereka.

Contoh Gunakan kasing

  • Google Bigtable, Apache HBase dan Apache Cassandra, dan Postgresql menggunakan filter Bloom untuk mengurangi pencarian disk untuk baris atau kolom yang tidak ada. Menghindari pencarian disk yang mahal sangat meningkatkan kinerja operasi permintaan basis data.
  • Medium menggunakan filter Bloom untuk memeriksa apakah suatu artikel telah direkomendasikan kepada pengguna
  • Ethereum menggunakan filter Bloom untuk menemukan log di blockchain Ethereum dengan cepat
  • Peramban web Google Chrome digunakan untuk menggunakan filter Bloom untuk mengidentifikasi URL jahat. Setiap URL pertama kali diperiksa terhadap filter Bloom lokal, dan hanya jika filter Bloom mengembalikan hasil positif adalah pemeriksaan penuh terhadap URL dilakukan (dan pengguna memperingatkan, jika itu juga mengembalikan hasil positif)

Apa yang ada di "Cuckoo"?

Kami telah menggunakan filter bloom di banyak tempat untuk menjawab pertanyaan seperti itu di platform data. Baru-baru ini saya menemukan makalah ini di filter Cuckoo yang menarik minat saya. Judulnya sendiri berbunyi, "Filter Cuckoo: Praktis Lebih Baik Daripada Mekar", jadi saya memutuskan untuk memeriksanya.

Filter Cuckoo meningkatkan desain filter mekar dengan menawarkan penghapusan, penghitungan terbatas, dan probabilitas positif palsu terbatas, sambil tetap mempertahankan kompleksitas ruang yang serupa. Mereka menggunakan hashing cuckoo untuk menyelesaikan tabrakan dan pada dasarnya tabel hash cuckoo kompak.

Filter kukuk dan bloom berguna untuk mengatur pengujian keanggotaan saat ukuran data asli besar. Keduanya hanya menggunakan 7 bit per entri. Mereka juga berguna ketika operasi yang mahal dapat dihindari sebelum dieksekusi oleh tes keanggotaan yang ditetapkan. Sebagai contoh, sebelum meng-query database, tes keanggotaan set dapat dilakukan untuk melihat apakah objek yang diinginkan ada dalam database.

Algoritma

Parameter Filter:
1. Dua Fungsi Hash: h1 dan h2
2. Array B dengan n ember. Bucket ke-i akan disebut B [i]

Input: L, daftar elemen yang akan dimasukkan ke dalam filter kukuk.

Algoritma:
Sementara L tidak kosong:
    Biarkan x menjadi item pertama dalam daftar L. Hapus x dari daftar.
    Jika B [h1 (x)] kosong:
        tempat x dalam B [h1 (x)]
    Lain, Jika B [h2 (x) kosong]:
        tempat x dalam B [h2 (x)]
    Lain:
        Biarkan y menjadi elemen dalam B [h2 (x)].
        Sertakan y ke L
        tempat x dalam B [h2 (x)]

Pelaksanaan

Implementasi tampaknya cukup mudah, jadi saya memutuskan untuk mencobanya dan membandingkan seberapa efisien ruang / waktu dibandingkan dengan filter bloom. Filter Cuckoo terdiri dari tabel hash Cuckoo yang menyimpan 'sidik jari' dari barang-barang yang dimasukkan. Sidik jari suatu item adalah string bit yang berasal dari hash item tersebut. Tabel hash cuckoo terdiri dari susunan bucket tempat item yang akan dimasukkan dipetakan ke dua kemungkinan bucket berdasarkan pada dua fungsi hash. Setiap ember dapat dikonfigurasikan untuk menyimpan sejumlah sidik jari. Biasanya, filter Cuckoo diidentifikasi oleh sidik jari dan ukuran embernya. Sebagai contoh, a (2,4) filter Cuckoo menyimpan sidik jari 2 bit panjang dan setiap ember di tabel hash Cuckoo dapat menyimpan hingga 4 sidik jari.

Insersi

Algoritma:

f = sidik jari (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
jika bucket [i1] atau bucket [i2] memiliki entri kosong, maka
   tambahkan f ke ember itu;
   kembali Selesai;
// harus memindahkan item yang ada;
i = pilih secara acak i1 atau i2;
untuk n = 0; n 
// Hashtable dianggap penuh;
Kegagalan pengembalian;

Kode:

Pencarian

Algoritma:

f = sidik jari (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
jika bucket [i1] atau bucket [i2] memiliki f maka
    return True;
mengembalikan False;

Kode:

Menghapus

Algoritma:

f = sidik jari (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
jika bucket [i1] atau bucket [i2] memiliki f maka
   hapus salinan f dari ember ini;
   return True;
mengembalikan False;

Kode:

Uji kinerja

Saya telah menggunakan perpustakaan Will Fitzgerald untuk pengujian pada filter Bloom. Rasio FPP (False Positive Probability) yang diambil untuk filter cuckoo adalah 0,001

Kompleksitas Ruang

Sehubungan dengan filter kukuk dan mekar, mereka melakukan berbeda pada probabilitas positif palsu yang berbeda. Ketika probabilitas positif palsu dari filter kurang dari atau sama dengan 3%, filter cuckoo memiliki lebih sedikit bit per entri. Ketika lebih tinggi, filter bloom memiliki lebih sedikit bit per entri.

Kompleksitas Waktu

Dalam hashing cuckoo, memasukkan elemen tampaknya jauh lebih buruk daripada O (1) dalam kasus terburuk karena mungkin ada banyak contoh selama tabrakan, di mana kita harus menghapus nilai untuk memberikan ruang bagi nilai saat ini. Plus, jika ada siklus maka seluruh tabel harus diulang.

Melakukan analisis waktu dari kedua filter menghasilkan hasil berikut:

Sepanjang percobaan ini (mengingat kode saya mungkin tidak sepenuhnya dioptimalkan), filter Bloom tampaknya berkinerja sangat baik dalam kompleksitas ruang, menempati lebih sedikit ruang untuk sejumlah besar item. Filter Cuckoo tampaknya berkinerja lebih baik dalam penyisipan sejumlah besar item, tetapi sedikit lebih lambat dalam pencarian (waktu pencarian) karena penerapannya.

Kesimpulan

Saya tidak akan benar-benar memihak filter mana yang direkomendasikan, saya pikir mereka berdua memiliki kasus penggunaan sendiri. Filter Bloom tidak mendukung penghapusan karena hashing bersifat lossy dan ireversibel. Meskipun menghitung filter bloom menyelesaikan masalah itu, filter Cuckoo berguna dalam kasus di mana Anda akan membutuhkan penghapusan. Tentu saja filter Cuckoo memberikan kesalahan ketika filter penuh, dan yang memiliki kelebihannya sendiri, sedangkan dalam filter Bloom, tidak ada kontrol atas kapasitas, itu hanya mengulangi pengulangan bit array yang ada.

Kode

Referensi

  • https://brilliant.org/wiki/cuckoo-filter/
  • https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
  • https://en.wikipedia.org/wiki/Cuckoo_hashing
  • https://blog.fastforwardlabs.com/2016/11/23/probabilistic-data-structure-showdown-cuckoo.html

P.S Jika Anda menemukan sesuatu yang salah dengan tes / implementasi, jangan ragu untuk meninggalkan saran / komentar Anda.