La concurrence optimiste par objet implique-t-elle une sérialisation si une transaction ne s'étendra jamais sur plusieurs objets?

13

Étant donné un système qui fournit:

  • Contrôle de concurrence / versionnage optimiste par objet (en utilisant CAS - Check-and-Set)
  • Transactions qui n'ont jamais besoin de s'étendre sur plus d'un seul objet.
  • Isolement de l'instantané

Ce système est-il considéré comme sérialisable ?

De l' isolement de l'instantané

Dans une anomalie d'écriture asymétrique, deux transactions (T1 et T2) lisent simultanément un ensemble de données qui se chevauchent (par exemple, les valeurs V1 et V2), effectuent simultanément des mises à jour disjointes (par exemple, les mises à jour T1 V1, T2 les mises à jour V2), et finalement valident simultanément, sans avoir vu la mise à jour effectuée par l'autre. Si le système était sérialisable, une telle anomalie serait impossible, car T1 ou T2 devraient se produire "en premier" et être visibles par l'autre. En revanche, l'isolement de l'instantané permet des anomalies d'écriture asymétrique.

À titre d'exemple concret, imaginez que V1 et V2 sont deux soldes détenus par une seule personne, Phil. La banque permettra à V1 ou V2 de présenter un déficit, à condition que le total détenu dans les deux ne soit jamais négatif (c'est-à-dire V1 + V2 ≥ 0). Les deux soldes sont actuellement de 100 $. Phil initie deux transactions simultanément, T1 retirant 200 $ du V1 et T2 retirant 200 $ du V2.

Sur la base de cela, il semble que le potentiel de décalage d'écriture soit la seule raison pour laquelle un système garantissant que l'isolement de l'instantané n'est pas sérialisable.

Cependant, dans un système qui ne permet pas à une transaction de s'étendre sur plusieurs objets (dans les exemples ci-dessus V1 et V2), il semble impossible qu'un décalage d'écriture se produise.

Par conséquent, le système décrit ci-dessus est sérialisable. Est-ce correct?

Geert-Jan
la source
1
Je pense que la réponse est oui, à condition que la base de données soit autorisée à abandonner les transactions qui autrement introduiraient un biais d'écriture - si les transactions sont limitées à la lecture / écriture d'un seul objet, alors elles sont disjointes ou en collision.
pjc50
2
Je pense que vous auriez également besoin d'un moyen d'empêcher les enregistrements en double pour une validation initiale. Dans ce cas, deux écrivains optimistes pouvaient chacun voir un instantané vide et que l'enregistrement était nouveau et donc vous pouviez avoir deux objets, chacun à la version 0.
Matthew Mark Miller

Réponses:

1

Non, je ne pense pas que vos stipulations aboutissent à un système que nous devrions considérer sérialisable.

