Welche Möglichkeiten gibt es, um Duplikate zu vermeiden, wenn Sie keinen eindeutigen Index hinzufügen können?

10

Ich stecke in einem Parallelitätsproblem.

Ist ein typisches Problem, bei dem der Benutzer 2 oder 3 Transaktionen sendet, um einige Daten beizubehalten, die NICHT in der Datenbank dupliziert werden sollten. Im Falle eines doppelten Datensatzes sollten Sie einen Fehler zurückgeben.

Dieses Problem ist einfach, wenn Sie einer Spalte, in der Sie einen Hash speichern, einfach einen Index (eindeutig) hinzufügen können.

Aber in diesem Fall habe ich eine riesige Tabelle (wahrscheinlich Millionen von Datensätzen) und kann die Tabelle nicht einfach ändern.

Tatsächlich haben wir eine Spalte, in der wir einen Hash der Daten speichern, der nicht dupliziert werden sollte, aber kein eindeutiger Index festgelegt wurde.

Ich versuche mit meinem Java-Code zu überprüfen, ob er kurz vor dem Flush vorhanden ist, und erhalte immer noch Duplikate.

Meine möglichen Lösungen hierfür sind:

  • Erstellen Sie einen Trigger, der prüft, ob der Hash, den ich einzufügen versuche, bereits in der Tabelle vorhanden ist.
  • Erstellen Sie eine weitere Tabelle, um eindeutige Indizes für diese Tabelle zu speichern, und fügen Sie der Haupttabelle einen Fremdschlüssel hinzu.
  • Setzen Sie sich auf die fetale Position und weinen Sie
database concurrency Rafuru
quelle
Schlägt Ihre Überprüfung des Hash aufgrund von Hash-Kollisionen oder eines Fehlers in der Überprüfung fehl?
candied_orange
4
Ich habe deine Frage nicht verstanden. Anstatt also einmal für alle Ihre riesigen Tabellen mit Millionen von Datensätzen zu indizieren, lesen Sie lieber für jede der nächsten Millionen Datensätze, die Sie hinzufügen, die vorhandenen Millionen, um nach Doppelwerten zu suchen? oder einige Informationen duplizieren und Verknüpfungen hinzufügen, um Ihre Prüfung durchzuführen?
Christophe
Das Problem ist, dass ich für diese Änderung gewarnt wurde, dass wir viel Platz und lange Ausfallzeiten für unseren Service benötigen, um einige Anforderungen zu erfüllen. Unser Service kann nicht länger als 2 Stunden monatlich ausfallen. Ich weiß, dass der beste Weg ist, eine Wartung an diesem Tisch durchzuführen, aber das kann ich derzeit nicht tun, daher brauchen wir eine Problemumgehung.
Rafuru
4
Ich verstehe es nicht - warum dauert das Hinzufügen eines Triggers oder das Hinzufügen einer anderen Tabelle zum "Emulieren" eines Index weniger Ausfallzeit als das Hinzufügen eines Index zur vorhandenen Tabelle?
Doc Brown
2
@rafuru: Wer hat gesagt, dass Sie einen eindeutigen Index erstellen müssen? Ein standardmäßiger, nicht eindeutiger Index ist wahrscheinlich alles, was Sie benötigen, um schnell alle Zeilen mit demselben Hashwert zu finden.
Doc Brown

Antworten:

3

Es gibt einige mögliche Szenarien, die leicht zu lösen sind, und ein schädliches, das es nicht ist.

Für einen Benutzer, der einen Wert eingibt und einige Zeit später denselben Wert eingibt, führt ein einfaches SELECT, bevor das INSERT das Problem erkennt. Dies funktioniert für den Fall, dass ein Benutzer einen Wert übermittelt und einige Zeit später ein anderer Benutzer denselben Wert übermittelt.

Wenn der Benutzer eine Liste von Werten mit Duplikaten - beispielsweise {ABC, DEF, ABC} - in einem einzigen Aufruf des Codes übermittelt, kann die Anwendung die Duplikate erkennen und filtern, wodurch möglicherweise ein Fehler ausgelöst wird. Sie müssen außerdem vor dem Einfügen überprüfen, ob die Datenbank keinen der eindeutigen Werte enthält.

Das schwierige Szenario besteht darin, dass sich der Schreibvorgang eines Benutzers gleichzeitig mit dem Schreibvorgang eines anderen Benutzers im DBMS befindet und denselben Wert schreibt. Dann haben Sie ein Rennen eine Bedingung zwischen ihnen. Da das DBMS (höchstwahrscheinlich - Sie sagen nicht, welches Sie verwenden) ein präventives Multitasking-System ist, kann jede Aufgabe zu jedem Zeitpunkt ihrer Ausführung angehalten werden. Das bedeutet, dass die Aufgabe von Benutzer1 prüfen kann, ob keine Zeile vorhanden ist, die Aufgabe von Benutzer2 prüfen kann, ob keine Zeile vorhanden ist, die Aufgabe von Benutzer1 diese Zeile einfügen kann und die Aufgabe von Benutzer2 diese Zeile einfügen kann. An jedem Punkt sind die Aufgaben individuell froh, dass sie das Richtige tun. Global tritt jedoch ein Fehler auf.

