Алгоритмы в процедурном мире должны уравновешивать различные факторы, такие как время, использование ресурсов и даже точность. Для одной и той же проблемы, в зависимости от масштаба или сценария, используемый алгоритм будет другим, и также будет задействовано множество компромиссов.
Если и есть одно правило в программировании, так оно и есть: всегда будут компромиссы.
ты действительно существуешь
Сегодня мы обсудим, как определить, существует ли значение в существующем наборе. Такие проблемы встречаются во многих сценариях, таких как предотвращение поломки кэша, разбиение по дублированию URL-кармана, запутывание словаря и кэширование прокси-сервера CDN.
В качестве примера возьмем поисковый робот. Связи между сетями сложны, и поисковые программы, «ползающие» между сетями, могут образовывать «петли». Во избежание «звонков» программе необходимо знать URL посещаемого веб-сайта. Когда программа снова встречает веб-сайт по его URL-адресу, как определить, был ли он посещен?
Первая идея — поместить существующий URL-адрес вHashSet, затем используйтеHashSetхарактеристики, о которых нужно судить. Это занимает всего O (1) времени. Однако этот метод занимает много места в памяти, даже если имеется всего 100 миллионов URL-адресов, каждый URL-адрес содержит только 50 символов и требует около 5 ГБ памяти.
Как уменьшить использование памяти? URL-адрес может быть слишком длинным. Давайте воспользуемся односторонним хешированием, например MD5, прежде чем сохранять его в HashSet. Обрабатываемое поле имеет размер всего 128 бит, что позволяет сэкономить много места. Наш веб-сканер может снова возобновить выполнение.
Но хорошие времена не длятся долго, онлайн-мир огромен, и количество URL-адресов быстро растет, а 128-битное хранилище также занимает много памяти.
В этом случае мы также можем использоватьBitSet, используйте хеш-функцию, чтобы преобразовать URL-адрес в 1 бит и сохранить его в BitSet. Однако хэш-функция имеет относительно высокую вероятность коллизии, и чтобы уменьшить вероятность коллизии до 1%, необходимоBitSetДлина устанавливается равной 100-кратному количеству URL-адресов.
Но конфликт неизбежен, что приводит к просчету. Идеальный алгоритм всегда точен и быстр, но на самом деле это часто «куриное перо в одном месте». Нам действительно нужна 100% точность? При необходимости нельзя избежать накладных расходов времени и пространства; если можно допустить низкую вероятность ошибки, есть способы значительно сократить накладные расходы времени и пространства.
Таким образом, все должно быть компромиссом. Фильтр Блума — это алгоритм с низким уровнем ошибок, но значительно экономящий место.
Фильтр Блума
Фильтр Блума — это высокоэффективная структура случайных пространственных данных, которая использует очень простой набор битов, представляющих набор, и может определить, принадлежит ли элемент этому набору. Этот эффективный фильтр Блума имеет определенную стоимость: при определении того, принадлежит ли элемент коллекции, можно поставить, что этот элемент не принадлежит множеству, ошибочно принадлежащему этому множеству (ложное срабатывание). Следовательно, фильтр Блума не подходит для приложений с нулевой ошибкой. В приложениях, которые могут выдерживать низкую частоту ошибок, фильтр Блума снижает количество ошибок в обмен на значительную экономию места для хранения.
Фильтр Bloom представляет собой пространственную вероятностную структуру данных, задуманную Burton Howard Bloom в 1970 году, которая используется для проверки того, возможен ли элемент набора. Ложные положительные совпадения возможны, но ложные негативы не являются, таким образом, негативы Фильтр имеет 100% скорость отзыва. Другими словами, запрос возвращается либо «возможно, в SET», либо «определенно не в наборе».
Приведенное выше описание взято из Википедии, а характеристики резюмируются следующим образом:
- Компактная вероятностная структура данных для проверки того, входит ли элемент в набор.
- Для вызова проверки существования элемента BloomFilter сообщит вызывающей стороне один из двух результатов: он может существовать или не должен существовать.
Существует множество сценариев использования фильтров Блума.В дополнение к упомянутому выше веб-краулеру, есть также обработка разбивки кеша и предотвращение чтения с диска. Фильтры Блума используются, в частности, в Goole Bigtable, Apache HBase и Postgresql.
Мы будем использовать следующий пример, чтобы конкретно описать сценарий использования BloomFilter, а также преимущества и недостатки BloomFilter в этом сценарии.
На диске существует набор элементов, и объем данных очень велик. Приложение надеется попытаться не читать диск, когда элемент не существует. В это время в памяти может быть создан фильтр Блума этих дисковых данных. Для случая чтения данных за один раз он делится на следующие ситуации:
Мы знаем, что такие структуры данных, как HashMap или Set, также могут поддерживать описанные выше сценарии, здесь мы сравним их преимущества и недостатки и приведем конкретные данные.
Точные измерения важны, Для производительности алгоритма мы можем не просто сравнивать ощущения, а проводить конкретные расчеты и тесты производительности. Найдите баланс между различными алгоритмами и решите, какой алгоритм использовать, исходя из баланса и реальности. Как и в Redis, его объекты используют разные структуры данных в разных ситуациях, например, встроенная структура объектов списка может быть изменена.ziplistилиlinkedlist, используя разные структуры данных в разных сценариях.
Запрашиваемый элемент отсутствует на диске. Если BloomFilter возвращает, что его не существует, то приложению не нужно читать логику диска, при условии, что эта вероятность равна P1. Если возврат BloomFilter может существовать, то это ситуация неправильной оценки, предполагая, что эта вероятность равна P2. Запрошенный элемент находится на диске, и BloomFilter возвращает существование, предполагая, что эта вероятность равна P3.
При использованииHashMapи другие структуры данных, ситуация следующая:
- Запрошенных данных нет на диске, приложение не читает логику диска, вероятность P1+P2
- Запрошенный элемент находится на диске, и применяется логика чтения диска, эта вероятность равна P3
Предполагая, что накладные расходы логики не чтения диска равны C1, а накладные расходы логики чтения диска равны C2, тогда накладные расходы BloomFilter и hashmap равны соответственно
- Cost(BloomFilter) = P1 * C1 + (P2 + P3) * C2
- Cost(HashMap) = (P1 + P2) * C1 + P3 * C2;
- Delta = Cost(BloomFilter) - Cost(HashMap) = P2 * (C2 - C1)
Таким образом, BloomFilter эквивалентен увеличению затрат времени P2 * (C2 - C1) для получения относительныхHashMapменьше места над головой.
Поскольку P2 является основным фактором, влияющим на производительность BloomFilter, как уменьшить вероятность P2 (то есть вероятность ложного срабатывания) при разработке BloomFilter? , на этот вопрос ответит следующий принцип BloomFilter.
Принципиальный анализ
В начальном состоянии фильтр Блума представляет собой битовый массив, содержащий m бит, и каждый бит установлен в 0.
Чтобы выразить набор из n элементов, таких как S={x1, x2,...,xn}, фильтр Блума использует k независимых хеш-функций, которые сопоставляют каждый элемент в наборе с диапазоном {1,...,m соответственно} . Для любого элемента x позиция hi(x) карты i-й хеш-функции будет установлена на 1 (1≤i≤k). Обратите внимание, что если позиция установлена на 1 несколько раз, сработает только первый раз, следующие несколько раз не будут иметь никакого эффекта. На рисунке ниже k=3, и есть две хеш-функции, которые выбирают одну и ту же позицию (пятое место слева).
При оценке того, принадлежит ли y этому набору, мы применяем хеш-функцию k раз к y. Если позиции всех hi (y) равны 1 (1≤i≤k), то мы считаем y элементом в наборе, в противном случае считается, что y не является элементом множества. На рисунке ниже y1 не является элементом множества. y2 может принадлежать этому набору, или это просто ошибочное суждение.
下面我们来看一下具体的例子，哈希函数的数量为3，首先加入1，10两个元素。 By the following two diagrams, we can clearly see that the two elements are mapped to different BITs by three different elements, and then determine if the 3 is in the collection, 3 BITs do not have a value. Therefore, it is absolutely not in Коллекция.
Что касается частоты ложных срабатываний, то при фактическом использовании ожидается, что она даст ожидание ложноположительной скорости и количество вставляемых элементов, а также подсчитает, какой объем памяти для выделения является более подходящим. Это включает в себя множество задач оптимального численного расчета, таких как оценка частоты ошибок, оптимальное количество хэш-функций и размер битового массива и т. д. Студенты, которые заинтересованы в вычислении связанных формул, могут использовать Baidu для просмотра времени выполнения. вычисление исчисления в колледже.
Фильтр Блума Гуавы
Еще раз стоит упомянуть наш Guava — это Java-пакет с открытым исходным кодом от Google, который предоставляет множество часто используемых функций, таких как те, о которых мы рассказали выше.Сверхдетальный анализ текущего принципа ограничения Guava RateLimiter.
В Guava реализация фильтра Блума в основном включает два класса:BloomFilterиBloomFilterStrategies, сначала посмотрите наBloomFilterпеременная-член. Обратите внимание, что разные версии GuavaBloomFilterРеализация разная.
/** guava实现的以CAS方式设置每个bit位的bit数组 */
private final LockFreeBitArray bits;
/** hash函数的个数 */
private final int numHashFunctions;
/** guava中将对象转换为byte的通道 */
private final Funnel<? super T> funnel;
/**
* 将byte转换为n个bit的策略，也是bloomfilter hash映射的具体实现
*/
private final Strategy strategy;
Вот его 4 переменные-члены:
-
LockFreeBitArrayопределяется вBloomFilterStrategiesВнутренний класс в , который инкапсулирует работу базового битового массива фильтра Блума. -
numHashFunctionsПредставляет количество хеш-функций. -
Funnel, это иPrimitiveSinkПри совместном использовании он может преобразовать объект любого типа в базовый тип данных Java.java.nio.ByteBufferРеализация и, наконец, преобразование в массив байтов. -
Strategyопределяется вBloomFilterИнтерфейс внутри класса, код такой, в основном 2 метода,putиmightContain.
interface Strategy extends java.io.Serializable {
/** 设置元素 */
<T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits);
/** 判断元素是否存在*/
<T> boolean mightContain(
T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits);
.....
}
Создайте фильтр Buron,BloomFilterПубличного конструктора нет, только один приватный конструктор, и внешне он предоставляет 5 перегруженныхcreateметод, ложноположительный уровень установлен на 3% по умолчанию, используяBloomFilterStrategies.MURMUR128_MITZ_64реализация.
BloomFilterStrategies.MURMUR128_MITZ_64даStrategyОдна из двух реализаций , Guava предоставляет эти две реализации в виде перечислений, что также является одним из методов, рекомендованных в книге «Эффективная Java» для предоставления объектов.
enum BloomFilterStrategies implements BloomFilter.Strategy {
MURMUR128_MITZ_32() {//....}
MURMUR128_MITZ_64() {//....}
}
Эти два соответствуют 32-битным функциям отображения хэшей и 64-битной функции отображения хэшей, последняя использует все 128 бит, сгенерированные Murmur3 Hash, с большим пространством, но принцип связан, мы выбираем относительно простойMURMUR128_MITZ_32анализировать.
Давайте посмотрим на егоputметод, который использует две хэш-функции для имитации ситуации с несколькими хеш-функциями, что является оптимизацией фильтра Блума.
public <T> boolean put(
T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) {
long bitSize = bits.bitSize();
// 先利用murmur3 hash对输入的funnel计算得到128位的哈希值，funnel现将object转换为byte数组，
// 然后在使用哈希函数转换为long
long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
// 根据hash值的高低位算出hash1和hash2
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
boolean bitsChanged = false;
// 循环体内采用了2个函数模拟其他函数的思想,相当于每次累加hash2
for (int i = 1; i <= numHashFunctions; i++) {
int combinedHash = hash1 + (i * hash2);
// 如果是负数就变为正数
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
// 通过基于bitSize取模的方式获取bit数组中的索引，然后调用set函数设置。
bitsChanged |= bits.set(combinedHash % bitSize);
}
return bitsChanged;
}
существуетputметод, сначала установите двоичный файл в позиции индекса в 1, а затем используйтеbitsChangedЗапишите результат вставки, если он возвращает true, это означает, что ни одна повторная вставка не удалась, иmightContainЧисленные методы всасываются в положение индекса, и определяет, является ли 0, который встречается до тех пор, пока 0, определяется, что его нет сразу.
public <T> boolean mightContain(
T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) {
long bitSize = bits.bitSize();
long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
for (int i = 1; i <= numHashFunctions; i++) {
int combinedHash = hash1 + (i * hash2);
// Flip all the bits if it's negative (guaranteed positive number)
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
// 和put的区别就在这里，从set转换为get，来判断是否存在
if (!bits.get(combinedHash % bitSize)) {
return false;
}
}
return true;
}
GuavaДля обеспечения эффективности я реализовал это самLockFreeBitArrayобеспечить безблокировочную установку и чтение битовых массивов. Давайте просто посмотрим на этоputфункция.
boolean set(long bitIndex) {
if (get(bitIndex)) {
return false;
}
int longIndex = (int) (bitIndex >>> LONG_ADDRESSABLE_BITS);
long mask = 1L << bitIndex; // only cares about low 6 bits of bitIndex
long oldValue;
long newValue;
// 经典的CAS自旋重试机制
do {
oldValue = data.get(longIndex);
newValue = oldValue | mask;
if (oldValue == newValue) {
return false;
}
} while (!data.compareAndSet(longIndex, oldValue, newValue));
bitCount.increment();
return true;
}
постскриптум
Добро пожаловать, чтобы оставить сообщение и продолжать следовать за мной.