Quels sont les moyens possibles d'éviter les doublons lorsque vous ne pouvez pas ajouter un index unique

10

Je suis coincé dans un problème de concurrence.

Est un problème typique où l'utilisateur envoie 2 ou 3 transactions pour conserver certaines données qui NE DEVRAIENT PAS ÊTRE dupliquées dans la base de données, en cas d'enregistrement en double, vous devez renvoyer une erreur.

Ce problème est facile lorsque vous pouvez simplement ajouter un index (unique) à une colonne où vous stockez un hachage.

Mais dans ce cas, j'ai une énorme table (probablement des millions d'enregistrements) et je ne peux pas simplement modifier la table.

En fait, nous avons une colonne où nous stockons un hachage des données qui ne doivent pas être dupliquées mais aucun index unique n'a été défini.

J'essaie mon code java pour vérifier s'il existe juste avant le vidage, en obtenant toujours des doublons.

Mes solutions possibles pour cela sont:

  • Créez un déclencheur qui vérifie si le hachage que j'essaie d'insérer existe déjà sur la table.
  • Créez une autre table pour stocker des index uniques pour cette table et ajoutez une clé étrangère à la table principale.
  • Asseyez-vous en position fœtale et pleurez
database concurrency rafuru
la source
Votre vérification du hachage échoue-t-elle en raison de collisions de hachage ou d'un bogue dans la vérification?
candied_orange
4
Je n'ai pas compris votre question. Donc, au lieu d'indexer une fois pour toutes votre immense table avec des millions d'enregistrements, vous préférez lire pour chacun des millions d'enregistrements suivants que vous ajouterez, les millions existants pour rechercher des doubles? ou dupliquer certaines informations et ajouter des jointures pour effectuer votre vérification?
Christophe
Le problème est que, pour effectuer ce changement, j'ai été averti que nous avons besoin de beaucoup d'espace et d'un long temps d'arrêt pour notre service, afin de répondre à certaines exigences, notre service ne peut pas être interrompu plus de 2 heures par mois. Je sais que la meilleure façon est d'effectuer une maintenance sur cette table, mais c'est quelque chose que je ne peux pas faire pour le moment, nous avons donc besoin d'une solution de contournement.
rafuru
4
Je ne comprends pas - pourquoi l'ajout d'un déclencheur ou l'ajout d'une autre table pour «émuler» un index prend moins de temps d'arrêt que l'ajout d'un index à la table existante?
Doc Brown
2
@rafuru: qui a dit que vous deviez créer un index unique? Un index standard et non unique sera probablement tout ce dont vous avez besoin pour trouver rapidement toutes les lignes avec la même valeur de hachage.
Doc Brown

Réponses:

3

Il existe quelques scénarios possibles qui sont faciles à résoudre et un autre pernicieux qui ne l'est pas.

Pour un utilisateur qui entre une valeur, puis saisit la même valeur quelque temps plus tard, un simple SELECT avant que INSERT détecte le problème. Cela fonctionne dans le cas où un utilisateur soumet une valeur et quelque temps plus tard, un autre utilisateur soumet la même valeur.

Si l'utilisateur soumet une liste de valeurs avec des doublons - disons {ABC, DEF, ABC} - en une seule invocation du code, l'application peut détecter et filtrer les doublons, provoquant peut-être une erreur. Vous devrez également vérifier que la base de données ne contient aucune des valeurs uniques avant l'insertion.

Le scénario délicat est lorsque l'écriture d'un utilisateur se trouve à l'intérieur du SGBD en même temps que l'écriture d'un autre utilisateur et qu'il écrit la même valeur. Ensuite, vous avez une course une condition entre eux. Étant donné que le SGBD est (très probablement - vous ne dites pas lequel vous utilisez) un système multitâche préemptif, toute tâche peut être interrompue à tout moment de son exécution. Cela signifie que la tâche de l'utilisateur1 peut vérifier qu'il n'y a pas de ligne existante, puis la tâche de l'utilisateur2 peut vérifier qu'il n'y a pas de ligne existante, puis la tâche de l'utilisateur1 peut insérer cette ligne, puis la tâche de l'utilisateur2 peut insérer cette ligne. À chaque point, les tâches sont individuellement satisfaites de faire la bonne chose. Globalement, cependant, une erreur se produit.