Normalerweise würde ein DBMS dies handhaben, indem es den fraglichen Wert sperrt. In diesem Problem erstellen Sie eine neue Zeile, sodass noch nichts gesperrt werden muss. Die Antwort ist eine Entfernungssperre. Wie dies nahelegt, wird ein Wertebereich gesperrt, unabhängig davon, ob sie derzeit vorhanden sind oder nicht. Nach dem Sperren kann eine andere Aufgabe erst dann auf diesen Bereich zugreifen, wenn die Sperre aufgehoben wird. Um Bereichssperren zu erhalten, müssen Sie die Isolationsstufe SERIALIZABLE angeben . Das Phänomen, dass sich eine andere Aufgabe nach der Überprüfung Ihrer Aufgabe hintereinander schleicht, wird als Phantomdatensätze bezeichnet .

Das Festlegen der Isolationsstufe für die gesamte Anwendung auf Serializable hat Auswirkungen. Der Durchsatz wird reduziert. Andere Rennbedingungen, die in der Vergangenheit gut genug funktionierten, können jetzt Fehler anzeigen. Ich würde vorschlagen, es auf die Verbindung zu setzen, die Ihren doppelt induzierenden Code ausführt, und den Rest der Anwendung unverändert zu lassen.

Eine codebasierte Alternative besteht darin, nach dem Schreiben und nicht vorher zu prüfen . Führen Sie also INSERT aus und zählen Sie die Anzahl der Zeilen mit diesem Hashwert. Wenn es Duplikate gibt, wird die Aktion zurückgesetzt. Dies kann einige perverse Ergebnisse haben. Angenommen, Aufgabe 1 schreibt dann Aufgabe 2. Dann prüft Aufgabe 1 und findet ein Duplikat. Es rollt zurück, obwohl es das erste war. In ähnlicher Weise können beide Aufgaben das Duplikat und beide Rollbacks erkennen. Aber zumindest haben Sie eine Nachricht, mit der Sie arbeiten können, einen Wiederholungsmechanismus und keine neuen Duplikate. Rollbacks sind verpönt, ähnlich wie Ausnahmen zur Steuerung des Programmflusses. Beachten Sie gut, dass alleDie Arbeit in der Transaktion wird zurückgesetzt, nicht nur das doppelte Schreiben. Und Sie müssen explizite Transaktionen haben, die die Parallelität verringern können. Die doppelte Überprüfung ist schrecklich langsam, es sei denn, Sie haben einen Index für den Hash. Wenn Sie dies tun, können Sie es auch zu einem einzigartigen machen!

Wie Sie kommentiert haben, ist die eigentliche Lösung ein eindeutiger Index. Es scheint mir, dass dies in Ihr Wartungsfenster passen sollte (obwohl Sie Ihr System natürlich am besten kennen). Angenommen, der Hash ist acht Bytes. Für einhundert Millionen Zeilen ist das ungefähr 1 GB. Die Erfahrung zeigt, dass ein vernünftiges Stück Hardware diese vielen Zeilen in ein oder zwei Minuten verarbeiten würde. Doppelte Überprüfungen und Eliminierungen tragen dazu bei, können jedoch im Voraus per Skript erstellt werden. Dies ist jedoch nur eine Seite.

Michael Green
quelle
2

Tatsächlich haben wir eine Spalte, in der wir einen Hash der Daten speichern, der nicht dupliziert werden sollte, aber kein eindeutiger Index festgelegt wurde.

Das Überprüfen von Hash-Kollisionen ist ein guter erster Schritt. Beachten Sie jedoch, dass Sie nicht garantieren können, dass dasselbe Programm beim Neustart denselben Hash für dieselben Daten erzeugt . Viele "schnelle" Hash-Funktionen verwenden ein eingebautes Programm, das beim Start des Programms gesetzt wird. Verwenden Sie einen kryptografischen Hash, wenn der Hash immer derselbe sein muss, egal wie in dieser Anwendung. Beachten Sie, dass Sie keinen guten oder sicheren kryptografischen Hash benötigen.

Der zweite Schritt besteht darin, die Datengleichheit tatsächlich zu überprüfen, da selbst die besten Hash-Funktionen manchmal zu Kollisionen führen, da Sie (normalerweise) die Entropie Ihrer Daten reduzieren.

Damit:

Schritt 1: Überprüfen Sie, ob bei einem kryptografischen Hash eine Kollision auftritt

