Jak wydajnie generować i sprawdzać sumy kontrolne plików?

Chciałbym mieć możliwość przechwytywania i sprawdzania sum kontrolnych dla zbiorów na dużą skalę plików, zwykle zagnieżdżonych w złożonej hierarchii katalogów.

Czy każdy plik potrzebuje sumy kontrolnej? Czy istnieją sposoby na wykorzystanie istniejącej struktury katalogów w celu, powiedzmy, sprawdzenia tylko węzła w drzewie plików, a niekoniecznie każdego pliku w obrębie?

Najbardziej efektywnym sposobem wykorzystania sum kontrolnych jest sprawienie, aby komputer zrobił to wszystko. Użyj systemu plików, takiego jak ZFS, który sumuje sumę kontrolną (w rzeczywistości używa skrótów, które są silniejsze niż suma kontrolna) wszystkich danych podczas ich zapisywania i weryfikuje je za każdym razem, gdy dane są odczytywane. Oczywiście wadą jest to, że ZFS nie wie, że usunięcie lub zastąpienie pliku jest pomyłką, a kiedy jest to normalne działanie, ale ponieważ ZFS używa semantyki kopiowania przy zapisie do wszystkiego, możesz użyć jego funkcji migawek, aby zmniejszyć ryzyko .

ZFS może także automatycznie przywracać dane, które nie przejdą kontroli skrótu, używając dowolnej skonfigurowanej nadmiarowości, czy to parzystości w stylu raid5, kopii lustrzanych dysków czy duplikatów kopii (dodaj właściwość copy = N do dowolnego systemu plików ZFS i zapisze N ​​kopii dowolnych zapisanych danych). Przechowuje również skróty w drzewie Merkle, gdzie wartość skrótu pliku zależy od skrótów bloków, skrót wpisu katalogu zależy od wartości skrótu zawartych w nim plików i katalogów, skrót skrótu systemu plików zależy w skrócie katalogu głównego itp.

Niezależnie od tego, z jakim rozwiązaniem się skończysz, niezmiennie przekonasz się, że proces ten jest ograniczony szybkością dysków, a nie szybkością procesora.

Nie zapomnij również wziąć pod uwagę BER swoich dysków. Są to w końcu zwykłe talerze wirującej rdzy. Napęd na poziomie konsumenta ma wskaźnik błędów 1 niepoprawnie odczytany bit na każde 10 ^ 14 bitów, co daje wynik 1-bitowy na każde 11 odczytanych terabajtów. Jeśli masz 11 terabajtowy zestaw danych i obliczasz skrót każdego pliku w nim, obliczysz jedną z tych sum kontrolnych niepoprawnie i trwale uszkodzi jeden blok jednego z plików w zestawie danych. ZFS zna jednak skrót każdego bloku, który zapisał na każdym dysku w puli, i dlatego wie, który blok został utracony. Następnie może użyć nadmiarowości (parzystości, kopii lustrzanych lub dodatkowych kopii) w puli, aby przepisać dane w tym bloku z poprawnymi wartościami.

Ben porusza jednak dobry punkt w komentarzach. ZFS nie ujawnia żadnej wartości skrótu obliczanej dla użytkownika, więc dane, które wchodzą lub wychodzą z systemu ZFS, powinny być uzupełnione hashami. Podoba mi się sposób, w jaki robi to Archiwum Internetowe z plikiem xml, który towarzyszy każdemu elementowi w archiwum. Zobacz https://ia801605.us.archive.org/13/items/fakebook_the-firehouse-jazz-band-fake-book/fakebook_the-firehouse-jazz-band-fake-book_files.xml jako przykład.

Wygenerowałbym sumę kontrolną dla każdego pliku. Sumy kontrolne są bardzo małe, a wygenerowanie sumy kontrolnej dla całego katalogu wymagałoby również przetworzenia każdego pliku (przynajmniej jeśli nie mówimy o sumie kontrolnej katalogu, wykonanej tylko z pozycji katalogu - zrobiłbym je również, aby zapewnić brak danych jest usunięty).

