Wer bringt den Müll raus?

Der Shenandoah Garbage Collector in Java – eine Einführung

Walery Strauch

©Shutterstock / NotionPic

OpenJDK bringt mehrere Garbage Collectors mit, wie ParallelGC, CMS und G1. G1 ist der Ersatz für den seit Java 9 als deprecated markierten Concurrent Mark Sweep GC (kurz CMS). Daneben existieren noch drei weitere Garbage Collectors: EpsilonGC, ZGC und Shenandoah. Allerdings werden sie im OpenJDK (Oracle Build) nicht mitgeliefert. Ein Blick auf Shenandoah im Detail lohnt sich jedoch.

Objekte werden auf dem Heap abgelegt, der nicht unendlich groß ist. Nach einer gewissen Zeit würde der Heap volllaufen. Viele der neu angelegten Objekte werden nach einer gewissen Zeit nicht mehr gebraucht. Damit der Heap nicht vollläuft, werden die unbrauchbaren Objekte gelöscht. Genau darin besteht die Aufgabe eines Garbage Collectors. Ein Garbage Collector allein reicht jedoch nicht aus. Zuerst werfen wir deshalb einen Blick auf die einzelnen Garbage Collectors. Danach wird klar, worin sie sich unterscheiden, und warum und wann man den einen oder den anderen einsetzen sollte.

ParallelGC vs. SerialGC

In der ersten Version von Java gab es nur einen Garbage Collector. Damit er seine Arbeit erledigen konnte, wurde die gesamte Java-Anwendung angehalten. Während dieser Pause (Stop the World oder kurz STW) wurde der Heap aufgeräumt und dann die Ausführung fortgesetzt. Angenommen, unsere Anwendung wäre ein Webserver. Während der STW-Pause kann dieser Server keine Anfragen beantworten. Alle Anfragen, die während des Garbage-Collector-Zyklus ankommen, werden erst beantwortet, wenn dieser beendet ist. Die Beantwortung der Anfragen soll ein Webserver übernehmen, die Dauer der STW-Pause hängt von der Heap-Größe ab. Je größer der Heap, desto länger die Pause. Wenn sich die Anwendung nicht in der STW-Pause befindet, läuft sie mit voller Geschwindigkeit. Der hier beschriebene Garbage Collector ist ParallelGC (auch Throughput GC genannt). Er wird nach wie vor mit OpenJDK mitgeliefert, bis Java 8 ist er der Standard-Garbage-Collector.

Es gibt noch den kleinen Bruder von ParallelGC: SerialGC. Der Unterschied zwischen den beiden besteht darin, dass SerialGC mit einem Thread die Aufräumarbeiten erledigt, ParallelGC dagegen mit mehreren. SerialGC wird bei schwachen Rechnern mit einer CPU eingesetzt, weshalb er heute keine Rolle mehr spielt. In diesem Artikel schauen wir deshalb nur auf ParallelGC.

API Summit 2018
Christian Schwendtner

GraphQL – A query language for your API

mit Christian Schwendtner (PROGRAMMIERFABRIK)

CMS/G1

In Java 1.2 kam ein weiterer Garbage Collector hinzu, der, wie wir heute sagen würden, experimentell war: Concurrent GC. Mit Java 1.4.1 hielt er endgültig unter neuem Namen Einzug: Concurrent Mark Sweep GC oder einfach CMS. CMS erledigt einen Teil der Aufräumarbeiten während der STW-Pause und einen anderen Teil, während die Anwendung läuft. Letzteres bedeutet concurrent zur Anwendung, dafür steht das C in CMS. Arbeitet der Garbage Collector, während die Anwendung läuft, hat das aber auch zur Folge, dass die Anwendung langsamer wird. Andererseits werden die STW-Pausen kürzer, da ein Teil bereits außerhalb der Pause gemacht wird. CMS ist seit Java 8 deprecated, der Nachfolger ist G1. G1 ist intern komplett anders implementiert als CMS, die Teilung der Aufgaben ist allerdings dieselbe. Ein Teil der Collection wird erledigt während die Anwendung läuft, ein anderer Teil während der STW-Pause. In der Dokumentation wird das als „best balance between latency and throughput“ beschrieben: Mit Latency ist die STW-Pause und mit Throughput der Durchsatz in der Anwendung gemeint.

