Der Garbage-Collection-Mechanismus der Java-Plattform steigert die Produktivität der Entwickler erheblich, aber ein schlecht implementierter Garbage-Collector kann die Anwendungsressourcen übermäßig beanspruchen. In diesem dritten Artikel der Serie zur Leistungsoptimierung der JVM bietet Eva Andreasson Java-Anfängern einen Überblick über das Speichermodell der Java-Plattform und den GC-Mechanismus. Sie erklärt dann, warum Fragmentierung (und nicht GC) das Hauptproblem bei der Leistung von Java-Anwendungen ist und warum generative Garbage Collection und Verdichtung derzeit die führenden (wenn auch nicht die innovativsten) Ansätze zur Verwaltung der Heap-Fragmentierung in Java-Anwendungen sind.

Garbage Collection (GC) ist der Prozess, der darauf abzielt, belegten Speicher freizugeben, der von keinem erreichbaren Java-Objekt mehr referenziert wird, und ist ein wesentlicher Bestandteil des dynamischen Speicherverwaltungssystems der Java Virtual Machine (JVM). In einem typischen Garbage Collection-Zyklus werden alle Objekte, die noch referenziert und damit erreichbar sind, aufbewahrt. Der von zuvor referenzierten Objekten belegte Platz wird freigegeben und zurückgewonnen, um die Zuweisung neuer Objekte zu ermöglichen.

Um die Garbage Collection und die verschiedenen GC-Ansätze und -Algorithmen zu verstehen, müssen Sie zunächst ein paar Dinge über das Speichermodell der Java-Plattform wissen.

Garbage Collection und das Speichermodell der Java-Plattform

Wenn Sie die Startoption -Xmx in der Befehlszeile Ihrer Java-Anwendung angeben (zum Beispiel: java -Xmx:2g MyApp), wird einem Java-Prozess Speicher zugewiesen. Dieser Speicher wird als Java-Heap (oder einfach Heap) bezeichnet. Dies ist der dedizierte Speicheradressraum, in dem alle von Ihrem Java-Programm (oder manchmal der JVM) erstellten Objekte zugewiesen werden. Wenn Ihr Java-Programm weiterläuft und neue Objekte zuweist, füllt sich der Java-Heap (d. h. der Adressraum).

Irgendwann ist der Java-Heap voll, was bedeutet, dass ein zuweisender Thread keinen ausreichend großen, zusammenhängenden Abschnitt freien Speichers für das Objekt finden kann, das er zuweisen möchte. Zu diesem Zeitpunkt stellt die JVM fest, dass eine Garbage Collection erforderlich ist, und benachrichtigt den Garbage Collector. Eine Garbage Collection kann auch ausgelöst werden, wenn ein Java-Programm System.gc() aufruft. Die Verwendung von System.gc() ist keine Garantie für eine Garbage Collection. Bevor eine Garbage Collection gestartet werden kann, stellt ein GC-Mechanismus zunächst fest, ob es sicher ist, sie zu starten. Es ist sicher, eine Garbage Collection zu starten, wenn sich alle aktiven Threads der Anwendung an einem sicheren Punkt befinden, der dies zulässt, z.B. einfach erklärt, dass es schlecht wäre, die Garbage Collection mitten in einer laufenden Objektzuweisung oder mitten in der Ausführung einer Sequenz von optimierten CPU-Anweisungen zu starten (siehe meinen vorherigen Artikel über Compiler), da man den Kontext verlieren und dadurch die Endergebnisse durcheinander bringen könnte.

Ein Garbage Collector sollte niemals ein aktiv referenziertes Objekt zurückfordern; dies würde die Spezifikation der Java Virtual Machine verletzen. Ein Garbage Collector ist auch nicht verpflichtet, tote Objekte sofort einzusammeln. Tote Objekte werden in nachfolgenden Garbage-Collection-Zyklen eingesammelt. Es gibt zwar viele Möglichkeiten, die Garbage Collection zu implementieren, aber diese beiden Annahmen gelten für alle Varianten. Die eigentliche Herausforderung der Garbage Collection besteht darin, alles zu identifizieren, was noch aktiv ist (noch referenziert wird), und nicht referenzierten Speicher zurückzugewinnen, ohne dabei laufende Anwendungen mehr als nötig zu beeinträchtigen. Ein Garbage Collector hat also zwei Aufgaben:

