Die Zeit ist fragmentiert; ein bisschen über die Ähnlichkeit verteilter Systeme und ein schwaches Speichermodell

Hallo an alle!

Heute möchten wir noch einmal auf das Thema der gleichzeitigen und sequentiellen Ausführung in verschiedenen Programmen, insbesondere in verteilten Systemen, eingehen. Bereits im September haben wir einen Artikel zu diesem Thema veröffentlicht: „ Synchronizität ist ein Mythos “. Jetzt veröffentlichen wir eine Übersetzung einer ernsthafteren Studie, die Ihnen hoffentlich dabei helfen wird, verteilte Systeme besser zu navigieren.

In der Informatik gibt es nur ein wirkliches Problem: zuzugeben, dass Cache-Ungültigkeitsfehler falsch benannt sind. Dies sind nur Einheitenfehler im Zusammenhang mit der Zeitnutzung.

- Unbekannter Autor

Zeit ist eine seltsame Sache.

Diese Zeit ist so seltsam, weil wir wirklich, wirklich glauben wollen, dass sie vollständig rationalisiert ist. Es scheint uns, dass jedes Ereignis um 15.00 Uhr (wie wir sagen würden) vor jedem Ereignis um 16.00 Uhr stattfindet - ohne Ausnahmen, Argumente oder Kompromisse.

Die Informatik kennt jedoch viele Beispiele, wenn es notwendig ist, diese Anforderung nicht so streng anzugehen. Es manifestiert sich auf der Ebene von Prozessoren, Compilern und Netzwerkknoten. Bei den Berechnungen befinden wir uns auf verschiedenen Ebenen des Stapels immer wieder in Situationen, in denen wir mit zwei Ereignissen konfrontiert sind und nicht wissen, in welcher Reihenfolge sie aufgetreten sind. Die Zeit ist offensichtlich nicht total; sie ist fragmentiert.

Warum? Tatsache ist, dass wir dies nicht wissen, da die Abstraktionsebene, über die wir existieren, keine Antwort auf diese Frage liefert. Unabhängig davon, ob es sich um einen Zufall handelt oder nicht, geben unsere rechnerischen Abstraktionen keine Garantie für das Verfahren. Durch die Freiheit, Ereignisse neu zu ordnen, können Sie häufig viel produktivere und kostengünstigere Systeme erstellen.

Der Prozessor kann ein Speicherordnungsmodell haben ; Es spiegelt wider, welche Garantien der Prozessor Ihnen in der Phase der Montage keine Garantien geben möchte - zum Beispiel, welche Anweisung früher und welche später ausgeführt wurde. Der Prozessor entscheidet genau, wie die Anweisungen übermittelt werden sollen, und führt sie nicht in der richtigen Reihenfolge aus - das heißt, er verwendet seine Chips effizienter als ich gedacht hätte.

Eine Sprache kann ein Speicheranpassungsmodell haben (kurz „Speichermodell“); Es spiegelt wider, welche Garantien die Sprache beim Generieren einer Assembly nicht bietet, z. B. beim Verteilen von Anweisungen auf mehrere Threads. Eine solche Neuordnung ist per Definition dem Hardwaremodell des Speichers inhärent und erklärt weitgehend, warum ein solches "schwaches" Zeitkonzept in Compilern bereitgestellt wird. Es ist im Rahmen eines solchen Speichermodells in der Sprache implementiert, die Sie programmieren, wenn Sie nicht blockierenden Code schreiben.

Ein berühmtes Beispiel für ein auf Sprachebene implementiertes Speichermodell ist das starke und schwache Speichermodell im C ++ 11-Standard. Standardmäßig bietet C ++ atomare Operationen mit Synchronisation, kann jedoch auch das Speicherzugriffsmodell schwächen, um die Leistung zu verbessern. Das auf diese Weise bereitgestellte Verhalten soll als Abstraktion über die heute verwendeten Hauptprozessorarchitekturen (x86, POWER und ARM) dienen.

