Pchełki SQL: Szanse kolizji

O synchronizacji danych i szansach kolizji kryptograficznych.

Dzisiejsza Pchełka nie zawiera ani jednej linii kodu SQL. Da się? Da się!

Jednym z możliwych podejść do synchronizacji danych między dwiema dużymi tabelami na SQL Serverze jest używanie funkcji haszującej.

W praktyce wygląda to tak:

  1. W tabeli źródłowej mamy dwie grupy kolumn: identyfikatory rekordu (klucz – jedna kolumna lub więcej) oraz cała reszta
  2. Dla każdego rekordu w tabeli źródłowej wyliczamy hasz skonkatenowanych kolumn klucza, zapisujemy go w osobnej kolumnie key_hash
  3. Dla każdego rekordu w tabeli źródłowej wyliczamy hasz skonkatenowanych kolumn danych (nienależących do klucza), zapisujemy go w kolumnie data_hash
  4. Zakładamy indeks na kolumnie key_hash, pokrywający kolumnę data_hash
  5. Tworzymy tabelę docelową jako dokładną kopię tabeli źródłowej, tylko pod inną nazwą
  6. Dla każdego rekordu w tabeli źródłowej:
    6.1. Sprawdzamy, czy key_hash istnieje w tabeli docelowej
    6.2. Jeżeli tak, porównujemy wartości data_hash między tabelami, jeżeli są różne, aktualizujemy rekord docelowy
    6.3. Jeżeli nie, wstawiamy nowy rekord do tabeli docelowej

Kroki 1-5 musimy wykonać tylko raz. Kroki 6.* wykonujemy przy kolejnych synchronizacjach.

Zalety:

(1) Porównujemy tylko jedną (indeksowaną!) wartość klucza, żeby stwierdzić, czy dany klucz już jest w tabeli docelowej, czy nie. Jeżeli kiedykolwiek trzeba będzie rozszerzyć klucz o więcej kolumn, nadal porównujemy tylko jedną wartość.
(2) Porównujemy tylko jedną wartość danych, która jest już częścią indeksu (a więc jest dostępna „od razu”, bez kosztownych operacji typu lookup), żeby stwierdzić, czy dane pod bieżącym kluczem uległy zmianie czy nie.
(3) Ponieważ (1) oraz (2), czas wykonania synchronzacji spada drastycznie. W przeprowadzonych przeze mnie testach na tabeli dwudziestomilionowej (około 30 kolumn różnych typów) czas synchronizacji spadł z 31 minut do 8 sekund (i tak, opróżniłem cache przed wykonaniem testu!)

Wady:

  1. Musimy wyliczać dwa hasze dla każdego rekordu źródłowego (to szybka operacja… ale jednak dodatkowy krok)
  2. Musimy te dwa hasze gdzieś przechować. VARBINARY(32) to niewiele przy tabeli z mnóstwem kolumn, ale dla „wąskich” tabel narzut może okazać się spory.
  3. Ryzykujemy kolizję (użycie funkcji haszujących ZAWSZE wiąże się z ryzykiem kolizji)

No i teraz meritum dzisiejszego wpisu, czyli: jaka jest szansa na kolizję?

Weźmy sobie tabelę z miliardem rekordów. Jaka jest szansa, że dwa z nich wygenerują ten sam hasz, przy założeniu, że używamy 256-bitowego algorytmu SHA2?

Bez wdawania się w zawiłości matematyczne ujawnię od razu, że szansa na to, że wśród naszego miliarda rekordów dwa z nich wygenerują ten sam hasz jest o czterdzieści trzy rzędy wielkości mniejsza od szansy, że w Ziemię w ciągu najbliższej sekundy uderzy meteoryt, który zniszczy naszą cywilizację.

43 rzędy wielkości. Czyli jedynka z 43 zerami. O tylekroć mniejsze są szanse na kolizję kryptograficzną.

Wygląda na to, że możemy haszować bez ryzyka!

Chociaż… prawo Murphy-ego nie śpi 😉

Autor: xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a'capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

Bądź pierwszy!

Powiadom o
avatar
wpDiscuz