Parallelitätskontrolle – Wikipedia

Posted on by
before-content-x4

In der Informationstechnologie und Informatik, insbesondere in den Bereichen Computerprogrammierung, Betriebssysteme, Multiprozessoren und Datenbanken, Parallelitätskontrolle stellt sicher, dass korrekte Ergebnisse für gleichzeitige Vorgänge generiert werden, während diese Ergebnisse so schnell wie möglich abgerufen werden.

after-content-x4

Computersysteme, sowohl Software als auch Hardware, bestehen aus Modulen oder Komponenten. Jede Komponente ist so konzipiert, dass sie ordnungsgemäß funktioniert, dh bestimmte Konsistenzregeln befolgt oder erfüllt. Wenn Komponenten, die gleichzeitig arbeiten, durch Messaging oder durch gemeinsame Nutzung von Daten, auf die zugegriffen wird (im Speicher oder im Speicher), interagieren, kann die Konsistenz einer bestimmten Komponente von einer anderen Komponente verletzt werden. Der allgemeine Bereich der Parallelitätskontrolle bietet Regeln, Methoden, Entwurfsmethoden und Theorien, um die Konsistenz von Komponenten zu gewährleisten, die während der Interaktion gleichzeitig arbeiten, und damit die Konsistenz und Korrektheit des gesamten Systems. Das Einführen der Parallelitätskontrolle in ein System bedeutet das Anwenden von Betriebsbeschränkungen, die normalerweise zu einer gewissen Leistungsminderung führen. Die Konsistenz und Korrektheit des Betriebs sollte mit möglichst guter Effizienz erreicht werden, ohne die Leistung unter ein angemessenes Maß zu reduzieren. Die Parallelitätssteuerung kann in einem gleichzeitigen Algorithmus im Vergleich zum einfacheren sequentiellen Algorithmus eine erhebliche zusätzliche Komplexität und zusätzlichen Aufwand erfordern.

Beispielsweise kann ein Fehler bei der Parallelitätssteuerung zu einer Datenbeschädigung durch zerrissene Lese- oder Schreibvorgänge führen.

Parallelitätskontrolle in Datenbanken[edit]