Schließlich kann ein verteiltes System ein eigenes Konsistenzmodell haben. Es spiegelt wider, welche Garantien das System Ihnen in Bezug auf die Reihenfolge der Ereignisse auf Clients und Replikaten im globalen Computernetzwerk nicht geben wird. Nachbestellungen, die in direktem Zusammenhang mit Kommunikationslatenz oder mangelnder Synchronisation stehen, erklären hauptsächlich, warum Sie in einem verteilten System nicht auf das erwähnte schwache Zeitmodell verzichten können. Dieses Konsistenzmodell programmieren Sie, wenn Sie eine verteilte Anwendung schreiben.

In der Praxis gibt es einen riesigen Zoo von Konsistenzmodellen, die Sie beim Programmieren eines verteilten Systems verwenden können. In all diesen Situationen beschreiben diese Modelle das (gewünschte) Verhalten des Systems, das von außerhalb dieses Systems beobachtet wird. Wenn ich - ein bestimmter Client oder ein bestimmter Stream - einen Wert schreibe und ihn dann sofort lese, ist dann garantiert, dass ich definitiv einen Datensatz sehe, der nicht älter als meiner ist? Wenn die Zeit nicht fragmentiert wäre, wenn wir immer eine klare Vorstellung davon hätten, in welcher Reihenfolge die Operationen in unserem System ablaufen - wäre die Antwort auf diese Frage natürlich positiv. Es wäre seltsam, überhaupt eine solche Frage zu stellen.

Aber die Zeit ist fragmentarisch - daher ist es notwendig, eine solche Frage zu stellen.

Konsistenzmodelle - ich meine Speichermodelle

Über solch eine fragmentierte Ordnung zu sprechen ist oft schwierig und immer unangenehm. Wir möchten von der Tatsache ausgehen, dass auf allen Ebenen des Stapels die Zeit immer absolut absolut ist - ob bei ACID-Transaktionen oder atomaren Operationen / Sperren. Je strenger die Garantien, desto einfacher ist es natürlich, mit ihnen zu programmieren!

Aber wir alle streben nach Geschwindigkeit. Unabhängig davon, ob es sich um verteilte Systeme handelt, bei denen die strikte Konsistenz für die Barrierefreiheit geopfert werden muss, oder um nicht blockierende Programmierung, bei der ein schwaches Speichermodell verwendet wird, um Synchronisationskosten zu vermeiden, ist es normalerweise für einen Programmierer, der mit einer beliebigen Ebene des Stapels arbeitet, ratsam, auf diese komplexen Argumente einzugehen .

Die Konsistenz von Shared-Memory-Modellen und die Konsistenz von Distributed-Memory-Modellen sind beide abstrakt . Sie beschreiben den mit dem System arbeitenden Programmierer, die Schnittstelle dieses Systems. Sie ermöglichen es zu verstehen, welche Verhaltensweisen einem schwachen Speichermodell entsprechen, da die von uns als selbstverständlich vorausgesetzten allgemeinen Eigenschaften der Reihenfolge von Ereignissen im System nicht mehr darin wirken. Es scheint, dass diese beiden Gedächtnismodelle ähnlich sind, beide Gemeinschaften haben jedoch ihre eigenen Diskurse zur Diskussion entwickelt. Die in ihnen verwendeten Werte unterscheiden sich, obwohl sie sich überschneiden.

Wir stellen uns bereits vor, wie verwirrt das sein kann. Was tun?

Beschreibung der Zeit als Einheit, die zwei bis acht Arten von Teilordnungen impliziert

Sebastian Burkhardt versucht in seinem Buch von 2014, die vielen Optionen für Konsistenzmodelle ausführlich zu beschreiben. Mit dieser Eigenschaft werden zusammen mit anderen mathematischen Strukturen zwei Varianten der logischen Reihenfolge von Ereignissen verwendet: "Sichtbarkeit" und "Arbitrierung", die zuvor auch in anderen Arbeiten von Burkhardt et al. Erwähnt wurden, siehe zum Beispiel den Artikel über Zeigen und Prüfen replizierte Datentypen (2014).

