Het garbage collection-mechanisme van het Java-platform verhoogt de productiviteit van ontwikkelaars enorm, maar een slecht geïmplementeerde garbage collector kan te veel systeembronnen van een toepassing in beslag nemen. In dit derde artikel in de serie JVM-prestatieoptimalisatie geeft Eva Andreasson Java-beginners een overzicht van het geheugenmodel en het GC-mechanisme van het Java-platform. Ze legt vervolgens uit waarom fragmentatie (en niet GC) de belangrijkste “gotcha!” van Java applicatie performance is, en waarom generationele garbage collection en compactie momenteel de leidende (maar niet de meest innovatieve) benaderingen zijn voor het managen van heap fragmentatie in Java applicaties.

Garbage collection (GC) is het proces dat zich richt op het vrijmaken van bezet geheugen waarnaar niet langer verwezen wordt door een bereikbaar Java object, en is een essentieel onderdeel van het Java virtual machine’s (JVM’s) dynamisch geheugen management systeem. In een typische vuilnisophaalcyclus worden alle objecten waarnaar nog wordt verwezen, en die dus nog bereikbaar zijn, bewaard. De ruimte die in beslag wordt genomen door objecten waarnaar eerder werd verwezen, wordt vrijgemaakt en teruggevorderd om nieuwe objecttoewijzing mogelijk te maken.

Om garbage collection en de verschillende GC-benaderingen en algoritmen te begrijpen, moet je eerst een paar dingen weten over het geheugenmodel van het Java-platform.

Garbage collection en het geheugenmodel van het Java-platform

Wanneer u op de opdrachtregel van uw Java-toepassing de opstartoptie -Xmx specificeert (bijvoorbeeld: java -Xmx:2g MyApp), wordt geheugen toegewezen aan een Java-proces. Dit geheugen wordt de Java heap (of gewoon heap) genoemd. Dit is de toegewezen geheugenadresruimte waar alle objecten die door je Java-programma (of soms de JVM) worden gemaakt, worden toegewezen. Als je Java programma blijft draaien en nieuwe objecten blijft toewijzen, zal de Java heap (dat wil zeggen die adresruimte) vol raken.

Eindelijk zal de Java heap vol zijn, wat betekent dat een toewijzende thread niet in staat is om een groot genoeg opeenvolgend deel van vrij geheugen te vinden voor het object dat het wil toewijzen. Op dat moment bepaalt de JVM dat er een garbage collection moet plaatsvinden en geeft het een melding aan de garbage collector. Een garbage collection kan ook worden gestart wanneer een Java-programma System.gc() aanroept. Het gebruik van System.gc() is geen garantie voor een garbage collection. Voordat een garbage collection kan beginnen, zal een GC-mechanisme eerst bepalen of het veilig is om het te starten. Het is veilig om een garbage collection te starten wanneer alle actieve threads van de applicatie op een veilig punt zijn om het mogelijk te maken, bijvoorbeeld eenvoudig uitgelegd dat het slecht zou zijn om een garbage collection te starten in het midden van een lopende object allocatie, of in het midden van het uitvoeren van een reeks geoptimaliseerde CPU instructies (zie mijn vorige artikel over compilers), omdat je context zou kunnen verliezen en daardoor eindresultaten zou kunnen verknoeien.

Een garbage collector zou nooit een actief gerefereerd object moeten terughalen; om dat te doen zou de Java virtual machine specificatie breken. Een vuilnisman hoeft dode objecten ook niet onmiddellijk op te halen. Dode objecten worden uiteindelijk verzameld tijdens volgende garbage collection cycli. Hoewel er vele manieren zijn om garbage collection te implementeren, zijn deze twee aannames waar voor alle varianten. De echte uitdaging van vuilnisverzameling is om alles te identificeren dat nog in gebruik is (waarnaar nog verwezen wordt) en alle geheugen terug te halen waarnaar niet verwezen wordt, maar dit te doen zonder de lopende toepassingen meer te belasten dan nodig is. Een garbage collector heeft dus twee taken:

1. Het snel vrijmaken van geheugen waarnaar niet verwezen wordt, om te voldoen aan de allocatiesnelheid van een applicatie, zodat deze niet zonder geheugen komt te zitten.
2. Het terugwinnen van geheugen met zo min mogelijk impact op de prestaties (bijv, latentie en doorvoer) van een draaiende applicatie.

Twee soorten garbage collection

In het eerste artikel in deze serie heb ik de twee belangrijkste benaderingen van garbage collection aangestipt, te weten referentietellende en tracerende collectors. Deze keer ga ik dieper in op elke benadering en introduceer dan enkele van de algoritmen die worden gebruikt om tracing collectors in productie-omgevingen te implementeren.

Reference counting collectors