Załóżmy, że masz jedną sumę kontrolną dla całego archiwum. Wiesz, że dane są uszkodzone, ale nie wiesz, czy jest to tylko jeden plik, a co ważniejsze, który z nich. Posiadanie oddzielnych sum kontrolnych daje większą elastyczność. Możesz wykryć pojedynczy plik, który jest uszkodzony, i zastąpić go z pliku z innej kopii zapasowej (co z kolei może spowodować uszkodzenie innego pliku).

W ten sposób Twoje dane mogą przetrwać.

Może to dobry moment, aby poruszyć BagIt . Jest to bardzo prosty, ale potężny format pakowania plików przeznaczony do archiwizacji, długotrwałego przechowywania i przesyłania obiektów cyfrowych. Do użytkowników należą Library of Congress i California Digital Library.

Narzędzie BagIt (istnieją w kilku językach programowania) umieszcza twoje pliki w określonej strukturze katalogów i dokonuje dla ciebie sumowania / haszowania. To wszystko.

PS: Oczywiście narzędzia BagIt mogą także weryfikować torby pod kątem sum kontrolnych / skrótów, a także dodawać metadane do worków. Ale to tak skomplikowane, jak torby.

Ta odpowiedź jest połączeniem odpowiedzi @ lechlukasz i @ db48x , a także zawiera pewne uwagi poczynione w komentarzach oraz moje własne przemyślenia.

Prosta ścieżka do przodu to połączenie systemu plików i oddzielnych metadanych.

Korzystając z systemu plików, który dokonuje haszowania i sprawdzania poprawności danych w locie, takiego jak ZFS lub Btrfs (zauważ, że chociaż dokonano wielkich postępów, Btrfs nie jest obecnie uważany za gotowy do użytku produkcyjnego), możesz być rozsądnie upewnij się, że jeśli dane można odczytać z dysku bez błędu systemu operacyjnego, to odczytane dane zostały zapisane na dysku w sposób zamierzony przez system plików. Dzięki okresowym operacjom „szorowania” wszystkie dane są odczytywane i weryfikowane pod kątem tego, co system plików powinien wiedzieć.

Chroni to jednak tylko przed uszkodzeniem na dysku (nieczytelne bloki, bezpośrednie błędy zapisu sprzętu, nieprawidłowe zapisy, które uszkadzają części danych bezpośrednio na urządzeniu blokującym itp.). Nie chroni przed błędem oprogramowania, niewłaściwą obsługą użytkownika lub złośliwym oprogramowaniem, które działa przez zamierzone funkcje systemu operacyjnego do pracy z plikami, przy założeniu, że narzędzia te są wolne od takich błędów.

Aby chronić się przed tym drugim, potrzebujesz kolejnej warstwy ochrony. Sumowanie danych kontrolnych lub mieszanie danych z perspektywy aplikacji użytkownika pomoże zabezpieczyć się przed wieloma wyżej wymienionymi zagrożeniami, ale należy je wykonać osobno (albo jako wbudowane działanie procesu w oprogramowaniu, albo jako całkowicie odrębny proces).

Przy dzisiejszym sprzęcie i praktycznym rozwiązaniu do przechowywania dużych ilości danych (spinningowe dyski twarde w przeciwieństwie do dysków półprzewodnikowych / SSD), nawet złożone algorytmy mieszające, takie jak SHA1, będą w dużej mierze ograniczone do operacji we / wy - to znaczy prędkości przy której dane są mieszane będą raczej funkcją prędkości odczytu systemu pamięci niż zdolności procesora komputera do obliczenia wartości skrótu. Zrobiłem eksperyment z uruchomieniem procesu mieszania MD5 w przestrzeni użytkownika na około 150 GB danych na tym, co w 2012 roku było komputerem klasy średniej, i zakończyło się po ćwiczeniu dysku w zasadzie bez przerwy przez około 40 minut. Skalując te liczby 100-krotnie, uzyskasz skróty MD5 kolekcji 15 TB w około trzy dni na tym samym sprzęcie. Dodając szybkość odczytu odczytu (co można łatwo osiągnąć npNa przykład RAID 0 to striping bez redundancji, powszechnie stosowany w celu uzyskania wyższej wydajności odczytu / zapisu, być może w połączeniu z RAID 1 tworzącym RAID 10 ), czas do ukończenia można skrócić dla tej samej ilości danych.

