在内存中存储大量IP地址

Question

在内存中存储大量IP地址

javadata-structuresout-of-memorysparse-matrixbitset

3

问题有点长，请耐心阅读。

我正在编写Java代码，将全天网络跟踪中的流聚合到每个子网的84秒时间段中。目前，我最多有256个子网和1024个子网的时间段。我使用这个来获取流量特征统计数据，例如每个子网每个窗口的连接数、输入/输出字节数、每个窗口的外部IP地址数量。虽然连接、输入/输出字节很简单，但获取唯一的外部IP地址数量会导致OutOfMemory错误。

为了确定唯一的外部IP地址数量，我需要将IP地址存储在某些数据结构（如哈希表）中，并在跟踪结束时获取此哈希表的大小。这意味着我将有1024*256个哈希表，每个哈希表都存储大量的12-15字节IP地址字符串（数十到数千个）。这很快就会爆炸，系统会因内存不足而崩溃（我已经尝试将Java堆大小设置为最多2GB，但没有效果）。有人能建议一种有效地存储如此多的对象的方法吗？

我尝试使用位集（将IP转换为int），但考虑到IP地址非常稀疏，它对内存情况没有帮助。作为最后的手段，我可能会使用colt库稀疏矩阵，每个double存储多达64个IP地址，但我想听听意见，以防我遗漏了一些明显的东西，可以节省编写/调试这样一个包装器的时间。

附注：为了了解规模，我看到每个跟踪中有数亿个流，我解析和聚合这些流。在大多数情况下，我使用256个子网中的10到20个，但我希望解决方案可扩展到所有256个子网。

- Faisal

首先，进行一些快速的草稿计算：102425615*10000/(1024^3) = 大约40 GB，假设您的哈希表只占用一个字节（实际上可能是几千个字节）。这很多，但并不太多，昂贵的服务器可以处理... ;)我不清楚为什么您需要将所有这些内容存储在RAM中，但是假设您不能使用磁盘数据库，似乎最好将负载分布在多台机器上。 - CodeBlind

你有多少个不同的IP地址？它们是否聚集在特定的子网中？ - kdgregory

Ben，我是研究生，没有使用服务器群的权限。目前每次跟踪大约需要10-15分钟。如果我使用基于分布式的存储，那将需要太多时间，可能需要数小时甚至一天的时间。我需要统计每个子网中每个bin中所有唯一IP地址的数量，并且这需要检查存储以确保唯一性。kdgregory，我正在记录所有连接到子网的ip地址机器的计数。可能的范围是IP-V4地址的全部，没有限制。你可能在8.8.8.8上访问Google，而另一个地址是202.192.1.1。 - Faisal

我真正要问的问题是关于稀疏性的。如果您的数据确实是稀疏的（即，数百万地址集中在几千个IP范围内），那么您可以利用Java多维数组没有完全分配的事实（即，int[256] [] [] [] 只占用了256个指针所需的空间）。 - kdgregory

看一下SparseBitSet，它应该会大幅减少你的内存消耗，你可能能够回到原来的BitSet实现：https://github.com/brettwooldridge/SparseBitSet - brettw

3个回答

1

不确定为什么你有1024*256？

你只需要一个数据结构来保存所有的数据；使用以IP地址作为4字节整数的红黑树作为键。这样可以获得O(log(n))的查找时间，这意味着最坏情况下需要32次比较才能找到一个IP地址。或者使用以Integer为键的HashMap。

在每个节点中，有84个“bin”对象（存储在链表、数组或其他适合访问模式的数据结构中），包含您想要存储的信息。如果您只需要聚合数据...只存储聚合数据。这真的会减少您的内存使用量。

编辑：我经常忘记Java int是有符号的。除非你真的想轻松排序它们，否则这不会造成问题，此时请使用long/Long。

- Brian Roach

我的内部网络属于B类，它有256 * 256个IP地址的范围。我将其划分为256个子网，因此每个子网都像128.0.1.x、128.0.2.x直到128.0.255.x。每个子网有1024个时间段，这1024个时间段组成了24小时。因此，来自128.0.1.127并在整个一天保持活动状态的连接将在该特定子网的所有1024个时间段中具有目的地。子网是基于内部网络的IP地址，而我想跟踪内部用户连接到的所有外部IP地址。可以将其视为128.0.1.x中的人们浏览的所有站点的IP地址。 - Faisal