Die Begriffe „concurrent“ und „parallel“ haben eine ganz bestimmte Bedeutung im Kontext von Garbage Collectors: Parallel bedeutet, dass der Garbage Collector selbst mehr als einen Thread benutzt, um den Heap zu reinigen. Concurrent bedeutet, dass Garbage Collector und Anwendung zur selben Zeit laufen.

Shenandoah

Shenandoah ist ein Garbage Collector, der von RedHat entwickelt wird. Die ersten Veröffentlichungen gab es im Jahr 2013. Shenandoah ist für alle Java-Versionen ab Version 8 verfügbar. Die STW-Pausen sind sehr kurz, und Shenandoah ist in der Lage, mit mehreren TB Heap umzugehen. Das Aufräumen des Heaps verursacht Kosten, mit der Wahl des Garbage Collectors entscheidet man, wie man diese Kosten begleicht. Wählt man ParallelGC, bezahlt man mit STW-Pausen. Die Pause dauert so lange, wie der GC braucht, um fertig zu werden. Die Anwendung selbst läuft dafür ohne Einbußen. Wählt man den G1, bezahlt man sowohl mit STW-Pausen als auch mit der Anwendungszeit. Der Grund hierfür ist, dass nur ein Teil der Arbeit in der STW-Pause stattfindet. Ein anderer Teil wird concurrent zu der Anwendung erledigt, was bedeutet, dass die Anwendung auch insgesamt langsamer wird. Mit Shenandoah werden die Kosten fast komplett in die Anwendung verlagert, die STW-Pausen werden also sehr kurz. Die eigentliche Aufräumarbeit wird concurrent zu der Anwendung erledigt, dadurch wird diese langsamer.

Mülltrennung

Der Heap wird in mehrere Bereiche (Regions) aufgeteilt, die standardmäßig keine Generationen besitzen, also im Gegensatz zu G1 in dieser Hinsicht gleichwertig sind. Während die Anwendung läuft, wird eine Region nach der anderen mit Objekten befüllt. Werfen wir einen Blick darauf, was passiert, wenn ein Shenandoah-GCZyklus stattfindet.

Um den Heap zu bereinigen, muss der Garbage Collector wissen, welche Objekte Garbage sind und welche nicht. Zuallererst muss das sogenannte Root Set bestimmt werden, in dem sich alle Objekte befinden, von denen bekannt ist, dass sie kein Garbage sind. Ein Beispiel hierfür sind die static-Referenzen. Objekte, die sich im Root Set befinden, dürfen nicht weggeräumt werden. Allerdings gibt es weitere Objekte, die kein Garbage sind (Abb. 1).

Abb. 1: Einfaches Beispiel von Objekten auf dem Heap

Abb. 1: Einfaches Beispiel von Objekten auf dem Heap

Ein Objekt innerhalb vom Root Set hat eine Referenz zu Objekt a. Objekt a hat eine Referenz zu b. Objekt b wiederum hat zwei Referenzen: eine zu Objekt c und eine zu Objekt d. Keines der Objekte a, b, c oder d darf gelöscht werden. Diese Objekte sind erreichbar und daher kein Garbage. Das Objekt e hingegen ist von nirgendwo erreichbar, somit ist es Garbage und kann gelöscht werden.

Tri-Color-Algorithmus

Damit die oben beschriebenen Objekte a, b, c und d nicht aus dem Heap entfernt werden, müssen sie als lebendig markiert werden. Dazu dient der sogenannte Tri-Color-Algorithmus. Er markiert alle Objekte, die aus dem Root Set durch Referenzen erreichbar sind. Die Markierung wird mit drei Farben vorgenommen: Schwarz bedeutet, dass das Objekt lebendig ist und seine Referenzen gescannt wurden, grau, dass das Objekt lebendig ist, aber seine Referenzen noch nicht gescannt wurden. Weiß bedeutet, dass das Objekt noch nicht erreicht wurde, oder nicht lebendig ist (= Garbage). In Abbildung 2 ist ein einfacher Scan anhand des vorherigen Beispiels dargestellt.

