Wer braucht Linearisierbarkeit?

Ich habe über die Unterschiede zwischen Serialisierbarkeit und Linearisierbarkeit gelesen , die beide Konsistenzkriterien für replizierte Systeme wie replizierte Datenbanken sind. Ich weiß jedoch nicht, in welchen Fällen Linearisierbarkeit erforderlich wäre, obwohl sie stärker ist als Serialisierbarkeit.

Könnten Sie sich Szenarien einfallen lassen, in denen solch ein starkes Eigentum tatsächlich notwendig wäre?

Betrachten Sie den Entwurf von gleichzeitigen, wartefreien (oder sperrenfreien, schwächeren) Datenstrukturen. In diesem Szenario ist im Allgemeinen eine Linearisierbarkeit erforderlich, obwohl in einigen Fällen die Leistung und Skalierbarkeit verbessert werden kann, indem eine schwächere Korrektheitsbedingung erfüllt wird. Ob eine Implementierung, die eine solche schwache Bedingung erfüllt, nützlich ist, hängt normalerweise von der Anwendung ab. Im Gegensatz dazu ist eine linearisierbare Implementierung immer verwendbar, da Designer sie als atomar betrachten können.

Darüber hinaus ist die Linearisierbarkeit eine nicht blockierende Eigenschaft: Eine Gesamtoperation (definiert für alle Objektzustände) ist niemals erforderlich, um zu blockieren. Die Serialisierbarkeit ist keine nicht blockierende Eigenschaft. Um den Grad der Parallelität zu erhöhen, verlassen sich Designer von gleichzeitigen Datenstrukturen daher immer auf die Linearisierbarkeit.

Ich habe Herlihy und Wing in den letzten 15 Jahren viele Male gelesen. Es ist eine sehr schwierige Lektüre. Und das ist bedauerlich, denn obwohl es einige Feinheiten an den Rändern gibt, ist die Grundidee eigentlich ganz vernünftig.

Kurz gesagt: Linearisierbarkeit ist wie Serialisierbarkeit, jedoch mit der zusätzlichen Anforderung, dass die Serialisierung zusätzliche Ordnungseinschränkungen zwischen den Transaktionen berücksichtigt. Das Ziel ist es, Ihnen zu ermöglichen, rigoros über eine einzelne atomare Datenstruktur nachzudenken, anstatt auf einmal über das gesamte System nachdenken zu müssen.

Linearisierbarkeit ist auch einfach zu erreichen: Verknüpfen Sie einfach einen Mutex mit dem Objekt, das Sie linearisieren möchten. Jede Transaktion für dieses Objekt beginnt mit dem Sperren des Mutex und endet mit dem Entsperren des Mutex.

Hier sind die Definitionen, die ich verwenden werde:

Ein System ist serialisierbar, wenn eine Reihe von Transaktionen über eine Reihe von Daten hinweg ausgeführt wird, jedes Ergebnis der Ausführung der Transaktionen dasselbe ist, als ob die Transaktionen in einer bestimmten Reihenfolge ausgeführt würden, und die Vorgänge innerhalb jeder Transaktion in ihrer Transaktion in der Reihenfolge enthalten sind angegeben durch den Transaktionscode.

Serialisierbarkeit verhindert das Auftreten einer Verschachtelung von Operationen zwischen verschiedenen Transaktionen und setzt voraus, dass die gewählte Reihenfolge der Transaktionen der Kausalität entspricht (wenn Transaktion A den Wert x schreibt und Transaktion B den Wert x liest, den A geschrieben hat, muss Transaktion A Transaktion B vorangehen Die gewählte serielle Reihenfolge.) Es wird jedoch nichts über andere Einschränkungen bei der Reihenfolge von Transaktionen gesagt (insbesondere nichts über Prozesse und die Reihenfolge, in der Prozesse Ereignisse wahrnehmen.)

Es gibt eine weitere verwandte Idee, die Einschränkungen hinsichtlich der Reihenfolge hinzufügt, in der Vorgänge ausgeführt werden (wobei jedoch nicht nur einzelne Lese- / Schreibvorgänge von Transaktionen gesprochen werden):

Ein System ist sequentiell konsistent, wenn das Ergebnis einer Ausführung dasselbe ist, als ob die Operationen aller Prozesse in einer sequentiellen Reihenfolge ausgeführt würden, und die Operationen jedes einzelnen Prozesses in dieser Reihenfolge in der von seinem Programm festgelegten Reihenfolge angezeigt werden. ( Lamport, "Wie erstelle ich einen Multiprozessor-Computer, der Multiprozessor-Programme korrekt ausführt", IEEE T Comp 28: 9 (690-691), 1979 ).

