logo标签列表

Java中用于IP地址过滤的内存数据结构的最佳选择

javafilteripin-memory
7
我有一个CIDR格式的文件，像这样：192.168.1.0/24，它被转换成了这个两列结构。
3232236030 3232235777

每个字符串IP地址的转换都使用以下代码：
String subnet = "192.168.1.0/24";
SubnetUtils utils = new SubnetUtils(subnet);

Inet4Address a = (Inet4Address) InetAddress.getByName(utils.getInfo().getHighAddress());
long high = bytesToLong(a.getAddress());
Inet4Address b = (Inet4Address) InetAddress.getByName(utils.getInfo().getLowAddress());
long low = bytesToLong(b.getAddress());

private static long bytesToLong(byte[] address) {
   long ipnum = 0;
   for (int i = 0; i < 4; ++i) {
       long y = address[i];
       if (y < 0) {
           y += 256;
       }
       ipnum += y << ((3 - i) * 8);
   }
   return ipnum;
}

考虑到有超过500万条记录(low high : 3232236030 3232235777)。此外，IP可能来自多个范围，只需要第一个即可。数据是只读的。找到ipToBefiltered所属范围的最快方法是什么？结构将完全存储在内存中，因此不需要数据库查找。
更新：我发现了这个Peerblock项目（已经有超过100万次下载，所以我认为它必须有一些快速算法）：http://code.google.com/p/peerblock/source/browse/trunk/src/pbfilter/filter_wfp.c 有人知道该项目用于创建范围列表然后搜索它们的技术吗？
该结构将完全存储在内存中，因此不需要进行数据库查找。- 为什么不使用内存数据库？ - corsiKa
你想知道给定的IP所属的范围，而不仅仅是它是否在某个定义好的范围内吗？请找出该IP所属的范围。 - Stephen P
@Mat 这些范围有重叠吗？ - armandino
5个回答
7
当涉及到IP地址是否存在于5M范围内时，我只需要知道这一点。
我会考虑一个n元树，其中n=256，并从点分地址而不是转换后的整数开始工作。
顶层将是256个对象的数组。null条目表示“否”，即没有包含该地址的范围，因此在您的示例192.168.1.0/24中，array[192]将包含一个对象，但array[100]可能为null，因为没有为任何100.x.x.x/n定义范围。
存储的对象包含（引用）另一个数组[256]和范围指定器，只有其中之一设置，因此192.0.0.0/8将以指示所有该范围内的地址都要进行过滤的范围指定器结束。这将允许类似于192.255.0.0/10的事情，其中地址的前10位是有效的1100 0000 11xx xxxx - 否则，您需要检查第二级数组中的下一个八位组。
最初将重叠的范围合并成更大的范围...例如3..10和7..16变为3..16...因为您不需要将给定的IP与定义它的范围相关联。
这应该不需要超过8个比较。每个八位组最初直接用作索引，然后是对null的比较，终端节点的比较（它是范围还是指向下一个树级别的指针）
最坏的情况下，理论上的内存消耗为4 GB（256 ^ 4），如果每个IP地址都在过滤范围内，但当然会合并为单个范围对象。更现实的最坏情况可能更接近256 ^ 3或16.7 MB。实际使用中，每个级别的大多数array[256]节点可能为空。
这本质上类似于Huffman /前缀编码。最短的不同前缀可以尽快终止答案（范围）被找到，因此通常您将具有<4个比较的平均值。
1

我会使用一个已排序的 int 数组（基地址）和另一个相同大小的数组（结束地址）。这将占用 5M * 8 = 40 MB 的空间。第一个 IP 是基础，第二个 IP 是范围内的最后一个地址。你需要消除交集。

要查找地址是否被过滤到二进制搜索 O(log N) 中，如果不是精确匹配，则检查它是否小于（或等于）上限。

1
我在Vuze（又名Azureus）项目中找到了这个二分查找算法：
public IpRange isInRange(long address_long) {
    checkRebuild();

    if (mergedRanges.length == 0) {
        return (null);
    }

    // assisted binary chop

    int bottom = 0;
    int top = mergedRanges.length - 1;
    int current = -1;

    while (top >= 0 && bottom < mergedRanges.length && bottom <= top) {

        current = (bottom + top) / 2;

        IpRange e = mergedRanges[current];

        long this_start = e.getStartIpLong();
        long this_end = e.getMergedEndLong();

        if (address_long == this_start) {
            break;
        } else if (address_long > this_start) {

            if (address_long <= this_end) {
                break;
            }

            // lies to the right of this entry

            bottom = current + 1;

        } else if (address_long == this_end) {
            break;
        } else {
            // < this_end

            if (address_long >= this_start) {
                break;
            }
            top = current - 1;
        }
    }

    if (top >= 0 && bottom < mergedRanges.length && bottom <= top) {

        IpRange e = mergedRanges[current];

        if (address_long <= e.getEndIpLong()) {
            return (e);
        }

        IpRange[] merged = e.getMergedEntries();

        if (merged == null) {
            //inconsistent merged details - no entries
            return (null);
        }

        for (IpRange me : merged) {
            if (me.getStartIpLong() <= address_long && me.getEndIpLong() >= address_long) {
                return (me);
            }
        }
    }
    return (null);
}

看起来表现还不错。如果您知道任何更快的东西，请让我知道。

1
如果您只有CIDR地址（或其列表），并且想要检查某个ipAddress是否在该CIDR（或CIDR列表）的范围内，只需定义一个SubnetUtils对象的集合即可。除非您正在过滤大量的N个地址，否则这都是字符串比较，执行速度非常快。您不需要基于高/低位顺序构建二叉树以及所有复杂的操作。
String subnet = "192.168.1.0/24";
SubnetUtils utils = new SubnetUtils(subnet);
//...
//for each subnet, create a SubnetUtils object
Set<SubnetUtils> subnets = getAllSubnets();
//...

使用Guava Predicate来过滤不在您子网集合范围内的ip地址：
   Set<String> ipAddresses = getIpAddressesToFilter();
   Set<String> ipAddressesInRange = 
       Sets.filter(ipAddresses, filterIpsBySubnet(subnets))


   Predicate<String> filterIpsBySubnet(final Set<SubnetUtils> subnets){
       return new Predicate<String>() {
            @Override
            public boolean apply(String ipAddress) {
                for (SubnetUtils subnet : subnets) {
                    if (subnet.getInfo().isInRange(ipAddress)) {
                        return true;
                    }
                }
                return false;
            }
        };
   }

现在，如果IP在任何一个子网中，你就有了一个简单的好用的过滤器，而不需要构建一个需要进行单元测试的数据结构。如果这样的性能还不够好，那么再去优化。不要过早地进行优化 :)
0

这里是一个答案的开头，我会在有空的时候回来。

设置：

  1. 按起始数字对范围进行排序。
  2. 由于这些是IP地址，我假设没有任何重叠的范围。如果有重叠，您应该运行列表合并范围和修剪不必要的范围（例如，如果您有一个范围1-10，则可以修剪范围5-7）。
    1. 要合并或修剪，请执行以下操作（假设范围a紧接着范围b）：
      1. 如果b.end < a.end，则范围b是范围a的子集，您可以删除范围b。
      2. 如果b.start < b.end且b.end > a.end，则可以合并范围a和b。将a.end = b.end然后删除范围b。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接