Bemerkungen:

  1. Dieser Abschnitt gilt für alle Transaktionssysteme, dh für alle Systeme, die diese verwenden Datenbanktransaktionen ((atomare Transaktionen;; B. Transaktionsobjekte in der Systemverwaltung und in Netzwerken von Smartphones, die typischerweise private, dedizierte Datenbanksysteme implementieren, nicht nur Allzweck-Datenbankverwaltungssysteme (DBMS).
  2. DBMS müssen sich auch mit Problemen der Parallelitätskontrolle befassen, die nicht nur für Datenbanktransaktionen, sondern allgemein für Betriebssysteme typisch sind. Diese Probleme (z. B. siehe Parallelitätskontrolle in Betriebssystemen unten) fallen nicht in den Geltungsbereich dieses Abschnitts.

Die Parallelitätskontrolle in Datenbankverwaltungssystemen (DBMS; z. B. Bernstein et al. 1987, Weikum und Vossen 2001), anderen Transaktionsobjekten und verwandten verteilten Anwendungen (z. B. Grid Computing und Cloud Computing) stellt dies sicher Datenbanktransaktionen werden gleichzeitig ausgeführt, ohne die Datenintegrität der jeweiligen Datenbanken zu verletzen. Daher ist die Parallelitätskontrolle ein wesentliches Element für die Korrektheit in jedem System, in dem zwei oder mehr Datenbanktransaktionen, die mit zeitlicher Überlappung ausgeführt werden, auf dieselben Daten zugreifen können, z. B. praktisch in jedem Allzweck-Datenbanksystem. Infolgedessen hat sich seit dem Aufkommen von Datenbanksystemen in den frühen 1970er Jahren eine Vielzahl verwandter Forschungsergebnisse angesammelt. Eine gut etablierte Theorie der Parallelitätskontrolle für Datenbanksysteme ist in den oben genannten Referenzen beschrieben: Serialisierbarkeitstheorie, mit der Methoden und Mechanismen der Parallelitätskontrolle effektiv entworfen und analysiert werden können. Eine alternative Theorie zur Parallelitätskontrolle atomarer Transaktionen über abstrakte Datentypen wird in (Lynch et al. 1993) vorgestellt und im Folgenden nicht verwendet. Diese Theorie ist verfeinert, komplexer, hat einen breiteren Anwendungsbereich und wurde in der Datenbankliteratur weniger verwendet als die obige klassische Theorie. Jede Theorie hat ihre Vor- und Nachteile, Schwerpunkte und Einsichten. Bis zu einem gewissen Grad ergänzen sie sich, und ihre Verschmelzung kann nützlich sein.

Um die Richtigkeit zu gewährleisten, garantiert ein DBMS normalerweise nur dies serialisierbar Transaktionspläne werden generiert, sofern nicht Serialisierbarkeit wird absichtlich gelockert, um die Leistung zu steigern, jedoch nur in Fällen, in denen die Richtigkeit der Anwendung nicht beeinträchtigt wird. Um die Korrektheit bei fehlgeschlagenen (abgebrochenen) Transaktionen zu gewährleisten (was aus vielen Gründen immer vorkommen kann), müssen die Zeitpläne ebenfalls über Folgendes verfügen: Wiederherstellbarkeit (vom Abbruch) Eigentum. Ein DBMS garantiert auch, dass keine Wirkung von engagiert sein Transaktionen gehen verloren und keine Auswirkung von abgebrochen (Rollback-) Transaktionen verbleiben in der zugehörigen Datenbank. Die allgemeine Transaktionscharakterisierung wird normalerweise durch die folgenden ACID-Regeln zusammengefasst. Da Datenbanken verteilt wurden oder für die Zusammenarbeit in verteilten Umgebungen erforderlich sind (z. B. Federated-Datenbanken Anfang 1990 und Cloud Computing derzeit), hat die effektive Verteilung von Mechanismen zur Kontrolle der Parallelität besondere Aufmerksamkeit erhalten.

Datenbanktransaktion und die ACID-Regeln[edit]

Das Konzept eines Datenbanktransaktion (oder Atomtransaktion) wurde entwickelt, um sowohl ein gut verstandenes Verhalten des Datenbanksystems in einer fehlerhaften Umgebung zu ermöglichen, in der jederzeit Abstürze auftreten können, als auch Wiederherstellung von einem Absturz zu einem gut verstandenen Datenbankstatus. Eine Datenbanktransaktion ist eine Arbeitseinheit, die normalerweise eine Reihe von Vorgängen über eine Datenbank (z. B. Lesen eines Datenbankobjekts, Schreiben, Erfassen einer Sperre usw.), eine in der Datenbank und auch in anderen Systemen unterstützte Abstraktion umfasst. Jede Transaktion hat genau definierte Grenzen, in Bezug darauf, welche Programm- / Codeausführungen in dieser Transaktion enthalten sind (vom Programmierer der Transaktion über spezielle Transaktionsbefehle festgelegt). Jede Datenbanktransaktion befolgt die folgenden Regeln (durch Unterstützung im Datenbanksystem, dh ein Datenbanksystem soll sie für die von ihr ausgeführten Transaktionen garantieren):

after-content-x4
  • Atomizität – Entweder bleiben die Auswirkungen aller oder keiner seiner Operationen erhalten (Semantik “alles oder nichts”), wenn eine Transaktion abgeschlossen ist (engagiert sein oder abgebrochen beziehungsweise). Mit anderen Worten, für die Außenwelt scheint eine festgeschriebene Transaktion (aufgrund ihrer Auswirkungen auf die Datenbank) unteilbar (atomar) zu sein, und eine abgebrochene Transaktion wirkt sich überhaupt nicht auf die Datenbank aus. Entweder sind alle Operationen ausgeführt oder keine.
  • Konsistenz – Jede Transaktion muss die Datenbank in einem konsistenten (korrekten) Zustand belassen, dh die vorgegebenen Integritätsregeln der Datenbank (Einschränkungen für und zwischen den Objekten der Datenbank) beibehalten. Eine Transaktion muss eine Datenbank von einem konsistenten Status in einen anderen konsistenten Status umwandeln (es liegt jedoch in der Verantwortung des Programmierers der Transaktion, sicherzustellen, dass die Transaktion selbst korrekt ist, dh korrekt ausgeführt wird, was beabsichtigt ist (aus Sicht der Anwendung) view), während die vordefinierten Integritätsregeln vom DBMS erzwungen werden). Da eine Datenbank normalerweise nur durch Transaktionen geändert werden kann, sind alle Status der Datenbank konsistent.
  • Isolation – Transaktionen können sich nicht gegenseitig stören (als Endergebnis ihrer Ausführung). Darüber hinaus sind die Auswirkungen einer unvollständigen Transaktion normalerweise (abhängig von der Parallelitätskontrollmethode) für eine andere Transaktion nicht einmal sichtbar. Die Bereitstellung von Isolation ist das Hauptziel der Parallelitätskontrolle.
  • Haltbarkeit – Die Auswirkungen erfolgreicher (festgeschriebener) Transaktionen müssen durch Abstürze bestehen bleiben (normalerweise durch Aufzeichnen der Auswirkungen der Transaktion und ihres Festschreibungsereignisses in einem nichtflüchtigen Speicher).

Das Konzept der atomaren Transaktion wurde im Laufe der Jahre auf Geschäftstransaktionen erweitert, die tatsächlich Arten von Workflows implementieren und nicht atomar sind. Bei solchen erweiterten Transaktionen werden jedoch typischerweise atomare Transaktionen als Komponenten verwendet.

Warum ist eine Parallelitätskontrolle erforderlich?[edit]

Wenn Transaktionen ausgeführt werden seriellDas heißt, sequentiell ohne zeitliche Überlappung existiert keine Transaktionsgleichzeitigkeit. Wenn jedoch gleichzeitige Transaktionen mit Verschachtelungsvorgängen auf unkontrollierte Weise zulässig sind, können einige unerwartete, unerwünschte Ergebnisse auftreten, wie z.

  1. Das Problem der verlorenen Aktualisierung: Eine zweite Transaktion schreibt einen zweiten Wert eines Datenelements (Datum) über einen ersten Wert, der von einer ersten gleichzeitigen Transaktion geschrieben wurde, und der erste Wert geht für andere Transaktionen verloren, die gleichzeitig ausgeführt werden und aufgrund ihrer Priorität erforderlich sind , um den ersten Wert zu lesen. Die Transaktionen, die den falschen Wert gelesen haben, enden mit falschen Ergebnissen.
  2. Das Dirty-Read-Problem: Transaktionen lesen einen Wert, der von einer Transaktion geschrieben wurde, die später abgebrochen wurde. Dieser Wert verschwindet beim Abbruch aus der Datenbank und sollte von keiner Transaktion gelesen worden sein (“Dirty Read”). Die Lesetransaktionen enden mit falschen Ergebnissen.
  3. Das falsche Zusammenfassungsproblem: Während eine Transaktion eine Zusammenfassung über die Werte aller Instanzen eines wiederholten Datenelements erstellt, aktualisiert eine zweite Transaktion einige Instanzen dieses Datenelements. Die resultierende Zusammenfassung spiegelt kein korrektes Ergebnis für eine (normalerweise zur Richtigkeit erforderliche) Rangfolge zwischen den beiden Transaktionen wider (wenn eine vor der anderen ausgeführt wird), sondern ein zufälliges Ergebnis, abhängig vom Zeitpunkt der Aktualisierungen und ob dies sicher ist Aktualisierungsergebnisse wurden in die Zusammenfassung aufgenommen oder nicht.

Die meisten Hochleistungs-Transaktionssysteme müssen Transaktionen gleichzeitig ausführen, um ihre Leistungsanforderungen zu erfüllen. Ohne Parallelitätskontrolle können solche Systeme daher weder korrekte Ergebnisse liefern noch ihre Datenbanken konsistent pflegen.

Parallelitätskontrollmechanismen[edit]

Kategorien[edit]

Die Hauptkategorien von Parallelitätskontrollmechanismen sind:

  • Optimistisch – Verzögern Sie die Überprüfung, ob eine Transaktion die Isolations- und andere Integritätsregeln (z. B. Serialisierbarkeit und Wiederherstellbarkeit) erfüllt, bis zu ihrem Ende, ohne einen ihrer (Lese-, Schreib-) Vorgänge zu blockieren (“… und seien Sie optimistisch, welche Regeln eingehalten werden) … “) und brechen Sie dann eine Transaktion ab, um den Verstoß zu verhindern, wenn die gewünschten Regeln bei ihrem Festschreiben verletzt werden sollen. Eine abgebrochene Transaktion wird sofort neu gestartet und erneut ausgeführt, was einen offensichtlichen Overhead verursacht (anstatt sie nur einmal bis zum Ende auszuführen). Wenn nicht zu viele Transaktionen abgebrochen werden, ist es normalerweise eine gute Strategie, optimistisch zu sein.
  • Pessimistisch – Blockieren Sie einen Vorgang einer Transaktion, wenn dies zu einem Verstoß gegen die Regeln führen kann, bis die Möglichkeit eines Verstoßes verschwindet. Blockierungsvorgänge sind normalerweise mit einer Leistungsreduzierung verbunden.
  • Halboptimistisch – Blockieren Sie Vorgänge in bestimmten Situationen, wenn sie zu Verstößen gegen bestimmte Regeln führen können, und blockieren Sie sie in anderen Situationen nicht, während Sie die Überprüfung der Regeln (falls erforderlich) bis zum Ende der Transaktion verzögern, wie dies mit Optimismus geschehen ist.