Habituellement, un SGBD gérerait cela en mettant un verrou sur la valeur en question. Dans ce problème, vous créez une nouvelle ligne, il n'y a donc rien à verrouiller. La réponse est un verrou de plage. Comme il le suggère, cela verrouille une plage de valeurs, qu'elles existent actuellement ou non. Une fois verrouillée, cette plage ne peut plus être accédée par une autre tâche tant que le verrou n'est pas libéré. Pour obtenir des verrous de plage, vous devez spécifier et le niveau d'isolement de SERIALIZABLE . Le phénomène d'une autre tâche se faufilant après une vérification de votre tâche est connu sous le nom d' enregistrements fantômes .

La définition du niveau d'isolement sur Sérialisable dans l'ensemble de l'application aura des implications. Le débit sera réduit. D'autres conditions de course qui fonctionnaient assez bien dans le passé peuvent commencer à montrer des erreurs maintenant. Je suggère de le définir sur la connexion qui exécute votre code induisant des doublons et de laisser le reste de l'application tel quel.

Une alternative basée sur le code consiste à vérifier après l'écriture plutôt qu'avant. Faites donc l'INSERT, puis comptez le nombre de lignes qui ont cette valeur de hachage. S'il y a des doublons, annulez l'action. Cela peut avoir des résultats pervers. Dites que la tâche 1 écrit puis la tâche 2. Ensuite, la tâche 1 vérifie et trouve un doublon. Il recule même s'il était le premier. De même, les deux tâches peuvent détecter le doublon et les deux annulations. Mais au moins, vous aurez un message à utiliser, un mécanisme de nouvelle tentative et aucun nouveau doublon. Les annulations sont désapprouvées, tout comme l'utilisation d'exceptions pour contrôler le flux du programme. Notez bien que tousle travail dans la transaction sera annulé, pas seulement l'écriture induisant un doublon. Et vous devrez avoir des transactions explicites qui peuvent réduire la concurrence. La vérification en double sera horriblement lente, sauf si vous avez un index sur le hachage. Si vous le faites, vous pouvez tout aussi bien en faire un modèle unique!

Comme vous l'avez commenté, la vraie solution est un index unique. Il me semble que cela devrait s'intégrer dans votre fenêtre de maintenance (bien que vous connaissiez bien votre système). Disons que le hachage fait huit octets. Pour cent millions de lignes, c'est environ 1 Go. L'expérience suggère qu'un peu de matériel raisonnable traiterait ces nombreuses lignes en une ou deux minutes. La vérification et l'élimination des doublons ajouteront à cela, mais peuvent être scriptées à l'avance. Ce n'est qu'un aparté, cependant.

Michael Green
la source
2

En fait, nous avons une colonne où nous stockons un hachage des données qui ne doivent pas être dupliquées mais aucun index unique n'a été défini.

La vérification des collisions de hachage est une bonne première étape, mais attention, vous ne pouvez pas garantir que le même programme produira le même hachage sur les mêmes données s'il est redémarré . De nombreuses fonctions de hachage "rapides" utilisent un prng intégré qui est initialisé au moment du démarrage du programme. Utilisez un hachage cryptographique si le hachage doit toujours être le même, quoi que vous fassiez, comme vous le faites dans cette application. Notez que vous n'avez pas besoin d'un hachage cryptographique correct ou sécurisé.

La deuxième étape consiste à vérifier réellement l'égalité des données, car même les meilleures fonctions de hachage entraîneront parfois des collisions, car vous réduisez (généralement) l'entropie de vos données.

Donc:

Étape 1: vérifiez si vous obtenez une collision sur un hachage cryptographique