Reference counting collectors houden bij hoeveel referenties er naar elk Java object wijzen. Zodra de teller voor een object nul wordt, kan het geheugen onmiddellijk worden teruggehaald. Deze onmiddellijke toegang tot teruggevorderd geheugen is het grote voordeel van de referentietellende aanpak van vuilnisophaling. Er is zeer weinig overhead wanneer het aankomt op het vasthouden van geheugen zonder verwijzingen. Het bijhouden van alle referentietellingen kan echter behoorlijk kostbaar zijn.

Het grootste probleem met referentietellende verzamelaars is het nauwkeurig houden van de referentietellingen. Een andere bekende uitdaging is de complexiteit van het omgaan met circulaire structuren. Als twee objecten naar elkaar verwijzen en geen levend object verwijst naar hen, zal hun geheugen nooit worden vrijgegeven. Beide objecten zullen voor altijd met een niet-nul graaf blijven. Het terugwinnen van geheugen dat is geassocieerd met circulaire structuren vereist een grondige analyse, die kostbare overhead voor het algoritme, en dus voor de applicatie, met zich meebrengt.

Tracing collectors

Tracing collectors zijn gebaseerd op de aanname dat alle levende objecten kunnen worden gevonden door iteratief alle verwijzingen en opvolgende verwijzingen van een initiële set van bekende levende objecten te traceren. De initiële verzameling van levende objecten (root objects of kortweg roots genoemd) wordt gelokaliseerd door de registers, globale velden en stack frames te analyseren op het moment dat een vuilnisophaal wordt getriggerd. Nadat een initiële verzameling van levende objecten is geïdentificeerd, volgt het tracing-collector de referenties van deze objecten en plaatst ze in een wachtrij om als levend gemarkeerd te worden en vervolgens hun referenties te laten traceren. Het markeren van alle gevonden gerefereerde objecten als live betekent dat de bekende live set toeneemt in de loop van de tijd. Dit proces gaat door totdat alle objecten waarnaar verwezen wordt (en dus alle live objecten) gevonden en gemarkeerd zijn. Zodra de tracing-collector alle live-objecten heeft gevonden, zal hij het resterende geheugen terugwinnen.

Tracing-collectoren verschillen van verwijzings-tellende collectoren in het feit dat ze circulaire structuren aankunnen. Het addertje onder het gras bij de meeste tracing-collectors is de markeringsfase, die een wachttijd met zich meebrengt voordat niet-verwezen geheugen kan worden teruggehaald.

Tracing-collectors worden het meest gebruikt voor geheugenbeheer in dynamische talen; ze komen verreweg het meest voor in de Java-taal en zijn al vele jaren commercieel beproefd in productie-omgevingen. Ik zal me voor de rest van dit artikel richten op tracing collectors, te beginnen met enkele van de algoritmen die deze benadering van garbage collection implementeren.

Tracing collector algoritmen

Copying en mark-and-sweep garbage collection zijn niet nieuw, maar het zijn nog steeds de twee meest voorkomende algoritmen die tracing garbage collection implementeren vandaag de dag.

Kopieer-verzamelaars

Traditionele kopieer-verzamelaars gebruiken een from-space en een to-space — dat wil zeggen, twee afzonderlijk gedefinieerde adresruimten van de heap. Op het moment van vuilnisophaling worden de levende objecten binnen het gebied gedefinieerd als from-space gekopieerd naar de eerstvolgende beschikbare ruimte binnen het gebied gedefinieerd als to-space. Wanneer alle levende objecten binnen de from-ruimte zijn verplaatst, kan de gehele from-ruimte worden teruggewonnen. Wanneer de toewijzing opnieuw begint, begint deze vanaf de eerste vrije plaats in de to-space.

In oudere implementaties van dit algoritme wisselen de from-space en to-space van plaats, wat betekent dat wanneer de to-space vol is, de vuilnisophaalprocedure opnieuw wordt gestart en de to-space de from-space wordt, zoals te zien is in figuur 1.

Meer moderne implementaties van het kopieeralgoritme staan toe dat willekeurige adresruimten binnen de heap worden toegewezen als to-space en from-space. In deze gevallen hoeven ze niet noodzakelijkerwijs van plaats te wisselen met elkaar; in plaats daarvan wordt elk een andere adresruimte binnen de heap.

Een voordeel van kopieerverzamelaars is dat objecten strak tegen elkaar worden gealloceerd in de to-space, waardoor fragmentatie volledig wordt geëlimineerd. Fragmentatie is een veel voorkomend probleem waar andere garbage collection algoritmen mee worstelen; iets wat ik later in dit artikel zal bespreken.

Downsides of copying collectors

