Jakie są możliwe sposoby uniknięcia duplikatów, gdy nie można dodać unikalnego indeksu

10

Utknąłem w problemie współbieżności.

Jest typowym problemem, gdy użytkownik wysyła 2 lub 3 transakcje, aby utrwalić niektóre dane, których NIE POWINNY BYĆ duplikowane w bazie danych. W przypadku duplikatu rekordu należy zwrócić błąd.

Ten problem jest łatwy, gdy możesz po prostu dodać indeks (unikalny) do kolumny, w której przechowujesz skrót.

Ale w tym przypadku mam ogromną tabelę (prawdopodobnie miliony rekordów) i nie mogę tak po prostu modyfikować tabeli.

W rzeczywistości mamy kolumnę, w której przechowujemy skrót danych, których nie należy powielać, ale nie ustawiono unikalnego indeksu.

Próbuję na moim kodzie Java, aby sprawdzić, czy istnieje tuż przed opróżnieniem, nadal otrzymuję duplikaty.

Moje możliwe rozwiązania tego:

  • Utwórz wyzwalacz, który sprawdzi, czy skrót, który próbuję wstawić, już istnieje w tabeli.
  • Utwórz kolejną tabelę, aby przechowywać unikalne indeksy dla tej tabeli i dodaj klucz obcy do głównej tabeli.
  • Usiądź na pozycji embrionalnej i płacz
rafuru
źródło
Czy sprawdzanie skrótu kończy się niepowodzeniem z powodu kolizji skrótu lub błędu w czeku?
candied_orange
4
Nie dostałem twojego pytania. Więc zamiast indeksować raz na całą swoją ogromną tabelę z milionami rekordów, wolisz czytać dla każdego następnego miliona rekordów, które dodasz, istniejące miliony, aby szukać podwójnych? lub powielić niektóre informacje i dodać złączenia, aby sprawdzić?
Christophe
Problem polega na tym, że dla dokonania tej zmiany zostałem ostrzeżony, że potrzebujemy dużo miejsca i długiego przestoju dla naszej usługi, aby spełnić niektóre wymagania, nasza usługa nie może być wyłączona dłużej niż 2 godziny miesięcznie. Wiem, że najlepszym sposobem jest wykonanie konserwacji na tym stole, ale w tej chwili nie mogę tego zrobić, więc potrzebujemy obejścia.
rafuru
4
Nie rozumiem - dlaczego dodanie wyzwalacza lub dodanie kolejnej tabeli w celu „emulacji” indeksu zajmuje mniej czasu przestoju niż zwykłe dodanie indeksu do istniejącej tabeli?
Dok. Brown
2
@rafuru: kto powiedział, że musisz stworzyć unikalny indeks? Standardowy, nieunikalny indeks będzie prawdopodobnie wszystkim, czego potrzebujesz, aby szybko znaleźć wszystkie wiersze o tej samej wartości skrótu.
Dok. Brown

Odpowiedzi:

3

Istnieje kilka możliwych scenariuszy, które są łatwe do rozwiązania, i zgubny, który nie jest.

Dla użytkownika, który wprowadza wartość, a następnie wprowadza tę samą wartość jakiś czas później prosty WYBÓR, zanim INSERT wykryje problem. Działa to w przypadku, gdy jeden użytkownik przesyła wartość, a jakiś czas później inny użytkownik przesyła tę samą wartość.

Jeśli użytkownik prześle listę wartości z duplikatami - powiedzmy {ABC, DEF, ABC} - w jednym wywołaniu kodu aplikacja może wykryć i filtrować duplikaty, być może zgłaszając błąd. Musisz także sprawdzić, czy DB nie zawiera żadnych unikalnych wartości przed wstawieniem.

Trudny scenariusz polega na tym, że zapis jednego użytkownika znajduje się w DBMS w tym samym czasie, co zapis innego użytkownika i zapisują tę samą wartość. Potem masz wyścig między nimi. Ponieważ DBMS jest (najprawdopodobniej - nie mówisz, którego używasz) prewencyjnym systemem wielozadaniowym, każde zadanie może zostać wstrzymane w dowolnym momencie jego wykonywania. Oznacza to, że zadanie użytkownika 1 może sprawdzić, czy nie ma istniejącego wiersza, następnie zadanie użytkownika 2 może sprawdzić, czy nie ma istniejącego wiersza, następnie zadanie użytkownika 1 może wstawić ten wiersz, a następnie zadanie użytkownika 2 może wstawić ten wiersz. W każdym punkcie zadania są indywidualnie zadowolone, że robią dobrze. Jednak globalnie występuje błąd.

