algorithm - 从磁盘查找最长前缀

Question

我目前有一些从基数树数据结构执行最长前缀查找（LPM）的实现。此数据结构包含 IP 前缀（最大深度为 128 位的基数树），目前完全保存在内存中。数据是只读数据，永远不会被修改。

不幸的是，数据变大了，我不再能够在内存中维护它。我正在寻找一种可以保存在磁盘上并提供高效查找的高效数据结构。我打算在它上面使用一些缓存机制。

Answer 1

高效的数据结构，可以保存在磁盘上，并提供高效的查找

对我来说看起来像一个XY 问题：

1. 我们谈论的是 IPv6（128 位）。
2. 我们正在谈论 IPv6 路由（最长前缀匹配）。
3. 对于 10 Gbit/s 链路，每秒可能进行多达 1480 万次路由查找。
4. 根据公开数据，目前大约有 5 万个 IPv6 前缀。

如果以上假设正确，我们需要在基数树中存储 50K 乘以 128 位 = 800KB。它应该很容易融入内存。

我们需要每秒查找这些数据数百万次。将数据放到磁盘上是一个数量级的减速。

我的猜测是您的问题不是您的根本问题，所以请：

1. 包括有关更广泛情况的信息以及任何尝试的解决方案。
2. 如果您已经排除了其他解决方案，请分享您排除它们的原因。这提供了有关您的要求的更多信息。

更新：

因此，在只读的 20M 组 IPv6 前缀上每小时进行 2M 次 IPv6 查找。我们仍然不知道那些 20M 前缀是什么，因为从实际的角度来看，整个 Internet 中并没有那么多前缀。但不管怎么说。

1. 2M 查找/小时使得 ~550 查找/秒。根据维基百科，传统（机械）硬盘无法承受这样的负载。所以我们需要一个 SSD 驱动器来存储数据库。

2. 根据 Wikipedia，B 树是用于外部搜索的良好结构。

3. 根据 Wikipedia的说法，即使是非常大的文件，内存映射文件也会使用少量的 RAM。

把所有的位放在一起。那些 20M IPv6 前缀应该被组织成一个节点大小PAGE_SZIE（通常为 4KB）的 B 树，并映射到进程的虚拟地址空间。缓存将由操作系统管理，因此不需要其他缓存机制。