Redis или Mongo для определения, попадает ли число в диапазоны?

Question

Мне нужен способ быстро проверить, попадает ли IP-адрес в один из многих запрещенных диапазонов IP-адресов.

В настоящее время я использую iptables, чтобы проверить, попадает ли IP-адрес в указанный диапазон.Это отлично работает для нескольких тысяч диапазонов, но это число собирается резко возрасти до нескольких сотен тысяч и будет продолжать расти.

Другая проблема с моим текущим методом простого добавления новых правил в iptables - это увеличениечисло дубликатов.

Мне нужен эффективный метод проверки, попадает ли IP или диапазон в существующий (больший) диапазон, прежде чем он будет добавлен в набор правил.

Ruby - это язык, который я больше всегознакомы, но какие структуры данных были бы лучшими вариантами для постоянно растущего числа диапазонов?

Одно решение, которое я придумал, состоит в том, чтобы использовать наборы Redis или, возможно, MongoDB для хранения отдельных IP-адресов в виде целых чисел, а затем просто проверитьесли IP существует в наборе ... но моя интуиция говорит мне, что должен быть более разумный способ.

Если бы я конвертировал IP в целые числа и сохранял диапазоны, каков был бы оптимальный способ запуска?через диапазоны, чтобы увидеть, может ли новый IP или диапазон уже охватываться существующим большим диапазоном?

---

Последнее замечание: скорость важнее, чем стоимость памяти.

Answer 1

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

В дополнение к этому, используя отсортированный набор Redis, вы можете эмулировать отсортированный индекс (со сложностью O (log n)), если знаете, что делаете. Redis - это не просто хранилище значений ключей. Сортированные наборы Redis реализованы с использованием списка пропусков, и для сравнения элементов используются оценка и значение.

Чтобы решить эту проблему, необходима специальная структура индексации. Возможно, вы захотите взглянуть на:

http://en.wikipedia.org/wiki/Segment_tree или же http://en.wikipedia.org/wiki/Interval_tree

Если проблема заключается в скорости над пространством, то может быть интересно сгладить индекс. Например, давайте рассмотрим следующие диапазоны (для упрощения обсуждения используем только целые числа):

A 2-8
B 4-6
C 2-9
D 7-10

Может быть построена разреженная структура, индексирующая непересекающиеся сегменты.

0  []
2  [A C]
4  [A C B]
7  [A C D]
9  [C D]
10 [D]
11 []

Каждая запись содержит нижнюю границу непересекающегося сегмента в качестве ключа и список или набор совпадающих диапазонов в качестве значения. Записи должны быть проиндексированы с использованием отсортированного контейнера (дерево, список пропусков, btree и т. Д.)

Чтобы найти диапазоны, соответствующие 5, мы ищем первую запись, которая меньше или равна 5 (в этом примере это будет 4), и предоставляется список диапазонов ([A C B])

При такой структуре данных сложность запросов действительно равна O (log n). Однако это не тривиально (и дорого), чтобы построить и поддерживать его. Это может быть реализовано как с mongodb, так и с Redis.

Вот пример с Redis:

> rpush range:2 2-8 2-9
(integer) 2
> rpush range:4 2-8 2-9 4-6
(integer) 3
> rpush range:7 2-8 2-9 7-10
(integer) 3
> rpush range:9 2-9 7-10
(integer) 2
> rpush range:10 7-10
(integer) 1
> zadd range_index 0 range:0 2 range:2 4 range:4 7 range:7 9 range:9 10 range:10
(integer) 6
> zrevrangebyscore range_index 5 0 LIMIT 0 1
1) "range:4"
> lrange range:4 0 -1
1) "2-8"
2) "2-9"
3) "4-6"

Answer 2

Если вы имеете дело с диапазонами, mongodb будет лучше, чем redis для этого. Если вы имеете дело с конкретными IP-адресами, redis будет лучшим выбором.

Почему?

Mongodb может создавать индексы по начальному и конечному диапазонам IP-адресов, которые вы можете запросить за O (log n), тогда как redis - это просто хранилище значений ключей.

Вы можете использовать хэш redis, если каждый ip, с которым вы хотите проверить, был в хеш-таблице и искать их за O (1) время, но поскольку вы используете диапазоны, я бы сказал, что монго - ваша лучшая ставка. Я не думаю, что вы будете лучше, чем записывать время с любой структурой данных в наборе инструментов Redis. O (n) с отсортированным набором или списком может быть, но не O (log n).