предисловие

когдаRedisПри использовании в качестве кеша цель состоит в том, чтобы уменьшить частоту доступа к базе данных и уменьшить нагрузку на базу данных, но если некоторые из наших данных не существуют вRedisИх, тогда запрос до сих пор доставит вас непосредственно в базу данных, и если бы большой запрос на недействительную кэшу одновременно не существует или кэш вредоносных атак на доступ к этим базам данных приведет к тому, как он должен это предотвратить?

Кэш Лавина

Кэш Лавина относится кRedisБольшое количество кешей недействительно одновременно, и если одновременно инициируется большое количество запросов, это приведет к тому, что запрос будет напрямую обращаться к базе данных, что может привести к перегрузке базы данных.

Лавина кеша обычно описывает данные, которые находятся не в кеше, а в базе данных, и запрос уходит в базу данных по истечению времени.

решение

Есть много способов решить проблему лавины кеша, и наиболее часто используемые из них следующие:

Блокировка для обеспечения однопоточного доступа к кешу. Таким образом, одновременно к базе данных не будет поступать много запросов.
keyВремя истечения срока действия значения не должно быть одинаковым. Как правило, при инициализации данных прогрева можно использовать произвольное время для сохранения данных в кэше, чтобы гарантировать, что не будет большого количества одновременных аннулирований кэша.
Кэш можно настроить так, чтобы он никогда не истекал, если позволяет память.

разбивка кеша

Разбивка кеша очень похожа на лавину кеша, разница в том, что разбивка кеша обычно относится к одному сбою кеша, и в то же время существует большое количество одновременных запросов, которым необходимо получить доступ к этомуkey, тем самым вызывая нагрузку на базу данных.

решение

Решение для разбивки кеша очень похоже на решение для лавинного кеша:

Блокировка для обеспечения однопоточного доступа к кешу. Таким образом, первый запрос доходит до базы данных, он перезаписывает кеш, последующие запросы читают кеш.
Кэш можно настроить так, чтобы он никогда не истекал, если позволяет память.

проникновение в кеш

Существенная разница между проникновением в кэш и двумя вышеупомянутыми явлениями заключается в том, что данные, к которым осуществляется доступ в это время, находятся не только вRedisОн не существует в базе данных и не существует в базе данных, поэтому, если параллелизм слишком велик, это приведет к тому, что данные будут постоянно поступать в базу данных, вызывая большую нагрузку на базу данных.

решение

Для проблемы проникновения в кеш блокировка не работает, потому что она сама по себеkeyЕго просто не существует, поэтому, даже если количество потоков доступа контролируется, запросы будут продолжать поступать в базу данных.

Проникновение для решения проблем с кешем обычно можно использовать в сочетании со следующей программой:

Уровень интерфейса проверяет и находит недопустимыеkeyВернуться напрямую. Например, в базе данных используется автоинкремент.id, то если не целоеidили отрицательныйidВы можете вернуться напрямую, или если вы используете32немногоuuid, затем найдитеidдлина не равна32Биты также могут быть возвращены напрямую.
Кешировать несуществующие данные, вы можете напрямую кэшировать пустые или другие согласованные недействительныеvalue. Таким способом лучше всегоkeyУстановите короткое время истечения, иначе большое количество несуществующихkeyхранится вRedis, это также займет много памяти.

Фильтр Блума

Для решения вышеупомянутого проникновения в кеш, давайте подумаем об этом: еслиkeyможет обойти1метод проверки, и в настоящее время существует большое количество несуществующихkeyдоступен (например,1Миллиард или10100 миллионов), то хранить их все в памяти в это время нереально.

Так есть ли лучшее решение? Это фильтр Блума, который мы представим далее.Фильтр Блума может хранить как можно больше данных на минимально возможном пространстве.

Что такое фильтр Блума

Фильтр Блума (Bloom Filter) сделан Блумом в1970Годовой предложенный. Это на самом деле очень длинный двоичный вектор (растровое изображение) и серия случайных функций сопоставленных (хэш-функции).

Фильтры Блума можно использовать для определения того, находится ли элемент в коллекции. Его преимущество в том, что эффективность использования памяти и время запроса намного лучше, чем у общего алгоритма, а недостаток в том, что должны быть определенные коэффициенты неправильного распознавания и трудности с удалением.

Битовая карта

