Persyaratan: Baru-baru ini, saya melihat video algoritma Redis Bloom di Bilibili untuk memecahkan masalah penetrasi cache, sederhananya, tambahkan lapisan penilaian logis sebelum mengakses database untuk menentukan apakah data tersebut ada, dan jika demikian, akses database. Misalnya, jika situs web adalah sistem berita, URL artikel dihasilkan oleh ID kunci primer yang bertambah sendiri (format URL example:/news-1.html), situs web mungkin hanya memiliki puluhan ribu artikel dan cache.
Awalnya:
Minta sumber daya berita -> Menentukan apakah cache ada -> Presence -> Cache mengembalikan data.
Minta sumber daya berita -> Tentukan apakah cache ada -> tidak ada -> Kueri dari database -> Present -> Cache dan kembalikan data.
Meminta sumber daya berita -> Menentukan apakah cache ada -> tidak ada -> Kueri dari database -> Tidak ada -> Mengembalikan kesalahan 404.
Sekarang:
Minta sumber berita -> algoritma Bloom -> Existence -> Ikuti logika aslinya.
Minta sumber daya berita -> algoritma Bloom -> tidak ada -> mengembalikan kesalahan 404 secara langsung.
Filter Mekar
Algoritma BloomFilter adalah algoritma penjadwalan data besar. Dalam himpunan dengan sejumlah besar data, dapat ditentukan secara akurat bahwa suatu objek tidak ada dalam himpunan; Dimungkinkan untuk menilai objek dalam satu set dan memakan sedikit ruang. diaTidak cocok untuk situasi yang membutuhkan akurasi tinggi dan nol kesalahan。 Penggunaan ruang yang efisien dicapai dengan mengorbankan akurasi parsial.
Algoritma Bloom adalah metode yang didasarkan padaMengorbankan akurasi tertentu dengan imbalan algoritme pemfilteran dengan konsumsi memori rendah, yang dapat mewujudkan pemfilteran, deduplikasi, dan operasi lain dari sejumlah besar data.
Algoritma Bloom hanyalah konsep abstrak dan dapat diimplementasikan dalam banyak cara, dan penggunaan BitMap di Redis dalam artikel hanyalah implementasi sederhana.
Referensi:Login hyperlink terlihat.
Pengenalan BitMap
BitMap adalah bitmap, yang sebenarnya merupakan array byte, diwakili dalam biner.Hanya ada dua angka, 0 dan 1, bitmap adalah menggunakan setiap bit biner untuk menyimpan atau menandai nilai yang sesuai dengan suatu elemen. Biasanya digunakan untuk menentukan apakah data tertentu ada atau tidak, karena disimpan dalam bit, sehingga Bitmap sendiri akan sangat menghemat ruang penyimpanan.
Seperti yang ditunjukkan pada gambar di bawah ini, string disimpan dalam bentuk biner di komputer.
Jenis data BitMap di Redis
Jenis data yang disediakan oleh Redis adalah BitMap, dan setiap bit sesuai dengan dua status: 0 dan 1. Meskipun penyimpanan internal masih dalam jenis String, Redis memberikan beberapa instruksi untuk memanipulasi BitMap secara langsung, yang dapat dianggap sebagai array bit, dan subskrip array adalah offset.
Keuntungannya adalah:Overhead memori rendah dan efisiensi tinggiDan operasinya sederhana.
Hemat ruang: Bit digunakan untuk mewakili nilai atau status elemen, di mana kunci adalah nilai elemen yang sesuai. Faktanya, 8 bit dapat membentuk byte, sehingga hemat ruang.
Efisiensi tinggi: Kompleksitas waktu setbit dan getbit adalah O(1), dan efisiensi bit lainnya juga tinggi.
Berikut adalah contoh penggunaan kumpulan set dan penyimpanan BitMap:
| Tipe data | Setiap userid memakan ruang | Jumlah pengguna yang perlu disimpan | Semua menempati memori | | mengeset | 32 bit adalah 4 byte (dengan asumsi userid menggunakan bilangan bulat, banyak situs web benar-benar menggunakan bilangan bulat panjang) | 50,000,000 | 32 bit * 50.000.000 = 200 MB | | Bitmap | 1 bit | 100,000,000 | 1 bit * 100.000.000 = 12,5 MB |
Waktu sedikit membentang
| | Suatu hari | Satu bulan | Satu tahun | | mengeset | 200 juta | 6G | 72G | | Bitmap | 12,5 juta | 375 juta | 4.5G |
Setelah perhitungan, ditemukan bahwa seiring bertambahnya waktu, jumlah data yang akan direkam meningkat, dan kontrasnya menjadi lebih jelas, dan BitMap memakan lebih sedikit ruang daripada yang ditetapkan.
Redis memberikan petunjuk berikut untuk mengoperasikan BitMap:
| perintah | Menggambarkan | Versi yang tersedia | Kompleksitas waktu | | Login hyperlink terlihat. | Atur atau hapus bit pada offset yang ditentukan untuk nilai string yang disimpan dalam kunci. | >= 2.2.0 | O(1) | | Login hyperlink terlihat. | Untuk nilai string yang disimpan dalam kunci, dapatkan bit pada offset yang ditentukan. | >= 2.2.0 | O(1) | | Login hyperlink terlihat. | Menghitung jumlah bit dalam string tertentu yang diatur ke 1. | >= 2.6.0 | O(N) | | Login hyperlink terlihat. | Mengembalikan posisi bit biner di bitmap di mana nilai pertama adalah bit. | >= 2.8.7 | O(N) | | Login hyperlink terlihat. | Manipulasi bit pada satu atau beberapa kunci string yang menahan bit biner. | >= 2.6.0 | O(N) | | Login hyperlink terlihat. | Perintah BITFIELD dapat beroperasi pada beberapa rentang bit secara bersamaan dalam satu panggilan. | >= 3.2.0 | O(1) |
Dokumentasi perintah:Login hyperlink terlihat.
Sekarang setelah Anda memiliki pemahaman singkat tentang algoritma dan fitur Bitmap serta sintaks Redis, mari kita gunakan redis untuk melakukan operasi sederhana.
Sintaks SETBIT:Nilai offset kunci SETBIT
Atur artikel id:9, 10, 156 ke 1, dan perintahnya adalah sebagai berikut:
Sintaks GETBIT: Offset kunci GETBIT
Untuk menentukan apakah id: 10 atau 11 ada, perintahnya adalah sebagai berikut:
.NET/C# memanipulasi jenis BitMap Redis
Kami mempelajari tentang beberapa perintah BitMap dalam redis dan cara mengoperasikannya secara terprogram. Buat proyek konsol .NET 3.1 baru, referensikan paket StackExchange.Redis, dan gunakan perintah berikut:
Kode sumbernya adalah sebagai berikut:
Ada banyak skenario aplikasi bitmap lainnya untuk Redis, sebagai berikut:
- Ini dapat digunakan sebagai filter Bloom sederhana untuk menentukan apakah pengguna telah melakukan tindakan tertentu.
- Statistik aktivitas harian pengguna, aktivitas bulanan, dan tingkat retensi
- Wujudkan statistik jumlah peluncuran pengguna
- Kehadiran online pengguna dan statistik orang
(Akhir)
|
Diposting pada 02/01/2023 17.37.01
|
|
|
|
Tuan tanah|
Diposting pada 02/01/2023 17.41.56
|
Diposting pada 02/01/2023 20.42.47
|
