Безбедна компресија со голема брзина (продолжува)

Оваа статија е веќе втора во темата за компресија на податоци со голема брзина. Првиот напис опиша компресор кој работи со брзина од 10 GB/s. по јадро на процесорот (минимална компресија, RTT-Min).

Овој компресор веќе е имплементиран во опремата на форензички дупликатори за компресија со голема брзина на депонии од медиум за складирање и за подобрување на јачината на криптографијата; може да се користи и за компресија на слики од виртуелни машини и датотеки за размена на RAM меморија кога се зачувуваат на голема брзина SSD дискови.

Првата статија, исто така, најави развој на алгоритам за компресија за компресирање на резервни копии на HDD и SSD диск драјвови (средна компресија, RTT-Mid) со значително подобрени параметри за компресија на податоци. Досега, овој компресор е целосно подготвен и оваа статија е за тоа.

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

Брзината на пакување/отпакување на податоците е критичен параметар кој го одредува опсегот на примена на технологиите за компресија. Малку е веројатно дека некој би помислил да компресира терабајт податоци со брзина од 10-15 мегабајти во секунда (точно тоа е брзината на архивите во стандардниот режим на компресија), бидејќи би биле потребни речиси дваесет часа со целосно оптоварување на процесорот. .

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

Затоа, компресирањето на информациите со голем волумен е важно ако се врши со брзина не помала од брзината на реалниот влез/излез. За модерни системи ова е најмалку 100 мегабајти во секунда.

Современите компресори можат да произведуваат такви брзини само во „брз“ режим. Токму во овој сегашен режим ќе го споредиме алгоритмот RTT-Mid со традиционалните компресори.

Компаративно тестирање на нов алгоритам за компресија

Компресорот RTT-Mid работеше како дел од програмата за тестирање. Во вистинска „работна“ апликација работи многу побрзо, паметно користи мултинишки и користи „нормален“ компајлер, а не C#.

Бидејќи компресорите што се користат во компаративниот тест се изградени на различни принципи и различни типови податоци различно се компресираат, заради објективноста на тестот, користен е методот на мерење на „просечната температура во болницата“ ...

Создадена е депонија од сектор по сектор на логички диск со оперативниот систем Виндоус 10; ова е најприродната мешавина од различни структури на податоци, всушност достапни на секој компјутер. Компресирањето на оваа датотека ќе ви овозможи да ја споредите брзината и степенот на компресија на новиот алгоритам со најнапредните компресори што се користат во современите архиви.

Еве ја депонија-датотеката:

Датотеката за депонија беше компресирана со помош на компресори PTT-Mid, 7-zip и WinRar. WinRar и 7-zip компресорот беа поставени на максимална брзина.

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

Го вчитува процесорот за 100%, додека просечната брзина на читање на оригиналниот депонија е околу 60 мегабајти/сек.

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

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

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

Сега работи програмата за тестирање на компресорот RTT-Средна:

Сликата од екранот покажува дека процесорот е вчитан на 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 е класичен пример за движење „назад во иднината“...

PTT компресорот користи уникатен скенер за пребарување на натпревари со голема брзина, кој ни овозможува да го забрзаме процесот на компресија. Самопроизведен скенер, ова е „мојот шарм...“, „прилично е скап, бидејќи е целосно рачно изработен“ (напишан во асемблерот).

Скенерот за пребарување на натпревари е направен според веројатноста за двостепена шема: прво, се скенира присуството на „знак“ на натпревар, а само откако ќе се идентификува „знакот“ на ова место, постапката за откривање на вистинско совпаѓање. е започната.

Прозорецот за пребарување на совпаѓања има непредвидлива големина, во зависност од степенот на ентропија во обработениот блок на податоци. За сосема случајни (некомпресибилни) податоци има големина од мегабајти, за податоци со повторувања секогаш е поголема од мегабајт.

Но, многу современи формати на податоци се некомпресибилни и водење на скенер со интензивни ресурси преку нив е бескорисен и непотребен, така што скенерот користи два режима на работа. Прво, се пребаруваат делови од изворниот текст со можни повторувања; оваа операција исто така се изведува со веројатен метод и се изведува многу брзо (со брзина од 4-6 гигабајти/сек). Областите со можни совпаѓања потоа се обработуваат од главниот скенер.

Компресијата на индексот не е многу ефикасна, мора да ги замените дупликатите фрагменти со индекси, а низата индекси значително го намалува односот на компресија.

За да се зголеми односот на компресија, не се индексираат само целосни совпаѓања на низи од бајти, туку и делумни, кога низата содржи совпаднати и неспоредливи бајти. За да го направите ова, форматот на индекс вклучува поле за маска за совпаѓање што ги означува соодветните бајти на два блока. За уште поголема компресија, индексирањето се користи за да се наметнат неколку делумно соодветни блокови на тековниот блок.

Сето ова овозможи во компресорот PTT-Mid да се добие сооднос на компресија споредлив со компресорите направени со методот на речникот, но работат многу побрзо.

Брзина на новиот алгоритам за компресија