Étape 2: si les hachages correspondent, vérifiez que les données réelles sont les mêmes

Turksarama
la source
Je ne vois pas comment cela répond à la question. Supposons un instant que la colonne de hachage disponible soit remplie par une fonction de hachage déterministe (sinon toute tentative de l'utiliser n'aurait aucun sens). À ma connaissance, le problème est qu'il n'y a pas d'index sur cette colonne de hachage dans la base de données, donc même la première étape de votre réponse - vérifier s'il y a une collision - nécessiterait toujours une analyse complète de la table pour chaque nouvel enregistrement sur une table avec plusieurs millions de disques, ce qui deviendra probablement beaucoup trop lent.
Doc Brown
C'est le mieux que vous puissiez faire sans créer d'index, c'est ce que la question demandait. Une analyse de hachage signifie au moins que vous n'avez qu'à vérifier une colonne, ce qui est beaucoup plus rapide que de vérifier le nombre de colonnes qu'ils auraient autrement à vérifier.
Turksarama
Je suis à peu près sûr, même lorsque la création d'un index n'est pas possible (ce qui est probablement le cas dans ce cas), la suggestion originale des OP de " créer une autre table pour stocker des index uniques pour cette table et ajouter une clé étrangère à la table principale " fait beaucoup plus de sens.
Doc Brown
Le hachage déterministe et le hachage cryptographique sont deux concepts orthogonaux, n'est-ce pas? un hachage cryptographique peut ne pas être déterministe et vice-versa, un hachage déterministe pourrait très bien ne pas avoir une force cryptographique.
Newtopian
Ce n'est pas la même chose, mais ils ne sont pas non plus orthogonaux. Les hachages cryptographiques sont un sous-ensemble de hachages déterministes, mais personne ne se soucie vraiment de créer des hachages déterministes non cryptographiques, sauf si vous voulez spécifiquement qu'il soit réversible pour une raison quelconque.
Turksarama
2

Créer une nouvelle table avec une clé primaire unique

Côté client, commencez à générer des GUID pour chaque enregistrement afin de pouvoir détecter les renvois simples.

Mettez de nouveaux enregistrements dans la nouvelle table afin qu'au moins vous soyez bon pour les nouvelles données qui arrivent.

Avoir une colonne dans la nouvelle table "CheckedAgainstOldData"

Avoir une tâche backend qui fait tout ce que vous contrôlez lentement le hachage consiste à voir s'il peut trouver un doublon dans les anciennes données et définir l'indicateur en conséquence, rejeter les doublons à ce stade, renvoyer une notification au client.

Pendant ce temps, vous avez une autre tâche principale qui déplace les données de l'ancienne vers la nouvelle table, vérifiant les doublons avec votre vérification de hachage et générant le GUID.

Vous pouvez laisser cette tâche en cours d'exécution pendant plusieurs jours (si nécessaire), en transférant les données sans interruption.

Une fois le transfert terminé, vous pouvez désactiver le processus lent "CheckedAgainstOldData". et transférer toutes les données dans une seule table.

Franchement, si le problème est aussi grave que vous le décrivez et que le logiciel est ancien, alors vous allez avoir des milliers de doublons.

Ewan
la source
1

En supposant que les données provenant de "l'utilisateur" désignent une personne assise devant un clavier et que les dupes proviennent de la saisie par deux utilisateurs des mêmes données au même moment. Essayez d'ajouter une fonction qui provoque un retard aléatoire au début du déclencheur. Donnez-lui un minimum du temps qu'il faut pour écrire un nouvel enregistrement sur la table et probablement pas plus d'un nanocentury ou plus. De cette façon, lorsque vous obtenez des demandes de dupe, la première doit être effectuée et le déclencheur d'existence doit renvoyer le résultat correct. (Clarification: chaque appel doit avoir son propre temps de retard aléatoire unique, selon les mêmes principes que le protocole ALOHA )

Gregor y
la source