Tair (Redis® OSS-Compatible):TairBloom

Ikhtisar

Di Redis, Anda dapat mengimplementasikan fungsionalitas serupa menggunakan Hash, Set, atau bitset yang disimpan dalam String. Namun, metode-metode tersebut baik mengonsumsi memori dalam jumlah besar maupun tidak dapat diskalakan secara dinamis sambil mempertahankan tingkat positif palsu yang stabil. TairBloom ideal untuk kasus penggunaan yang memerlukan pengujian keanggotaan yang efisien pada dataset besar dan dapat mentolerir tingkat positif palsu yang kecil. Anda dapat langsung menggunakan API TairBloom tanpa wrapper kustom atau implementasi lokal.

Fitur utama

• Jejak memori rendah.

• Mendukung auto-scaling.

• Tingkat positif palsu yang dapat dikustomisasi dan tetap stabil selama auto-scaling.

Use Cases

Praktik terbaik

void recommendedSystem(userid) {
    while (true) {
        // Dapatkan ID artikel kandidat.
        docid = getDocByRandom()
        if (bf.exists(userid, docid)) {
            // Artikel kemungkinan besar sudah direkomendasikan, jadi lewati.
            continue;
        } else {
            // Artikel pasti belum direkomendasikan, jadi kirimkan.
            sendRecommendMsg(docid);
            // Catat rekomendasi tersebut.
            bf.add(userid, docid);
            break;
        }
    }
}

bool crawlerSystem( ) {
    while (true) {
        // Dapatkan URL untuk di-crawl.
        url = getURLFromQueue()
        if (bf.exists(url_bloom, url)) {
            // URL kemungkinan besar sudah di-crawl, jadi lewati.
            continue;
        } else {
            // Unduh konten URL.
            doDownload(url)
            // Tambahkan URL ke TairBloom.
            bf.add(url_bloom, url);
        }
    }
}

Cara kerja

TairBloom adalah implementasi Scalable Bloom Filter. TairBloom mendukung auto-scaling dan mempertahankan tingkat positif palsu yang stabil. Scalable Bloom Filter merupakan versi yang dioptimalkan dari bloom filter. Bagian-bagian berikut menjelaskan prinsip dasar bloom filter dan Scalable Bloom Filter.

• Bloom filter

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

  Bloom filter baru adalah array bit berukuran m bit, dengan semua bit awalnya diatur ke 0. Bloom filter juga menggunakan k fungsi hash berbeda yang menghasilkan distribusi acak seragam, di mana k adalah konstanta yang lebih kecil dari m. Saat Anda menambahkan elemen ke bloom filter, k fungsi hash memetakan elemen tersebut ke k posisi dalam array bit, dan bit-bit pada posisi tersebut diatur ke 1. Satu bit dapat digunakan bersama oleh beberapa elemen. Gambar berikut menunjukkan bagaimana elemen X1 dan X2 dimasukkan ke dalam bloom filter dengan k = 3.

  Untuk mengkueri suatu elemen, k fungsi hash yang sama digunakan untuk mendapatkan k posisi bit yang sesuai. Jika semua bit pada posisi tersebut bernilai 1, elemen tersebut dianggap ada dalam bloom filter. Jika ada satu bit saja yang bernilai 0, elemen tersebut pasti tidak ada. Gambar berikut menunjukkan cara memeriksa keberadaan Y1 dan Y2 dalam bloom filter.

  Seperti yang ditunjukkan pada gambar, meskipun elemen Y2 tidak pernah dimasukkan ke dalam bloom filter, filter tersebut melaporkan bahwa Y2 ada. Ini disebut positif palsu. Berdasarkan hal ini, kita dapat merangkum karakteristik bloom filter sebagai berikut:

  • Posisi bit dapat digunakan bersama oleh elemen yang berbeda.

  • Positif palsu dapat terjadi. Semakin banyak elemen dalam bloom filter, semakin tinggi probabilitas positif palsu. Namun, negatif palsu tidak terjadi. Jika suatu elemen dilaporkan tidak ada, maka elemen tersebut pasti tidak ada.

  • Elemen dapat ditambahkan ke bloom filter tetapi tidak dapat dihapus. Hal ini karena posisi bit dapat digunakan bersama, dan mengosongkan bit untuk satu elemen dapat memengaruhi elemen lain.

