Високоскоростна безотказна компресия (продължение)

Тази статия е вече втората по темата за високоскоростното компресиране на данни. Първата статия описва компресор, работещ със скорост 10 GB/sec. на процесорно ядро ​​(минимална компресия, RTT-Min).

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

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

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

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

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

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

Съвременните компресори могат да произвеждат такива скорости само в "бърз" режим. Именно в този настоящ режим ще сравним алгоритъма RTT-Mid с традиционните компресори.

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

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

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

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

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

Дъмп файлът беше компресиран с помощта на компресори PTT-Mid, 7-zip и WinRar. WinRar и 7-zip компресорът бяха настроени на максимална скорост.

Компресорът работи 7-цип:

Натоварва процесора със 100%, докато средната скорост на четене на оригиналния дъмп е около 60 мегабайта/сек.

Компресорът работи WinRAR:

Ситуацията е подобна, натоварването на процесора е почти 100%, средната скорост на четене на дъмпа е около 125 мегабайта/сек.

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

Програмата за тестване на компресора вече работи RTT-Ср:

На скрийншота се вижда, че процесорът е натоварен на 50% и през останалото време не работи, защото няма къде да се качат компресираните данни. Дискът за качване на данни (Диск 0) е почти напълно зареден. Скоростта на четене на данни (диск 1) варира значително, но средно над 200 мегабайта/сек.

Скоростта на компресора е ограничена в този случай от възможността за записване на компресирани данни на диск 0.

Сега съотношението на компресия на получените архиви:

Може да се види, че компресорът RTT-Mid се справи най-добре с компресията; архивът, който създаде, беше с 1,3 гигабайта по-малък от архива на WinRar и с 2,1 гигабайта по-малък от архива 7z.

Време, прекарано в създаването на архива:

• 7-цип – 26 минути 10 секунди;
• WinRar – 17 минути 40 секунди;
• RTT-среда – 7 минути 30 секунди.

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

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

Но само на процесори с поддръжка на AVX-2, без поддръжка на тези инструкции компресорът не работи и не тествайте алгоритъма на по-стари AMD процесори, те са бавни по отношение на изпълнението на AVX инструкции...

Използван метод на компресия

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

PTT компресорът използва уникален високоскоростен скенер за търсене на съвпадения, който ни позволява да ускорим процеса на компресия. Самоделен скенер, това е „моят чар...“, „доста е скъп, защото е изцяло ръчно изработен“ (написано на асемблер).

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

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

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

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

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

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

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

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

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

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

Влияе значително върху скоростта на компресора и работата на системата за вход/изход на данни. Заявките към OP от I/O блокират заявките за данни от CPU, което също намалява скоростта на компресия. Този проблем е важен за лаптопи и настолни компютри; за сървъри е по-малко важен поради по-усъвършенстваното устройство за контрол на достъпа до системната шина и многоканалната RAM.

В целия текст в статията говорим за компресия; декомпресията остава извън обхвата на тази статия, тъй като „всичко е покрито с шоколад“. Декомпресията е много по-бърза и е ограничена от I/O скоростта. Едно физическо ядро ​​в една нишка лесно осигурява скорости на разопаковане от 3-4 GB/sec.

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

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

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

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

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

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

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

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

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

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

Невъзможно е да се възстанови информация от такъв „счупен“ архив.

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

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

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

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

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

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

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

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

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

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