Хранение большого количества IP-адресов в памяти

Question

Вопрос немного длинный, поэтому, пожалуйста, потерпите меня.

Я пишу Java-код для агрегирования потоков от трассировки сети на целый день в бункеры по 84 секунды для каждой подсети. В настоящее время у меня есть до 256 подсетей и 1024 бинов для каждой подсети. Я использую это для получения статистики о характеристиках трафика, таких как количество подключений, входных / выходных байтов, количество внешних IP-адресов в каждом окне каждой подсети. В то время как соединения, входящие / исходящие байты просты, получение уникального числа IP-адресов exteran вызывает ошибки OutOfMemory.

Чтобы определить уникальное количество внешних IP-адресов, мне нужно сохранить IP-адрес в некоторой структуре данных, такой как хеш-таблица, и в конце трассировки я могу получить размер этой хеш-таблицы. Это означает, что у меня будет 1024 * 256 хеш-таблиц, каждая из которых хранит большое количество 12-15-байтовых строк IP-адресов (от десятков до тысяч). Это быстро взрывается, и системе не хватает памяти (я пытался установить размер кучи Java до 2 ГБ безрезультатно). Кто-нибудь может предложить способ эффективного хранения такого большого количества объектов?

Я попытался использовать bitset (преобразование ip в int), однако, учитывая, что ip-адреса очень и очень редки, это не помогает в ситуации с памятью. В качестве последнего средства я мог бы использовать разреженные матрицы из библиотеки colt с каждым двойным сохранением до 64 IP-адресов, но я хотел бы получить мнение на случай, если я упущу что-то очевидное и смогу сэкономить время на написание / отладку такой оболочки. *

Sidenotes: Чтобы получить представление о масштабе, я вижу несколько сотен миллионов потоков на трассу, которые я анализирую и собираю. В большинстве случаев я использую от 10 до 20 из 256 подсетей, но я бы хотел, чтобы решение было масштабируемым для всех 256 подсетей.

Answer 1

Обновление: Если вы сохранили все 4 миллиарда адресов IPv4 в виде одного массива, вы можете представить время как отдельный короткий.

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

Это будет 8 ГБ с 65 КБразрешение по времениПросто подумайте, потому что это накладывает верхнюю границу на память, потому что любая другая схема должна быть под этим.Если вы используете байт, это будет 256-кратное разрешение для 337,5 с на бин и 4 ГБ.

Теперь вам остается только сказать, что вы видели хотя бы пакет внутри этого сегмента.Если вам нужен счетчик, который снова увеличивает объем памяти, но с коротким замыканием вы можете использовать 1024 сегмента с потенциальным 6-битным разрешением для подсчета: максимум 64 пакета.

Теперь со 100 миллионами уникальных IP-адресов, которые уменьшают объем памяти в 10 раз, поэтому вы теоретически перешли с 8 ГБ до 800 МБ.Не выделяя всего пространства, вы думаете, что можете сэкономить память, но вам все равно придется хранить 4 байта на IP: 400 МБ только для IP-адресов + 400 МБ для некоторой структуры сортировки для их хранения (указатели 100 МБ * 4 байта) и 2 байта длявремя: минимум 1 ГБ.Распределяя все пространство, вы получаете возможность пропустить повторное сохранение 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-адресе, выясните, к какой корзине он принадлежит, затем откройте файл и найдите его там, чтобы найти ответ.Эта схема означает, что вы можете увеличивать или уменьшать масштаб в зависимости от размера ваших данных, а также увеличивая и понижая свои границы.Вы можете повысить производительность, изменив структуру файлов, которые вы записываете для каждого бина.

Я знаю, извините за длину!: -)

Answer 2

Не уверен, почему у тебя 1024 * 256?

Вам нужна только одна структура данных для хранения всех данных; Используйте красно-черное дерево с ключом IP в качестве 4-байтового целого числа. Это дает вам O (log (n)) время поиска, что означает, что наихудший случай - 32 сравнения для поиска IP. Или HashMap, набранный Integer.

В каждом узле есть свои 84 «мусорных» объекта (хранящихся в связанном списке, массиве или в любом другом месте, имеющем смысл с точки зрения имеющегося у вас шаблона доступа), которые содержат информацию, которую вы хотите сохранить. Если вам нужен только агрегат ... храните только агрегат. Это действительно сократило бы использование вашей памяти.

Редактировать: Я склонен забывать о подписи Java int. Это не представляет проблемы, если вы на самом деле не хотите легко их сортировать, в этом случае используйте long / Long

Answer 3

У меня будет несколько бит-наборов, например,

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

Это будет всего 1 бит на адрес, в зависимости от того, как сэкономить IP-адрес. Поскольку многие диапазоны адресов не отображаются, потребление памяти может быть очень эффективным. Его очень сложно протестировать без реалистичного набора данных. ;)

В худшем случае объем памяти составляет 512 МБ, но для реалистичных наборов данных он должен быть намного меньше этого значения.