Zwykle DBMS poradziłby sobie z tym, blokując daną wartość. W tym problemie tworzysz nowy wiersz, więc nie ma jeszcze nic do zablokowania. Odpowiedzią jest blokada zasięgu. Jak sugeruje, blokuje to zakres wartości, niezależnie od tego, czy obecnie istnieją, czy nie. Po zablokowaniu dostęp do tego zakresu nie będzie możliwy przez inne zadanie, dopóki blokada nie zostanie zwolniona. Aby uzyskać blokady zasięgu, musisz określić i poziom izolacji opcji SERIALIZABLE . Zjawisko skradania się innego zadania z rzędu po sprawdzeniu zadania jest znane jako rekordy fantomowe .

Ustawienie poziomu izolacji na Serializable w całej aplikacji będzie miało implikacje. Przepustowość zostanie zmniejszona. Inne warunki wyścigowe, które w przeszłości działały wystarczająco dobrze, mogą teraz zacząć wykazywać błędy. Sugerowałbym ustawienie go na połączenie, które wykonuje kod wywołujący duplikaty i pozostawienie pozostałej części aplikacji bez zmian.

Alternatywą opartą na kodzie jest sprawdzenie po zapisie zamiast wcześniej. Podobnie INSERT, a następnie policz liczbę wierszy o tej wartości skrótu. Jeśli istnieją duplikaty, wycofaj działanie. Może to mieć pewne przewrotne wyniki. Powiedz, że zadanie 1 zapisuje, a następnie zadanie 2. Następnie zadanie 1 sprawdza i znajduje duplikat. Cofa się, mimo że był pierwszy. Podobnie oba zadania mogą wykryć duplikat i oba wycofać. Ale przynajmniej będziesz mieć wiadomość do pracy, mechanizm ponownej próby i żadnych nowych duplikatów. Wycofywanie jest marszczone, podobnie jak stosowanie wyjątków do kontrolowania przebiegu programu. Zauważ, że wszyscypraca nad transakcją zostanie wycofana, a nie tylko zapis wywołujący duplikaty. I będziesz musiał mieć wyraźne transakcje, które mogą zmniejszyć współbieżność. Powtórzenie kontroli będzie strasznie wolne, chyba że masz indeks w haszowaniu. Jeśli to zrobisz, równie dobrze możesz uczynić go wyjątkowym!

Jak skomentowałeś, prawdziwym rozwiązaniem jest unikalny indeks. Wydaje mi się, że powinno to pasować do okna konserwacji (choć oczywiście najlepiej znasz swój system). Powiedzmy, że hash ma osiem bajtów. Na sto milionów wierszy to około 1 GB. Doświadczenie sugeruje, że rozsądna ilość sprzętu przetwarzałaby te wiersze w ciągu minuty lub dwóch. Powielanie sprawdzania i eliminacji doda do tego, ale może być wcześniej napisane w skrypcie. To jednak tylko na bok.

Michael Green
źródło
2

W rzeczywistości mamy kolumnę, w której przechowujemy skrót danych, których nie należy powielać, ale nie ustawiono unikalnego indeksu.

Sprawdzanie kolizji skrótów to dobry pierwszy krok, ale uwaga, nie można zagwarantować, że ten sam program wygeneruje taki sam skrót na tych samych danych, jeśli zostanie ponownie uruchomiony . Wiele „szybkich” funkcji skrótu korzysta z wbudowanego pliku PRG, który jest inicjowany w momencie uruchomienia programu. Użyj skrótu kryptograficznego, jeśli skrót musi być zawsze taki sam, bez względu na wszystko, tak jak w tej aplikacji. Pamiętaj, że nie potrzebujesz dobrego lub bezpiecznego szyfrowania kryptograficznego.

Drugim krokiem jest sprawdzenie równości danych, ponieważ nawet najlepsze funkcje skrótu czasami powodują kolizje, ponieważ (zwykle) zmniejsza się entropię danych.

Więc:

Krok 1: Sprawdź, czy nie ma kolizji z hash kryptograficznym

