Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 18467] ファイルの概要

このコミットは、Goランタイムのガベージコレクション（GC）におけるスイープフェーズを並行化する重要な変更を導入します。これにより、GCによるアプリケーションの一時停止（Stop-the-World: STW）時間を大幅に削減し、全体的なパフォーマンスとレイテンシを向上させることを目的としています。具体的には、バックグラウンドで動作するスイーパーゴルーチンと、必要に応じて実行されるオンデマンドスイープを導入することで、スイープ処理がSTWフェーズから切り離されます。

コミット

commit 3c3be622011747f6db4b4cf81ed3a975dfca2b51
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Wed Feb 12 22:16:42 2014 +0400

    runtime: concurrent GC sweep
    Moves sweep phase out of stoptheworld by adding
    background sweeper goroutine and lazy on-demand sweeping.
    
    It turned out to be somewhat trickier than I expected,
    because there is no point in time when we know size of live heap
    nor consistent number of mallocs and frees.
    So everything related to next_gc, mprof, memstats, etc becomes trickier.
    
    At the end of GC next_gc is conservatively set to heap_alloc*GOGC,
    which is much larger than real value. But after every sweep
    next_gc is decremented by freed*GOGC. So when everything is swept
    next_gc becomes what it should be.
    
    For mprof I had to introduce 3-generation scheme (allocs, revent_allocs, prev_allocs),
    because by the end of GC we know number of frees for the *previous* GC.
    
    Significant caution is required to not cross yet-unknown real value of next_gc.
    This is achieved by 2 means:
    1. Whenever I allocate a span from MCentral, I sweep a span in that MCentral.
    2. Whenever I allocate N pages from MHeap, I sweep until at least N pages are
    returned to heap.
    This provides quite strong guarantees that heap does not grow when it should now.
    
    http-1
    allocated                    7036         7033      -0.04%
    allocs                         60           60      +0.00%
    cputime                     51050        46700      -8.52%
    gc-pause-one             34060569      1777993     -94.78%
    gc-pause-total               2554          133     -94.79%
    latency-50                 178448       170926      -4.22%
    latency-95                 284350       198294     -30.26%
    latency-99                 345191       220652     -36.08%
    rss                     101564416    101007360      -0.55%
    sys-gc                    6606832      6541296      -0.99%
    sys-heap                 88801280     87752704      -1.18%
    sys-other                 7334208      7405928      +0.98%
    sys-stack                  524288       524288      +0.00%
    sys-total               103266608    102224216      -1.01%
    time                        50339        46533      -7.56%
    virtual-mem             292990976    293728256      +0.25%
    
    garbage-1
    allocated                 2983818      2990889      +0.24%
    allocs                      62880        62902      +0.03%
    cputime                  16480000     16190000      -1.76%
    gc-pause-one            828462467    487875135     -41.11%
    gc-pause-total            4142312      2439375     -41.11%
    rss                    1151709184   1153712128      +0.17%
    sys-gc                   66068352     66068352      +0.00%
    sys-heap               1039728640   1039728640      +0.00%
    sys-other                37776064     40770176      +7.93%
    sys-stack                 8781824      8781824      +0.00%
    sys-total              1152354880   1155348992      +0.26%
    time                     16496998     16199876      -1.80%
    virtual-mem            1409564672   1402281984      -0.52%
    
    LGTM=rsc
    R=golang-codereviews, sameer, rsc, iant, jeremyjackins, gobot
    CC=golang-codereviews, khr
    https://golang.org/cl/46430043

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/3c3be622011747f6db4b4cf81ed3a975dfca2b51

元コミット内容

このコミットは、Goランタイムのガベージコレクション（GC）におけるスイープフェーズを並行化するものです。具体的には、スイープフェーズをStop-the-World（STW）から外し、バックグラウンドスイーパーゴルーチンと遅延オンデマンドスイープを導入します。

この変更は、ライブヒープのサイズや、mallocとfreeの一貫した数を常に把握できるわけではないため、予想よりも複雑な実装となりました。next_gc、mprof、memstatsなど、GCに関連するすべての要素がより複雑になります。