Łącząc oba, uzyskujesz to, co najlepsze z obu światów: system plików daje pewność, że to, co otrzymałeś podczas czytania pliku, jest tym, co zostało faktycznie zapisane, a osobny proces sprawdzania poprawności może przebiegać w całej kolekcji, zapewniając, że dane przechowywane nadal pasuje do tego, co zostało wprowadzone do archiwum. Każda niespójność między nimi (system plików mówi, że plik jest w porządku, sprawdzanie poprawności mówi, że nie) wskazuje na plik, który został zmodyfikowany poza zamierzonym trybem działania archiwum, ale z poziomu wyposażenia systemu operacyjnego, powodując przywrócenie z pomocniczego kopia (kopia zapasowa). Sprawdzanie poprawności może zatem być uruchamiane w dłuższym przedziale czasu, co staje się niezbędne w przypadku bardzo dużych archiwów, ale wszelkie gwarancje dostępu online nadal nie zostaną uszkodzone na sprzęcie, jeśli odczyt się powiedzie. Zasadniczo, oprogramowanie archiwalne może polegać na systemie plików, aby zgłaszać niespójności jako błędy odczytu, i przeprowadzać osobne sprawdzenie poprawności w tle, gdy użytkownik pracuje z plikiem i wyświetla odpowiedni komunikat, który powinien wskazywać, że plik nie pasuje do tego, co zostało pobrane do archiwum. Korzystając z systemu plików z blokowaniem blokowym, taki schemat miałby minimalny wpływ na postrzeganą wydajność, jednocześnie zapewniając pewność, że treść jest poprawna.

Przeszedłem odpowiedzi i chociaż podoba mi się pomysł polegający na ZFS do obsługi błędów warstwy danych, nadal istnieje problem zmiany plików, albo przez pomyłkę, albo złośliwie. ZFS nie ochroni cię w takim przypadku i, jak ktoś wspomniany, nie da ci widocznego przez użytkownika „skrótu” do przechowywania gdzie indziej w celu zewnętrznej weryfikacji.

Istnieje aplikacja Linux o nazwie TripWire, która była szeroko używana do monitorowania plików wykonywalnych systemu, aby sprawdzić, czy nie zostały zmienione po ataku. Ten projekt najwyraźniej jest teraz porzucony, ale jest nowy o nazwie AIDE (Advanced Intrusion Detection Environment), zalecany na ServerFault:

/server/62539/tripwire-and-alternatives

Podczas instalacji uruchamiałby się co x minut, konfigurowany przez użytkownika i sprawdzał wszystkie foldery, które określiłeś, pod kątem zmian w plikach. Musi uruchomić się raz, aby obliczyć wszystkie skróty pliku, a następnie sprawdza wszystkie skróty względem bieżącego pliku i upewnia się, że nadal są takie same. Możesz określić, jakiego rodzaju skrótu lub kombinacji skrótów użyć (nie poleciłbym niczego słabszego niż SHA-256), jakich atrybutów pliku użyć (zawartość, rozmiar, zmodyfikowany znacznik czasu itp.), Częstotliwość, z jaką sprawdza, jak / gdzie przechowywać bazę danych mieszania itp.

Niektórzy mogą rozważyć tę nadwyżkę, ale w zależności od wymagań PO, może dać mu więcej spokoju, że przechowywane przez niego dane pozostaną takie same po pewnym czasie.

National Archives of Australia opracowało [Checksum Checker] ( http://checksumchecker.sourceforge.net/ ), który jest dostępny bezpłatnie na GPLv3.

Odczytuje sumę kontrolną i algorytm z bazy danych, a następnie ponownie oblicza sumę kontrolną dla pliku, porównuje dwie wartości i zgłasza, jeśli wystąpił błąd. Obsługuje algorytmy MD5, SHA1, SHA2, SHA256 i SHA512.

Inne oprogramowanie w ich repozytorium cyfrowym [DPR] ( http://dpr.sourceforge.net/ ) generuje początkową sumę kontrolną (a także wykonuje wszystkie inne czynności związane z przetwarzaniem)