Qui a besoin de linéarisation?

13

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?

Eduardo Bezerra
la source
Vous pouvez vérifier sur wikipedia: en.wikipedia.org/wiki/… , ou sur l'article de Herlihy et Wing: "Linéarisation: une condition de correction pour les objets concurrents".
Eduardo Bezerra

Réponses:

5

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.

Massimo Cafaro
la source
1
ce n'est pas une bonne réponse, car il utilise encore un autre concept inexpliqué pour expliquer le concept dans le doute .. (lire c'est une perte de temps) .. les réponses ci-dessous sont bien meilleures ...
Richard
Il semble que vous n'ayez pas lu la question OP originale. Le PO ne demandait pas ce qu'est la linéarisation, il a demandé "Qui a besoin de linéarisation"? Ma réponse est appropriée, car elle fournit au PO un exemple de scénario (au moins, il a été jugé approprié et sélectionné par le PO). Le fait que vous ne sachiez pas quelles sont les structures de données simultanées et sans attente est une question de fait entièrement différente. Soit dit en passant, le PO savait de quoi je parlais. Si nous devions expliquer chaque concept que nous utilisons dans une réponse, la réponse ne se terminera jamais ;-)
Massimo Cafaro
10

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

Logique errante
la source
Que voulez-vous dire en affirmant que `` je crois que Herlihy et Wing ont peut-être essayé de définir rigoureusement un moniteur ''? Pourriez-vous s'il vous plaît ajouter quelques détails. (Je lis le journal de Herlihy et Wing.)
hengxin
1
Je ne pense pas que je voulais dire quelque chose de profond. Avant de lire Herlihy et Wing, les choses que j'avais lues sur les moniteurs étaient toutes opérationnelles. Quelque chose comme "un moniteur est un type de données abstrait qui a implicitement un mutex et chaque méthode du type acquiert le mutex au début et libère le mutex à la fin", suivie d'une discussion compliquée sur le moment où il est correct pour wait()et notify(). La linéarisation donne un moyen de parler de l'exactitude d'implémentations de moniteur beaucoup plus compliquées / optimisées.
Wandering Logic
Ça me semble logique. THX. Aujourd'hui, j'ai lu la Related Workpartie de l'article de Herlihy et Wing. Ils ont mentionné cela monitorcomme illustration de leur affirmation Our notion of linearizability generalizes and unifies similar notions found in specific examples in the literature. Cependant, une question générale: la notion de linéarisation a-t-elle été largement adoptée dans les systèmes multiprocesseurs (par exemple, matériel, compilateur, langage de programmation et structures de données simultanées)? (Étant myope, je ne connais que des choses comme le moniteur.) Sinon, quels sont les obstacles? Quel est l'état de l'art?
hengxin
Je pense que c'est considéré comme une propriété souhaitable qui est parfois trop chère à appliquer. Voir par exemple: courses.csail.mit.edu/6.852/01/papers/p91-attiya.pdf . Aussi, dans la pratique, je pense que la plupart des hashmaps simultanés ont un verrou par compartiment, mais pas de verrou global, et peuvent donc avoir un comportement étrange à chaque fois qu'une insertion / suppression provoque le redimensionnement de la table de hachage.
Wandering Logic
Merci pour la longue réponse, mais je crains que vous ne m'ayez pas dit quand la linéarisation était intéressante, mais plutôt que vous l'avez définie et, d'ailleurs, que vous l'avez mal définie: il ne suffit pas que chaque processus voit les opérations dans l'ordre de leur délivrance. L'ordre dans tous les processus doit également être cohérent. Mais corrigez-moi si je me trompe ...
Eduardo Bezerra
2

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.

Sriram Srinivasan
la source