Kompresja Baz Danych

Rozmiar danych i potrzeby baz danych

Systemy informatyczne przechowują dane z zakupów, mediów społecznościowych, badań i transakcji finansowych. Wraz ze wzrostem zbiorów od megabajtów do gigabajtów, terabajtów i petabajtów rośnie koszt ich obsługi. Narzędziem do zarządzania danymi ustrukturyzowanymi jest baza danych. Silnik musi jednocześnie utrzymać struktury indeksów, metadane i bufor stron. Kompresja dotyczy więc wybranych danych, a jej zysk zależy od warstwy, w której zostanie zastosowana.

Baza danych przechowuje rekordy i udostępnia operacje wyszukiwania, modyfikacji oraz analizy. Przy dużych wolumenach pojawiają się trzy powtarzające się wyzwania:

• Koszt przechowywania: Każdy bajt zajmuje miejsce na urządzeniu fizycznym, takim jak dysk twardy (HDD) albo SSD. W dużej instalacji koszt zakupu, zasilania, chłodzenia i utrzymania wielu urządzeń obciąża budżet operacyjny.
• Ograniczenia I/O: Zapytanie może wymagać odczytu danych z pamięci masowej do RAM. Wąskie gardło I/O zwiększa się wraz z ilością danych do odczytania, co może wydłużać odpowiedź.
• Kopie zapasowe i konserwacja: Kopiowanie wieloterabajtowej bazy oraz operacje konserwacyjne mogą trwać wiele godzin. W tym czasie obciążenie systemu i dostępność usług zależą od zastosowanej procedury.

Jedną z metod ograniczenia tych kosztów jest kompresja bazy danych. Dane są zapisywane w zwartej reprezentacji, co zmniejsza zajętość pamięci masowej. Mniejsza liczba odczytywanych bajtów może skrócić zapytanie, jeśli koszt dekodowania pozostaje niższy od zaoszczędzonego I/O. Ten sam mechanizm może zmniejszyć rozmiar kopii zapasowej i zwiększyć liczbę rekordów mieszczących się w pamięci podręcznej. Wpływ trzeba sprawdzić dla odczytu, zapisu i aktualizacji.

Granica strony wpływa na narzut, statystyki oraz możliwość pomijania danych podczas odczytu.

Kiedy kompresja skraca odczyt danych

Kompresja dodaje pracę procesora, ponieważ dane trzeba rozpakować przed użyciem. Ten koszt nazywa się narzutem CPU. Całkowity czas zależy od relacji między tym kosztem a czasem odczytu pamięci masowej.

Procesor i pamięć masowa mają różne koszty czasowe. Odczyt bloku z urządzenia obejmuje opóźnienie i transfer, natomiast proste dekodowanie może wykorzystywać szybkie obliczenia CPU. Relacja zależy od urządzenia, obciążenia i algorytmu.

Jeśli zapytanie odczytuje 100 megabajtów danych, a współczynnik kompresji wynosi 4:1, strumień skompresowany ma 25 megabajtów. Dekoder odtwarza te 25 megabajtów podczas rekonstrukcji danych. Odczyt obejmuje wtedy o 75% mniej danych. Jeżeli czas dekodowania jest mały względem oszczędności I/O, całkowite wykonanie może się skrócić. Przy zapisie dochodzi koszt kompresji, a przy aktualizacjach znaczenie ma zakres danych, który trzeba ponownie zakodować. Pomiar powinien obejmować przepustowość, opóźnienie i zużycie CPU.

Przechowywanie wierszowe i kolumnowe

Techniki kompresji zależą od układu danych na dysku. W magazynie wierszowym wartości jednego rekordu są przechowywane razem, natomiast w magazynie kolumnowym wartości jednej kolumny tworzą osobny ciąg. Układ wpływa na lokalną powtarzalność i na dobór kodowania. Magazyn wierszowy ułatwia pobranie pełnego rekordu, a kolumnowy ogranicza odczyt do pól użytych w zapytaniu. W obu przypadkach dane są zwykle dzielone na strony, fragmenty albo grupy wierszy.

Bazy zorientowane na wiersze (row stores)

W magazynie wierszowym dane jednego rekordu są przechowywane razem w sposób ciągły. Poniższy przykład przedstawia tabelę pracowników:

Baza danych zorientowana na wiersze zapisałaby te dane na dysku w następujący sposób:[1, Jan, Kowalski, Sprzedaż], [2, Anna, Nowak, Marketing], ...

Zastosowanie: Wspólne przechowywanie wartości rekordu wspiera przetwarzanie transakcji online (OLTP). Gdy rekord mieści się na jednej stronie danych, odczyt tej strony pobiera razem jego pola potrzebne do odczytu lub aktualizacji rekordu. Wstawienie wiersza także umieszcza jego pola obok siebie, zachowując lokalność przy późniejszym dostępie.

Bazy zorientowane na kolumny (column stores)

W magazynie kolumnowym wartości jednej kolumny są przechowywane razem w sposób ciągły. Układ jest używany między innymi w hurtowniach danych i systemach analitycznych. Dla tej samej tabeli dane mogłyby wyglądać tak:

Zastosowanie: Układ wspiera analityczne przetwarzanie online (OLAP). Przy agregacji kilku kolumn z milionów wierszy można odczytać tylko kolumny potrzebne do zapytania, na przykład 'Dział' i 'Pensja', pomijając 'ID', 'Imię' i 'Nazwisko'. Zmniejsza to ilość danych przekazywanych z pamięci masowej.

