Кэш Лавина
Лавина кеша означает, что большой объем горячих данных Redis истекает (аннулируется) одновременно.Поскольку установлено одно и то же время истечения срока действия, одновременное количество запросов Redis в это время очень велико, что приведет к тому, что все запросы упадут до база данных.
Как решить эту проблему?
- Добавьте MUTEX или используйте очередь, чтобы разрешить только один поток для запроса базы данных для того же ключа
- Кэш регулярно обновляется заранее, чтобы избежать одновременной инвалидации
- Срок действия ключей истекает в разное время путем добавления случайных чисел
- кеш никогда не истекает
проникновение в кеш
Взгляните на эту картинку, пользователиВозможно, был сделан запрос с неправильными условиями,На данный момент редиса не существует.По нормальному процессу идем в базу данных,чтобы его найти,но это некорректный условный запрос.Конечно,база не будет существовать,и не будет записывать значения в redis, и возвращать пустое значение пользователю. Это нормально, чтобы работать один или два раза, но это хорошо для большего количества раз. Я поставил redis, чтобы заблокировать первый блок и уменьшить нагрузку на базу данных. Теперь redis стал бесполезен. Каждый раз Я иду в базу данных, чтобы найти его, это называется кешированием. Проникновение означает, что редис больше не существует и сломан. Это хорошее решение для этой ситуации. Мы можем кэшировать редис в редисе.
空字符串или特殊字符串，比如&&, в следующий раз, когда мы перейдем к redis для запроса, когда полученное значение будет пустым или &&, мы знаем, что значение отсутствует в базе данных, поэтому мы не будем запрашивать в базе данных,Примечание: При отсутствии ключа в кеше здесь необходимо установить время истечения срока действия, иначе когда база данных добавит эту запись, это приведет к несогласованности между кешем и базой данных.
Вышеупомянутый случай повторного запроса одного и того же несуществующего значения Что, если несуществующее значение каждого запроса отличается? Даже если каждый раз кешировать специальную строку, это бесполезно, потому что ее значение разное.Например, в нашей базе id пользователя 111, 112, 113, 114 увеличивается по очереди, но кто-то хочет напасть на вас, сознательно возьмите -100, -936 , -545 - это грязный ключ для запроса. В настоящее время значение Redis и базы данных не существует, и ключ, который люди получают каждый раз, отличается. Даже если вы его кэшируете, он бесполезен. В настоящее время ,нагрузка на базу данных довольно большая,это гораздо страшнее,чем описанная выше ситуация.Что делать?В это время наш главный герой сегодняФильтр Блумапоявившийся. .
Говоря с лица вопросы
просить:Как быстро определить, существует ли элемент среди большого количества элементов (например, 1 миллиард неупорядоченных, неопределенной длины, неповторяющихся)?Ну, наша самая простая идея - поместить столько данных в структуры данных, такие как Список, Карта и Дерево, они не могут выйти после поиска, такого как map.get(), мы предполагаем, что элемент 1 байт Поле, 1 миллиард данных требует около 900 ГБ памяти, что невыносимо для обычных серверов.Конечно, интервьюер не хочет слышать ваш ответ, потому что это слишком глупо, мы должны использовать своего рода Хороший способ, умный способ решения , вот компактная структура данных,битовая карта, который представляет собой упорядоченный массив только с двумя значениями, 0 и 1. 0 означает, что не существует, 1 означает, что он существует.
С этой сумасшедшей штукой теперь нам все еще нужны отношения сопоставления.Вы должны знать, где находится элемент, и тогда вы можете видеть, является ли он 0 или 1 в этой позиции.Как решить эту проблему, тогда вам нужно использовать хэш функция, есть два преимущества использования хеш-функции, первое — это хеш-функцияНезависимо от длины входного значения, выходное значение фиксированной длины получается, второй егоРаспределение равномерное, как его отличить, если сжать все вместе, например, MD5 и SHA-1 — распространенные алгоритмы хеширования.
После того, как мы вычислим его через хэш-функцию, мы можем перейти в соответствующую позицию, чтобы узнать, существует ли он.Смотрим на красную строку.Значение хеш-функции, полученное хэш-функцией 24 и 147, одинаково.Мы называем эту ситуациюхеш-коллизия или хеш-коллизия. Коллизия хэшей неизбежна, что мы можем сделать, так это уменьшить вероятность коллизии хэшей,ПервоеМожно расширить длину размерного массива или разрядность битмапа, так как наша функция распределена равномерно, чем больше разрядность битмапа, тем меньше вероятность коллизии хэшей в одной и той же позиции. Но чем больше емкость битмапа, тем больше потребление памяти, поэтому думаем, можно ли это решить другими способами,секундаМетод заключается в вычислении нескольких хэш-функций.Вы думаете, 24 и 147 сталкиваются после одного вычисления.Если я еще могу столкнуться после 5,10 и 100 вычислений,то это действительно судьба.Вы можете быть вместе,но больше хеш-функции вычисления тем лучше, потому что это быстро заполнит битмап, а вычисление тоже требует времени, поэтому нам нужно найти баланс между временем и пространством. .
Например: какая емкость растрового изображения и сколько хэш-функций нам нужно для хранения 1 миллиона элементов?
Фильтр Блума
Сегодняшний главный герой, фильтр Блума, выходит на сцену. Этот вопрос изучался давно.В 1970 году предшественник по имени Блум изучил проблему суждения о существовании элементов в массивных элементах, то есть сколько битовой емкости и сколько хэшей нужно функции, он опубликовал статью , а предлагаемый контейнер называется фильтром Блума.
Давайте взглянем на эту картинку.Посмотрим на 3 элемента в наборе.Теперь мы должны его сохранить.1 хранится в соответствующей позиции,а элементы b и c также вычисляются этими тремя функциями и помещаются в соответствующие должность. При взятии элемент a вычисляется функцией f1(a), и оказывается, что эта позиция равна 1, нет проблем, вторая позиция тоже 1, и третья позиция тоже 1. В это время мы говорим что это a находится в фильтрации Блума Он существует в фильтре, в этом нет ничего плохого Аналогично, давайте посмотрим на следующее d. После трех вычислений мы находим, что все полученные результаты равны 1. Тогда можем ли мы сказать, что d существует в фильтре Фильтр Блума? Очевидно, что нет. Мы внимательно смотрим на то, что три единицы, полученные d, на самом деле хранятся в f1(a), f1(b), f2(c), а не в самом d, это вызвано коллизией хэшей, мы ставим Это тот факт, что несуществующие элементы в фильтре Блума ошибочно оцениваются как существующие, называется ложным срабатыванием (вероятность ложного срабатывания, FPP).
Давайте посмотрим на другой элемент, элемент e. Нам нужно определить, существует ли он в контейнере, и использовать эти три функции для его вычисления. Первая позиция — 1, вторая позиция — 1, третья позиция — 0. Так может ли элемент e определить, находится ли он в фильтре Блума? Ответ: да, e не должно существовать. Вы думаете, что если e существует, то все три позиции устанавливаются в 1, когда он депонирован, и теперь одна из позиций оказывается равной 0, что доказывает, что он не депонирован. . Из приведенной выше иллюстрации мы можем сделать два важных вывода.
С точки зрения контейнера:
- Если фильтр Блума определяет, что элемент существует в коллекции, он не обязательно существует.
- Если фильтр Блума считает, что он не существует, он не должен существовать.
С точки зрения элемента:
- Если элемент действительно существует, фильтр Блума должен определить, что он существует.
- Если элемент на самом деле не существует, фильтр Блума может определить, что он существует.
Ребята, пожалуйста, имейте это в виду. .
Guava реализует фильтр Блума
Почему язык Java написан таким большим количеством людей и имеет большую базу?Потому что это открытый исходный код, включает в себя открытый исходный код, имеет множество фреймворков и много колес, а для функции существует более одного колеса.Есть fastjson, jackson и gson для сериализации. Колесо фильтра Блума — это гуава, предоставленная Google, давайте воспользуемся кодом, чтобы увидеть, как его использовать.
Сначала представьте наш пакет полки
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>21.0</version>
</dependency>
Здесь сначала сохраните 1 миллион элементов в фильтре Блума, а затем проверьте правильную скорость и частоту ложных срабатываний 100 существующих элементов и 9900 несуществующих элементов соответственно.
//插入多少数据
private static final int insertions = 1000000;
//期望的误判率
private static double fpp = 0.02;
public static void main(String[] args) {
//初始化一个存储string数据的布隆过滤器,默认误判率是0.03
BloomFilter<String> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions, fpp);
//用于存放所有实际存在的key，用于是否存在
Set<String> sets = new HashSet<String>(insertions);
//用于存放所有实际存在的key，用于取出
List<String> lists = new ArrayList<String>(insertions);
//插入随机字符串
for (int i = 0; i < insertions; i++) {
String uuid = UUID.randomUUID().toString();
bf.put(uuid);
sets.add(uuid);
lists.add(uuid);
}
int rightNum = 0;
int wrongNum = 0;
for (int i = 0; i < 10000; i++) {
// 0-10000之间，可以被100整除的数有100个（100的倍数）
String data = i % 100 == 0 ? lists.get(i / 100) : UUID.randomUUID().toString();
//这里用了might,看上去不是很自信，所以如果布隆过滤器判断存在了,我们还要去sets中实锤
if (bf.mightContain(data)) {
if (sets.contains(data)) {
rightNum++;
continue;
}
wrongNum++;
}
}
BigDecimal percent = new BigDecimal(wrongNum).divide(new BigDecimal(9900), 2, RoundingMode.HALF_UP);
BigDecimal bingo = new BigDecimal(9900 - wrongNum).divide(new BigDecimal(9900), 2, RoundingMode.HALF_UP);
System.out.println("在100W个元素中，判断100个实际存在的元素，布隆过滤器认为存在的：" + rightNum);
System.out.println("在100W个元素中，判断9900个实际不存在的元素，误认为存在的：" + wrongNum + "，命中率：" + bingo + "，误判率：" + percent);
}
конечный результат
Мы видим, что этот результат подтверждает сделанный выше вывод, эти 100 реальных элементов должны существовать в фильтре Блума, а остальные 9900 элементов, которых не существует, фильтр Блума все равно считает, что 216 существуют, это неверно Причина указана выше, поэтому фильтр Блума не панацея, но очень хорошо, что он может помочь нам противостоять большинству данных, которых не существует, и это значительно снизило нагрузку на базу данных, Кроме того, показатель ложных срабатываний 0,02 составляет in При инициализации фильтра Блума задаем сами, если не задаем, то по умолчанию 0,03.Когда мы устанавливаем его сами, мы не должны устанавливать 0!
Емкость растрового изображения рассчитывается на основе количества элементов и частоты ложных срабатываний.
long numBits = optimalNumOfBits(expectedInsertions, fpp);
По размеру битового массива далее рассчитываем количество хеш-функций.
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
С помощью этой формулы мы подсчитали, что хранение 1 миллиона элементов занимает всего 0,87 М памяти и генерирует 5 хеш-функций.
Сайт онлайн-вычислений:Внезапно фильтр тела/цвета…
Исходный код: com/xhj/bloom/memory/BloomFilterDemo.java.
Redis реализует фильтр Блума
上面使用guava实现布隆过滤器是把数据放在本地内存中，我们项目往往是分布式的，我们还可以把数据放在redis中，用redis来实现布隆过滤器，这就需要我们自己设计映射函数，自己度量二进制向量的长度，下面贴代码，大家可以直接拿来用的，已经经过测试了。 .
/**
* 布隆过滤器核心类
*
* @param <T>
* @author jack xu
*/
public class BloomFilterHelper<T> {
private int numHashFunctions;
private int bitSize;
private Funnel<T> funnel;
public BloomFilterHelper(int expectedInsertions) {
this.funnel = (Funnel<T>) Funnels.stringFunnel(Charset.defaultCharset());
bitSize = optimalNumOfBits(expectedInsertions, 0.03);
numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
}
public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp) {
this.funnel = funnel;
bitSize = optimalNumOfBits(expectedInsertions, fpp);
numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
}
public int[] murmurHashOffset(T value) {
int[] offset = new int[numHashFunctions];
long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
for (int i = 1; i <= numHashFunctions; i++) {
int nextHash = hash1 + i * hash2;
if (nextHash < 0) {
nextHash = ~nextHash;
}
offset[i - 1] = nextHash % bitSize;
}
return offset;
}
/**
* 计算bit数组长度
*/
private int optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
/**
* 计算hash方法执行次数
*/
private int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
}
Здесь мы работаем с битовой картой redis. Вы можете знать только пять типов данных redis, string, list, hash, set, zset. Вы никогда не слышали о битовой карте, но это не имеет значения. Можно сказать, что нет, поскольку его суть все же строка, я позже напишу статью, чтобы представить типы данных и сценарии их использования в Интернете. .
/**
* redis操作布隆过滤器
*
* @param <T>
* @author xhj
*/
public class RedisBloomFilter<T> {
@Autowired
private RedisTemplate redisTemplate;
/**
* 删除缓存的KEY
*
* @param key KEY
*/
public void delete(String key) {
redisTemplate.delete(key);
}
/**
* 根据给定的布隆过滤器添加值，在添加一个元素的时候使用，批量添加的性能差
*
* @param bloomFilterHelper 布隆过滤器对象
* @param key KEY
* @param value 值
* @param <T> 泛型，可以传入任何类型的value
*/
public <T> void add(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for (int i : offset) {
redisTemplate.opsForValue().setBit(key, i, true);
}
}
/**
* 根据给定的布隆过滤器添加值，在添加一批元素的时候使用，批量添加的性能好，使用pipeline方式(如果是集群下，请使用优化后RedisPipeline的操作)
*
* @param bloomFilterHelper 布隆过滤器对象
* @param key KEY
* @param valueList 值，列表
* @param <T> 泛型，可以传入任何类型的value
*/
public <T> void addList(BloomFilterHelper<T> bloomFilterHelper, String key, List<T> valueList) {
redisTemplate.executePipelined(new RedisCallback<Long>() {
@Override
public Long doInRedis(RedisConnection connection) throws DataAccessException {
connection.openPipeline();
for (T value : valueList) {
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for (int i : offset) {
connection.setBit(key.getBytes(), i, true);
}
}
return null;
}
});
}
/**
* 根据给定的布隆过滤器判断值是否存在
*
* @param bloomFilterHelper 布隆过滤器对象
* @param key KEY
* @param value 值
* @param <T> 泛型，可以传入任何类型的value
* @return 是否存在
*/
public <T> boolean contains(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for (int i : offset) {
if (!redisTemplate.opsForValue().getBit(key, i)) {
return false;
}
}
return true;
}
}
Наконец, тестовый класс
public static void main(String[] args) {
RedisBloomFilter redisBloomFilter = new RedisBloomFilter();
int expectedInsertions = 1000;
double fpp = 0.1;
redisBloomFilter.delete("bloom");
BloomFilterHelper<CharSequence> bloomFilterHelper = new BloomFilterHelper<>(Funnels.stringFunnel(Charset.defaultCharset()), expectedInsertions, fpp);
int j = 0;
// 添加100个元素
List<String> valueList = new ArrayList<>();
for (int i = 0; i < 100; i++) {
valueList.add(i + "");
}
long beginTime = System.currentTimeMillis();
redisBloomFilter.addList(bloomFilterHelper, "bloom", valueList);
long costMs = System.currentTimeMillis() - beginTime;
log.info("布隆过滤器添加{}个值，耗时：{}ms", 100, costMs);
for (int i = 0; i < 1000; i++) {
boolean result = redisBloomFilter.contains(bloomFilterHelper, "bloom", i + "");
if (!result) {
j++;
}
}
log.info("漏掉了{}个,验证结果耗时：{}ms", j, System.currentTimeMillis() - beginTime);
}
Обратите внимание, что здесь используется addList, его нижний уровень — это конвейер конвейерной обработки, а нижний уровень метода add — это setBit цикла for, который очень медленный, но может иметь возвращаемое значение, чтобы узнать, была ли вставка выполнена. успешным, а конвейерную обработку я не знаю, поэтому какой метод выбрать, зависит от вашего бизнес-сценария и скорости вставки. .
Реализация Редиссона
Ну а выше на самом деле написанный вручную распределенный фильтр Блума.Так как Java с открытым исходным кодом, должны быть хорошие люди, которые помогут нам его реализовать, иначе мы будем писать каждый раз один.Есть неэффективности и много моментов, которые не учтены. Тогда этот зрелый фреймворк — знаменитый Redisson!
Справочные документы следующие,GitHub.com/Редис сын/Горячие…
Ниже я написал реализацию одного узла:
/**
* @author jack xu
*/
public class SingleTest {
public static void main(String[] args) {
Config config = new Config();
config.setCodec(new org.redisson.client.codec.StringCodec());
//指定使用单节点部署方式
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
RedissonClient redisson = Redisson.create(config);
RBloomFilter<SomeObject> bloomFilter = redisson.getBloomFilter("sample");
// 初始化布隆过滤器，预计统计元素数量为55000000，期望误差率为0.03
bloomFilter.tryInit(55000000L, 0.03);
bloomFilter.add(new SomeObject("field1Value", "field2Value"));
bloomFilter.add(new SomeObject("field5Value", "field8Value"));
bloomFilter.contains(new SomeObject("field1Value", "field8Value"));
}
}
Распределенный фильтр Блума кластера Redisson на основе Redis предоставляет функцию сегментирования данных фильтра Блума для среды Redis в состоянии кластера через интерфейс RClusteredBloomFilter. Освободите место в памяти кластера, сжимая неиспользуемые биты с помощью оптимизированного и более эффективного алгоритма. Состояние каждого объекта будет распределено по кластеру. Максимальное число включенных битов составляет 2^64.Примечание. Эта функция доступна только в версии Redisson PRO.
RClusteredBloomFilter<SomeObject> bloomFilter = redisson.getClusteredBloomFilter("sample");
// 采用以下参数创建布隆过滤器
// expectedInsertions = 255000000
// falseProbability = 0.03
bloomFilter.tryInit(255000000L, 0.03);
bloomFilter.add(new SomeObject("field1Value", "field2Value"));
bloomFilter.add(new SomeObject("field5Value", "field8Value"));
bloomFilter.contains(new SomeObject("field1Value", "field8Value"));
Фильтр Блума со счетчиком
Если база данных удаляет данные, данные фильтра Блума также удаляются. Но в фильтре Блума нет метода удаления. Почему фильтр Блума не предоставляет метод удаления?
Разберем, например, если мы удалим a, то все три позиции должны измениться на 0. Но при оценке того, существует ли элемент b, поскольку одна позиция становится 0, считается, что элемент b не существует, но на самом деле элемент b существует. Это происходит из-за коллизии хэшей, поэтому элементы можно только сохранять, но не удалять.
Так что, если мы хотим реализовать функцию удаления, аналогичную методу цепочки адресов HashMap, мы можем добавить счетчик к каждой позиции нижнего индекса. Например, если эта позиция попадает дважды, счетчик равен 2. При удалении элемента сначала измените счетчик на 1. Когда элемент b удаляется, счетчик становится равным 0, а соответствующий бит ниже в это время устанавливается равным 0.
Мы называем этот bf с функцией удаления Counting Bloom Filter, исходный код: com/xhj/bloom/countBloom/CountingBloomFilterTest.java
Рабочее положение фильтра Блума
Первым шагом является загрузка всех данных из базы данных в фильтр Блума. На втором этапе, когда есть запрос, сначала перейдите к фильтру Блума, чтобы запросить, если bf говорит «нет», третий шаг возвращается напрямую. Если bf говорит «да», процесс перед сбоем.
Другие сценарии применения фильтров Блума
- Поисковые роботы дедуплицируют URL-адреса, чтобы избежать сканирования одних и тех же URL-адресов;
- Защита от спама, чтобы определить, является ли почтовый ящик ящиком для спама из миллиардов списков спама;
- Google Chrome использует фильтры Блума для выявления вредоносных URL-адресов;
- Medium использует фильтр Блума, чтобы не рекомендовать статьи, которые пользователи уже прочитали;
- Google BigTable, Apache HBbase и Apache Cassandra используют фильтры Блума, чтобы сократить количество поисковых запросов для несуществующих строк и столбцов.
На этом фильтр Блума закончился. Во время интервью интервьюер спросит, что делать с разбивкой кеша. Думаю, вы сможете ответить на этот вопрос. Просто скажите это понятным языком. Тогда он сможет также могут применяться на работе, например службы аутентификации.Когда пользователи входят в систему, они могут сначала использовать фильтр Блума для оценки, вместо того, чтобы напрямую обращаться к Redis и базе данных для проверки. Исходный код этой статьи:GitHub.com/Сюй Хаоцзя/Горячая земля…