GCの終了時、next_gcは保守的にheap_alloc*GOGCという実際の値よりもはるかに大きな値に設定されます。しかし、各スイープの後、next_gcはfreed*GOGCだけ減らされます。これにより、すべてのスイープが完了すると、next_gcは本来あるべき値になります。

mprofに関しては、GCの終了時に前のGCで解放されたオブジェクトの数がわかるため、3世代スキーム（allocs、recent_allocs、prev_allocs）を導入する必要がありました。

まだ不明なnext_gcの実際の値を超えないように、細心の注意が必要です。これは以下の2つの方法で実現されます。

  1. MCentralからスパンを割り当てるたびに、そのMCentral内のスパンをスイープします。
  2. MHeapからNページを割り当てるたびに、少なくともNページがヒープに返されるまでスイープします。 これらの対策により、ヒープが不必要に成長しないという強力な保証が得られます。

コミットメッセージには、http-1とgarbage-1という2つのベンチマークの結果が含まれており、特にgc-pause-oneとgc-pause-totalが大幅に削減されていることが示されています。これは、STW時間の削減という目標が達成されたことを裏付けています。

変更の背景

Goの初期のガベージコレクションは、マークフェーズとスイープフェーズの両方がStop-the-World（STW）で行われていました。STWとは、GCが実行されている間、アプリケーションのすべてのゴルーチンが一時停止される状態を指します。これにより、GCの実行中はアプリケーションが応答しなくなり、特にレイテンシに敏感なアプリケーションではユーザー体験に悪影響を与える可能性がありました。

このコミットの主な目的は、GCのSTW時間を短縮することです。GCの3つの主要なフェーズ（マーク、スイープ、準備）のうち、スイープフェーズはヒープ上の到達不能なオブジェクトが占めていたメモリを解放し、再利用可能にする役割を担います。このスイープフェーズをSTWから切り離し、アプリケーションの実行と並行して（concurrently）または遅延して（lazily）実行できるようにすることで、GCによるアプリケーションの一時停止を最小限に抑えることが可能になります。

特に、GoのGCは「マーク＆スイープ」方式を採用しており、オブジェクトの到達可能性をマークした後、到達不能なオブジェクトが占めるメモリ領域をスイープして解放します。このスイープ処理がヒープサイズに比例して時間がかかるため、大規模なヒープを持つアプリケーションではSTW時間が長くなる傾向がありました。スイープを並行化することで、このボトルネックを解消し、よりスムーズなアプリケーション実行を実現します。

前提知識の解説

このコミットの変更を理解するためには、Goランタイムのメモリ管理とガベージコレクションに関するいくつかの基本的な概念を理解しておく必要があります。

  • ガベージコレクション (GC): プログラムが不要になったメモリを自動的に解放する仕組みです。GoのGCは「マーク＆スイープ」アルゴリズムをベースにしています。
    • マークフェーズ (Mark Phase): GCのルート（グローバル変数、スタック上の変数など）から到達可能なすべてのオブジェクトを「ライブ（生きている）」としてマークします。このフェーズは通常STWで行われます。
    • スイープフェーズ (Sweep Phase): マークされなかったオブジェクト（到達不能なオブジェクト、つまり「ゴミ」）が占めるメモリ領域を解放し、再利用可能にします。
    • Stop-the-World (STW): GCの特定のフェーズ中に、すべてのアプリケーションゴルーチンが一時停止される状態です。GCがヒープの一貫したスナップショットを取得し、安全にメモリを操作するために必要ですが、アプリケーションの応答性を低下させます。
  • ヒープ (Heap): プログラムが動的にメモリを割り当てる領域です。Goのランタイムは、このヒープを効率的に管理するために独自のメモリ管理システムを持っています。
  • スパン (MSpan): Goのメモリ管理における基本的なメモリ割り当て単位です。ヒープはページ（通常8KB）の集まりで構成され、複数のページが集まってスパンを形成します。スパンは特定のサイズのオブジェクト（例えば、8バイトオブジェクト用、16バイトオブジェクト用など）を格納するために使用されます。
  • MCentral: 特定のサイズクラスのスパンを管理する中央キャッシュです。ゴルーチンはMCentralからスパンを取得し、そのスパンからオブジェクトを割り当てます。
  • MHeap: すべてのスパンを管理するグローバルなヒープです。MCentralがスパンを使い果たした場合、MHeapから新しいスパンを取得します。
  • gcpercent: 環境変数GOGCで設定されるGCのトリガー閾値です。デフォルトは100です。gcpercent=100の場合、現在使用中のヒープメモリが2倍になったときにGCがトリガーされます。例えば、現在4MB使用している場合、8MBに達するとGCが実行されます。
  • next_gc: 次のGCがトリガーされるヒープ割り当ての目標値を示すランタイム変数です。
  • mprof: メモリプロファイリングに関連する統計情報です。