考虑到所有这些因素，从我看来，当外部IP地址本身是子网的聚合部分时，你似乎正在聚合外部IP地址。基本上，我想知道每个子网/二进制的独特外部IP数量，以便我可以确定是否突然出现了巨大的峰值。如果我对你的解决方案误解了，请纠正我。我应该在我的第一篇帖子中解释所有这些内容，但我希望保持相对简洁。 - Faisal

0

我会有多个BitSet，例如：

private final BitSet[] ips = new BitSet[256*256*256];

public void sample(int address) {
   BitSet bs = ips[address >>> 8];
   if (bs == null)
      ips[address >>> 8] = new BitSet();
   bs.set(address & 0xFFFF);
}

public int count() {
   int total = 0;
   for(BitSet bs: ips)
      total += bs.cardinality();
   return total;
}

这将根据IP地址的稀缺程度，每个地址仅需1位。由于许多地址范围不会出现，内存消耗可能非常高效。没有真实数据集很难进行测试。;)

最坏情况下的内存大小为512 MB，但对于真实数据集来说应该远远小于此值。

- Peter Lawrey

这非常有趣，但很简单。至少它将消除具有极少IP的子网的消耗。我将在我的数据集中报告测试结果。 - Faisal

刚试了这种方法，仍然出现了OutOfMemory错误。虽然第一个ips数组位置是基于需要分配的，但bs BitSet仍会获得各种各样的IP，并且平均需要4096字节。因此，即使在上半部分有15个不同的IP和256个子网中的20个，它也会消耗1024 * 20 * 15 * 409 = 1,258,291,200字节或1.2 GB内存，而且这是平均情况甚至更好的情况。无论如何，这是一个有趣的方法。 - Faisal

我已经调整了分发，现在你可以试试看吗？ - Peter Lawrey

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- chubbsondubs · Accepted Answer

更新：如果您将整个40亿个IPv4地址存储为单个数组，则可以将时间表示为单独的short。

short[] ipv4 = new short[Integer.MAX_VALUE * 2]; // technically not possible blah blah

那将是8GB，时间分辨率为65K。考虑到这一点，因为它将内存上限设定在此之下，任何其他方案都必须在此之下。如果您使用一个字节，每个垃圾桶的时间分辨率将为256，每个垃圾桶为337.5秒，4GB。

现在，这只给你一个位来说你至少看到了一个数据包。如果你需要计数，那么会再次增加内存，但是使用短整型，你可以使用1024个垃圾桶，并具有潜在的6位计数分辨率：最多64个数据包。

现在，对于1亿个唯一的IP地址，理论上可以将内存缩小10倍，因此从8GB降至800MB。虽然不分配整个空间可以节省内存，但是您仍然必须存储每个IP的4个字节：仅用于IP的400MB + 400MB用于某种结构来保存它们（100M指针* 4字节），以及2字节的时间：1GB最小。通过分配完整空间，您可以跳过再次存储IP的能力，因为您的哈希是您的IP。如果您减少数组，则不再拥有IP，因为它已被哈希掉。现在，您可以不存储IP并且仍然可以回答有关IP的问题，但是您无法重复。

如果您存储一系列子网掩码，然后将所有IP地址都滚动到该掩码下，并保留该子网掩码的统计信息，会怎样呢？例如，您有256个具有自己子网掩码的子网。您的程序将接受掩码的下限。那就是如果你的掩码是209.134.0.0/16并使用8的下限。然后，它将为该子网创建256个垃圾桶，这些垃圾桶属于209.134.0.0-209.134.255.255。您将为您拥有的所有256个子网重复同样的过程。使用8位的下限意味着每个子网的较低256个地址将被滚动。您可以将任何IP地址哈希到垃圾桶中并在内存中保留统计信息。但是，您不能说任何关于单个IP地址的事情。但是，如果您需要更高分辨率，只需删除较低的子网掩码，例如降至4，现在有更多的垃圾桶。

仅当其中有1个IP时才创建垃圾桶，因此如果您没有IP出现，您可以节省一些空间，因此它是低分辨率和高分辨率之间的平衡，但是足以跳过为您不需要的内容创建垃圾桶。

然后，您可以编写每个垃圾桶的日志，并在磁盘上跟踪每个垃圾桶中发生的情况。如果您想回答有关单个IP的问题，则找出它所属的垃圾桶，然后打开文件并在其中查找答案。这种方案意味着您可以根据数据的大小和提高和降低限制来进行缩放。您可以通过更改每个垃圾桶写出的文件结构来获得性能提升。

对不起，我知道长度有点长！ :-)