GoSuda

Go runtime, který vám vezme šálek zeleného čaje, GreenTea GC

By snowmerak
views ...

Proč přichází další nový GC

Proč existuje stávající GC

Současný Go GC lze popsat následujícími slovy:

  • Concurrent tri-color mark and sweep
    • Pro sledování stavu objektů se používají celkem 3 barvy (bílá, šedá, černá).
      • Bílá: Objekt, který ještě nebyl navštíven
      • Šedá: Objekt, který byl navštíven, ale nebyly navštíveny všechny jeho podřízené objekty
      • Černá: Objekt, u kterého byly navštíveny všechny podřízené objekty
      • Po dokončení průchodu jsou shromážděny všechny bílé objekty.
    • K ochraně nově vytvářené paměti během GC se používá Write Barrier.
      • Doba zapnutí/vypnutí Write Barrier tvoří významnou část toho, co se běžně nazývá Stop-The-World (dále jen STW).
    • Tento proces je prováděn souběžně (concurrently).
  • No Compaction
    • Go GC neprovádí komprimaci (compaction).
    • Může dojít k fragmentaci paměti.
      • Avšak u objektů menších než 32 kb je fragmentace minimalizována využitím per-P cache alokátoru paměti jazyka Go (Allocator).
  • Non-Generational
    • Go GC nespravuje objekty podle generací.
    • Všechny objekty patří do stejné generace.
  • Escape Analysis
    • Go používá Escape Analysis k určení, zda má být objekt alokován na haldě (heap) nebo na zásobníku (stack).
    • Zhruba řečeno, pokud se používají dangling pointery nebo rozhraní, lze předpokládat alokaci na haldě.

Důležitá věc

Důležité je, že Go GC prohledává všechny objekty od kořene (root) a provádí tri-color mark. Tento proces lze shrnout do jedné věty jako algoritmus souběžného prohledávání grafu topologického řazení. Avšak je vysoce pravděpodobné, že jednotlivé objekty se nacházejí v různých paměťových oblastech. Konkrétně řečeno:

  1. Předpokládejme, že existují paměťové oblasti vzdálené přibližně 32 MB.
  2. V těchto dvou paměťových oblastech je alokováno 5 objektů.
    1. Objekty A, B, C jsou v oblasti 1.
    2. Objekty D, E jsou v oblasti 2.
  3. Pořadí referencí objektů je A -> D -> B -> E -> C.
  4. Když GC začne, navštíví A, poté D, poté B, poté E a nakonec C.
  5. Vzhledem k tomu, že A a D se nacházejí v různých paměťových oblastech, je nutné při přechodu z A na D přesunout se mezi paměťovými oblastmi.
  6. Během tohoto procesu vznikají náklady spojené s tzv. skokem v paměti (memory jump cost), jako je přesun mezi paměťovými oblastmi a vyplňování nových cache linek. Značná část času CPU, který aplikace spotřebuje, může být přidělena na tyto GC operace.
  7. Tyto náklady vznikají po celou dobu provádění GC.

Takže co je problém?

Tento způsob fungování GC je problematický v následujících případech:

  • Velký počet jader (cores) a velká paměť
    • Go GC je v zásadě prováděn souběžně (concurrently).
    • Pokud je však paměťová oblast rozsáhlá a objekty jsou rozptýleny, více jader bude souběžně prohledávat objekty v různých paměťových prostorech.
    • Pokud sběrnice mezi CPU a pamětí není dostatečně široká, může se propustnost paměti (memory bandwidth) stát úzkým hrdlem.
    • Navíc, protože jsou fyzicky vzdálené, každý průchod prohledávání bude mít poměrně velkou latenci.
  • Velké množství malých objektů
    • Pokud provozujete v Go stromové nebo grafové struktury s velkou hloubkou nebo mnoha potomky (children), GC musí prohledat všechny tyto objekty.
    • Pokud jsou objekty rozptýleny v různých paměťových oblastech, dojde k latenci z důvodu uvedeného v prvním bodě.
    • Navíc, pokud je malých objektů mnoho, GC je musí všechny prohledat, což znamená, že během provádění GC bude CPU jádro věnovat značnou část své kapacity na GC.

K řešení těchto problémů tým Golang představil GreenTea GC.

Už nemáte čas na další zelený čaj

Co vám bere zelený čaj

