Скоростная отказоустойчивая компрессия (Продолжение)

Данная статья уже вторая в теме о скоростной компрессии данных. В первой статье был описан компрессор работающий со скоростью 10Гбайт/сек. на одно процессорное ядро (минимальное сжатие, RTT-Min).

Этот компрессор, уже внедрен в оборудование криминалистических дубликаторов для скоростного сжатия дампов носителей информации и усиления стойкости криптографии, также он может применяться для сжатия образов виртуальных машин и своп файлов оперативной памяти при сохранении их на быстродействующих SSD накопителях.

В первой статье также анонсировалась разработка алгоритма компрессии для сжатия резервных копий HDD и SSD дисковых накопителей (среднее сжатие, RTT-Mid) с существенно улучшенными параметрами сжатия данных. К настоящему времени этот компрессор полностью готов и данная статья именно о нем.

Компрессор, реализующий алгоритм RTT-Mid обеспечивает степень сжатия сравнимую со стандартными архиваторами типа WinRar, 7-Zip, работающих в скоростном режиме. При этом скорость его работы как минимум на порядок выше.

Скорость упаковки/распаковки данных является критическим параметром определяющим область применения технологий компрессии. Вряд ли кому придет в голову сжимать терабайт данных со скоростью 10-15 МегаБайт в секунду (именно такая скорость архиваторов в стандартном режиме компрессии), ведь на это придется затратить почти двадцать часов при полной загрузке процессора…

С другой стороны тот же терабайт можно скопировать на скоростях порядка 2-3ГигаБайт в секунду минут за десять.

Поэтому сжатие информации большого обьема актуально если его производить со скоростью не ниже скорости реального ввода/вывода. Для современных систем это не менее 100МегаБайт в секунду.

Такие скорости современные компрессоры могут выдавать только в режиме «fast». Вот в этом актуальном режиме и будем проводить сравнение алгоритма RTT-Mid с традиционными компрессорами.

Сравнительное тестирование нового алгоритма компрессии

Компрессор RTT-Mid работал в составе тестовой программы. В реальном «рабочем» приложении он работает значительно быстрее, там грамотно используется многопоточность и применяется «нормальный» компилятор, а не С#.

Поскольку используемые в сравнительном тесте компрессоры построены на разных принципах и различные типы данных сжимают по разному, то для объективности теста использовался метод замера «средней температуры по больнице»…

Был создан файл посекторного дампа логического диска с операционной системой Windows 10, это наиболее естественная смесь различных структур данных реально имеющаяся на каждом компьютере. Сжатие этого файла позволит провести сравнение по скорости и степени компрессии нового алгоритма с самыми продвинутыми компрессорами используемыми в современных архиваторах.

Вот этот файл дампа:

Файл дампа сжимался компрессорами РТТ-Mid, 7-zip, WinRar. Компрессор WinRar и 7-zip были выставлены на максимальную скорость работы.

Работает компрессор 7-zip:

Он грузит процессор на 100%, при этом средняя скорость чтения исходного дампа около 60 МегаБайт/сек.

Работает компрессор WinRar:

Ситуация аналогичная, загрузка процессора практически 100%, средняя скорость чтения дампа около 125 МегаБайт/сек.

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

Теперь работает тестовая программа компрессора RTT-Mid:

Скриншот показывает, что процессор загружен на 50% и простаивает остальное время, потому как некуда выгружать скомпрессированные данные. Диск выгрузки данных (Диск 0) загружен практически полностью. Скорость чтения данных (Диск 1) сильно скачет, но в среднем более 200 МегаБайт/сек.

Скорость работы компрессора ограничивается в данном случае возможностью записи сжатых данных на Диск 0.

Теперь степень сжатия получившихся архивов:

Видно, что компрессор RTT-Mid лучше всех справился с компрессией, архив созданный им на 1,3 ГигаБайта меньше архива WinRar и на 2,1ГигаБайта меньше архива 7z.

Время затраченное на создание архива:

• 7-zip – 26минут 10 секунд;
• WinRar – 17минут 40 секунд;
• RTT-Mid – 7 минут 30 секунд.

Таким образом, даже тестовая, не оптимизированная программа, используя алгоритм RTT-Mid, смогла более чем в два с половиной раза быстрее создать архив, при этом архив оказался существенно меньшим нежели у конкурентов…

Те, кто не верит скриншотам, могут проверить их достоверность самостоятельно. Тестовая программа доступна по ссылке, скачивайте и проверяйте.

Но только на процессорах с поддержкой AVX-2, без поддержки этих инструкций компрессор не работает, и не тестируйте алгоритм на старых процессорах AMD, они медленные в части выполнения AVX команд…

Используемый метод компрессии

В алгоритме используется метод индексирования повторяющихся фрагментов текста в байтовой грануляции. Такой метод сжатия известен давно, но не использовался, поскольку операция поиска совпадений была очень затратна по необходимым ресурсам и требовала гораздо более времени нежели построение словаря. Так что алгоритм RTT-Mid является классическим примером движения «назад в будущее»…

В компрессоре РТТ используется уникальный скоростной сканер поиска совпадений, именно он позволил ускорить процесс компрессии. Сканер собственного изготовления, это «моя прелесть…», «цены он немалой, потому как полностью ручной работы» (написан на ассемблере).