1. Nicht referenzierten Speicher schnell freizugeben, um die Zuweisungsrate einer Anwendung zu erfüllen, damit ihr der Speicher nicht ausgeht.
2. Speicher zurückzufordern und dabei die Leistung (z. B. Latenz und Durchsatz) der Anwendung möglichst wenig zu beeinträchtigen,

Zwei Arten der Garbage Collection

Im ersten Artikel dieser Serie habe ich die beiden Hauptansätze der Garbage Collection behandelt, nämlich Referenzzählung und Tracing Collectors. Diesmal werde ich die beiden Ansätze näher erläutern und dann einige der Algorithmen vorstellen, die zur Implementierung von Tracing Collectors in Produktionsumgebungen verwendet werden.

Referenzzählungskollektoren

Referenzzählungskollektoren verfolgen, wie viele Referenzen auf jedes Java-Objekt zeigen. Sobald die Zählung für ein Objekt Null wird, kann der Speicher sofort zurückgewonnen werden. Dieser unmittelbare Zugriff auf den wiedergewonnenen Speicher ist der größte Vorteil des Referenz-Counting-Ansatzes bei der Garbage Collection. Es gibt nur sehr wenig Overhead, wenn es darum geht, nicht referenzierten Speicher aufzubewahren. Es kann jedoch recht kostspielig sein, alle Referenzzählungen auf dem neuesten Stand zu halten.

Die Hauptschwierigkeit bei referenzzählenden Sammlern besteht darin, die Referenzzählungen genau zu halten. Eine weitere bekannte Herausforderung ist die Komplexität, die mit dem Umgang mit zirkulären Strukturen verbunden ist. Wenn zwei Objekte aufeinander verweisen und kein lebendes Objekt auf sie verweist, wird ihr Speicher nie freigegeben. Beide Objekte bleiben für immer mit einem Zählerstand ungleich Null erhalten. Die Rückgewinnung von Speicher, der mit zirkulären Strukturen verbunden ist, erfordert eine umfangreiche Analyse, die dem Algorithmus und damit der Anwendung einen kostspieligen Overhead beschert.

Tracing-Collectors

Tracing-Collectors basieren auf der Annahme, dass alle lebenden Objekte gefunden werden können, indem alle Verweise und nachfolgenden Verweise von einer anfänglichen Menge bekannter lebender Objekte iterativ verfolgt werden. Die anfänglichen lebenden Objekte (Root-Objekte oder kurz Roots genannt) werden durch Analyse der Register, globalen Felder und Stack-Frames zum Zeitpunkt der Auslösung einer Garbage Collection ermittelt. Nachdem ein erster Satz aktiver Objekte identifiziert wurde, verfolgt der Tracing-Collector die Verweise dieser Objekte und stellt sie in eine Warteschlange, um sie als aktiv zu markieren und ihre Verweise anschließend zu verfolgen. Die Kennzeichnung aller gefundenen referenzierten Objekte als live bedeutet, dass die bekannte live Menge mit der Zeit zunimmt. Dieser Prozess wird fortgesetzt, bis alle referenzierten (und damit alle aktiven) Objekte gefunden und markiert sind. Sobald der Tracing-Collector alle aktiven Objekte gefunden hat, gibt er den verbleibenden Speicher wieder frei.

Tracing-Collectors unterscheiden sich von Reference-Counting-Collectors dadurch, dass sie mit zirkulären Strukturen umgehen können. Der Haken bei den meisten Tracing-Collectors ist die Markierungsphase, die eine Wartezeit mit sich bringt, bevor nicht referenzierter Speicher zurückgewonnen werden kann.

