Kiiruselt usaldusväärne tihendus (Jätkukiri)

See artikkel on juba teine teema kiirusest andmete tihendamisel. Esimeses artiklis kirjeldati tihendajat, mis töötab kiirusel 10 Gbyte/s ühe protsessorituuma kohta (minimaalne tihendus, RTT-Min).

See tihendaja on juba rakendatud kriminalistika duplikaatorite seadmetesse kiirusel andmedumpide tihendamiseks ja krüptograafia vastupidavuse suurendamiseks; samuti saab seda kasutada virtuaalmasinate piltide ja operatiivmälu swap-failide tihendamiseks nende salvestamisel kiiretel SSD salvestusseadmetel.

Esimeses artiklis kuulutati välja ka HDD ja SSD ketaste varukoopiate tihendusalgoritmi arendamine (keskmine tihendus, RTT-Mid) märkimisväärselt paranenud andmete tihendamise parameetritega. Praeguseks on see tihendaja täielikult valmis ja see artikkel räägib just temast.

Tihendaja, mis teostab RTT-Mid algoritmi, tagab tihendustaseme, mis on võrreldav standardsete arhiveerijatega nagu WinRar, 7-Zip, mis töötavad kiiruserežiimis. Samal ajal on tema töökiirus vähemalt kordades kõrgem.

Andmete pakkimise/avamise kiirus on kriitiline parameeter, mis määrab tihendustehnoloogiate kasutusala. Harva kellelgi tuleks pähe tihendada terabait andmeid kiirusel 10-15 MegaBaiti sekundis (see on arhiveerijate standardrežiimis saavutatud kiirus), kuna sellele kulub peaaegu kakskümmend tundi täisprotsessorikoormuse korral...

Teisest küljest saab sama terabaiti kopeerida kiirusel umbes 2-3 GigaBaiti sekundis kümne minuti jooksul.

Seetõttu on suurtel andmemahtudel teabe tihendamine relevantne, kui seda tehakse mitte madalama kiirusena kui reaalse sisendi/väljundi kiirus. Kaasaegsete süsteemide puhul on see vähemalt 100 MegaBaiti sekundis.

Need kiirus näitajad saavad kaasaegsed tihendajad andma ainult «kiire» režiimis. Just selle aktuaalse režiimi järgi teeme RTT-Mid algoritmi ja traditsiooniliste tihendajate võrdluse.

Uue tihendusalgoritmi võrdlev testimine

Tihendaja RTT-Mid töötas testprogrammi koostisosana. Tegelikus «töötavas» rakenduses töötab see oluliselt kiiremini, kus järjekindlalt kasutatakse mitme lõimega töötlemist ja rakendatakse «tavalist» kompilaatorit, mitte C#.

Kuna võrreldes testides kasutatavad kompressorid põhinevad erinevatel printsiipidel ja erinevad andmetüübid kokku suruvad erinevalt, kasutati objektiivsuse tagamiseks meetodit "keskmine temperatuur haiglas"…

Loodi sektorite kaupa loogilise kettadumpli fail, kus on operatsioonisüsteem Windows 10, see on kõige loomulikum segu erinevatest andmestruktuuridest, mis tegelikult on igal arvutil. Selle faili kokkusurutamine võimaldab võrrelda uue algoritmi kiirus ja kokkusurumise aste kõige arenenumate kompressorite seas, mida kasutatakse kaasaegsetes arhiivijas.

Siin on see dumpli fail:

Dumpli faili surusid kokku kompressorid RTT-Mid, 7-zip, WinRar. WinRari ja 7-zip kompressorid olid seadistatud maksimaalsele töökiirusel.

Kompressor töötab 7-zip:

See koormab protsessorit 100%, samal ajal on keskmine kiirus lähtedumpli lugemisel umbes 60 MegaBaidi/s.

Kompressor töötab WinRar:

Olukord on sarnane, protsessori koormus on praktiliselt 100%, keskmine kiirus dumpli lugemisel on umbes 125 MegaBaidi/s.

