Tair (Redis® OSS-Compatible)：Bloom

Ikhtisar

Bitmap pada struktur data Redis seperti hash, set, dan string dapat digunakan untuk mengimplementasikan fitur serupa dengan TairBloom. Namun, struktur data ini mungkin mengonsumsi banyak memori atau gagal mempertahankan tingkat positif palsu yang stabil selama penskalaan dinamis. Oleh karena itu, TairBloom ideal untuk memeriksa keanggotaan dalam kumpulan data besar sambil mengizinkan adanya tingkat positif palsu tertentu. Filter Bloom bawaan TairBloom dapat digunakan tanpa enkapsulasi lebih lanjut atau pembuatan filter tambahan pada perangkat lokal Anda.

Fitur

• Penggunaan memori rendah.

• Skalabilitas dinamis.

• Tingkat positif palsu yang stabil selama penskalaan.

Skenario tipikal

Praktik terbaik

void recommendedSystem(userid) {
    while (true) {
        // Dapatkan ID artikel acak atau ID artikel yang diinginkan.
        docid = getDocByRandom()
        if (bf.exists(userid, docid)) {
            // Jika artikel mungkin telah direkomendasikan kepada pengguna, artikel berikutnya direkomendasikan.
            continue;
        } else {
            // Jika artikel belum direkomendasikan kepada pengguna, artikel tersebut direkomendasikan.
            sendRecommendMsg(docid);
            // Jika artikel telah direkomendasikan, ID artikel dicatat dalam filter Bloom.
            bf.add(userid, docid);
            break;
        }
    }
}

bool crawlerSystem( ) {
    while (true) {
        // Dapatkan URL yang ingin Anda crawl.
        url = getURLFromQueue()
        if (bf.exists(url_bloom, url)) {
            // Jika URL mungkin telah di-crawl, URL dilewati.
            continue;
        } else {
            // Crawl URL ini.
            doDownload(url)
            // Tambahkan URL ini ke filter Bloom.
            bf.add(url_bloom, url);
        }
    }
}

Cara kerjanya

TairBloom adalah implementasi dari SBFs. Fiturnya mencakup skalabilitas dinamis sambil menjaga tingkat positif palsu yang stabil. SBFs adalah filter Bloom yang dioptimalkan. Bagian berikut menjelaskan prinsip dasar filter Bloom dan SBFs.

• Filter Bloom

  Filter Bloom adalah struktur data probabilistik yang hemat ruang, dibayangkan oleh Burton Howard Bloom pada tahun 1970, yang digunakan untuk menguji apakah sebuah elemen merupakan anggota dari suatu set.

  Filter Bloom baru adalah larik bit dari m bit, semuanya disetel ke 0. Filter Bloom juga mencakup satu set fungsi hash k yang berbeda untuk menghasilkan distribusi acak seragam. k adalah konstanta yang kurang dari m. Saat Anda menambahkan elemen ke filter Bloom, fungsi hash k memetakan elemen-elemen ini ke k bit dalam larik bit dan menyetel k bit menjadi nilai 1. Dalam hal ini, satu bit dapat digunakan bersama oleh beberapa data. Gambar berikut menunjukkan cara memasukkan X1 dan X2 ke dalam filter Bloom yang mencakup 3 fungsi hash.

  Saat Anda menanyakan elemen dalam filter Bloom, Anda dapat menggunakan fungsi hash k untuk mendapatkan k bit. Jika semua k bit memiliki nilai 1, elemen tersebut ada dalam filter Bloom. Sebaliknya, elemen tersebut tidak ada. Gambar berikut menunjukkan cara menanyakan Y1 dan Y2 dalam filter Bloom.

  Gambar sebelumnya menunjukkan bahwa meskipun Y2 tidak pernah dimasukkan ke dalam filter Bloom, Y2 ditentukan ada dalam filter Bloom. Skenario ini menunjukkan bahwa filter Bloom memiliki tingkat positif palsu. Analisis sebelumnya menunjukkan bahwa filter Bloom memiliki fitur berikut:

  • Sebuah bit dapat digunakan bersama oleh beberapa data.

  • Filter Bloom memiliki tingkat positif palsu dan tingkat tersebut meningkat seiring dengan bertambahnya jumlah elemen dalam filter Bloom. Namun, filter Bloom tidak memiliki tingkat negatif palsu. Jika elemen ada dalam filter Bloom, elemen tersebut selalu ditentukan ada.

  • Elemen dapat ditambahkan ke filter Bloom tetapi tidak dapat dihapus dari filter Bloom. Alasannya adalah bit dapat digunakan bersama. Jika Anda menghapus elemen dari filter Bloom, elemen lain dalam filter Bloom terpengaruh.