Unterschiedliche Kategorien bieten unterschiedliche Leistung, dh unterschiedliche durchschnittliche Transaktionsabschlussraten (Durchsatz), abhängig von der Mischung der Transaktionstypen, dem Rechengrad der Parallelität und anderen Faktoren. Wenn Auswahl und Wissen über Kompromisse verfügbar sind, sollten Kategorie und Methode ausgewählt werden, um die höchste Leistung zu erzielen.

Das gegenseitige Blockieren zwischen zwei Transaktionen (wobei jede die andere blockiert) oder mehr führt zu einem Deadlock, bei dem die beteiligten Transaktionen blockiert sind und nicht abgeschlossen werden können. Die meisten nicht optimistischen Mechanismen (mit Blockierung) sind anfällig für Deadlocks, die durch einen absichtlichen Abbruch einer blockierten Transaktion (die die anderen Transaktionen in diesem Deadlock freigibt) und deren sofortigen Neustart und erneute Ausführung behoben werden. Die Wahrscheinlichkeit eines Deadlocks ist normalerweise gering.

Blockieren, Deadlocks und Abbrüche führen zu einer Leistungsminderung und damit zu Kompromissen zwischen den Kategorien.

Methoden[edit]

Es gibt viele Methoden zur Parallelitätskontrolle. Die meisten von ihnen können in beiden oben genannten Hauptkategorien implementiert werden. Die wichtigsten Methoden,[1] die jeweils viele Varianten haben und in einigen Fällen überlappen oder kombiniert werden können, sind:

  1. Sperren (z. Zweiphasenverriegelung – 2PL) – Steuern des Zugriffs auf Daten durch Sperren, die den Daten zugewiesen sind. Der Zugriff einer Transaktion auf ein Datenelement (Datenbankobjekt), das von einer anderen Transaktion gesperrt wurde, kann (abhängig vom Sperrtyp und vom Zugriffsoperationstyp) bis zur Freigabe der Sperre blockiert werden.
  2. Überprüfung des Serialisierungsdiagramms (auch als Serialisierbarkeits-, Konflikt- oder Prioritätsdiagrammprüfung bezeichnet) – Überprüfen Sie das Diagramm des Zeitplans auf Zyklen und unterbrechen Sie diese durch Abbrüche.
  3. Zeitstempelbestellung (TO) – Zuweisen von Zeitstempeln zu Transaktionen und Steuern oder Überprüfen des Zugriffs auf Daten nach Zeitstempelreihenfolge.
  4. Verpflichtungsbestellung (oder Commit-Reihenfolge; CO) – Steuern oder Überprüfen der chronologischen Reihenfolge von Commit-Ereignissen von Transaktionen, um mit ihrer jeweiligen Prioritätsreihenfolge kompatibel zu sein.