Die Definition der sequentiellen Konsistenz impliziert, dass wir nur sequentielle Reihenfolgen akzeptieren, bei denen für jede Speicherstelle (Objekt) die induzierte sequentielle Reihenfolge von Operationen der Regel entspricht, dass der von jeder Leseoperation an die Stelle xzurückgegebene Wert der gleiche Wert sein muss, von dem geschrieben wurde die unmittelbar vorhergehende Schreiboperation an die Stelle xin der sequentiellen Reihenfolge.

Die Linearisierbarkeit hat die gute Absicht, (a) den Begriff der Transaktionen (aus der Serialisierung) mit dem Begriff zu kombinieren, dass Prozesse die von ihnen ausgegebenen Operationen in der Reihenfolge (aus der sequentiellen Konsistenz) abschließen, und (b) die Korrektheitskriterien einzuengen, um über die einzelnen zu sprechen Objekt isoliert, anstatt Sie zu zwingen, über das System als Ganzes nachzudenken. (Ich möchte sagen können, dass die Implementierung meines Objekts auch in einem System korrekt ist, in dem es andere Objekte gibt, die nicht linearisierbar sind.) Ich glaube, Herlihy und Wing haben möglicherweise versucht, einen Monitor genau zu definieren .

Teil (a) ist "einfach": Eine sequentielle konsistenzähnliche Anforderung wäre, dass die von jedem Prozess ausgegebenen Transaktionen für das Objekt in der resultierenden Reihenfolge in der vom Programm angegebenen Reihenfolge erscheinen. Eine serialisierungsähnliche Anforderung wäre, dass sich alle Transaktionen auf dem Objekt gegenseitig ausschließen (serialisiert werden können).

Die Komplexität ergibt sich aus Ziel (b) (in der Lage sein, über jedes Objekt unabhängig von allen anderen zu sprechen).

In einem System mit mehreren Objekten ist es möglich, dass Operationen für Objekt B Einschränkungen in der Reihenfolge enthalten, in der Operationen für Objekt A aufgerufen wurden. Wenn wir die gesamte Systemhistorie betrachten, sind wir auf bestimmte sequentielle Reihenfolgen und beschränkt müssen andere ablehnen. Wir wollten jedoch ein Korrektheitskriterium, das wir isoliert verwenden können (Überlegung, was mit Objekt A passiert, ohne die globale Systemgeschichte anzugreifen).

Beispiel: Angenommen, ich versuche, über die Richtigkeit von Objekt A, das eine Warteschlange ist, zu streiten. Angenommen, Objekt B ist ein Speicherort, und ich habe die folgenden Ausführungsverläufe: Thread 1: A.enqueue (x), A. dequeue () (gibt y zurück). Thread 2: A.enqueue (y), A.dequeue () (gibt x zurück). Gibt es eine Verschachtelung von Ereignissen, die es ermöglichen würde, dass diese Implementierung der Warteschlange korrekt ist? Ja:

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

Was ist nun, wenn der Verlauf ( einschließlich Objekt B ) wie folgt lautet: B beginnt mit dem Wert 0. Thread 1: A.enqueue (x), A.dequeue () (gibt y zurück), B.write (1). Thread 2: B.read () (gibt 1 zurück) A.enqueue (y), A.dequeue () (gibt x zurück).

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)

Nun möchten wir, dass unsere Definition von "Korrektheit" besagt, dass diese Historie anzeigt, dass entweder unsere Implementierung von A fehlerhaft ist oder unsere Implementierung von B fehlerhaft ist, da es keine Serialisierung gibt, die "sinnvoll" ist (entweder muss Thread 2 lesen) Ein Wert von B, der noch nicht geschrieben wurde, oder Thread 1 muss einen Wert von A, der noch nicht in die Warteschlange gestellt wurde, aus der Warteschlange entfernen erlaubt eine Geschichte wie die zweite, dann ist sie eindeutig falsch.

Die durch die Linearisierung hinzugefügten Einschränkungen sind also durchaus vernünftig (und sogar für einfache Datenstrukturen wie FIFO - Warteschlangen erforderlich). Sie lauten wie folgt: "Ihre Implementierung sollte dequeue () einen Wert nicht zulassen, der erst in der Warteschlange () gespeichert wird Zukunft." Linearisierbarkeit ist recht einfach (und natürlich) zu erreichen: Ordnen Sie Ihrem Objekt einfach einen Mutex zu, und jede Transaktion beginnt mit dem Sperren und endet mit dem Entsperren. Das Denken über die Linearisierbarkeit wird schwierig, wenn Sie versuchen, Ihre Atomarität mit nicht blockierenden oder sperrenden oder wartefreien Techniken anstelle einfacher Mutexe zu implementieren.

