Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Code
  2. Redis
Code

Memahami keajaiban Bloom filter dengan Node.js & Redis

by
Length:LongLanguages:

Indonesian (Bahasa Indonesia) translation by Fajar Bahri (you can also view the original English article)

Di kasus yang benar, Bloom filter tampak seperti keajaiban. Itu adalah pernyataan berani, tetapi dalam tutorial ini kita akan menjelajahi struktur data penasaran, cara terbaik untuk menggunakannya, dan beberapa contoh-contoh praktis menggunakan Redis dan Node.js.

Bloom filter adalah struktur data probabilistik, sekali jalan. Kata 'filter' dapat membingungkan dalam konteks ini; Filter menyiratkan bahwa itu hal yang aktif, kata kerja, tapi itu mungkin lebih mudah untuk menganggapnya sebagai penyimpanan, kata benda. Dengan bloom filter sederhana Anda dapat melakukan dua hal:

  1. Tambahkan item.
  2. Periksa jika item belum ditambahkan sebelumnya.

Ini adalah keterbatasan yang penting untuk memahami-Anda tidak dapat menghapus item tidak dapat Anda daftar item dalam Bloom filter. Juga, Anda tidak bisa mengatakan, dengan pasti, jika item telah ditambahkan ke filter di masa lalu. Ini adalah tempat sifat probabilistik Bloom filter datang — positif palsu mungkin, tetapi kesalahan negatif tidak. Jika filter sudah disetel dengan benar, positif palsu dapat sangat langka.

Ada varian Bloom filter, dan mereka menambahkan kemampuan lain, seperti penghapusan atau scaling, tetapi mereka juga menambahkan kompleksitas dan keterbatasan. Hal ini penting untuk pertama-memahami Bloom Filter sederhana sebelum pindah ke varian. Artikel ini hanya akan mencakup Bloom filter sederhana.

Dengan keterbatasan ini Anda memiliki sejumlah manfaat: ukkuran tetap, enkripsi berbasis hash dan pencarian cepat.

Bila Anda membuat Bloom filter, Anda memberikan ukuran. Ukuran ini adalah tetap, jadi jika Anda memiliki satu item atau item satu miliar di filter, itu tidak pernah akan tumbuh melampaui ukuran tertentu. Ketika Anda menambahkan lebih banyak item untuk filter Anda, kemungkina positif palsu meningkat. Jika Anda menetapkan filter kecil, menilai positif palsu ini akan meningkat lebih cepat daripada jika Anda memiliki ukuran yang lebih besar.

Bloom filter yang dibangun pada konsep hashing one-way. Banyak seperti menyimpan sandi, Bloom filter menggunakan algoritma hash untuk menentukan pengidentifikasi unik untuk item yang dimasukan ke dalamnya. Hash, secara alami, tidak dapat dikembalikan dan diwakili oleh serangkaian karakter acak. Jadi, jika seseorang mendapatkan akses ke Bloom filter, itu tidak akan langsung mengungkapkan salah satu isi.

Akhirnya, Bloom filtear itu cepat. Operasi ini melibatkan perbandingan jauh lebih sedikit daripada metode lainnya, dan dengan mudah dapat disimpan dalam memori, mencegah performance-robbing database hits.

Sekarang bahwa Anda tahu keuntungan Bloom filter dan batas-batasnya, mari kita lihat beberapa situasi di mana Anda dapat menggunakannya.

Setup

Kita akan menggunakan Redis dan Node.js untuk menggambarkan Bloom filter. Redis adalah media penyimpanan Bloom filter; ini cepat, in-memory, dan memiliki beberapa perintah khusus (GETBIT, SETBIT) yang membuat implementasi yang efisien. Saya akan berasumsi bahwa Anda memiliki Node.js, npm, dan Redis diinstal pada sistem Anda. Server Redis Anda harus berjalan di localhost di port default untuk contoh kami bekerja.

Dalam tutorial ini, kita tidak akan dapat menerapkan filter dari awal Sebaliknya, kita akan fokus pada manfaat praktis dengan modul pre-built di npm: bloom-redis. bloom-redis memiliki seperangkat sangat ringkas metode: add, contains dan clear.

Seperti disebutkan sebelumnya, Bloom filter membutuhkan hashing algoritma untuk dihasilkan pengidentifikasi unik untuk item. bloom-redis menggunakan algoritma MD5 terkenal, yang, meskipun mungkin tidak sempurna cocok untuk bloom filter (sedikit lambat, overkill pada bit), akan bekerja dengan baik.

