Фон
Кэш-память является важной концепцией для решения повседневных программных проблем. Ваше приложение может выполнять ресурсоемкие операции, которые вы не хотите выполнять снова и снова, вместо этого вы получаете результат один раз и кэшируете его в памяти. Иногда узким местом является IO, например, вы не хотите многократно обращаться к базе данных и хотели бы кэшировать результаты и обновлять кеш только в случае изменения базовых данных.
Точно так же существуют другие случаи использования, когда нам нужно выполнить быстрый поиск, чтобы решить, что делать с входящим запросом. Например, рассмотрим этот случай использования, когда вы должны определить, что один URL-адрес указывает на вредоносный сайт или нет. Подобных URL может быть много, чтобы сделать это в одном случае, если мы кэшируем все вредоносные URL-адреса в памяти, для этого потребуется много места для их хранения. Или другой вариант использования может быть для определения, имеет ли введенная пользователем строка какую-либо ссылку на место в США. Как «музей в Вашингтоне» — в этой строке Вашингтон — это название места в США. Должны ли мы сохранить все места в США в памяти, а затем искать? Насколько большим будет размер кэша? Эффективно ли это делать без поддержки базы данных?
Вот где нам нужно отойти от базовой структуры данных карты и искать ответы в более сложной структуре данных, такой как bloomfilter. Вы можете рассмотреть bloomfilter, как и любую другую коллекцию java, где вы можете поместить в нее элементы и спросить, присутствует ли в них элемент или нет (например, HashSet). Если Bloomfilter упоминает, что он не содержит элемент, то определенно этот элемент отсутствует. Но если он упоминает, что он видел предмет, то это может быть неправильно. Если мы будем достаточно осторожны, мы можем спроектировать фильтр Блум так, чтобы вероятность неправильного контроля контролировалась.
объяснение
Bloomfilter выполнен в виде массива (A) из m бит. Первоначально все эти биты установлены в 0.
Чтобы добавить элемент:
Чтобы добавить любой элемент, его нужно передать через k хеш-функций. Каждая хеш-функция будет генерировать число, которое можно рассматривать как позицию битового массива (длина хеш-модуля по модулю может дать нам индекс массива), и мы установим это значение этой позиции в 1. Например — первая хеш-функция (hash1) для элемента I создаю битовую позицию x, аналогично вторая и третья хеш-функции создают позицию y и z.
Итак, мы установим:
|
1
|
A[x]=A[y]=A[z] = 1 |
Чтобы найти предмет:
Аналогичный процесс будет повторен, элемент будет хеширован три раза через три разные хеш-функции. Каждая хеш-функция выдаст целое число, которое будет обрабатываться как позиция массива. Мы проверим эти x, y, z позиции массива битов и посмотрим, установлены они в 1 или нет. Если нет, наверняка никто никогда не пытался добавить этот элемент в bloomfilter, но если все биты установлены, это может быть ложным срабатыванием.
Вещи для настройки
Из приведенного выше объяснения становится ясно, что для разработки хорошего фильтра Bloomfilter нам необходимо отслеживать следующие вещи
- Хорошие хеш-функции, которые могут генерировать широкий диапазон хеш-значений как можно быстрее
- Значение m (размер массива битов) очень важно. Если размер слишком мал, все биты будут быстро установлены в 1, и количество ложных срабатываний будет расти в основном.
- Количество хеш-функций (k) также важно, чтобы значения распределялись равномерно.
Если мы сможем оценить, сколько элементов мы планируем оставить в фильтре Блума, мы можем рассчитать оптимальные значения k и m. Пропустив математические детали, формулы для вычисления k и m достаточно, чтобы написать хороший фильтр Блум.
Формула для определения m (количество бит для фильтра Блума) выглядит следующим образом:
|
1
|
m = - nlogp / (log2)^2; |
где p = желаемая ложноположительная вероятность
Формула для определения k (количество хеш-функций) выглядит следующим образом:
|
1
|
k = m/n log(2) ; |
где k = количество хеш-функций, m = количество бит и n = количество элементов в фильтре
Хэш
Хеширование — это область, которая влияет на производительность Bloomfilter. Нам нужно выбрать хеш-функцию, которая эффективна, но не требует много времени. В статье «Меньше хеширования, та же производительность: создание лучшего фильтра Блума» обсуждается, как мы можем использовать две хеш-функции для генерации K-хеш-функций. Сначала нам нужно вычислить две хеш-функции h1 (x) и h2 (x). Далее, мы можем использовать эти две хеш-функции для моделирования k хеш-функций природы
|
1
|
gi(x) = h1(x) + ih2(x); |
где я могу варьироваться от {1..k}
Библиотека гуавы Google использует этот трюк в своей реализации bloomfilter, логика хеширования изложена здесь:
|
1
2
3
4
5
6
7
8
|
long hash64 = …; //calculate a 64 bit hash function//split it in two halves of 32 bit hash values int hash1 = (int) hash64; int hash2 = (int) (hash64 >>> 32);//Generate k different hash functions with a simple loopfor (int i = 1; i <= numHashFunctions; i++) { int nextHash = hash1 + i * hash2;} |
Приложения
Из математических формул ясно, что для того, чтобы применить bloomfilter для решения проблемы, нам нужно очень хорошо разбираться в предметной области. Как будто мы можем применить bloomfilter для хранения всех названий городов в США. Это число является детерминированным, и у нас есть предварительные знания, поэтому мы можем определить n (общее количество элементов, добавляемых в фильтр Bloom). Fix p (вероятность ложного срабатывания) в соответствии с бизнес-требованиями. В этом случае у нас есть идеальный кеш, который эффективно использует память и время поиска очень мало.
Реализации
В библиотеке гуавы Google есть реализация Bloomfilter. Проверьте, как работает конструктор этого класса, который запрашивает ожидаемые элементы и уровень ложных срабатываний.
|
1
2
3
4
5
6
7
|
import com.google.common.hash.BloomFilter;import com.google.common.hash.Funnels;//Create Bloomfilterint expectedInsertions = ….;double fpp = 0.03; // desired false positive probabilityBloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("UTF-8")), expectedInsertions,fpp) |