技術的詳細

このコミットは、GoランタイムのGCスイープフェーズを並行化するために、いくつかの重要な技術的変更を導入しています。

  1. バックグラウンドスイーパーゴルーチン (bgsweep):

    • GCのマークフェーズが完了した後、専用のバックグラウンドゴルーチンが起動され、ヒープ上のスパンを並行してスイープします。
    • このゴルーチンはruntime·sweepone()を繰り返し呼び出し、スイープが必要なスパンを一つずつ処理します。
    • スイープするスパンがなくなると、このゴルーチンは自身をパーク（一時停止）し、次のGCサイクルで再び起動されるのを待ちます。
    • これにより、アプリケーションの実行と並行してメモリの解放が進み、STW時間が短縮されます。

  2. 遅延オンデマンドスイープ (runtime·MSpan_EnsureSwept, runtime·MCentral_AllocList, MHeap_Reclaim):

    • バックグラウンドスイーパーだけでは、ヒープの成長速度が速い場合にスイープが追いつかない可能性があります。
    • このため、メモリ割り当て時に必要に応じてスパンをスイープする「オンデマンドスイープ」が導入されました。
    • runtime·malloc（オブジェクト解放時）やaddspecial/removespecial（ファイナライザやプロファイル関連の特殊なレコード操作時）など、スパンのGCビットマップを読み書きする可能性のある操作の前に、runtime·MSpan_EnsureSwept(s)が呼び出されます。これは、スパンがまだスイープされていない場合、その場でスイープを実行するか、バックグラウンドスイーパーが完了するのを待つことで、GCビットマップの破損を防ぎます。
    • runtime·MCentral_AllocList（MCentralからスパンを割り当てる際）では、スイープが必要なスパンを優先的にスイープし、再利用を試みます。
    • runtime·MHeap_Alloc（MHeapから新しいページを割り当てる際）では、MHeap_Reclaimが呼び出されます。これは、新しいメモリを割り当てる前に、既存のヒープから少なくとも要求されたページ数分のメモリをスイープして解放しようとします。これにより、ヒープが不必要に成長するのを防ぎます。

  3. sweepgen (スイープ世代) の導入:

    • MSpan構造体にsweepgenフィールドが追加されました。これは、各スパンがどのGC世代でスイープされたか、またはスイープが必要か、スイープ中かを示すために使用されます。
    • mheap.sweepgenはGCごとに2ずつインクリメントされます。
    • s->sweepgen == h->sweepgen - 2: スパンはスイープが必要な状態です。
    • s->sweepgen == h->sweepgen - 1: スパンは現在スイープ中です。
    • s->sweepgen == h->sweepgen: スパンはスイープ済みで、使用可能です。
    • このsweepgenを用いることで、並行スイープ中にスパンの一貫性を保ち、古いGC世代のスパンが誤って再利用されたり、GCビットマップが破損したりするのを防ぎます。

  4. next_gc の動的な調整:

    • 並行スイープでは、GC終了時に正確なライブヒープサイズが不明なため、next_gcの計算が複雑になります。
    • GC終了時、next_gcは保守的にmstats.heap_alloc + mstats.heap_alloc * gcpercent / 100という大きな値に設定されます。これは、すべてのメモリがライブであると仮定した値です。
    • その後、runtime·MSpan_Sweepがスパンをスイープしてメモリを解放するたびに、mstats.next_gcは-(uint64)(freed_size * (gcpercent + 100)/100)だけ減らされます。
    • これにより、スイープが進むにつれてnext_gcが実際のライブヒープサイズに近づき、次のGCトリガーが適切に調整されます。

  5. mprof の3世代スキーム:

    • メモリプロファイリング（mprof）の統計情報（割り当てと解放の数、バイト数）を正確に収集するために、Bucket構造体にprev_allocs, prev_freesなどのフィールドが追加されました。
    • これは、GC終了時に「前のGCで解放されたオブジェクトの数」がわかるという特性に対応するためです。
    • MProf_GC関数が呼び出されるたびに、recent統計がprev統計に移動され、prev統計がallocs/freesに加算されます。これにより、GCサイクルをまたいだ正確なプロファイリングが可能になります。

  6. ロックの変更:

    • ファイナライザのキューイングやバックグラウンドスイーパーの管理のために、finlockがgclockに置き換えられ、GC関連のロックがより一元的に管理されるようになりました。

