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)并提供范围列表([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"