Автор этой статьи: Лу Вей, старший бэкенд-инженер компании Palm Read.
Зачем вводить
В нашем бизнесе мы часто сталкиваемся с проблемой прохождения через библиотеку, которую обычно можно решить кэшированием. Если имеется много измерений данных и результирующий набор данных относительно велик, эффект кэширования не очевиден. Поэтому, чтобы решить проблему прохождения через библиотеку, мы вводим фильтр Блума.
Адрес открытого проекта:GitHub.com/reed2007/no...
давайте сначала посмотрим一般业务缓存流程:
Сначала запросите кеш, а затем запросите базу данных, если кеш отсутствует. Затем поместите результаты запроса в кеш, даже если данных не существует, вам нужно создать кеш, чтобы предотвратить прохождение через библиотеку. Здесь нам нужно различать, существуют ли данные или нет. Если данные не существуют, время кэширования можно установить относительно коротким, чтобы предотвратить усиление проблемы из-за таких проблем, как синхронизация ведущий-ведомый.
Слабая проблема в этом процессе в том, что при слишком большом количестве пользователей мы будем кэшировать большое количество данных и пустых данных, а как только придет волна холодных пользователей, это вызовет лавинный эффект.
Для этого случая мы генерируем процесс второй версии:redis过滤冷用户缓存流程
Ставим попадаемых пользователей в БД в установленном типе Redis, и настройки не имеют срока действия.
Таким образом, Redis считается индексом базы данных.Пока вы запрашиваете Redis, вы можете знать, существуют ли данные.
Если его нет в Redis, результат можно вернуть напрямую.
Если он существует, следуйте приведенному выше一般业务缓存流程иметь дело с.
Умный вы обязательно придумаете еще вопросы:
- Сам Redis можно использовать для кэширования, так почему бы не возвращать данные напрямую?
- Если объем данных относительно велик, будут ли проблемы с производительностью при работе с одним набором?
- Бизнес не важен. Положить полное количество данных в Redis, занимает много серверов. Входной выход непропорциональный?
Вопрос 1 должен различать бизнес-сценарии, данные результата малы, мы можем напрямую использовать Redis в качестве кеша и напрямую возвращать данные. Результат относительно велик и не подходит для хранения с помощью Redis. Например, пользовательский контент, в комментарии могут быть десятки тысяч слов, а бизнес-сфер много.
Есть много трюков с использованием Redis. Bigkey более вреден, будь то освобождение приложения памяти, вызванное расширением или сужением, Возврат большого объема данных из-за неправильного использования команд запроса повлияет на стабильность Redis. Причины и вред здесь подробно обсуждаться не будут. Решение проблемы bigkey простое. Мы можем использовать хеш-функцию для разделения данных на несколько ключей. Уменьшите размер одного ключа, не влияя на эффективность запросов.
Проблема 3 заключается в том, что хранилище Redis занимает слишком много памяти. Поэтому нам нужно уменьшить использование памяти. Переосмыслите цель внедрения Redis. Redis — это как коллекция, и все дело в том, чтобы проверить, есть ли в коллекции параметры запроса.
Большинство языков программирования имеют встроенные фильтры.
братьpythonНапример, функция filter используется для фильтрации последовательностей,
Отфильтровывает элементы, не соответствующие условию, и возвращает список элементов, соответствующих условию.
Давайте посмотрим на пример:
$ python2
Python 2.7.10 (default, Oct 6 2017, 22:29:07)
[GCC 4.2.1 Compatible Apple LLVM 9.0.0 (clang-900.0.31)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> s = {2, 4}
>>> filter(lambda x:x in s, [0, 1, 2])
[2]
В наборе s есть два числа 2, 4, нам нужно запросить 0, 1, 2, которые находятся в наборе s.lambda x:x in sСоздайте анонимную функцию, чтобы определить, находится ли входной параметр x в наборе s.
Фильтр filter, в свою очередь, выполняет анонимную функцию для чисел в списке. окончательный список возврата[2].
Для реализации набора в Redis используются две структуры: intset и хэш-таблица. Когда это не число или большое количество чисел, оно вырождается в хеш-таблицу. Так может ли хороший алгоритм сэкономить размер хеш-таблицы?
Фактически, еще в 1970 г.Burton Howard BloomПредлагаемый фильтр Блума.
На самом деле это длинный двоичный вектор и ряд функций случайного отображения.
Фильтры Блума можно использовать для определения того, находится ли элемент в коллекции.
Его преимущество в том, что эффективность использования пространства и время запроса намного больше, чем у общего алгоритма.
Недостаток в том, что существует определенная скорость неправильного распознавания и сложность удаления.
Принцип фильтра Блум
Обычно мы объединяем бизнес-поля с md5 и помещаем их в коллекцию. md5 генерирует 128-битную строку фиксированной длины. Если мы используем растровое изображение для представления, нам нужно
2**128 = 340282366920938463463374607431768211456 bit
При оценке того, присутствует ли значение, он становится оценкой того, равен ли бит 1 в этом растровом изображении. Но наше машинное хранилище по всему миру также не может хранить загрузки. Таким образом, мы можем выделить только ограниченное пространство для хранения. Например:
import crc32
def BloomFilter(sample, size, hash_size=1):
# 构造一个hash函数，将输入数据散列到size一个位置上
hash = lambda x:crc32(str(x).encode())%size
collision, s = 0, set()
for i in range(sample):
k = set()
for j in range(hash_size):
k.add(hash(i+j*size/hash_size))
# 只有所有散列结果k都在s中，才认为i重复
if not k - s:
collision += 1
continue
# 将散列结果k更新到集合s中
s |= k
return collision
Когда есть только одна хэш-функция: легко могут возникнуть коллизии.
Видно, что результаты хеширования 1 и 2 выше равны 7, и возникает конфликт. Что произойдет, если вы увеличите хэш-функцию?
Мы используем больше хеш-функций и большие наборы данных для тестирования. получить следующую таблицу
Видно, что при добавлении метода хеширования вероятность коллизии может быть эффективно снижена. Хорошие данные следующие:
Однако после добавления метода хеширования эффективность использования пространства будет снижена. Когда коллекция занимает 25% от общего пространства, Эффект увеличения хешрейта уже не очевиден
Использование нескольких вышеперечисленных методов хеширования для уменьшения коллизий — основная идея BloomFilter.
подходящая сцена
-
База данных для предотвращения прохождения через библиотеку Google Bigtable, Apache HBase и Apache Cassandra, а также Postgresql используют BloomFilter, чтобы сократить количество операций поиска на диске для несуществующих строк или столбцов. Избегание дорогостоящих обращений к диску значительно повышает производительность операций запросов к базе данных. Так же, как бизнес-сценарий в начале. Если объем данных большой, неудобно помещать их в кеш. Запрос необходимо перехватить, чтобы предотвратить его прохождение через библиотеку.
-
Кэшировать Когда кеш не работает, использование фильтра Блума может привести к определенной степени ошибочной оценки. Причина в том, что в дополнение к частоте ложных срабатываний самого фильтра Блума кеш перед отключением может не покрыть все данные в БД, Когда пользователь запрашивает данные, которые никогда не запрашивались ранее, произойдет ложное срабатывание на в этот раз. Конечно, использование фильтров Блума в качестве экстренного метода, когда кеш не работает, должно быть терпимым.
-
веб-перехватчик Тот же перехват запросов предотвращает атаки. Когда пользователь запрашивает в первый раз, параметры запроса помещаются в BloomFilter, а когда делается второй запрос, сначала оценивается, попали ли параметры запроса в BloomFilter. Может улучшить скорость попадания в кеш
-
Обнаружение вредоносного адреса Браузер Chrome проверяет наличие вредоносных адресов. Любые URL-адреса сначала проверяются по локальному фильтру BloomFilter, а выполненный URL-адрес полностью проверяется только в том случае, если фильтр BloomFilter возвращает положительный результат (и пользователь получает предупреждение, если он также возвращает положительный результат).
-
Ускорение биткойнов биткойн использует BloomFilter для ускорения синхронизации кошелька.
Преимущества алгоритма:
- Объем данных небольшой, и нет необходимости хранить сами данные.
Недостатки самого алгоритма:
- Элементы можно добавлять в коллекцию, но нельзя удалять.
- Результат сопоставления может быть только «абсолютно не в наборе», и нет никакой гарантии, что совпадающее значение уже находится в наборе.
- Когда коллекция почти заполнена, то есть близка к расчетной максимальной емкости, вероятность ложных срабатываний возрастает.
- Объем данных увеличен. В общем, для 1% вероятности ложных срабатываний каждый элемент меньше 10 бит, независимо от размера или количества элементов в наборе. - Процесс запроса замедляется, а количество хеш-функций увеличивается, что приводит к необходимости находить несколько битов (количество хэшей) для каждого совпадающего процесса, чтобы подтвердить, существует ли он.
За преимуществами BloomFilter можно не принимать во внимание недостатки. В конце концов, для хранения N элементов требуется всего kN дискового пространства. Эффективность использования пространства отличная.
Как использовать БлумФильтр
BloomFilter требует для хранения большого растрового изображения. Учитывая текущее состояние компании, лучший контейнер для хранения — это Redis. отgithub topics: bloom-filterПосле простого исследования.
Redis интегрировала схему BloomFilter:
- Родной Python вызывает setbit для создания BloomFilter
- луа-скрипт
- Rebloom - Bloom Filter Module for Redis(Примечание: модуль redis был представлен в redis4.0)
- Используйте Hiredis для вызова RedispyreBloom
Нативный метод Python слишком медленный, а развертывание lua-скриптов и модулей обременительно. Поэтому мы рекомендуем использовать pyreBloom, нижний слой.
pyreBloom:master λ ls
Makefile bloom.h bloom.pxd murmur.c pyreBloom.pyx
bloom.c bloom.o main.c pyreBloom.c
Из названия файла видно, что Bloom написан на c. pyreBloom написан на китоне.
Bloom.h реализует основную логику BloomFilter, завершает взаимодействие с сервером Redis, хэш-функцию, реализацию методов добавления, проверки и удаления.
int init_pyrebloom(pyrebloomctxt * ctxt, char * key, uint32_t capacity, double error, char* host, uint32_t port, char* password, uint32_t db);
int free_pyrebloom(pyrebloomctxt * ctxt);
int add(pyrebloomctxt * ctxt, const char * data, uint32_t len);
int add_complete(pyrebloomctxt * ctxt, uint32_t count);
int check(pyrebloomctxt * ctxt, const char * data, uint32_t len);
int check_next(pyrebloomctxt * ctxt);
int delete(pyrebloomctxt * ctxt);
pyreBloom.pyx
import math
import random
cimport bloom
class pyreBloomException(Exception):
'''Some sort of exception has happened internally'''
pass
cdef class pyreBloom(object):
cdef bloom.pyrebloomctxt context
cdef bytes key
property bits:
def __get__(self):
return self.context.bits
property hashes:
def __get__(self):
return self.context.hashes
def __cinit__(self, key, capacity, error, host='127.0.0.1', port=6379,
password='', db=0):
self.key = key
if bloom.init_pyrebloom(&self.context, self.key, capacity,
error, host, port, password, db):
raise pyreBloomException(self.context.ctxt.errstr)
def __dealloc__(self):
bloom.free_pyrebloom(&self.context)
def delete(self):
bloom.delete(&self.context)
def put(self, value):
if getattr(value, '__iter__', False):
r = [bloom.add(&self.context, v, len(v)) for v in value]
r = bloom.add_complete(&self.context, len(value))
else:
bloom.add(&self.context, value, len(value))
r = bloom.add_complete(&self.context, 1)
if r < 0:
raise pyreBloomException(self.context.ctxt.errstr)
return r
def add(self, value):
return self.put(value)
def extend(self, values):
return self.put(values)
def contains(self, value):
# If the object is 'iterable'...
if getattr(value, '__iter__', False):
r = [bloom.check(&self.context, v, len(v)) for v in value]
r = [bloom.check_next(&self.context) for i in range(len(value))]
if (min(r) < 0):
raise pyreBloomException(self.context.ctxt.errstr)
return [v for v, included in zip(value, r) if included]
else:
bloom.check(&self.context, value, len(value))
r = bloom.check_next(&self.context)
if (r < 0):
raise pyreBloomException(self.context.ctxt.errstr)
return bool(r)
def __contains__(self, value):
return self.contains(value)
def keys(self):
'''Return a list of the keys used in this bloom filter'''
return [self.context.keys[i] for i in range(self.context.num_keys)]
原生pyreBloom方法:
cdef class pyreBloom(object):
cdef bloom.pyrebloomctxt context
cdef bytes
property bits:
property hashes:
// 使用的hash方法数
def delete(self):
// 删除，会在redis中删除
def put(self, value):
// 添加 底层方法, 不建议直接调用
def add(self, value):
// 添加单个元素，调用put方法
def extend(self, values):
// 添加一组元素，调用put方法
def contains(self, value):
// 检查是否存在，当`value`可以迭代时，返回`[value]`, 否则返回`bool`
def keys(self):
// 在redis中存储的key列表
Так как pyreBloom использует библиотеку найретиса, в ней нет такой логики, как переподключение, поэтому простая инкапсуляция неверна.
# coding=utf-8
'''
bloom filter 基础模块
可用方法:
extend, keys, contains, add, put, hashes, bits, delete
使用方法:
>>> class TestModel(BaseModel):
... PREFIX = "bf:test"
>>> t = TestModel()
>>> t.add('hello')
1
>>> t.extend(['hi', 'world'])
2
>>> t.contains('hi')
True
>>> t.delete()
'''
import logging
from six import PY3 as IS_PY3
from pyreBloom import pyreBloom, pyreBloomException
from BloomFilter.utils import force_utf8
class BaseModel(object):
'''
bloom filter 基础模块
参数：
SLOT: 可用方法类型
PREFIX: redis前缀
BF_SIZE: 存储最大值
BF_ERROR: 允许的出错率
RETRIES: 连接重试次数
host: redis 服务器IP
port: redis 服务器端口
db: redis 服务器DB
_bf_conn: 内部保存`pyreBloom`实例
'''
SLOT = {'add', 'contains', 'extend', 'keys', 'put', 'delete',
'bits', 'hashes'}
PREFIX = ""
BF_SIZE = 100000
BF_ERROR = 0.01
RETRIES = 2
def __init__(self, redis=None):
'''
初始化redis配置
:param redis: redis 配置
'''
# 这里初始化防止类静态变量多个继承类复用，导致数据被污染
self._bf_conn = None
self._conf = {
'host': '127.0.0.1', 'password': '',
'port': 6379, 'db': 0
}
if redis:
for k, v in redis.items():
if k in self._conf:
self._conf[k] = redis[k]
self._conf = force_utf8(self._conf)
@property
def bf_conn(self):
'''
初始化pyreBloom
'''
if not self._bf_conn:
prefix = force_utf8(self.PREFIX)
logging.debug(
'pyreBloom connect: redis://%s:%s/%s, (%s %s %s)',
self._conf['host'], self._conf['port'], self._conf['db'],
prefix, self.BF_SIZE, self.BF_ERROR,
)
self._bf_conn = pyreBloom(
prefix, self.BF_SIZE, self.BF_ERROR, **self._conf)
return self._bf_conn
def __getattr__(self, method):
'''调用pyrebloom方法
没有枚举的方法将从`pyreBloom`中获取
:param method:
:return: pyreBloom.{method}
'''
# 只提供内部方法
if method not in self.SLOT:
raise NotImplementedError()
# 捕获`pyreBloom`的异常, 打印必要的日志
def catch_error(*a, **kwargs):
'''多次重试服务'''
args = force_utf8(a)
kwargs = force_utf8(kwargs)
for _ in range(self.RETRIES):
try:
func = getattr(self.bf_conn, method)
res = func(*args, **kwargs)
# python3 返回值和python2返回值不相同，
# 手工处理返回类型
if method == 'contains' and IS_PY3:
if isinstance(res, list):
return [i.decode('utf8') for i in res]
return res
except pyreBloomException as error:
logging.warn(
'pyreBloom Error: %s %s', method, str(error))
self.reconnect()
if _ == self.RETRIES:
logging.error('pyreBloom Error')
raise error
return catch_error
def __contains__(self, item):
'''跳转__contains__方法
:param item: 查询元素列表/单个元素
:type item: list/basestring
:return: [bool...]/bool
'''
return self.contains(item)
def reconnect(self):
'''
重新连接bloom
`pyreBloom` 连接使用c driver，没有提供timeout参数，使用了内置的timeout
同时为了保证服务的可靠性，增加了多次重试机制。
struct timeval timeout = { 1, 5000 };
ctxt->ctxt = redisConnectWithTimeout(host, port, timeout);
del self._bf_conn 会调用`pyreBloom`内置的C的del方法，会关闭redis连接
'''
if self._bf_conn:
logging.debug('pyreBloom reconnect')
del self._bf_conn
self._bf_conn = None
_ = self.bf_conn
Дополнительно: фильтр подсчета
Предоставляет способ реализации операций удаления в BloomFilter без повторного создания фильтра. В фильтре счетчика позиции массива (сегменты) расширяются от одного бита до n-битного счетчика. На самом деле, обычный фильтр Блума можно рассматривать как счетный фильтр с размером ведра в один бит.
Операции вставки расширены для увеличения значения корзины, а операции поиска проверяют каждую требуемую корзину на ненулевое значение. Затем операция удаления состоит из уменьшения значения каждого сегмента.
Арифметическое переполнение ведер является проблемой, и ведра должны быть достаточно большими, чтобы это происходило редко. Если это все-таки произойдет, операции увеличения и уменьшения должны установить ведро на максимально возможное значение, чтобы сохранить свойства BloomFilter.
Размер счетчика обычно 3 или 4 бита. Таким образом, для вычисления фильтров Блума требуется в 3–4 раза больше места, чем для статических фильтров Блума. Напротив, структуры данных Pagh, Pagh, and Rao (2005) и Fan et al. (2014) также допускают удаление, но занимают меньше места, чем статический BloomFilter.
Еще одна проблема с подсчетом фильтров — ограниченная масштабируемость. Так как таблица фильтра Блума не может быть расширена, максимальное количество ключей, которые должны быть одновременно сохранены в фильтре, должно быть известно заранее. Как только расчетная емкость таблицы превышена, частота ложных срабатываний будет быстро расти по мере вставки большего количества ключей.
Бономи и др. (2006) представили структуру данных на основе хэша d-left, которая функционально эквивалентна, но использует примерно половину объема вычислений фильтра Блума. В этой структуре данных проблем с масштабируемостью не возникает. Как только расчетная емкость превышена, ключ можно повторно вставить в новую хеш-таблицу двойного размера.
Компактный вариант Putze, Sanders, and Singler (2007) также можно использовать для реализации счетных фильтров, поддерживая вставки и удаления.
Роттенстрайх, Канизо и Кесласи (2012) представили новый общий метод, основанный на переменных приращениях, который значительно улучшает вероятность ложного срабатывания при вычислении фильтров Блума и их вариантов, но при этом поддерживает отсев. В отличие от подсчета фильтров Блума, хэш-счетчик увеличивается на единицу приращения хеш-переменной, а не на единицу при каждой вставке элемента. Для запроса элементов необходимо учитывать точные значения счетчиков, а не только их положительность. На запрос может быть возвращен отрицательный ответ, если сумма, представленная значением счетчика, не может быть составлена из соответствующего приращения переменной элемента запроса.
Адрес открытого проекта:GitHub.com/reed2007/no...