Advertisement
  1. Code
  2. Redis

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

Scroll to top
Read Time: 16 min

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 следующим образом:

1
var
2
  Bloom         =   require('bloom-redis'),
3
  express       =   require('express'),
4
  redis         =   require('redis'),
5
  
6
  app,
7
  client,
8
  filter;
9
10
//setup our Express server

11
app = express();
12
13
//create the connection to Redis

14
client = redis.createClient();
15
16
17
filter = new Bloom.BloomFilter({ 
18
  client    : client, //make sure the Bloom module uses our newly created connection to Redis

19
  key       : 'username-bloom-filter', //the Redis key

20
  
21
  //calculated size of the Bloom filter.

22
  //This is where your size / probability trade-offs are made

23
  //http://hur.st/bloomfilter?n=100000&p=1.0E-6

24
  size      : 2875518, // ~350kb

25
  numHashes : 20
26
});
27
28
app.get('/check', function(req,res,next) {
29
  //check to make sure the query string has 'username'

30
  if (typeof req.query.username === 'undefined') {
31
    //skip this route, go to the next one - will result in a 404 / not found

32
    next('route');
33
  } else {
34
   filter.contains(
35
     req.query.username, // the username from the query string

36
     function(err, result) {
37
       if (err) { 
38
        next(err); //if an error is encountered, send it to the client

39
        } else {
40
          res.send({ 
41
            username : req.query.username, 
42
            //if the result is false, then we know the item has *not* been used

43
            //if the result is true, then we can assume that the item has been used

44
            status : result ? 'used' : 'free' 
45
          });
46
        }
47
      }
48
    );
49
  }
50
});
51
52
53
app.get('/save',function(req,res,next) {
54
  if (typeof req.query.username === 'undefined') {
55
    next('route');
56
  } else {
57
    //first, we need to make sure that it's not yet in the filter

58
    filter.contains(req.query.username, function(err, result) {
59
      if (err) { next(err); } else {
60
        if (result) {
61
          //true result means it already exists, so tell the user

62
          res.send({ username : req.query.username, status : 'not-created' });
63
        } else {
64
          //we'll add the username passed in the query string to the filter

65
          filter.add(
66
            req.query.username, 
67
            function(err) {
68
              //The callback arguments to `add` provides no useful information, so we'll just check to make sure that no error was passed

69
              if (err) { next(err); } else {
70
                res.send({ 
71
                  username : req.query.username, status : 'created' 
72
                });
73
              }
74
            }
75
          );
76
        }
77
      }
78
    });
79
  }
80
});
81
82
app.listen(8010);

Для запуска этого сервера: 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:

1
var
2
  async         =   require('async'),
3
  Bloom         =   require('bloom-redis'),
4
  express       =   require('express'),
5
  redis         =   require('redis'),
6
  
7
  app,
8
  client,
9
  filter,
10
  
11
  // From Project Gutenberg - opening lines of the top 10 public domain ebooks

12
  // https://www.gutenberg.org/browse/scores/top

13
  openingLines = {
14
    'pride-and-prejudice' : 
15
      'It is a truth universally acknowledged, that a single man in possession of a good fortune, must be in want of a wife.',
16
    'alices-adventures-in-wonderland' : 
17
      'Alice was beginning to get very tired of sitting by her sister on the bank, and of having nothing to do: once or twice she had peeped into the book her sister was reading, but it had no pictures or conversations in it, \'and what is the use of a book,\' thought Alice \'without pictures or conversations?\'',
18
    'a-christmas-carol' :
19
      'Marley was dead: to begin with.',
20
    'metamorphosis' : 
21
      'One morning, when Gregor Samsa woke from troubled dreams, he found himself transformed in his bed into a horrible vermin.',
22
    'frankenstein'  : 
23
      'You will rejoice to hear that no disaster has accompanied the commencement of an enterprise which you have regarded with such evil forebodings.',
24
    'adventures-of-huckleberry-finn' : 
25
      'YOU don\'t know about me without you have read a book by the name of The Adventures of Tom Sawyer; but that ain\'t no matter.',
26
    'adventures-of-sherlock-holmes' :
27
      'To Sherlock Holmes she is always the woman.',
28
    'narrative-of-the-life-of-frederick-douglass' :
29
      'I was born in Tuckahoe, near Hillsborough, and about twelve miles from Easton, in Talbot county, Maryland.',
30
    'the-prince' :
31
      'All states, all powers, that have held and hold rule over men have been and are either republics or principalities.',
32
    'adventures-of-tom-sawyer' :
33
      'TOM!'
34
  };
