Хранение 1 ГБ данных в облаке стоит от 2 до 12 рублей. Можно ждать, пока диски подешевеют, а можно сжать данные и получить «бесплатный» апгрейд хранилища. Но если вы храните данные в облаке, сжимать все подряд — как пытаться загрузить стиральную машинку не глядя: льняные брюки могут сесть в 5 раз и освободить место, но если кинуть в барабан кирпич, меньше он не станет, зато вы получите грохот, счет за электричество, недовольных соседей и возможно — сломанную машинку.
Чтобы не потратить кучу CPU с сомнительным результатом, мы у себя в команде R&D Cloud.ru решили исследовать, как сделать сжатие оптимальным, чтобы не тратить время на упаковку того, что сжатию не поддается и эффективно расходовать вычислительные ресурсы.
Я Александр Аксенов, мой профиль — оптимизация хранения данных и мне есть что вам рассказать про то, как ускорить процесс сжатия до 80 раз, сэкономить CPU и сохранить качество. Звучит как кликбейт (так оно и есть ?), но почему это технически правда и может пригодиться вы узнаете из статьи. Надеюсь, мои выводы окажутся полезными всем, кто работает с данными, в особенности инженерам СХД, DevOps, разработчикам распределенных систем и архитекторам облачных решений.
Почему сжимать все подряд — плохая идея
Экономия места при сжатии достигается за счет удаления части информации. Компрессия бывает:
С потерями — когда невозможно восстановить исходные данные. Обычно такая компрессия применяется для изображений, видео, музыки. В этом случае сжатие происходит за счет удаления части данных, возможного ухудшения качества изображения/видео/музыки, но достигается уменьшение размера.
Без потерь — когда из сжатых данных можно полностью восстановить исходные в процессе декомпрессии. При сжатии без потерь, алгоритм компрессии ищет повторяющиеся паттерны в данных и перекодирует их. В общем случае используется именно такое сжатие.
Сжатие без потерь основано на поиске избыточности информации в данных и их перекодировании, чтобы эту избыточность устранить. Это работает, потому что большинство настоящих данных, таких как, например, текст, избыточны. Если данные абсолютно случайны, то сжать их не получится.
Качество результатов работы алгоритма компрессии характеризуется коэффициентом сжатия (ratio):
Вообще, с компрессией без потерь сталкиваются практически все: для этого совсем не обязательно заниматься облачными технологиями, думаю с rar- и zip-архивами все встречались. Но, в отличие от того, как работают популярные архиваторы, сжатие в распределенном блочном хранилище имеет свои принципиальные отличия и особенности. В случае с архивными файлами вопросом хранения занимается файловая система, она позволяет экономить место после сжатия, «знает» где находятся границы сжимаемых файлов и их тип. Это помогает заранее предсказать уровень компрессии данных и саму возможность их сжатия.
В случае с блочным хранилищем данные вполне могут представлять из себя просто бинарный поток без определенных границ, что делает бессмысленным использование такой информации для разных форматов. К подобным данным мы попробовали применить различные способы анализа, которые отвечают на вопрос стоит ли пытаться сжать блок данных.
У каждой предсказательной аналитики есть две важные характеристики:
точность — предсказание, которое не сбывается, бессмысленно: проще сжимать все данные;
скорость работы: суммарная экономия времени с фильтрацией несжимаемых блоков достигается за счет того, что мы не тратим время на сжатие блоков, которые сжать нельзя.
Однако для части блоков, которая сжимается, время с использованием такого анализа возрастает — ведь сначала мы тратим время на то, чтобы понять стоит ли сжимать этот блок, а потом сжимаем его за то же время, как если бы мы сжимали все блоки. Получается, что экономия времени зависит от процента несжимаемых блоков данных в выборке. Причем, чем быстрее работает аналитика, тем меньше нужно несжимаемых блоков, чтобы начать получать выигрыш во времени.
Очевидный способ понять, хорошо ли сжимаются данные — сжать и сравнить полученный размер с исходным. Но такой подход не оптимален: на блоки данных, которые не сжимаются, мы потратим те же вычислительные ресурсы, сэкономим разве что на операциях чтения/записи диска, не записывая результат компрессии. Быстрее может быть взять часть блока и попробовать ее сжать.
Здесь и далее для тестирования мы использовали библиотеку zstd с уровнем сжатия 3 (уровень сжатия по умолчанию). Наше блочное хранилище оперирует блоками данных по 4 Кб, и, поскольку мы рассматриваем сжатие для него, то результаты сжатия округляли вверх до 4 Кб. Данные сжимались блоками по 16 Кб, поэтому в результате мы могли получить такие исходы работы компрессии:
сжатые данные размером 4, 8 или 12 Кб — это отличные результаты, компрессия экономит занимаемое место, такие блоки считаем сжимаемыми;
сжатые данные размером 16 Кб или более — это значит, что такие блоки сжать нельзя, такие блоки считаем несжимаемыми.
В качестве экспериментальных данных — SilesiaCorpus (dickens, mozilla, mr, nci, ooffice, osdb, reymont, samba, sao, webster, xml, x-ray), несколько вариантов синтетических данных:
Zeroes — блок данных, состоящий только из нулей. Должен сжиматься очень хорошо.
Repeated patterns — блок данных, состоящий из повторяющихся паттернов 0 и 1. Тоже отличный кандидат для сжатия.
Mixed 50% rand — блок данных, состоящий из смеси нулей и случайных данных в пропорции 1 к 1.
Random — случайные данные.
И разбавили это данными, которые выполняли роль реальных:
Linux files — данные из системных папок Linux
Encrypt — зашифрованные данные
Compressed — предварительно сжатые данные
Прежде чем анализировать результаты предсказаний мы оценили саму возможность сжатия тестовых данных — сколько блоков из них может быть сжато, а сколько не может быть.
Видно, что в основном наборы данных жмутся хорошо, кроме sao (база данных), случайных, зашифрованных и уже сжатых данных. Не очень хорошо жмется набор x-ray — медицинские данные, результаты рентгена.
Эвристики vs. энтропия: битва методов
Какие данные жмутся хорошо, а какие нет, мы выяснили, но какой способ оптимален? В конце концов, не всегда понятно, не потратим ли мы слишком много ресурсов CPU и времени, чтобы в итоге выиграть в объеме. Чтобы найти баланс между точностью и скоростью, мы решили протестировать 3 метода.
Сжатие части данных
Цель эксперимента была посмотреть сколько времени мы сможем сэкономить предсказывая сжимаемость блока с помощью сжатия части этого блока — часть блока данных сжимается быстрее целого блока и на основании сэкономили мы место благодаря сжатию части или нет, мы делаем вывод о том, стоит ли тратить ресурсы на сжатие всего блока.
Мы попробовали использовать 10% каждого блока данных для частичного сжатия тестовых данные и сэмплов из SileciaCorpus и вот что получилось:
точность предсказания не ниже 80% для всех данных, кроме osdb
основные ошибки — ложноотрицательные предсказания. То есть мы не сожмем часть блоков, эффективность компрессии с таким предсказанием будет меньше
средняя точность среди всех наборов данных — 91%
В среднем время сжатия части блока данных занимало 16 us, а сжатие блока целиком — 80 us. Получается, что 20% данных должны быть несжимаемыми, чтобы наступала экономия времени при использовании этого метода. Увеличить точность метода можно увеличив размер сжимаемой части блока данных, но это приведет к еще большему увеличению времени работы аналитики. Попробуем поискать способ быстрее и точнее.
Экономия места в результате сжатия без потерь достигается за счет устранения избыточности в исходных данных. А что если нам подсчитать эту избыточность с помощью энтропии?
Энтропия
Информацио́нная энтропи́я — мера неопределенности некоторой системы. Энтропия дискретного источника равна среднему количеству информации, приходящейся на один символ источника. Характеризует непредсказуемость появления какого-либо символа алфавита. Другими словами, это объем информации, необходимый для представления случайной величины. Под таким углом немного легче увидеть, как энтропию можно рассматривать как меру неопределенности.
Обычный пример случайной величины — результат подбрасывания монеты. Если эксперимент проходит честно, то у нас есть два равновероятных события: выпадение орла или решки. Для описания такой случайной величины на нужен 1 бит информации (например, 1 — орел, 0 — решка), и этот объем невозможно сократить, ведь результат эксперимента неизвестен заранее. Другое дело, если мы будем подбрасывать нечестную монету нечестно, так, что всегда будет выпадать, например, орел. Для такой «случайной» величины нам нужно будет 0 бит информации — сколько ни бросай монету, исход известен заранее.
В 1948 году Клод Шеннон опубликовал статью «Математическая теория связи», в которой предложил формулу, по которой возможно подсчитать минимально необходимый объем данных для передачи информации с учетом частоты встречающихся символов и назвал это «энтропией». Формула достаточно лаконична:
Она означает, что энтропия данных, это сумма вероятности символа данных, умноженная на логарифм по основанию размерности алфавита от этой вероятности.
Какое все это имеет отношение к нашим предсказаниям сжимаемости блоков? Достаточно прямое — если энтропия близка к максимальной, то избыточность данных мала и сжать их не получится. В нашем случае, поскольку данные — бинарные, у алфавита всего две «буквы», 0 и 1, поэтому логарифм будет двоичный. При побайтовом подсчете энтропии данных, результат будет лежать в диапазоне 0;8, и чем ближе значение к 8, тем хуже данные подвержены сжатию.
Мы используем предсказательные аналитики для принятия решения «сжимать/не сжимать», поэтому для энтропии нам нужно выбрать какое-то пороговое значение, при энтропии ниже которого будем пытаться сжать данные, при энтропии выше или равной которому — нет. В исследованиях энтропия нередко используется для подобных предсказаний, и обычно там используют границу в 7.9-7.6 бит (98-95%). Мы взяли за граничное значение 7.6 бит на байт.
Преимущество энтропии как предсказания — в основном ложноположительные, а не ложноотрицательные ошибки. В этом случае мы не пропускаем данные, которые можем сжать. Но разброс в точности у энтропии оказался больше, чем у частичного сжатия, хотя в среднем 90% точности, в случаях, когда аналитика работала, точность не падала ниже 90%, зато два кейса оказались энтропии не под силу: база данных sao и рентгеновские данные. Скорость работы немного выросла по сравнению с частичным сжатием — 15 us на блок в среднем.
Быстрые эвристики (еще лучше энтропии!)
В целом, энтропия выглядит приемлемым рабочим вариантом, но подсчет энтропии достаточно затратен в плане вычислительных ресурсов, да и не всегда необходим: если данные состоят из одинаковых байт, повторяют сами себя, большая часть данных покрывается небольшим количеством значений байт, то такой блок тоже хороший кандидат на сжатие, и это можно понять без подсчетов энтропии. Есть целый набор подобных эвристик, которые помогают «дешево» принять решение стоит сжимать данные или нет. Подобный подход используется, например, в btrfs в коде ядра Linux. Вот эвристики, которые там используются:
повторяющиеся паттерны. Если первая половина данных идентична со второй - данные стоит сжать.
вариативность значений байт в данных. Если количество разных значений байт в данных не превышает 64, то скорее всего это - текст, и он будет сжиматься
вариативность значений байт в 90% данных. Если 90% от данных состоит не более чем из 64 значений байт (25% всех значений), то данные скорее всего сожмутся хорошо, а если более чем из 200 значений байт (>78% возможных значений), то такие данные, весьма вероятно, сжать не удастся
наконец, если предыдущие эвристики не помогли, то можно вернуться к старой-доброй энтропии.
Поскольку btrfs – файловая система, там эти эвристики применяются к, внезапно, файлам. То есть зачастую однородным, четко ограниченным частям данных. В случае же блочного хранилища данные могут быть перемешаны и разнородные данные попадут в один блок компрессии. Однако, на практике это никак не мешает эвристикам работать с достаточно высокой точностью:
Эвристики представляют из себя по сути дополнительные быстрые и простые проверки перед энтропией, они не улучшают и не ухудшают качества работы по сравнению с энтропией: есть провалы для отдельных типов данных (sao, x-ray), в среднем точность в районе 90%.
Но зато за счет этих быстрых проверок, сильно растет среднее время работы — оно составило всего 1 us (времясжатия блока — 80 us), получается всего не менее 1.25% данных должны быть несжимаемыми чтобы эвристики начинали экономить время. Вот здесь внимательный читатель и поймет, к чему я вел, когда говорил в начале про кликбейт: процесс действительно может ускориться в 80 раз, но это справедливо только для данных, которые не сжимаются — мы быстро понимаем, что их не надо даже пытаться упаковать и не жмем, но это «понимание» у нас наступает в 80 раз быстрее, чем если бы мы начали сжимать не разобравшись.
В результате всех экспериментов у нас получилась такая вот картина:
Результаты поединка
Итак, исследовав всех наших кандидатов на фильтрацию несжимаемых блоков данных, похоже у нас есть победитель — это быстрые эвристики. Все подходы хорошо справились по качеству, но эвристики заметно вырвались вперед по времени работы — неплохой кандидат для дальнейшего улучшения качества и внедрения. Ключ к успеху оказался в простоте и скорости работы аналитики.
Конечно, после исследования на тестовых данных, мы перепроверили выводы на реальных, там эвристики показали себя не хуже. Так что, если вдруг вы хотите сжимать данные в блочном хранилище и раздумываете как бы сделать это эффективнее, не сжимая все подряд — могу рекомендовать вам присмотреться к эвристикам, в ходе наших исследований метод показал свою эффективность. Кстати, по Free Tier в нашем Evolution Object Storage можно хранить до 15 Гб данных бесплатно, а раз вы теперь вы знаете как их упаковывать, можно безнаказанно втиснуться в этот лимит и радоваться.
Мораль истории такова: чтобы эффективно сжимать данные, достаточно просто... сначала подумать. Революционно, да? ? А если серьезно, расскажите, какие методы вы пробовали на практике? Какие эвристики оказались самыми эффективными в ваших кейсах? Или может быть вы пошли каким-то совершенно иным путем — было бы любопытно почитать.