实现BlackList的最有效方法

Question

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

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

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

我有时间，可以从零开始创建任何东西。难度对我来说并不重要。如果你能用上任何东西，你应该怎么做？

Answer 1

提高这种系统性能的一种方法是使用布隆过滤器。这是一种概率数据结构，占用的内存非常少，其中可能会出现假阳性，但不会出现假阴性。

当您想要查找IP地址时，首先要检查Bloom过滤器。如果未命中，您可以立即允许交通。如果有一个命中，你需要检查你的权威数据结构(例如哈希表或前缀树)。

您还可以创建一个小缓存，其中包含“在Bloom Filter中命中但实际上允许的”地址，在Bloom Filter之后但在权威数据结构之前进行检查。

基本上，这个想法是以牺牲慢速路径(拒绝IP地址)为代价来加速快速路径(允许IP地址)。

Answer 2

哈希表是未来的发展方向。它们的查找、插入和删除的平均复杂度为O(1)！它们往往比树占用更多的内存，但速度要快得多。

由于您只需处理32位整数(当然，您可以将IP转换为32位整数)，因此事情将变得非常简单和快速。

您可以只使用排序数组。插入和移除的成本是O(n)，但是查找是O(log )，特别是对于每个ip来说，内存只有4字节。实现非常简单，也许太多了:D

二叉树的查找、插入和删除的复杂度为O(log )。一个简单的二叉树是不够的，然而，你需要一个AVL树或一个红黑树，这可能是非常烦人和复杂的实现。AVL和RBT树能够自我平衡，我们需要这样做，因为不平衡的树查找的时间复杂度最差，为O(n)，这与简单的链表是一样的！

如果你需要禁止ip范围，而不是单一和唯一的ip，你可能需要一个Patricia Trie，也称为Radix Tree，它们是为单词字典和ip字典而发明的。然而，如果写得不好，这些树可能会更慢\平衡。哈希表对于简单的查找总是更好！它们太快了，以至于不是真的:)

现在，关于同步：

如果您只在应用程序启动时填充一次黑名单，则可以使用一个普通的只读哈希表(或基数树)，它不存在多线程和锁定的问题。

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

如果您需要非常频繁的更新，我建议您使用并发哈希表。警告:不要编写自己的代码，它们非常复杂且容易出现bug，请在web上查找实现！它们使用了大量(相对)新的新处理器的原子CAS操作(CAS表示比较和交换)。这些是一组特殊的指令或指令序列，允许在单个原子操作中比较和交换内存中的32位或64位字段，而无需锁定。使用它们可能很复杂，因为你必须非常了解你的处理器，你的操作系统，你的编译器和算法本身是违反直觉的。有关归档存储的更多信息，请参阅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，您需要4个字节的IP和一个指针。你还需要一个很大的指针数组(或者32位整数加上一些技巧)，它的大小应该是一个大于应该存储的项数的质数。当然，如果需要，哈希表还可以根据需要调整自身大小，但它们也可以存储比质数更多的项，代价是查找时间变慢。

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

我希望这是一个多线程应用程序，而不是一个多进程应用程序(fork)。如果不是多线程，你就不能以快速可靠的方式共享一部分内存。

Answer 3

“最有效”是一个很难量化的术语。显然，如果您有无限的内存，那么您将为每个IP地址创建一个bin，并且可以立即对其进行索引。

一种常见的权衡是使用B-tree类型的数据结构。可以为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地址。