Pchełki SQL: Szanse kolizji

https://xpil.eu/gga

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 😉

https://xpil.eu/gga

2 komentarze

  1. Czas nieskończenie długi jest wystarczająco długi ażeby każde, nawet najmniej prawdopodobne zdarzenie, mogło w końcu zajść.

    Nie pamiętam skąd to pamiętam…
    To oczywiście tylko taka głupio-mądra prowokacja 🙂
    Pozdrawiam, Marian S. od Miłosza, alma mater Lazurowa

    1. W podobnym klimacie było kiedyś u Urbańczyka: poruszając się, nawet najwolniej, dotrzemy wszędzie. Stojąc w miejscu, nie dotrzemy nigdzie.

Leave a Comment

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]

Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.