В правильном случае фильтры Блума кажутся волшебством. Это смелое утверждение, но в этом уроке мы рассмотрим любопытную структуру данных, как ее лучше использовать и несколько практических примеров с использованием Redis и Node.js.
Фильтры Блума — это вероятностная, односторонняя структура данных. Слово «фильтр» может быть запутанным в этом контексте; Фильтр подразумевает, что это активная вещь, глагол, но может быть проще думать о нем как о хранилище, существительном. С помощью простого фильтра Блума вы можете сделать две вещи:
- Добавить предмет.
- Проверьте , не был ли предмет ранее добавлен.
Это важные ограничения для понимания — вы не можете удалить элемент или вывести список элементов в фильтре Блума. Кроме того, вы не можете с уверенностью сказать, был ли элемент добавлен в фильтр в прошлом. Вот где появляется вероятностная природа фильтра Блума — ложные срабатывания возможны, а ложные отрицания — нет. Если фильтр настроен правильно, ложные срабатывания могут быть крайне редки.
Существуют варианты фильтров Блума, и они добавляют другие способности, такие как удаление или масштабирование, но они также добавляют сложность и ограничения. Важно сначала понять простые фильтры Блума, прежде чем переходить к вариантам. Эта статья будет охватывать только простые фильтры Bloom.
С этими ограничениями у вас есть ряд преимуществ: фиксированный размер, шифрование на основе хеша и быстрый поиск.
Когда вы устанавливаете фильтр Блума, вы даете ему размер. Этот размер является фиксированным, поэтому если в фильтре есть один элемент или один миллиард элементов, он никогда не превысит указанный размер. Когда вы добавляете больше элементов в свой фильтр, вероятность ложного срабатывания увеличивается. Если вы указали меньший фильтр, этот показатель ложных срабатываний будет увеличиваться быстрее, чем если бы вы имели больший размер.
Фильтры Блума построены на концепции одностороннего хеширования. Подобно правильному хранению паролей, фильтры Bloom используют алгоритм хеширования, чтобы определить уникальный идентификатор для передаваемых в него элементов. Хэши по своей природе не могут быть обращены и представлены, казалось бы, случайной строкой символов. Таким образом, если кто-то получит доступ к фильтру Блума, он не будет напрямую раскрывать содержимое.
Наконец, фильтры Bloom работают быстро. Операция включает в себя гораздо меньше сравнений, чем другие методы, и ее можно легко хранить в памяти, предотвращая попадания в базу данных, снижающие производительность.
Теперь, когда вы знаете ограничения и преимущества фильтров Bloom, давайте рассмотрим некоторые ситуации, в которых вы можете их использовать.
Настроить
Мы будем использовать Redis и Node.js для иллюстрации фильтров Bloom. Redis — это хранилище для вашего фильтра Bloom; это быстро, в памяти и имеет несколько специальных команд ( GETBIT , SETBIT ), которые делают реализацию эффективной. Я предполагаю, что в вашей системе установлены Node.js, npm и Redis. Ваш сервер Redis должен работать на localhost через порт по умолчанию, чтобы наши примеры работали.
В этом уроке мы не будем реализовывать фильтр с нуля; вместо этого мы сосредоточимся на практическом использовании с предварительно собранным модулем в npm: bloom-redis . Bloom-Redis имеет очень краткий набор методов: add , contains и clear .
Как упоминалось ранее, фильтрам Блума нужен алгоритм хеширования для генерации уникальных идентификаторов для элемента. Bloom-Redis использует хорошо известный алгоритм MD5, который, хотя, возможно, не идеально подходит для фильтра Блума (немного медленный, излишний бит), будет работать нормально.
Уникальные имена пользователей
Имена пользователей, особенно те, которые идентифицируют пользователя в URL, должны быть уникальными. Если вы создадите приложение, которое позволяет пользователям изменять имя пользователя, вам, скорее всего, понадобится имя пользователя, которое никогда не использовалось, чтобы избежать путаницы и перебора имен пользователей.
Без фильтра Блума вам нужно будет ссылаться на таблицу, в которой есть все когда-либо использованные имена пользователей, а в масштабе это может быть очень дорого. Фильтры Блума позволяют добавлять элемент каждый раз, когда пользователь вводит новое имя. Когда пользователь проверяет, введено ли имя пользователя, все, что вам нужно сделать, это проверить фильтр Блума. Он сможет с полной уверенностью сказать вам, было ли запрошенное имя пользователя добавлено ранее. Возможно, что фильтр ошибочно вернет, что имя пользователя использовалось, когда оно не использовалось, но это приводит к ошибкам со стороны предосторожности и не может причинить реального вреда (за исключением того, что пользователь может не иметь права требовать «k3w1d00d47») ,
Чтобы проиллюстрировать это, давайте создадим быстрый REST-сервер с Express. Сначала создайте файл package.json а затем выполните следующие команды терминала.
npm install bloom-redis --save
npm install express --save
npm install redis --save
Параметры по умолчанию для bloom-redis имеют размер, установленный в два мегабайта. Это приводит к ошибкам, но оно довольно большое. Настройка размера фильтра Блума имеет решающее значение: слишком велик, и вы тратите память, слишком мал, и уровень ложных срабатываний будет слишком высоким. Математика, связанная с определением размера, довольно сложна и выходит за рамки этого учебного пособия, но, к счастью, есть калькулятор размера фильтра Блума, чтобы выполнить работу без взлома учебника.
Теперь создайте ваш app.js следующим образом:
« `javascript var Bloom = require (‘bloom-redis’), express = require (‘express’), redis = require (‘redis’),
приложение, клиент, фильтр;
// настроить наше приложение для сервера Express = express ();
// создать соединение с Redis client = redis.createClient ();
filter = new Bloom.BloomFilter ({client: client, // убедитесь, что модуль Bloom использует наше вновь созданное соединение с ключом Redis: ‘username-bloom-filter’, // ключ Redis
// расчетный размер фильтра Блума. // Здесь можно найти компромиссы между размером и вероятностью //http://hur.st/bloomfilter?n=100000&p=1.0E-6 size: 2875518, // ~ 350kb numHashes: 20});
app.get (‘/ check’, function (req, res, next) {// проверяем, что строка запроса имеет ‘username’ if (typeof req.query.username === ‘undefined’) {// пропустить этот маршрут, перейти к следующему — приведет к 404 / not found next (‘route’);} else {filter.contains (req.query.username, // имя пользователя из функции строки запроса (err, result ) {if (err) {next (err); // если обнаружена ошибка, отправьте ее клиенту} else {res.send ({username: req.query.username, // если результат равен false, тогда мы знаем, что элемент не использовался // если результат равен true, то мы можем предположить, что элемент был использован status: result? ‘used’: ‘free’});}});}});
app.get (‘/ save’, function (req, res, next) {if (typeof req.query.username === ‘undefined’) {next (‘route’);} else {// сначала нам нужно чтобы убедиться, что его еще нет в фильтре filter.contains (req.query.username, function (err, result) {if (err) {next (err);} else {if (result) {// true result означает он уже существует, поэтому сообщите пользователю res.send ({username: req.query.username, status: ‘not-made’});} else {// мы добавим имя пользователя, переданное в строке запроса, в фильтр filter.add (req.query.username, function (err) {// Добавляемые аргументы обратного вызова не дают полезной информации, поэтому мы просто проверим, чтобы убедиться, что ошибки не было передано, если (err) {next (err) ;} else {res.send ({имя пользователя: req.query.username, статус: ‘создан’});}});}}});}});
app.listen (8010); « `
Чтобы запустить этот сервер: node app.js Перейдите в браузер и укажите его: https://localhost:8010/check?username=kyle . Ответ должен быть: {"username":"kyle","status":"free"} .
Теперь давайте сохраним это имя пользователя, указав в браузере адрес http://localhost:8010/save?username=kyle . Ответ будет: {"username":"kyle","status":"created"} . Если вы вернетесь по адресу http://localhost:8010/check?username=kyle , ответом будет {"username":"kyle","status":"used"} . Точно так же, возвращаясь к http://localhost:8010/save?username=kyle получите {"username":"kyle","status":"not-created"} .
Из терминала вы можете увидеть размер фильтра: redis-cli strlen username-bloom-filter .
Прямо сейчас с одним предметом должно отображаться 338622 .
Теперь продолжайте и попробуйте добавить больше имен пользователей с маршрутом /save . Попробуйте столько, сколько захотите.
Если вы снова проверите размер, вы можете заметить, что ваш размер немного увеличился, но не для каждого добавления. Любопытно, правда? Внутренне фильтр Блума устанавливает отдельные биты (1/0) в разных позициях в строке, сохраненной в имени пользователя-Блум. Тем не менее, они не являются смежными, поэтому, если вы установите бит в индекс 0, а затем в индекс 10 000, все между будет равным 0. Для практического использования изначально не важно понимать точную механику каждой операции — просто знайте, что это это нормально, и ваше хранилище в Redis никогда не превысит указанное вами значение.
Свежий контент
Свежий контент на сайте заставляет пользователя возвращаться, так как вы каждый раз показываете что-то новое? Используя традиционный подход к базе данных, вы можете добавить в таблицу новую строку с идентификатором пользователя и идентификатором истории, а затем выполнить запрос к этой таблице, когда решите показать часть содержимого. Как вы можете себе представить, ваша база данных будет расти очень быстро, особенно с ростом пользователей и контента.
В этом случае ложный отрицательный результат (например, не показ невидимого фрагмента контента) имеет очень незначительные последствия, что делает фильтры Блума жизнеспособным вариантом. На первый взгляд, вы можете подумать, что вам понадобится фильтр Блума для каждого пользователя, но мы будем использовать простое объединение идентификатора пользователя и идентификатора контента, а затем вставим эту строку в наш фильтр. Таким образом, мы можем использовать единый фильтр для всех пользователей.
В этом примере давайте создадим еще один базовый сервер Express, который отображает контент. Каждый раз, когда вы посещаете маршрут /show-content/any-username (где any-username является любым URL-безопасным значением), будет отображаться новый фрагмент контента до тех пор, пока на сайте не закончится контент. В приведенном примере содержание является первой строкой первой десятки книг о Project Gutenberg .
Нам нужно будет установить еще один модуль npm. Из терминала запустите: npm install async --save
Ваш новый файл app.js:
« `javascript var async = require (‘async’), Bloom = require (‘bloom-redis’), express = require (‘express’), redis = require (‘redis’),
приложение, клиент, фильтр,
// Из Проекта Гутенберга — первые строки в 10 лучших книгах в области общественного достояния // https://www.gutenberg.org/browse/scores/top creationLines = {‘pride-and-prejudice’: ‘Это истина, общепризнанная что одинокий мужчина, обладающий удачей, должен нуждаться в жене »,« Алиса-приключения в стране чудес »:« Алиса начинала очень уставать сидеть со своей сестрой на берегу, и из-за того, что ей нечего было делать: один или два раза она заглянула в книгу, которую читала ее сестра, но в ней не было ни картинок, ни разговоров, — а какая польза от книги, — подумала Алиса, — без картинок или разговоров? ‘,’ a-christmas-carol ‘:’ Марли был мертв: для начала. ‘,’ metamorphosis ‘:’ Однажды утром, когда Грегор Самса проснулся от беспокойных снов, он обнаружил, что превратился в своей постели в ужасных паразитов ‘. , «Франкенштейн»: «Вы будете рады услышать, что ни одна катастрофа не сопровождала начало предприятия, которое вы рассматривали с такими злыми предчувствиями»., adventu res-of-huckleberry-finn ‘: «Вы не знаете обо мне без того, что читали книгу под названием« Приключения Тома Сойера »; но это неважно. »,« Приключения Шерлока Холмса »:« Шерлоку Холмсу она всегда женщина »,« Повествование о жизни Фредерика Дугласа »:« Я родился в Тукахо, недалеко от Хиллсборо, и примерно в двенадцати милях от Истона, в округе Тэлбот, штат Мэриленд. ‘,’ Принц ‘:’ Все государства, все державы, которые владели и держали власть над людьми, были и являются либо республиками, либо являются республиками. или княжества. ‘,’ Приключения Тома Сойера ‘:’ TOM! ‘ };
app = express (); client = redis.createClient ();
filter = new Bloom.BloomFilter ({клиент: клиент, ключ: ‘3content-bloom-filter’, // размер ключа Redis: 2875518, // ~ 350kb // размер: 1024, numHashes: 20});
app.get (‘/ show-content /: user’, function (req, res, next) {// мы собираемся перебирать contentIds, проверяя, есть ли они в фильтре. // Так как тратить время на каждый contentId было бы нецелесообразно для большого количества contentIds // Но, в этом случае число contentIds небольшое / фиксированное, и наша функция filter.contains быстро работает, это нормально. var // создает массив ключей, определенных в открытии линии contentIds = Object.keys (открытиеLines), // получая часть пути от URI user = req.params.user, checkContentId, found = false, done = false;
// поскольку filter.contains является асинхронным, мы используем асинхронную библиотеку для выполнения нашего цикла async.whilst (// проверка функции, где наш асинхронный цикл завершится function () {return (! found &&! done);}, function (cb) {// получить первый элемент из массива contentIds CheckContentId = contentIds.shift ();
// false означает, что мы уверены, что его нет в фильтре if (! checkContentId) { сделано = верно; // это будет поймано функцией проверки выше CB (); } еще { // объединяем пользователя (из URL) с идентификатором контента filter.contains (user + checkContentId, function (err, results) { if (err) {cb (err); } еще { найдено =! результаты; CB (); } }); } }, function (err) { if (err) {next (err); } еще { if (creationLines [checkContentId]) { // прежде чем мы отправим свежий contentId, давайте добавим его в фильтр, чтобы он не показывался снова filter.add ( Пользователь + checkingContentId, function (err) { if (err) {next (err); } еще { // отправить свежую цитату res.send (openingLines [checkingContentId]); } } ); } еще { res.send ('нет нового контента!'); } } }); });
app.listen (8011); « `
Если вы внимательно следите за временем прохождения туда и обратно в Dev Tools, вы заметите, что чем больше вы запрашиваете один путь с именем пользователя, тем дольше это занимает. Хотя проверка фильтра занимает фиксированное время, в этом примере мы проверяем наличие большего количества элементов. Фильтры Блума ограничены в том, что они могут вам сказать, поэтому вы проверяете наличие каждого элемента. Конечно, в нашем примере это довольно просто, но тестирование сотен предметов будет неэффективным.
Устаревшие данные
В этом примере мы создадим небольшой сервер Express, который будет выполнять две вещи: принимать новые данные через POST и отображать текущие данные (с помощью запроса GET). Когда новые данные отправляются на сервер POST, приложение проверяет их наличие в фильтре. Если его нет, мы добавим его в набор в Redis, в противном случае мы вернем ноль. Запрос GET извлечет его из Redis и отправит клиенту.
Это отличается от двух предыдущих ситуаций тем, что ложные срабатывания не будут в порядке. Мы будем использовать фильтр Блума в качестве первой линии защиты. Учитывая свойства фильтров Блума, мы будем точно знать, что чего-то нет в фильтре, поэтому в этом случае мы можем пойти дальше и пустить данные. Если фильтр Блума возвращает то, что, вероятно, находится в фильтре, мы сделаю проверку по сравнению с фактическим источником данных.
Итак, что мы получаем? Мы получаем скорость, когда нет необходимости каждый раз сравнивать с фактическим источником. В ситуациях, когда источник данных медленный (внешние API, базы данных pokey, середина плоского файла), увеличение скорости действительно необходимо. Чтобы продемонстрировать скорость, давайте добавим реалистическую задержку в 150 мс в нашем примере. Мы также будем использовать console.time / console.timeEnd для регистрации различий между проверкой фильтра Блума и проверкой фильтра не Блума.
В этом примере мы также будем использовать чрезвычайно ограниченное количество битов: всего 1024. Он быстро заполнится. Когда он заполняется, он будет показывать все больше ложных срабатываний — вы увидите увеличение времени отклика по мере того, как уровень ложных срабатываний увеличивается.
Этот сервер использует те же модули, что и раньше, поэтому установите для файла app.js значение:
« `javascript var async = require (‘async’), Bloom = require (‘bloom-redis’), bodyParser = require (‘body-parser’), express = require (‘express’), redis = require (‘ Redis’),
приложение, клиент, фильтр,
currentDataKey = ‘current-data’, usedDataKey = ‘used-data’;
app = express (); client = redis.createClient ();
filter = new Bloom.BloomFilter ({client: client, key: ‘stale-bloom-filter’, // для иллюстрации это очень маленький фильтр. Он должен заполняться примерно до 500 элементов, поэтому для производственной нагрузки, вам нужно что-то намного большее! size: 1024, numHashes: 20});
app.post (‘/’, bodyParser.text (), function (req, res, next) {var used;
console.log ('POST -', req.body); // регистрируем текущие данные, публикуемые console.time ( 'пост'); // начинаем измерять время, необходимое для завершения нашего фильтра и процесса условной проверки //async.series используется для управления несколькими асинхронными вызовами функций. async.series ([ function (cb) { filter.contains (req.body, function (err, filterStatus) { if (err) {cb (err); } еще { used = filterStatus; CB (ERR); } }); }, function (cb) { if (used === false) { // Фильтры Блума не имеют ложных негативов, поэтому нам не требуется дополнительная проверка CB (нуль); } еще { // он * может * быть в фильтре, поэтому нам нужно выполнить дополнительную проверку // для целей данного учебного пособия мы добавим сюда задержку 150 мс, поскольку Redis может быть достаточно быстрым, чтобы его было трудно измерить, а задержка будет имитировать медленный вызов базы данных или API setTimeout (function () { console.log («возможно ложное срабатывание»); client.sismember (usedDataKey, req.body, function (err, членство) { if (err) {cb (err); } еще { // sismember возвращает 0, если член не является частью набора, и 1, если это так. // Это преобразует эти результаты в логические значения для согласованного логического сравнения б = членство === 0? false true; CB (ERR); } }); } 150); } }, function (cb) { if (used === false) { console.log («Добавление в фильтр»); filter.add (req.body, CB); } еще { console.log («Пропущено добавление фильтра, [ложь] положительный результат»); CB (нуль); } }, function (cb) { if (used === false) { client.multi () .set (currentDataKey, req.body) // неиспользуемые данные установлены для легкого доступа к клавише 'current-data' .sadd (usedDataKey, req.body) // и добавлен в набор для последующей простой проверки .exec (CB); } еще { CB (нуль); } } ], function (err, cb) { if (err) {next (err); } еще { console.timeEnd ( 'пост'); // записывает количество времени с момента вызова console.time выше res.send ({сохранено:! использовано}); // возвращает, если элемент был сохранен, true для свежих данных, false для устаревших данных. } } ); });
app.get (‘/’, function (req, res, next) {// просто вернуть свежие данные client.get (currentDataKey, function (err, data) {if (err) {next (err);} else { res.send (data);}});});
app.listen (8012); « `
Так как размещение на сервере может быть сложнее с браузером, давайте использовать curl для тестирования.
curl --data “your data goes here" --header "Content-Type: text/plain" http://localhost:8012/
Быстрый скрипт bash может быть использован, чтобы показать, как выглядит заполнение всего фильтра:
bash #!/bin/bash for i in `seq 1 500`; do curl --data “data $i" --header "Content-Type: text/plain" http://localhost:8012/ done
Смотреть на заполнение или полный фильтр интересно. Так как этот маленький, вы можете легко просмотреть его с помощью redis-cli . redis-cli get stale-filter из терминала между добавлениями элементов, вы увидите увеличение отдельных байтов. Полный фильтр будет \xff для каждого байта. В этот момент фильтр всегда будет возвращать положительный результат.
Вывод
Фильтры Блума не являются решением проблемы панацеи, но в правильной ситуации фильтр Блума может обеспечить быстрое и эффективное дополнение к другим структурам данных.