"Sichtbarkeit" ist eine Teilordnung, die einer möglichen Konditionierung innewohnt. Sie können verfolgen, welche Ereignisse (möglicherweise in anderen Replikaten) für welche anderen Ereignisse sichtbar sind. Es gibt keine anderen Anforderungen an die Sichtbarkeit als die Azyklizität. Ereignisse in einem Objekt können für Ereignisse in einem anderen Objekt sichtbar sein, und das Lesen oder Schreiben eines Ereignisses hat keinen Einfluss auf dessen Sichtbarkeit für andere Ereignisse.

"Willkür" ist eine allgemeine Reihenfolge, mit der Sie verfolgen können, wie ein verteiltes System, in dem eine Situation der Wahl auftritt, beurteilt, welches Ereignis früher und welches später eintritt.

Da verteilte Konsistenzmodelle Speichermodellen ähnlich sind, stellt sich heraus, dass solche Phänomene der Sichtbarkeit und Zufälligkeit auch bei der Erörterung von Speichermodellen nützlich sein können. Insbesondere im Anhang zu seinem Artikel von 2014 zeigt Burkhardt, "wie nahe" das schwache Speichermodell von C ++ 11 an der objektbasierten kausalen Konsistenz liegt, jedoch mit einigen interessanten Abweichungen. Dies wird im Rest des Beitrags besprochen.

