MVCC - Multiversion Concurrency Control

Beim Multiversion Concurrency Control-Verfahren werden konkurrierende Zugriffe auf Datensätze (Lesen, Einfügen, Ändern, Löschen) durch verschiedene, unveränderliche Versionen dieser Datensätze kontrolliert. Bei jedem manipulierenden Zugriff (Einfügen, Ändern, Löschen) wird für den Datensatz eine neue Version erstellt. Die verschiedenen Versionen werden in einer zeitlichen Reihenfolge gebracht, indem jede Version auf ihre Vorgängerversion verweist. MVCC hat sich gerade bei NoSQL-Systemen zu einer zentralen Basistechnologie entwickelt, die es ermöglicht, konkurrierende Zugriffe auch ohne das Sperren von Datensätzen zu koordinieren.

Um die geforderten Antwortzeiten erlangen zu können bei mehreren Hunderttausend oder auch Millionen von Benutzern bei gleichzeitiger Verarbeitung von Datenmengen im Tera- und Peta-Byte-Bereich wird eigentlich immer implizit vorausgesetzt, dass die NoSQL-Datenbanksysteme auf verteilten Systemen ausgeführt werden. Also auf Servernetzen mit mehreren dutzend, mehreren hundert oder tausend Servern. In diesem Umfeld erweist sich der relationale Transaktionsansatz mit Sperren von Datensätzen als Haupthindernis. Zum einen ist der Zeit- und Kommunikationsaufwand für eine Übereinkunft über das Setzen und Aufheben einer Sperre immens groß, zum anderen kann auf einen gesperrten Datensatz nicht lesend zugegriffen werden. Und genau hier liegen die Vorteile beim MVCC. Es steht immer eine aktuelle Version zur Verfügung, die gelesen werden kann.

MVCC: Lesen trotz Schreiben
MVCC: Lesen trotz Schreiben

Ablauf:

  • Lesen
    • Das Lesen ist vom Schreiben völlig entkoppelt, keine Wartezeiten. Zu jedem Zeitpunkt steht eine aktuelle Version zum Lesen bereit.
    • Teilweise besteht in Systemen mit MVCC-Verfahren die Möglichkeit, sog. "Zeitreise-Anfragen" zu formulieren, die auf der Basis älterer Versionen einen konsistenten Zustand in der Vergangenheit auswerten. Dies kann für Datenanalysen durchaus vorteilhaft sein.
MVCC: Versionskonflikt
MVCC: Versionskonflikt
  • Schreiben
    • Jeder Prozess der die aktuelle Version ändert, erstellt eine neue Version dieses Datensatzes mit einem Verweis auf die dafür gelesene aktuelle Version.
    • Beim Transaktionsende wird die Vorgänger-Versionsnummer des aktuell in dieser Transaktion geänderten Datensatzes mit seiner aktuellen Versionsnummer verglichen:
      • Vorgänger-Versionsnummer = aktuellen Versionsnummer, dann kann der geänderte Datensatz gespeichert werden. Seine Versionsnummer wird zur neuen aktuellen Versionsnummer.
      • Vorgänger-Versionsnummer < aktuellen Versionsnummer, dann liegt ein Konflikt vor.
        • Im Idealfall kann das DBMS bei Konflikten die Werte der neuen Versionen vergleichen. Wurden bei den neuen Versionen unterschiedliche Attributwerte (Spaltenwerte) geändert, so kann der Konflikt automatisch gelöst werden, in dem die neue Version aus den neuen Attributwerten beider Transaktionen zusammen gesetzt wird.
        • Ein für das DBMS unlösbarer Konflikt liegt erst dann vor, wenn bei einem Datensatz zumindest ein Attribut von beiden Anwendungen geändert wurde. Nur in diesem Fall ist die Transaktion abzubrechen und ein Fehler an die Anwendung/den Benutzer zu melden.
  • Aufräumen
    • In periodischen Zeitabständen müssen alte Versionen gelöscht werden, damit nicht zu viel Speicherplatz für nicht mehr benötigte Versionen verschwendet wird. Ein Datensatz kann alt sein, wenn er von keiner Transaktion mehr verwendet wird oder wenn die Version noch älter ist als die für "Zeitreise-Anfragen" benötigten Versionen.

Als Versionsnummer kann eine fortlaufende Transaktionsnummer verwendet werden, der Transaktionsstartzeitpunkt, der Zeitpunkt der Datenmanipulation oder aber auch die in verteilten Systemen an vielen Stellen erfolgreich arbeitenden Vector Clocks?. Einzige Anforderung in diesem Zusammenhang ist die strenge Monotonie der Nummern.

Dadurch, dass MVCC mehrere Datensatzversionen speichert, ist das Verfahren recht speicherintensiv und zwischendurch muss das DBS auch noch nicht mehr benötigte Versionen löschen, das sog. "Aufräumen". Diese Aufwände sind vernachlässigbar für den Vorteil "jederzeit ohne Wartezeiten lesen zu können". Zumal Speicherkosten recht gering sind und das Aufräumen durchaus auf Zeiten mit geringerer Nutzerlast verschoben werden kann.

Quellen:

  • Birman, K.P.: "Maintaining Consistency in Distributed Systems", Proceedings of the 5. Workshop on ACM SIGOPS European Workshop, Mont Saint-Michel, France, 1992
  • Carey, M.J., Muhanna, W.A.: "The Performance of Multiversion Concurreny Control Algorithm", ACM Transactions on Copmuter Systems, 1986
  • Edlich, Friedland, Hampe, Brauer: „NoSQL – Einstieg in die Welt der nichtrelationalen Web2.0- Anwendungen“, Hanser-Verlag, 2010, ISBN 978-3-446-42355-8
  • Oracle: "Technical Comparision of Oracle Database vs. IBM DB2 UDB: Focus on Performance", Oracle White Paper, Februar 2002

Weiterführende Literatur:

  • Frey, M.: „Etablierte Datenmodelle der NoSQL-Familie und ihre spezifischen Eigenschaften im Kontext von Cloud-Datenbanken“, Bachelorarbeit, FH Köln, Institut für Informatik, 08/2010
  • Kossmann, D., Kraska T.: „Data Management in the Cloud: Promises, State- of-the-art and Open Questions“, in „Datenbanken und Cloud-Computing“, Datenbank Spektrum, Band 10 Heft 3, Springer-Verlag, 12.2010, S. 121-129

Weiterführende Links:

Kategorie: Neue DB-Entwicklungen, Grundlagen, NoSQL, M