Andere wichtige Arten der Parallelitätskontrolle, die in Verbindung mit den oben genannten Methoden verwendet werden, sind:

  • Multiversion-Parallelitätskontrolle (MVCC) – Erhöhen der Parallelität und Leistung durch Generieren einer neuen Version eines Datenbankobjekts bei jedem Schreiben des Objekts und Ermöglichen der Lesevorgänge von Transaktionen mit mehreren letzten relevanten Versionen (jedes Objekts) in Abhängigkeit von der Planungsmethode.
  • Kontrolle der Index-Parallelität – Synchronisieren von Zugriffsvorgängen mit Indizes und nicht mit Benutzerdaten. Spezialisierte Methoden sorgen für erhebliche Leistungssteigerungen.
  • Privates Arbeitsbereichsmodell ((Zurückgestelltes Update) – Jede Transaktion unterhält einen privaten Arbeitsbereich für ihre Daten, auf die zugegriffen wird, und ihre geänderten Daten werden außerhalb der Transaktion erst nach ihrem Festschreiben sichtbar (z. B. Weikum und Vossen 2001). Dieses Modell bietet in vielen Fällen ein anderes Verhalten bei der Parallelitätskontrolle mit Vorteilen.

Der häufigste Mechanismus-Typ in Datenbanksystemen seit ihren Anfängen in den 1970er Jahren war Starke strenge Zweiphasenverriegelung (SS2PL; auch genannt Strenge Planung oder Rigorose 2PL) Dies ist ein Sonderfall (Variante) sowohl der Zweiphasenverriegelung (2PL) als auch der Verpflichtungsbestellung (CO). Es ist pessimistisch. Trotz seines langen Namens (aus historischen Gründen) ist die Idee des SS2PL Der Mechanismus ist einfach: “Alle von einer Transaktion angewendeten Sperren werden erst nach Beendigung der Transaktion freigegeben.” SS2PL (oder Rigorosität) ist auch der Name des Satzes aller Zeitpläne, die durch diesen Mechanismus generiert werden können, dh, dies sind SS2PL-Zeitpläne (oder Rigoros) mit der Eigenschaft SS2PL (oder Rigorosität).

Hauptziele von Parallelitätskontrollmechanismen[edit]

Parallelitätskontrollmechanismen müssen zunächst korrekt funktionieren, dh um die Integritätsregeln jeder Transaktion (in Bezug auf die Parallelität; anwendungsspezifische Integritätsregeln fallen hier nicht in den Geltungsbereich) beizubehalten, während Transaktionen gleichzeitig ausgeführt werden, und damit die Integrität des gesamten Transaktionssystems . Korrektheit muss mit möglichst guter Leistung erreicht werden. Darüber hinaus besteht zunehmend ein Bedarf an einem effektiven Betrieb, während Transaktionen über Prozesse, Computer und Computernetzwerke verteilt werden. Andere Themen, die die Parallelitätskontrolle beeinflussen können, sind Wiederherstellung und Replikation.

Richtigkeit[edit]

Serialisierbarkeit[edit]

Aus Gründen der Korrektheit besteht ein gemeinsames Hauptziel der meisten Mechanismen zur Kontrolle der Parallelität darin, Zeitpläne mit dem zu generieren Serialisierbarkeit Eigentum. Ohne Serialisierbarkeit können unerwünschte Phänomene auftreten, z. B. kann Geld von Konten verschwinden oder aus dem Nichts generiert werden. Serialisierbarkeit eines Zeitplans bedeutet Äquivalenz (in den resultierenden Datenbankwerten) zu einigen seriell Zeitplan mit denselben Transaktionen (dh, bei denen Transaktionen ohne zeitliche Überlappung sequentiell und somit vollständig voneinander isoliert sind: Es ist kein gleichzeitiger Zugriff von zwei Transaktionen auf dieselben Daten möglich). Die Serialisierbarkeit wird als die höchste Isolationsstufe unter Datenbanktransaktionen und als das wichtigste Korrektheitskriterium für gleichzeitige Transaktionen angesehen. In einigen Fällen sind kompromittierte, entspannte Formen der Serialisierbarkeit für eine bessere Leistung zulässig (z. B. die beliebte Snapshot-Isolation Mechanismus) oder um die Verfügbarkeitsanforderungen in stark verteilten Systemen zu erfüllen (siehe Eventuelle Konsistenz), aber nur, wenn die Korrektheit der Anwendung durch die Entspannung nicht verletzt wird (z. B. ist bei Geldtransaktionen keine Entspannung zulässig, da durch Entspannung Geld verschwinden oder aus dem Nichts erscheinen kann).

Fast alle implementierten Parallelitätskontrollmechanismen erreichen Serialisierbarkeit durch Bereitstellung Konfliktserialisierbarkeit, ein breiter Spezialfall der Serialisierbarkeit (dh er deckt die meisten serialisierbaren Zeitpläne ab, ermöglicht keine wesentlichen zusätzlichen verzögerungsbedingten Einschränkungen), der effizient implementiert werden kann.

Wiederherstellbarkeit[edit]
Sehen Wiederherstellbarkeit im Serialisierbarkeit

Kommentar: Während sich der Begriff “Wiederherstellbarkeit” im allgemeinen Bereich von Systemen auf die Fähigkeit eines Systems beziehen kann, sich von einem Fehler oder einem falschen / verbotenen Zustand zu erholen, hat dieser Begriff innerhalb der Parallelitätskontrolle von Datenbanksystemen eine bestimmte Bedeutung erhalten.

Die Parallelitätskontrolle stellt in der Regel auch die Wiederherstellbarkeit Eigenschaft von Zeitplänen zur Aufrechterhaltung der Korrektheit bei abgebrochenen Transaktionen (was aus vielen Gründen immer vorkommen kann). Wiederherstellbarkeit (vom Abbruch) bedeutet, dass keine festgeschriebene Transaktion in einem Zeitplan Daten gelesen hat, die von einer abgebrochenen Transaktion geschrieben wurden. Solche Daten verschwinden aus der Datenbank (beim Abbruch) und sind Teile eines falschen Datenbankstatus. Das Lesen solcher Daten verstößt gegen die Konsistenzregel von ACID. Im Gegensatz zur Serialisierbarkeit kann die Wiederherstellbarkeit in keinem Fall beeinträchtigt oder gelockert werden, da jede Lockerung bei Abbrüchen zu einer schnellen Verletzung der Datenbankintegrität führt. Die oben aufgeführten Hauptmethoden bieten Serialisierbarkeitsmechanismen. Keiner von ihnen in seiner allgemeinen Form bietet automatisch Wiederherstellbarkeit, und spezielle Überlegungen und Mechanismenverbesserungen sind erforderlich, um die Wiederherstellbarkeit zu unterstützen. Ein häufig verwendeter Sonderfall der Wiederherstellbarkeit ist StrengeDies ermöglicht eine effiziente Datenbankwiederherstellung nach einem Ausfall (schließt jedoch optimistische Implementierungen aus; z. B. kann Strict CO (SCO) keine optimistische Implementierung haben, sondern halboptimistische).

Kommentar: Notiere dass der Wiederherstellbarkeit Die Eigenschaft wird auch dann benötigt, wenn kein Datenbankfehler auftritt und keine Datenbank vorhanden ist Wiederherstellung von Ausfall wird benötigt. Es ist vielmehr erforderlich, Transaktionsabbrüche automatisch automatisch zu behandeln, was möglicherweise nicht mit einem Datenbankfehler und einer Wiederherstellung danach zusammenhängt.

Verteilung[edit]

Mit der schnellen technologischen Entwicklung des Rechnens verschwimmt der Unterschied zwischen lokalem und verteiltem Rechnen über Netzwerke oder Busse mit geringer Latenz. Daher ist die recht effektive Verwendung lokaler Techniken in solchen verteilten Umgebungen üblich, z. B. in Computerclustern und Mehrkernprozessoren. Die lokalen Techniken haben jedoch ihre Grenzen und verwenden Multi-Prozesse (oder Threads), die von Multi-Prozessoren (oder Multi-Cores) unterstützt werden, um zu skalieren. Dadurch werden Transaktionen häufig in verteilte Transaktionen umgewandelt, wenn sie selbst mehrere Prozesse umfassen müssen. In diesen Fällen lassen sich die meisten lokalen Techniken zur Steuerung der Parallelität nicht gut skalieren.

Verteilte Serialisierbarkeit und Commitment-Bestellung[edit]
Sehen Verteilte Serialisierbarkeit im Serialisierbarkeit

Mit der Verteilung von Datenbanksystemen oder der Zusammenarbeit in verteilten Umgebungen (z. B. Verbunddatenbanken in den frühen neunziger Jahren und heutzutage Grid Computing, Cloud Computing und Netzwerke mit Smartphones) wurden einige Transaktionen verteilt. Eine verteilte Transaktion bedeutet, dass die Transaktion Prozesse umfasst und sich über Computer und geografische Standorte erstrecken kann. Dies erfordert effektive Mechanismen zur verteilten Parallelitätskontrolle. Erreichen der Serialisierbarkeitseigenschaft des Zeitplans eines verteilten Systems (siehe Verteilte Serialisierbarkeit und Globale Serialisierbarkeit ((Modulare Serialisierbarkeit)) stellt effektiv besondere Herausforderungen dar, die von den meisten regulären Serialisierbarkeitsmechanismen, die ursprünglich für den lokalen Betrieb entwickelt wurden, normalerweise nicht bewältigt werden. Dies ist insbesondere auf die Notwendigkeit einer kostspieligen Verteilung von Informationen zur Parallelitätskontrolle bei Kommunikation und Computerlatenz zurückzuführen. Die einzige bekannte allgemein wirksame Technik für den Vertrieb ist die Commitment Ordering, die 1991 (nach ihrer Patentierung) öffentlich bekannt gegeben wurde. Verpflichtungsbestellung (Commit Ordering, CO; Raz 1992) bedeutet, dass die chronologische Reihenfolge der Commit-Ereignisse von Transaktionen mit ihrer jeweiligen Prioritätsreihenfolge kompatibel bleibt. CO erfordert keine Verteilung von Informationen zur Parallelitätskontrolle und bietet eine allgemeine effektive Lösung (zuverlässig, leistungsstark und skalierbar) für verteilte und globale Serialisierbarkeit, auch in einer heterogenen Umgebung mit Datenbanksystemen (oder anderen Transaktionsobjekten) mit unterschiedlichen ( beliebige) Mechanismen zur Kontrolle der Parallelität.[1] CO ist gleichgültig, welcher Mechanismus verwendet wird, da es keine Transaktionsoperationsplanung stört (die von den meisten Mechanismen gesteuert wird) und nur die Reihenfolge der Festschreibungsereignisse bestimmt. Somit ermöglicht CO die effiziente Verteilung aller anderen Mechanismen und auch die Verteilung einer Mischung verschiedener (beliebiger) lokaler Mechanismen, um eine verteilte und globale Serialisierbarkeit zu erreichen. Die Existenz einer solchen Lösung wurde bis 1991 und von vielen Experten auch später aufgrund von Missverständnissen der CO-Lösung als “unwahrscheinlich” angesehen (siehe Zitate in Globale Serialisierbarkeit). Ein wichtiger Nebeneffekt von CO ist die automatische verteilte Deadlock-Auflösung. Im Gegensatz zu CO neigen praktisch alle anderen Techniken (wenn sie nicht mit CO kombiniert werden) zu verteilten Deadlocks (auch als globale Deadlocks bezeichnet), die einer besonderen Behandlung bedürfen. CO ist auch der Name der resultierenden Zeitplaneigenschaft: Ein Zeitplan hat die CO-Eigenschaft, wenn die chronologische Reihenfolge der Festschreibungsereignisse seiner Transaktionen mit der Vorrangreihenfolge der jeweiligen Transaktionen (Teilreihenfolge) kompatibel ist.

Das oben erwähnte SS2PL ist eine Variante (Sonderfall) von CO und somit auch wirksam, um eine verteilte und globale Serialisierbarkeit zu erreichen. Es bietet auch eine automatische verteilte Deadlock-Auflösung (eine Tatsache, die in der Forschungsliteratur auch nach der Veröffentlichung von CO übersehen wird) sowie Strenge und damit Wiederherstellbarkeit. Der Besitz dieser gewünschten Eigenschaften zusammen mit bekannten effizienten Implementierungen auf der Basis von Sperren erklärt die Beliebtheit von SS2PL. SS2PL wird seit 1980 verwendet, um eine verteilte und globale Serialisierbarkeit effizient zu erreichen, und ist zum De-facto-Standard dafür geworden. SS2PL blockiert und beschränkt jedoch (pessimistisch), und mit der zunehmenden Verbreitung und Nutzung von Systemen, die sich von herkömmlichen Datenbanksystemen unterscheiden (z. B. wie beim Cloud Computing), sind möglicherweise weniger einschränkende CO-Typen (z. B. optimistisches CO) erforderlich bessere Leistung.

Bemerkungen:

  1. Das Verteilte Serialisierbarkeit von Konflikten Eigentum in seiner allgemeinen Form ist schwer effizient zu erreichen, aber es wird effizient über seinen Sonderfall erreicht Verteiltes CO: Jede lokale Komponente (z. B. ein lokales DBMS) muss sowohl eine Form von CO bereitstellen als auch eine spezielle erzwingen Abstimmungsstrategie für die Zweiphasiges Festschreibungsprotokoll (2PC: Wird zum Festschreiben verteilter Transaktionen verwendet). Abweichend vom allgemeinen verteilten CO, Verteilte SS2PL existiert automatisch, wenn alle lokalen Komponenten SS2PL-basiert sind (in jeder Komponente existiert CO, impliziert, und die Strategie für die Reihenfolge der Stimmen wird jetzt automatisch erfüllt). Diese Tatsache ist seit den 1980er Jahren bekannt und wird genutzt (dh SS2PL existiert global, ohne über CO Bescheid zu wissen), um verteiltes SS2PL effizient zu nutzen, was verteilte Serialisierbarkeit und Strenge impliziert (siehe z. B. Raz 1992, Seite 293; dies ist auch in Bernstein impliziert) et al. 1987, Seite 78). Eine weniger eingeschränkte verteilte Serialisierbarkeit und Strenge kann effizient durch verteiltes striktes CO (SCO) oder durch eine Mischung aus SS2PL-basierten und SCO-basierten lokalen Komponenten erreicht werden.
  2. Über die Referenzen und die Reihenfolge der Zusagen: (Bernstein et al. 1987) wurde vor der Entdeckung von CO im Jahr 1990 veröffentlicht. Die Eigenschaft CO-Zeitplan wird aufgerufen Dynamische Atomizität in (Lynch et al. 1993, Seite 201). CO wird in (Weikum und Vossen 2001, Seiten 102, 700) beschrieben, aber die Beschreibung ist teilweise und verfehlt das Wesen von CO. (Raz 1992) war der erste referierte und zur Veröffentlichung angenommene Artikel über CO-Algorithmen (Veröffentlichungen über eine äquivalente dynamische Atomizitätseigenschaft können jedoch bis 1988 zurückverfolgt werden). Weitere CO-Artikel folgten. (Bernstein und Newcomer 2009)[1] Beachten Sie CO als eine der vier wichtigsten Methoden zur Kontrolle der Parallelität und die Fähigkeit von CO, Interoperabilität zwischen anderen Methoden bereitzustellen.
Verteilte Wiederherstellbarkeit[edit]

Im Gegensatz zur Serialisierbarkeit Verteilte Wiederherstellbarkeit und Verteilte Strenge kann auf einfache Weise effizient erreicht werden, ähnlich wie verteiltes CO: In jedem Datenbanksystem müssen sie lokal angewendet werden und eine Abstimmungsstrategie für das Zwei-Phasen-Festschreibungsprotokoll anwenden (2PC; Raz 1992, Seite 307) ).