Tracing-Collectors werden am häufigsten für die Speicherverwaltung in dynamischen Sprachen verwendet; sie sind bei weitem die gebräuchlichsten für die Sprache Java und haben sich seit vielen Jahren in Produktionsumgebungen bewährt. Ich werde mich im weiteren Verlauf dieses Artikels auf Tracing-Collectors konzentrieren und mit einigen der Algorithmen beginnen, die diesen Ansatz der Garbage Collection implementieren.

Tracing-Collector-Algorithmen

Das Kopieren und die Mark-and-Sweep-Garbage-Collection sind nicht neu, aber sie sind immer noch die beiden gängigsten Algorithmen, die heute die Tracing-Garbage-Collection implementieren.

Kopierkollektoren

Traditionelle Kopierkollektoren verwenden einen From-Space und einen To-Space, d.h. zwei separat definierte Adressräume des Heaps. Zum Zeitpunkt der Garbage Collection werden die lebenden Objekte innerhalb des als from-space definierten Bereichs in den nächsten freien Platz innerhalb des als to-space definierten Bereichs kopiert. Wenn alle lebenden Objekte innerhalb des from-space ausgelagert sind, kann der gesamte from-space zurückgewonnen werden. Wenn die Zuweisung erneut beginnt, wird mit dem ersten freien Platz im to-space begonnen.

In älteren Implementierungen dieses Algorithmus tauschen der from-space und der to-space die Plätze, d.h. wenn der to-space voll ist, wird die Garbage Collection erneut ausgelöst und der to-space wird zum from-space, wie in Abbildung 1 dargestellt.

Moderne Implementierungen des Kopieralgorithmus erlauben es, beliebige Adressräume innerhalb des Heaps als To-Space und From-Space zuzuweisen. In diesen Fällen müssen sie nicht notwendigerweise den Ort miteinander tauschen; vielmehr wird jeder zu einem anderen Adressraum innerhalb des Heaps.

Ein Vorteil des Kopierens von Kollektoren ist, dass die Objekte im To-Space eng beieinander liegen, wodurch eine Fragmentierung vollständig vermieden wird. Fragmentierung ist ein häufiges Problem, mit dem andere Garbage-Collection-Algorithmen zu kämpfen haben, worauf ich später in diesem Artikel eingehen werde.

Nachteile von Kopiersammlern

Kopiersammler sind in der Regel Stop-the-World-Sammler, was bedeutet, dass keine Anwendungsarbeit ausgeführt werden kann, solange sich die Garbage Collection im Zyklus befindet. Bei einer Stop-the-world-Implementierung ist die Auswirkung auf die Anwendungsleistung umso größer, je größer der zu kopierende Bereich ist. Dies ist ein Nachteil für Anwendungen, die auf Antwortzeiten angewiesen sind. Bei einem kopierenden Collector müssen Sie auch das Worst-Case-Szenario in Betracht ziehen, wenn alles im From-Space live ist. Sie müssen immer genügend Spielraum für zu verschiebende lebende Objekte lassen, was bedeutet, dass der “to-space” groß genug sein muss, um alles im “from-space” aufzunehmen. Der Kopieralgorithmus ist aufgrund dieser Einschränkung etwas speicherineffizient.

Mark-and-Sweep-Kollektoren

Die meisten kommerziellen JVMs, die in Produktionsumgebungen eingesetzt werden, verwenden Mark-and-Sweep- (oder Markierungs-) Kollektoren, die nicht die Leistungseinbußen wie Kopierkollektoren haben. Einige der bekanntesten Markierungskollektoren sind CMS, G1, GenPar und DeterministicGC (siehe Ressourcen).

Ein Mark-and-Sweep-Kollektor verfolgt Referenzen und markiert jedes gefundene Objekt mit einem “Live”-Bit. Normalerweise entspricht ein gesetztes Bit einer Adresse oder in einigen Fällen einer Gruppe von Adressen auf dem Heap. Das Live-Bit kann z.B. als Bit im Objekt-Header, als Bit-Vektor oder als Bit-Map gespeichert werden.

