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

Question

У меня есть файл, который имеет формат CIDR, подобный этому 192.168.1.0/24, и он преобразуется в эти два столбца Strucutre

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;
}

Учтите, что существует более 5 миллионов записей (low high : 3232236030 3232235777).
Также будут пересечения, чтобы IP мог происходить из нескольких диапазонов. Просто первый более чем хорошо.
Данные только для чтения.
Какой самый быстрый способ найти диапазон, к которому принадлежит ipToBefiltered? Структура будет полностью в памяти, поэтому нет поиска в базе данных.

UPDATE:

Я нашел этот Peerblock проект (его скачали более миллиона, поэтому я думаю, что он должен иметь несколько быстрых алгоритмов): http://code.google.com/p/peerblock/source/browse/trunk/src/pbfilter/filter_wfp.c

Кто-нибудь знает, какую технику использует проект для создания списка диапазонов и чем их искать?

Answer 1

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

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

Верхним уровнем будет массив из 256 объектов.Запись null означает «Нет», нет диапазона, содержащего адрес, поэтому в вашем примере 192.168.1.0/24 array [192] будет содержать объект, но array [100] может быть нулевым, поскольку для любых 100 не определено ни одного диапазона..xxx / 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 сравнений.Каждый октет первоначально используется непосредственно в качестве индекса, за которым следует сравнение для нулевого значения, сравнение для терминального узла (это диапазон или указатель на следующий уровень дерева)

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

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

Answer 2

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

Answer 3

Я нашел этот алгоритм бинарной резки в Vuze (он же azureus) project:

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);
}

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

Answer 4

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

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

Answer 5

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

Установка:

1. Сортировка диапазонов по начальному номеру.
2. Поскольку это IP-адреса, я предполагаю, что ни один из диапазонов не перекрывается. Если есть перекрытия, вам, вероятно, следует запустить слияние диапазонов списка и обрезку ненужных диапазонов (например, если у вас есть диапазон 1 - 10, вы можете обрезать диапазон 5 - 7).
   1. Чтобы объединить или обрезать, сделайте это (предположим, диапазон a непосредственно предшествует диапазону b):
      1. Если b.end Если b.start a.end, то вы можете объединить диапазоны a и b. Установите a.end = b.end, затем удалите диапазон b.