实现BlackList的最有效的方法

我开发了一个Ip过滤器，并且猜测如何使用任何类型的esque数据结构开发一个非常高效和快速的BlackList过滤器。实现BlackList的最有效的方法

我想要做的事情很简单，我必须检查阻止的IP列表中的每个传入/传出连接。

IP分散，内存使用应该是线性的（不依赖于阻塞列表的数量，因为我想在有限的系统（自制软件路由器）上使用）。

我有时间并且可以创建零之间的任何东西。困难对我来说并不重要。如果你可以使用任何东西，你应该做什么？

来源

2011-10-26 bratao

如果你变得更具体，例如，它会非常有帮助。描述一些性能将很重要的场景。如果需要，它将完全采用不同的实现。你是针对整个IP范围，如果你的目标是“分散的”单个IP地址。 – Jon

谢谢jon提示，我指定了更多！ – bratao

如果内存使用量保持不变，那么很明显会对黑名单中可能存在的最大IP数量施加限制。 –

提高此类系统性能的一种方法是使用Bloom Filter。这是一种概率数据结构，占用很少的内存，其中可能出现误报，但是假阴性则不可能。

当你想查找一个IP地址，你首先检查在布隆过滤器。如果有一个错过，你可以立即允许交通。如果遇到问题，您需要检查您的权威数据结构（例如哈希表或前缀树）。

您还可以创建一个小的缓存“在布隆过滤器命中，但实际上允许”地址，在布隆过滤器后，但在权威数据结构之前被选中。

基本思路是加快在慢速路径的代价（允许的IP地址）的快速路径（IP地址被拒绝）。

来源

2011-10-27 05:14:37 caf

Thnak你，那就是我想要的。 – bratao

散列表是要走的路。他们平均O（1）查找，插入和删除的复杂性！他们往往比树木占用更多的内存，但速度要快得多。

由于您只是使用32位整数（当然，您可以将IP转换为32位整数），事情会非常简单快速。

您可以使用排序后的数组。插入和移除成本是O（n），但查找是O（log n），特别是每个ip的内存仅为4个字节。实现非常简单，可能太多了：D

二叉树的复杂度为O（log n），用于查找，插入和删除。但是，一个简单的二叉树是不够的，你需要一个AVL树或一个红黑树，这可能非常烦人而且很难实现。 AVL和RBT树能够自我平衡，我们需要这样做，因为不平衡树的查找时间复杂度为O（n），这与简单的链表相同！

如果不是单一和唯一的IP你需要禁止IP范围，可能你需要一个Patricia Trie，也称为基数树，它们是为词典和IP词典而发明的。但是如果写得不好，平衡的话，这些树可能会变慢。对于简单的查找，散列表总是更好！他们太快是真实:)

现在关于同步：

如果您在应用程序启动填补了黑名单只有一次，你可以用一个简单的只读哈希表（或基数树），唐”没有关于多线程和锁定的问题。

如果您需要不经常更新它，我建议您使用读写器锁。

如果你需要非常频繁的更新，我会建议你使用并发散列表。警告：不要自己写，它们非常复杂，容易出错，在网上找到一个实现！他们使用很多（相对）新的原子CAS操作的新处理器（CAS意味着比较和交换）。这些是一组特殊的指令或指令序列，它们允许比较内存上的32位或64位字段，并在单个原子操作中进行交换，而无需锁定。使用它们可能很复杂，因为你必须非常清楚你的处理器，操作系统，编译器和算法本身是否违反直觉。有关CAS的更多信息，请参阅http://en.wikipedia.org/wiki/Compare-and-swap。

并发AVL树被发明，但它是如此复杂，我真的不知道该说这些:)例如什么，http://hal.inria.fr/docs/00/07/39/31/PDF/RR-2761.pdf

我刚刚发现，并发基数树存在： ftp://82.96.64.7/pub/linux/kernel/people/npiggin/patches/lockless/2.6.16-rc5/radix-intro.pdf但也很复杂。

并行排序数组不存在，当然，你需要更新一个读写锁。

也是内存来处理非并发哈希表所需要的量可以说是相当少考虑：对于每个IP您需要的IP和指针4字节。你还需要一个大数组指针（或一些技巧的32位整数），其大小应该是比应该存储的项目数大的素数。当需要时，如果需要，哈希表当然也可以调整自己的大小，但是它们可以存储比该素数更多的项目，代价是查找速度较慢。

对于树和散列表，空间复杂度都是线性的。

我希望这是一个多线程的应用程序，而不是多进程应用程序（叉）。如果不是多线程，则不能以快速可靠的方式共享部分内存。

来源

2011-10-26 23:36:15

“最高效”是一个难以量化的术语。显然，如果你有无限的内存，你将有一个垃圾箱为每个IP地址，并可以立即索引到它。

一个常见的折衷是使用B树型数据结构。第一级容器可以预设为IP地址的前8位，这可以存储指向包含所有当前阻止的IP地址的列表的大小和大小。第二个列表将被填充以防止不必要的memmove()调用并可能排序。（具有大小和在存储器中列表的长度允许的列表中轻微昂贵的插入时间上就地二进制搜索。）

例如：

127.0.0.1 =insert=> { 127 :: 1 } 
127.0.1.0 =insert=> { 127 :: 1, 256 } 
12.0.2.30 =insert=> { 12 : 542; 127 :: 1, 256 }

这样的开销数据结构最小，总存储大小是固定的。显然，最坏的情况将是具有相同最高位的大量IP地址。

来源

2011-10-26 23:49:03 utopianheaven

实现BlackList的最有效的方法

回答

相关问题