Układ kolumnowy sprzyja kompresji, ponieważ wartości w jednej kolumnie mają ten sam typ i często powtarzają się w podobnych zakresach. Taki ciąg łatwiej modelować niż mieszaninę typów obecnych w pojedynczym wierszu. Format kolumnowy może najpierw zastosować kodowanie słownikowe, RLE albo delta, a następnie kompresor bajtowy dla całej strony. Kolejność tych etapów wpływa na wynik.

Techniki kompresji w bazach zorientowanych na wiersze

Magazyny wierszowe łączą różne typy danych w rekordzie, dlatego często stosują techniki ogólnego przeznaczenia.

Kompresja na poziomie strony

W wielu systemach OLTP dane są przenoszone w porcjach zwanych stronami danych. Kompresja strony obejmuje wiele wierszy przed zapisem. Przy odczycie strona jest pobierana w postaci skompresowanej i rozpakowywana w pamięci. Konkretne zachowanie zależy od silnika. Duże wartości tekstowe lub binarne mogą być w wybranych silnikach przechowywane poza główną stroną i kompresowane osobno. Trzeba wtedy uwzględnić dodatkowe odwołania do tych fragmentów.

Silnik może użyć szybkiego kodera ogólnego przeznaczenia, takiego jak zlib oparty na DEFLATE albo LZ4. Takie metody wyszukują powtarzające się sekwencje bajtów w obrębie strony.

Inne techniki wierszowe

• Kompresja zależna od typu: Silnik może uwzględnić zakres typu danych. Liczby całkowite i daty mogą zajmować mniej bajtów, jeśli wartości mieszczą się w mniejszym zakresie niż domyślna reprezentacja.
• Kompresja prefiksów: Niektóre indeksy tekstowe wykorzystują wspólny prefiks kolejnych wpisów. Dla adresów URL zaczynających się od $https://www.przyklad.pl/$ prefiks można przechować raz, a dla kolejnych wpisów zapisać różniące się sufiksy.

Techniki kompresji w bazach zorientowanych na kolumny

Magazyny kolumnowe mogą uzyskiwać wysoką redukcję, ponieważ kodują jednorodne ciągi osobno dla każdej kolumny. Wynik zależy od rozkładu wartości, sortowania i zastosowanego formatu. W praktycznych formatach kolumna jest dzielona na fragmenty, aby dekoder mógł odczytać wybrany zakres. Słownik może zostać odrzucony na rzecz kodowania prostego, gdy liczba różnych wartości jest zbyt duża.

Kodowanie słownikowe

Kodowanie słownikowe pasuje do kolumn o niskiej kardynalności. Dla wybranej strony lub fragmentu kolumny silnik tworzy słownik i przypisuje wartościom małe kody całkowitoliczbowe. Zamiast powtarzać długi tekst, na przykład "Stany Zjednoczone Ameryki", zapisuje kod, a słownik przechowuje raz w tym fragmencie. Liczba bitów kodu zależy od liczby wpisów, a kodowanie musi uwzględnić także rozmiar słownika i jego metadane.

Kodowanie długości serii (RLE)

RLE zastępuje ciąg identycznych wartości parą złożoną z wartości i liczby powtórzeń. Zamiast przechowywać [Sprzedaż, Sprzedaż, Sprzedaż, Sprzedaż, IT, IT], można zapisać [(Sprzedaż, 4), (IT, 2)]. Sortowanie według daty albo innego klucza zwiększa długość takich serii w danych kolumnowych.

Kodowanie delta

Kodowanie delta stosuje się do kolumn liczbowych o powolnych lub przewidywalnych zmianach, takich jak kolejne identyfikatory, znaczniki czasu i odczyty czujników. Zapis obejmuje wartość bazową oraz różnice od poprzedniego elementu. Sekwencję $1005, 1006, 1007$ można zapisać jako $1005, +1, +1$, a małe różnice poddać kolejnemu kodowaniu. Przy zmianie znaku delty trzeba użyć reprezentacji obsługującej liczby ujemne. Sortowanie według czasu często zwiększa korzyść, lecz wynik zależy od kolejności wierszy.

Pakowanie bitów

Stały typ danych może zajmować więcej miejsca niż wymaga zakres wartości. Typ 64-bitowej liczby całkowitej może przechowywać wartości, które nigdy nie przekroczą 100. Pakowanie bitów wykorzystuje minimalną liczbę bitów potrzebną do zapisu kodu. Łączy się je z kodowaniem słownikowym i delta, aby przechowywać małe kody oraz różnice. Dla zakresu od 0 do 100 potrzebnych jest 7 bitów na wartość, jeśli zapis obejmuje cały zakres. Metadane muszą przechować użyty rozmiar pola.

Połączenie tych technik może w sprzyjających danych dać współczynnik 10:1 albo wyższy. Wynik zależy od kardynalności, kolejności wartości i narzutu metadanych, dlatego należy traktować ten współczynnik jako wynik pomiaru zależny od danych. W praktycznym formacie kodowanie działa zwykle dla strony, fragmentu albo grupy wierszy. Odczyt może pominąć inne fragmenty, lecz każdy fragment przechowuje własny nagłówek i statystyki. Zbyt mała grupa zwiększa narzut, a zbyt duża utrudnia selektywny odczyt. Test powinien więc sprawdzać rozmiar całego zbioru oraz czas zapytania, odczyt wybranych kolumn, pracę CPU i wpływ na pamięć podręczną. W Parquet indeksy słownikowe mogą być kodowane hybrydą RLE i pakowania bitów, a przekroczenie rozmiaru słownika prowadzi do kodowania prostego. Wyniki trzeba rozdzielić dla odczytu pełnego i selektywnego.