В этой статье мы обсудим фильтр Блума с точки зрения Xiaobai.Если вы профессионал, или вы умны, или действительно хотите полностью понять фильтр Блума, вы можете двигаться дальше.
Я не знаю, когда это началось, изначально неизвестный фильтр Блума вдруг стал известен, как будто он был в Интернете, занимался разработкой, никто об этом не знал, никто не знал, даже маленькие друзья, которым было все равно. технология слушала его мимо его имени. Я также потратил много времени на изучение фильтров Блума и прочитал много блогов, но, к сожалению, я не профессионал, я не настолько умен, и я ленив... вверх» Бесконечное перевоплощение следует рассматривать как понимание основной идеи фильтра Блума, поэтому я хочу поделиться ею с вами.
Применение фильтров Блума
Давайте сначала рассмотрим сценарии применения фильтра Блума, чтобы все знали, на что способен волшебный фильтр Блума.
проникновение в кеш
Мы часто помещаем некоторые данные в кеши, такие как Redis, например сведения о продукте. Таким образом, когда приходит запрос запроса, мы можем напрямую получить данные из кеша по идентификатору продукта, не читая базу данных, Это самый простой, распространенный и эффективный способ повышения производительности. Общий процесс запроса запроса выглядит следующим образом: сначала проверяем кеш, если кеш есть, возвращаем напрямую, если кеша нет, идем в базу на запрос, а потом кладем данные из базы в кеш, все выглядит неплохо. Но что произойдет, если прямо сейчас поступает много запросов, и все они запрашивают идентификатор продукта, которого не существует? Так как product ID не существует, то не должно быть кэша, не должно быть кеша, тогда к базе данных будет отправлено большое количество запросов, внезапно возникнет нагрузка на базу данных, и базу можно убить. Хотя есть много способов решить эту проблему, наш главный герой — «Фильтр Блума», да, «Фильтр Блума» может решить (смягчить) проблему проникновения в кэш. А почему оно называется «рельефным», вы поймете, когда прочитаете.
Большой объем данных, чтобы определить, есть ли в нем данное
Сейчас есть большой объем данных, и размер этих данных намного превысил память сервера.Теперь я даю вам еще один кусок данных, как судить, есть в нем данные вам данные или нет. Если память сервера достаточно велика, то использование HashMap является хорошим решением.Теоретическая временная сложность может достигать O(1), но сейчас размер данных намного превышает память сервера, поэтому HashMap использовать нельзя. , Это Вы можете использовать «Фильтр Блума», чтобы решить эту проблему. Но все равно будет определенная «скорость ошибочных суждений».
Что такое фильтр Блума
Фильтр Блума был предложен человеком по имени «Блум». Сам по себе он представляет собой очень длинный двоичный вектор. Поскольку это двоичный вектор, очевидно, что он хранит либо 0, либо 1.
Теперь мы создаем новый фильтр Блума длиной 16, значение по умолчанию равно 0, как показано ниже:
Теперь нам нужно добавить данные:
Мы вычисляем Hash1 (данные) = 5 с помощью некоторого метода вычисления, такого как Hash1, и меняем нижний индекс 5 на 1 следующим образом:
Мы вычисляем Hash2(data)=9 с помощью некоторого метода вычисления, такого как Hash2, и меняем нижний индекс 9 на 1 следующим образом:
Или с помощью какого-либо метода вычисления, такого как Hash3, после вычисления Hash3 (данные) = 2 мы изменим нижний индекс 2 на 1, как показано ниже:
Таким образом, только что добавленные данные занимают три сетки фильтра Блума «5», «9» и «2».
Видно, что только из самого фильтра Блума вообще не сохраняются полные данные, но используется ряд функций случайного отображения для вычисления положения, а затем заполнения двоичного вектора.
Какая от этого польза? Например, если вам сейчас дан другой фрагмент данных, и вы хотите оценить, повторяются ли данные, что вы делаете?
Вам нужно только использовать три вышеуказанных фиксированных метода расчета, чтобы вычислить, какие сетки занимают данные, а затем посмотреть, все ли сетки равны 1. Если какая-либо сетка не равна 1, это означает, что число не входит в их число. Это легко понять. Например, данные, которые вы только что добавили, предоставляются вам. Благодаря трем фиксированным методам расчета результат расчета должен быть точно таким же, как указано выше, и он также занимает фильтр Блума «5». " 9", "2" три сетки.
Однако есть проблема, которую необходимо отметить: если в этих сетках размещены все единицы, это не обязательно означает, что данные данные должны быть повторены, возможно, результаты других данных, рассчитанных тремя фиксированными методами расчета, будут одинаковыми. Это тоже легко понять, например, если нам нужно определить, равны ли объекты, мы не можем просто определить, равны ли их хэш-значения.
Другими словами, фильтр Блума может только определить, должны ли данные существовать, но не может определить, должны ли они существовать.
Само собой разумеется, что после введения процесса добавления и запроса необходимо ввести процесс удаления, но, к сожалению, фильтру Блума трудно удалить данные, почему? Подумайте об этом, например, если вы хотите удалить только что предоставленные вам данные, вы меняете три сетки «5», «9» и «2» на 0, но другие данные также могут быть сопоставлены с «5». ","9" ","2" три сетки, это не перепутано?
Я считаю, что после моего введения у всех должно быть простое представление о фильтре Блума, по крайней мере, вы должны знать преимущества и недостатки фильтра Блума:
- Преимущества: поскольку сохраненные данные не являются полными, они занимают очень мало памяти, а скорость запроса достаточно высока для новых дополнений;
- Недостатки: по мере увеличения данных увеличивается частота ошибочных суждений; данные нельзя удалить; он может только определить, должны ли данные существовать, но не может определить, должны ли данные существовать.
Как видите, преимущества и недостатки фильтра Блума столь же очевидны.
В приведенном выше примере длина двоичного вектора равна 16, а позиция вычисляется с помощью трех функций случайного отображения.В реальной разработке, если вы хотите добавить большой объем данных, только 16 бит недостаточно.Чтобы сделать Частота ложных срабатываний Ниже мы также можем использовать больше функций случайного отображения и более длинные двоичные векторы для расчета позиции.
Guava реализует фильтр Блума
Теперь я считаю, что у вас должно быть более перцептивное понимание фильтра Блума. Основная идея фильтра Блума на самом деле не сложна. Сложность заключается в том, как разработать функцию случайного отображения, сколько раз отображать и сколько длина бинарного вектора задана для сравнения. Ну, это может быть не то, с чем могут справиться обычные разработчики. К счастью, боссы Google предоставляют нам готовые компоненты, чтобы помочь нам реализовать фильтры Блума. Теперь давайте посмотрим, как Боссы Google посылают нам Дайте нам "подарок".
Сначала введите «подарок» в помпон:
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>19.0</version>
</dependency>
Затем вы можете протестировать:
private static int size = 1000000;//预计要插入多少数据
private static double fpp = 0.01;//期望的误判率
private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
public static void main(String[] args) {
//插入数据
for (int i = 0; i < 1000000; i++) {
bloomFilter.put(i);
}
int count = 0;
for (int i = 1000000; i < 2000000; i++) {
if (bloomFilter.mightContain(i)) {
count++;
System.out.println(i + "误判了");
}
}
System.out.println("总共的误判数:" + count);
}
Простой анализ кода: Мы определяем фильтр Блума с двумя важными параметрами, а именно с тем, сколько данных мы ожидаем вставить, и с нашей ожидаемой частотой ложных срабатываний, которая не может быть равна 0. Я вставил 0-1000000 в фильтр Блума, а затем использовал 1000000-2000000 для проверки частоты ложных срабатываний.
результат операции:
1999501误判了
1999567误判了
1999640误判了
1999697误判了
1999827误判了
1999942误判了
总共的误判数:10314
Всего существует 1 миллион данных, которых не существует, и было сделано 10 314 ошибочных суждений.
Redis реализует фильтр Блума
Вышеприведенное использование гуавы для реализации фильтра Блума заключается в том, чтобы поместить данные в локальную память, и совместное использование фильтра Блума не может быть реализовано.Мы также можем поместить данные в Redis и использовать Redis для реализации фильтра Блума. данные, которые мы хотим использовать Структура растровая, у вас могут возникнуть сомнения, Redis поддерживает пять структур данных: String, List, Hash, Set, ZSet, растровой карты нет. Да, на самом деле суть растрового изображения — это String.
Некоторые знакомые могут сказать, Нани, фильтр Блума еще не ввели, почему вышел битмап, ничего страшного, можно понимать битмап как бинарный вектор.
Чтобы использовать Redis для реализации фильтра Блума, нам нужно спроектировать функцию отображения и измерить длину двоичного вектора самостоятельно. Это, несомненно, невыполнимая задача для меня. Я могу использовать только поисковую систему. Код непосредственно выпущен ниже . . .
public class RedisMain {
static final int expectedInsertions = 1000;//要插入多少数据
static final double fpp = 0.01;//期望的误判率
//bit数组长度
private static long numBits;
//hash函数数量
private static int numHashFunctions;
static {
numBits = optimalNumOfBits(expectedInsertions, fpp);
numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
}
public static void main(String[] args) {
Jedis jedis = new Jedis("localhost", 6379);
for (int i = 0; i < 1000; i++) {
long[] indexArray = getIndexArray(String.valueOf(i));
for (long index : indexArray) {
jedis.setbit("codebear:bloom", index, true);
}
}
int num = 0;
for (int i = 1000; i < 2000; i++) {
long[] indexArray = getIndexArray(String.valueOf(i));
for (long index : indexArray) {
if (!jedis.getbit("codebear:bloom", index)) {
System.out.println(i + "一定不存在");
num++;
break;
}
}
}
System.out.println("一定不存在的有" + num + "个");
}
/**
* 根据key获取bitmap下标
*/
private static long[] getIndexArray(String key) {
long hash1 = hash(key);
long hash2 = hash1 >>> 16;
long[] result = new long[numHashFunctions];
for (int i = 0; i < numHashFunctions; i++) {
long combinedHash = hash1 + i * hash2;
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
result[i] = combinedHash % numBits;
}
return result;
}
private static long hash(String key) {
return Hashing.MURMUR_HASH.hash(key);
}
//计算hash函数个数
private static int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
//计算bit数组长度
private static long optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
}
результат операции:
1997一定不存在
1998一定不存在
1999一定不存在
一定不存在的有989个
На этом блог заканчивается, всем спасибо.