L'isolement d'instantané est une technique qui garantit qu'une transaction voit le même ensemble de données tout au long de la transaction. L'isolement de cliché offre certaines garanties mais ne définit pas toutes les caractéristiques nécessaires pour comprendre comment les transactions fonctionnent réellement (sauf si nous choisissons de confondre l'isolement de cliché et MVCC).

L'isolement de cliché est le plus souvent implémenté à l'aide de MVCC, Multi Version Consistency Control. MVCC définit plus en détail les transactions dans le contexte de leurs instantanés: il est dit qu'elles ne nécessitent d'isolement qu'en cas de conflit d'écriture (emplacements uniquement, ou, emplacements + valeurs, selon l'implémentation). MVCC fournit un modèle de cohérence détendu et souffre d'un biais d'écriture.

Les modèles de cohérence détendue sont difficiles à comprendre car ils sont comme un hybride entre l'absence d'isolement et l'isolement complet.

Commençons donc par un modèle de concurrence stricte en premier. Deux transactions doivent être isolées l'une de l'autre si l'une écrit sur des données que l'autre lit ou écrit (et vice versa ...).

Lorsque nous ne savons pas pourquoi une transaction lit des données, nous devons présumer qu'une valeur différente lue peut modifier le comportement du client impliqué, c'est pourquoi la condition de chevauchement des transactions indique l'isolement. Sans isolement, une lecture de données périmées dans un instantané peut facilement présenter une cohérence détendue, un autre terme pour lequel il s'agit d'incohérence, c'est-à-dire d'erreur.

Nous devons seulement considérer les données exactes lues ou écrites par les transactions, aucune donnée en dehors de cet ensemble n'a besoin d'être prise en compte. Cependant, il est essentiel de réaliser que lorsque nous parlons de données lues par une transaction, nous devons nécessairement inclure toutes les "métadonnées" (et les données et métadonnées lues par des métadonnées telles que la vérification des contraintes). Des exemples de métadonnées sont / les opérations de métadonnées sont: l'identification d'une nouvelle clé primaire unique; un autre est la somme d'une colonne entière; une autre consiste à rechercher quelque chose et à ne pas le trouver; recherches de gamme ou sommes. Cela va au commentaire de @ Matthew sur la prévention des doublons, ainsi qu'à la réponse de @Tersosauros, dans laquelle il considère l'état.

Par exemple, cela signifie que deux transactions se chevauchent (nécessitent une isolation) lorsqu'elles insèrent toutes deux une ligne (en supposant une contrainte de clé primaire unique) car la vérification de la contrainte de clé est synonyme de lecture de la colonne de clé primaire entière. Comme autre exemple, rechercher quelque chose et le trouver, c'est comme lire cette valeur, mais ne pas le trouver, c'est comme regarder chaque valeur de la colonne.

MVCC protège uniquement contre les écritures qui se chevauchent ou sont en conflit, mais ne protège pas contre les lectures (sauf si elles sont également écrites par cette transaction). Ainsi, pour obtenir une erreur de cohérence dans MVCC, tout ce que nous devons faire est de lire quelque chose qui est modifié par une autre transaction (où l'autre transaction se produit après que l'instantané de l'ancien est obtenu, mais se valide en premier), tandis que l'autre transaction continue d'utiliser des données périmées et prend toute décision différemment sur la base de ces données périmées par rapport à ce qu'il aurait fait des données à jour. C'est plus facile à provoquer que vous ne le pensez.

La cohérence détendue est une autre façon de dire potentiellement incohérente ou sujette aux erreurs. (La cohérence décontractée ne doit pas être confondue avec la cohérence éventuelle, qui est une autre forme d'erreurs populaire différente de "NoSQL".)

Sur votre question, lorsque vous dites que les transactions ne doivent jamais s'étendre sur plus d'un objet, cela doit s'appliquer aux lectures et aux écritures, ainsi qu'aux métadonnées (et aux métadonnées), y compris la vérification de cohérence, les agrégats de colonnes entières, les vérifications d'absence, les recherches de plage, etc. .: si oui, alors jusqu'ici tout va bien.

Pourtant...

J'en déduis de votre question que vous utilisez l'isolement d'instantané (MVCC) sur des objets individuels (disons plutôt que le verrouillage d'objet). (Vous mentionnez également CAS; j'ai entendu parler de comparaison et d'échange, et de test et de réglage, mais pas de contrôle et de réglage, même si je suppose que c'est similaire).

La rédaction de votre question me suggère que les "objets" ont plus d'un champ, sinon les stipulations de la question seraient inutiles.

Par conséquent, étant donné que vos objets gérés par un instantané / gérés par MVCC ont plusieurs champs, vous êtes enclin à écrire un biais dans des objets uniques. Si deux transactions mettent à jour le même objet en même temps, on peut lire un champ de la valeur de l'objet rendu obsolète par une autre transaction simultanée sur le même objet, et continuer sans savoir, donc, l'incohérence potentielle (aka erreur).

Vous pouvez utiliser le verrouillage d'objet à la place, ce qui empêcherait deux transactions (pour la mise à jour) de même regarder le même objet si une autre transaction était déjà en train de le faire.

Je crois qu'une autre forme d'isolement de cliché peut être effectuée sans utiliser le modèle de comparaison en écriture uniquement cassé de MVCC. Ainsi, vous pouvez (algorithmiquement) promouvoir l'ensemble de comparaison à partir de l'écriture seule pour inclure également l'ensemble de lecture. Ensuite, deux transactions mettant à jour le même objet ne seraient pas en mesure de provoquer un décalage d'écriture (car celle qui tenterait de valider plus tard serait abandonnée). Je pense que cela peut être la solution appropriée au problème que vous décrivez, car vous obtenez déjà la plupart des avantages que MVCC nous achèterait, en empêchant les transactions multi-objets.

(Nous devons seulement considérer les éléments / champs exacts et spécifiques lus ou écrits, mais nous devons inclure ceux lus en tant que métadonnées, potentiellement pendant les méta-opérations pour éviter un biais d'écriture (c'est-à-dire une erreur). Si nous supprimons le jeu de lecture du jeu de comparaison , ou si nous ne prenons pas en compte les métadonnées (potentiellement utilisées par les méta-opérations), nous avons alors un modèle qui permettra l'erreur.)

Erik Eidt
la source
0

Je pense, comme l'a déclaré @ pjc50 , ( Je souligne :) " si les transactions se limitent à lire / écrire un seul objet" alors "la réponse est oui". Cependant, je pense que là où cela tombe, c'est dans l'idée d'un seul objet.

Dans l'exemple tiré de l' isolement de capture instantanée , T1 et T2 ne partagent aucune valeur. Cependant, ils sont encore un potentiel pour un biais d'écriture parce que " ni [n'a] vu la mise à jour effectuée par l'autre " source . C'est donc la capacité d'une transaction à voir toutes les autres mises à jour avant de valider qui rend une transaction vraiment sérialisable.

De la sérialisation :

La sérialisation d'une planification signifie l'équivalence (dans le résultat, l'état de la base de données, les valeurs des données) à une planification en série (c'est-à-dire séquentielle sans chevauchement de transactions dans le temps) avec les mêmes transactions.

Malheureusement, à cause de cela (et comme le souligne @Matthew Mark Miller ), nous devons également prendre en compte l' état ainsi que les valeurs. Avec cette considération, deux transactions utilisant OCC auraient le potentiel de biais d'écriture chaque fois qu'un état de base de données est écrit .

Tersosauros
la source