Advertisement
  1. Code
  2. Redis

Понимание магии цветных фильтров с помощью Node.js и Redis

by
Read Time:14 minsLanguages:

Russian (Pусский) translation by Masha Kolesnikova (you can also view the original English article)

При правильном использовании фильтры Bloom окажутся магией. Это смелое утверждение, но в этом уроке мы рассмотрим любопытную структуру данных, как лучше всего ее использовать и несколько практических примеров с использованием Redis и Node.js.

Фильтры Bloom - это вероятностная односторонняя структура данных. Слово «фильтр» может запутать в этом контексте; фильтр подразумевает, что это активная вещь, глагол, но было бы легче думать об этом как о хранилище, существительном. С помощью простого фильтра Bloom вы можете сделать две вещи:

  1. Добавить элемент.
  2. Проверить, не был ли добавлен элемент ранее.

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

Существуют фильтры Bloom, и они добавляют другие способности, такие как удаление или масштабирование, но также добавляют сложности и ограничения. Важно сначала понять простые фильтры Bloom, прежде чем перейти к вариантам. В этой статье будут рассмотрены только простые фильтры Bloom.

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

Когда вы устанавливаете фильтр Bloom, вы придаете ему размер. Этот размер фиксирован, поэтому, если у вас есть один элемент или один миллиард элементов в фильтре, он никогда не будет расти за указанный размер. Когда вы добавляете больше элементов в свой фильтр, вероятность ложного позитива увеличивается. Если вы указали меньший фильтр, эта ложная положительная скорость будет увеличиваться быстрее, чем если бы вы имели больший размер.

Фильтры Bloom построены на концепции одностороннего хеширования. Как и в случае правильного хранения паролей, фильтры 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 нуждаются в алгоритме хеширования для генерирования уникальных идентификаторов для элемента. bloom-redis использует известный алгоритм MD5, который, хотя, может быть, и не идеально подходит для фильтра Блума (немного медленный), будет работать нормально.

Уникальные имена пользователей

Имена пользователей, особенно те, которые идентифицируют пользователя в URL-адресе, должны быть уникальными. Если вы создаете приложение, которое позволяет пользователям изменять имя пользователя, тогда вам, скорее всего, понадобится имя пользователя, которое никогда не использовалось, чтобы избежать путаницы и перехвата имен пользователей.

Без фильтра Bloom вам нужно будет ссылаться на таблицу с каждым именем пользователя, когда она используется, и в масштабе это может быть очень дорого. Фильтры Bloom позволяют добавлять элемент каждый раз, когда пользователь принимает новое имя. Когда пользователь проверяет, требуется ли имя пользователя, все, что вам нужно сделать, это проверить фильтр Bloom. Он сможет с полной уверенностью сказать вам, если ранее было добавлено запрошенное имя пользователя. Возможно, что фильтр будет ложно возвращаться к тому, что имя пользователя использовалось, когда оно на самом деле не было, но это ошибочно на стороне предостережения и не может нанести никакого реального вреда (кроме того, что пользователь, возможно, не может претендовать на «k3w1d00d47») ,

Чтобы проиллюстрировать это, давайте построим быстрый сервер REST с помощью Express. Сначала создайте файл package.json и запустите следующие команды терминала.

npm install bloom-redis --save

npm install express --save

npm install redis --save

Параметры по умолчанию для bloom-redis имеют размер, заданный в двух мегабайтах. Это ошибочно на стороне осторожности, но оно довольно велико. Настройка размера фильтра Bloom имеет решающее значение: слишком большой и вы теряете память, слишком маленький, и ваш ложный положительный уровень будет слишком высоким. Математика, участвующая в определении размера, довольно сложная и выходит за рамки этого урока, но, к счастью, есть калькулятор размера Bloom.

Теперь создайте приложение app.js следующим образом:

Для запуска этого сервера: node app.js. Перейдите в свой браузер и откройте https://localhost: 8010/check?username=kyle. Ответ должен быть: {"username": "kyle", "status": "free"}.

Теперь давайте сохраним это имя пользователя, открыв ваш браузер на http://localhost:8010/save?гsername=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. Постарайтесь побольше.

