See artikkel on kiire andmete tihendamise teemal juba teine. Esimeses artiklis kirjeldati kompressorit, mis töötab kiirusega 10 GB/sek. protsessori tuuma kohta (minimaalne tihendus, RTT-Min).
Seda kompressorit on juba rakendatud kohtuekspertiisi paljundusmasinate seadmetes salvestusmeediumiprügi kiireks tihendamiseks ja krüptograafia tugevuse suurendamiseks; seda saab kasutada ka virtuaalmasinate kujutiste ja RAM-i vahetusfailide tihendamiseks, kui need salvestatakse kiirele kiirusele. SSD-draivid.
Esimeses artiklis teatati ka tihendusalgoritmi väljatöötamisest HDD- ja SSD-kettaseadmete varukoopiate tihendamiseks (keskmine tihendus, RTT-Mid) oluliselt täiustatud andmete tihendamise parameetritega. Nüüdseks on see kompressor täiesti valmis ja see artikkel räägib sellest.
RTT-Mid algoritmi rakendav kompressor tagab tihendussuhte, mis on võrreldav tavaliste arhiiviseadmetega, nagu WinRar, 7-Zip, mis töötavad kiires režiimis. Samal ajal on selle töökiirus vähemalt suurusjärgu võrra suurem.
Andmete pakkimise/lahtipakkimise kiirus on kriitiline parameeter, mis määrab tihendustehnoloogiate rakendusala. Vaevalt, et kellelgi tuleks pähe terabaidise andmemahu tihendamine kiirusega 10-15 megabaiti sekundis (täpselt selline on standardse tihendusrežiimi arhiveerijate kiirus), sest protsessori täiskoormusega kuluks selleks ligi paarkümmend tundi. .
Teisalt saab sama terabaiti kopeerida kiirusega 2-3 gigabaiti sekundis umbes kümne minutiga.
Seetõttu on suuremahulise teabe tihendamine oluline, kui seda teostatakse kiirusega, mis ei ole väiksem tegeliku sisendi/väljundi kiirusest. Kaasaegsete süsteemide puhul on see vähemalt 100 megabaiti sekundis.
Kaasaegsed kompressorid suudavad selliseid kiirusi toota ainult "kiire" režiimis. Selles praeguses režiimis võrdleme RTT-Mid algoritmi traditsiooniliste kompressoritega.
Uue tihendusalgoritmi võrdlev testimine
RTT-Mid kompressor töötas testprogrammi osana. Päris "töötavas" rakenduses töötab see palju kiiremini, kasutab targalt mitme lõimega töötlemist ja kasutab "tavalist" kompilaatorit, mitte C#.
Kuna võrdlustestis kasutatavad kompressorid on üles ehitatud erinevatel põhimõtetel ja erinevat tüüpi andmeid tihendatakse erinevalt, siis testi objektiivsuse huvides kasutati “haigla keskmise temperatuuri” mõõtmise meetodit...
Loodi Windows 10 operatsioonisüsteemiga loogilise ketta sektoripõhine tõmmisfail, mis on kõige loomulikum segu erinevatest andmestruktuuridest, mis on tegelikult igas arvutis saadaval. Selle faili tihendamine võimaldab teil võrrelda uue algoritmi kiirust ja tihendusastet kaasaegsetes arhiiviseadmetes kasutatavate kõige arenenumate kompressoritega.
Siin on tühjefail:
Dump fail tihendati PTT-Mid, 7-zip ja WinRar kompressorite abil. WinRar ja 7-zip-kompressor seadistati maksimaalsele kiirusele.
Kompressor töötab 7-zip:
See laadib protsessorit 100%, samas kui algse väljavõtte lugemise keskmine kiirus on umbes 60 megabaiti sekundis.
Kompressor töötab WinRAR:
Olukord on sarnane, protsessori koormus on peaaegu 100%, keskmine dump lugemiskiirus on umbes 125 Megabaiti/sek.
Nagu ka eelmisel juhul, piiravad arhiveerija kiirust protsessori võimalused.
Kompressori testimisprogramm töötab nüüd RTT-Mid:
Ekraanipildil on näha, et protsessor on 50% laetud ja ülejäänud aja on jõude, kuna tihendatud andmeid pole kuhugi üles laadida. Andmete üleslaadimise ketas (ketas 0) on peaaegu täielikult laetud. Andmete lugemise kiirus (Disk 1) on väga erinev, kuid keskmiselt rohkem kui 200 megabaiti/sek.
Kompressori kiirust piirab sel juhul tihendatud andmete kettale 0 kirjutamise võimalus.
Nüüd saadud arhiivide tihendussuhe:
On näha, et RTT-Mid kompressor sai kõige paremini tihendamisega hakkama; selle loodud arhiiv oli 1,3 gigabaiti väiksem kui WinRari arhiiv ja 2,1 gigabaiti väiksem kui 7z arhiiv.
Arhiivi loomisele kulunud aeg:
- 7-tõmblukk – 26 minutit 10 sekundit;
- WinRar – 17 minutit 40 sekundit;
- RTT-Mid – 7 minutit 30 sekundit.
Nii suutis ka test, optimeerimata programm, kasutades RTT-Mid algoritmi, luua arhiivi enam kui kaks ja pool korda kiiremini, samas kui arhiiv osutus konkurentide omast oluliselt väiksemaks...
Need, kes ekraanipilte ei usu, saavad nende autentsust ise kontrollida. Testiprogramm on saadaval aadressil , laadige alla ja kontrollige.
Kuid ainult AVX-2 toega protsessoritel, ilma nende juhiste toetamiseta kompressor ei tööta ja ärge testige algoritmi vanematel AMD protsessoritel, need on AVX-i käskude täitmisel aeglased...
Kasutatud tihendusmeetodit
Algoritm kasutab meetodit korduvate tekstifragmentide indekseerimiseks baiditäpsusega. See tihendusmeetod on tuntud juba pikka aega, kuid seda ei kasutatud, kuna sobitusoperatsioon oli vajalike ressursside poolest väga kulukas ja nõudis palju rohkem aega kui sõnastiku koostamine. Nii et RTT-Mid algoritm on klassikaline näide "tagasi tulevikku" liikumisest...
PTT-kompressor kasutab ainulaadset kiiret vasteotsingu skannerit, mis võimaldab tihendusprotsessi kiirendada. Isetehtud skanner, see on "minu võlu...", "see on üsna kallis, sest see on täielikult käsitsi valmistatud" (kirjutatud assembleris).
Vasteotsingu skanner tehakse kahetasandilise tõenäosusskeemi järgi: esiteks skannitakse vaste "märgi" olemasolu ja alles pärast "märgi" tuvastamist selles kohas tehakse tõelise vaste tuvastamise protseduur. käivitatakse.
Vasteotsingu aken on ettearvamatu suurusega, olenevalt töödeldud andmeploki entroopia astmest. Täiesti juhuslike (kompresseerimata) andmete puhul on selle suurus megabaidid, kordustega andmete puhul on see alati suurem kui megabait.
Kuid paljud kaasaegsed andmevormingud on tihendamatud ja nende kaudu ressursimahuka skanneri käivitamine on kasutu ja raiskav, mistõttu skanner kasutab kahte töörežiimi. Esiteks otsitakse lähteteksti võimalike kordustega lõigud, seegi toiming viiakse läbi tõenäosusmeetodil ja tehakse väga kiiresti (kiirusega 4-6 Gigabaiti/sek). Võimalike vastetega alasid töötleb seejärel põhiskanner.
Indeksi tihendamine ei ole väga tõhus, dubleerivad fragmendid tuleb asendada indeksitega ja indeksimassiivi vähendab oluliselt tihendussuhet.
Tihendusastme suurendamiseks ei indekseerita mitte ainult baidistringide täielikke vasteid, vaid ka osalisi vasteid, kui string sisaldab sobitatud ja sobitamata baite. Selleks sisaldab indeksi vorming vaste maski välja, mis näitab kahe ploki sobivaid baite. Veelgi suuremaks tihendamiseks kasutatakse indekseerimist, et lisada praegusele plokile mitu osaliselt sobivat plokki.
Kõik see võimaldas saavutada PTT-Mid kompressoris tihendusastme, mis on võrreldav sõnastikumeetodil valmistatud, kuid palju kiiremini töötavate kompressoritega.
Uue tihendusalgoritmi kiirus
Kui kompressor töötab eranditult vahemälu kasutamisega (ühele lõimele on vaja 4 megabaiti), jääb töökiirus vahemikku 700-2000 megabaiti/sek. protsessori tuuma kohta, olenevalt tihendatavate andmete tüübist ja sõltub vähe protsessori töösagedusest.
Kompressori mitme keermega teostuse korral määrab efektiivse skaleeritavuse kolmanda taseme vahemälu suurus. Näiteks kui pardal on 9 megabaiti vahemälu, pole mõtet käivitada rohkem kui kahte tihenduslõimi, kiirus sellest ei suurene. Kuid 20-megabaidise vahemäluga saate käivitada juba viis tihenduslõimi.
Samuti muutub RAM-i latentsusaeg oluliseks parameetriks, mis määrab kompressori kiiruse. Algoritm kasutab juhuslikku juurdepääsu OP-le, millest osa ei pääse vahemällu (umbes 10%) ja see peab olema tühikäigul, oodates OP-st andmeid, mis vähendab töökiirust.
Mõjutab oluliselt kompressori kiirust ja andmete sisend/väljundsüsteemi tööd. Päringud OP-le I/O-lt blokeerivad protsessori andmete päringuid, mis samuti vähendab tihenduskiirust. See probleem on märkimisväärne sülearvutite ja lauaarvutite puhul; serverite puhul on see vähem oluline täiustatud süsteemisiini juurdepääsu juhtimisseadme ja mitme kanaliga RAM-i tõttu.
Kogu artikli tekstis räägime kompressioonist; dekompressioon jääb selle artikli reguleerimisalast välja, kuna "kõik on šokolaadiga kaetud". Dekompressioon on palju kiirem ja seda piirab I/O kiirus. Üks füüsiline tuum ühes lõimes tagab hõlpsasti lahtipakkimiskiiruse 3-4 GB/sek.
Selle põhjuseks on vastete otsimise toimingu puudumine dekompressiooniprotsessi ajal, mis "sööb" tihendamise ajal protsessori ja vahemälu peamised ressursid.
Tihendatud andmesalvestuse töökindlus
Nagu kogu andmete tihendamist kasutava tarkvara klassi nimi (arhiivid) viitab, on need mõeldud teabe pikaajaliseks säilitamiseks, mitte aastateks, vaid sajanditeks ja aastatuhandeteks...
Salvestamise ajal kaotavad andmekandjad osa andmeid, siin on näide:
See “analoog” infokandja on tuhat aastat vana, mõned killud on kadunud, aga üldiselt on info “loetav”...
Ükski kaasaegsete digitaalsete andmesalvestussüsteemide ja nende jaoks digitaalsete andmekandjate vastutavatest tootjatest ei anna garantiid täielikule andmeohutusele üle 75 aasta.
Ja see on probleem, kuid edasi lükatud probleem, meie järeltulijad lahendavad selle...
Digitaalsed andmesalvestussüsteemid võivad andmeid kaotada mitte ainult 75 aasta pärast, andmetes võivad vead ilmneda igal ajal, isegi nende salvestamise ajal, neid moonutusi püütakse redundantsi kasutades minimeerida ja veaparandussüsteemidega parandada. Liiasus- ja parandussüsteemid ei saa alati kaotatud teavet taastada ja kui nad seda teevad, ei ole mingit garantiid, et taastamisoperatsioon viidi õigesti lõpule.
Ja see on ka suur probleem, kuid mitte edasilükatud, vaid praegune probleem.
Kaasaegsed digitaalsete andmete arhiveerimiseks kasutatavad kompressorid on üles ehitatud sõnastikumeetodi erinevatele modifikatsioonidele ja selliste arhiivide jaoks on teabe kadumine saatuslikuks sündmuseks, sellise olukorra jaoks on isegi kehtestatud termin - "katkine" arhiiv. ...
Sõnastiku tihendamisega arhiivides teabe säilitamise madal usaldusväärsus on seotud tihendatud andmete struktuuriga. Sellises arhiivis olev teave ei sisalda lähteteksti, sinna salvestatakse sõnastiku kirjete numbrid ja sõnastikku ennast muudab dünaamiliselt praegune tihendatud tekst. Arhiivifragmendi kaotsimineku või riknemise korral ei saa kõiki järgnevaid arhiivikirjeid tuvastada ei sõnastiku kirje sisu ega pikkuse järgi, kuna pole selge, millele sõnaraamatu kirje number vastab.
Sellisest "katkisest" arhiivist on teavet võimatu taastada.
RTT-algoritm põhineb tihendatud andmete salvestamise usaldusväärsemal meetodil. See kasutab korduvate fragmentide arvestamiseks indeksmeetodit. Selline tihendamise lähenemisviis võimaldab minimeerida andmekandjal oleva teabe moonutamise tagajärgi ja paljudel juhtudel automaatselt parandada teabe salvestamise ajal tekkinud moonutusi.
Selle põhjuseks on asjaolu, et indeksi tihendamise korral sisaldab arhiivifail kahte välja:
- lähteteksti väli, millelt korduvad lõigud on eemaldatud;
- indeksi väli.
Teabe taastamiseks kriitilise tähtsusega registriväli ei ole suur ja seda saab usaldusväärseks andmete salvestamiseks dubleerida. Seega, isegi kui lähteteksti või indeksimassiivi fragment kaob, taastatakse kogu muu teave probleemideta, nagu pildil "analoogse" andmekandja puhul.
Algoritmi puudused
Ei ole eeliseid ilma puudusteta. Indeksi tihendamise meetod ei tihenda lühikesi korduvaid jadasid. See on tingitud indeksmeetodi piirangutest. Indeksid on vähemalt 3 baiti suurused ja võivad olla kuni 12 baiti. Kui tekib kordus, mille suurus on väiksem kui seda kirjeldav indeks, siis seda ei võeta arvesse, olenemata sellest, kui sageli tihendatud failis selliseid kordusi tuvastatakse.
Traditsiooniline sõnastiku tihendamise meetod tihendab tõhusalt mitu lühikese pikkusega kordust ja saavutab seetõttu kõrgema tihendusastme kui indekstihendus. Tõsi, see saavutatakse tänu keskprotsessori suurele koormusele; selleks, et sõnastikumeetod hakkaks andmeid tõhusamalt tihendama kui indeksmeetod, peab see vähendama andmetöötluse kiirust 10-20 megabaidile sekundis reaalarvutis. arvutiinstallatsioonid täisprotsessori koormusega.
Sellised madalad kiirused on tänapäevaste andmesalvestussüsteemide jaoks vastuvõetamatud ja pakuvad rohkem "akadeemilist" kui praktilist huvi.
Info tihendamise astet suurendatakse oluliselt juba väljatöötamisel oleva RTT algoritmi järgmise modifikatsiooniga (RTT-Max).
Niisiis, nagu ikka, jätkub...
Allikas: www.habr.com