niedziela, 20 lutego 2011

Deduplikacja - kopie idą precz! (Część 3 - Hash collisions)

Kontynuujemy tematy związane z deduplikacją , tym razem odchodzimy trochę od rozważań dotyczących jej zastosowania a skupimy się na pewnym aspekcie technicznym. Chodzi o sam mechanizm tworzenia skrótów (hash-y) i niebezpieczeństwo, że dwa odrębne pakiety danych wygenerują ten sam skrót.

Szybka powtórka:


Dane są wysyłane do systemu deduplikującego. Ten dzieli je na części/paczki (w zależności do poziomu na którym działa są to np: pliki, bloki danych różnej wielkości itd...), a następnie z każdej takiej pojedynczej części wyznacza jej skrót. Skrót (hash) jest, w założeniu, pewnym "odciskiem palca" jednoznacznie identyfikującym daną paczkę (chunk) danych. System deduplikujący sprawdza w swojej bazie hashy czy ten wygenerowany przed chwilą już się w niej znajduje. Jeżeli nie, to jest dopisywany, a dane które go opisują zeskładowane, jeżeli tak, to oznacza to, iż te dane zostały już wcześniej zapisane, a ich kolejne wystąpienie jest zastępowane wskaźnikiem do zeskładowanej kopii.


W jaki sposób liczony jest hash i sprawdzane duplikaty danych:

Są trzy podstawowe metody sprawdzania czy dane przychodzące do dedpulikatora zostały już na nim wcześniej zeskładowanie:

  1. Wykorzystuje się algorytmy kryptograficzne  (używane np: przy generowaniu podpisów cyfrowych) do tworzenia skrótów (hashy) z przychodzących danych. Przykładowe algorytmami, które są stosowane to SH1 i MD5. Hash tworzony za pomocą SH1 ma 160 bitów długości, przy wykorzystaniu MD5 - 128bitów. Jeżeli paczki danych są różne, powinny generować różne skróty.
  2. Wykorzystuje się algorytmy stworzone/zmodyfikowane przez producenta danego systemu. Podobnie jak w metodzie 1 z danych przychodzących generowany jest skrót. Zarówno długość skrótu jak i mechanizm jego tworzenia może być różny, w zależności od producenta danego rozwiązania.
  3. Porównanie bit po bicie - najpewniejszą metodą sprawdzenia czy dana paczka danych jest już zeskładowana jest wykonanie jej porównia bit po bicie do istniejących już danych. Oczywiście metoda ta jest także najbardziej czasochłonna i wymaga wykonania największej ilości operacji.


Hash Collision (kolizja skrótów):

Do kolizji skrótów dochodzi kiedy dwie różne paczki danych wygenerują ten sam hash.

Jakie są konsekwencje takiego wydarzenia?

Przede wszystkim dla systemu obydwa te różne pakiety danych będą wyglądały identycznie co spowoduje, że zeskładowany zostanie tylko jeden z nich a drugi zostanie zastąpiony wskaźnikiem. Dla samego deduplikatora wszystko będzie w porządku i wykonana operacja będzie po prostu usunięciem zduplikowanych danych. Gorzej sytuacja wygląda przy odtworzeniu - dane dla których wystąpił hash collision mogły zostać usunięte i zastąpione innymi. System odtworzy te inne dane, przez co spowoduje korupcję całego backupu i w rezultacie jego utratę.
Problem z wystąpieniem kolizji hashy nie dotyczy jednak pojedynczego backupu. Typowy współczynnik deduplikacji jest równy około 10:1 - oznacza to, że (średnio) do każdej paczki danych zapisanych przez deduplikator prowadzi 10 odnośników. Idąc dalej - dla danych przy których wystapiła kolizja hashy, połowa z tych wskaźników będzie prowadziła do danych innych niż orginalne.
Summa summarum dla pojedyńczej kolizji skrótów możemy mówić o mniej więcej 5 utraconych backupach.

Czy jest to duży problem? To wszysko zależy od częstotliwości jego występowania. Jeżeli kolizja skrótów występuje raz na sto paczek danych wtedy skutki mogą być tragiczne. Jeżeli raz na miliard, to może da się ją zignorować?

Jakie jest prawdopodobieństwo wystąpienia kolizji skrótów?