35
36
37
app = express();
38
client = redis.createClient();
39
40
filter = new Bloom.BloomFilter({ 
41
  client    : client,
42
  key       : '3content-bloom-filter', //the Redis key

43
  size      : 2875518, // ~350kb

44
  //size      : 1024,

45
  numHashes : 20
46
});
47
48
app.get('/show-content/:user', function(req,res,next) {
49
  //we're going to be looping through the contentIds, checking to see if they are in the filter.

50
  //Since this spends time on each contentId wouldn't be advisable to do over a high number of contentIds

51
  //But, in this case the number of contentIds is small / fixed and our filter.contains function is fast, it is okay.

52
  var
53
    //creates an array of the keys defined in openingLines

54
    contentIds = Object.keys(openingLines),
55
    //getting part of the path from the URI

56
    user = req.params.user,
57
    checkingContentId,
58
    found = false,
59
    done = false;
60
   
61
  //since filter.contains is asynchronous, we're using the async library to do our looping 

62
  async.whilst(
63
    //check function, where our asynchronous loop will end

64
    function () { return (!found && !done); },
65
    function(cb) {
66
      //get the first item from the array of contentIds

67
      checkingContentId = contentIds.shift();
68
      
69
      //false means we're sure that it isn't in the filter

70
      if (!checkingContentId)  {
71
         done = true; // this will be caught by the check function above

72
         cb();
73
      } else {
74
        //concatenate the user (from the URL) with the id of the content

75
        filter.contains(user+checkingContentId, function(err, results) {
76
          if (err) { cb(err); } else {
77
            found = !results;
78
            cb();
79
          }
80
        });
81
      }
82
    },
83
    function(err) {
84
      if (err) { next(err); } else {
85
        if (openingLines[checkingContentId]) {
86
          //before we send the fresh contentId, let's add it to the filter to prevent it from showing again

87
          filter.add(
88
            user+checkingContentId, 
89
            function(err) {
90
              if (err) { next(err); } else {
91
                //send the fresh quote

92
                res.send(openingLines[checkingContentId]);
93
              }
94
            }
95
          );
96
        } else {
97
          res.send('no new content!');
98
        }
99
      }
100
    }
101
  );
102
});
103
104
app.listen(8011);

Если вы внимательно обратите внимание на время прохождения в 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:

1
var
2
  async           =   require('async'),
3
  Bloom           =   require('bloom-redis'),
4
  bodyParser      =   require('body-parser'),
5
  express         =   require('express'),
6
  redis           =   require('redis'),
7
  
8
  app,
9
  client,
10
  filter,
11
  
12
  currentDataKey  = 'current-data',
13
  usedDataKey     = 'used-data';
14
  
15
app = express();
16
client = redis.createClient();
17
18
filter = new Bloom.BloomFilter({ 
19
  client    : client,
20
  key       : 'stale-bloom-filter',
21
  //for illustration purposes, this is a super small filter. It should fill up at around 500 items, so for a production load, you'd need something much larger!

22
  size      : 1024,
23
  numHashes : 20
24
});
25
26
app.post(
27
  '/',
28
  bodyParser.text(),
29
  function(req,res,next) {
30
    var
31
      used;
32
      
33
    console.log('POST -', req.body); //log the current data being posted

34
    console.time('post'); //start measuring the time it takes to complete our filter and conditional verification process

35
    
36
    //async.series is used to manage multiple asynchronous function calls.

37
    async.series([
38
      function(cb) {
39
        filter.contains(req.body, function(err,filterStatus) {
40
          if (err) { cb(err); } else {
41
            used = filterStatus;
42
            cb(err);
43
          }
44
        });
45
      },
46
      function(cb) {
47
        if (used === false) {
48
          //Bloom filters do not have false negatives, so we need no further verification

49
          cb(null);
50
        } else {
51
          //it *may* be in the filter, so we need to do a follow up check

52
          //for the purposes of the tutorial, we'll add a 150ms delay in here since Redis can be fast enough to make it difficult to measure and the delay will simulate a slow database or API call

53
          setTimeout(function() {
54
            console.log('possible false positive');
55
            client.sismember(usedDataKey, req.body, function(err, membership) {
56
              if (err) { cb(err); } else {
57
                //sismember returns 0 if an member is not part of the set and 1 if it is.

58
                //This transforms those results into booleans for consistent logic comparison

59
                used = membership === 0 ? false : true;
60
                cb(err);
61
              }
62
            });
63
          }, 150);
64
        }
65
      },
66
      function(cb) {
67
        if (used === false) {
68
          console.log('Adding to filter');
69
          filter.add(req.body,cb);
70
        } else {
71
          console.log('Skipped filter addition, [false] positive');
72
          cb(null);
73
        }
74
      },
75
      function(cb) {
76
        if (used === false) {
77
          client.multi()
78
            .set(currentDataKey,req.body) //unused data is set for easy access to the 'current-data' key

79
            .sadd(usedDataKey,req.body) //and added to a set for easy verification later

80
            .exec(cb); 
81
        } else {
82
          cb(null);
83
        }
84
      }
85
      ],
86
      function(err, cb) {
87
        if (err) { next(err); } else {
88
          console.timeEnd('post'); //logs the amount of time since the console.time call above

89
          res.send({ saved : !used }); //returns if the item was saved, true for fresh data, false for stale data.

90
        }
91
      }
92
    );
93
});
94
95
app.get('/',function(req,res,next) {
96
  //just return the fresh data

97
  client.get(currentDataKey, function(err,data) {
98
    if (err) { next(err); } else {
99
      res.send(data);
100
    }
101
  });
102
});
103
104
app.listen(8012);

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

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

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

1
#!/bin/bash

2
for i in `seq 1 500`;
3
do

4
  curl --data “data $i" --header "Content-Type: text/plain" http://localhost:8012/

5
done   

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

Заключение

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

Advertisement
Did you find this post useful?
Want a weekly email summary?
Subscribe below and we’ll send you a weekly email summary of all new Code tutorials. Never miss out on learning about the next big thing.
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.