Abb. 2: Tri-Color-Algorithmus

Abb. 2: Tri-Color-Algorithmus

Shenandoah Schritt für Schritt

Nun sind alle Voraussetzungen bekannt, um Schritt für Schritt zu beschreiben, wie Shenandoah funktioniert. Bevor Shenandoah entscheidet, einen Garbage-Collector-Zyklus durchzuführen, läuft die Applikation ganz normal und befüllt den Heap. Wird der Heap zu voll, wird ein Garbage-Collector-Zyklus gestartet. Daran schließt sich die erste Phase an: Init Mark. In dieser Phase wird zuerst ein STW durchgeführt, währenddessen das aktuelle Root Set bestimmt und ein SATB Flag gesetzt. Was ein SATB Flag ist und wofür es gebraucht wird, klärt sich in der nächsten Phase.

Das Root Set wird bestimmt. Während die Anwendung läuft, wird der Inhalt des Heaps und dadurch auch der Root Set verändert. Die STW-Pause verhindert, dass die Anwendung das Root Set verändert, während es bestimmt wird. Zum Abschluss dieser Phase wird die STW-Pause wieder aufgehoben.

Die nächste Phase heißt Concurrent Marking. Das Root Set ist nun bekannt. Es werden alle erreichbaren Objekte ausgehend vom Root Set markiert. Dafür kommt der Tri-Color-Algorithmus zum Einsatz. Die Anwendung läuft concurrent zum Garbage Collector. Der Heap-Inhalt könnte von der Anwendung modifiziert werden. Der bestehende Objektbaum kann also geändert werden, während die Objekte markiert werden. Schauen wir uns zwei Fälle an: Die Referenz wird verschoben (Abb. 3) und ein neues Objekt erzeugt (Abb. 4).

Abb. 3: Durch Verschieben der Referenz wird ein Objekt, das lebendig ist, nicht gefunden

Abb. 3: Durch Verschieben der Referenz wird ein Objekt, das lebendig ist, nicht gefunden

Abb. 4: Ein neu erzeugtes Objekt wird nicht als lebendig markiert

Abb. 4: Ein neu erzeugtes Objekt wird nicht als lebendig markiert

Fall 1: Die Referenz wird verschoben: In Schritt eins bearbeitet der Garbage-Collector-Thread (Duke in Abb. 3) gerade Objekt a und hat alle ausgehenden Referenzen gescannt. Dadurch ist Objekt a schwarz und Objekt b ist grau. Im zweiten Schritt scannt der Garbage-Collector-Thread das graue Objekt b. Alle Objekte, die über Referenzen von b erreicht werden, müssen grau markiert werden. Der Garbage-Collector-Thread ist allerdings nicht der einzige, der auf dem Heap arbeitet. Concurrent zu dem Garbage-Collector-Thread läuft auch die Anwendung und kann die Referenzen ändern.

Schritte 3 und 4: Bevor der Garbage-Collector-Thread die Referenzen gescannt hat, ist ihm die Anwendung zuvorgekommen. Die Anwendung hat den Pointer von b→c auf a→c abgeändert. Im Code sieht das so aus:

a.c = b.c; // Schritt 3
b.c = null; // Schritt 4

Angekommen bei Schritt fünf hat der Garbage-Collector-Thread alle Referenzen in b gescannt. Dadurch, dass die Referenz von der Anwendung geändert wurde, konnte c nicht gescannt und somit auch nicht als lebendig identifiziert werden. Nach dem Tri-Color-Algorithmus wird Objekt c als Garbage identifiziert.