Rozważmy metodę nr 1 z opisanych wcześniej sposobów wyznaczania hashy, czyli zastosowanie algorytmów SH1 i MD5. Prawdopodobnieństwo, że dwie różne paczki danych wygenerują ten sam skrót zależne jest od długości samego skrótu i równe 1/2^160 dla SH1 i 1/2^128 dla MD5.
Są to liczby niewyobrażalnie małe - gdyby wszystkie dane przechowywane na całym świecie przepuścić przez jeden system deduplikujący to ryzyko, że któreś z dwóch paczek wygenerują taki sam skrót było by miliony razy mniejsze niż szansa wygrania głównej nagrody w lotto. Można powiedzieć, iż wystąpienie kolizji skrótów wydaje się pomijanie małe.
Niektórzy zwracają jednak uwagę na fakt, iż obliczenia te mogą niedokładnie odzwierciedlać stan rzeczywisty. Metoda liczenia, której użycie może radykalnie zwiększyć prawdopodobieństwo wystąpienia kolizji znana jest jako "Paradoks dnia urodzin".
Jeżeli znajduję się w pomieszczeniu z 30 osobami to szansa, że jest wśród nich ktoś kto ma urodziny w tym samym dniu co ja, jest mniejsza niż 10% , natomiast prawdopodobieństwo, dość podobnego (wydaje się) zdarzania, że w tej grupie znajdują się dowolne dwie osoby mające urodziny w tym samym dniu jest sporo większe niż połowa. Wynika to z faktu że dowolnych par z dwóch osób pośród 30 można złożyć o wiele więcej niż par w których ja stanowię jedną z tych osób - im większą grupę weźmiemy tym te dwa prawodpodobieństwa będą się bardziej od siebie różniły. Podobna zależność występuje przy wyliczaniu prawdopodobieństwa wystąpienia kolizji skrótów. Jeżeli badamy szansę na wystąpienie kolizji między dwoma wybranymi paczkami danych, to jest ona praktycznie zerowa , jeżeli jednak weźmiemy pod uwagę całą pulę danych gdzie ilość paczek (np: bloków) idzie w dziesiątki milionów to szanse na uzyskanie kolizji wśród którejkolwiek z par paczek danych prezentuje się zupełnie inaczej.
Czy dalej szansa wystąpienia kolizji danych jest pomijalnie mała?
Nie zamierzam tutaj przedstawiać dokładnych wyliczeń (wpis na blogu backupcentral.com który to wyznacza, jest w sekcji do poczytania), w każdym razie aby prawdopodobieństwo wystąpienia kolizji hashy było większe niż 0.000000000000001% musimy mieć conajmniej 50EB danych (1EB=1024PB).
Znowu wielkość, która praktycznie nie ma żadnego znacznia.
Czy ktoś z Was przechowuje 50EB danych? A może chociaż 1EB?
W każdym razie nawet gdyby ktoś chciał uznać takie ryzyko za znaczące, to warto aby wiedział, że zagrożenie wystąpieniem niewykrytego błędu zapisu na taśmie LTO jest większe ( mimo, iż także niewyobrażalnie nikłe).
Wydaje mi się, że gdyby ktoś podjął się oszacowania ryzyka, że w ziemską atmosferę wpadnie meteor i rozpadnie się w niej na 4 części z których każda trafi dokładnie w nasze centra komputerowe rozsiane po całej kuli ziemskiej i zniszczy fizycznie przechowywane cztery kopie danych - to prawdopodobieństwo takiego zdarzenia i tak okaże się wyższe niż pradowpodobieństwo wystąpienia kolizji skrótów.

I tym akcentem zakończę ten wpis...


Do poczytania:

Paradoks dnia urodzin
Hash Collisions: The real odd
When hashes collide
What do hash collisions really mean
The skinny on data deduplication

poniedziałek, 7 lutego 2011

Deduplikacja - kopie idą precz! (Część 2 - Primary Storage Dedupe)

Ten wpis dalej pozostaje w temacie deduplikcji, ale dotyczy pewnego wyjątkowego jej zastosowania, rzadziej spotkanego i nieco bardziej "egzotycznego", a mianowicie deduplikacji primary storage.
Notka będzie raczej krótka i stanowi jedynie zarysowanie tematu, niż jego głęboką analizę.

