Лучший выбор для структуры данных в памяти для фильтра IP-адресов в Java

Когда дело доходит до этого, мне просто нужно знать, присутствует ли IP-адрес в любом из диапазонов 5M.

Я бы рассмотрел n-арное дерево, где n=256, и работал бы с точечным адресом, а не с преобразованным целым числом.

Верхний уровень будет массивом из 256 объектов. Запись null означает «Нет», диапазон, содержащий адрес, отсутствует, поэтому в вашем примере 192.168.1.0/24 array[192] будет содержать объект, но array[100] может быть нулевым, поскольку для любого 100.x.x.x/n не был определен диапазон.

Сохраненный объект содержит (ссылку на) другой массив[256] и спецификатор диапазона, только один из двух будет установлен, поэтому 192.0.0.0/8 будет иметь спецификатор диапазона, указывающий, что все адреса в этом диапазоне должны быть отфильтрованы. Это позволит использовать такие вещи, как 192.255.0.0/10, где первые 10 бит адреса являются значащими 1100 0000 11xx xxxx - в противном случае вам нужно проверить следующий октет в массиве 2-го уровня.

Первоначальное объединение перекрывающихся диапазонов, если таковые имеются, в более крупные диапазоны... например. 3 .. 10 и 7 .. 16 становятся 3 .. 16 ... позволяют это, поскольку вам не нужно связывать данный IP-адрес с каким диапазоном, в котором он определен.

Для этого должно потребоваться не более 8 сравнений. Каждый октет изначально используется непосредственно как индекс, за которым следует сравнение для нуля, сравнение для конечного узла (это диапазон или указатель на следующий уровень дерева)

Теоретически потребление памяти в худшем случае составляет 4 ГБ (256 ^ 4), если каждый IP-адрес находится в диапазоне фильтрации, но, конечно, это объединится в один диапазон, поэтому на самом деле будет только 1 объект диапазона. Более реалистичный наихудший случай, вероятно, будет больше похож на (256 ^ 3) или 16,7 МБ. В реальном мире, вероятно, большинство узлов массива[256] на каждом уровне пусты.

Это по существу похоже на кодирование Хаффмана/префикса. Самый короткий отдельный префикс может прекратиться, как только будет найден ответ (диапазон), поэтому часто у вас будет среднее значение < 4 сравнений.

Я бы использовал отсортированный массив int (базовый адрес) и другой массив того же размера (конечный адрес). Это будет использовать 5M * 8 = 40 МБ. Первый IP-адрес является базовым, а второй IP-адрес — последним адресом в диапазоне. Вам нужно будет удалить пересечения.

Чтобы узнать, фильтруется ли адрес для двоичного поиска O (log N), и если нет точного совпадения, проверьте, что он меньше (или равен) верхней границе.

Я нашел этот двоичный алгоритм отсечения в проекте 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);
}

Кажется, он неплохо выступает. Если вы знаете о чем-то более быстром, пожалуйста, дайте мне знать.

Если у вас есть только адрес 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 для фильтрации 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-адрес находится в любой из подсетей, у вас есть хороший простой фильтр, и вам не нужно создавать структуру данных, которую вам придется тестировать. Если этого недостаточно, то переходим к оптимизации. Не оптимизируйте преждевременно :)

Вот начало ответа, я вернусь, когда у меня будет больше свободного времени

Настройка:

1. Отсортируйте диапазоны по начальному номеру.
2. Since these are IP Addresses, I assume that none of the ranges overlap. If there are overlaps, you should probably run the list merging ranges and trimming unnecessary ranges (ex. if you have a range 1 - 10, you can trim the range 5 - 7).
   1. To merge or trim do this (assume range a immediately precedes range b):
      1. If b.end < a.end then range b is a subset of range a and you can remove range b.
      2. Если b.start ‹ b.end и b.end > a.end, вы можете объединить диапазоны a и b. Установите a.end = b.end, затем удалите диапазон b.