Nama pengguna unik

Nama pengguna, khususnya yang mengidentifikasi seorang pengguna di URL, harus unik. Jika Anda membangun sebuah aplikasi yang memungkinkan pengguna untuk mengubah nama pengguna, maka Anda mungkin akan ingin nama pengguna yang belum pernah digunakan untuk menghindari kebingungan dan mengecam dari nama pengguna.

Tanpa Bloom filter, Anda akan perlu untuk referensi tabel yang memiliki setiap pengguna yang pernah digunakan, dan pada skala ini bisa sangat mahal. Bloom filter memungkinkan Anda untuk menambahkan item setiap kali pengguna mengadopsi nama baru. Saat pengguna memeriksa untuk melihat jika username sudah dipakai, semua yang Anda perlu lakukan adalah memeriksa Bloom filter. Itu akan dapat memberitahu Anda, dengan kepastian yang mutlak, jika username yang diminta telah ditambahkan sebelumnya. Dimungkinkan bahwa filter palsu akan mengembalikan username telah digunakan ketika belum, tetapi ini keliru di sisi hati-hati dan dapat menyebabkan kerusakan nyata (selain dari pengguna mungkin tidak mampu mengklaim 'k3w1d00d47').

Untuk menggambarkan hal ini, mari kita membangun server quick REST dengan Express. Pertama, membuat package.json file dan kemudian jalankan perintah terminal berikut.

npm install bloom-redis --save

npm install express --save

npm install redis --save

Pilihan default untuk bllom-redis memiliki ukuran yang ditetapkan pada dua megabyte. Ini keliru di sisi hati-hati, tapi itu cukup besar. Mengatur ukuran filter bloom filter sangat penting: terlalu besar dan Anda membuang-buang memori, terlalu kecil dan Anda menilai positif palsu akan terlalu tinggi. Matematika terlibat dalam menentukan ukuran cukup terlibat dan di luar cakupan tutorial ini, tapi Untungnya ada Bloom filter ukuran kalkulator untuk mendapatkan pekerjaan yang dilakukan tanpa merusak textbook.

Sekarang, buat app.js sebagai berikut:

Untuk menjalankan server ini: node app.js. Pergi ke browser Anda dan titik itu ke: https://localhost:8010/check?username=kyle. Respon harus: {"username": "kyle", "status": "bebas"}.

Sekarang, mari kita simpan nama pengguna dengan menunjuk peramban pada http://localhost:8010/save?username=kyle. respons akan: {"username": "kyle", "status": "created"}. Jika Anda kembali ke alamat http://localhost:8010/check? username=kyle, respon akan {"username": "kyle", "status": "used"}. Demikian pula, akan kembali ke http://localhost:8010/save? username=kyle akan hasilnya {"username": "kyle", "status": "not-created"}.

Dari terminal, Anda dapat melihat ukuran filter: redis-cli strlen username-bloom-filter.

Sekarang, dengan satu item, itu harus menunjukkan 338622.

Sekarang, pergi ke depan dan mencoba menambahkan lebih username dengan /save route. Mencoba sebanyak yang Anda suka.

Jika Anda kemudian memeriksa ukuran lagi, Anda mungkin memperhatikan bahwa ukuran Anda sudah naik sedikit, tetapi tidak untuk setiap tambahan. Penasaran, kan? Secara internal, Bloom filter set bit individu (1 / 0 di) pada posisi yang berbeda dalam string disimpan pada username-bllom. Namun, ini tidak berdekatan, jadi jika Anda menetapkan sedikit pada index 0 dan kemudian satu di index 10.000, semuanya diantara akan 0. Untuk penggunaan praktis, hal ini awalnya tidak penting untuk memahami mekanisme tepat setiap operasi — hanya tahu bahwa ini normal dan bahwa penyimpanan Anda di Redis akan pernah melebihi nilai yang Anda tentukan.

Konten segar

kontensegar di situs web membuat pengguna kembali, jadi bagaimana Anda menunjukkan pengguna sesuatu yang baru setiap kali? Menggunakan pendekatan tradisional database, Anda bisa menambahkan baris baru ke tabel dengan pengidentifikasi pengguna dan pengenal cerita, dan kemudian Anda akan kueri tabel ketika memutuskan untuk menunjukkan bagian dari konten. Seperti yang Anda bayangkan, database Anda akan tumbuh sangat cepat, terutama dengan pertumbuhan pengguna dan konten.