Fall 2: Ein neues Objekt wird erzeugt: Zuerst bearbeitet der Garbage-Collector-Thread Objekt b. Anschließend erzeugt die Anwendung ein neues Objekt (f) und referenziert es aus dem bereits vom Garbage-Collector-Thread gescannten Objekt (schwarzes Objekt). Im Code könnte das so aussehen: a.f = new F();. Das hat zur Folge, dass Objekt f niemals vom Garbage-Collector-Thread gescannt wird.

Die beiden Fälle lösen: Um Fall 1 abzufangen, werden alle Referenzen, die gelöscht werden, grau markiert. Nehmen wir dieses Codebeispiel: b.c = null;. Die Referenz c im Objekt b wird gelöscht. Objekt c wird grau markiert. Angewendet sieht dieser Fall wie in Abbildung 5 aus.

Abb. 5: Alle gelöschten Referenzen werden grau und so als lebendig markiert

Abb. 5: Alle gelöschten Referenzen werden grau und so als lebendig markiert

In Schritt 4 wird die Referenz zu Objekt c gelöscht. In diesem Fall wird eingegriffen. Das bedeutet, dass Objekt c grau markiert wird (Schritt 5). Dieses Objekt wird nicht direkt vom Garbage-Collector-Thread abgearbeitet, sondern in die SATB-Queue gelegt. Objekt c wird also vom Garbage Collector nicht gelöscht.

Um den zweiten Fall richtig abzufangen, werden alle neu erzeugten Objekte grau markiert. Unser Codebeispiel lautet: new F();. Es wurde ein neues Objekt F von f erzeugt. Deswegen wird dieses Objekt grau markiert. Angewendet sieht dieser Fall wie in Abbildung 6 aus.

Abb.6: Alle neu erzeugten Objekte werden grau und so als lebendig markiert

Abb. 6: Alle neu erzeugten Objekte werden grau und so als lebendig markiert

Im dritten Schritt wird ein neues Objekt erzeugt. Danach wird dieses Ereignis abgefangen und das neue Objekt grau markiert. Dieses Objekt wird nicht direkt vom Garbage-Collector-Thread abgearbeitet, sondern in die SATB-Queue gelegt. Der Garbage Collector löscht Objekt c also nicht.

Zwischenbilanz – Concurrent Marketing

In dieser Phase markiert der Garbage-Collector-Thread lebendige Objekte auf dem Heap. Zum selben Zeitpunkt läuft die Anwendung und kann den Heap verändern. Das kann dazu führen, dass Objekte, die erreichbar sind, nicht markiert werden und somit als Garbage gelten: Das sogenannte „Lost Object Problem“. Um dieses Problem zu umgehen, werden alle gelöschten Referenzen und neu erzeugten Objekte grau markiert. Dieses Verfahren heißt „Snapshot at the beginning“, kurz SATB.

SATB Barrier

Zwei Ereignisse, das Löschen einer Referenz und das Erzeugen eines neuen Objekts, müssen abgefangen werden. Das ist notwendig, um Concurrents zu verändern und das Markieren des Heaps zu ermöglichen. Das Abfangen der Ereignisse findet durch die SATB Barrier statt, nicht zu verwechseln mit dem Memory Barrier. Der Bytecode wird von der JVM gelesen und ausgeführt. Die tatsächliche Ausführung findet auf der CPU statt, das heißt, der Bytecode wird in den nativen Code übersetzt (Assembler). Wenn die JVM mit ShenandoahGC läuft, wird in den nativen Code an bestimmten Stellen zusätzlicher Code eingefügt. Im konkreten SATB-Fall sind es die Stellen, an denen eine Referenz gelöscht oder ein neues Objekt erzeugt wird.

Man kann sich das so vorstellen:

if (SATB-Flag) {
// lege abgefangenes Objekt in die SATB Queue
}

Dieses Beispiel soll verdeutlichen, was die SATB-Barrier macht. Tatsächlich wird der Code direkt als Assembler eingefügt. Der SATB-Flag wird in der vorherigen Phase, der Init-Mark-Phase, gesetzt. Nachdem alle Objekte im Heap markiert wurden, kommt wieder die STW-Pause. In dieser Pause werden alle Objekte aus der SATB-Queue abgearbeitet. Abgesehen davon wird das SATB-Flag wieder herausgenommen.

