Qui a besoin de linéarisation?

J'ai lu sur les différences entre la sérialisation et la linéarisation , qui sont tous deux des critères de cohérence pour les systèmes répliqués tels que les bases de données répliquées. Cependant, je ne sais pas dans quels cas la linéarisation serait nécessaire, même si elle est plus forte que la sérialisation.

Pourriez-vous proposer des scénarios où une telle propriété forte serait réellement nécessaire?

Envisagez la conception de structures de données simultanées, sans attente (ou sans verrouillage, ce qui est plus faible). Dans ce scénario, la linéarisation est généralement requise, même si dans certains cas, les performances et l'évolutivité peuvent être améliorées en satisfaisant à une condition de correction plus faible. L'utilité d'une implémentation satisfaisant une condition aussi faible dépend généralement de l'application. En revanche, une implémentation linéarisable est toujours utilisable, car les concepteurs peuvent la voir comme atomique.

De plus, la linéarisation est une propriété non bloquante: une opération totale (définie pour tous les états d'objet) n'est jamais requise pour bloquer. Au lieu de cela, la sérialisation n'est pas une propriété non bloquante. Par conséquent, afin d'augmenter le degré de concurrence, les concepteurs de structures de données simultanées s'appuient toujours sur la linéarisation.

J'ai relu Herlihy et Wing plusieurs fois au cours des 15 dernières années. C'est une lecture très difficile. Et c'est dommage, car bien qu'il y ait quelques subtilités sur les bords, l'idée de base est en fait tout à fait raisonnable.

En bref: la linéarisation est comme la sérialisation, mais avec l'exigence supplémentaire que la sérialisation respecte des contraintes de commande supplémentaires entre les transactions. L'objectif est de vous permettre de raisonner rigoureusement sur une structure de données atomique individuelle plutôt que d'avoir à raisonner sur le système entier d'un seul coup.

La linéarisation est également facile à réaliser: il suffit d'associer un mutex à l'objet que vous souhaitez linéariser. Chaque transaction sur cet objet commence par verrouiller le mutex et se termine par déverrouiller le mutex.

Voici les définitions que j'utiliserai:

Un système est sérialisable s'il reçoit un ensemble de transactions sur un ensemble de données, tout résultat de l'exécution des transactions est le même que si les transactions ont été exécutées dans un ordre séquentiel et que les opérations de chaque transaction sont contenues dans leur transaction dans l'ordre spécifié par le code de la transaction.

La sérialisation interdit l'apparition de l'entrelacement des opérations entre les différentes transactions et requiert que l'ordre choisi des transactions satisfasse la causalité (si la transaction A écrit la valeur x et que la transaction B lit la valeur x que A a écrite, alors la transaction A doit précéder la transaction B dans l'ordre de série choisi.) Mais il ne dit rien sur les autres contraintes sur l'ordre des transactions (en particulier, il ne dit rien sur les processus et l'ordre dans lequel les processus perçoivent les événements.)

Il existe une autre idée connexe qui ajoute des contraintes sur l'ordre dans lequel les opérations exécutées sont traitées (mais ne parle pas des transactions uniquement des opérations de lecture / écriture individuelles):

Un système est séquentiellement cohérent si le résultat d'une exécution est le même que si les opérations de tous les processus ont été exécutées dans un certain ordre séquentiel, et les opérations de chaque processus individuel apparaissent dans cette séquence dans l'ordre spécifié par son programme. ( Lamport, "Comment faire un ordinateur multiprocesseur qui exécute correctement les programmes multiprocessus", IEEE T Comp 28: 9 (690-691), 1979 ).

La définition de la cohérence séquentielle implique implicitement que nous acceptons uniquement les ordres séquentiels où, pour chaque emplacement de mémoire (objet), l'ordre séquentiel des opérations induit obéit à la règle selon laquelle la valeur renvoyée par chaque opération de lecture à l'emplacement xdoit être la même que celle qui a été écrite par l'opération d'écriture immédiatement précédente à l'emplacement xdans l'ordre séquentiel.

La linéarisation a les bonnes intentions de (a) combiner ensemble la notion de transactions (de sérialisation) avec la notion que les processus s'attendent à ce que les opérations qu'ils émettent se terminent dans l'ordre (par cohérence séquentielle) et (b) de restreindre les critères de correction pour parler de chacun objecter isolément, plutôt que de vous forcer à raisonner sur le système dans son ensemble. (Je voudrais pouvoir dire que l'implémentation de mon objet est correcte même dans un système où il y a d'autres objets qui ne sont pas linéarisables.) Je crois que Herlihy et Wing ont peut-être essayé de définir rigoureusement un moniteur .

La partie (a) est "facile": Une exigence séquentielle de consistance serait que les transactions sur l'objet émises par chaque processus apparaissent dans la séquence résultante dans l'ordre spécifié par le programme. Une exigence de type sérialisation serait que les transactions sur l'objet s'excluent toutes mutuellement (peuvent être sérialisées).

La complexité vient de l'objectif (b) (pouvoir parler de chaque objet indépendamment de tous les autres).

Dans un système avec plusieurs objets, il est possible que les opérations sur l'objet B imposent des contraintes sur l'ordre dans lequel nous pensons que les opérations ont été appelées sur l'objet A. Si nous examinons l'historique complet du système, nous serons contraints à certains ordres séquentiels, et devra rejeter les autres. Mais nous voulions un critère d'exactitude que nous pourrions utiliser de manière isolée (raisonnement sur ce qui arrive à l'objet A sans faire appel à l'historique du système global).