Standardowe zastosowanie deduplikacji polega na wykorzystaniu jej dla zmniejszenia objętości danych backupowanych. Nie wchodząć w szczegóły i nie rozpatrując różnych wariantów, typowy proces deduplikacji polega na tym, iż strumień danych wysyłany przez serwer wykonujący składowanie trafia do wirtualnego urządzania taśmowego (VTL), zostaje zdeduplikowany, a nastepnie zapisany na dyski. Uzystkujemy znaczną oszczędność jeżeli chodzi o zajmowaną przestrzeń, ale dotyczy to jedynie danych zeskładowanych, czyli nieaktywnych. Można się zastanowić, czy podobnego uzysku nie można by było osiągnąć dla tzw: primary storage, czyli tych danych, które są wykorzystywane produkcyjnie i z których na bieżąco korzystają użytkownicy naszego systemu/aplikacji.
Dwie sprawy mogą nasuwać się kiedy rozważamy deduplikację primary storage. Po pierwsze jak wpływa to na wydajność samego systemu dyskowego, a po drugie czy możemy oczekiwać takich samych współczynników redukcji jak przy deduplikowaniu składowań.

Na drugie pytanie odpowiedź brzmi - nie.
Przy przewidywaniu współczynnika deduplikacji na primary storage bardzo dużo zależy od typu danych i charakterystyce aplikacji jaka na nim działa. Zwykle bazy danych (czyli dane struktruralne) bardzo słabo dają się deduplikować - wiąże się to z ich architekturą i samym sposobem w jaki są używane. Ich budowa to przeważnie pojedyńcze, bardzo duże pliki, na których ciągle dokonywane są zapisy w różnych (losowych) miejscach. Dodatkowo często sam silnik bazy dokonuje usunięcia z niej redundantnych fragmentów, co oczywiście obniża sprawność (i sensowność stosowania) mechanizmu deduplikcji.
Inne dane, które nie powinny być deduplikowane na primary storage to np: formaty zawierające już wbudowane mechanizmy pre-kompresji ( jak np pdf) oraz pliki zaszyfrowane.
Jeżeli  chodzi o dane "aktywne", to oczywiście wiele z nich jest powtórzonych, szczególnie jeżeli mówimy o sprawdzaniu duplikatów na poziomie bloków danych. Nie ma tutaj jednak pozytywnego efektu zwiększającego redukcję zajętości, występującego w backupach i archiwach, które bardzo dobrze się deduplikują, między innymi dlatego, iż są cyklicznie robione, a między kolejnymi kopiami stosunkowo niewielka ilość danych się zmieniła.

Jeżeli mówimy o wpływie na wydajność systemu dyskowego z włączoną deduplikacją, to wbrew pozorom nie jest ona znacząca. Trzeba jednak być świadomym jednej sprawy - dane nie są deduplikowane w locie (in-line) w momencie ich zapisywania. Zapis odbywa się "normalnie" bez usuwania kopii. Sam proces deduplikowania odbywa się cyklicznie (np: raz dziennie) i zwykle jest uruchamiany w momencie gdy sam storage jest najmniej obciążony.
Co prawda zaczynają pojawiać się przymiarki do rozwiązań deduplikujących primary storage "w locie" ale w tej chwili ciężko jeszcze coś konstruktywnego na ten temat powiedzieć.

Z innych spraw, które warto mieć na uwadze przy wyborze optymalnego systemu deduplikacji primary storage to jego współpraca z naszą aplikacją do backupu. Optymalnie było by gdyby nasze środowisko backupowe wspierało składowanie danych już zdeduplikowanych. Jeżeli przeprowadzenie backupy wymaga przywrócenia danych do postaci oryginalnej przed wysłaniem do nośnika backupowego to działanie takie jest stratą czasu i zasobów.

Co do konkretnych rozwiązań i produktów wspierających ten rodzaj deduplikacji napiszę innym razem. Jeden z ostatnich postów w temacie deduplikacji będzie takim przeglądem rozwiązań występujących na rynku razem z opisem ich możliwości.

Do poczytania:
Primary storage deduplication
Six requirements for deploying primary storage optimization
De-duplicating primary storage
Disk Deduplication For Primary Storage