Schritt 2: Wenn die Hashes übereinstimmen, überprüfen Sie, ob die tatsächlichen Daten identisch sind

Turksarama
quelle
Ich sehe nicht, wie dies die Frage beantwortet. Nehmen wir für einen Moment an, dass die verfügbare Hash-Spalte mit einer deterministischen Hash-Funktion gefüllt ist (andernfalls wäre jeder Versuch, sie zu verwenden, nicht sinnvoll). Nach meinem Verständnis besteht das Problem darin, dass es keinen Index für diese Hash-Spalte in der Datenbank gibt. Daher würde selbst der erste Schritt in Ihrer Antwort - die Überprüfung, ob eine Kollision vorliegt - immer noch einen vollständigen Tabellenscan für jeden neuen Datensatz in einer Tabelle mit erfordern mehrere Millionen Datensätze, die wahrscheinlich viel zu langsam werden.
Doc Brown
Es ist das Beste, was Sie tun können, ohne einen Index zu erstellen, wie es die Frage stellte. Ein Hash-Scan bedeutet zumindest, dass Sie nur eine Spalte überprüfen müssen. Dies ist viel schneller als das Überprüfen der Spalten, die sonst geprüft werden müssten.
Turksarama
Ich bin mir ziemlich sicher, auch wenn das Erstellen eines Index nicht möglich ist (was in diesem Fall wahrscheinlich der Fall ist), macht der ursprüngliche Vorschlag des OP, " eine andere Tabelle zu erstellen, um eindeutige Indizes für diese Tabelle zu speichern und der Haupttabelle einen Fremdschlüssel hinzuzufügen ", viel mehr Sinn.
Doc Brown
Deterministischer Hash und kryptografischer Hash sind zwei orthogonale Konzepte, nicht wahr? Ein kryptografischer Hash ist möglicherweise nicht deterministisch und umgekehrt kann ein deterministischer Hash sehr wohl nicht kryptografisch stark sein.
Newtopian
Sie sind nicht dasselbe, aber sie sind auch nicht orthogonal. Kryptografische Hashes sind eine Teilmenge deterministischer Hashes, aber niemand stört es wirklich, nicht kryptografische deterministische Hashes zu erstellen, es sei denn, Sie möchten ausdrücklich, dass sie aus irgendeinem Grund reversibel sind.
Turksarama
2

Erstellen Sie eine neue Tabelle mit einem eindeutigen Primärschlüssel

Beginnen Sie auf der Clientseite mit der Generierung von GUIDs für jeden Datensatz, damit Sie einfache erneute Sendevorgänge erkennen können.

Fügen Sie neue Datensätze in die neue Tabelle ein, damit Sie zumindest für neue Daten gut sind.

Haben Sie eine Spalte in der neuen Tabelle "CheckedAgainstOldData"

Haben Sie eine Backend-Aufgabe, die alles tut, was Sie derzeit tun, um zu überprüfen, ob ein Duplikat in den alten Daten gefunden werden kann, und setzen Sie das Flag entsprechend, lehnen Sie Duplikate an dieser Stelle ab und senden Sie eine Benachrichtigung an den Client zurück.

In der Zwischenzeit haben Sie eine weitere Backend-Aufgabe, die Daten von der alten in die neue Tabelle verschiebt, mit Ihrer Hash-Prüfung nach Duplikaten sucht und die GUID generiert.

Sie können diese Aufgabe mehrere Tage lang ausführen (falls erforderlich) und die Daten ohne Ausfallzeiten übertragen.

Sobald die Übertragung abgeschlossen ist, können Sie den langsamen "CheckedAgainstOldData" -Prozess ausschalten. und übertragen Sie alle Daten in eine einzige Tabelle.

Ehrlich gesagt, wenn das Problem so schlimm ist, wie Sie es beschreiben, und die Software alt ist, werden Sie Tausende von Duplikaten haben.

Ewan
quelle
1

Angenommen, die Daten stammen vom "Benutzer", bedeutet jemand, der an einer Tastatur sitzt, und die Dupes entstehen, wenn zwei Benutzer gleichzeitig dieselben Daten eingeben. Versuchen Sie, eine Funktion hinzuzufügen, die zu Beginn des Triggers eine zufällige Verzögerung verursacht. Geben Sie ein Minimum an, wie lange es dauert, um einen neuen Datensatz in die Tabelle zu schreiben, und wahrscheinlich höchstens ein Nanocentury oder so. Auf diese Weise sollte, wenn Sie betrogene Anfragen erhalten, die erste durchgeführt werden und der Existenzauslöser sollte das richtige Ergebnis zurückwerfen. (Klarstellung: Jeder Anruf sollte eine eigene zufällige Verzögerungszeit haben, die den gleichen Prinzipien wie das ALOHA-Protokoll entspricht. )

Gregor y
quelle