Zu Beginn der Concurrent-Evacuation-Phase ist bekannt, welche Objekte auf dem Heap lebendig sind. Die Regions, in denen nur Garbage ist, werden sofort nach dem Final Mark freigegeben. Diese Regions können von der Anwendung direkt wieder verwendet werden. Die Regions, in denen es wenige lebendige Objekte gibt, ziehen dann in eine neue Region um, sie werden evakuiert.

Ein einzelnes Objekt kopieren

Um ein Objekt auf dem Heap von einer auf die andere Stelle umziehen zu lassen, braucht es zwei Schritte. Eine Kopie des Objekts wird in den neuen Regions erstellt. Daneben müssen alle Referenzen, die auf die alte Kopie zeigen, aktualisiert werden (Abb. 7).

Abb. 7: Umzug eines Objekts im Heap

Abb. 7: Umzug eines Objekts im Heap

Möchte man alle alten Referenzen updaten, muss man wissen, wo sie sich befinden. Dafür läuft man den Heap einmal komplett durch. Die Referenzen werden also nach und nach aktualisiert, sobald sie beim Durchlaufen des Heaps gefunden werden (Abb. 8).

Abb. 8: Referenzen werden nach und nach abgeändert

Abb. 8: Referenzen werden nach und nach abgeändert

Dieser Schritt läuft concurrent zur Anwendung ab. In dem Zeitraum, in dem der Garbage-Collector-Thread durch den Heap läuft, um alle Referenzen upzudaten, sind möglicherweise beide Kopien gleichzeitig erreichbar. Aus diesem Grund könnte ein Problem auftauchen, wie es in Abbildung 9 zu sehen ist. Beispielsweise wurde eine Kopie vom Objekt erstellt und der Heap wird durchlaufen, um alle Referenzen auf den aktuellsten Stand zu bringen. Es wurden bereits zwei Referenzen gefunden und diese zeigen auf die neue Kopie. Zwei fehlen noch. Daneben kann es auch vorkommen, dass die Anwendung weiterarbeitet, und Objekt A ändert den Wert der Variable bar oder Objekt D den der Variable foo.

Abb. 9: Ein mögliches Problem, wenn man Referenzen nach und nach updated und die Anwendung concurrent läuft

Abb. 9: Ein mögliches Problem, wenn man Referenzen nach und nach updated und die Anwendung concurrent läuft

Nun entsteht das Problem, dass wir zwei Versionen eines Objekts haben, die zum selben Zeitpunkt benutzt werden. Das Problem ließe sich auch anders formulieren: Es existieren zwei Kopien vom selbem Objekt zum selbem Zeitpunkt, die gleichwertig sind. Um dieses Problem zu lösen, dürfte nur eine Kopie zu einem Zeitpunkt gültig sein.

Brooks Pointer

Die Lösung, die bei Shenandoah greift, heißt Brooks Pointer oder auch Forward Pointer (Abb. 10). Jedes Objekt auf dem Heap bekommt zusätzlich einen Forward Pointer. Dieser Pointer kann auf sich selbst oder eine Kopie des Objekts zeigen. Referenzen verweisen nicht mehr direkt auf die Objekte, sondern immer auf die Forward Pointer. Ein Forward Pointer zeigt dann auf die gültige Kopie des Objekts (Abb. 11).

Abb. 10: Jedes Objekt bekommt einen Forward Pointer, auf den alle Referenzen zeigen

Abb. 10: Jedes Objekt bekommt einen Forward Pointer, auf den alle Referenzen zeigen

Abb. 11: Forward Pointer, der auf neues Objekt zeigt

Abb. 11: Forward Pointer, der auf neues Objekt zeigt