Сканер поиска совпадений выполнен по двухуровневой вероятностной схеме, сначала сканируется наличие «признака» совпадения, и только после выявления «признака» в этом месте запускается процедура обнаружения реального совпадения.

Окно поиска совпадений имеет непредсказуемый размер, зависящий от степени энтропии в обрабатываемом блоке данных. Для полностью случайных (несжимемых) данных оно имеет размер мегабайт, для данных имеющих повторы всегда имеет размер больше мегабайта.

Но многие современные форматы данных несжимаемы и «гонять» по ним ресурсоемкий сканер бесполезно и расточительно, поэтому в сканере используется два режима работы. Сначала ищутся участки исходного текста с возможными повторами, эта операция проводится тоже вероятностным методом и выполняется очень быстро (на скорости 4-6 ГигаБайт/сек). Затем участки с возможными совпадениями обрабатываются основным сканером.

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

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

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

Скорость работы нового алгоритма компрессии

Если компрессор работает с монопольным использованием кеш памяти (на один поток требуется 4 МегаБайта), то скорость работы колеблется в диапазоне 700-2000 Мегабайт/сек. на одно процессорное ядро в зависимости от типа сжимаемых данных и мало зависит от рабочей частоты процессора.

При многопоточной реализации компрессора эффективная масштабируемость определяется обьемом кеш-памяти третьего уровня. К примеру, имея «на борту» 9 МегаБайт кеш-памяти запускать более двух потоков компрессии нет смысла, скорость расти от этого не будет. Но при кеше в 20 МегаБайт можно уже запускать пять потоков компрессии.

Также существенным параметром определяющим скорость работы компрессора становится латентность оперативной памяти. Алгоритм использует рандомные обращения к ОП, часть из которых не попадает в кеш память (около 10%) и ему приходится простаивать, ожидая данные из ОП, что снижает скорость работы.

Существенно влияет на скорость компрессора и работа системы ввода/вывода данных. Запросы к ОП от ввода/вывода блокируют обращения за данными со стороны ЦП, что также снижает скорость компрессии. Эта проблема существенна для ноутбуков и десктопов, для серверов она менее существенна благодаря более продвинутому блоку управления доступом к системной шине и многоканальной оперативной памяти.

Везде по тексту в статье идет речь об компрессии, декомпрессия остается за рамками этой статьи поскольку там «все в шоколаде». Декомпрессия проводится значительно быстрее, и ограничивается скоростью ввода/вывода. Одно физическое ядро в одном потоке спокойно обеспечивает скорости распаковки на уровне 3-4 Гигабайта/сек.

Это связано с отсутствием в процессе распаковки операции поиска совпадений, которая «сжирает» основные ресурсы процессора и кеш-памяти при компрессии.

Надежность хранения сжатых данных

Как следует из названия всего класса программных средств использующих компрессию данных (архиваторы), они предназначены для длительного хранения информации, не годами, а столетиями и тысячелетиями…

За время хранения носители информации теряют часть данных, вот пример:

Этому «аналоговому» носителю информации тысяча лет, некоторые фрагменты утеряны, но в целом информация «читаема»…

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

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

И это тоже большая проблема, но не отложенная, а текущая.

Современные компрессоры используемые для архивации цифровых данных построены на различных модификациях словарного метода и для таких архивов утеря фрагмента информации будет фатальным событием, существует даже устоявшийся термин для такой ситуации — «битый» архив…

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

Восстановить информацию из такого «битого» архива невозможно.

Алгоритм RTT построен на основе более надежного метода хранения сжатых данных. В нем применяется индексный метод учета повторяющихся фрагментов. Такой подход к компрессии позволяет минимизировать последствия искажения информации на носителе, и во многих случаях автоматически корректировать искажения возникшие при хранении информации.
Это связано с тем, что архивный файл в случае индексного сжатия содержит два поля:

• поле исходного текста с удаленными из него участками повтора;
• поле индексов.

Критически важное для восстановления информации поле индексов, не велико по размеру и его можно дублировать для надежности хранения данных. Поэтому даже если будет утерян фрагмент исходного текста или индексного массива, то вся остальная информация будет восстанавливаться без проблем, как на картинке с «аналоговым» носителем информации.

Недостатки алгоритма

Достоинств не бывает без недостатков. Индексный метод компрессии не сжимает повторяющиеся последовательности малой длины. Это связано с ограничениями индексного метода. Индексы имеют размер не менее 3 байт и могут быть размером до 12байт. Если встречается повтор с меньшим размером чем описывающий его индекс, то он не учитывается, как бы часто такие повторы не выявлялись в сжимаемом файле.

Традиционный, словарный метод компрессии, эффективно сжимает множественные повторы малой длины и поэтому достигает большего коэффициента сжатия нежели индексная компрессия. Правда это достигается за счет высокой загруженности центрального процессора, чтобы словарный метод начал сжимать данные эффективнее индексного метода ему приходится снижать скорость обработки данных до 10-20 мегабайт в секунду на реальных вычислительных установках при полной загрузке ЦП.

Такие низкие скорости неприемлемы для современных систем хранения данных и представляют больше «академический» интерес, нежели практический.

Степень сжатия информации будет существенно повышена в следующей модификации алгоритма РТТ (RТТ- Max), он уже в разработке.

Так что как всегда, продолжение следует…

Источник: habr.com