Nejrychlejším řešením stávajícího GC se zdá být zaměření na lokalitu dat v paměti (memory locality). To znamená minimalizovat skoky v paměti tím, že se objekty umístí blízko sebe. Nicméně nelze vynutit vzorce programátorů při psaní kódu a alokace objektů je nepředvídatelná v závislosti na pracovním postupu (workflow).

Proto se tým Golang rozhodl pro metodu nazvanou Memory Span.

Co je Memory Span?

Memory Span je poměrně velká oblast paměti alokovaná pro alokaci malých objektů. A nový GC, pojmenovaný GreenTea GC, provádí sběr odpadu (garbage collection) v těchto Memory Spans. Detailní fungování je téměř identické se stávajícím Tri-Color Mark and Sweep.

Fungování GreenTea GC

Nejprve GreenTea GC alokuje Memory Span. Jak bylo předem popsáno, velikost je 8 KiB, což je poměrně velká velikost. A uvnitř lze alokovat objekty o maximální velikosti 512 bytů. Tato velikost je taková, že je obtížné, aby ji překročila velikost uzlů stromu nebo grafu, které byly uvedeny jako příklad, nebo velikost běžných struktur, které unikají na haldu. Objekty menší než 512 bytů se hromadí v tomto Memory Span pokaždé, když uniknou na haldu, a když se Memory Span zaplní, alokuje se nový Memory Span.

Když nyní dojde ke spuštění GC, GreenTea GC zařadí tyto Memory Spans do fronty a postupně je kontroluje. Během tohoto procesu používá GreenTea GC plánování (scheduling) téměř identické se stávajícím modelem GMP. Je implementováno i kradení práce (work stealing). Každopádně pracovník (worker), který si vybere Memory Span z fronty, kontroluje vnitřní objekty jemu přiděleného Memory Span. Během tohoto procesu se používá stejný Tri-Color Mark and Sweep.

Jaké jsou výhody?

Zásadní rozdíl oproti stávajícímu GC spočívající v tomto procesu je pouze jeden. Jednotkou, ve které se GC provádí, se stal Memory Span namísto objektu. Díky tomu získává GC následující výhody:

  • Lokalita dat v paměti (Memory Locality): Protože jsou objekty shromážděny v Memory Span, skoky v paměti jsou při prohledávání objektů minimalizovány. To znamená maximální využití CPU cache.
  • Zlepšení výkonu GC: Prováděním GC na úrovni Memory Span pracuje GC efektivněji v multijádrovém prostředí.
  • Optimalizace alokace paměti: Memory Spans jsou alokovány s pevnou velikostí, což snižuje režii alokace paměti při alokaci malých objektů a snižuje pravděpodobnost fragmentace. To zvyšuje efektivitu uvolňování paměti.

Zkrátka, od nynějška můžeme alokovat objekty menší než 512 bytů častěji a s menšími obavami.

Nicméně i zde existují oblasti, kde je to obzvláště výhodné:

  • Stromové/grafové struktury: V případě vysokého fan-outu a zřídkavých změn
    • B+ stromy, Trie, AST (Abstract Syntax Tree)
    • Datové struktury přátelské k cache
  • Dávkové zpracování (Batch Processing): Pracovní postupy s hromadnou alokací malých dat
    • Mnoho malých objektů vytvořených parsováním JSON
    • DAO objekty (Data Access Object) z výsledků databáze

V těchto případech může GreenTea GC poskytnout lepší výkon než stávající GC. Nicméně to neplatí ve všech případech, a zejména tam, kde jsou objekty rozptýleny v různých paměťových oblastech, nelze stále očekávat dramatické zlepšení výkonu.

Závěr

Zdá se, že tým Golang má v úmyslu pokračovat ve zlepšování GC z dlouhodobého hlediska. Tento GreenTea GC lze považovat za menší změnu v malé oblasti a nenahrazuje stávající GC. Nicméně GreenTea GC je zajímavým příkladem, který nám umožňuje nahlédnout na problémy, kterým tým Golang čelí nebo které očekává. Působivý je i pokus vyřešit poměrně složitý problém přidáním relativně jednoduchého konceptu. Osobně to považuji za zajímavý případ.

GreenTea GC je experimentální funkce, která je zaváděna od Go 1.25. Lze ji aktivovat pomocí proměnné prostředí GOEXPERIMENT=greenteagc. Protože je tato funkce stále experimentální, je před jejím použitím v produkčním prostředí nutné důkladné testování.

Reference