Если вы затем снова проверите размер, вы можете заметить, что ваш размер немного вырос, но не для каждого добавления. Любопытно, правда? Внутри фильтр Bloom устанавливает отдельные биты (1's / 0's) в разных положениях строки, сохраненной в username-bloom. Однако они не смежны, поэтому, если вы установите бит в индексе 0, а затем на индекс 10 000, все между ними будет 0. Для практического использования сначала не важно понимать точную механику каждой операции - просто знайте, что это нормально, и что ваше хранилище в Redis никогда не превысит указанное вами значение.

Свежий контент

Свежий контент на веб-сайте позволяет пользователю вернуться, так как вы каждый раз показываете пользователю что-то новое? Используя традиционный подход к базе данных, вы можете добавить новую строку в таблицу с идентификатором пользователя и идентификатором истории, а затем вы будете запрашивать эту таблицу при выборе части содержимого. Как вы можете себе представить, ваша база данных будет расти чрезвычайно быстро, особенно с ростом как пользователей, так и контента.

В этом случае ложный негатив (например, не показывающий невидимую часть контента) имеет очень мало последствий, что делает Bloom фильтром хороши решением. На первый взгляд, вы можете подумать, что для каждого пользователя вам понадобится фильтр Bloom, но мы будем использовать простую конкатенацию идентификатора пользователя и идентификатора содержимого, а затем вставьте эту строку в наш фильтр. Таким образом, мы можем использовать один фильтр для всех пользователей.

В этом примере давайте создадим еще один базовый Express-сервер, который отображает контент. Каждый раз, когда вы посещаете маршрут /show-content/any-username (с любым именем пользователя, являющимся любым безопасным значением URL), будет отображаться новый фрагмент контента до тех пор, пока на сайте будет доступен новый контент. В этом примере контент является первой строкой из десяти лучших книг по проекту Gutenberg.

Нам понадобится установить еще один модуль npm. С терминала запустите: npm install async --save

Ваш новый файл app.js:

Если вы внимательно обратите внимание на время прохождения в Dev Tools, вы заметите, что чем больше вы запрашиваете один путь с именем пользователя, тем больше времени требуется. Хотя проверка фильтра занимает фиксированное время, в этом примере мы проверяем наличие большего количества элементов. Фильтры Bloom ограничены тем, что они могут вам сказать, поэтому вы проверяете наличие каждого элемента. Конечно, в нашем примере это довольно просто, но тестирование на сотни предметов будет неэффективным.

Старые данные

В этом примере мы построим небольшой сервер Express, который будет делать две вещи: принимать новые данные через POST и отображать текущие данные (с запросом GET). Когда новые данные отправляются на сервер, приложение проверяет наличие их в фильтре. Если их там нет, мы добавим их в набор в Redis, иначе мы вернем null. Запрос GET выберет из Redis и отправит клиенту.

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

Итак, что мы получаем? Мы получаем скорость, которую вам не нужно проверять в сравнении с фактическим источником каждый раз. В ситуациях, когда источник данных работает медленно (внешние API, базы данных pokey, середина плоского файла), увеличение скорости действительно необходимо. Чтобы продемонстрировать скорость, давайте добавим реалистичную задержку в 150 мс в нашем примере. Мы также будем использовать console.time / console.timeEnd для регистрации различий между проверкой фильтра Bloom и проверкой фильтра не-Bloom.

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

Этот сервер использует те же модули, что и раньше, поэтому установите файл app.js:

Поскольку отправлять POST запрос на сервер в браузере не очень удобно, давайте использовать curl для тестирования.

curl --data “your data goes here" --header "Content-Type: text/plain" http://localhost:8012/

Быстрый сценарий bash можно использовать, чтобы показать, как выглядит заполнение всего фильтра:

Интересно смотреть на заполняющийся или полный фильтр. Так как наш совсем маленький, вы можете легко просмотреть его с помощью redis-cli. Запустив команду redis-cli get stale-filter из своего терминала между добавлением элементов, вы увидите увеличение отдельных байтов. Полный фильтр будет \xff для каждого байта. На этом этапе фильтр всегда будет возвращать положительный ответ.

Заключение

Фильтры Bloom не являются панацеей, но в правильной ситуации фильтр Bloom может обеспечить быстрое и эффективное дополнение к другим структурам данных.

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.