Nagu eelmisel juhul, on arhiivija töö kiirus piiratud protsessori võimalustega.

Nüüd töötab kompressori testprogramm RTT-Mid:

Ekraanipilt näitab, et protsessor on koormatud 50% ja ülejäänud aja on see vaikne, kuna pole kohta, kuhu kokku suruda andmeid. Andmete väljastus ketas (Ketas 0) on praktiliselt täis. Andmete lugemise kiirus (Ketas 1) kõigub tugevalt, kuid keskmiselt on see üle 200 MegaBaidi/s.

Kompressor töö kiirus on antud juhul piiratud kokku surutud andmete kirjutamisega Kettale 0.

Nüüd on saadud arhiivide kokkusurumise aste:

On nähtav, et kompressor RTT-Mid on kõige paremini kokku surunud, arhiiv, mille ta lõi, on 1,3 GigaBaiti väiksem WinRari arhiivist ja 2,1 GigaBaiti väiksem 7z arhiivist.

Aeg arhiivi loomisele:

• 7-zip – 26 minutit 10 sekundit;
• WinRar – 17 minutit 40 sekundit;
• RTT-Mid – 7 minutit 30 sekundit.

Nii et isegi testprogramm, mis pole optimeeritud, suutis RTT-Midi algoritmi kasutades rohkem kui kaks ja pool korda kiiremini arhiivi luua, samal ajal on arhiiv märkimisväärselt väiksem kui konkurentidel…

Need, kes ei usalda ekraanipilte, saavad nende autentsust ise kontrollida. Testprogramm on saadaval lingil, laadige alla ja kontrollige.

Aga ainult AVX-2 toega protsessoritel, neid juhiseid toeta protsessorite puhul kompressor ei tööta, ning ärge testige algoritmi vanadel AMD protsessoritel, need on AVX käsu täitmisel aeglased...

Kasutatud kompressioonimeetod

Algritmis kasutatakse korduvate tekstifragmentide indekseerimise meetodit baitide granulaarsuses. Selline tihendamise meetod on tuntud juba pikka aega, kuid seda ei ole kasutatud, kuna vasteotsingu teostamine oli ressursside osas väga kulukas ja nõudis aega oluliselt rohkem kui sõnastiku koostamine. Seega on algoritm RTT-Mid klassikaline näide liikumisest "tagasi tulevikku"...

RTT kompressor kasutab ainulaadset kiirete vasteotsingu skannerit, see võimaldas kiirendada kompressiooniprotsessi. Skanner on tehtud käsitööna, "mu ilus", "hind on suur, kuna see on täielikult käsitsi valmistatud" (kirjutatud assembleris).

Vasteotsingu skanner on teostatud kaheastmelise tõenäosusmeetodi kohaselt, esmalt skaneeritakse "märgi" olemasolu ja alles pärast märgi tuvastamist käivitatakse reaalse vaste avastamise protseduur.

Vasteotsingu aken on ettearvamatu suurusega, sõltudes töödeldava andmepaki entropia määrast. Täiesti juhuslike (tihendamatute) andmete puhul on selle suurus megabait, korduvate andmete puhul on see alati suurem kui megabait.

Aga paljud tänapäevased andmeformaatide on tihendamatud ja ressursside nõudlik skanner nende peal on kasutu ja raiskav, seetõttu kasutatakse skanneris kahte töörežiimi. Esmalt otsitakse originaalteksti osi võimalike korduste jaoks, see toiming tehakse samuti tõenäosusmeetodi kaudu ja toimub väga kiiresti (kiirus 4-6 Gigabaiti/sek). Seejärel töödeldakse võimalikud kokkulangevused põhiskanneriga.

Indekseerimine ei ole väga efektiivne, tuleb asendada korduvad fragmentid indeksitega ja indeksimassiiv vähendab märgatavalt tihendamise suhet.

