Ten artykuł jest już drugim w temacie szybkiej kompresji danych. W pierwszym artykule opisano kompresor pracujący z szybkością 10 GB/s. na rdzeń procesora (minimalna kompresja, RTT-Min).
Kompresor ten został już zaimplementowany w sprzęcie powielaczy kryminalistycznych w celu szybkiej kompresji zrzutów nośników danych i zwiększenia siły kryptografii; może być również używany do kompresji obrazów maszyn wirtualnych i plików wymiany pamięci RAM podczas zapisywania ich na szybkich nośnikach danych Dyski SSD.
W pierwszym artykule zapowiedziano także opracowanie algorytmu kompresji służącego do kompresji kopii zapasowych dysków HDD i SSD (kompresja średnia, RTT-Mid) o znacznie ulepszonych parametrach kompresji danych. W tej chwili ten kompresor jest całkowicie gotowy i ten artykuł jest o tym.
Kompresor realizujący algorytm RTT-Mid zapewnia stopień kompresji porównywalny ze standardowymi archiwizatorami typu WinRar, 7-Zip, pracującymi w trybie high-speed. Jednocześnie jego prędkość robocza jest co najmniej o rząd wielkości wyższa.
Szybkość pakowania/rozpakowania danych jest krytycznym parametrem determinującym zakres zastosowania technologii kompresji. Jest mało prawdopodobne, aby komukolwiek przyszło do głowy kompresować terabajt danych z prędkością 10-15 megabajtów na sekundę (jest to dokładnie prędkość archiwizatorów w standardowym trybie kompresji), ponieważ przy pełnym obciążeniu procesora zajęłoby to prawie dwadzieścia godzin. .
Z drugiej strony ten sam terabajt można skopiować z szybkością 2-3 gigabajtów na sekundę w około dziesięć minut.
Dlatego też kompresja informacji o dużej objętości jest istotna, jeśli odbywa się ona z szybkością nie mniejszą niż prędkość rzeczywistego wejścia/wyjścia. W nowoczesnych systemach jest to co najmniej 100 megabajtów na sekundę.
Nowoczesne sprężarki mogą wytwarzać takie prędkości tylko w trybie „szybkim”. To właśnie w tym bieżącym trybie porównamy algorytm RTT-Mid z tradycyjnymi kompresorami.
Testy porównawcze nowego algorytmu kompresji
Kompresor RTT-Mid pracował w ramach programu testowego. W prawdziwie „działającej” aplikacji działa znacznie szybciej, mądrze wykorzystuje wielowątkowość i używa „normalnego” kompilatora, a nie C#.
Ponieważ kompresory użyte w teście porównawczym są zbudowane na różnych zasadach i różne typy danych kompresują się w różny sposób, dla obiektywności testu zastosowano metodę pomiaru „średniej temperatury w szpitalu”…
Utworzono plik zrzutu sektor po sektorze dysku logicznego z systemem operacyjnym Windows 10; jest to najbardziej naturalna mieszanina różnych struktur danych dostępnych obecnie na każdym komputerze. Skompresowanie tego pliku umożliwi porównanie szybkości i stopnia kompresji nowego algorytmu z najbardziej zaawansowanymi kompresorami stosowanymi we współczesnych archiwizatorach.
Oto plik zrzutu:
Plik zrzutu został skompresowany przy użyciu kompresorów PTT-Mid, 7-zip i WinRar. Kompresor WinRar i 7-zip został ustawiony na maksymalną prędkość.
Sprężarka działa 7-zip:
Obciąża procesor w 100%, natomiast średnia prędkość odczytu oryginalnego zrzutu wynosi około 60 Megabajtów/s.
Sprężarka działa WinRAR:
Sytuacja jest podobna, obciążenie procesora wynosi prawie 100%, średnia prędkość odczytu zrzutu wynosi około 125 Megabajtów/s.
Podobnie jak w poprzednim przypadku, prędkość archiwizatora jest ograniczona możliwościami procesora.
Program testu sprężarki jest teraz uruchomiony RTT — środek:
Na zrzucie ekranu widać, że procesor jest obciążony w 50%, a przez resztę czasu pozostaje bezczynny, ponieważ nie ma gdzie wgrać skompresowanych danych. Dysk do przesyłania danych (dysk 0) jest prawie w pełni załadowany. Szybkość odczytu danych (dysk 1) jest bardzo zróżnicowana, ale średnio przekracza 200 megabajtów/s.
Szybkość kompresora jest w tym przypadku ograniczona możliwością zapisu skompresowanych danych na Dysku 0.
Teraz stopień kompresji powstałych archiwów:
Można zauważyć, że kompresor RTT-Mid najlepiej poradził sobie z kompresją; utworzone przez niego archiwum było o 1,3 gigabajta mniejsze niż archiwum WinRar i 2,1 gigabajta mniejsze niż archiwum 7z.
Czas spędzony na tworzeniu archiwum:
- 7-zip – 26 minut 10 sekund;
- WinRar – 17 minut 40 sekund;
- RTT-Mid – 7 minut 30 sekund.
Tym samym nawet testowy, niezoptymalizowany program, korzystający z algorytmu RTT-Mid, był w stanie utworzyć archiwum ponad dwa i pół razy szybciej, a archiwum okazało się znacznie mniejsze niż u konkurencji...
Ci, którzy nie wierzą zrzutom ekranu, mogą sami sprawdzić ich autentyczność. Program testowy dostępny jest pod adresem , pobierz i sprawdź.
Ale tylko na procesorach z obsługą AVX-2, bez obsługi tych instrukcji kompresor nie działa i nie testuj algorytmu na starszych procesorach AMD, są one powolne w wykonywaniu instrukcji AVX...
Zastosowana metoda kompresji
Algorytm wykorzystuje metodę indeksowania powtarzających się fragmentów tekstu z dokładnością bajtową. Ta metoda kompresji była znana od dawna, jednak nie była stosowana, ponieważ operacja dopasowywania była bardzo kosztowna pod względem niezbędnych zasobów i wymagała znacznie więcej czasu niż budowanie słownika. Zatem algorytm RTT-Mid jest klasycznym przykładem przeniesienia się „powrotem do przyszłości”…
Kompresor PTT wykorzystuje unikalny, szybki skaner wyszukiwania dopasowań, który pozwala przyspieszyć proces kompresji. Skaner własnej roboty, to jest „mój urok…”, „jest dość drogi, bo w całości wykonany ręcznie” (napisany w asemblerze).
Skaner wyszukiwania dopasowań tworzony jest według dwupoziomowego schematu probabilistycznego: w pierwszej kolejności skanowana jest obecność „znaku” dopasowania, a dopiero po zidentyfikowaniu „znaku” w tym miejscu procedura wykrywania prawdziwego dopasowania jest rozpoczęty.
Okno wyszukiwania dopasowań ma nieprzewidywalny rozmiar, zależny od stopnia entropii w przetwarzanym bloku danych. Dla danych całkowicie losowych (nieściśliwych) ma on rozmiar megabajtów, dla danych z powtórzeniami jest zawsze większy niż megabajt.
Jednak wiele nowoczesnych formatów danych jest niekompresowalnych, a uruchamianie przez nie skanera wymagającego dużych zasobów jest bezużyteczne i marnotrawione, dlatego skaner wykorzystuje dwa tryby pracy. W pierwszej kolejności przeszukiwane są fragmenty tekstu źródłowego z możliwymi powtórzeniami, operacja ta również odbywa się metodą probabilistyczną i jest wykonywana bardzo szybko (z szybkością 4-6 Gigabajtów/s). Obszary z możliwymi dopasowaniami są następnie przetwarzane przez główny skaner.
Kompresja indeksów nie jest zbyt wydajna, trzeba zastąpić zduplikowane fragmenty indeksami, a tablica indeksów znacznie zmniejsza 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 ciąg zawiera dopasowane i niedopasowane bajty. Aby to zrobić, format indeksu zawiera pole maski dopasowania, które wskazuje pasujące bajty dwóch bloków. Aby uzyskać jeszcze większą kompresję, stosuje się indeksowanie w celu nałożenia kilku częściowo pasujących bloków na bieżący blok.
Wszystko to pozwoliło uzyskać w kompresorze PTT-Mid stopień kompresji porównywalny z kompresorami wykonanymi metodą słownikową, ale pracującymi znacznie szybciej.
Szybkość nowego algorytmu kompresji
Jeżeli kompresor wykorzystuje wyłącznie pamięć podręczną (wymagane są 4 megabajty na wątek), wówczas prędkość robocza mieści się w zakresie 700-2000 megabajtów/s. na rdzeń procesora, w zależności od rodzaju kompresowanych danych i w niewielkim stopniu zależy od częstotliwości roboczej procesora.
W przypadku wielowątkowej implementacji kompresora efektywna skalowalność zależy od rozmiaru pamięci podręcznej trzeciego poziomu. Na przykład, mając „na pokładzie” 9 megabajtów pamięci podręcznej, nie ma sensu uruchamiać więcej niż dwóch wątków kompresji, prędkość nie wzrośnie z tego powodu. Ale przy pamięci podręcznej wynoszącej 20 megabajtów możesz już uruchomić pięć wątków kompresji.
Również opóźnienie pamięci RAM staje się ważnym parametrem określającym prędkość kompresora. Algorytm korzysta z losowego dostępu do OP, z czego część nie trafia do pamięci podręcznej (około 10%) i musi czekać na dane z OP, co zmniejsza szybkość działania.
Znacząco wpływa na prędkość kompresora i pracę układu wejścia/wyjścia danych. Żądania do OP z we/wy blokują żądania danych z procesora, co również zmniejsza prędkość kompresji. Problem ten jest istotny w przypadku laptopów i komputerów stacjonarnych, w przypadku serwerów jest mniej istotny ze względu na bardziej zaawansowaną jednostkę kontroli dostępu do magistrali systemowej i wielokanałową pamięć RAM.
W całym tekście artykułu mówimy o kompresji; dekompresja pozostaje poza zakresem tego artykułu, ponieważ „wszystko jest pokryte czekoladą”. Dekompresja jest znacznie szybsza i jest ograniczona szybkością operacji we/wy. Jeden rdzeń fizyczny w jednym wątku z łatwością zapewnia prędkość rozpakowywania 3-4 GB/s.
Wynika to z braku operacji wyszukiwania dopasowań podczas procesu dekompresji, która „pożera” główne zasoby procesora i pamięci podręcznej podczas kompresji.
Niezawodność przechowywania skompresowanych danych
Jak sugeruje nazwa całej klasy oprogramowania wykorzystującego kompresję danych (archiwizatory), są one przeznaczone do długotrwałego przechowywania informacji, nie przez lata, ale przez stulecia i tysiąclecia...
Podczas przechowywania nośniki pamięci tracą część danych, oto przykład:
Ten „analogowy” nośnik informacji ma tysiąc lat, niektóre fragmenty zaginęły, ale ogólnie informacja jest „czytelna”…
Żaden z odpowiedzialnych producentów nowoczesnych cyfrowych systemów przechowywania danych i nośników cyfrowych dla nich nie daje gwarancji pełnego bezpieczeństwa danych przez okres dłuższy niż 75 lat.
I to jest problem, ale problem odłożony na później, nasi potomkowie go rozwiążą...
Cyfrowe systemy przechowywania danych potrafią utracić dane nie tylko po 75 latach, błędy w danych mogą pojawić się w każdej chwili, nawet podczas ich zapisu, starają się minimalizować te zniekształcenia stosując redundancję i korygując je systemami korekcji błędów. Systemy redundancji i korekcji nie zawsze są w stanie przywrócić utracone informacje, a jeśli tak się stanie, nie ma gwarancji, że operacja przywracania została wykonana prawidłowo.
I to też jest duży problem, ale nie odroczony, tylko aktualny.
Nowoczesne kompresory służące do archiwizacji danych cyfrowych budowane są w oparciu o różne modyfikacje metody słownikowej i dla takich archiwów utrata fragmentu informacji będzie wydarzeniem fatalnym, istnieje nawet ustalone określenie takiej sytuacji – „zepsute” archiwum ...
Niska niezawodność przechowywania informacji w archiwach z kompresją słownikową jest związana ze strukturą skompresowanych danych. Informacje w takim archiwum nie zawierają tekstu źródłowego, przechowywane są w nim numery haseł słownika, a sam słownik jest dynamicznie modyfikowany o bieżący skompresowany tekst. Jeżeli fragment archiwum zaginie lub zostanie uszkodzony, wszystkie kolejne wpisy archiwalne nie będą mogły zostać zidentyfikowane ani na podstawie treści, ani długości hasła w słowniku, ponieważ nie jest jasne, któremu odpowiada numer hasła w słowniku.
Nie ma możliwości przywrócenia informacji z tak „zepsutego” archiwum.
Algorytm RTT opiera się na bardziej niezawodnej metodzie przechowywania skompresowanych danych. Wykorzystuje metodę indeksową do rozliczania powtarzających się fragmentów. Takie podejście do kompresji pozwala zminimalizować skutki zniekształcenia informacji na nośniku, a w wielu przypadkach automatycznie skorygować zniekształcenia powstałe podczas przechowywania informacji.
Wynika to z faktu, że plik archiwum w przypadku kompresji indeksu zawiera dwa pola:
- pole tekstu źródłowego z usuniętymi powtarzającymi się sekcjami;
- pole indeksowe.
Pole indeksu, które ma kluczowe znaczenie dla odzyskiwania informacji, nie jest duże i można je powielić w celu niezawodnego przechowywania danych. Dlatego nawet w przypadku utraty fragmentu tekstu źródłowego lub tablicy indeksowej wszystkie pozostałe informacje zostaną przywrócone bez problemów, jak na zdjęciu z „analogowym” nośnikiem danych.
Wady algorytmu
Nie ma zalet bez wad. Metoda kompresji indeksu nie kompresuje krótkich, powtarzających się sekwencji. Wynika to z ograniczeń metody indeksowej. Indeksy mają rozmiar co najmniej 3 bajtów i mogą mieć rozmiar do 12 bajtów. Jeżeli napotkane zostanie powtórzenie o rozmiarze mniejszym niż indeks je opisujący, to nie jest ono brane pod uwagę, niezależnie od tego, jak często takie powtórzenia wykrywane są w skompresowanym pliku.
Tradycyjna metoda kompresji słownikowej skutecznie kompresuje wielokrotne powtórzenia o małej długości i dlatego osiąga wyższy współczynnik kompresji niż kompresja indeksowa. To prawda, że osiąga się to ze względu na duże obciążenie centralnego procesora; aby metoda słownikowa zaczęła kompresować dane wydajniej niż metoda indeksowa, musi zmniejszyć prędkość przetwarzania danych do 10-20 megabajtów na sekundę w rzeczywistości instalacje obliczeniowe przy pełnym obciążeniu procesora.
Tak niskie prędkości są nie do zaakceptowania w przypadku nowoczesnych systemów przechowywania danych i mają raczej charakter „naukowy” niż praktyczny.
Stopień kompresji informacji zostanie znacznie zwiększony w kolejnej modyfikacji algorytmu RTT (RTT-Max), która jest już w fazie rozwoju.
Zatem jak zwykle ciąg dalszy...
Źródło: www.habr.com