Redis或Mongo用于确定数字是否在范围内？

Question

我需要一种方法来快速检查IP地址是否属于许多禁止的IP范围之一。

我目前使用iptables检查IP是否落在指定范围内。这在几千个范围内都可以正常工作，但是这个数字将急剧增加到几十万，并且还将继续增长。

我当前的简单地向iptables添加新规则的方法的另一个问题是重复项的数量不断增加。

在将IP或范围添加到规则集之前，我需要一种有效的方法来检查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），并提供了范围列表（[ACB]）

使用这种数据结构，查询的复杂度实际上为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"