Kuna indekseerimise määr katab mitte ainult täielikke vasteid baitide stringidele, vaid ka osalisi, kui stringis on nii vastavad kui ka mitte соответствующие byte'id. Selleks on indeksi formaati kaasatud vaste maski väli, mis näitab kahe ploki vastavaid byte'e. Veelgi suuremaks kokkusurutuseks kasutatakse indekseerimist, kus on ülekattega mitu osaliselt kattuvat plokki, praeguse ploki kohal.

Kõik see võimaldas RТT-Mid kompressoril saavutada kokkusurumise taset, mis on võrreldav sõnaraamatute meetodil töötavate kompressoritega, kuid töötab tunduvalt kiiremini.

Uue kokkusurumise algoritmi töökiirus

Kui kompressor töötab mälukahevormil (ühe niidi jaoks on vajalik 4 Megabaiti), siis töökiirus kõigub 700-2000 Megabaiti/seki ühe protsessorituuma kohta, olenevalt tihendatavate andmete tüübist ja sõltub vähe protsessori töötamise sagedusest.

Mitme niidiga kompressori rakendamisel määrab tõhus skaleeritavus kolmanda taseme vahemälu suurus. Näiteks, kui on olemas 9 Megabaiti vahemälu, ei ole mõtet käivitada rohkem kui kahte tihendamisniiti, kuna kiirus ei tõuse sellest. Kuid 20 Megabaiti vahemäluga saab juba käivitada viis tihendamisniiti.

Samuti on oluline parameeter, mis määrab kompressori töökiirusel, operatiivmälu latentsus. Algoritm kasutab juhuslikke pöördumisi OП-le, millest osa ei jõua vahemällu (umbes 10%), mistõttu peab see ootama OП-st andmete saamist, mis vähendab töökiirust.

Ka andmete sisendi/väljundi süsteemi töö mõjutab märkimisväärselt kompressori kiirus. OП päringud sisendi/väljundi seostavad CPU andmete taotlusi, mis samuti vähendab kokkusurumise kiirus. See probleem on oluline sülearvutitele ja lauaarvutitele, serverid kuna see on vähem oluline, tänu arenenumale süsteemile, mis reguleerib juurdepääsu süsteemi bussile ja mitmekanalilisele operatiivmälu.

Kogu artikli tekstis räägitakse kompressioonist, dekompressioon jääb selle artikli raames välja, kuna seal "on kõik korras". Dekompressioon toimub märgatavalt kiiremini ja on piiratud sisendi/väljundi kiirusest. Üks füüsiline süda suudab ühes voos rahulikult saavutada 3-4 gigabaiti/s suuruseid lahti pakkimise kiirus.

See on seotud sellega, et lahti pakkimise protsessis puudub vaste otsimise operatsioon, mis "neelab" kompressiooniprotsessi käigus peamisi protsessori ja vahemälu ressursse.

Suruandmete usaldusväärne säilitamine

Nimes tuleneb kogu programmide klassist, mis kasutab andmete kompressiooni (arhivaatorid), nad on mõeldud teabe pikaajaliseks säilitamiseks, mitte aastateks, vaid sajanditeks ja tuhandeteks aastateks...

Andmete säilitamise jooksul kaotavad info kandjad osa andmeid, siin on näide:

Sellel "analoogsel" teabe kandjal on aastatuhande ajalugu, mõned fragmendid on kadunud, kuid üldiselt on info "loetav"...

Ükski vastutav kaasaegne digitaalsete andmesalvestussüsteemide tootja ega digitaalsete andmevahendite tootja ei anna garantiisid, et andmed säilivad täielikult üle 75 aasta.
Ja see on probleem, kuid probleem, mis on edasi lükatud, lahendavad selle meie järeltulijad...