Ако компресорот работи со ексклузивна употреба на кеш меморија (потребни се 4 мегабајти по нишка), тогаш работната брзина се движи од 700-2000 мегабајти/сек. по јадро на процесорот, во зависност од типот на податоците што се компресирани и малку зависи од работната фреквенција на процесорот.

Со мулти-нишка имплементација на компресорот, ефективната приспособливост се одредува според големината на кешот од трето ниво. На пример, имајќи „на одборот“ 9 мегабајти кеш меморија, нема смисла да лансирате повеќе од две нишки за компресија; брзината нема да се зголеми од ова. Но, со кеш од 20 мегабајти, веќе можете да извршите пет нишки за компресија.

Исто така, доцнењето на RAM меморијата станува важен параметар кој ја одредува брзината на компресорот. Алгоритмот користи случаен пристап до ОП, од кои некои не влегуваат во кеш меморијата (околу 10%) и мора да работи во мирување, чекајќи податоци од ОП, што ја намалува брзината на работа.

Значително влијае на брзината на компресорот и работата на системот за влез/излез на податоци. Барањата до ОП од В/И блокираат барања за податоци од процесорот, што исто така ја намалува брзината на компресија. Овој проблем е значаен за лаптопите и десктоп компјутерите; за серверите е помалку значаен поради понапредната единица за контрола на пристап до системската автобуска и повеќеканалната RAM меморија.

Во текот на целиот текст во статијата зборуваме за компресија; декомпресија останува надвор од опсегот на овој напис бидејќи „сè е покриено со чоколадо“. Декомпресијата е многу побрза и е ограничена со брзината на В/И. Едно физичко јадро во една нишка лесно обезбедува брзина на распакување од 3-4 GB/s.

Ова се должи на отсуството на операција за пребарување на натпревари за време на процесот на декомпресија, што ги „јаде“ главните ресурси на процесорот и кеш меморијата за време на компресија.

Сигурност на складирање на компресирани податоци

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

За време на складирањето, медиумите за складирање губат некои податоци, еве еден пример:

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

Ниту еден од одговорните производители на модерни системи за складирање на дигитални податоци и дигитални медиуми за нив не дава гаранции за целосна безбедност на податоците повеќе од 75 години.
И ова е проблем, но одложен проблем, нашите потомци ќе го решат...

Системите за складирање на дигитални податоци можат да изгубат податоци не само по 75 години, грешките во податоците може да се појават во секое време, дури и за време на нивното снимање, тие се обидуваат да ги минимизираат овие нарушувања со користење на вишок и нивно коригирање со системи за корекција на грешки. Системите за вишок и корекција не можат секогаш да ги вратат изгубените информации, а ако го сторат тоа, нема гаранција дека операцијата за обновување е правилно завршена.

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

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

Ниската доверливост за складирање на информации во архиви со компресија на речник е поврзана со структурата на компресираните податоци. Информациите во таквата архива не го содржат изворниот текст, таму се чуваат броевите на записите во речникот, а самиот речник динамички се менува од тековниот компримиран текст. Ако некој архивски фрагмент е изгубен или оштетен, сите последователни архивски записи не може да се идентификуваат ниту според содржината ниту според должината на записот во речникот, бидејќи не е јасно на што одговара бројот на записот во речникот.

Невозможно е да се вратат информациите од таква „скршена“ архива.

Алгоритмот RTT се заснова на посигурен метод за складирање на компресирани податоци. Го користи индексниот метод на сметководство за повторување на фрагменти. Овој пристап кон компресија ви овозможува да ги минимизирате последиците од изобличувањето на информациите на медиумот за складирање и во многу случаи автоматски да ги коригирате изобличувањата што се појавија за време на складирањето информации.
Ова се должи на фактот дека архивската датотека во случај на компресија на индекс содржи две полиња:

• поле за изворен текст со повторливи делови отстранети од него;
• поле за индекс.

Индексното поле, кое е критично за враќање на информациите, не е големо и може да се дуплира за сигурно складирање податоци. Затоа, дури и ако се изгуби фрагмент од изворниот текст или индексната низа, сите други информации ќе се обноват без проблеми, како на сликата со „аналоген“ медиум за складирање.

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

Нема предности без недостатоци. Индексниот метод на компресија не ги компресира кратките секвенци што се повторуваат. Ова се должи на ограничувањата на методот на индекс. Индексите се со големина од најмалку 3 бајти и може да бидат со големина до 12 бајти. Ако се сретне повторување со помала големина од индексот што го опишува, тогаш тоа не се зема предвид, без разлика колку често таквите повторувања се откриваат во компресираната датотека.

Традиционалниот метод на компресија во речник ефикасно компресира повеќекратни повторувања со кратка должина и затоа постигнува повисок сооднос на компресија од индексната компресија. Навистина, ова се постигнува поради големото оптоварување на централниот процесор; за да може методот на речник да почне да ги компресира податоците поефикасно од методот на индекс, треба да ја намали брзината на обработка на податоци на 10-20 мегабајти во секунда на реално компјутерски инсталации со целосно оптоварување на процесорот.

Ваквите ниски брзини се неприфатливи за современите системи за складирање податоци и се од повеќе „академски“ интерес отколку практичен.

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

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

Извор: www.habr.com