Проект Generator позволяет генерировать текстовые файлы со списком рандомных IP адресов разделенных переносом строки. Требуемое количество адресов можно задать в main в переменной ipCount. Можно задать тип переноса строк CRLF/LF через переменную isCrLf.

Сгенерированный файл сохраняется в папке files. Туда же кладется файл со статистикой количества повторов айпи адресов.

Проект Analyzer позволяет анализировать большие текстовые файлы содержащие IP адресов разделенных переносом строки. Поддерживаются разделители LF и CRLF.

Анализатор применяет шардированный массив для подсчета количества повторов айпи адресов. Так как по задаче требуется только определить количество уникальных, т.е. адресов встречающихся только один раз, нам нужно считать только до 2. 0 - не встречается, 1 - встречается один раз, 2 - встречается два и более раза. Для этого нам достаточно хранить счетчик в 2 битах. В одном байте храним сразу 4 значения.

Анализатор для ускорения логически делит файл на куски и обрабатывает каждую в разных потоках. Потоки считывают строки с айпи адресами и преобразуют их в UInt значение. Это значение выступает в качестве индекса в массиве, указывает на 2-битовый блок в шардированном массиве. На каждый айпи адрес производится инкрементация значения в массиве согласно UInt индексу. Значение блока увеличивается только до 3 (0b11).

После прохода всего файла, делается подсчет количества уникальных айпи адресов, путем определения количества блоков в массиве со значением 1.

Шардированный массив для хранения 2^32 блоков по 2 бита каждый, для экономии памяти. Массив должен занимать в памяти 1ГБ + небольшой размер вспомогательных структур.

Шардирование, т.е. разделение массива на части, необходимо для ускорения, во избежание ожиданий при циклах блокировки/разблокировки частей при параллельном доступе нескольких потоков к частям массива.

В значении блока храним значения от 0 до 3, так как для определения уникальности IP адреса этого достаточно.

Блоки хранятся в массиве байтов. В одном байте содержится 4 блока (2 бита * 4 = 8 бит = 1 байт) Переданное UInt значение, как числовое представление IP адреса, используется как индекс в этом массиве, и указывает на блок.

При инкрементации делается блокировка в корутине части массива в котором содержится инкрементируемый блок. После записи нового значения часть массива разблокировывается.

Максимальный размер кучи: 2ГБ (-Xmx2g)
Исходный файл 42.6 ГБ (45_843_685_941 байт)
Количество IP адресов: 3 миллиарда строк
Анализ занял время: 1972 сек (32 мин 52 сек)
Анализ массива занял время: 40 сек.

Максимальный размер кучи: 2ГБ (-Xmx2g)
Исходный файл: 66.5 ГБ (71_406_206_674 байт)
Количество IP адресов: 5 миллиардов строк
Анализ занял время: 2261 сек (37 мин 41 сек)
Анализ массива занял время: 33 сек.

Можно ускорить процесс подсчета за счет оптимального подбора:

• размера части массива (шардов), в зависимости от размера исходного файла
• количества потоков (чанков файла)
• размера буфера чтения чанка