Алгоритмы сжатия данных Java - UPROGER

Сжатие данных – очень распространенная тема. В интернете мы можем найти множество материалов о ней. Существуют разные тесты для всех видов алгоритмов сжатия. Тесты производительности для Java существуют, но, все они немного устарели, поскольку были написаны давным-давно.

Эффективность сжатия (как производительности, так и размера) зависит от фактических данных. Поэтому для меня имело смысл повторить тесты, чтобы определить, какой алгоритм (если таковой имеется) подойдёт больше всего. Также хотелось просто побольше узнать о сжатии данных в Java.

Какие данные мы сравниваем?

Мы собираемся провести сравнение двух наборов данных: нашей внутренней структуру данных разного размера и набора искусственно сгенерированных случайным образом данных с различными степенями сжатия и размерами.

Внутренняя структура данных – это своего рода trie с URL-адресами, UUID и другой двоичной информацией (закодированной как сообщения protobuf).

Случайный датасеты – это просто рандомные символы из разных наборов. Вот функция для генерации данных:

private static java.util.Random rnd = ...;

private static byte[] generateImpl(
  byte[] alphabet,
  int length)
{
  byte[] result = new byte[length];
  for (int i = 0; i < result.length; i++) {
      result[i] = alphabet[rnd.nextInt(alphabet.length)];
  }
  return result;
}

Для разных текстов я рассчитал коэффициенты сжатия и вызвал разные наборы в соответствии с их коэффициентами:

low (1.3) -> "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
medium (2.1) -> "0123456789"
high (3.4) -> "0123"
extra high (6.2) -> "01"

Дисклеймер: случайный датасет не является полностью рандомным, как вы можете видеть, для целей сравнения. Это просто нестатический набор данных с более или менее стабильной степенью сжатия.

Алгоритмы сжатия

Я выбрал несколько популярных алгоритмов сжатия:

gzip через Apache Commons Compress
deflate также через Commons Compress
MySQL compression: в основном, он использует алгоритм deflate, а также префиксы с 4 байтами исходной длины данных (что помогает выделить буфер для распаковки). Через java.util.zip.Deflater.
zstd: алгоритм сжатия Facebook, который предположительно быстрее и имеет лучшую степень сжатия, чем deflate.
snappy: алгоритм сжатия Google, который был разработан таким образом, чтобы быть очень быстрым при разумных коэффициентах сжатия. Через snappy-java.
brotli: еще один алгоритм сжатия от Google, который нацелен на лучшую степень сжатия и сопоставимую производительность с deflate. Для brotli мы будем использовать 3 уровня сжатия: 0, 6 и 11 (по умолчанию, максимальный). Используя Brotli4j.
lz4: алгоритм сжатия, который направлен на достижение наилучшей производительности декодирования. Для lz4 мы будем использовать 3 уровня сжатия: быстрый, 9 (по умолчанию), 17 (максимальный). Через lz4-java.

Степени сжатия

Для реального набора данных лучшую степень сжатия предоставляет brotli, худшую snappy и lz4 fast:

Для случайного датасета лучшую степень сжатия предоставляет brotli, а худшую, неизменно, lz4 fast.

Электронная таблица со всеми коэффициентами сжатия доступна здесь.

Тесты производительности

Тесты были выполнены с использованием JMH для 3 JDK: openjdk-8, openjdk-11 и openjdk-17.

Декодирование реальных данных

Во-первых, давайте посмотрим на производительность декодирования для реальных данных (длина данных составляет от 600 КБ до 4 МБ):

Другим представлением для этой диаграммы была бы пропускная способность в байтах в секунду:

Из этих графиков видно, что lz4 (все 3 уровня) значительно превосходит все остальные алгоритмы. Следующими после lz4 fast являются zstd и snappy.

Кодирование реальных данных

Далее давайте проверим производительность кодирования для реальных данных (длина данных составляет от 600 КБ до 4 МБ):

Ух ты! Brotli с 11-м уровнем потребовалось 13 секунд, чтобы закодировать 4 МБ данных… Сначала я не поверил в это, подумал, что, должно быть, неправильно пользуюсь библиотекой. Но потом я запустил оригинальный родной двоичный файл:

$ time brotli ~/1/bins/total_4072805_with_34010_items.bin

real 0m12.945s
user 0m12.878s
sys 0m0.064s

Действительно, 11 уровень сжатия чрезвычайно медленный. Давайте исключим его, чтобы увидеть нормальную работу других алгоритмов:

