Скоростная компрессия

Форсирование скорости ввода/вывода с помощью компрессии

Применение сжатия (компрессии) информации перед записью на носитель данных известный метод повышения производительности операций ввода/вывода. Но, современные форматы хранения данных уже изначально сжаты, повторное сжатие это пустая трата времени.
Поэтому в настоящее время использование компрессоров для сжатия информации целесообразно в системах, где данные поступают на хранение с большой внутренней избыточностью. Типов информации с избыточностью сейчас не так много, но такая информация имеет большую значимость и занимает существенный обьем хранилищ данных на вычислительных ресурсах, это:
— своп файлы операционных систем;
— образы памяти виртуальных машин;
— секторные дампы дисков;
— дампы файловых систем.

Такие объекты хорошо сжимаемы (в два-три раза), поэтому теоретически можно увеличить скорость операций ввода/вывода этих информационных обьектов.
Конкретный пример:
Нужно сохранить образ виртуальной машины размером 4 гигабайта с внутренней избыточностью 50% на диск работающий со скоростью 1 ГБайт/сек.
Если не применять компрессию, то на это потратится 4 секунды.
Если применить компрессию, то можно сжать информацию до двух гигабайт и записать этот образ за 2 секунды, т.е. ровно в два раза ускорить процедуры сохранения и соответственно развертывания виртуальной машины.
Однако сейчас компрессия с целью увеличения скорости работ конечных систем применяется только в «облачных хранилищах», и то, с большими ограничениями. Причина банальна — нет технологий сжатия информации, превышающих скорость работы современных HDD и SSD дисков.
До настоящего времени было быстрее записать/прочитать данные на скоростной диск без компрессии, чем тратить процессорное время на процедуру сжатия/разжатия.
Если говорить конкретно, то для файлов образов оперативной памяти нужно обеспечить скорость компрессии, превышающую скорость работы современных SSD дисков, а это 2-3 ГБайт/сек. Известные методы компрессии на таких скоростях не работают, либо требуют специальных аппаратных сопроцессоров.
Для дампов дисковых пространств требуется обеспечить скорость сжатия, превышающую скорость работы дисковых хранилищ, там скорости имеют разброс от 100 МБайт/сек. до 1 ГБайт/сек.
Существующие компрессоры могут обеспечить такую скорость, но при этом полностью загрузят работой процессор, система будет часами работать исключительно над созданием дампа. Вряд ли это приемлемо, так что для дампов дисков нужно тоже обеспечивать скорости сжатия недостижимые на современном оборудовании и известных алгоритмах компрессии.
И так, задача скоростной компрессии актуальна и значима, но до настоящего времени не имела решения.
Поэтому был сконструирован новый алгоритм компрессии максимально быстро реализуемый в аппаратуре и системе команд современных процессоров х86/64.
Для краткости мы его называем алгоритм РТТ.

Алгоритм РТТ

В алгоритме РТТ применяются только последовательные операции чтения и записи, а все преобразования выполняются исключительно на регистрах процессора.
Алгоритм основан на операциях сдвига, он уступает по эффективности сжатия известным методам, но обеспечивает именно те скорости, которые требуются — около 10 Гигабайт в секунду для одного процессорного ядра, функционирующего на частоте 4 ГГерца и, что немаловажно, не «сжирает» память.
Такие параметры получены на стенде, в идеальных условиях работы. В реальном программном и аппаратном окружении скорость работы алгоритма РТТ будет конечно меньше, но не намного, это можно увидеть на конкретном примере реализации алгоритма РТТ в серийном изделии:

На снимке редкий «зверь» — криминалистический дубликатор. Это устройство позволяет параллельно считывать информацию с восьми дисков/флешек/карт памяти на внутренний SSD накопитель.
Сжатие информации в этом устройстве применяется для увеличения скорости операций копирования. Устройство может обеспечивать суммарную пропускную способность до 1600 мегабайт/сек. по 8 каналам чтения, это ограничение аппаратное, больше не могут пропустить используемые USB хабы.
Чтобы не быть голословным, продемонстрирую эффективность компрессии по алгоритму РТТ реализованную в криминалистическом дубликаторе.
Для сравнения возьмем коммерческую систему создания резервных копий фирмы «Acronis» — «мирового лидера систем резервного копирования» (так они себя рекламируют) с включенным режимом сжатия.
Используем обе системы по прямому назначению, создадим дамп диска. Для этого возьмем SSD диск с системным разделом:

В системном разделе занято 17,9 ГБ из общего обьема 48,3 ГБ.
Создаем дамп этого диска «Acronis`ом» с максимальной степенью компрессии, и видим следующую картину:

Процессор загружен компрессией на 99%, система практически неработоспособна, даже мышь начинает тормозить.
А вот что может компрессор РТТ:

Работа системы дампирования с компрессором РТТ проходит фактически в фоновом режиме, загрузка процессора не превышает 16%.
Комментарии излишни, но может «Acronis» качественнее работает?
Посмотрим размеры получившихся дампов:

Компрессор РТТ сжал дамп в три раза лучше, чем это смог сделать «Acronis».
Опять без комментариев, пожалеем коммерсантов….

В результате

Время создания дампа с компрессией РТТ составило 2.26 минут при загрузке процессора не более 16%.
«Acronis» работал 9.35 минут при 100% загрузке процессора и создал дамп в три раза большего размера по сравнению с дампом РТТ.
Если бы мы сжимали данный дамп коммерческим компрессором, типа WinZip либо ему подобному, то получили бы дамп размером около 7 гигабайт, но потратили бы на это более часа, при этом загрузка процессора была бы 100%.
Поэтому велик соблазн достичь параметров сжатия, превосходящих лучшие методы компрессии, но при этом работать быстрее, ну так, раз в 100 (чего уж там скромничать).
Задача сложная, но уже практически реализованная.
Сейчас в процессе тестирования новый компрессор, который будет работать на скоростях около 500 Мегабайт/сек для одного процессорного ядра и обеспечивать качество компрессии на уровне лучших известных алгоритмов компрессии.
Но об этом в следующей статье.
Так что, как всегда, продолжение следует…