存储IP和网络的最佳数据结构

Question

我的目标是存储在Redis：

像228.228.228.228

• IP网络一样的
• 简单IP地址(如228.228.228.0/24

)

为了检查请求/响应周期中当前IP xxx.yyy.xxx.vvv是否在(包含)：

• 平原ips

或

228.228.228.0/24)内部的

• Ip网络(例如228.228.228.228 )

总数量的ips和网络-只有1000项。

问题是:在Redis中存储普通ips和网络并在不从Redis获取数据的情况下进行上述检查的最佳方式(最佳结构)是什么？

谢谢。

目前的IP已经被知道了。

更新

好的，让我们用例子来简化它。

我有2个ips和2个网络，我想检查是否包含某些ip。

# 2 plain ip
202.76.250.29
37.252.145.1

# 2 networks
16.223.132.0/24
9.76.202.0/24

有两种可能的方法可以包含确切的ip：

(1)只是简单的ips。例如，上述结构中包含的202.76.250.29和215.08.11.23并不仅仅包含在定义中。

( 2)Ip可能包含在网络中。例如，9.76.202.100包含在网络中，9.76.202.0/24不包含在普通ips列表中，因为没有任何确切的ip = 9.76.202.100.。

关于ip网络的一点解释。非常简单。

Ip网络代表ips的范围。例如，ipv4网络"192.4.2.0/24"表示256个ip地址：

IPv4Address('192.4.2.1'), IPv4Address('192.4.2.2'),
…
…
…
IPv4Address('192.4.2.253'), IPv4Address('192.4.2.254')

换句话说，ip网络是一系列ip地址。

from '192.4.2.1' up to '192.4.2.254'

在我们的示例中，9.76.202.100包含在网络中，9.76.202.0/24作为范围内的其中一个地址。

我的想法是：

任何ip地址都可以表示为整数。202.76.250.29转换为整数的ip地址之一是3394042397。

由于ip网络是ips的一个范围，因此可以通过在整数范围内转换第一个和最后一个ip来将其转换为整数范围内的整数。例如，我们的一个网络16.223.132.0/24表示IPv4Address('16.223.132.1')和IPv4Address('16.223.132.254')之间的范围。或者整数范围从283083777到步骤1的283083781。

单个ip可以表示为它的整数与其整数+1之间的范围(下界包括在内，上限排除在外)。

显然，在普通的ips中搜索可以通过将它们放到SET中，然后使用SISMEMBER来完成。但是在网络内部搜索呢。我们能用范围表演一些把戏吗？

Answer 1

“最佳”是主观的(在内存、速度等方面)，但您可以使用两组/散列来存储它们。因为它们是唯一的，所以hashes和sets都很好。如果您愿意，可以使用单个set/hash来保存ip地址和网络ip地址，但我更喜欢单独保存，因为它们是两种不同类型的数据集(就像数据库表一样)。

然后你可以使用其中任何一种

具有O(1)时间复杂度的

• SISMEMBER complexity
• HEXISTS .

它可以使用多个命令或lua脚本(在一个事务中)在应用程序级别上处理。

根据您的选择，使用SADD和HSET添加到键中(字段值为1)。

-编辑：(希望我做得对)

对于网络地址的范围，从围绕两个点(如12.345.67.1-12.345.67.254 )的整数创建集将表示为12.345.67，并将其添加到集合中。当您想要搜索12.345.67.x时，它将在应用程序级别被解析为12.345.67，并且您将使用SISMEMBER进行检查。对HEXISTS的哈希也可以这样做。

因为ip地址包含有三个点的四个不同的数字，所以您将丢弃最后一个点和最后一个数字，其余的将表示(我假设)网络范围。

Answer 2

对于IP，您可以在O(1)时间内通过特定的IP使用Set和查询。

对于IP范围，我认为您可以使用List和Lua脚本进行查询。List将有O(n)时间进行搜索，但是由于您只有1000个条目，所以O(N)和O(1)在内存查询中对Redis没有太大的区别。