Nachdem alles live markiert wurde, beginnt die Sweep-Phase. Wenn ein Collector eine Sweep-Phase hat, beinhaltet sie im Grunde einen Mechanismus, um den Heap erneut zu durchlaufen (nicht nur die Live-Menge, sondern die gesamte Heap-Länge), um alle nicht markierten Chunks aufeinanderfolgender Speicheradressräume zu finden. Nicht markierter Speicher ist frei und kann zurückgewonnen werden. Der Collector verknüpft dann diese nicht markierten Chunks zu organisierten freien Listen. In einem Garbage Collector kann es verschiedene freie Listen geben, die normalerweise nach der Größe der Chunks geordnet sind. Einige JVMs (wie z.B. JRockit Real Time) implementieren Kollektoren mit Heuristiken, die dynamisch Größenlisten auf der Grundlage von Anwendungsprofilen und Objektgrößenstatistiken erstellen.

Wenn die Sweep-Phase abgeschlossen ist, beginnt die Zuweisung erneut. Neue Zuweisungsbereiche werden aus den freien Listen zugewiesen, und die Speicherchunks können an die Objektgrößen, die durchschnittlichen Objektgrößen pro Thread-ID oder die auf die Anwendung abgestimmten TLAB-Größen angepasst werden. Eine bessere Anpassung des freien Speicherplatzes an die Größe dessen, was die Anwendung zuzuweisen versucht, optimiert den Speicher und kann dazu beitragen, die Fragmentierung zu verringern.

Nachteile von Mark-and-Sweep-Collectors

Die Mark-Phase ist abhängig von der Menge der Live-Daten auf dem Heap, während die Sweep-Phase von der Heap-Größe abhängt. Da Sie warten müssen, bis sowohl die Markierungs- als auch die Sweep-Phase abgeschlossen sind, um Speicher zurückzugewinnen, führt dieser Algorithmus bei größeren Heaps und größeren Live-Datenmengen zu Problemen mit der Pausenzeit.

Eine Möglichkeit, um Anwendungen mit hohem Speicherverbrauch zu unterstützen, ist die Verwendung von GC-Tuning-Optionen, die verschiedene Anwendungsszenarien und -anforderungen berücksichtigen. Tuning kann in vielen Fällen dazu beitragen, dass eine dieser Phasen nicht zu einem Risiko für Ihre Anwendung oder Ihre Service-Level-Agreements (SLAs) wird. (Ein SLA legt fest, dass die Anwendung bestimmte Antwortzeiten einhalten muss, d. h. die Latenzzeit.) Die Abstimmung für jede Laständerung und Anwendungsmodifikation ist jedoch eine sich wiederholende Aufgabe, da die Abstimmung nur für eine bestimmte Arbeitslast und Zuweisungsrate gilt.

Implementierungen von Mark-and-Sweep

Es gibt mindestens zwei kommerziell verfügbare und bewährte Ansätze für die Implementierung der Mark-and-Sweep-Sammlung. Der eine ist der parallele Ansatz und der andere ist der nebenläufige (oder überwiegend nebenläufige) Ansatz.

Parallele Kollektoren

Parallele Sammlung bedeutet, dass dem Prozess zugewiesene Ressourcen parallel zum Zweck der Garbage Collection verwendet werden. Die meisten kommerziell implementierten parallelen Kollektoren sind monolithische Stop-the-World-Kollektoren – alle Anwendungs-Threads werden angehalten, bis der gesamte Garbage-Collection-Zyklus abgeschlossen ist. Durch das Anhalten aller Threads können alle Ressourcen effizient parallel genutzt werden, um die Garbage Collection durch die Markierungs- und Sweep-Phasen abzuschließen. Dies führt zu einer sehr hohen Effizienz, die sich in der Regel in hohen Ergebnissen bei Durchsatz-Benchmarks wie SPECjbb niederschlägt. Wenn der Durchsatz für Ihre Anwendung entscheidend ist, ist der parallele Ansatz eine ausgezeichnete Wahl.