Šis straipsnis yra jau antrasis didelės spartos duomenų glaudinimo temoje. Pirmajame straipsnyje buvo aprašytas kompresorius, veikiantis 10 GB/sek greičiu. vienam procesoriaus branduoliui (minimalus suspaudimas, RTT-Min).
Šis kompresorius jau įdiegtas kriminalistinių kopijavimo aparatų įrangoje, skirtas sparčiam laikmenų sąvartynų suspaudimui ir kriptografijos stiprumo didinimui; juo taip pat galima suspausti virtualių mašinų vaizdus ir RAM apsikeitimo failus išsaugant juos didelės spartos. SSD diskai.
Pirmajame straipsnyje taip pat buvo paskelbtas suspaudimo algoritmas, skirtas suspausti atsargines HDD ir SSD diskų įrenginių kopijas (vidutinis suspaudimas, RTT-Mid) su žymiai patobulintais duomenų glaudinimo parametrais. Šiuo metu šis kompresorius yra visiškai paruoštas ir šis straipsnis yra apie jį.
Kompresorius, įgyvendinantis RTT-Mid algoritmą, užtikrina glaudinimo koeficientą, panašų į standartinius archyvavimo įrenginius, tokius kaip WinRar, 7-Zip, veikiančius didelės spartos režimu. Tuo pačiu metu jo veikimo greitis yra bent eilės tvarka didesnis.
Duomenų pakavimo/išpakavimo greitis yra kritinis parametras, nulemiantis glaudinimo technologijų taikymo sritį. Vargu ar kam nors kiltų mintis suspausti terabaitą duomenų 10-15 megabaitų per sekundę greičiu (būtent tokia sparta yra archyvatorių standartiniu suspaudimo režimu), nes pilnai apkrovus procesorių tai užtruktų beveik dvidešimt valandų. .
Kita vertus, tą patį terabaitą galima nukopijuoti 2–3 gigabaitų per sekundę greičiu maždaug per dešimt minučių.
Todėl didelės apimties informacijos suspaudimas yra svarbus, jei jis atliekamas ne mažesniu greičiu nei realus įvesties/išvesties greitis. Šiuolaikinėse sistemose tai yra mažiausiai 100 megabaitų per sekundę.
Šiuolaikiniai kompresoriai gali pagaminti tokį greitį tik „greitu“ režimu. Būtent šiuo dabartiniu režimu palyginsime RTT-Mid algoritmą su tradiciniais kompresoriais.
Naujo glaudinimo algoritmo lyginamasis testavimas
RTT-Mid kompresorius veikė kaip bandymo programos dalis. Tikroje „darbinėje“ programoje ji veikia daug greičiau, ji protingai naudoja kelių gijų kūrimą ir naudoja „įprastą“ kompiliatorių, o ne C#.
Kadangi lyginamajame tyrime naudojami kompresoriai yra sukurti skirtingais principais ir skirtingų tipų duomenys suspaudžiami skirtingai, bandymo objektyvumui užtikrinti buvo panaudotas „vidutinės temperatūros ligoninėje“ matavimo metodas...
Buvo sukurtas loginio disko su Windows 10 operacine sistema sektorius iškelties failas – tai natūraliausias įvairių duomenų struktūrų derinys, iš tikrųjų prieinamas kiekviename kompiuteryje. Suspaudę šį failą galėsite palyginti naujojo algoritmo greitį ir suspaudimo laipsnį su pažangiausiais šiuolaikiniuose archyvuose naudojamais kompresoriais.
Čia yra išrašymo failas:
Iškelties failas buvo suspaustas naudojant PTT-Mid, 7-zip ir WinRar kompresorius. „WinRar“ ir 7 užtrauktukų kompresorius buvo nustatyti maksimaliu greičiu.
Kompresorius veikia 7 zip:
Он грузит процессор на 100%, при этом средняя скорость чтения исходного дампа около 60 МегаБайт/сек.
Kompresorius veikia WinRAR:
Situacija panaši, procesoriaus apkrova beveik 100%, vidutinis dump skaitymo greitis apie 125 Megabaitai/sek.
Kaip ir ankstesniu atveju, archyvavimo greitį riboja procesoriaus galimybės.
Dabar veikia kompresoriaus bandymo programa RTT-Mid:
Ekrano kopijoje matyti, kad procesorius apkraunamas 50%, o likusį laiką neveikia, nes nėra kur įkelti suspaustų duomenų. Duomenų įkėlimo diskas (Disk 0) beveik visiškai įkeltas. Duomenų skaitymo greitis (1 diskas) labai skiriasi, bet vidutiniškai daugiau nei 200 megabaitų/sek.
Šiuo atveju kompresoriaus greitį riboja galimybė įrašyti suglaudintus duomenis į 0 diską.
Dabar gautų archyvų suspaudimo koeficientas:
Galima pastebėti, kad RTT-Mid kompresorius geriausiai atliko suspaudimo darbą; jo sukurtas archyvas buvo 1,3 gigabaito mažesnis nei „WinRar“ archyvas ir 2,1 gigabaito mažesnis nei 7z archyvas.
Laikas, praleistas kuriant archyvą:
- 7-zip – 26 minutės 10 sekundžių;
- WinRar – 17 minučių 40 sekundžių;
- RTT-Mid – 7 minutės 30 sekundžių.
Taigi net bandomoji, neoptimizuota programa, naudojant RTT-Mid algoritmą, galėjo sukurti archyvą daugiau nei du su puse karto greičiau, o archyvas pasirodė esąs gerokai mažesnis nei konkurentų...
Tie, kurie netiki ekrano nuotraukomis, gali patys patikrinti jų autentiškumą. Bandymo programą rasite adresu , atsisiųskite ir patikrinkite.
Bet tik ant procesorių su AVX-2 palaikymu, be šių instrukcijų palaikymo kompresorius neveikia, o senesniuose AMD procesoriuose algoritmo netikrina, jie lėtai vykdo AVX instrukcijas...
Naudojamas suspaudimo metodas
В алгоритме используется метод индексирования повторяющихся фрагментов текста в байтовой грануляции. Такой метод сжатия известен давно, но не использовался, поскольку операция поиска совпадений была очень затратна по необходимым ресурсам и требовала гораздо более времени нежели построение словаря. Так что алгоритм RTT-Mid является классическим примером движения «назад в будущее»…
PTT kompresorius naudoja unikalų didelės spartos atitikmenų paieškos skaitytuvą, kuris leidžia paspartinti suspaudimo procesą. Savarankiškai pagamintas skaitytuvas, tai yra „mano žavesys...“, „jis gana brangus, nes visiškai rankų darbo“ (parašyta assembler).
Atitikties paieškos skaitytuvas pagamintas pagal dviejų lygių tikimybinę schemą: pirmiausia nuskaitomas degtuko „ženklo“ buvimas ir tik identifikavus „ženklą“ šioje vietoje, atliekama tikros atitikties aptikimo procedūra. yra pradėtas.
Окно поиска совпадений имеет непредсказуемый размер, зависящий от степени энтропии в обрабатываемом блоке данных. Для полностью случайных (несжимемых) данных оно имеет размер мегабайт, для данных имеющих повторы всегда имеет размер больше мегабайта.
Tačiau daugelis šiuolaikinių duomenų formatų yra nesuspaudžiami ir per juos paleisti daug resursų reikalaujantį skaitytuvą yra nenaudinga ir švaistoma, todėl skaitytuvas naudoja du darbo režimus. Pirmiausia ieškoma šaltinio teksto dalių su galimais pasikartojimais, ši operacija taip pat atliekama tikimybiniu metodu ir atliekama labai greitai (4-6 Gigabaitai/sek. greičiu). Tada sritis su galimomis atitiktimis apdoroja pagrindinis skaitytuvas.
Indekso suspaudimas nėra labai efektyvus, jūs turite pakeisti pasikartojančius fragmentus indeksais, o indeksų masyvas žymiai sumažina suspaudimo laipsnį.
Siekiant padidinti suspaudimo laipsnį, indeksuojamos ne tik visos baitų eilučių atitiktys, bet ir dalinės, kai eilutėje yra suderintų ir nesuderintų baitų. Norėdami tai padaryti, indekso formate yra atitikties kaukės laukas, nurodantis dviejų blokų atitinkančius baitus. Siekiant dar didesnio suspaudimo, indeksavimas naudojamas kelis iš dalies atitinkančius blokus uždėti ant esamo bloko.
Visa tai leido PTT-Mid kompresoriuje gauti suspaudimo laipsnį, panašų į kompresorių, pagamintų naudojant žodyno metodą, bet veikiantį daug greičiau.
Naujojo glaudinimo algoritmo greitis
Jei kompresorius veikia naudodamas išskirtinai talpyklą (vienai gijai reikia 4 megabaitų), tada veikimo greitis svyruoja nuo 700 iki 2000 megabaitų/sek. vienam procesoriaus branduoliui, priklausomai nuo glaudinamų duomenų tipo ir mažai priklauso nuo procesoriaus veikimo dažnio.
Naudojant kelių gijų kompresorių, efektyvų mastelį lemia trečiojo lygio talpyklos dydis. Pavyzdžiui, turint 9 megabaitų talpyklos atmintį, nėra prasmės paleisti daugiau nei dvi glaudinimo gijas; greitis nuo to nepadidės. Tačiau turėdami 20 megabaitų talpyklą, jau galite paleisti penkias suspaudimo gijas.
Taip pat svarbiu parametru, lemiančiu kompresoriaus greitį, tampa RAM delsa. Algoritmas naudoja atsitiktinę prieigą prie OP, kai kurios iš jų nepatenka į sparčiąją atmintį (apie 10%) ir ji turi veikti tuščiąja eiga, laukdama duomenų iš OP, o tai sumažina veikimo greitį.
Ženkliai įtakoja kompresoriaus greitį ir duomenų įvesties/išvesties sistemos veikimą. Užklausos OP iš I/O blokuoja duomenų iš procesoriaus užklausas, o tai taip pat sumažina suspaudimo greitį. Ši problema yra svarbi nešiojamiesiems ir staliniams kompiuteriams, o serveriams ji yra mažiau reikšminga dėl pažangesnio sistemos magistralės prieigos valdymo bloko ir kelių kanalų RAM.
Visame straipsnio tekste kalbame apie suspaudimą; dekompresija nepatenka į šio straipsnio taikymo sritį, nes „viskas padengta šokoladu“. Dekompresija yra daug greitesnė ir ją riboja įvesties / išvesties greitis. Vienas fizinis branduolys vienoje gijoje lengvai užtikrina 3-4 GB/sek išpakavimo greitį.
Taip yra dėl to, kad dekompresijos metu nėra atitikmenų paieškos operacijos, kuri glaudinimo metu „suvalgo“ pagrindinius procesoriaus ir talpyklos išteklius.
Suspaustų duomenų saugojimo patikimumas
Kaip rodo visos programinės įrangos klasės, kuri naudoja duomenų glaudinimą (archyvus), pavadinimas, jie yra skirti ilgalaikiam informacijos saugojimui ne metams, o šimtmečiams ir tūkstantmečiams...
Saugojimo metu laikmenos praranda dalį duomenų. Štai pavyzdys:
Šiai „analoginei“ informacijos laikmenai jau tūkstantis metų, kai kurie fragmentai pamesti, bet apskritai informacija „įskaitoma“...
Nė vienas iš atsakingų šiuolaikinių skaitmeninių duomenų saugojimo sistemų ir joms skirtų skaitmeninių laikmenų gamintojų nesuteikia visiško duomenų saugumo garantijų daugiau nei 75 metus.
Ir tai yra problema, bet atidėta problema, ją išspręs mūsų palikuonys...
Skaitmeninės duomenų saugojimo sistemos gali prarasti duomenis ne tik po 75 metų, duomenų klaidos gali atsirasti bet kuriuo metu, net ir jų įrašymo metu, šiuos iškraipymus jos stengiasi kuo labiau sumažinti pasitelkdamos dubliavimą ir taisydami klaidų taisymo sistemomis. Atleidimo ir taisymo sistemos ne visada gali atkurti prarastą informaciją, o jei taip, nėra garantijos, kad atkūrimo operacija buvo atlikta teisingai.
Ir tai taip pat yra didelė problema, bet ne atidėta, o dabartinė.
Šiuolaikiniai skaitmeniniams duomenims archyvuoti naudojami kompresoriai yra sukurti remiantis įvairiomis žodyno metodo modifikacijomis, o tokiems archyvams informacijos praradimas bus lemtingas įvykis, tokiai situacijai net yra nustatytas terminas - „sugedęs“ archyvas. ...
Mažas informacijos saugojimo archyvuose patikimumas su žodyno suglaudinimu siejamas su suglaudintų duomenų struktūra. Tokiame archyve esančioje informacijoje nėra šaltinio teksto, jame saugomi žodyno įrašų numeriai, o pats žodynas yra dinamiškai modifikuojamas esamo suspausto teksto. Pametus ar sugadinus archyvo fragmentą, visų vėlesnių archyvo įrašų negalima atpažinti nei pagal turinį, nei pagal įrašo žodyne ilgį, nes neaišku, ką atitinka žodyno įrašo numeris.
Iš tokio „sugedusio“ archyvo informacijos atkurti neįmanoma.
RTT algoritmas pagrįstas patikimesniu suspaustų duomenų saugojimo metodu. Jis naudoja indekso metodą pasikartojančių fragmentų apskaitai. Šis glaudinimo metodas leidžia sumažinti informacijos iškraipymo laikmenoje pasekmes ir daugeliu atvejų automatiškai ištaisyti iškraipymus, atsiradusius informacijos saugojimo metu.
Taip yra dėl to, kad archyvo faile indekso glaudinimo atveju yra du laukai:
- поле исходного текста с удаленными из него участками повтора;
- rodyklės laukas.
Indekso laukas, kuris yra labai svarbus informacijos atkūrimui, nėra didelio dydžio ir gali būti dubliuojamas, kad būtų galima patikimai saugoti duomenis. Todėl net praradus šaltinio teksto fragmentą ar indeksų masyvą, visa kita informacija bus atkurta be problemų, kaip parodyta paveikslėlyje naudojant „analoginę“ laikmeną.
Algoritmo trūkumai
Nėra privalumų be trūkumų. Indekso glaudinimo metodas neglaudina trumpų pasikartojančių sekų. Taip yra dėl indekso metodo apribojimų. Indeksai yra mažiausiai 3 baitų dydžio ir gali būti iki 12 baitų. Jei aptinkamas pakartojimas, kurio dydis yra mažesnis nei jį apibūdinantis indeksas, į jį neatsižvelgiama, nesvarbu, kaip dažnai tokie pasikartojimai aptinkami suspaustame faile.
Tradicinis žodyno suspaudimo metodas efektyviai suspaudžia kelis trumpo ilgio pakartojimus ir todėl pasiekia didesnį suspaudimo laipsnį nei indekso glaudinimas. Tiesa, tai pasiekiama dėl didelės centrinio procesoriaus apkrovos; kad žodyno metodas pradėtų spausti duomenis efektyviau nei indekso metodas, realiame duomenų apdorojimo greitį reikia sumažinti iki 10-20 megabaitų per sekundę. skaičiavimo įrenginiai su visa procesoriaus apkrova.
Toks mažas greitis yra nepriimtinas šiuolaikinėms duomenų saugojimo sistemoms ir yra labiau „akademinis“ nei praktiškas.
Informacijos suspaudimo laipsnis bus žymiai padidintas kitoje RTT algoritmo modifikacijoje (RTT-Max), kuri jau yra kuriama.
Taigi, kaip visada, tęsinys...
Šaltinis: www.habr.com