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

Brak komentarzy:

Prześlij komentarz