Bonjour à tous!
Aujourd'hui, nous aimerions aborder une fois de plus le sujet de l'exécution simultanée et séquentielle dans divers programmes, en particulier dans les systèmes distribués. En septembre dernier, nous avons publié un article «La
synchronicité est un mythe » sur ce sujet et nous publions maintenant la traduction d'une étude plus sérieuse qui, nous l'espérons, vous aidera à mieux naviguer dans les systèmes distribués.
Il n'y a qu'un seul vrai problème en informatique: admettre que les erreurs d'invalidation du cache sont mal nommées. Ce ne sont que des erreurs unitaires liées à l'utilisation du temps.
- Auteur inconnu
Le temps est une chose étrange.
Cette fois est si étrange, parce que nous voulons vraiment, vraiment croire qu'elle est complètement rationalisée. Il nous semble que tout événement à 15h00 se produit (comme nous le dirions) avant tout événement à 16h00 - sans exceptions, arguments ou compromis.
Cependant, l'informatique connaît de nombreux exemples lorsqu'il est nécessaire d'aborder cette exigence de manière moins stricte. Il se manifeste au niveau des processeurs, des compilateurs, des nœuds de réseau. Encore et encore dans les calculs, à différents niveaux de la pile, nous nous retrouvons dans des situations où nous sommes confrontés à deux événements, et nous ne savons pas dans quel ordre ils se sont produits. Le temps n'est évidemment pas total; elle est fragmentée.
Pourquoi? Le fait est que nous ne le savons pas, car le niveau d'abstraction sur lequel nous existons ne fournit pas de réponse à cette question. Qu'elle soit accidentelle ou non, nos abstractions de calcul ne donnent aucune garantie quant à la procédure. La liberté de réorganiser les événements vous permet souvent de créer des systèmes beaucoup plus productifs et abordables.
Le processeur peut avoir un
modèle de commande de mémoire ; il reflète les garanties que le processeur ne veut pas vous donner de garanties au stade de l'assemblage - par exemple, quelle instruction a été exécutée plus tôt et laquelle plus tard. Le processeur décide exactement comment transmettre les instructions et les exécute dans le désordre - c'est-à-dire qu'il utilise ses puces plus efficacement que je ne l'aurais pensé.
Un langage peut avoir un
modèle de correspondance de mémoire («modèle de mémoire» pour faire court); il reflète les garanties que le langage ne vous donne pas lors de la génération d'un assembly, par exemple, lors de la distribution d'instructions sur plusieurs threads. Une telle réorganisation est par définition inhérente au modèle matériel de la mémoire et explique dans une large mesure pourquoi un tel concept de temps «faible» est fourni dans les compilateurs. C'est dans le cadre d'un tel modèle de mémoire implémenté dans le langage que vous programmez lorsque vous écrivez du code non bloquant.
Un exemple célèbre d'un modèle de mémoire implémenté au niveau du langage est le
modèle de mémoire forte et faible dans la norme C ++ 11. Par défaut, C ++ fournit des opérations atomiques avec synchronisation, mais il peut également affaiblir le modèle d'accès à la mémoire pour améliorer les performances. Le comportement ainsi fourni est destiné à servir d'abstraction aux principales architectures de processeur utilisées aujourd'hui (x86, POWER et ARM).
Enfin, un système distribué peut avoir son propre modèle de cohérence; il reflète les garanties que le système ne va pas vous donner concernant l'ordre des événements sur les clients et les répliques du réseau informatique mondial. Les réordonnances qui sont directement liées à la latence de communication ou au manque de synchronisation expliquent principalement pourquoi dans un système distribué, vous ne pouvez pas vous passer du modèle de temps faible mentionné. C'est ce modèle de cohérence que vous programmez lorsque vous écrivez une application distribuée.
Dans la pratique, il existe un énorme
zoo de modèles de cohérence que vous pouvez utiliser lors de la programmation d'un système distribué. Dans toutes ces situations, ces modèles décrivent le comportement (souhaité) du système observé de l'extérieur de ce système. Si je - un client ou un flux spécifique - écris une valeur, puis la lis immédiatement, est-il garanti que je verrai définitivement un enregistrement pas plus ancien que le mien? Si le temps n'était pas fragmenté, si nous avions toujours une idée claire de l'ordre dans lequel se déroulent les opérations dans notre système - naturellement, la réponse à cette question serait affirmative. Il serait étrange de poser une telle question.
Mais le temps est fragmentaire - il est donc nécessaire de soulever une telle question.
Modèles de cohérence - je veux dire, modèles de mémoire
Parler d'un ordre aussi fragmenté est souvent difficile et toujours désagréable. Nous voudrions partir du fait qu'à tous les niveaux de la pile, le temps est toujours absolument absolu - que ce soit avec des transactions ACID ou des opérations / verrous atomiques. Plus les garanties sont strictes, plus il est naturellement facile de programmer avec elles!
Mais nous aspirons tous à la vitesse. Qu'il s'agisse de systèmes distribués où il est nécessaire de sacrifier une cohérence stricte pour des raisons de disponibilité, ou de programmation non bloquante, où un modèle de mémoire faible est utilisé pour éviter les coûts de synchronisation, il est généralement conseillé pour un programmeur travaillant avec n'importe quel niveau de la pile d'aller dans ces arguments complexes. .
La cohérence des modèles de mémoire partagée et la cohérence des modèles de mémoire distribuée sont toutes deux
abstraites . Ils décrivent le programmeur travaillant avec le système, l'interface de ce système. Ils permettent de comprendre quels types de comportements correspondent à un modèle de mémoire faible, étant donné que les propriétés générales de l'ordre des événements dans le système, que nous tenons pour acquis, n'y agissent plus. Il peut sembler que ces deux modèles de mémoire sont similaires, cependant, les deux communautés ont développé leurs propres discours de discussion. Les valeurs utilisées diffèrent, bien qu'elles se chevauchent.
Nous imaginons déjà à quel point cela peut être confus. Que faire?
Description du temps en tant qu'entité, impliquant entre deux et huit types d'ordre partiel
Dans
son livre de 2014, Sebastian Burkhardt cherche à fournir une description exhaustive des nombreuses options de modèles de cohérence. Avec cette caractéristique, ainsi que d'autres structures mathématiques, deux variantes de l'ordre logique des événements sont utilisées: «visibilité» et «arbitrage», précédemment également mentionnées dans d'autres travaux de Burkhardt et al, voir, par exemple, l'
article sur le pointage et la vérification types de données répliquées (2014).
La «visibilité» est un ordre partiel inhérent au conditionnement potentiel. Il vous permet de suivre quels événements (éventuellement dans d'autres répliques) sont visibles pour quels autres événements. Il n'y a aucune exigence de visibilité autre que l'acyclicité; les événements d'un objet peuvent être visibles par les événements d'un autre objet, et l'opération de lecture ou d'écriture d'un événement n'affecte pas sa visibilité pour les autres événements.
«L'arbitraire» est un ordre général qui vous permet de suivre comment un système distribué dans lequel une situation de choix se produit jugera quel événement se produit plus tôt et lequel plus tard.
Étant donné que les modèles de cohérence distribuée sont similaires aux modèles de mémoire, il s'avère que de tels phénomènes de visibilité et d'aléatoire peuvent également être utiles lors de l'examen des modèles de mémoire. En particulier,
dans l'annexe de son article de 2014, Burkhardt démontre "à quel point" le modèle de mémoire faible de C ++ 11 est à la cohérence objet par causalité, mais avec quelques écarts intéressants. Cela sera discuté dans la suite de l'article.
Pour commencer, étoffons la visibilité et l'aléatoire, en tenant compte de la «lecture» et de «l'ordre des changements». Lors de la «lecture», la visibilité entre deux objets quelconques ne sera prise en compte que dans les situations où la lecture et l'écriture touchent le même objet, et lors de la lecture d'un seul enregistrement (ou plusieurs) peut être visible.
Cela correspond à une situation dans laquelle un processeur avec une mémoire partagée à un moment donné peut enregistrer des informations dans une seule cellule de mémoire pour un objet particulier, même si différents threads peuvent y accéder à différents moments de cause à effet (d'autre part, dans un système distribué, la logique un objet peut être enregistré immédiatement dans de nombreuses répliques distinctes).
L '«ordre de modification» correspond à la même étape de concrétisation de l'arbitraire, il est objectif et ne permet que des enregistrements. Encore une fois, cette spécialisation est basée sur le fait qu'avec une spécification de mémoire faible, les garanties catégorielles ne sont données qu'au niveau d'un objet.
Ensuite, discutons des axiomes de cohérence formulés par Burkhardt et al. Et voyons comment ils s'appliquent à un modèle de mémoire faible. Remarque: même en dépit du mot «axiomes», ce sont simplement des propriétés qui peuvent ou non être fournies dans divers modèles de mémoire. L'article de Burkhardt se concentre sur les propriétés qui déterminent la causalité inter-objets.
La cohérence finalement
Pour un événement particulier, il ne peut y avoir un nombre indéfini d'événements qui ne le voient pas. Autrement dit, tout événement
est finalement visible pour le système.
La construction logique de telles conditions dans un système avec un modèle de mémoire faible devrait être un peu plus difficile: il faut soutenir que pour un
enregistrement particulier
, il ne peut pas y avoir un nombre infini d'opérations de lecture qui ne liraient pas cet enregistrement ou des enregistrements antérieurs (dans l'ordre de modification).
Dans la spécification C ++ 11, la conformité à cet axiome n'est pas garantie, bien qu'en pratique il soit difficile de trouver un contre-exemple.
Cohérence éthérée
Lors du suivi de la «conditionnalité potentielle» au niveau des flux / opérations client et en ce qui concerne la visibilité / lisibilité, vous devez comprendre qu'il n'y a pas de temps de retour. C'est pourquoi il est nécessaire que les fermetures lors de la commande des flux impliquant une lecture soient acycliques. En règle générale, il ne fait aucun doute que cette propriété sera observée dans les systèmes distribués, mais c'est cette propriété qui ne permet pas la visibilité de l'utilisateur dans certaines versions spéculatives si le système a un modèle de mémoire faible.
Burkhardt et al soulignent que cet axiome n'est "pas confirmé" dans la spécification C ++ 11, et il n'est pas clair "ne valide pas" si "des cycles satisfaisants" peuvent être
observés dans la pratique .
Axiomes de conditionnalité
Pour spécifier exactement à quoi le phénomène de conditionnalité se rapporte dans un modèle de mémoire faible, nous devons déterminer précisément quels événements peuvent influencer les résultats de quels autres événements. Pour commencer, considérons nos axiomes de cause à effet standard:
garanties de session . Ce sont quatre qualités interdépendantes reflétant les propriétés de cohérence des opérations de lecture et d'écriture qui se produisent dans différents flux, de plus, elles doivent être spécifiées au niveau de chaque objet (voir
Burkhardt et al .,
Fig.23 ).
- RYW (Lire vos enregistrements): l'opération de lecture suivant l'opération d'écriture se fait dans la même cellule, au sein du même flux / réplique / session, elle doit lire des données non moins pertinentes que l'enregistrement. La variante de cette propriété pour les systèmes distribués est spécifiée exclusivement en termes de visibilité, tandis que la variante pour un modèle de mémoire faible doit être basée à la fois sur l'ordre de lecture et sur l'ordre de changement.
- RM (lectures monolithiques): les lectures suivantes (dans le même flux, dans la même cellule) devraient également voir des données non moins pertinentes à l'avenir.
- WFR (d'abord lu, puis écrit): si l'écriture suit la lecture dans le flux, dans la même cellule, alors dans l'ordre des changements elle devrait aller plus tard que l'opération de lecture.
- MW (Monolithic Records): les enregistrements ultérieurs (au sein du flux, dans la même cellule) devraient aller plus tard dans l'ordre de modification.
Les versions originales de WFR et MW existent en deux versions, pour le hasard et la visibilité; mais cela n'est important que lorsque vous travaillez avec des cellules de données plus complexes qu'avec des registres d'entiers.
Ces propriétés reflètent les notions de conditionnalité, conformes à notre bon sens; cependant, ils manquent le plus intéressant. En particulier, lors de l'analyse dans un modèle de mémoire faible, ces phénomènes de conditionnalité sont limités par les limites du flux / réplique / session et de la cellule / objet spécifique où l'entrée est effectuée:
dans un article de Burkhardt et al . dans ce cas, on parle de «visibilité conditionnelle objet par condition» et «arbitraire arbitraire objet par condition», voir également fig. 23. Ces phénomènes ne limitent pas complètement le comportement du système lorsque différents flux écrivent des informations dans différentes cellules.
Ensuite, les axiomes du conditionnement inter-objets décrivent l'effet des relations de cause à effet au niveau de divers objets / cellules de mémoire.
- COCV (Cross-Object Conditional Visibility): le même cas que RYW, mais sans la condition que la lecture finale doit être faite tout dans le même thread / réplique / session. Les lectures d'un objet qui sont objectivement postérieures aux enregistrements de cet objet devraient prendre des données non moins pertinentes que celles entrées lors de l'enregistrement.
La spécification C ++ 11 reflète ces propriétés. Veuillez noter: ils sont définis de telle manière que les restrictions sur la visibilité de l'enregistrement et l'arbitraire de l'ordre de modification ne reflètent pas trop ces définitions.
Mais cela ne s'applique pas à cette dernière propriété.
- COCA (Cross-Object Conditional Arbitrary): similaire aux enregistrements monolithiques, mais s'applique à différents flux, similaire au COCV - c'est RYW pour différents flux. Cependant, étant donné que l'ordre de modification n'affecte que les enregistrements d'un seul objet, la formulation d'un modèle de mémoire faible permet au système d'avoir une distribution incohérente des événements d'enregistrement dans différents objets, et les enregistrements peuvent ne correspondre ni aux lectures ni à l'ordre à l'intérieur du flux.
Plus précisément, COCA dans un modèle de mémoire faible est une propriété beaucoup plus faible. C'est pourquoi avec un modèle de mémoire faible, le code suivant peut retourner
{x ≡ 0, y ≡ 0} .
Thread A: y := 0; x := 1; return x
Thread B: x := 0; y := 1; return yL'ordre dans chaque flux peut être incompatible avec l'ordre objet par ordre et l'ordre de modification. Attention: avec RYW il n'y a pas
x := 0 → x := 1 dans l'ordre de modification et pour
y la même chose; ainsi, l'ordre de modification doit contenir
x := 1 → x := 0 et
y := 1 → y := 0 . Ainsi, l'ordre de modification forme évidemment un cycle dans l'ordre des flux.
Une telle boucle est autorisée dans COCA avec un modèle de mémoire faible. Ce n'est pas que l'ordre des flux / lectures est contraire à l'ordre de modification, mais que chaque flux voit un historique d'enregistrement cohérent. Ces histoires ne sont cohérentes avec les histoires d'autres flux que si nous limitons objectivement la portée de leur application.
Qu'est-ce que tout cela signifie?
Le temps est fragmenté.
Même s'il nous semble que le temps s'écoule de manière très ordonnée, l'étude des systèmes distribués et d'un modèle de mémoire faible vous montre clairement que ce n'est pas le cas. C'est pourquoi dans ces deux situations, notre sur-approximation standard, selon laquelle le temps est total, limite les performances - que nous ne pouvons pas nous permettre.
Puis, reconnaissant que le temps est vraiment fragmenté, nous trouvons de nombreuses petites mais importantes différences entre les variétés d'une telle partialité. Même les deux domaines mentionnés ci-dessus, qui semblent si similaires à première vue, dans de nombreuses nuances subtiles, permettent de distinguer quels types particuliers d'événements sont considérés comme affectant mutuellement.
Il est nécessaire de comprendre plus en détail les détails techniques de diverses propriétés déjà après que quelqu'un puisse exprimer les propriétés d'un champ dans la langue d'un autre.
Le temps est fragmenté. Peut-être que nous devons juste nous y habituer.