Krok 2: jeśli skróty są zgodne, sprawdź, czy rzeczywiste dane są takie same

Turksarama
źródło
Nie widzę, jak to odpowiada na pytanie. Załóżmy przez chwilę, że dostępna kolumna haszująca jest wypełniona deterministyczną funkcją haszującą (w przeciwnym razie każda próba jej wykorzystania nie miałaby sensu). Według mnie problem polega na tym, że nie ma indeksu w tej kolumnie mieszającej w bazie danych, więc nawet pierwszy krok w odpowiedzi - sprawdzenie, czy występuje kolizja - nadal wymagałby pełnego skanowania tabeli dla każdego nowego rekordu w tabeli z kilka milionów płyt, które prawdopodobnie staną się zbyt wolne.
Doc Brown
Jest to najlepsze, co możesz zrobić bez tworzenia indeksu, o co pytało pytanie. Skanowanie mieszające oznacza przynajmniej, że musisz sprawdzić tylko jedną kolumnę, co jest znacznie szybsze niż sprawdzenie, ile kolumn w przeciwnym razie musiałoby sprawdzić.
Turksarama
Jestem prawie pewien, że nawet jeśli utworzenie indeksu nie jest możliwe (co w tym przypadku prawdopodobnie jest), oryginalna sugestia OP: „ utwórz kolejną tabelę do przechowywania unikalnych indeksów dla tej tabeli i dodaj klucz obcy do głównej tabeli ” robi dużo więcej rozsądku.
Dok. Brown
Hash deterministyczny i hash kryptograficzny to dwie ortogonalne koncepcje, prawda? skrót kryptograficzny może nie być deterministyczny i odwrotnie, deterministyczny skrót może nie mieć siły kryptograficznej.
Newtopian
Nie są tym samym, ale też nie są ortogonalne. Skrypty kryptograficzne są podzbiorem skrótów deterministycznych, ale nikt tak naprawdę nie zawraca sobie głowy tworzeniem niekryptograficznych skrótów deterministycznych, chyba że z jakiegoś powodu chcesz, aby były odwracalne.
Turksarama,
2

Stwórz nowy stół z unikalnym kluczem podstawowym

Po stronie klienta zacznij generować identyfikatory GUID dla każdego rekordu, abyś mógł wykryć proste ponowne wysyłanie.

Umieść nowe rekordy w nowej tabeli, abyś przynajmniej był dobry na nowe dane.

Mają kolumnę w nowej tabeli „CheckedAgainstOldData”

Zadaniem backendowym, które wykonuje dowolne bieżące powolne sprawdzanie skrótu, jest sprawdzenie, czy może znaleźć duplikat w starych danych i odpowiednio ustawić flagę, odrzucić duplikaty w tym momencie, Wysyłając powiadomienie z powrotem do klienta.

W międzyczasie mamy inne zadanie zaplecza, które przenosi dane ze starej do nowej tabeli, sprawdzając duplikaty za pomocą kontroli skrótu i ​​generując identyfikator GUID.

Możesz pozostawić to zadanie uruchomione na kilka dni (jeśli to konieczne), przenosząc dane bez przestojów.

Po zakończeniu przesyłania możesz wyłączyć powolny proces „CheckedAgainstOldData”. i przenieś wszystkie dane do jednej tabeli.

Szczerze mówiąc, jeśli problem jest tak poważny, jak to opisujesz, a oprogramowanie jest stare, będziesz mieć tysiące duplikatów.

Ewan
źródło
1

Zakładając, że dane pochodzące od „użytkownika” oznaczają osobę siedzącą przy klawiaturze i że duplikaty powstają, gdy dwóch użytkowników wprowadza te same dane w tym samym momencie. Spróbuj dodać funkcję, która powoduje losowe opóźnienie na początku wyzwalacza. Daj mu minimum czasu, jaki zajmuje zapisanie nowego rekordu na stole, i prawdopodobnie maksymalnie nie więcej niż nanocentury. W ten sposób, gdy otrzymasz prośby o duplikat, pierwsza powinna zostać wykonana, a wyzwalacz istnienia powinien odrzucić prawidłowy wynik. (Wyjaśnienie: każde połączenie powinno mieć swój unikalny losowy czas opóźnienia, zgodnie z tymi samymi zasadami, co protokół ALOHA )

Gregor y
źródło