ruby - Redis 或 Mongodb 用于确定数字是否在范围内？

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