Par exemple: supposons que j'essaie de discuter de l'exactitude de l'objet A, qui est une file d'attente, supposons que l'objet B est un emplacement de mémoire, et supposons que j'ai les historiques d'exécution suivants: Thread 1: A.enqueue (x), A. dequeue () (renvoie y). Thread 2: A.enqueue (y), A.dequeue () (renvoie x). Y a-t-il un entrelacement d'événements qui permettrait à cette mise en œuvre de la file d'attente d'être correcte? Oui:

Thread 1                           Thread 2
A.enqueue(x)                       ...
...                                A.enqueue(y)
...                                A.dequeue() (returns x)
A.dequeue(y) (returns y)           ...

Mais maintenant que se passe-t-il si l'historique ( y compris l'objet B ) est: B commence par la valeur 0. Thread 1: A.enqueue (x), A.dequeue () (retourne y), B.write (1). Thread 2: B.read () (renvoie 1) A.enqueue (y), A.dequeue () (renvoie x).

Thread 1                           Thread 2
A.enqueue(x)                       ...
A.dequeue() (returns y)            ...                       (uh oh!)
B.write(1)                         ...
...                                B.read() (returns 1)
...                                A.enqueue(y)
...                                A.dequeue() (returns x)

Maintenant, nous aimerions que notre définition de "l'exactitude" dise que cette histoire indique que notre implémentation de A est boguée ou notre implémentation de B est boguée, car il n'y a pas de sérialisation qui "ait du sens" (soit le Thread 2 doit être lu une valeur de B qui n'a pas encore été écrite, ou le thread 1 doit retirer une valeur de A qui n'a pas encore été mise en file d'attente.) Ainsi, alors que notre sérialisation d'origine des transactions sur A semblait raisonnable, si notre implémentation permet une histoire comme la seconde, alors elle est clairement incorrecte.

Les contraintes que la linéarisation ajoute sont donc tout à fait raisonnables (et nécessaires même pour les structures de données simples comme les files d'attente FIFO.) Ce sont des choses comme: "votre implémentation devrait interdire dequeue () une valeur qui ne sera pas mise en file d'attente () avant un certain temps dans la futur." La linéarisation est assez facile (et naturelle) à réaliser: il suffit d'associer un mutex à votre objet, et chaque transaction commence par le verrouillage et se termine par le déverrouillage. Le raisonnement sur la linéarisation commence à devenir difficile lorsque vous essayez de mettre en œuvre votre atomicité avec des techniques non bloquantes ou sans verrouillage ou sans attente au lieu de simples mutex.

Si vous êtes intéressé par certains pointeurs de la littérature, j'ai trouvé ce qui suit (même si je pense que la discussion sur le "temps réel" est l'un des red-herrings qui rendent la linéarisation plus difficile qu'elle ne devrait l'être.) Https: // stackoverflow.com/questions/4179587/difference-between-linearizability-and-serializability

Premièrement, la linéarisation et la sérialisation ne sont pas directement comparables. Comme le montre le tableau ci-dessous, la principale différence est que sur le côté gauche, toutes les opérations individuelles sont atomiques (comme avoir un javasynchronized autour de chaque op. Sur le côté droit, l'unité d'atomicité est une transaction; une opération individuelle n'est pas atomique C'est pourquoi la sérialisation a toujours fait partie de la documentation de la base de données, tandis que le côté gauche a fait l'objet de la littérature sur la mémoire du processeur (l'opération de lecture / écriture est atomique). Les magasins de valeurs-clés d'origine (tels que dbm et memcached) a commencé sur le côté gauche (get / put est atomique), mais les plus récents prennent de plus en plus en charge les transactions (telles que la clé de Google).

obj. les opérations sont atomiques | Les transactions sont atomiques
-------------------------------- + ----------------- ----------------
Linéarisation |
Cohérence séquentielle | Sérialisabilité
Cohérence causale |
Cohérence du cache |

La linéarisation nécessite qu'un système d'objets dans un paramètre simultané se comporte de la même manière qu'un système séquentiel qui gère une opération (une paire demande / réponse) à la fois - dans un univers parallèle - de telle sorte que (a) les clients dans les deux univers, voir exactement les mêmes réponses (b) l'ordre temporel est préservé (voir ci-dessous).

La définition de la sérialisation, comme la cohérence séquentielle, ne nécessite que le premier critère.

La préservation de l'ordre temporel signifie ceci: si A: x.op1 () (A est un client, x est un objet et op1 est une opération) terminée avant une autre opération B: y.op2 () a commencé, puis dans l'univers séquentiel le les demandes sont traitées dans le même ordre. Ceci n'est pas requis dans la cohérence séquentielle (SC); l'objet est autorisé à mettre en file d'attente la demande d'un client, à répondre au client, puis à l'évaluer plus tard. De plus, l'objet peut gérer une demande ultérieure d'un autre client hors tour, l'évaluant avant de passer au premier.

La non-préservation de l'ordre temporel est un problème. Après A: x.op1 (), supposons que A décroche le téléphone et en parle à B, puis B appelle x.op2 (). Il n'y a aucun moyen pour le système de connaître cette chaîne d'événements causale, car la deuxième étape impliquait un message non suivi par le système. Dans de nombreux cas réels, il n'est pas déraisonnable pour A de supposer qu'une fois que x y a répondu, l'invocation de B peut s'appuyer sur l'état mis à jour. Si l'ordre temporel n'a pas été préservé, A et B sont pour une surprise. Cela ne se produirait pas dans un système linéarisable.

La deuxième belle propriété de la préservation de l'ordre temporel est la localité et la compositionnalité, qu'un système construit d'objets linéarisables est lui-même linéarisable. Ainsi, au lieu d'avoir un magasin de valeurs-clés monolithique, vous pouvez le scinder en plusieurs partitions distinctes chacune gérée par son propre serveur de magasin KV; si chacun d'eux est linéarisable, la base de données entière fonctionne comme un magasin KV monolithique linéarisable, sans effort supplémentaire.