如何有效存储 IP 地址和 CIDR 范围

Question

我有一个不知道如何解决的用例。我在这里询问它是为了获得一些关于我需要学习什么来解决这个问题的指导。

我需要存储IP地址（很多，可能有几亿）。这些可以是
```
1.1.1.2
```
或
```
CIDR
```
范围，如
```
1.1.1.1/24
```

要求如下

- Save all the IP address which comes as above format in-memory
- Search should work as following  
   - if I have IP address as 1.1.1.2 and 1.1.1.1/24, it should match the specific IP address 1.1.1.2 and not the CIDR range it falls into (1.1.1.1/24)
   - If specific IP address is not found but CIDR range is available, CIDR range is returned
   - if no match is found, return null/throw exception

问题
- 什么数据结构可以帮助我解决这个问题？尝试一下？ - 你会采取什么方法？ - 如何确保它不会消耗太多内存并且搜索速度快（会有一些合理的权衡）

谢谢

Answer 1

我会使用二叉树（这种树称为Radix Trees）：

IP 地址的位用于从 MSB 开始进行导航（例如 0 = 左子节点，1 = 右子节点）
所有特定的 IP 地址都是叶子，而 CIDR 范围是内部节点（使用虚拟叶子来指示“丢失”的 IP 地址，就像在红黑树中一样）
一些节点将是您拥有的实际数据，其他节点只是“导航”节点（它们对应于您没有的 CIDR 范围，用标志标记它们）

搜索：只需使用您拥有的地址在树中导航即可。如果您最终位于叶子中，则您拥有该特定的 IP 地址，否则带有标志的“最低”节点（请参阅第 3 点）是您拥有的最具体的 CIDR 范围。

示例：让我们使用 8 位 IP 和 2 位“部分”地址；插入 1.1.1.0/6 后，树将是（IP后面的数字是“包含”标志，nils是虚拟叶子）

    <root> -- nil
      |
00.00.00.00/1 (0) -- nil
      |
01.00.00.00/2 (0) -- nil
      |
01.00.00.00/3 (0) -- nil
      |
01.01.00.00/4 (0) -- nil
      |
01.01.00.00/5 (0) -- nil
      |
01.01.01.00/6 (1) --nil
      |
     nil

如果您查找 IP 地址 1.1.1.1，您将停在 1.1.1.1/6，这是一个 CIDR 范围，因为它没有子项，并且是最具体的（在树中）。如果您现在插入 1.1.1.1，树将是

    <root> -- nil
      |
00.00.00.00/1 (0) -- nil
      |
01.00.00.00/2 (0) -- nil
      |
01.00.00.00/3 (0) -- nil
      |
01.01.00.00/4 (0) -- nil
      |
01.01.00.00/5 (0) -- nil
      |
01.01.01.00/6 (1) -- nil
      |
01.01.01.00/7 (0) -- nil
      |
01.01.01.01 (1)

1.1.1.1 没有叶子，因为它是一个 IP 地址。最后我们插入1.1.2.1

    <root> -- nil
      |
00.00.00.00/1 (0) -- nil
      |
01.00.00.00/2 (0) -- nil
      |
01.00.00.00/3 (0) -- nil
      |
01.01.00.00/4 (0) --------------------+
      |                               |
01.01.00.00/5 (0) -- nil        01.01.10.00/5 (0) -- nil
      |                               |
01.01.01.00/6 (1) -- nil        01.01.10.00/6 (0) -- nil        
      |                               |
01.01.01.00/7 (0) -- nil        01.01.10.00/7 (0) -- nil
      |                               |
01.01.01.01 (1)                 01.01.10.01 (1)

Answer 2

首先，您需要确定一些决策点。这必须是完全确定性的。您所说的唯一决定点是应该首先检查主机地址（/32），然后寻找更短的掩码。

它是否应该寻找逐渐变短的掩码（最长匹配）？
如果包含特定的面罩长度，您会考虑较短的还是也可以使用更长的掩码长度，或者仅限于该掩码长度，面罩长度变短，还是面罩长度变长？如果您想查看其他长度，您是否想要路由表那样的最长匹配？
您如何处理像您的示例这样的地址，
```
1.1.1.1/24
```
，其中地址是否比掩码长度允许的长度长？你认为它是仅主机地址 (
```
1.1.1.1/32
```
)，还是寻找上述决策点发挥作用的子网 (
```
1.1.1.0/24
```
)？

当您需要以任何合理的速度处理几亿个地址时，您将需要克服内存消耗问题。

我假设主机地址将是您拥有的最大数量的地址，并且随着掩码长度变短，每个掩码长度的地址将逐渐减少。

如果您使用哈希表（32 个掩码长度中的每一个都有一个），您可以从最长掩码长度 (/32) 表开始，如果未找到匹配项，则查看短掩码长度表，具体取决于上面的确定性规则。

例如，对于问题中的

1.1.1.1/24

，假设您有

1.1.1.0/24

、

1.1.0.0/23

和

1.1.0.0/22

的聚合。

Table /32
1.1.1.1

Table /31
not found

Table /30
not found

Table /29
not found

Table /28
not found

Table /27
not found

Table /26
not found

Table /25
not found

Table /24
1.1.1.0

Table /23
1.1.0.0

Table /22
1.1.0.0

Table /21
not found

Table /20
not found

Table /19
not found

Table /18
not found

Table /17
not found

Table /16
not found

Table /15
not found

Table /14
not found

Table /13
not found

Table /12
not found

Table /11
not found

Table /10
not found

Table /9
not found

Table /8
not found

Table /7
not found

Table /6
not found

Table /5
not found

Table /4
not found

Table /3
not found

Table /2
not found

Table /1
not found

例如，使用

1.1.1.1/24

：您可以开始在

/32

表中查找主机地址。如果没有找到，则

AND

带掩码的地址以在

1.1.1.0

表中获取

/24

。如果您没有找到，请使用下一个较短的掩码

AND

并查看该表。重复直到找到匹配项或掩码长度达到

。具体如何执行此操作取决于您上述决定所产生的算法。

对于每个主机地址或聚合来说，这只占用一个 32 位内存块，但是，对于几亿个地址来说，这不会是一个小数目。性能将高度依赖于所使用的哈希算法，但它应该表现得很好。

Answer 3

postgreSQL 支持 inet、cidr 地址，并具有内置函数来搜索它们（以及范围类型）。

http://www.postgresql.org/docs/9.4/interactive/datatype-net-types.html

不确定这是否是您要问的。

Answer 4

我试图在博客文章中解释有关 trie 和 cidr 的所有细节

希望它有助于理解。

如何有效存储 IP 地址和 CIDR 范围

问题描述投票：0回答：4

4个回答

最新问题

如何有效存储 IP 地址和 CIDR 范围

问题描述 投票：0回答：4

4个回答

最新问题

问题描述投票：0回答：4