これらの変更により、GoのGCは「部分的に並行（partially concurrent）」なGCとなり、マークフェーズはSTWのままですが、スイープフェーズは並行して実行されるようになりました。

コアとなるコードの変更箇所

このコミットにおける主要なコード変更は以下のファイルに集中しています。

  • src/pkg/runtime/malloc.h: MSpan構造体へのsweepgenフィールドの追加、新しい関数の宣言。
  • src/pkg/runtime/malloc.goc: runtime·freeにおけるruntime·MSpan_EnsureSweptの呼び出し。
  • src/pkg/runtime/mcentral.c: runtime·MCentral_AllocListにおけるスイープロジックの追加、runtime·MCentral_FreeSpanの変更。
  • src/pkg/runtime/mgc0.c: GCのメインロジックが記述されているファイルで、最も広範な変更が行われています。
    • runtime·MSpan_EnsureSwept、runtime·MSpan_Sweep、bgsweep、runtime·sweeponeといった並行スイープの核心となる関数の実装。
    • runtime·gcにおけるスイープフェーズの変更、next_gcの計算ロジックの更新。
    • gcstatsへの新しい統計情報の追加。
  • src/pkg/runtime/mheap.c: MHeap構造体へのsweepgen関連フィールドの追加、MHeap_Reclaim関数の追加、runtime·MHeap_Allocにおけるスイープの考慮。
  • src/pkg/runtime/mprof.goc: メモリプロファイリングの3世代スキームの実装。

コアとなるコードの解説

src/pkg/runtime/malloc.h

struct MSpan
{
	// ...
	uint32	sweepgen; // sweep generation, see comment in MSpan
	// ...
};

void	runtime·MSpan_EnsureSwept(MSpan *span);
bool	runtime·MSpan_Sweep(MSpan *span);

// ...

struct MHeap
{
	// ...
	MSpan **sweepspans;		// copy of allspans referenced by sweeper
	uint32	sweepgen;		// sweep generation, see comment in MSpan
	uint32	sweepdone;		// all spans are swept
	// ...
};

MSpan構造体にsweepgenが追加され、各スパンのスイープ状態を追跡します。MHeapにはグローバルなsweepgen、スイーパーが参照するスパンのコピーsweepspans、そしてスイープ完了を示すsweepdoneが追加されています。

src/pkg/runtime/malloc.goc

void runtime·free(void *v)
{
	// ...
	// Ensure that the span is swept.
	// If we free into an unswept span, we will corrupt GC bitmaps.
	runtime·MSpan_EnsureSwept(s);
	// ...
}

オブジェクトを解放する際に、そのオブジェクトが属するスパンが確実にスイープされていることをruntime·MSpan_EnsureSweptで確認します。これは、GCビットマップの破損を防ぐための重要な安全策です。

src/pkg/runtime/mcentral.c