In Abbildung 12 wird gezeigt, wie zwei verschiedene Pointer auf die gleichen Objektkopien zeigen. Das Umlenken des Pointers kann nur dann stattfinden, wenn beide Kopien gleich sind. Das Compare-And-Set-(CAS-)Verfahren dient dazu, dies sicherzustellen. Sobald der Pointer in der alten Version auf das neue Objekt zeigt, können die Referenzen nach und nach aktualisiert werden. Das Problem, dass zwei Versionen gleichzeitig erreichbar sind, besteht nicht mehr.

Abb.12: Die Referenzen können durch Forward Pointer nach und nach ohne Probleme aktualisiert werden

Abb. 12: Die Referenzen können durch Forward Pointer nach und nach ohne Probleme aktualisiert werden

Forward Pointer machen es möglich, die Objekte auf dem Heap zu verschieben, während die Anwendung läuft. Das bedeutet, dass alle Referenzen immer auf den Forward Pointer zeigen. Um auf ein Objekt zuzugreifen, muss erst einmal der Forward Pointer gelesen werden. Er gibt Auskunft, wo sich das eigentliche Objekt befindet, was durch zusätzliche Instruktionen ermöglicht wird, die beim Erzeugen von nativem Code eingefügt werden.

Zwischenbilanz – Concurrent Evacuation

Nach der Mark-Phase ist bekannt, welche Objekte noch lebendig sind. Als Nächstes gilt es, Regions freizuräumen. Es werden Regions ausgewählt, die wenige lebendige Objekte besitzen. Objekte aus diesen Regions werden in eine neue gemeinsame Region kopiert. Um zu verhindern, dass zwei Versionen vom selben Objekt gleichzeitig erreicht werden, verwendet man Brooks Pointer. In dieser Phase werden die ausgewählten Objekte in neue Regions kopiert und die Forward Pointer auf die Kopien gesetzt. Das bedeutet, dass vorhandene Referenzen auf Objekte in den alten Regions zeigen, die zu den neuen Kopien weitergeleitet werden.

Aktuell zeigen noch alle Referenzen auf alte Objekte, durch den Forward Point er gelangen sie zu den neuen. In dieser Phase wird der komplette Heap durchlaufen und alle Referenzen, die auf die alten Objekte zeigen, werden aktualisiert. Die Brooks Pointer ermöglichen es, das concurrent zu der Anwendung durchzuführen.

Barrier

Barriers sind zusätzliche Instruktionen im nativen Code. Nehmen wir als Beispiel die Read Barrier: Um ein Objekt zu lesen, muss zuerst der Forward Pointer gelesen werden. Er zeigt, wo sich das eigentliche Objekt befindet. Dieser Mehraufwand ist immer vorhanden, egal ob der Garbage Collector gerade aktiv ist oder nicht. Im Fall von Shenandoah gibt es außer der Read Barrier noch Write Barrier, SATB Barrier und andere. All diese Barriers verlangsamen die Ausführung der JVM, sie haben nichts mit der Java Memory Barrier zu tun.

Fazit

Die Wahl eines Garbage Collectors entscheidet, welche Kosten er verursacht. Wer ParallelGC nutzt, hat einen riesigen Aufwand, um die STW-Pausen in der Anwendung zu vermeiden. Bei Shenandoah hingegen reicht es einfach, sich eine stärkere CPU oder zusätzliche Server zu beschaffen.

Verwandte Themen:

Geschrieben von
Walery Strauch
Walery Strauch
Walery Strauch ist freiberuflicher Softwareentwickler. Seit 2007 beschäftigt er sich intensiv mit Projekten in den Bereichen Java, Web und Cloud. Als Mitbegründer und CEO einer Softwarefirma im Jahre 2010 konnte er sein Wissen auch im Business über Jahre erfolgreich anwenden. Sein Know-how hat er dabei nicht nur als unternehmensinterner Coach geteilt, sondern auch in Java-Vorlesungen an der Hochschule Heidelberg weitergegeben.
Kommentare

Hinterlasse einen Kommentar

Hinterlasse den ersten Kommentar!

avatar
400
  Subscribe  
Benachrichtige mich zu: