Ten artykuł jest drugą częścią cyklu dotyczącego szybkiej kompresji danych. W pierwszym artykule opisano kompresor działający z prędkością 10 GB/s na jedno rdzenie procesora (minimalna kompresja, RTT-Min).
Ten kompresor został już wdrożony w sprzęcie kryminalistycznych duplikatorów do szybkiej kompresji zrzutów informacji oraz wzmacniania odporności kryptografii. Może również być używany do kompresji obrazów maszyn wirtualnych i plików swap pamięci operacyjnej przy ich zapisywaniu na szybkich dyskach SSD.
W pierwszym artykule zapowiedziano również opracowanie algorytmu kompresji do kompresji kopii zapasowych dysków HDD i SSD (średnia kompresja, RTT-Mid) z niezwykle ulepszonymi parametrami kompresji danych. Do tej pory ten kompresor jest w pełni gotowy i ten artykuł dotyczy właśnie jego.
Kompresor realizujący algorytm RTT-Mid zapewnia stopień kompresji porównywalny ze standardowymi archiwizatorami, takimi jak WinRar czy 7-Zip, działającymi w trybie szybkiej kompresji. Przy tym jego prędkość działania jest co najmniej o rząd wyższa.
Szybkość pakowania/rozpakowywania danych jest krytycznym parametrem określającym obszar zastosowania technologii kompresji. Mało kto pomyślałby o kompresji terabajta danych z prędkością 10-15 MB na sekundę (taka właśnie prędkość archiwizatorów w standardowym trybie kompresji), ponieważ zajmie to prawie dwadzieścia godzin przy pełnym obciążeniu procesora...
Z drugiej strony ten sam terabajt można skopiować z prędkością rzędu 2-3 GB na sekundę w ciągu około dziesięciu minut.
Dlatego kompresja dużych ilości danych jest istotna, jeśli odbywa się z prędkością nie mniejszą niż rzeczywista prędkość wejścia/wyjścia. Dla nowoczesnych systemów oznacza to co najmniej 100 MB na sekundę.
Takie prędkości nowoczesne kompresory mogą osiągnąć tylko w trybie 'fast'. I właśnie w tym aktualnym trybie będziemy porównywać algorytm RTT-Mid z tradycyjnymi kompresorami.
Porównawcze testowanie nowego algorytmu kompresji
Kompresor RTT-Mid działał w ramach programu testowego. W rzeczywistej 'roboczej' aplikacji działa znacznie szybciej, gdzie zyskuje się na wielowątkowości i wykorzystuje 'normalny' kompilator, a nie C#.
Ponieważ używane w teście porównawczym kompresory działają na różnych zasadach, a różne typy danychCompressują różnie, do obiektywności testu zastosowano metodę pomiaru „średniej temperatury w szpitalu”...
Stworzono plik sekcyjnego zrzutu logicznego dysku z systemem operacyjnym Windows 10, jest to najbardziej naturalna mieszanka różnych struktur danych, które można znaleźć na każdym komputerze. Kompresja tego pliku pozwoli porównać szybkość i stopień kompresji nowego algorytmu z najbardziej zaawansowanymi kompresorami używanymi w nowoczesnych archiwizatorach.
Oto ten plik zrzutu:
Plik zrzutu był kompresowany przez kompresory RTT-Mid, 7-zip, WinRar. Kompresor WinRar i 7-zip zostały ustawione na maksymalną prędkość pracy.
Kompresor działa 7-zip:
Obciąża procesor na 100%, podczas gdy średnia prędkość odczytu oryginalnego zrzutu wynosi około 60 MegaBajtów/s.
Kompresor działa WinRar:
Sytuacja analogiczna, obciążenie procesora prawie 100%, średnia prędkość odczytu zrzutu wynosi około 125 MegaBajtów/s.
Jak w poprzednim przypadku, szybkość pracy archiwizatora jest ograniczona przez możliwości procesora.
Teraz działa program testowy kompresora RTT-Mid:
Zrzut ekranu pokazuje, że procesor jest obciążony w 50% i resztę czasu jest bezczynny, ponieważ nie ma możliwości zrzutu skompresowanych danych. Dysk zrzutu danych (Dysk 0) jest prawie w pełni obciążony. Szybkość odczytu danych (Dysk 1) waha się, ale średnio wynosi ponad 200 MegaBajtów/s.
Szybkość pracy kompresora jest w tym przypadku ograniczana przez możliwości zapisu skompresowanych danych na Dysku 0.
Teraz stopień kompresji otrzymanych archiwów:
Widać, że kompresor RTT-Mid poradził sobie najlepiej z kompresją, archiwum stworzone przez niego jest o 1,3 GigaBajta mniejsze od archiwum WinRar i o 2,1 GigaBajta mniejsze od archiwum 7z.
Czas poświęcony na utworzenie archiwum:
- 7-zip – 26 minut 10 sekund;
- WinRar – 17 minut 40 sekund;
- RTT-Mid – 7 minut 30 sekund.
Tak więc, nawet testowy, nieoptymalizowany program, wykorzystując algorytm RTT-Mid, mógł stworzyć archiwum ponad dwa i pół razy szybciej, a archiwum okazało się znacznie mniejsze niż u konkurencji…
Ci, którzy nie wierzą w zrzuty ekranu, mogą sami sprawdzić ich wiarygodność. Program testowy jest dostępny pod , pobieraj i sprawdzaj.
Jednak tylko na procesorach z obsługą AVX-2, bez wsparcia dla tych instrukcji kompresor nie działa, i nie testuj algorytmu na starych procesorach AMD, są wolne w zakresie wykonywania komend AVX...
Używana metoda kompresji
W algorytmie stosuje się metodę indeksowania powtarzających się fragmentów tekstu w granicach bajtowych. Taka metoda kompresji jest znana od dawna, ale nie była wcześniej stosowana, ponieważ operacja wyszukiwania dopasowań była bardzo kosztowna pod względem wymaganych zasobów i zajmowała znacznie więcej czasu niż budowanie słownika. Tak więc algorytm RTT-Mid jest klasycznym przykładem ruchu "wstecz w przyszłość"...
W kompresorze RTT zastosowano unikalny szybki skaner wyszukiwania dopasowań, to właśnie on pozwolił przyspieszyć proces kompresji. Skaner własnej produkcji, to "moja świeczka...", "cena nie jest mała, ponieważ jest to w pełni ręczna robota" (napisany w asemblerze).
Skaner wyszukiwania dopasowań jest oparty na dwupoziomowej prawdopodobieństwowej strukturze, najpierw skanowane jest wystąpienie "znaku" dopasowania, a dopiero po zidentyfikowaniu "znaku" w tym miejscu uruchamiana jest procedura wykrywania rzeczywistego dopasowania.
Okno wyszukiwania dopasowań ma nieprzewidywalny rozmiar, zależny od poziomu entropii w przetwarzanym bloku danych. Dla całkowicie losowych (niekompresowalnych) danych ma rozmiar megabajtu, dla danych zawierających powtórzenia zawsze ma rozmiar większy niż megabajt.
Jednak wiele nowoczesnych formatów danych nie da się skompresować i "przesuwanie" po nich zasobożernym skanerem jest bezsensowne i marnotrawne, dlatego w skanerze stosuje się dwa tryby pracy. Najpierw wyszukiwane są fragmenty oryginalnego tekstu z możliwymi powtórzeniami, ta operacja również przeprowadzana jest metodą probabilistyczną i wykonywana jest bardzo szybko (z prędkością 4-6 Gigabajtów/s). Następnie fragmenty z możliwymi dopasowaniami są przetwarzane przez główny skaner.
Kompresja indeksowa nie jest zbyt efektywna, trzeba zastępować powtarzające się fragmenty indeksami, a tablica indeksów znacznie obniża współczynnik kompresji.
Aby zwiększyć stopień kompresji, indeksowane są nie tylko pełne dopasowania ciągów bajtów, ale także częściowe, gdy w ciągu znajdują się dopasowane i niedopasowane bajty. W tym celu do formatu indeksu włączono pole maski dopasowań, które wskazuje na dopasowane bajty dwóch bloków. Dla jeszcze większej kompresji stosuje się indeksowanie z nakładaniem kilku częściowo dopasowanych bloków na aktualny blok.
Wszystko to pozwoliło uzyskać w kompresorze RTT-Mid stopień kompresji porównywalny z kompresorami działającymi w oparciu o metodę słownikową, ale działającym znacznie szybciej.
Prędkość działania nowego algorytmu kompresji
Jeśli kompresor pracuje przy monopolnym wykorzystaniu pamięci podręcznej (na jeden wątek wymaga 4 MB), to prędkość pracy waha się w zakresie 700-2000 MB/s na jedno rdzeń procesora, w zależności od rodzaju kompresowanych danych i nieznacznie od częstotliwości pracy procesora.
W przypadku wielowątkowej realizacji kompresora efektywna skalowalność jest określana przez objętość pamięci podręcznej trzeciego poziomu. Na przykład, mając „na pokładzie” 9 MB pamięci podręcznej, uruchamianie więcej niż dwóch wątków kompresji nie ma sensu, ponieważ prędkość od tego nie wzrośnie. Ale przy pamięci podręcznej o pojemności 20 MB można już uruchamiać pięć wątków kompresji.
Istotnym parametrem wpływającym na prędkość działania kompresora jest również latencja pamięci RAM. Algorytm wykorzystuje losowe odwołania do RAM, z których część nie trafia do pamięci podręcznej (około 10%) i musi czekać na dane z RAM, co obniża prędkość pracy.
Na prędkość kompresora znacząco wpływa również praca systemu wejścia/wyjścia danych. Żądania do RAM od wejścia/wyjścia blokują dostęp do danych ze strony CPU, co również obniża prędkość kompresji. Problem ten jest znaczący dla laptopów i komputerów stacjonarnych, serwerów jest mniej istotny dzięki bardziej zaawansowanemu blokowi zarządzania dostępem do magistrali systemowej i pamięci RAM wielokanałowej.
W całym tekście artykułu mowa jest o kompresji, dekompresja nie jest poruszana, ponieważ tam „wszystko jest w porządku”. Dekompresja przebiega znacznie szybciej i ogranicza się do prędkości wejścia/wyjścia. Jedno fizyczne rdzeń w jednym wątku swobodnie zapewnia prędkości rozpakowywania na poziomie 3-4 gigabajty/sek.
Jest to związane z brakiem w procesie rozpakowywania operacji wyszukiwania dopasowań, która „zabiera” główne zasoby procesora i pamięci podręcznej podczas kompresji.
Niezawodność przechowywania skompresowanych danych
Jak wynika z nazwy całej klasy oprogramowania wykorzystującego kompresję danych (archiwizatory), są one przeznaczone do długoterminowego przechowywania informacji, nie na lata, ale na wieki i tysiąclecia...
W trakcie przechowywania nośniki informacji tracą część danych, oto przykład:
Temu „analogowemu” nośnikowi informacji jest tysiąc lat, niektóre fragmenty są utracone, ale ogólnie informacja jest „czytelna”…
Żaden z odpowiedzialnych producentów nowoczesnych cyfrowych systemów przechowywania danych oraz cyfrowych nośników do nich nie daje gwarancji pełnej trwałości danych na więcej niż 75 lat.
I to jest problem, ale problem odłożony, jego rozwiązaniem zajmą się nasi następcy...
Systemy przechowywania danych cyfrowych mogą tracić dane nie tylko po 75 latach, błędy w danych mogą pojawić się w każdej chwili, nawet podczas ich zapisu, te zniekształcenia starają się zminimalizować, stosując nadmiarowość i poprawiając dzięki systemom korekcji błędów. Nadmiarowość i systemy korekcji mogą przywrócić utraconą informację nie zawsze, a jeśli już przywracają, to nie ma gwarancji, że operacja przywracania przebiegła poprawnie.
I to też jest duży problem, ale nie odłożony, a bieżący.
Nowoczesne kompresory używane do archiwizacji danych cyfrowych opierają się na różnych modyfikacjach metody słownikowej i w przypadku takich archiwów utrata fragmentu informacji będzie wydarzeniem katastroficznym, istnieje nawet ustalony termin dla takiej sytuacji - „zepsute” archiwum…
Niska niezawodność przechowywania informacji w archiwach z kompresją słownikową jest związana z strukturą skompresowanych danych. Informacja w takim archiwum nie zawiera oryginalnego tekstu, przechowywane są numery rekordów w słowniku, a sam słownik jest dynamicznie modyfikowany przez aktualnie kompresowany tekst. W przypadku utraty lub uszkodzenia fragmentu archiwum, wszystkie subsequent records in the archive cannot be identified either by content or by length in the dictionary, since it is unclear what the dictionary entry number corresponds to.
Odzyskanie informacji z takiego "zepsutego" archiwum jest niemożliwe.
Algorytm RTT oparty jest na bardziej niezawodnej metodzie przechowywania skompresowanych danych. Wykorzystuje on indeksową metodę śledzenia powtarzających się fragmentów. Takie podejście do kompresji minimalizuje skutki zniekształcenia informacji na nośniku i w wielu przypadkach automatycznie koryguje zniekształcenia, które powstały podczas przechowywania informacji.
Jest to związane z tym, że plik archiwum w przypadku kompresji indeksowej zawiera dwa pola:
- pole oryginalnego tekstu z usuniętymi fragmentami powtarzania;
- pole indeksów.
Krytycznie ważne dla odzyskiwania informacji pole indeksów, nie jest duże pod względem rozmiaru i można je zduplikować dla niezawodności przechowywania danych. Dlatego nawet jeśli fragment oryginalnego tekstu lub tablica indeksów zostanie utracona, cała pozostała informacja będzie mogła być odzyskiwana bez problemów, jak na obrazku z "analogowym" nośnikiem informacji.
Wady algorytmu
Zalety nie istnieją bez wad. Indeksowa metoda kompresji nie kompresuje powtarzających się sekwencji małej długości. Jest to związane z ograniczeniami metody indeksowej. Indeksy mają rozmiar nie mniejszy niż 3 bajty i mogą mieć rozmiar do 12 bajtów. Jeśli występuje powtórzenie o mniejszym rozmiarze niż opisujący je indeks, to nie jest brane pod uwagę, niezależnie od tego, jak często takie powtórzenia występują w kompresowanym pliku.
Tradycyjna metodą kompresji oparta na słowniku skutecznie kompresuje wielokrotne powtórzenia małej długości, osiągając większy współczynnik kompresji niż kompresja indeksowa. Niestety, jest to uzyskiwane kosztem wysokiego obciążenia procesora centralnego; aby metoda słownikowa mogła efektywniej kompresować dane w porównaniu do metody indeksowej, musi obniżyć szybkość przetwarzania danych do 10-20 megabajtów na sekundę w rzeczywistych instalacjach obliczeniowych przy pełnym obciążeniu CPU.
Tak niskie prędkości są nieakceptowalne dla nowoczesnych systemów przechowywania danych i mają większe zainteresowanie «akademickie» niż praktyczne.
Stopień kompresji informacji zostanie znacznie zwiększony w następnej modyfikacji algorytmu RTT (RTT-Max), który jest już w fazie rozwoju.
Tak więc, jak zawsze, ciąg dalszy nastąpi…
Źródło: habr.com
