Using I/O-based Hints to Make Memory-Deduplication Scanners More Efficient

  • Type:Diploma Thesis
  • Date:29.07.2012
  • Supervisor:

    Prof. Dr. Frank Bellosa, Konrad Miller

  • Graduand:Fabian Franz
  • Links:PDF
  • Abstract (In German):

    Der primäre Engpass für die Konsolidierung von mehreren Virtuellen Maschinen (VMs) auf einem physischen Computer ist die begrenzte Größe der Hauptspeichers. Speicher kann nicht beliebig aufgerüstet werden und ist im Vergleich zu mehr CPU Geschwindigkeit immer noch eine teure Resource. Moderne Betriebssysteme benutzen Paging um Applikationen mehr virtuellen Speicher zuzuteilen als physisch vorhanden ist.

    Um Speicher zu sparen werden physische Speicherseiten mit identischem Inhalt unter Nutzung von copy-on-write dedupliziert, d.h. schreibgeschützte virtuelle Seiten zeigen auf die gleiche physische Seite. Dies ist ein übliches Verfahren und wird meist in Kombination mit mmap und fork benutzt. Zum Beispiel werden die Seiten einer dynamischen Bibliothek dedupliziert, so dass diese nur einmal Speicher im System belegt.

    Eine virtuelle Maschine ist eine 'Black Box' für den Host auf dem sie läuft. Der Host hat keine Information über den Inhalt des Speichers der VM und kann diesen demnach nicht deduplizieren.

    Lösungsansätze für dieses Problem sind Paravirtualisierung und Memory Scanner (Speicherscanner). In der Paravirtualisierung gibt das Gast-Betriebssystem in der VM dem Host Informationen über die Speicherseiten und ermöglicht so dem Host den Speicher zu deduplizieren, freizugeben oder anderweitig zu nutzen. Memory Scanner dagegen katalogisieren die Speicherseiten des Gastes basierend auf ihrem Inhalt und finden so Duplikate.

    Memory Scanner sind begrenzt durch eine gewisse Scan Rate mit der sie den Speicher auf Duplikate untersuchen, z.B. 100 Seiten alle 100 ms. Mit dieser Scan Rate kann ein Memory Scanner aber keine kurz-lebigen Deduplikationsmöglichkeiten finden, da die Seiten sich wieder geändert haben bevor der Scanner sie findet. Eine höhere Scan Rate, wo der Scanner z.B. eine ganze CPU voll auslastet, ist nicht gerechtfertigt, da der Aufwand in keinem Verhältnis zum Nutzen steht.

    Benchmarks, die als Teil dieser Arbeit durchgeführt wurden, zeigen dass 80% aller Deduplikationsmöglichkeiten zwischen 30 s und 5 min existieren. Es existiert also ein großes Deduplikationspotential, dass von Memory Scannern mit der Standard Scan Rate nicht gefunden wird. Zwischen 64% und 93% der gemeinsam nutzbaren Seiten zwischen VMs stammen aus dem Page cache der Gastbetriebssysteme.

    Diese Arbeit führt einen neuen Ansatz ein, der I/O Requests im VFS des Host Betriebssystems abfängt und die Adressen der zugehörigen Speicherbereiche in der Form von Hints an Memory Scanner weiter gibt. Dieser Ansatz wird im folgenden KSM++ genannt. Mit dieser Information kann KSM++ Speicher früher scannen als traditionelle Memory Scanner und findet so Deduplikationsmöglichkeiten die ihren Ursprung im Page Cache der Gastbetriebssysteme haben.

    KSM++ wurde als Erweiterung von KSM (Kernel Samepage Merging) im Linux Kernel als Prototyp implementiert und evaluiert. Im Gegensatz zur Paravirtualisierung muss das Gastbetriebssystem nicht geändert werden.

    Die Evaluationsergebnisse zeigen, dass KSM++ doppelt soviel Speicher deduplizieren kann wie KSM und Deduplizierungsmöglichkeiten, bei einer Scan Rate von 1000 Seiten pro Sekunde, bis zu 8 Minuten früher findet als KSM.

    Als Fazit ist KSM++ eine nützliche Erweiterung um Memory Scanner effektiver und effizienter zu machen.

    BibTex:
     
    @diplomathesis{franz12memorydeduplicationscanners,
     author = {Fabian Franz},
     title = {Using I/O-based Hints to Make Memory-Deduplication Scanners More Efficient},
     type = {Diploma Thesis},
     address = {System Architecture Group, Karlsruhe Institute of Technology (KIT), Germany},
     month = jul # "29",
     year = 2012,
     url = {http://os.ibds.kit.edu/}
     }