Runtime Benefits of Memory Deduplication

  • Type:Diploma Thesis
  • Date:05.07.2012
  • Supervisor:

    Prof. Dr. Frank Bellosa, Konrad Miller

  • Graduand:Marc Rittinghaus
  • Links:PDF
  • Abstract (In German):

    Speicherduplikation entsteht, wenn mehrere Speicherseiten (page frames) den gleichen Inhalt tragen und dadurch unnötige Redundanz im Hauptspeicher entsteht. Eine empirische Studie von Speicherduplikation auf Virtualisierungssystemen hat ergeben, dass, abhängig vom eingesetzten Betriebssystem und den ausgeführten Anwendungen, der Anteil von redundanten Speicherseiten zwischen 11% und 86% liegt. Weitere Untersuchungen belegen diese Ergebnisse und nennen Werte zwischen 40% und 50%.

    Um Speicherduplikation entgegenzuwirken und eine effizientere Nutzung des Hauptspeichers zu ermöglichen, sind eine Vielzahl von Deduplizierungsmechanismen entwickelt worden. Ihnen gemein ist das grundlegende Prinzip, unnötige Kopien einer Speicherseite für andere Zwecke freizugeben und stattdessen Referenzen im System über Copy-On-Write auf die verbleibende Instanz zeigen zu lassen. Unterscheidungen gibt es dagegen in der Art und Weise wie der jeweilige Algorithmus Duplikate identifiziert und welche Typen von Speicherseiten designbedingt erfasst werden können (z.B. nur Speicherseiten, die für I/O verwendet werden). Abhängig vom Algorithmus ergibt sich durch das Vergleichen von Speicherseiten und dem Management entsprechender Datenstrukturen ein beträchtlicher Rechenaufwand, der im ungünstigsten Fall einen vollständigen Prozessorkern auslasten kann. Auch birgt Deduplizierung die Gefahr unnötiger Kosten, wenn das Zusammenlegen identischer Seiten aufgrund anschließender Schreibzugriffe rückgängig gemacht werden muss. Es ist daher entscheidend, ein besseres Verständnis über die Charakteristika von identischen Seiten zu erlangen und dieses in bestehende Algorithmen einfließen zu lassen. Auf diese Weise können Anstrengungen zur Deduplizierung auf vielversprechende Speicherbereiche fokussiert und Unkosten reduziert werden.

    Frühere Forschungsarbeit auf dem Gebiet der Speicherduplikation lässt jedoch eine Menge Fragen bzgl. der Eigenschaften von identischen Seiten offen. So wurde bisher wenig Forschung betrieben, um die zeitliche und räumliche Verteilung von identischen Seiten zu erfassen und diese Daten mit Zugriffsmustern und der Art der Speichernutzung zu korrelieren. Darüber hinaus liegen keine Erkenntnisse über die Auswirkungen von Speicherdeduplizierung auf die Geschwindigkeit von Hardwarekomponenten wie Prozessor-Caches vor. Ein weiteres Problem früherer Forschungsarbeiten ist, dass aufgrund der Schwierigkeit, kontinuierliche Daten zu sammeln, die Auswertung in jedem Fall auf abgetasteten Daten beruht. Dies ist inhärent mit der Gefahr unvollständiger Informationen und daraus entstehenden falschen oder ungenauen Aussagen verbunden.

    Die vorliegende Arbeit befasst sich deshalb mit der Entwicklung eines flexiblen Werkzeugs zur feingranularen Analyse von identischen Seiten sowie zur Messung von Effekten der Speicherdeduplizierung. Um die zeitliche Vollständigkeit der zugrundeliegenden Datenbasis zu garantieren, wird dabei auf die umfassende Simulation des zu untersuchenden Systems (Full System Simulation) gesetzt, die eine deutlich genauere Analyse erlaubt, als es in früheren Forschungsarbeiten möglich war. Darüber hinaus stehen durch den Einsatz von Betriebssystem-Introspektion (d.h. dem Aufzeichnen von relevanten Operationen im Betriebssystem) erstmals gleichzeitig detaillierte Informationen zum Systemzustand (z.B. aktuell laufender Prozess, Layout von Adressräumen, Nutzung von Speicherseiten) zur Verfügung, die eine genaue semantische Korrelation erlauben.

    Eine erste prototypische Evaluation hat gezeigt, dass mit Hilfe der entwickelten Analysemethode ein genauer Einblick in die Charakteristika von identischen Speicherseiten ermöglicht wird. Neben der Bestätigung früherer Forschungsergebnisse, konnten ebenso bereits neue Erkenntnisse, z.B. über die Lebenszeit und die Effekte von Speicherduplikation auf CPUCaches, gewonnen werden.

    BibTex:
     
    @diplomathesis{rittinghaus12memorydeduplication,
     author = {Marc Rittinghaus},
     title = {Runtime Benefits of Memory Deduplication},
     type = {Diploma Thesis},
     address = {System Architecture Group, Karlsruhe Institute of Technology (KIT), Germany},
     month = jul # "5",
     year = 2012,
     url = {http://os.ibds.kit.edu/}
     }