int32 runtime·MCentral_AllocList(MCentral *c, MLink **pfirst)
{
	// ...
	sg = runtime·mheap.sweepgen;
retry:
	for(s = c->nonempty.next; s != &c->nonempty; s = s->next) {
		if(s->sweepgen == sg-2 && runtime·cas(&s->sweepgen, sg-2, sg-1)) {
			runtime·unlock(c);
			runtime·MSpan_Sweep(s); // On-demand sweep
			runtime·lock(c);
			goto retry;
		}
		if(s->sweepgen == sg-1) {
			continue; // Being swept by background sweeper, skip
		}
		goto havespan; // Already swept, allocate from it
	}
	// ... (similar logic for empty list)
	// ...
}

MCentral_AllocListは、スパンを割り当てる際に、まずnonemptyリストとemptyリストを走査し、スイープが必要なスパン（s->sweepgen == sg-2）を見つけると、runtime·MSpan_Sweepを呼び出してその場でスイープを実行します。これにより、メモリ割り当て時に必要なメモリを即座に利用可能にすることができます。

src/pkg/runtime/mgc0.c

// Concurrent sweep.
// The sweep phase proceeds concurrently with normal program execution.
// The heap is swept span-by-span both lazily (when a goroutine needs another span)
// and concurrently in a background goroutine (this helps programs that are not CPU bound).
// ... (詳細な説明) ...

void runtime·MSpan_EnsureSwept(MSpan *s)
{
	uint32 sg;
	sg = runtime·mheap.sweepgen;
	if(runtime·atomicload(&s->sweepgen) == sg)
		return; // Already swept
	if(runtime·cas(&s->sweepgen, sg-2, sg-1)) {
		runtime·MSpan_Sweep(s); // Sweep it now
		return;
	}
	// Unfortunate condition, wait for background sweeper
	while(runtime·atomicload(&s->sweepgen) != sg)
		runtime·osyield();  
}

bool runtime·MSpan_Sweep(MSpan *s)
{
	// ... (スイープのコアロジック) ...
	// Decrement next_gc by freed memory
	runtime·xadd64(&mstats.next_gc, -(uint64)(nfree * size * (gcpercent + 100)/100));
	// ...
	return res; // true if span returned to heap
}

static void bgsweep(void)
{
	g->issystem = 1;
	for(;;) {
		while(runtime·sweepone() != -1) {
			gcstats.nbgsweep++;
			runtime·gosched(); // Yield to other goroutines
		}
		// ... (finalizer logic and park) ...
	}
}

uintptr runtime·sweepone(void)
{
	// ... (一つスパンをスイープするロジック) ...
	if(!runtime·MSpan_Sweep(s))
		npages = 0;
	// ...
	return npages; // pages returned to heap, or -1 if nothing to sweep
}

void gc(struct gc_args *args)
{
	// ...
	// Sweep what is not sweeped by bgsweep.
	while(runtime·sweepone() != -1)
		gcstats.npausesweep++; // Count sweeps during STW
	// ...
	// Conservatively set next_gc to high value assuming that everything is live
	// concurrent/lazy sweep will reduce this number while discovering new garbage
	mstats.next_gc = mstats.heap_alloc+mstats.heap_alloc*gcpercent/100;
	// ...
	// Start/wake up background sweeper goroutine
	runtime·lock(&gclock);
	if(sweep.g == nil)
		sweep.g = runtime·newproc1(&bgsweepv, nil, 0, 0, runtime·gc);
	else if(sweep.parked) {
		sweep.parked = false;
		runtime·ready(sweep.g);
	}
	runtime·unlock(&gclock);
	// ...
}

mgc0.cは並行スイープの心臓部です。

  • runtime·MSpan_EnsureSweptは、スパンがスイープ済みであることを保証します。必要であればその場でスイープするか、バックグラウンドスイーパーの完了を待ちます。
  • runtime·MSpan_Sweepは、個々のスパンをスイープする実際の処理を行います。解放されたメモリ量に基づいてnext_gcを減らします。
  • bgsweepは、バックグラウンドでruntime·sweeponeを繰り返し呼び出し、ヒープをスイープする専用のゴルーチンです。
  • runtime·sweeponeは、スイープが必要なスパンを一つ見つけてスイープし、解放されたページ数を返します。
  • gc関数は、GCの開始時に残っている未スイープのスパンを強制的にスイープし（gcstats.npausesweepでカウント）、next_gcを保守的に設定します。また、bgsweepゴルーチンを起動または再開します。