Wie oben erwähnt, verwendet Distributed SS2PL, einschließlich Distributed Strictness (Wiederherstellbarkeit) und Distributed Commitment Ordering (Serialisierbarkeit), automatisch die erforderliche Abstimmungsreihenfolge-Strategie und wird (global) erreicht, wenn sie lokal in jedem (lokalen) Datenbanksystem eingesetzt wird (wie bisher) ist seit vielen Jahren bekannt und wird genutzt. Tatsächlich wird die Lokalität durch die Grenze eines 2PC-Teilnehmers definiert (Raz 1992).

Andere wichtige Themen der Aufmerksamkeit[edit]

Das Design von Parallelitätskontrollmechanismen wird häufig von folgenden Themen beeinflusst:

Wiederherstellung[edit]

Alle Systeme sind fehleranfällig und handhabbar Wiederherstellung vom Scheitern ist ein Muss. Die Eigenschaften der generierten Zeitpläne, die vom Parallelitätskontrollmechanismus vorgegeben werden, können die Effektivität und Effizienz der Wiederherstellung beeinflussen. Beispielsweise ist die Strictness-Eigenschaft (oben im Abschnitt Wiederherstellbarkeit erwähnt) häufig für eine effiziente Wiederherstellung wünschenswert.

Reproduzieren[edit]

