Bagaimana untuk mengelakkan penembusan cache? Artikel berikut akan membawa anda mempelajari tentang Penapis Bloom (Bloom Filter), alat yang berkuasa dalam Redis untuk mengelakkan penembusan cache. Saya harap ia akan membantu anda!
Penapis Bloom (Bloom Filter) ialah struktur data yang dicadangkan oleh Burton Howard Bloom pada tahun 1970. Ia sebenarnya vektor binari yang panjang dan satu siri fungsi pemetaan rawak. [Cadangan berkaitan: Tutorial Video Redis]
Penapis Bloom boleh digunakan untuk mendapatkan semula dengan cekap sama ada elemen berada dalam koleksi. Kelebihannya ialah kecekapan ruang dan masa pertanyaan jauh lebih baik daripada algoritma biasa Kelemahannya ialah ia mempunyai kadar salah pengiktirafan tertentu dan sukar untuk dipadamkan (biasanya tidak disokong dan memerlukan pelaksanaan tambahan).
Kadar positif palsu bermakna ia boleh dinilai bahawa elemen itu pasti tiada dalam set, ia boleh dinilai bahawa elemen itu mungkin berada dalam set, tetapi ia tidak boleh dinilai. bahawa elemen mesti berada dalam set.
Penapis Bloom adalah cekap kerana ia adalah struktur data kebarangkalian yang mengesahkan bahawa elemen pasti tiada dalam set, atau elemen itu mungkin berada dalam set. Sebab mengapa ia mungkin adalah kerana ia mempunyai kadar salah pengiktirafan tertentu, menjadikannya mustahil untuk 100% pasti bahawa elemen mesti berada dalam set.
Dalam kerja harian, terdapat keperluan umum untuk menentukan sama ada sesuatu elemen berada dalam set. Contohnya, senario berikut
Apabila menghadapi masalah seperti ini, intuisi kita biasanya memberitahu kita bahawa kita harus menggunakan struktur data seperti set untuk melaksanakannya. Sebagai contoh, simpan dahulu semua IP dalam pangkalan data senarai hitam IP ke dalam satu set, dan kemudian semak sama ada IP yang ditentukan wujud dalam set Jika ia wujud, ini bermakna IP mencecah senarai hitam.
Gunakan sekeping kod untuk mensimulasikan storan dan menyemak perpustakaan senarai hitam IP.
public class IPBlackList {
public static void main(String[] args) {
Set<String> set = new HashSet<>();
set.add("192.168.1.1");
set.add("192.168.1.2");
set.add("192.168.1.4");
System.out.println(set.contains("192.168.1.1"));
System.out.println(set.contains("192.168.1.2"));
System.out.println(set.contains("192.168.1.3"));
System.out.println(set.contains("192.168.1.4"));
}
}Bahan dalaman koleksi biasanya dilaksanakan menggunakan jadual cincang. Kelebihannya ialah pertanyaan itu sangat cekap, tetapi kelemahannya ialah ia menggunakan lebih banyak ruang storan.
Secara amnya apabila jumlah data agak kecil, kami akan menggunakan koleksi untuk penyimpanan. Ruang perdagangan untuk masa boleh meningkatkan kecekapan pertanyaan sambil menduduki ruang yang lebih sedikit.
Namun, apabila jumlah data yang disimpan agak besar, memakan banyak ruang akan menjadi masalah. Kerana data ini biasanya disimpan dalam memori proses untuk mempercepatkan kecekapan pertanyaan. Memori mesin biasanya terhad dan mesti digunakan secekap mungkin.
Sebaliknya, jadual hash perlu seimbang dari segi ruang dan kecekapan. Menyimpan bilangan elemen yang sama, jika kapasiti jadual hash lebih kecil, kebarangkalian konflik adalah lebih tinggi, dan lebih banyak masa akan dibelanjakan untuk menyelesaikan konflik, sekali gus menjejaskan prestasi.
Kemunculan penapis Bloom (Bloom Filter) dapat menyelesaikan masalah ini dengan baik. Di satu pihak, ia boleh menyimpan data dengan kurang memori, dan sebaliknya, ia boleh mencapai prestasi pertanyaan yang sangat cekap.
Mula-mula, cipta vektor binari dan tetapkan semua bit kepada 0
Kemudian, pilih fungsi cincang K digunakan untuk mencincang elemen K kali dan mengira indeks bit vektor.
Apabila elemen ditambah pada set, fungsi cincang K digunakan pada elemen masing-masing untuk menghasilkan nilai K sebagai subskrip dan tetapkan bit vektor yang sepadan kepada 1.
Jika anda ingin menyemak sama ada unsur wujud dalam set, gunakan kaedah pencincangan yang sama untuk menjana subskrip K dan semak sama ada bit yang sepadan bagi vektor adalah Semua adalah 1.
Jika semua adalah 1, elemen itu mungkin berada dalam set; sebaliknya (selagi 1 atau lebih bit adalah 0), elemen itu pasti tiada dalam set.
Andaikan terdapat penapis Bloom dengan kapasiti 15 bit dan 2 fungsi cincang, seperti yang ditunjukkan di bawah.
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |0||||||||||||||||
Tambah rentetan a dan cincang dua kali untuk mendapatkan subskrip 4 dan 10, tandakan bit yang sepadan dengan 4 dan 10 dari 0 hingga 1.
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1|||||1|||||||||
Tambah rentetan lain b, cincang dua kali untuk mendapatkan subskrip ialah 11, tandakan bit yang sepadan dengan 11 dari 0 hingga 1.
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1||||||1|1|||||||
Tambah rentetan lain c, cincang dua kali untuk mendapatkan subskrip 11 dan 12, dan tandakan bit yang sepadan dari 0 hingga 1.
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1|||||1|1|1||||||
Akhirnya tambah rentetan sam dan cincang dua kali untuk mendapatkan Subskrip adalah 0 dan 7, menandakan bit yang sepadan dari 0 hingga 1.
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |1||||1|||1|||1|1||||||
Di atas, kami menambah 4 rentetan, setiap rentetan dilakukan 2 kali Dalam cincang, yang sepadan 2 bit ditandakan sebagai 1, dan akhirnya terdapat 6 bit ditandakan sebagai 1 dan bukannya 8 bit.
Ini menunjukkan bahawa kedudukan yang diperoleh dengan mencincang elemen berbeza mungkin bertindih. Lebih banyak elemen terdapat, lebih tinggi kebarangkalian bertindih. Jika terdapat dua elemen dalam kedudukan bertindih, kita tidak boleh menilai bahawa mana-mana elemen mesti berada dalam set.
Jika anda ingin menyemak sama ada unsur wujud dalam set, anda hanya perlu mencincangnya dua kali dengan cara yang sama dan mencari bit yang sepadan dalam penapis Bloom untuk dua subskrip yang diperolehi. Jika 2 bit yang sepadan bukan semua 1, maka elemen itu pasti tiada dalam set. Jika 2 bit yang sepadan semuanya adalah 1, ini bermakna elemen itu mungkin berada dalam set atau ia mungkin tidak wujud.
Sebagai contoh, apabila menyemak sama ada rentetan b wujud dalam set, 2 subskrip yang diperoleh melalui pencincangan ialah kedua-duanya 11. Semak dan dapatkan bit yang sepadan dengan 11 ialah 1. Namun, ini tidak bermakna b mesti ada dalam set. Ini kerana subskrip dicincang rentetan c juga mengandungi 11. Ada kemungkinan rentetan c berada dalam set, tetapi b tidak wujud Ini menyebabkan kesilapan pengecaman, juga dikenali sebagai positif palsu.
Semak rentetan foo sekali lagi, subskrip yang diperolehi dengan pencincangan masing-masing adalah 8 dan 13, dan bit yang sepadan semuanya 0. Oleh itu, rentetan foo pasti tiada dalam set.
Prinsip matematik di sebalik penapis Bloom ialah
Kebarangkalian dua nombor rawak sepenuhnya berlanggar adalah sangat kecil, jadi ia boleh digunakan dalam sangat kecil Di bawah keadaan kadar pengecaman palsu yang rendah, sejumlah besar maklumat disimpan dalam ruang yang kecil.
Kadar salah pengiktirafan (FPP, false positive probabilistic) dikira seperti berikut.
Dengan mengandaikan bahawa saiz penapis bloom ialah m bit dan n elemen disimpan, gunakan fungsi cincang k untuk mengira lokasi storan elemen.
1/m dan kebarangkalian bahawa sebarang bit ialah 0 ialah 1-1/m; menambah 1 elemen, Selepas k kali pencincangan, kebarangkalian bahawa sebarang bit ialah 0 ialah (1-1/m)^k, dan kebarangkalian sebarang bit menjadi 1 ialah 1-(1-1/m)^k; (1-1/m)^kn elemen, maka Kebarangkalian bahawa sebarang bit sudah pun 1 adalah sama seperti di atas, dengan kebarangkalian 1-(1-1/m)^kn. Oleh itu, kebarangkalian bahawa semua k bit ialah 1 ialah: n1-(1-1/m)^kn(1-(1-1/m)^kn)^kApabila nilai n agak besar, $(1-(1-1/m)^{kn})^k$ dengan mengandaikan bahawa saiz penapis mekar $(1-e^{-kn/m})^k$ ialah 16 bit, k ialah 8, dan elemen storan ialah 1, maka kebarangkalian kesilapan pengecaman (positif palsu) ialah lima daripada sepuluh ribu (5/10000).
Pada masa ini, m, sebenarnya ini bermakna 1 elemen menggunakan 16 bit ruang untuk menyimpan. n
adalah sama, m/n=16 mempunyai kadar salah pengiktirafan yang sama apabila 16/1, 32/2, 64/4, dsb.
Tapak webkBloom Filter - the mathm/n memberikan jadual kadar pengecaman palsu bagi penapis Bloom, yang boleh disemak dan ditangani dengan mudah oleh
, yang berbeza diberi Kadar pengecaman palsu di bawah nilai. mMenyelesaikan kadar pengecaman palsunkKaedah biasa untuk menyelesaikan kadar pengecaman palsu termasuk
Senarai Putih
Pengesahan Menjejak Kembali
Pada masa ini, anda boleh menyimpan perpustakaan spam ini dahulu dalam penapis Bloom Apabila menerima e-mel, anda boleh menapis kebanyakan e-mel biasa dahulu dengan cekap melalui penapis Bloom.
Untuk sebilangan kecil hits (mungkin) e-mel spam, sesetengah daripadanya mungkin e-mel biasa.
再创建一个白名单库，当在布隆过滤器中判断可能为垃圾邮件时，通过查询白名单来确认是否为正常邮件。
对于没在白名单中的邮件，默认会被移动到垃圾箱。通过人工识别的方式，当发现垃圾箱中存在正常邮件的时候，将其移入白名单。
很多时候，使用布隆过滤器是为了低成本，高效率的拦截掉大量数据不在集合中的场景。例如
这是布隆过滤器非常典型的应用场景，先过滤掉大部分请求，然后只处理少量不明确的请求。
这个方法，和白名单库的区别是，不需要再另外建立一套库来处理，而是使用本来就已经存在的数据和逻辑。
例如 Google Bigtable 查询数据行本来就是需要查的，只不过使用布隆过滤器拦截掉了大部分不必要的请求。而 IP 是否为黑名单也是需要查询的，同样是先使用布隆过滤器来拦截掉大部分IP。
而上面垃圾邮件的处理，对于可能为垃圾邮件的情况，不是通过完整的垃圾邮件库再查询一次进行确认，而是用增加白名单来进行判断的方式。因为通常来说，白名单库会更小，便于缓存。
这里所说的回源，实际上是对可能被误识别的请求，最后要回到数据源头或逻辑确认一次。
Guava 中就提供了一种 Bloom Filter 的实现。
要使用 Bloom Filter，需要引入 guava 包
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>23.0</version>
</dependency>下面对布隆容器的误判率进行测试，分2步
往过滤器中放一百万个数，然后去验证这一百万个数是否能通过过滤器
另外找一万个数，去检验漏网之鱼的数量
/**
* 测试布隆过滤器(可用于redis缓存穿透)
*
* @author 敖丙
*/
public class TestBloomFilter {
private static int total = 1000000;
private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total);
// private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total, 0.001);
public static void main(String[] args) {
// 初始化1000000条数据到过滤器中
for (int i = 0; i < total; i++) {
bf.put(i);
}
// 匹配已在过滤器中的值，是否有匹配不上的
for (int i = 0; i < total; i++) {
if (!bf.mightContain(i)) {
System.out.println("有坏人逃脱了~~~");
}
}
// 匹配不在过滤器中的10000个值，有多少匹配出来
int count = 0;
for (int i = total; i < total + 10000; i++) {
if (bf.mightContain(i)) {
count++;
}
}
System.out.println("误伤的数量：" + count);
}
}运行结果
误伤的数量：320
运行结果表示，遍历这一百万个在过滤器中的数时，都被识别出来了。一万个不在过滤器中的数，误伤了320个，错误率是0.03左右。
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions) {
return create(funnel, (long) expectedInsertions);
}
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
}
public static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp) {
return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);
}
static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
......
}Bloom Filter 一共四个 create 方法，不过最终都是走向第4个。看一下每个参数的含义
funnel：数据类型(一般是调用Funnels工具类中的)
expectedInsertions：期望插入的值的个数
fpp： 错误率(默认值为0.03)
strategy： 哈希算法 Bloom Filter的应用
更多编程相关知识，请访问：编程视频！！
Atas ialah kandungan terperinci Analisis mendalam tentang Penapis Bloom dalam Redis. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
Perisian pangkalan data yang biasa digunakan
Apakah pangkalan data dalam memori?
Yang manakah mempunyai kelajuan bacaan yang lebih pantas, mongodb atau redis?
Cara menggunakan redis sebagai pelayan cache
Bagaimana redis menyelesaikan ketekalan data
Bagaimanakah mysql dan redis memastikan konsistensi penulisan dua kali?
Apakah data yang biasanya disimpan oleh redis cache?
Apakah 8 jenis data redis
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