src/pkg/runtime/mheap.c

static void MHeap_Reclaim(MHeap *h, uintptr npage)
{
	// To prevent excessive heap growth, before allocating n pages
	// we need to sweep and reclaim at least n pages.
	if(!h->sweepdone) {
		// Prioritize sweeping busy spans with large objects
		// Then smaller objects
		// Finally, sweep everything that is not yet swept
	}
}

MSpan* runtime·MHeap_Alloc(MHeap *h, uintptr npage, int32 sizeclass, bool large, bool zeroed)
{
	// ...
	if(!h->sweepdone)
		MHeap_Reclaim(h, npage); // Reclaim pages before allocation
	// ...
}

MHeap_Reclaimは、新しいメモリを割り当てる前に、ヒープが不必要に成長するのを防ぐために導入されました。これは、まず大きなオブジェクトのスパンからスイープを試み、次に小さなオブジェクトのスパン、そして最後にまだスイープされていないすべてのスパンをスイープして、要求されたページ数分のメモリを確保しようとします。runtime·MHeap_AllocはこのMHeap_Reclaimを呼び出します。

src/pkg/runtime/mprof.goc

struct Bucket
{
	// ...
	struct  // typ == MProf
	{
		// ...
		uintptr	prev_allocs;  // since last but one till last gc
		uintptr	prev_frees;
		uintptr	prev_alloc_bytes;
		uintptr	prev_free_bytes;

		uintptr	recent_allocs;  // since last gc till now
		uintptr	recent_frees;
		uintptr	recent_alloc_bytes;
		uintptr	recent_free_bytes;
		// ...
	};
	// ...
};

void MProf_GC(void)
{
	Bucket *b;
	for(b=mbuckets; b; b=b->allnext) {
		b->allocs += b->prev_allocs;
		b->frees += b->prev_frees;
		b->alloc_bytes += b->prev_alloc_bytes;
		b->free_bytes += b->prev_free_bytes;

		b->prev_allocs = b->recent_allocs;
		b->prev_frees = b->recent_frees;
		b->prev_alloc_bytes = b->recent_alloc_bytes;
		b->prev_free_bytes = b->recent_free_bytes;

		b->recent_allocs = 0;
		b->recent_frees = 0;
		b->recent_alloc_bytes = 0;
		b->recent_free_bytes = 0;
	}
}

void runtime·MProf_Free(Bucket *b, void *p, uintptr size, bool freed)
{
	runtime·lock(&proflock);
	if(freed) {
		b->recent_frees++;
		b->recent_free_bytes += size;
	} else {
		b->prev_frees++;
		b->prev_free_bytes += size;
	}
	// ...
}

mprof.gocでは、メモリプロファイリングの統計を正確に収集するために、Bucket構造体にprev_allocsなどのフィールドが追加され、3世代スキームが導入されました。MProf_GC関数は、GCが実行されるたびに統計を更新し、recentな統計をprevに、prevな統計を最終的なallocs/freesに加算します。runtime·MProf_Freeは、オブジェクトが実際に解放されたかどうか（freed引数）に基づいて、recentまたはprevの解放統計を更新します。

関連リンク

  • Goのガベージコレクションに関する公式ドキュメントやブログ記事は、Goの進化とともに更新されるため、最新の情報を参照することが重要です。
  • Goのソースコードリポジトリ: https://github.com/golang/go
  • このコミットの変更リスト（Gerrit）: https://golang.org/cl/46430043

参考にした情報源リンク

  • Goのガベージコレクションの歴史と進化に関する記事（例: "Go's new GC: less pause time, more throughput" by Rick Hudson, "The Go garbage collector: Prioritizing low latency and simplicity" by Rick Hudson and Michael Knyszek）
  • Goランタイムのソースコード（特にsrc/runtimeディレクトリ）
  • Goのメモリ管理に関する技術ブログやカンファレンス発表資料

これらの変更により、GoのGCはより効率的になり、特にレイテンシが重要なアプリケーションにおいて、GCによる一時停止が大幅に削減されました。