• Filter Bloom yang Dapat Diskalakan

  Saat jumlah elemen meningkat, tingkat positif palsu juga meningkat. Jika Anda ingin mempertahankan tingkat positif palsu yang stabil, Anda harus menambah ukuran filter Bloom secara proporsional. Namun, ukuran tersebut tidak dapat ditingkatkan karena batasan struktural. SBFs muncul sebagai tanggapan atas masalah ini. SBFs adalah jenis baru filter Bloom yang menggabungkan beberapa filter Bloom menjadi satu.

  Gambar berikut menunjukkan model dasar SBF. SBF ini memiliki dua lapisan: BF0 dan BF1. Awalnya, SBF hanya berisi lapisan BF0. Jika Anda memasukkan elemen a, b, dan c ke dalam SBF ini dan lapisan BF0 tidak cukup besar untuk mempertahankan tingkat positif palsu yang ditentukan, lapisan BF1 dibuat untuk meningkatkan ukuran SBF. Kemudian, elemen d, e, dan f dimasukkan ke lapisan BF1. Lapisan baru bernama BF2 dibuat jika lapisan BF1 juga tidak dapat mempertahankan tingkat positif palsu yang ditentukan. Untuk informasi lebih lanjut, lihat Filter Bloom yang Dapat Diskalakan.

  Penting

  Selama penskalaan dinamis TairBloom, kapasitas lapisan baru adalah dua kali lipat dari lapisan sebelumnya, dan ruang memori yang ditempati adalah empat kali lipat dari lapisan sebelumnya.

  Dengan setiap lapisan tambahan, beberapa filter Bloom mungkin perlu dilalui selama kueri. SBFs hanya menyisipkan data ke lapisan terakhir dan menanyakan data dari lapisan terakhir hingga lapisan BF0. Oleh karena itu, peningkatan skala TairBloom dapat mengakibatkan pembuatan kunci besar dan dapat menyebabkan penurunan kinerja, dengan tingkat penurunan meningkat seiring dengan bertambahnya jumlah elemen.

  Dalam penggunaan aktual, kami sarankan Anda mempertimbangkan peningkatan skala TairBloom hanya sebagai tindakan pencegahan dan tidak sering melakukan peningkatan skala TairBloom. Pastikan memori yang cukup dicadangkan untuk instans untuk mencegah kegagalan tulis setelah Anda meningkatkan skala TairBloom, yang dapat menyebabkan operasi pengusiran data yang berkepanjangan dan menghambat pemrosesan permintaan.

  Anda dapat menjalankan perintah BF.INFO untuk memeriksa apakah kunci akan memicu peningkatan skala. Saat jumlah item di lapisan terbaru sama dengan kapasitas, ini menunjukkan bahwa peningkatan skala akan segera terjadi.

  Jika kapasitas aktual melebihi batas yang telah ditentukan, Anda dapat meningkatkan skala TairBloom untuk memastikan operasi tulis untuk bisnis dapat dilakukan pada TairBloom untuk mencegah insiden langsung. Setelah Anda meningkatkan skala TairBloom, kami sarankan Anda segera membangun ulang untuk meningkatkan kinerja dan mengurangi risiko terkait peningkatan skala di masa depan.

Prasyarat

Peringatan

• Data TairBloom yang ingin Anda kelola disimpan dalam instans Tair.