Copying collectors zijn meestal stop-the-world collectors, wat betekent dat er geen toepassingswerk kan worden uitgevoerd zolang de garbage collection in cyclus is. In een stop-de-wereld implementatie, hoe groter het gebied dat je moet kopiëren, hoe groter de impact op je applicatieprestatie zal zijn. Dit is een nadeel voor toepassingen die gevoelig zijn voor responstijd. Bij een kopieerverzamelaar moet je ook rekening houden met het slechtste scenario, als alles live is in de from-ruimte. Je moet altijd genoeg ruimte overlaten voor live objecten die verplaatst moeten worden, wat betekent dat de to-space groot genoeg moet zijn om alles in de from-space te herbergen. Het kopieeralgoritme is enigszins inefficiënt vanwege deze beperking.

Mark-and-sweep collectors

De meeste commerciële JVM’s die worden gebruikt in productie-omgevingen draaien mark-and-sweep (of markering) collectors, die niet de prestatie-impact hebben die kopieer-collectors wel hebben. Enkele van de bekendste markeer-verzamelaars zijn CMS, G1, GenPar, en DeterministicGC (zie Bronnen).

Een markeer-en-veeg verzamelaar traceert referenties en markeert elk gevonden object met een “live” bit. Gewoonlijk correspondeert een “live” bit met een adres of in sommige gevallen met een reeks adressen op de heap. De “live” bit kan bijvoorbeeld worden opgeslagen als een bit in de object header, een bit vector, of een bit map.

Nadat alles “live” gemarkeerd is, zal de sweep fase beginnen. Als een verzamelaar een sweep-fase heeft, bevat deze in principe een mechanisme om de heap opnieuw te doorzoeken (niet alleen de live set, maar de hele heap-lengte) om alle niet-gemarkeerde brokken van opeenvolgende geheugenadresruimten te vinden. Niet-gemarkeerd geheugen is vrij en kan worden teruggevorderd. De verzamelaar koppelt dan deze niet-gemarkeerde stukken aan elkaar in georganiseerde vrije lijsten. Er kunnen verschillende vrije lijsten zijn in een vuilnisman — meestal gerangschikt op brokgrootte. Sommige JVM’s (zoals JRockit Real Time) implementeren verzamelaars met heuristieken die dynamisch grootte-range lijsten gebaseerd op applicatie profiling gegevens en object-grootte statistieken.

Als de sweep fase is voltooid begint de toewijzing opnieuw. Nieuwe allocatiegebieden worden toegewezen vanuit de vrije lijsten en geheugenchunks kunnen worden afgestemd op objectgroottes, objectgrootte-gemiddelden per thread ID, of de op de applicatie afgestemde TLAB-groottes. Door de vrije ruimte beter af te stemmen op de grootte van wat uw toepassing probeert toe te wijzen, wordt het geheugen geoptimaliseerd en kan fragmentatie worden verminderd.

Downsides of mark-and-sweep collectors

De mark-fase is afhankelijk van de hoeveelheid live data op je heap, terwijl de sweep-fase afhankelijk is van de heap-grootte. Omdat u moet wachten tot zowel de mark- als de sweep-fase zijn voltooid om geheugen terug te winnen, veroorzaakt dit algoritme pauzetijdproblemen voor grotere heaps en grotere gegevensverzamelingen.

Eén manier waarop u toepassingen kunt helpen die veel geheugen gebruiken, is door GC-afstemmingsopties te gebruiken die aan verschillende toepassingsscenario’s en -behoeften voldoen. Afstemming kan in veel gevallen helpen om ten minste uit te stellen dat een van deze fasen een risico wordt voor uw applicatie of service-level agreements (SLA’s). (Een SLA specificeert dat de applicatie aan bepaalde applicatie-reactietijden zal voldoen — d.w.z., latency.) Het afstemmen voor elke belastingswijziging en applicatiewijziging is echter een repetitieve taak, omdat de afstemming alleen geldt voor een specifieke werkbelasting en toewijzingssnelheid.

Implementaties van mark-and-sweep

Er zijn ten minste twee commercieel beschikbare en beproefde benaderingen voor de implementatie van mark-and-sweep collection. De ene is de parallelle aanpak en de andere is de gelijktijdige (of grotendeels gelijktijdige) aanpak.

Parallelle verzamelaars

Parallelle verzameling betekent dat aan het proces toegewezen bronnen parallel worden gebruikt voor de vuilnisophaal. De meeste commercieel geïmplementeerde parallelle collectors zijn monolithische stop-de-wereld collectors — alle applicatie-threads worden gestopt totdat de hele vuilnisverzamelingscyclus is voltooid. Door alle threads te stoppen kunnen alle bronnen efficiënt parallel worden gebruikt om de vuilnisverzameling via de mark en sweep fasen te voltooien. Dit leidt tot een zeer hoge mate van efficiëntie, wat gewoonlijk resulteert in hoge scores op doorvoerbenchmarks zoals SPECjbb. Als doorvoer essentieel is voor uw toepassing, is de parallelle aanpak een uitstekende keuze.