Rsync i de-duplikacja podczas przesyłania kopii zapasowych

Rsync wspierając funkcję „Rolling” dla sumy kontrolnej – idzie krok dalej w stosunku do konwencjonalnego podejścia do przyrostowego tworzenia kopii zapasowych.

Problem

Wyobraź sobie, że masz dwa pliki A i B, chcesz zaktualizować plik B żeby był identyczny jak plik A. Oczywiście najprościej jest skopiować A na B.

Teraz wyobraź sobie, że oba pliki znajdują się na dwóch komputerach połączonych ze sobą bardzo wolnym łączem np. połączenie EDGE – 296 kbit/s. Jeżeli A jest duży, to skopiowanie A na B będzie długo trwało. Żeby przyspieszyć proces, przed wysłaniem można skompresować A, ale przeważnie jest to tylko współczynnik 2 do 4.

Załóżmy teraz, że A i B są bardzo podobne, być może obie wersje są wariacją tego samego oryginalnego pliku. Trzeba skorzystać z tego podobieństwa, aby naprawdę przyspieszyć kopiowanie. Popularną metodą jest wysyłanie jedynie różnic pomiędzy A i B, a następnie przy wykorzystaniu listy tych różnic odtworzyć plik.

Problem polega na tym, że zwykłe metody tworzące zestaw różnic pomiędzy dwoma plikami wymagają dostępu do obu plików. Co za tym idzie oba pliki muszą znajdować się na tym samym komputerze, jeżeli jednak tak nie jest to metody te nie mogą być wykorzystane (oczywiste jest też to, że gdy masz już oba pliki na tym samym komputerze to nie potrzebujesz listy różnic). Ten problem rozwiązuje rsync.

Algorytm rsync skutecznie oblicza, która część pliku źródłowego pasuje, do której części pliku docelowego. Pasujące części nie muszą być przesyłane przez łącze; jedyne co musi być wysłane, to odnośniki do pasujących części pliku docelowego. W całości muszą być przesłane tylko części pliku źródłowego, które nie pasują. Odbiorca może zrekonstruować plik źródłowy, za pomocą odnośników do części pasujących i w całości przesłanych części.

Dodatkowo, dane przesyłane do odbiorcy mogą zostać skompresowane w celu przyspieszenia całego procesu.

Algorytm rsync

Załóżmy, że mamy dwa komputery α i β. Komputer α ma dostęp do pliku A, a komputer β ma dostęp do pliku B, gdzie A i B są do siebie podobne. Pomiędzy komputerami α i β mamy wolne łącze.

Algorytm rsync składa się z następujących kroków:

1. β dzieli plik B na nie nachodzących na siebie bloki o stałej wielkości S bajtów. Ostatni blok może być mniejszy od S bajtów.
2. Dla każdego z bloków β przelicza dwie sumy kontrolne: słabą 32-bitową z funkcją „Rolling” (opisaną poniżej) i mocną 128-bitową „MD4”.
3. β wysyła obie sumy kontrolne do α.
4. α przeszukuje plik A w celu odnalezienia bloków o długości S bajtów (każde przesunięcie, nie tylko wielokrotność S), które mają identyczne sumy kontrolne (słabą i mocną) jak bloki pliku B. Robione jest to naraz, bardzo szybko, za pomocą specjalnej właściwości sumy kontrolnej opisanej poniżej.
5. α wysyła β sekwencje instrukcji do rekonstrukcji pliku A. Każda instrukcja  zawiera, albo odnośnik do bloku B, albo są to dosłowne dane. Dane są wysyłane tylko dla tych sekcji, które nie pasowały do żadnego z bloków B.

Rezultatem jest to, że  β ma idealną kopię pliku A, ale tylko kawałki A nie znalezione w B (plus bardzo niewielka ilość danych tj. sumy kontrolne i indeks bloków) zostały przesłane przez łącze. Algorytm wymaga tylko jednej tury na przekazanie wszystkich potrzebnych informacji co znacznie minimalizuje obciążenie łącza.

Najważniejsze szczegóły dotyczące algorytmu odnoszą się do sumy kontrolnej z funkcją “rolling” i do mechanizmu wyszukiwania, który pozwala na szybkie wyszukiwanie odpowiednich sum kontrolnych.

Suma kontrolna z funkcją “Rolling”

Słabsza suma kontrolna z funkcją „rolling”, która jest wykorzystywana w algorytmie rsync, ma właściwość umożliwiającą obliczenie jednocześnie sumy kontrolnej dla buforów X₂ .. X_n+1 i X₁ .. X_n oraz podaje wartości w bajtach dla X₁ oraz X_n+1.

Algorytm słabszej sumy kontrolnej, który wykorzystujemy został stworzony przez Marka Adlersa i nazywany jest sumą kontrolną adler-32. Nasza suma kontrolna zdefiniowana jest przez:

Dla uproszczenia zapisaliśmy to jako M = 2¹⁶.

Ważną właściwością tej sumy kontrolnej jest to, że kolejne wartości można obliczyć bardzo skutecznie za pomocą relacji powtarzalności.

Tak więc suma kontrolna może być obliczona dla bloków o długości S na wszystkich możliwych przesunięciach wewnątrz pliku, z nakładem bardzo małej ilości obliczeń w każdym punkcie ich wykonywania.

Pomimo swojej prostoty, ta suma kontrolna okazała się całkiem dobra na pierwszy poziom kontroli dopasowania dwóch bloków pliku. Sprawdziliśmy w praktyce, że prawdopodobieństwo tego, że bloki do siebie nie pasują mimo identycznej słabej sumy kontrolnej jest bardzo niska. Jest to bardzo ważne, ponieważ bardziej zasobożerna, mocniejsza suma kontrolna musi być obliczona dla każdego bloku, dla którego słabsza suma kontrolna pasuje.

Wyszukiwanie sumy kontrolnej

Gdy α otrzyma listę sum kontrolnych bloków pliku B, wtedy musi przeszukać A w celu odnalezienia bloków w tym bloków z przesunięciami, które mają identyczną wartość sumy kontrolnej jak dany blok B. Podstawowa strategia to przeliczanie 32-bitowych sum kontrolnych z funkcją rolling, dla bloku o długości S zaczynając kolejno od każdego następnego bajta pliku A. Dla każdej sumy kontrolnej przeszukujemy całą listę dopasowań. Aby to zrobić wykorzystujemy 3 poziomowy schemat wyszukiwania.

Pierwszy poziom wykorzystuje 16-bitową funkcję skrótu (hash) 32-bitowej sumy kontrolnej z funkcją rolling i 2¹⁶ wpis tabeli funkcji skrótu (hash). Lista wartości sumy kontrolnej (to znaczy, sumy kontrolne z bloków B) jest posortowana według 16-bitowej funkcji skrótu (hash) 32-bitowej sumy kontrolnej z funkcją rolling. Każdy wpis w tabeli funkcji skrótu wskazuje na pierwszy element z listy dla tej wartości funkcji skrótu lub zawiera wartość „null”, jeżeli żaden element z listy nie  odpowiada wartości funkcji skrótu.

Na każdym przesunięciu w pliku obliczane są: 32-bitowa suma kontrolna z funkcją rolling i jej 16-bitowa funkcja skrótu. Jeżeli wartość wpisu w tablicy funkcji skrótu dla tej wartości funkcji skrótu nie wynosi „null”, to wywoływany jest drugi poziom kontroli.

Drugi poziom kontroli obejmuje skanowanie posortowanej listy sumy kontrolnej począwszy od wpisu wskazanego przez wpis tabeli funkcji skrótu. Poszukując wpisu, którego 32-bitowa suma kontrolna z funkcją rolling odpowiada obecnej wartości. Skanowanie kończy się gdy napotka na niepasujący wpis 16-bitowej funkcji skrótu. Jeżeli wyszukiwanie powiedzie się to wywoływany jest trzeci poziom kontroli.

Trzeci poziom kontroli polega na obliczeniu mocnej sumy kontrolnej dla obecnego przesunięcia w pliku i porównania go z wartością w liście wpisów. Jeżeli obie wartości mocnych sum kontrolnych pasują do siebie, to zakładamy, że udało nam się znaleźć blok pliku A, który odpowiada blokowi pliku B. W rzeczywistości bloki mogą być różne, ale prawdopodobieństwo tego jest mikroskopijne i w praktyce jest to rozsądne założenie.

Kiedy zostanie odnalezione dopasowanie w A między obecnym przesunięciem pliku, wtedy na podstawie indeksu pasującego bloku w B, α wysyła β dane i informację o końcu poprzedniego dopasowania. Dane są wysłane natychmiast po odnalezieniu identycznego bloku, dzięki czemu pasmo nie jest obciążane.

Jeżeli nie znaleziono dopasowania w danym przesunięciu pliku to suma kontrolna z funkcją rolling jest aktualizowana do następnego przesunięcia i wyszukiwanie jest kontynuowane. Jeżeli dopasowanie jest odnalezione, wtedy wyszukiwanie jest ponownie uruchomiane pod koniec dopasowanego bloku. Strategia ta pozwala zmniejszyć ilość obliczeń dla przypadku, gdy dwa pliki są niemal identyczne. Ponadto, ułatwia to kodowanie indeksów bloku w locie gdy seria kolejnych bloków A pasuje do bloków B.

Wielozadaniowość

Powyższa sekcja opisała proces rekonstrukcji na zdalnym systemie kopi tylko jednego pliku. Jeżeli mamy do skopiowania kilka plików, to możemy znacznie zmniejszyć opóźnienia na łączu przez uruchomienie dwóch procesów w tym samym czasie.