• Kapasitas awal dan tingkat positif palsu yang memenuhi persyaratan Anda harus dihitung terlebih dahulu. Untuk membuat kunci TairBloom yang memiliki kapasitas jauh lebih dari 100 elemen, jalankan perintah BF.RESERVE bukan perintah BF.ADD.

  Berikut ini menunjukkan perbedaan antara perintah BF.ADD dan perintah BF.RESERVE:

  • BF.ADD (juga dikenal sebagai BF.MADD): Jika kunci TairBloom tidak ada saat perintah ini dijalankan, kunci tersebut dibuat secara otomatis. Kapasitas default kunci adalah 100, dan tingkat positif palsu default kunci adalah 0,01. Jika Anda memerlukan kapasitas kunci yang jauh lebih dari 100, Anda hanya dapat meningkatkan skala kunci untuk mendukung lebih banyak elemen.

  • BF.RESERVE (juga dikenal sebagai BF.INSERT): Kapasitas awal ditentukan saat perintah ini dijalankan. Perintah ini menentukan kapasitas awal di lapisan pertama kunci. Jika kunci berisi lebih sedikit lapisan filter Bloom, kecepatan kueri kunci lebih cepat.

  Catatan

  Sebagai contoh, asumsikan Anda ingin memasukkan 10.000.000 elemen ke dalam kunci dan mengizinkan tingkat positif palsu sebesar 0,01. Ukuran kunci yang dibuat adalah 176 MB jika Anda menggunakan perintah BF.ADD, atau 16 MB jika Anda menggunakan perintah BF.RESERVE.

  Tabel berikut mencantumkan berbagai ukuran kunci yang didukung oleh perintah BF.RESERVE dan kapasitas awal serta tingkat positif palsu yang sesuai.

  Kapasitas (jumlah elemen)	positif salah:0,01	positif salah:0,001	positif salah:0,0001
  100.000	0,12 MB	0,25 MB	0,25 MB
  1.000.000	2 MB	2 MB	4 MB
  10.000.000	16 MB	32 MB	32 MB
  100.000.000	128 MB	256 MB	256 MB
  1.000.000.000	2 GB	2 GB	4 GB

  Saat Anda membuat kunci dengan kapasitas ultra-tinggi, Anda harus memperhatikan presisi tingkat kesalahan. Kunci dengan kapasitas ultra-tinggi dan presisi ultra-tinggi mungkin gagal dibuat karena memori instans tidak mencukupi.

• Ukuran kunci tidak dapat dikurangi karena elemen hanya dapat ditambahkan tetapi tidak dapat dihapus dari kunci. Untuk mencegah masalah kapasitas seperti kesalahan memori habis (OOM), kami sarankan Anda menerapkan solusi berikut:

  • Pisahkan data bisnis. Anda dapat membagi data bisnis untuk mencegah kunci besar yang memengaruhi kinerja kueri. Jika kunci besar ada, sebagian besar permintaan dibuat ke instans yang berisi kunci-kunci ini. Hal ini dapat menyebabkan hotkeys atau bahkan permintaan yang tidak seimbang.

    Anda dapat mendistribusikan data yang dipisahkan ke beberapa kunci. Jika data bisnis Anda disimpan dalam instans kluster Tair, Anda dapat mendistribusikan data yang dipisahkan ke beberapa node dalam instans untuk memastikan bahwa kunci besar dan hotkeys tidak terjadi.

  • Bangun ulang kunci secara berkala. Jika memungkinkan, Anda dapat menjalankan perintah DEL untuk menghapus data dari kunci, lalu menyisipkan data dari database backend ke dalam kunci untuk mengelola ukuran kunci.

    Anda juga dapat membuat beberapa kunci untuk digunakan secara bergantian. Dengan cara ini, ukuran kunci tunggal tetap sesuai. Manfaat dari solusi ini adalah Anda hanya perlu membuat kunci sekali. Namun, beberapa kunci harus dibuat dan beberapa memori mungkin terbuang.

Perintah yang didukung

BF.RESERVE

BF.RESERVE BFKEY 0.01 100

OK

BF.ADD

BF.ADD BFKEY item1

(integer) 1

BF.MADD

BF.MADD BFKEY item1 item2 item3

(integer) 1
(integer) 1
(integer) 1

BF.EXISTS

BF.EXISTS BFKEY item1

(integer) 1

BF.MEXISTS

BF.MEXISTS BFKEY item1 item5

(integer) 1
(integer) 0

BF.INSERT

BF.INSERT bfkey1 CAPACITY 10000 ERROR 0.001 ITEMS item1 item2 item3

(integer) 1
(integer) 1
(integer) 1

BF.INFO

BF.INFO bk1

1) "total_items:6,num_blooms:2"
2) "bytes:4 bits:32 hashes:7 hashwidth:64 capacity:3 items:3 error_ratio:0.01"
3) "bytes:16 bits:128 hashes:9 hashwidth:64 capacity:10 items:3 error_ratio:0.0025"