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

我有一个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;
}

假设(low high : 3232236030 3232235777)有超过500万条记录。
也会有交集，所以IP可以来自多个范围。只有第一个比OK还好。
数据是只读的。
找到ipToBefiltered所属范围的最快方法是什么?该结构将完全在内存中，因此没有数据库查找。

更新:

我发现了这个Peerblock项目(它有超过百万的下载，所以我认为它必须有一些快速的算法):http://code.google.com/p/peerblock/source/browse/trunk/src/pbfilter/filter_wfp.c

有谁知道什么技术是用于创建范围列表的项目，而不是搜索它们?

当涉及到它时，我只需要知道IP是否存在于任何5M范围内。

我将考虑一个n-ary树，其中n=256，并且从虚线地址而不是转换后的整数开始工作。

顶层是一个包含256个对象的数组。null条目表示"No"，没有包含地址的范围，因此给定示例192.168.1.0/24数组[192]将包含一个对象，但数组[100]可能是空的，因为没有为任何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的比较，终端节点的比较(它是一个范围还是一个指向下一个树级别的指针)

如果每个 IP地址都在过滤范围内，理论上最坏的情况下内存消耗是4 GB (256 ^ 4)，但当然这将合并成一个范围，因此实际上只有一个范围对象。更现实的最坏情况可能更像(256 ^ 3)或16.7 MB。现实世界的使用可能会使每个级别的大多数数组[256]节点为空。

这本质上类似于霍夫曼/前缀编码。只要找到答案(一个范围)，最短的不同前缀就可以终止，所以您通常会得到< 4比较的平均值。

我将使用int(基址)和另一个相同大小的数组(结束地址)的排序数组。这将使用5M * 8 = 40 MB。第一个IP是基本地址，第二个IP是范围内的最后一个地址。你需要删除交叉路口。

查找一个地址是否被过滤为二进制搜索O(log N)，如果不是精确匹配，检查它是否小于(或等于)上界。

我在Vuze (aka 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);
}

似乎表现得很好。如果你知道更快的事情，请告诉我。

如果你只是有一个CIDR地址(或一个CIDR列表)，你想检查一些ipAddress是否在该CIDR(或CIDR列表)的范围内，只需定义一组SubnetUtils对象。

除非你要过滤一个非常大的N个地址，否则这都是字符串比较，执行起来会非常快。您不需要基于高/低阶位和所有复杂的Jazz构建二叉树。

String subnet = "192.168.1.0/24";
SubnetUtils utils = new SubnetUtils(subnet);
//...
//for each subnet, create a SubnetUtils object
Set<SubnetUtils> subnets = getAllSubnets();
//...

使用Guava谓词来过滤不在您的子网范围内的ipaddress:

   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在任何子网中，你有一个很好的简单过滤器，你不必建立一个数据结构，你将不得不进行单元测试。如果这还不够性能，那么就去优化。不要过早优化:)

这是一个答案的开头，当我有更多的空闲时间我会回来的

设置:

按起始编号排序。
由于这些是IP地址，我假设这些范围都没有重叠。如果有重叠，你可能应该运行列表合并范围并修剪不必要的范围(例如，如果你有一个范围1 - 10，你可以修剪范围5 - 7)。
1. 要合并或修剪，这样做(假设范围a紧接在范围b之前):
  1. If b.end <a.end则范围b是范围a的子集，您可以删除范围b。>
  2. b.start a.end则可以合并范围a和b.设置a.end = b.end则删除范围b.

更新:

有谁知道什么技术是用于创建范围列表的项目，而不是搜索它们?

相关内容

最新更新

热门标签：