RedisОдной из структур данных является битовая карта, а важной реализацией фильтра Блума является реализация битовой карты, то есть битового массива, и каждая позиция в этом массиве имеет только0и1Два состояния, каждое положение занимает только1байт, из них0означает, что ни один элемент не существует,1Указывает, что есть элемент. Как показано на рисунке ниже, является примером простого резинового фильтра (ОдинkeyЗначение хешируется и побитно, чтобы выяснить, куда оно должно попасть):

хэш-коллизия

Выше мы обнаружили, чтоlonelyиwolfОн падает в том же положении, что разные значения ключевых значений, полученные после того же феномена хешированного значения, называютсяхэш-коллизия. После того, как произойдет коллизия хэшей, выполняется битовая операция, после чего он обязательно окажется в той же позиции.

Если будет слишком много хеш-коллизий, это повлияет на точность решения, поэтому, чтобы уменьшить количество хеш-коллизий, мы обычно учитываем следующее.2факторы:

Увеличьте размер массива растровых изображений (чем больше массив растровых изображений, тем больше памяти он занимает).
Увеличьте количество раз, когда хеш-функция (та же самаяkeyзначение проходит1Функции равны, то после2Вероятность получения такого же результата при вычислении одной или нескольких хеш-функций, естественно, уменьшится).

Нам нужно рассматривать два вышеуказанных метода комплексно: например, увеличение битового массива будет занимать больше места, а чем больше хеш-вычислений, тем больше места будет потребляться.cpuЭто влияет на окончательное время расчета, поэтому, насколько велик битовый массив и сколько раз хеш-функция должна быть правильно рассчитана, требует специального анализа конкретной ситуации.

2 Особенности фильтров Блума

На картинке ниже прохождение2Фильтр Блума, полученный второй хэш-функцией, согласно следующему рисунку, мы можем легко увидеть, что если нашRedisвообще не существует, ноRedisпроходить через2Две позиции, полученные после второй хеш-функции, уже1(одинwolfпройти черезf2получить, одинNosqlпройти черезf1, поэтому произошла коллизия хэшей, и поэтому фильтр Блума может ошибаться).

Таким образом, через описанное выше явление, с точки зрения фильтра Блума, мы можем сделать вывод, что фильтр Блума в основном имеет2Большие возможности:

Если фильтр Блума определяет, что элемент существует, то этот элементЭто может существовать.
Если фильтр Блума определяет, что элемент не существует, то этот элементне должно существовать.

И с точки зрения элемента также можно сделать вывод, что2Большие возможности:

Фильтр Блума, если элемент действительно существуетдолжно быть оценено как существующее.
Фильтр Блума, если элемент не существуетможно считать существующим.

PS:Следует отметить, что еслиNХеш-функция, вам нужно получитьNлокации1можно считать существующим, пока существует0, можно определить, что элемент не существует в фильтре Блума.

fpp

Потому что в фильтре Блума всегда будет ложное срабатывание, потому что коллизий хэшей невозможно избежать на 100%.Эта частота ложных срабатываний называется вероятностью ложных срабатываний фильтра Блума., а именно: Вероятность ложного срабатывания, называемаяfpp.

При использовании фильтров Блума на практике вы можете определить их самостоятельно.fpp, а затем вы можете рассчитать, сколько хеш-функций и сколько места битового массива необходимо в соответствии с теорией фильтра Блума. Следует отметить, что этоfppнельзя определить как100%, потому что нет 100% гарантии от коллизий хэшей.

Реализация фильтра Блума (Guava)

существуетGuavaРеализация фильтра Блума предоставляется в пакете, и передается следующееGuavaОпыт применения фильтра Buron:

вводитьpomполагаться

<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>29.0-jre</version>
</dependency>

Создайте новый тестовый классBloomFilterDemo:

package com.lonely.wolf.note.redis;

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.UUID;

public class GuavaBloomFilter {
    private static final int expectedInsertions = 1000000;

    public static void main(String[] args) {
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),expectedInsertions);

        List<String> list = new ArrayList<>(expectedInsertions);

        for (int i = 0; i < expectedInsertions; i++) {
            String uuid = UUID.randomUUID().toString();
            bloomFilter.put(uuid);
            list.add(uuid);
        }

        int mightContainNum1 = 0;

        NumberFormat percentFormat =NumberFormat.getPercentInstance();
        percentFormat.setMaximumFractionDigits(2); //最大小数位数

        for (int i=0;i < 500;i++){
            String key = list.get(i);
            if (bloomFilter.mightContain(key)){
                mightContainNum1++;
            }
        }
        System.out.println("【key真实存在的情况】布隆过滤器认为存在的key值数：" + mightContainNum1);
        System.out.println("-----------------------分割线---------------------------------");

        int mightContainNum2 = 0;

        for (int i=0;i < expectedInsertions;i++){
            String key = UUID.randomUUID().toString();
            if (bloomFilter.mightContain(key)){
                mightContainNum2++;
            }
        }

        System.out.println("【key不存在的情况】布隆过滤器认为存在的key值数：" + mightContainNum2);
        System.out.println("【key不存在的情况】布隆过滤器的误判率为：" + percentFormat.format((float)mightContainNum2 / expectedInsertions));
    }
}

