Ez a cikk már a második a nagy sebességű adattömörítés témakörében. Az első cikk egy 10 GB/sec sebességgel működő kompresszort írt le. processzormagonként (minimális tömörítés, RTT-Min).
Ezt a tömörítőt már beépítették a törvényszéki sokszorosítók berendezéseibe az adathordozó dumpok nagysebességű tömörítésére és a kriptográfia erősségének növelésére, valamint a virtuális gépek képeinek és a RAM swap fájlok tömörítésére is használható, amikor azokat nagy sebességre menti. SSD meghajtók.
Az első cikk egy tömörítési algoritmus kifejlesztését is bejelentette a HDD és SSD lemezmeghajtók biztonsági másolatainak tömörítésére (közepes tömörítés, RTT-Mid), jelentősen javított adattömörítési paraméterekkel. Mostanra ez a kompresszor teljesen készen van, és ez a cikk erről szól.
Az RTT-Mid algoritmust megvalósító tömörítő olyan tömörítési arányt biztosít, amely összehasonlítható a nagy sebességű üzemmódban működő szabványos archiválókéval, mint például a WinRar, 7-Zip. Ugyanakkor a működési sebessége legalább egy nagyságrenddel nagyobb.
Az adatcsomagolás/kicsomagolás sebessége kritikus paraméter, amely meghatározza a tömörítési technológiák alkalmazási körét. Nem valószínű, hogy bárkinek is eszébe jutna 10-15 megabájt/másodperc sebességgel terabájtnyi adatot tömöríteni (ez pont az archiválók sebessége normál tömörítési módban), mert ez majdnem húsz órát venne igénybe teljes processzorterhelés mellett. .
Másrészt ugyanaz a terabájt 2-3 gigabájt/másodperc nagyságrendű sebességgel másolható körülbelül tíz perc alatt.
Ezért fontos a nagy mennyiségű információ tömörítése, ha azt a valós bemeneti/kimeneti sebességnél nem kisebb sebességgel hajtják végre. A modern rendszerek esetében ez legalább 100 megabájt másodpercenként.
A modern kompresszorok csak „gyors” üzemmódban képesek ilyen sebességet produkálni. Ebben a jelenlegi módban hasonlítjuk össze az RTT-Mid algoritmust a hagyományos kompresszorokkal.
Egy új tömörítési algoritmus összehasonlító tesztelése
Az RTT-Mid kompresszor a tesztprogram részeként működött. Egy igazi „működő” alkalmazásban sokkal gyorsabban működik, okosan használja a többszálas kezelést, és „normál” fordítót használ, nem C#-t.
Mivel az összehasonlító tesztben használt kompresszorok eltérő elvekre épülnek, és a különböző típusú adatokat eltérően tömörítik, a teszt objektivitása érdekében a „kórházi átlaghőmérséklet” mérési módszert alkalmaztuk...
Létrejött a Windows 10 operációs rendszerrel működő logikai lemez szektoronkénti dump fájlja; ez a legtermészetesebb keveréke a különféle adatstruktúráknak, amelyek minden számítógépen ténylegesen elérhetők. A fájl tömörítése lehetővé teszi az új algoritmus sebességének és tömörítési fokának összehasonlítását a modern archiválókban használt legfejlettebb tömörítőkkel.
Íme a dump fájl:
A dump fájlt PTT-Mid, 7-zip és WinRar tömörítőkkel tömörítették. A WinRar és a 7-zip kompresszor maximális sebességre lett állítva.
A kompresszor fut 7-zip:
100%-kal terheli a processzort, miközben az eredeti kiírás átlagos olvasási sebessége körülbelül 60 megabájt/sec.
A kompresszor fut WinRAR:
Hasonló a helyzet, a processzorterhelés közel 100%, az átlagos dump olvasási sebesség körülbelül 125 Megabyte/sec.
Az előző esethez hasonlóan az archiváló sebességét a processzor képességei korlátozzák.
A kompresszorteszt program most fut RTT-Mid:
A képernyőképen látható, hogy a processzor 50%-on van terhelve, a többi időben tétlen, mert nincs hova feltölteni a tömörített adatokat. Az adatfeltöltő lemez (Disk 0) majdnem teljesen be van töltve. Az adatolvasási sebesség (1. lemez) nagyon változó, de átlagosan több mint 200 megabájt/sec.
A tömörítő sebességét ebben az esetben korlátozza az a képesség, hogy tömörített adatokat írjon a 0-s lemezre.
Most a kapott archívumok tömörítési aránya:
Látható, hogy az RTT-Mid tömörítő teljesítette a legjobb munkát a tömörítésben: az általa létrehozott archívum 1,3 GigaBájttal kisebb volt, mint a WinRar archívum, és 2,1 Gigabájttal kisebb, mint a 7z archívum.
Az archívum létrehozására fordított idő:
- 7-cipzár – 26 perc 10 másodperc;
- WinRar – 17 perc 40 másodperc;
- RTT-Mid – 7 perc 30 másodperc.
Így még egy teszt, nem optimalizált program is az RTT-Mid algoritmust használva több mint két és félszer gyorsabban tudott archívumot készíteni, miközben az archívum lényegesen kisebbnek bizonyult, mint versenytársaié...
Azok, akik nem hisznek a képernyőképeknek, maguk is ellenőrizhetik azok hitelességét. A tesztprogram elérhető a címen , töltse le és ellenőrizze.
De csak AVX-2 támogatással rendelkező processzorokon, ezen utasítások támogatása nélkül a tömörítő nem működik, és ne tesztelje az algoritmust a régebbi AMD processzorokon, azok lassúak az AVX utasítások végrehajtásában...
Alkalmazott tömörítési módszer
Az algoritmus egy módszert használ az ismétlődő szövegrészletek bájtos részletességű indexelésére. Ez a tömörítési módszer régóta ismert, de nem alkalmazták, mert a párosítási művelet igen költséges volt a szükséges erőforrások szempontjából, és sokkal több időt igényelt, mint egy szótár elkészítése. Tehát az RTT-Mid algoritmus a „vissza a jövőbe” klasszikus példája...
A PTT-kompresszor egyedülálló, nagy sebességű egyezéskeresőt használ, amivel felgyorsíthatjuk a tömörítési folyamatot. Saját készítésű szkenner, ez az „én varázsom...”, „elég drága, mert teljesen kézzel készült” (az assemblerben írva).
Az egyezéskeresési szkenner egy kétszintű valószínűségi séma szerint készül: először az egyezés „jelének” meglétét vizsgálják, és csak miután a „jelet” ezen a helyen azonosították, a valódi egyezés észlelésének eljárása. elindul.
Az egyezéskereső ablak megjósolhatatlan méretű, a feldolgozott adatblokkban lévő entrópia mértékétől függően. Teljesen véletlenszerű (nem tömöríthető) adatoknál megabájt méretű, ismétlődő adatoknál mindig nagyobb, mint egy megabájt.
De sok modern adatformátum nem tömöríthető, és egy erőforrás-igényes szkenner futtatása rajtuk haszontalan és pazarló, ezért a szkenner két üzemmódot használ. Először a forrásszöveg esetleges ismétlődéseket tartalmazó részeit keresik meg, ezt a műveletet szintén valószínűségi módszerrel hajtják végre, és nagyon gyorsan (4-6 GigaByte/sec sebességgel) hajtják végre. A lehetséges egyezésekkel rendelkező területeket ezután a fő szkenner dolgozza fel.
Az indextömörítés nem túl hatékony, a duplikált töredékeket indexekkel kell helyettesíteni, és az indextömb jelentősen csökkenti a tömörítési arányt.
A tömörítési arány növelése érdekében nem csak a bájtkarakterláncok teljes egyezését indexeli a rendszer, hanem a részlegeseket is, amikor a karakterlánc egyező és párosítatlan bájtokat tartalmaz. Ehhez az indexformátum tartalmaz egy illesztési maszk mezőt, amely két blokk egyező bájtjait jelzi. A még nagyobb tömörítés érdekében az indexelést több, részben egyező blokk egymásra helyezésére használják az aktuális blokkra.
Mindez lehetővé tette, hogy a PTT-Mid kompresszorban a szótári módszerrel készült, de sokkal gyorsabban működő kompresszorokhoz hasonló tömörítési arányt kapjunk.
Az új tömörítési algoritmus sebessége
Ha a tömörítő kizárólag cache memória használatával működik (szálonként 4 megabájt szükséges), akkor a működési sebesség 700-2000 megabájt/sec. processzormagonként, a tömörítendő adatok típusától függően, és kevéssé függ a processzor működési frekvenciájától.
A tömörítő többszálas megvalósítása esetén a hatékony méretezhetőséget a harmadik szintű gyorsítótár mérete határozza meg. Például, ha 9 megabájt gyorsítótár van a fedélzeten, nincs értelme kettőnél több tömörítési szálat indítani, a sebesség ettől nem fog növekedni. De 20 megabájtos gyorsítótárral már öt tömörítési szálat futtathat.
Ezenkívül a RAM késleltetése fontos paraméterré válik, amely meghatározza a kompresszor sebességét. Az algoritmus véletlenszerű hozzáférést használ az OP-hoz, amelyek egy része nem kerül be a cache memóriába (kb. 10%), és üresjáratban kell állnia, várva az OP-tól érkező adatokat, ami csökkenti a működés sebességét.
Jelentősen befolyásolja a kompresszor sebességét és az adatbeviteli/kimeneti rendszer működését. Az OP-nak küldött kérések az I/O-tól adatkérések a CPU-tól, ami szintén csökkenti a tömörítési sebességet. Ez a probléma laptopok és asztali számítógépek esetében jelentős, szervereknél kevésbé jelentős a fejlettebb rendszerbusz hozzáférés-vezérlő egység és a többcsatornás RAM miatt.
A cikkben végig a kompresszióról beszélünk; a dekompresszió kívül esik ennek a cikknek a hatókörén, mivel „mindent csokoládé borít”. A dekompresszió sokkal gyorsabb, és az I/O sebesség korlátozza. Egyetlen fizikai mag egy szálban könnyedén 3-4 GB/s-os kicsomagolási sebességet biztosít.
Ennek oka az egyezéskeresési művelet hiánya a kicsomagolási folyamat során, ami a tömörítés során „felemészti” a processzor és a gyorsítótár fő erőforrásait.
A tömörített adattárolás megbízhatósága
Ahogy az adattömörítést használó szoftverek (archiválók) teljes osztályának neve is sugallja, hosszú távú információtárolásra készültek, nem évekre, hanem évszázadokra, évezredekre...
Tárolás közben az adathordozók elveszítenek néhány adatot, íme egy példa:
Ez az „analóg” információhordozó ezer éves, néhány töredéke elveszett, de általában az információ „olvasható”...
A modern digitális adattároló rendszerek és a számukra digitális adathordozók felelős gyártói közül senki sem vállal garanciát a teljes adatbiztonságra több mint 75 évre.
És ez probléma, de elodázott probléma, utódaink megoldják...
A digitális adattároló rendszerek nem csak 75 év elteltével veszíthetnek adatot, az adatokban hibák bármikor, akár rögzítésük során is megjelenhetnek, ezeket a torzulásokat redundancia alkalmazásával, hibajavító rendszerekkel korrigálva igyekeznek minimalizálni. A redundancia- és korrekciós rendszerek nem mindig tudják visszaállítani az elveszett információkat, és ha igen, akkor nincs garancia arra, hogy a helyreállítási műveletet megfelelően végezték el.
És ez is nagy probléma, de nem halasztott, hanem aktuális.
A digitális adatok archiválására használt modern tömörítők a szótármódszer különféle módosításaira épülnek, és az ilyen archívumok számára egy információ elvesztése végzetes esemény lesz; még egy ilyen helyzetre is létezik egy bevett kifejezés - „törött” archívum. ...
Az archívumokban való, szótári tömörítéssel történő információtárolás alacsony megbízhatósága a tömörített adatok szerkezetével függ össze. Az ilyen archívumban lévő információk nem tartalmazzák a forrásszöveget, ott tárolódnak a szótárban szereplő bejegyzések száma, és magát a szótárt dinamikusan módosítja az aktuális tömörített szöveg. Ha egy archív töredék elveszett vagy megsérül, az összes későbbi archív bejegyzés sem a szótárban szereplő szócikk tartalma, sem hossza alapján nem azonosítható, mivel nem világos, hogy a szótári bejegyzés száma minek felel meg.
Egy ilyen „törött” archívumból lehetetlen visszaállítani az információkat.
Az RTT algoritmus a tömörített adatok tárolásának megbízhatóbb módszerén alapul. Az index módszert használja az ismétlődő töredékek elszámolására. A tömörítésnek ez a megközelítése lehetővé teszi az adathordozón lévő információtorzulás következményeinek minimalizálását, és sok esetben automatikusan kijavítja az információtárolás során keletkezett torzulásokat.
Ez annak köszönhető, hogy az archív fájl indextömörítés esetén két mezőt tartalmaz:
- egy forrásszöveg mező, amelyből eltávolították az ismétlődő szakaszokat;
- index mező.
Az információ-helyreállítás szempontjából kritikus indexmező nem nagy méretű, és a megbízható adattárolás érdekében sokszorosítható. Ezért még akkor is, ha a forrásszöveg vagy indextömb egy töredéke elvész, minden más információ probléma nélkül visszaáll, mint a képen egy „analóg” adathordozóval.
Az algoritmus hátrányai
Nincsenek előnyök hátrányok nélkül. Az indextömörítési módszer nem tömöríti a rövid ismétlődő sorozatokat. Ez az index módszer korlátaiból adódik. Az indexek legalább 3 bájt méretűek, és legfeljebb 12 bájt méretűek lehetnek. Ha az azt leíró indexnél kisebb méretű ismétlődést találunk, akkor azt nem veszik figyelembe, függetlenül attól, hogy milyen gyakran észlelnek ilyen ismétlődéseket a tömörített fájlban.
A hagyományos szótári tömörítési módszer hatékonyan tömöríti a többszörös rövid hosszúságú ismétléseket, és ezért nagyobb tömörítési arányt ér el, mint az indextömörítés. Igaz, ez a központi processzor nagy terhelése miatt valósul meg, ahhoz, hogy a szótár módszer az indexeljárásnál hatékonyabban kezdje el az adatokat tömöríteni, az adatfeldolgozási sebességet 10-20 megabájt/másodpercre kell csökkentenie valóson. számítástechnikai telepítések teljes CPU-terhelés mellett.
Az ilyen alacsony sebességek elfogadhatatlanok a modern adattároló rendszerek számára, és inkább „akadémiai” érdeklődésre tartanak számot, mint gyakorlatias.
Az információtömörítés mértéke jelentősen megnövekszik az RTT algoritmus következő, már fejlesztés alatt álló módosításában (RTT-Max).
Szóval, mint mindig, folytatás következik...
Forrás: will.com