应用程序请求与 Linux 内核中的响应的在线匹配
Online matching of appliction's requests with responses in Linux Kernel
我使用 Netfilter 的钩子实现了一个 Linux 内核模块，用于检查主机的所有传入和传出数据包。使用此模块，我可以监视该主机上给定应用程序 运行ning 的流量，即，通过了解 src/dst ports/IPs 我可以过滤掉（分类）相关数据包received/sent。
我接下来要做的是在 运行 时匹配传入应用程序的请求与相应的传出响应。每个 request/response 都由 src/dst IP 和唯一 ID 标识。
天真的实现 是流动的：
- 将每个传入请求存储在列表中（array/linked 列表等）
- 对于每个外发回复：
- 搜索列表以找到匹配的请求。如果找到请求，请将其从列表中删除。
- 定期 p运行e 删除早于 X 秒的请求的请求列表。
问题 是对于每个响应，这种天真的算法需要通过请求列表进行线性搜索以识别匹配项。这在高利率下是昂贵的。
你能推荐一个可以降低复杂度的算法吗？牺牲精度（松散一些匹配项）以保持性能是可以接受的。
谢谢！
您可以使用散列 tables 来减少查找操作，在 linux 内核 3.7+ 中有通用散列 table implementation，您可以在您的内核模块。它有非常简单易用的功能。
您必须根据您的要求构建一个密钥，比如 src/dest ip & port + 请求唯一 ID 并在散列 table 中使用它，散列 table 存储一个值每个键，值都可以是指向真实请求负载的指针。基于它的实现，它可能有 O(n) 的最坏情况，但是具有良好填充因子的散列 tables 可以轻松实现 O(1) 或 O(logN)。
为了进一步优化，您可以使用布隆过滤器，布隆过滤器可用于过滤无效或丢弃的请求。它非常快，并且没有像 hash tables 这样的内存访问惩罚。但与 hash table 不同，它不存储每个键的值，因此您还需要 hash table。 Linux 内核 here
有布隆过滤器实现
我使用 Netfilter 的钩子实现了一个 Linux 内核模块，用于检查主机的所有传入和传出数据包。使用此模块，我可以监视该主机上给定应用程序 运行ning 的流量，即，通过了解 src/dst ports/IPs 我可以过滤掉（分类）相关数据包received/sent。
我接下来要做的是在 运行 时匹配传入应用程序的请求与相应的传出响应。每个 request/response 都由 src/dst IP 和唯一 ID 标识。
天真的实现 是流动的：
- 将每个传入请求存储在列表中（array/linked 列表等）
- 对于每个外发回复：
- 搜索列表以找到匹配的请求。如果找到请求，请将其从列表中删除。
- 定期 p运行e 删除早于 X 秒的请求的请求列表。
问题 是对于每个响应，这种天真的算法需要通过请求列表进行线性搜索以识别匹配项。这在高利率下是昂贵的。
你能推荐一个可以降低复杂度的算法吗？牺牲精度（松散一些匹配项）以保持性能是可以接受的。
谢谢！
您可以使用散列 tables 来减少查找操作，在 linux 内核 3.7+ 中有通用散列 table implementation，您可以在您的内核模块。它有非常简单易用的功能。
您必须根据您的要求构建一个密钥，比如 src/dest ip & port + 请求唯一 ID 并在散列 table 中使用它，散列 table 存储一个值每个键，值都可以是指向真实请求负载的指针。基于它的实现，它可能有 O(n) 的最坏情况，但是具有良好填充因子的散列 tables 可以轻松实现 O(1) 或 O(logN)。
为了进一步优化，您可以使用布隆过滤器，布隆过滤器可用于过滤无效或丢弃的请求。它非常快，并且没有像 hash tables 这样的内存访问惩罚。但与 hash table 不同，它不存储每个键的值，因此您还需要 hash table。 Linux 内核 here
有布隆过滤器实现