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

Тази статия е втората по темата за бързо компресиране на данни. В първата статия беше описан компресор, работещ със скорост 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