Wenn Sie an einigen Hinweisen auf die Literatur interessiert sind, habe ich Folgendes gefunden (obwohl ich denke, dass die Diskussion über "Echtzeit" eine der Red Herings ist, die die Linearisierbarkeit schwieriger machen, als sie sein muss.) Https: // stackoverflow.com/questions/4179587/differenz zwischen-linearisierbarkeit und-serialisierbarkeit

Erstens sind Linearisierbarkeit und Serialisierbarkeit nicht direkt vergleichbar. Wie die folgende Tabelle zeigt, besteht der Hauptunterschied darin, dass auf der linken Seite alle Einzeloperationen atomar sind (wie ein Java synchronizedum jede Operation . Auf der rechten Seite ist die Einheit der Atomizität eine Transaktion; eine Einzeloperation ist nicht atomar Aus diesem Grund war die Serialisierbarkeit immer Teil der Datenbankliteratur, während die linke Seite Gegenstand der Prozessor-Speicher-Literatur war (read / write op is atomic) memcached) hat auf der linken Seite begonnen (get / put ist atomar), aber neuere unterstützen zunehmend Transaktionen (wie Google's spanner).

obj. Operationen sind atomar Transaktionen sind atomar
-------------------------------- + ----------------- ----------------
Linearisierbarkeit |
Sequenzielle Konsistenz | Serialisierbarkeit
Kausale Konsistenz |
Cache-Konsistenz |

Die Linearisierbarkeit erfordert, dass sich ein System von Objekten in einer gleichzeitigen Umgebung identisch mit einem sequentiellen System verhält, das jeweils eine Operation (ein Anforderungs- / Antwortpaar) - in einem parallelen Universum - so verarbeitet, dass (a) die Clients In beiden Universen sieht man genau die gleichen Antworten. (b) Die zeitliche Ordnung bleibt erhalten (mehr dazu weiter unten).

Die Definition der Serialisierbarkeit erfordert ebenso wie die sequentielle Konsistenz nur das erste Kriterium.

Die zeitliche Beibehaltung der Ordnung bedeutet Folgendes: Wenn A: x.op1 () (A ist ein Client, x ist ein Objekt und op1 ist eine Operation) beendet ist, bevor eine andere Operation B: y.op2 () gestartet wurde, wird im sequentiellen Universum die Anfragen werden in der gleichen Reihenfolge bearbeitet. Dies ist in Sequential Consistency (SC) nicht erforderlich. Das Objekt kann die Anforderung eines Clients in die Warteschlange stellen, dem Client antworten und sie später auswerten. Ferner kann das Objekt eine spätere Anforderung von einem anderen Client außerhalb der Reihe verarbeiten und sie auswerten, bevor es zur ersten gelangt.

Die Nichterhaltung der zeitlichen Ordnung ist ein Problem. Nehmen wir an, A hat nach A: x.op1 () den Hörer abgenommen und B davon erzählt, und dann hat B x.op2 () angerufen. Es gibt keine Möglichkeit für das System, über diese kausale Kette von Ereignissen Bescheid zu wissen, da der zweite Schritt eine Nachricht beinhaltete, die vom System nicht verfolgt wurde. In vielen realen Fällen ist es für A nicht unangemessen anzunehmen, dass sich der Aufruf von B auf den aktualisierten Status verlassen kann, sobald x darauf geantwortet hat. Wenn die zeitliche Ordnung nicht eingehalten wurde, stehen A und B vor einer Überraschung. Dies würde in einem linearisierbaren System nicht passieren.

Die zweite schöne Eigenschaft der Erhaltung der zeitlichen Ordnung ist die Lokalität und Komposition, dass ein aus linearisierbaren Objekten aufgebautes System selbst linearisierbar ist. Anstatt einen monolithischen Schlüsselwertspeicher zu haben, können Sie ihn in mehrere separate Partitionen aufteilen, die jeweils von einem eigenen KV-Speicherserver verwaltet werden. Wenn jede von ihnen linearisierbar ist, funktioniert die gesamte Datenbank ohne zusätzlichen Aufwand als ein linearisierbarer monolithischer KV-Speicher.