β musi zainicjować dwa niezależne procesy. Pierwszy generuje i wysyła sumy kontrolne do α gdy drugi proces odbiera informacje o różnicach od α i rekonstruuje pliki.

Jeżeli łącze jest buforowane to te dwa procesy mogą bez problemów działać niezależnie, dzięki czemu łącze jest w pełni wykorzystane w obu kierunkach, przez większość czasu.

Wyniki

W celu przetestowania działania algorytmu, protokołem tar spakowano dwie wersje jądra Linuxa, odpowiednio 1.99.10 i 2.0.0. Wielkość spakowanych plików to w przybliżeniu 24MB.

Z 2441 plików w wersji 1.99.10, w porównaniu do wersji 2.0.0 tylko 291 plików zostało zmienionych, dodatkowo 19 plików zostało usuniętych, a 25 plików zostało dodanych.

Na dwóch spakowanych plikach tar wykonano standardowe polecenie „diff”, które przetworzyło ponad 32 tysiące wpisów co w sumie dało 2.1 MB.

Poniższa tabela pokazuje wynik dla rsync między dwoma plikami o różnej wartości bloku.

W każdym przypadku czas wykorzystania CPU był mniejszy od czasu jaki jest potrzebny na wykonanie polecenia “diff” na dwóch plikach.

Kolumny w tabeli prezentują:

• rozmiar bloku – Rozmiar w bajtach sumy kontrolnej bloków.
• dopasowania – Ilość identycznych bloków B znalezionych w A.
• pasujące tagi – Ilość 16 bitowych funkcji skrótu wykonanych dla sum kontrolnych z funkcją rolling, mających dopasowaną funkcję skrótu do jednej z sum kontrolnych pliku B.
• fałszywe alarmy – Ilość 32 bitowych sum kontrolnych z funkcją rolling pasujących, ale bez dopasowania już dla mocnych sum kontrolnych.
• dane – Ilość dosłownie przesłanych danych w bajtach.
• zapisano – Całkowita liczba bajtów zapisanych przez α włącznie z danymi protokołów. W większości to dane należące do plików.
• odczytano – Całkowita liczba bajtów odczytanych przez α włącznie z danymi protokołów. W większości to informacje o sumach kontrolnych.

Wyniki pokazują, że dla bloku o wielkości powyżej 300 bajtów, tylko niewielka część (około 5%) pliku została przeniesiona. Ilość przesłanych danych była również znacznie mniejsza niż rozmiar pliku diff, który musiałby być przesłany, jeżeli chcielibyśmy wykorzystać go do aktualizacji pliku na zdalnym komputerze.

Ilość miejsca potrzebnego na przechowanie sum kontrolnych była spora, ale i tak było to znacznie mniej niż rozmiar danych jakie trzeba było by przesyłać w każdym przypadku. Każda para sum kontrolnych zajmowała 20 bajtów: 4 bajty na sumę kontrolną z funkcją rolling plus 16 bajtów na 128-bitową sumę kontrolną MD4.

Liczba fałszywych alarmów była mniejsza niż 1/1000 liczby prawdziwych dopasowań, dowodząc tym samym, że 32 bitowa suma kontrolna z funkcją rolling jest bardzo dobra w eliminacji fałszywych wyników.

Liczba trafionych tagów dowodzi, że drugi poziom tj. algorytm wyszukiwania sumy kontrolnej był wyzwalany co 50 znaków. To jest dość wysoka wartość, ponieważ całkowita liczba bloków w pliku, to duża część wielkości tagu w tabeli funkcji skrótu. W przypadku mniejszych plików współczynnik trafień tagu powinien być zbliżony do liczby dopasowań. Dla bardzo dużych plików, wielkość tabeli funkcji skrótu powinna być większa.

Następna tabela pokazuje podobne wyniki dla znacznie mniejszych plików. W tym przypadku pliki nie były spakowane protokołem tar. Zamiast tego rsync został uruchomiony z opcją rekurencyjnego zejścia przez drzewo katalogów. Wykorzystane pliki należały do dwóch wersji oprogramowania zwanego “Samba”. Całkowita wielkość kodu źródłowego to 1,7 MB, a różnica pomiędzy tymi dwoma wersjami to 4155 linijek co w sumie daje nam 120 kB.

Podsumowanie

Obecnie jednym z kryteriów rozwoju firm produkujących rozwiązania serwerowe i ich konkurencyjności jest to czy ich produkty wspierają de-duplikację i w jakim stopniu. Ponieważ dużo firm chwali się, że obsługują rsync, to właśnie obsługa sumy kontrolnej „adler-32” umożliwiającej wdrożenie de-duplikacji można uznać za wskaźnik ich poziomu wiedzy i możliwości technicznych. W tym aspekcie rozwiązanie CTERA może być postrzegane jako kamień milowy w ciągłym rozwój firmy.