Lassen Sie uns zunächst Sichtbarkeit und Zufälligkeit unter Berücksichtigung von „Lesen“ und „Reihenfolge der Änderungen“ ausarbeiten. Beim „Lesen“ wird die Sichtbarkeit zwischen zwei beliebigen Objekten nur in Situationen berücksichtigt, in denen sowohl Lesen als auch Schreiben dasselbe Objekt berühren und beim Lesen nur ein Datensatz (oder mehrere) sichtbar sein kann.
Dies entspricht einer Situation, in der ein Prozessor mit gemeinsam genutztem Speicher zu einem bestimmten Zeitpunkt Informationen in nur einer Speicherzelle für ein bestimmtes Objekt aufzeichnen kann, selbst wenn verschiedene Threads zu unterschiedlichen Zeitpunkten für Ursache und Wirkung darauf zugreifen können (andererseits in einem verteilten System die logische Ein Objekt kann sofort in vielen separaten Repliken aufgezeichnet werden.

"Änderungsreihenfolge" entspricht der gleichen Stufe bei der Konkretisierung von Willkür, ist objektiv und erlaubt nur Aufzeichnungen. Diese Spezialisierung basiert wiederum auf der Tatsache, dass bei einer schwachen Speicherspezifikation kategoriale Garantien nur auf der Ebene eines Objekts gegeben werden.

Lassen Sie uns als nächstes die von Burkhardt et al. Formulierten Axiome der Konsistenz diskutieren und sehen, wie sie auf ein schwaches Speichermodell angewendet werden. Bitte beachten Sie: Trotz des Wortes „Axiome“ handelt es sich lediglich um Eigenschaften, die in verschiedenen Speichermodellen bereitgestellt werden können oder nicht. Burkhardts Artikel konzentriert sich auf die Eigenschaften, die die objektübergreifende Kausalität bestimmen.

Kohärenz letztendlich

Für ein bestimmtes Ereignis kann es nicht unbegrenzt viele Ereignisse geben, die es nicht sehen. Das heißt, jedes Ereignis ist letztendlich für das System sichtbar.

Das logische Erstellen solcher Bedingungen in einem System mit einem schwachen Speichermodell sollte etwas schwieriger sein: Es muss argumentiert werden, dass es für einen bestimmten Datensatz nicht unendlich viele Leseoperationen geben kann, die diesen Datensatz oder frühere Datensätze (in der Änderungsreihenfolge) nicht lesen würden.

In der C ++ 11-Spezifikation ist die Einhaltung dieses Axioms nicht garantiert, obwohl es in der Praxis schwierig ist, ein Gegenbeispiel zu finden.

Ätherische Konsistenz

Wenn Sie die „potenzielle Konditionalität“ auf der Ebene der Flows / Client-Vorgänge und in Bezug auf Sichtbarkeit / Lesbarkeit verfolgen, müssen Sie verstehen, dass es keine Rückgabezeit gibt. Aus diesem Grund ist es erforderlich, dass die Verschlüsse bei der Bestellung der zu lesenden Flüsse azyklisch sind. In der Regel besteht kein Zweifel daran, dass diese Eigenschaft in verteilten Systemen beobachtet wird. Diese Eigenschaft ermöglicht jedoch in einigen spekulativen Versionen keine Sichtbarkeit des Benutzers, wenn das System über ein schwaches Speichermodell verfügt.

Burkhardt et al. Weisen darauf hin, dass dieses Axiom in der C ++ 11-Spezifikation „nicht bestätigt“ ist und es unklar ist, „nicht validiert“, ob in der Praxis „zufriedenstellende Zyklen“ beobachtet werden können .

Axiome der Konditionalität

Um genau anzugeben, worauf sich das Phänomen der Konditionalität unter einem schwachen Speichermodell bezieht, müssen wir genau bestimmen, welche Ereignisse die Ergebnisse welcher anderen Ereignisse beeinflussen können. Betrachten Sie zunächst unsere Standard-Axiome für Ursache und Wirkung: Sitzungsgarantien . Dies sind vier miteinander verbundene Eigenschaften, die die Kohärenzeigenschaften von Lese- und Schreiboperationen widerspiegeln, die in verschiedenen Streams auftreten. Darüber hinaus sollten sie auf der Ebene jedes Objekts angegeben werden (siehe Burkhardt et al ., Abb. 23 ).

• RYW (Lesen Sie Ihre Datensätze): Der Lesevorgang nach dem Schreibvorgang wird in derselben Zelle innerhalb desselben Streams / Replikats / derselben Sitzung ausgeführt. Er muss Daten lesen, die nicht weniger relevant sind als der Datensatz. Die Variante dieser Eigenschaft für verteilte Systeme wird ausschließlich in Bezug auf die Sichtbarkeit angegeben, während die Variante für ein schwaches Speichermodell sowohl auf der Lesereihenfolge als auch auf der Änderungsreihenfolge basieren sollte.
• MR (monolithische Messwerte): Nachfolgende Messwerte (innerhalb desselben Stroms, in derselben Zelle) sollten auch in Zukunft nicht weniger relevante Daten enthalten.
• WFR (zuerst lesen, dann schreiben): Wenn der Schreibvorgang dem Lesevorgang innerhalb des Streams in derselben Zelle folgt, sollte er in der Reihenfolge der Änderungen später als der Lesevorgang ausgeführt werden.
• MW (Monolithic Records): Spätere Datensätze (innerhalb des Streams in derselben Zelle) sollten später in der Änderungsreihenfolge angezeigt werden.

Die Originalversionen von WFR und MW existieren aus Gründen der Zufälligkeit und Sichtbarkeit in zwei Versionen. Dies ist jedoch nur wichtig, wenn mit komplexeren Datenzellen als mit Registern für Ganzzahlen gearbeitet wird.

Diese Eigenschaften spiegeln die Begriffe der Konditionalität wider, die unserem gesunden Menschenverstand entsprechen. Sie vermissen jedoch die interessantesten. Insbesondere bei der Analyse in einem schwachen Speichermodell sind solche Phänomene der Konditionalität durch die Grenzen des Flusses / der Replik / der Sitzung und der spezifischen Zelle / des spezifischen Objekts, in die / der der Eintrag erfolgt, begrenzt: In einem Artikel von Burkhardt et al . in diesem Fall handelt es sich um "Objekt-durch-bedingte bedingte Sichtbarkeit" und "Objekt-durch-bedingte willkürliche Willkür", siehe auch Abb. 23. Diese Phänomene schränken das Verhalten des Systems nicht vollständig ein, wenn verschiedene Streams Informationen in verschiedene Zellen schreiben.

Dann beschreiben die Axiome der objektübergreifenden Konditionierung die Wirkung von Ursache-Wirkungs-Beziehungen auf der Ebene verschiedener Objekte / Speicherzellen.

• COCV (Objektübergreifende bedingte Sichtbarkeit): Der gleiche Fall wie bei RYW, jedoch ohne die Bedingung, dass der endgültige Lesevorgang alle im selben Thread / Replikat / Sitzung durchgeführt werden muss. Messwerte von einem Objekt, die objektiv später als Datensätze in diesem Objekt sind, sollten Daten enthalten, die nicht weniger relevant sind als die während der Aufzeichnung eingegebenen.

Die C ++ 11-Spezifikation spiegelt diese Eigenschaften wider. Bitte beachten Sie: Sie sind so definiert, dass Einschränkungen der Aufzeichnungssichtbarkeit und die Beliebigkeit der Änderungsreihenfolge diese Definitionen nicht zu sehr beeinflussen.

Dies gilt jedoch nicht für die letztere Eigenschaft.

• COCA (Cross-Object Conditional Arbitrary): Ähnlich wie monolithische Datensätze, gilt jedoch für verschiedene Streams, ähnlich wie COCV - es ist RYW für verschiedene Streams. Da die Änderungsreihenfolge jedoch nur Datensätze in einem Objekt betrifft, ermöglicht die Formulierung für ein schwaches Speichermodell dem System eine inkonsistente Verteilung von Aufzeichnungsereignissen in verschiedenen Objekten, und die Datensätze entsprechen möglicherweise nicht den Messwerten oder der Reihenfolge innerhalb des Streams.

Insbesondere ist COCA in einem schwachen Speichermodell eine viel schwächere Eigenschaft. Aus diesem Grund kann bei einem schwachen Speichermodell der folgende Code {x ≡ 0, y ≡ 0} .

Thread A: y := 0; x := 1; return x
Thread B: x := 0; y := 1; return y

Die Reihenfolge innerhalb jedes Streams kann mit der Reihenfolge der einzelnen Objekte und der Änderungsreihenfolge nicht übereinstimmen. Bitte beachten Sie: Mit RYW gibt es kein x := 0 → x := 1 in der Änderungsreihenfolge und für y dasselbe; Daher sollte die Änderungsreihenfolge x := 1 → x := 0 und y := 1 → y := 0 . Somit bildet die Änderungsreihenfolge offensichtlich einen Zyklus in der Reihenfolge der Flüsse.
Eine solche Schleife ist in COCA mit einem schwachen Speichermodell zulässig. Es ist nicht so, dass die Reihenfolge der Streams / Lesevorgänge der Reihenfolge der Änderung widerspricht, sondern dass jeder Stream einen konsistenten Datensatzverlauf sieht. Diese Geschichten stimmen nur dann mit den Geschichten anderer Flüsse überein, wenn wir den Umfang ihrer Anwendung objektiv einschränken.

Was bedeutet das alles?

Die Zeit ist fragmentiert.

Auch wenn es uns so scheint, als würde die Zeit ordentlich fließen, zeigt das Studium verteilter Systeme und eines schwachen Speichermodells deutlich, dass dies nicht der Fall ist. Aus diesem Grund schränkt in beiden Situationen unsere Standardüberschätzung, nach der die Zeit insgesamt ist, die Leistung ein - was wir uns nicht leisten können.
Wenn wir dann erkennen, dass die Zeit wirklich fragmentiert ist, finden wir viele kleine, aber wichtige Unterschiede zwischen den Sorten einer solchen Parteilichkeit. Selbst die beiden oben genannten Felder, die auf den ersten Blick so ähnlich erscheinen, ermöglichen es in vielen subtilen Nuancen zu unterscheiden, welche Arten von Ereignissen sich gegenseitig beeinflussen.

Es ist notwendig, die technischen Details verschiedener Eigenschaften bereits genauer zu verstehen, nachdem jemand die Eigenschaften eines Feldes in der Sprache eines anderen ausdrücken kann.

Die Zeit ist fragmentiert. Vielleicht müssen wir uns nur daran gewöhnen.