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

Тази статия е втората по темата за бързото компресиране на данни. В първата статия беше описан компресор, работещ със скорост 10ГБ/сек. на едно процесорно ядро (минимално компресиране, RTT-Min).

Този компресор вече е внедрен в оборудването на криминалистичните дубликатори за бързо компресиране на дъмпове на информационни носители и засилване на устойчивостта на криптографията. Освен това може да се използва за компресиране на образи на виртуални машини и своп файлове на оперативната памет при запазването им на бързи SSD носители.

В първата статия също беше анонсирано разработването на алгоритъм за компресия за компресиране на резервни копия от HDD и SSD дискови носители (средно компресиране, RTT-Mid) с значителни подобрения в параметрите на компресията на данни. Към настоящия момент този компресор е напълно готов и статията е именно за него.

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

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

От друга страна, същият терабайт може да бъде копиран със скорости около 2-3 Гигабайта за десет минути.

Следователно, компресирането на информация с голям обем е актуално, ако се извършва със скорост не по-ниска от реалната скорост на вход/изход. За съвременните системи това е не по-малко от 100 Мегабайта в секунда.

Тези скорости съвременните компресори могат да постигат само в режим „бързо“. Ето в този актуален режим ще сравним алгоритма RTT-Mid с традиционните компресори.

Сравнително тестване на новия алгоритъм за компресия.

Компресорът RTT-Mid работеше в рамките на тестова програма. В реално „работно“ приложение работи значително по-бързо, там ефективно се използва многопоточност и се прилага „нормален“ компилатор, а не C#.

Тъй като компресорите, използвани в сравнителния тест, са изградени на различни принципи и различните типове данни се компресират по различен начин, за обективност на теста беше използван методът на измерване „средната температура в болницата“…

Създаден е файл с секторен дъмп на логическия диск с операционната система Windows 10, което представлява най-естествената смес от различни структури от данни, налична на всеки компютър. Компресирането на този файл ще позволи да се проведе сравнение на скоростта и степента на компресия на новия алгоритъм с най-напредналите компресори, използвани в съвременните архиватори.

Ето този файл с дъмп:

Файлът с дъмпа беше компресиран с компресорите RTT-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 е класически пример за движение "назад в бъдещето"…

В компресора RTT се използва уникален бърз скенер за търсене на съвпадения, именно той е позволил да се ускори процеса на компресия. Скенерът е собствено производство, това е "моят хит…", "цената му не е малка, тъй като е изцяло ръчна работа" (написан на асемблер).

Скенерът за търсене на съвпадения е реализиран по двустепенна вероятностна схема, първо се сканира наличието на "признак" за съвпадение и само след откриването на "признака" на това място се стартира процедурата за откриване на реалното съвпадение.

Размерът на прозореца за търсене на съвпадения е непредсказуем и зависи от степента на ентропия в обработвания блок данни. За напълно случайни (несжимаеми) данни той има размер в мегабайти, а за данните с повтаряния винаги има размер над един мегабайт.

Но много съвременни формати данни са несжимаеми и "гоненето" им с ресурсоемък скенер е безполезно и разточително, затова в скенера се използват два режима на работа. Първо, се търсят участъци от оригиналния текст с възможни повтаряния и тази операция също се извършва по вероятностен метод и се изпълнява много бързо (със скорост 4-6 гигабайта/сек). След това участъците с възможни съвпадения се обработват от основния скенер.

Индексното сжатие не е много ефективно, трябва да заместваме повтарящите се фрагменти с индекси, и индексният массив значително намалява коефициента на компресия.

За да се увеличи степента на компресия, се индексират не само пълните съвпадения на байтовите низове, но и частичните, когато в низа има съвпадащи и несъвпадащи байтове. За целта в формата на индекса е включено поле за маска на съвпадения, което указва на съвпадащите байтове на двата блока. За още по-голяма компресиия се използва индексиране с наслагане на няколко частично съвпадащи блока върху текущия блок.

Всичко това позволи да се постигне в компресора RTT-Mid степен на компресия, съизмерима с компресорите, изработени по речников метод, но работещи много по-бързо.

Скоростта на работа на новия алгоритъм за компресия

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

При многопоточна реализация на компресора, ефективната мащабируемост се определя от обема на кеш паметта от трето ниво. Например, при налични 9 Мегабайта кеш памет, няма смисъл да се стартират повече от два потока компресия, тъй като скоростта от това няма да се увеличи. Но при кеш от 20 Мегабайта може да се стартират вече пет потока компресия.

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

Съществено влияние върху скоростта на компресора оказва и работата на системата за вход/изход на данни. Запитванията от ОП към входа/изхода блокират запитванията за данни от ЦП, което също намалява скоростта на компресия. Тази проблема е съществена за лаптопи и десктопи, сървъри но тя е по-малко съществена благодарение на по-напреднал блок за управление на достъпа до системната шина и многоканална оперативна памет.

В текста на статията се обсъждат компресията, докато декомпресията остава извън обсъждането, тъй като там «всичко е наред». Декомпресията протича значително по-бързо и е ограничена от скоростта на входа/изхода. Едно физическо ядро в един поток осигурява скорости на разпаковане от 3-4 гигабайта/секунда.

Това се дължи на липсата на операция за търсене на съвпадения в процеса на разпаковане, която «изяжда» основните ресурси на процесора и кеша при компресия.

Надеждност на съхранението на компресирани данни

Както подсказва името на целия клас софтуерни средства, използващи компресия на данни (архиватори), те са предназначени за дългосрочно съхранение на информация, не в продължение на години, а на векове и хилядолетия...

През времето на съхранение носителите на информация губят част от данните, ето един пример:

Този «аналогов» носител на информация е на хиляда години, някои фрагменти са загубени, но информацията като цяло остава «четима»...

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

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

И това е голям проблем, но не отложен, а текущ.

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

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

Възстановяването на информация от такъв "разрушен" архив е невъзможно.

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

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

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

Недостатъци на алгоритъма

Няма достойнства без недостатъци. Индексният метод за компресия не компресира повтарящи се последователности с малка дължина. Това е свързано с ограниченията на индексния метод. Индексите имат размер не по-малък от 3 байта и могат да бъдат с размер до 12 байта. Ако се среща повторение с по-малък размер от описващия го индекс, то не се отчита, без значение колко често се откриват такива повторения в компресируемия файл.

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

Тези ниски скорости са неприемливи за съвременните системи за съхранение на данни и представляват по-скоро „академичен“ интерес, отколкото практичен.

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

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

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