Digitaalsete andmete salvestussüsteemid võivad kaotada andmeid mitte ainult 75 aasta pärast, andmevead võivad ilmneda igal ajal, isegi nende salvestamise ajal. Nende moonutuste minimeerimiseks püüavad nad kasutada liigset teavet ja korrigeerida vigade parandamise süsteemide abil. Liigne teave ja vigade parandamise süsteemid suudavad kaotatud teavet kaugelt mitte alati taastada, ja isegi kui nad taastavad, ei ole garantiid, et taastamisoperatsioon toimus õigesti.

Ja see on samuti suur probleem, kuid mitte edasi lükatud, vaid praegune.

Kaasaegsed kompressorid, mida kasutatakse digitaalsete andmete arhiveerimiseks, põhinevad erinevatel sõnaraamatu meetodi modifikatsioonidel, ja selliste arhivide puhul on teabe fragmendi kaotamine fataalne sündmus. Sellise olukorra jaoks on olemas isegi väljakujunenud mõisted — "rikkis" arhiiv...

Madala usaldusväärsus andmete säilitamisel sõnaraamiga tihendatud arhiivides on seotud tihendatud andmete struktuuriga. Sellises arhiivis ei ole algset teksti, vaid seal hoitakse sõnaraamatu salvestuste numbreid, samas kui sõnaraamat muudetakse dünaamiliselt jooksva tihendatava teksti põhjal. Arhiivi murrangu või moonduse korral on kõiki järgnevaid arhiivi salvestusi võimatu tuvastada ei sisu ega sõnaraamatu salvestuse pikkuse järgi, kuna ei ole selge, millele vastab sõnaraamatu salvestuse number.

Teavet sellisest "katkestatud" arhiivist ei ole võimalik taastada.

RTT algoritm põhineb usaldusväärsemal meetodil tihendatud andmete hoidmiseks. Siin rakendatakse indeksimeetodit korduvate fragmentide arvestamiseks. Selline lähenemine tihendusele aitab minimeerida andmete moonutamise tagajärgi ja paljusid moonutusi, mis esinevad andmete hoidmisel, on võimalik automaatselt korrigeerida.
See on tingitud sellest, et indeksitihenduse korral sisaldab arhiivifail kahte väljad:

• algse teksti väli, millest on eemaldatud korduvate osade osad;
• indeksite väli.

Kriitiliselt oluline teabe taastamiseks on indeksi väli, mis on suuruselt väike ja seda saab andmete usaldusväärse hoidmise nimel dubleerida. Seega, isegi kui algse teksti või indeksimassi fragment kaob, saab kogu muu teabe taastada ilma probleemideta, nagu pildil sarnase analoogse andmekandja puhul.

Alati on puudusi.

Eeliseid ei ole ilma puudusteta. Indeksimeetod ei tihenda korduvaid lühikesi järjekordi. See on seotud indeksimeetodi piirangutega. Indeksid on vähemalt 3 biiti suured ja võivad ulatuda isegi 12 biidini. Kui esineb kordus, mille suurus on väiksem kui seda kirjeldav indeks, siis ei arvestata seda, olenemata sellest, kui tihti sellised kordused esinevad tihendatud failis.

Traditsiooniline, sõnaraamatupõhine kompressioonimeetod tõhusalt tihendab lühikesi korduseid ja seega saavutab suurema tihendusteguri kui indeksikompressioon. Kuid see saavutatakse protsessorile kõrgema koormuse hinnaga, et sõnaraamatupõhine meetod hakkaks andmeid efektiivsemalt tihendama, peab see vähendama andmete töötlemise kiiruseni 10-20 megabaiti sekundis reaalsetes arvutuses, kui CPU on täielikult koormatud.

Nii madalad kiirusd on tänapäevaste andmesalvestussüsteemide jaoks vastuvõetamatud ja pakuvad rohkem "akadeemilist" huvi kui praktilist.

Teabe tihendamise tase suureneb märkimisväärselt järgmises RTT (RТT- Max) algoritmi modifikatsioonis, mis on juba arendamisel.

Nii et nagu ikka, järgnevad sündmused…

Allikas: habr.com