ガベージコレクション概要

解放を書き忘れた 1 行が、3 日後にサーバーを落とす

C で malloc した領域は、free を呼ぶまで空きに戻りません。1 リクエストにつき 200 バイト解放し忘れるだけでも、毎秒 100 リクエストを捌くサーバーなら 1 日で 1.7GB 積み上がります。逆に、まだ誰かが持っているポインタの先を free してしまうと、次にそこを読んだコードが意味不明な値をつかみます。前者がメモリリーク、後者が use-after-free です。

どちらも「もう誰も使っていないか」を人間が判断しているから起きます。ならばその判断を機械にやらせよう、というのがガベージコレクションです。

素朴な答えは、指されている数を数えること

一番わかりやすいのは、オブジェクトごとに「今いくつの変数から指されているか」を数える方法です。代入で 1 増え、変数がスコープを抜けると 1 減り、0 になった瞬間に解放します。CPython の主力はこれで、sys.getrefcount で数を覗けます。

不要になった瞬間に回収されるので、掃除のために止まる時間もほぼありません。ただしこの方式には、塞げない穴が 1 つあります。

a = {}
b = {}
a["next"] = b
b["prev"] = a
del a, b        # 変数は消えたが、互いに指し合っているのでカウントは 1 のまま

外から見れば完全なゴミですが、2 つは互いを指しているためカウントが 0 になりません。輪になったゴミは、数を数える方式では永久に回収できません。

「指されているか」ではなく「辿り着けるか」で決める

そこで発想を変えます。実行中のスタックやグローバル変数を出発点として、参照をひたすら辿ります。辿り着けたものが生きているもので、それ以外はすべてゴミです。印を付けて回る工程をマーク、印の無いものを回収する工程をスイープと呼びます。

D と E は互いを指していますが、出発点から辿り着けないので回収されます。先ほどの穴が塞がりました。

代わりに支払うものがあります。辿っている最中にオブジェクトの繋がりが書き換わると答えが狂うため、この方式はアプリを止めて実行する必要が出てきます。数十ミリ秒アプリ全体が固まる、あの停止時間の正体です。Java の ZGC や Go のように、アプリと並行して辿ることで停止を 1 ミリ秒以下に抑える実装が主流になってきました。

GC があってもリークは起きる

回収されないのは「辿り着けてしまうゴミ」です。グローバルな辞書にキャッシュを入れっぱなしにする、イベントリスナーを登録したまま外し忘れる。参照が残っている以上、GC から見れば生きているオブジェクトなので、いつまでも解放されません。

自動になったのは解放の実行であって、「もう要らない」と手放す判断ではない、ということです。