И соответствующий график пропускной способности (байты в секунду):

Здесь 4 лидера: lz4 fast (500+Мбит/с), brotli_0 (450+Мбит/с), snappy (400+Мбит/с) и zstd (250+Мбит/с). Худший – lz4_high17 с 13-30 Мбит /с.

Сравнение производительности в разных JDK

Сравнивая производительность в разных JDK, мы можем увидеть, что производительность более или менее одинакова, поскольку большинство библиотек используют JNI под капотом:

То же самое и для кодирования:

Сравнение тестов случайного датасета

Несмотря на то, что коэффициенты сжатия в реальном наборе данных разные, в основном они равны 2 и выше, плюс не все данные случайны. Также интересно проверить, как алгоритмы ведут себя при более разных степенях сжатия и большем количестве случайных данных. Итак, давайте проверим производительность рандомных данных при различных степенях сжатия.

lz4 fast vs snappy

Глядя на графики пропускной способности, кажется, что lz4 fast compressor – очень достойная альтернатива snappy, когда степень сжатия не очень важна. Декодирование происходит быстрее:

А теперь кодирование:

Однако, этот тест не учитывает ограничение ввода-вывода системы: пропускная способность сети / диска не бесконечна, поэтому сжатие не будет работать с максимальной производительностью. Я попытался эмулировать ограничение ввода-вывода, но, похоже, у меня это плохо получилось. Поэтому я собираюсь скоро запустить еще один тест…

gzip vs deflate

Gzip и deflate имеют разницу в размерах в 12 байт. Кроме того, gzip использует deflate для сжатия данных. Но между ними есть разница в производительности!

Это очень странно, потому что под капотом как deflate, так и gzip используют классы Inflater/ Deflater из JDK.

deflate vs MySQL Compress

Размер разницы (дополнительные 4 байта) позволяет точно распределять буфер при декодировании, что может сэкономить несколько выделений и копирование памяти. И это то, что мы действительно видим на графике:

Здесь оптимизация действительно очень помогает.

brotli vs gzip

Предполагается, что Brotli является более эффективной заменой deflate / gzip. С точки зрения производительности, Brotli с уровнем сжатия 6, как правило, быстрее, чем gzip / deflate. После определённого размера (в этом тесте где-то между 20K и 30K) Brotli работает значительно лучше:

То же самое касается и кодирования, но там порог еще меньше (около 3K-4K):

Другие интересные детали

Brotli

Существует 3 библиотеки для Java:

org.brotli:dec: старая библиотека от Google, последнее обновление было в 2017 году.
com.nixxcode.jvmbrotli:jvmbrotli: тоже старая, обновлена в 2019 году.
com.aayushatharva.brotli4j:brotli4j: та, которую я использовал при сравнении.

Библиотека dec допускает только декомпрессию. Я решил провести сравнительный анализ, и результаты очень печальные:

Action   (algorithm) (ratio) (length)      Score  Units
decode      brotli_6  medium   102400    813.029  us/op
decode           dec  medium   102400   2220.280  us/op
decode     jvmbrotli  medium   102400   2644.517  us/op

lz4

lz4 поддерживается в Commons Compress. Краткий тест показал, что он более чем на 1 порядок медленнее, чем org.lz4:lz4-java.

Action  (algorithm)  (length)    Score  Units
decode    lz4_block     62830  726.496  us/op
decode   lz4_framed     62830  891.120  us/op
decode     lz4_fast     62830   30.119  us/op
decode   lz4_high17     62830   22.561  us/op
decode    lz4_high9     62830   22.075  us/op

Заключение

Несмотря на то, что результаты теста выглядят многообещающими, я не до конца уверен, что увижу такой же уровень производительности в реальном приложении: я кратко упомянул, что ограничение ввода-вывода сети / диска тяжело эмулировать, поэтому трудно предсказать, как оно будет себя вести.

В любом случае,

lz4 выглядит действительно многообещающе. Я с нетерпением жду возможности сделать с его помощью более полный тест производительности!
Brotli удивил тем, что по умолчанию он использует максимальное сжатие, которое происходит чрезвычайно медленно. Ещё больше меня удивило то, что скорость декодирования сильно сжатых данных ниже, что делает средний уровень сжатия гораздо лучшим выбором.
Zstd находится где-то посередине с точки зрения производительности и степени сжатия.

Поиграйте с графиками здесь. Исходный код находится на GitHub.

https://t.me/javatg – изучение java в нашем телеграм канале.