Dalam kasus ini, negatif palsu (misalnya tidak menampilkan bagian konten yang tidak terlihat) memiliki konsekuensi sangat sedikit, membuat bloom-filter menjad pilihan yang layak. Sepintas, Anda mungkin berpikir bahwa Anda akan memerlukan sebuah bloom-filter untuk setiap pengguna, tetapi kita akan menggunakan rangkaian sederhana pengidentifikasi pengguna dan pengenal konten, dan kemudian masukkan string ke filter kami. Dengan cara ini kita dapat menggunakan single filter untuk semua pengguna.

Dalam contoh ini, mari kita membangun basic Express server lain yang menampilkan konten. Setiap kali Anda mengunjungi route /show-content/any-username (dengan username apapun menjadi nilai URL-aman), potongan baru konten akan ditampilkan sampai situs kehabisan konten. Dalam contoh, konten adalah baris pertama dari atas sepuluh buku mengenai Proyek Gutenberg.

Kita akan perlu untuk menginstal satu modul npm lain. Dari terminal, jalankan: npm install async --save

File app.js baru:

Jika Anda dengan hati-hati memperhatikan waktu pulang-pergi di Dev Tools, Anda akan melihat bahwa semakin Anda meminta satu jalan dengan nama pengguna, makin lama waktu yang diperlukan. Sementara memeriksa filter mengambil waktu yang tetap, dalam contoh ini, kami sedang memeriksa keberadaan item-item lain. Bloom filter terbatas dalam apa yang mereka dapat memberitahu Anda, sehingga Anda menguji untuk kehadiran setiap item. Tentu saja, dalam contoh kita memang cukup sederhana, tetapi pengujian untuk ratusan item akan tidak efisien.

Data basi

Dalam contoh ini, kita akan membangun sebuah server Express kecil yang akan melakukan dua hal: menerima data baru melalui POST, dan menampilkan data saat ini (dengan GET request). Ketika data baru POST'ed ke server, aplikasi akan memeriksa kehadirannya di filter. Jika itu tidak hadir, kami akan menambahkannya dan di set di Redis, sebaliknya kita akan mengembalikan null. Permintaan GET akan mengambil itu dari Redis dan mengirimkannya kepada klien.

Hal ini berbeda dari dua situasi sebelumnya, bahwa positif palsu tidak akan baik-baik saja. Kita akan menggunakan bloom-filter sebagai garis pertama pertahanan. Beri properti bloom filter, kita akan hanya tahu dengan pasti bahwa sesuatu yang tidak ada dalam filter, sehingga dalam kasus ini kita dapat pergi ke depan dan membiarkan datanya. Jika Bloom filter mengembalikan itu mungkin adalah di dalam filter, kami akan melakukan cek versus sumber data aktual.

Jadi, apa kita memperoleh? Kita mendapatkan kecepatan tidak harus memeriksa versus sumber yang sebenarnya setiap waktu. Dalam situasi dimana sumber data adalah lambat (eksternal APIs, muslihat database, tengah flat file), peningkatan kecepatan benar-benar diperlukan. Untuk menunjukkan kecepatan, mari kita tambahkan di penundaan realistis 150ms dalam contoh. Kami juga akan menggunakan console.time / console.timeEnd untuk log perbedaan antara Bloom filter cek dan non-bloom filter cek.

Dalam contoh ini, kami juga akan menggunakan jumlah bit yang sangat dibatasi: hanya 1024. Itu akan mengisi dengan cepat. Seperti ini mengisi, itu akansemakin menunjukkan positif palsu  — Anda akan melihat waktu respon yang meningkat karena nilai positif palsu meningkat.

Server ini menggunakan modul yang sama seperti sebelumnya, jadi mengatur app.js file untuk:

Sejak POSTing ke server dapat menjadi rumit dengan browser, mari kita menggunakan curl untuk mengujinya.

curl--data "your data goes here"--header "Content-Type: text/plain" http://localhost:8012/

quick bash script dapat digunakan untuk menunjukkan bagaimana mengisi seluruh filter terlihat:

Melihat penuh atau mengisi filter ini menarik. Karena yang satu ini kecil, Anda dapat dengan mudah melihat itu dengan redis-cli. Dengan menjalankan redis-cli get stale-filter dari terminal antara menambahkan item, Anda akan melihat byte individu yang meningkat. Filter penuh akan \xff untuk setiap byte. Pada titik ini, filter akan selalu mengembalikan positif.

Kesimpulan

Bloom filter bukan solusi obat mujarab, tapi dalam situasi yang tepat, Bloom filter dapat memberikan yang cepat, efisien untuk melengkapi struktur data lain.

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.