Результат после запуска:

Вывод первой частиmightContainNum1должно быть сforРавно значению в цикле, т.е. совпадение на сто процентов. Это соответствует принципу1:Если элемент действительно существует, то фильтр Блума должен определить, что он существует.. Частота ложных срабатываний вывода второй части равнаfppвсегда в3%вокруг и сforЧем больше количество петель, тем теснее3%. который удовлетворяет принципу2:Если элемент не существует, то фильтр Блума может определить, что он существует..

это3%Как возникла частота ложноположительных результатов? Переходим к созданию фильтра Блумаcreateметод, обнаружил, что fpp по умолчанию0.03:

для этого значения по умолчанию3%изfppСколько места нужно для битового массива и сколько раз получается хэш-функция? существуетBloomFilterНиже класса есть дваdefaultМетод может получить размер пространства битового массива и количество хеш-функций:

OptimalnumOfHashfunctions: количество раз, чтобы получить хеш-функцию
OPTIMALNUMOFBITS: получите размер битового массива

debugЗагляните внутрь:

Полученный результат7298440 bit=0.87M, затем после5Хэш-операция. Можно заметить, что занимаемая площадь очень мала,100Wизkeyтолько что занят0.87M.

PS:кликните сюдаМожно ввести расчет сайтаbitРазмер массива и количество хеш-функций.

Как убрать фильтр Блума

Фильтр Блума для определения существования элемента заключается в том, чтобы определить, является ли соответствующая позиция1определить, но если вы хотите удалить элемент, вы не можете напрямую поставить1изменить на0Да, потому что в этой позиции могут быть другие элементы, поэтому, если мы хотим поддержать удаление, что нам делать? Самый простой способ — добавить счетчик, т. е. если каждый бит битового массива не существует, он0, есть несколько элементов для хранения конкретных чисел, а не только1, то есть проблема, изначально1Достаточно одной цифры, но если вы хотите сохранить определенные числа, например2, то вам нужно2немного, такBuron Filter с счетчиком занимает большую площадь.

Фильтр Блума со счетчиком

Вот пример фильтра Блума со счетчиком:

pomФайл вводит зависимости:

<dependency>
    <groupId>com.baqend</groupId>
    <artifactId>bloom-filter</artifactId>
    <version>1.0.7</version>
</dependency>

Создайте новый фильтр Блума со счетчикомCountingBloomFilter:

package com.lonelyWolf.redis.bloom;

import orestes.bloomfilter.FilterBuilder;

public class CountingBloomFilter {
    public static void main(String[] args) {
        orestes.bloomfilter.CountingBloomFilter<String> cbf = new FilterBuilder(10000,
                0.01).countingBits(8).buildCountingBloomFilter();

        cbf.add("zhangsan");
        cbf.add("lisi");
        cbf.add("wangwu");
        System.out.println("是否存在王五：" + cbf.contains("wangwu")); //true
        cbf.remove("wangwu");
        System.out.println("是否存在王五：" + cbf.contains("wangwu")); //false
    }
}

Построить фронт фильтра Блума2Один из параметров — это ожидаемое количество элементов, а другой —fppзначение, послеcountingBitsПараметр - размер, занимаемый счетчиком,Вот8бит, т.е. до255Повторы, если не проходят, то вот по умолчанию16Размер бита, то есть разрешить65535повторения.

Суммировать

В этой статье в основном описывается использованиеRedisЕсть три вида проблем: лавина кеша, поломка кеша и проникновение в кеш. Решение каждой проблемы описывается отдельно, и, наконец, представлено решение проблемы проникновения в кеш: фильтр Блума. Родной фильтр Блума не поддерживает удаление, но можно ввести счетчик для реализации фильтра Блума со счетчиком для реализации функции удаления, в то же время, как было сказано в конце, фильтр Блума со счетчиком займет больше космическая проблема.