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!
Ikhtisar
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.
Pengenalan soalan
Dalam kerja harian, terdapat keperluan umum untuk menentukan sama ada sesuatu elemen berada dalam set. Contohnya, senario berikut
- Memandangkan pangkalan data senarai hitam IP, semak sama ada IP yang ditentukan berada dalam senarai hitam?
- Apabila menerima e-mel, bagaimana untuk menentukan sama ada alamat e-mel adalah spam?
- Dalam perisian pemprosesan perkataan, semak sama ada perkataan Inggeris dieja dengan betul?
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"));
}
}Salin selepas log masuk
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.
Prinsip Asas
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.
Tambah elemen
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.
Menyemak elemen
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.
Demo
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|0||||||||||||||||
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|||||1|||||1|||||||||
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|||||1||||||1|1|||||||
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|||||1|||||1|1|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
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
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.
- menambah 1 elemen, maka kebarangkalian bahawa sebarang bit ialah 1 ialah
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 , dan kebarangkalian bahawa sebarang bit ialah 1 ialah - ; ialah
(1-1/m)^k, dan kebarangkalian sebarang bit menjadi 1 ialah 1-(1-1/m)^k; - Jika elemen baharu ditambahkan pada penapis Bloom yang sudah mempunyai
(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: , iaitu kadar salah pengiktirafan unsur yang baru dimasukkan. 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
Oleh itu, apabila
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
Cara biasa untuk menyelesaikan kadar pengecaman palsu adalah dengan mewujudkan senarai putih yang lebih kecil untuk menyimpan mereka yang mungkin salah dikenal pasti data . Ambil penapisan spam sebagai contoh. Katakan kami mempunyai perpustakaan spam yang menapis spam apabila menerima e-mel.
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，Apache HBase以及Apache Cassandra和PostgreSQL 使用 Bloom 过滤器来减少对不存在的行或列的磁盘查找。避免进行昂贵的磁盘查找，可大大提高数据库查询操作的性能。
- 在谷歌浏览器用于使用布隆过滤器来识别恶意URL的网页浏览器。首先会针对本地 Bloom 过滤器检查所有 URL，只有在 Bloom 过滤器返回肯定结果的情况下，才对执行的 URL 进行全面检查（如果该结果也返回肯定结果，则用户会发出警告）。
- 拦截掉大量非IP黑名单请求，对于少量可能在黑名单中的IP，再查询一次黑名单库。
这是布隆过滤器非常典型的应用场景，先过滤掉大部分请求，然后只处理少量不明确的请求。
这个方法，和白名单库的区别是，不需要再另外建立一套库来处理，而是使用本来就已经存在的数据和逻辑。
例如 Google Bigtable 查询数据行本来就是需要查的，只不过使用布隆过滤器拦截掉了大部分不必要的请求。而 IP 是否为黑名单也是需要查询的，同样是先使用布隆过滤器来拦截掉大部分IP。
而上面垃圾邮件的处理，对于可能为垃圾邮件的情况，不是通过完整的垃圾邮件库再查询一次进行确认，而是用增加白名单来进行判断的方式。因为通常来说，白名单库会更小，便于缓存。
这里所说的回源，实际上是对可能被误识别的请求，最后要回到数据源头或逻辑确认一次。
Guava中的布隆容器的实现
Guava 中就提供了一种 Bloom Filter 的实现。
guava包引入
要使用 Bloom Filter，需要引入 guava 包
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>23.0</version>
</dependency>Salin selepas log masuk
误判率测试
下面对布隆容器的误判率进行测试，分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);
}
}Salin selepas log masuk
运行结果
误伤的数量：320
Salin selepas log masuk
运行结果表示，遍历这一百万个在过滤器中的数时，都被识别出来了。一万个不在过滤器中的数，误伤了320个，错误率是0.03左右。
Bloom Filter 源码分析
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) {
......
}Salin selepas log masuk
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!
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