• Scalable Bloom Filter

  Saat semakin banyak elemen ditambahkan ke bloom filter, tingkat positif palsu meningkat. Untuk menjaga tingkat positif palsu tetap stabil, ukuran bloom filter harus ditingkatkan. Namun, bloom filter standar tidak dapat diubah ukurannya. Scalable Bloom Filter mengatasi hal ini dengan membuat bloom filter baru dan menumpuknya menjadi satu filter logis.

  Gambar berikut menunjukkan model dasar Scalable Bloom Filter (SBF), yang terdiri dari dua lapisan: BF0 dan BF1. Awalnya, SBF hanya berisi lapisan BF0. Misalkan setelah elemen a, b, dan c dimasukkan, lapisan BF0 tidak lagi dapat mempertahankan tingkat positif palsu yang ditentukan pengguna. Pada titik ini, lapisan baru (BF1) dibuat. Elemen-elemen berikutnya d, e, dan f dimasukkan ke lapisan BF1. Demikian pula, saat lapisan BF1 tidak lagi memenuhi tingkat positif palsu, lapisan baru (BF2) dibuat, dan seterusnya. Untuk informasi lebih lanjut, lihat Scalable Bloom Filter.

  Penting

  Saat TairBloom melakukan auto-scaling, lapisan baru memiliki kapasitas dua kali lipat dan penggunaan memori empat kali lipat dari lapisan sebelumnya.

  Setiap lapisan tambahan meningkatkan waktu kueri karena kueri mungkin perlu melintasi beberapa lapisan bloom filter. Scalable Bloom Filter selalu memasukkan data ke lapisan terbaru, dan kueri dimulai dari lapisan terbaru lalu berlanjut mundur ke lapisan pertama (BF0). Akibatnya, operasi auto-scaling pada TairBloom dapat membuat kunci besar dan menurunkan performa. Penurunan performa meningkat seiring bertambahnya jumlah elemen.

  Dalam praktiknya, Anda harus menghindari memicu auto-scaling TairBloom dan memperlakukan fitur ini sebagai pengaman. Sediakan cukup memori untuk instans guna mencegah kegagalan penulisan setelah kejadian auto-scaling, yang dapat memicu proses eviksi data berkepanjangan dan membuat instans tidak responsif. Anda dapat menggunakan perintah BF.INFO untuk memeriksa apakah suatu kunci akan segera memicu kejadian auto-scaling. Saat jumlah items di lapisan terbaru mencapai capacity-nya, kejadian auto-scaling akan segera terjadi.

  Saat kapasitas aktual melebihi kapasitas yang telah ditentukan, TairBloom melakukan auto-scaling untuk memastikan operasi penulisan dapat berlanjut, sehingga mencegah insiden produksi. Setelah TairBloom menyelesaikan operasi auto-scaling, segera bangun ulang kunci tersebut untuk meningkatkan performa dan mengurangi risiko yang terkait dengan kejadian auto-scaling berikutnya.

Prasyarat

Catatan penggunaan

• Perintah dalam topik ini beroperasi pada data TairBloom dalam instans Tair.

• Rencanakan kapasitas awal dan tingkat positif palsu terlebih dahulu. Jika kapasitas yang diharapkan untuk kunci target jauh lebih besar dari 100, gunakan perintah BF.RESERVE untuk membuat kunci TairBloom. Hindari membuat kunci dengan perintah BF.ADD.

  Daftar berikut menjelaskan perbedaan antara menjalankan perintah BF.ADD dan perintah BF.RESERVE.

  • BF.ADD (atau BF.MADD): Jika kunci target tidak ada saat perintah dijalankan, Tair secara otomatis membuat instans TairBloom dengan kapasitas default 100 dan tingkat positif palsu (error_rate) 0,01. Jika kapasitas yang Anda butuhkan jauh lebih besar dari 100, Anda dapat menambahkan lebih banyak elemen nanti dengan memperluas kapasitas. Namun, saat jumlah lapisan internal dalam TairBloom meningkat, operasi kueri harus melintasi beberapa Bloom filter, yang secara signifikan menurunkan performa.

  • BF.RESERVE (atau BF.INSERT): Saat menjalankan perintah ini, Anda harus menetapkan capacity (kapasitas awal). Perintah ini menginisialisasi kapasitas di lapisan pertama kunci TairBloom. Kunci TairBloom dengan lebih sedikit lapisan memberikan kueri yang lebih cepat.

  Catatan

  Sebagai contoh, untuk memasukkan 10.000.000 elemen dengan tingkat positif palsu 0,01, membuat kunci TairBloom dengan perintah BF.ADD memerlukan memori 176 MB. Sebaliknya, membuat kunci dengan perintah BF.RESERVE hanya memerlukan 16 MB.

  Tabel berikut mencantumkan penggunaan memori untuk kunci yang dibuat dengan kapasitas awal dan tingkat positif palsu berbeda menggunakan perintah BF.RESERVE. Nilai-nilai ini hanya sebagai referensi.

  Kapasitas	Tingkat positif palsu: 0,01	Tingkat positif palsu: 0,001	Tingkat positif palsu: 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 membuat kunci dengan kapasitas sangat besar, pertimbangkan error_rate. Kunci dengan kapasitas sangat besar dan presisi tinggi (nilai error_rate rendah) dapat gagal karena memori instans tidak mencukupi.

• TairBloom memungkinkan Anda memasukkan elemen baru tetapi tidak menghapus elemen yang sudah ada. Akibatnya, penggunaan memori kunci TairBloom hanya meningkat. Untuk mencegah kunci TairBloom tumbuh secara berlebihan dan menyebabkan error out of memory (OOM), pertimbangkan saran berikut.

  • Pisahkan data bisnis: Pisahkan dan perhalus data bisnis Anda untuk menghindari penyimpanan data dalam jumlah besar dalam satu kunci TairBloom. Hal ini tidak hanya mencegah kunci menjadi terlalu besar dan memengaruhi performa kueri, tetapi juga mencegah sebagian besar trafik kueri diarahkan ke instans Redis tempat kunci tersebut berada, yang dapat menciptakan hot key dan menyebabkan ketimpangan akses.

    Pisahkan data bisnis Anda dan distribusikan data tersebut ke beberapa kunci TairBloom. Jika Anda menggunakan instans cluster, Anda dapat mendistribusikan kunci TairBloom ke berbagai node dalam cluster untuk menyeimbangkan memori dan trafik, yang membantu Anda memanfaatkan cluster terdistribusi secara optimal.

  • Bangun ulang secara berkala: Jika bisnis Anda memungkinkan, Anda dapat membangun ulang kunci TairBloom secara berkala. Gunakan perintah DEL untuk menghapus kunci TairBloom, lalu tarik data dari database backend untuk membangunnya kembali. Hal ini membantu mengontrol ukuran kunci TairBloom.

    Anda juga dapat membuat beberapa kunci TairBloom sejak awal dan melakukan rotasi di antara kunci-kunci tersebut untuk mengontrol ukuran masing-masing kunci. Pendekatan ini menghindari pembangunan ulang yang sering tetapi mengonsumsi lebih banyak memori.

Referensi perintah

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"

FAQ