Für Hochverfügbarkeit sind Datenbankobjekte häufig repliziert. Aktualisierungen von Replikaten desselben Datenbankobjekts müssen synchronisiert bleiben. Dies kann die Art und Weise beeinflussen, wie die Parallelitätskontrolle durchgeführt wird (z. B. Gray et al. 1996)[2]).

Siehe auch[edit]

Verweise[edit]

Zitate[edit]

Parallelitätskontrolle in Betriebssystemen[edit]

Multitasking-Betriebssysteme, insbesondere Echtzeit-Betriebssysteme, müssen die Illusion aufrechterhalten, dass alle darauf ausgeführten Aufgaben gleichzeitig ausgeführt werden, obwohl aufgrund der. Zu einem bestimmten Zeitpunkt nur eine oder wenige Aufgaben tatsächlich ausgeführt werden Einschränkungen der Hardware, auf der das Betriebssystem ausgeführt wird. Ein solches Multitasking ist ziemlich einfach, wenn alle Aufgaben unabhängig voneinander sind. Wenn jedoch mehrere Aufgaben versuchen, dieselbe Ressource zu verwenden, oder wenn Aufgaben versuchen, Informationen auszutauschen, kann dies zu Verwirrung und Inkonsistenz führen. Die Aufgabe des Concurrent Computing besteht darin, dieses Problem zu lösen. Einige Lösungen beinhalten “Sperren”, die den in Datenbanken verwendeten Sperren ähneln, aber sie können eigene Probleme wie Deadlocks verursachen. Andere Lösungen sind nicht blockierende Algorithmen und Read-Copy-Update.

Siehe auch[edit]

Verweise[edit]


after-content-x4