Network Attached Processing の Pauseless GC

更新履歴
(2005.11.18) 脚注*2を加筆。
(2005.11.17) 文章を推敲。
(2005.11.14) NMT bit の read barrier について嘘を書いていたので修正。

1. 前置き
2. Pauseless GC
3. Marking Phase
4. Relocation & Remap Phase
5. おしまい
6. 参考文献

Azul Sysmtes (米日) は Java や .NET に特化した専用計算機 Network Attached Processing (NAP) を提唱し、 製品として Azul Compute Appliance を開発した。 Azul Compute Appliance は、 すでに稼動中の Solaris/Linux の J2SE/J2EE システムの Java VM を Azul Systems が提供するスタブ JVM に置き換えるだけで、 元のマシンで実行されていたプログラム(バイトコード) が Azul Compute Appliance に転送・実行されるようになる リモート計算機だ (*1)。

Azul Systems は専用の CPU (Vega) を一から設計・実装し、 その上で動く Azul Virtual Machine も独自開発した(*2)。 そのためふつ〜のプロセッサの Java VM にはない独自機構を数多く備えている。 このページでは NAP の特殊な機構のうち、 JavaOne Tokyo 2005 で 開発者の Dr. Cliff Click から聞いた GC アルゴリズム部分を紹介する。

Azul Compute Appliance このボディで 96 コアの SMP マシン

ガーベージコレクション(GC) の分類方法には Stop-The-World 型 (STW) と On-the-fly 型 の 2 つに分ける方法がある。

STW は GC が起動する前にアプリケーションスレッド(Java の場合は Java スレッド) を「時よ止まれ」と全て停止ささせ、 その後にガーベージとなったオブジェクトを回収し、 回収が終わったらアプリケーションスレッドを再開するタイプの GC だ。 そのためどうしても GC ポーズ時間 が生じる。 このポーズ時間の間、 タイマー処理もネットワークの待ち受けも停止して何もできない状態が続く。 そのためポーズ時間が長すぎるといろいろ破綻が起きる。

一方 On-the-fly 型 GC の場合、アプリケーションスレッドと GC スレッドが平行に動作し、 アプリケーションスレッドを完全に停止させることなく GC スレッドがガーベージを再利用可能にしてゆく。

上の説明だけを読むと On-the-fly 型の方が優れていると思うかもしれないが、 GC 以外も含めた全体性能・信頼性を比較すると On-the-fly 型 GC は STW 型 GC に負けることが多い。 そのため各種言語・ランタイムの GC アルゴリズムを見ると、 STW 型を採用する方が多い。

ただ GC 採用に先鞭をつけた Java システムは、 エンタープライズシステムの世界で使用されることが多くなってきた。 STW 型 GC の多くはメモリの使用量に比例して GC ポーズ時間が伸びてゆく傾向があるので、 Java 仮想マシンにギガバイト単位のメモリが与えられると、 GC ポーズ時間は数秒〜数分に到達するようになる。 これではたまらんので最近の Sun、IBM の Java 仮想マシンは STW 型と On-the-fly 型の折衷である Mostly Concurrent Mark & Sweep を採用したりして、GC ポーズ時間の増大を凌ごうとしている。 しかし mostly という単語がつくことから分かるように この GC は完全な無停止 GC ではなく、 やはり使用メモリ量に比例したGC停止時間が必要となる。

ここから本題。 Azul Sytems の NAP は Pauseless GC という一風変わった GC アルゴリズムを採用している。 Pauseless GC は理論上 STW がない。 にも関わらず性能もあまり悪くないというキ印もの。

Pauseless GC は、 まず以下の 3 つのフェーズを持つ GC である。

1. Marking phase: 生きているオブジェクトを探すためマーキングを行う。
2. Relocation phase: 連続した領域をフリーにするため、オブジェクトを別の場所に移動させる。
3. Remap phase: 移動元のオブジェクトを指す全てのポインタを移動先を指すように書き換える。

GC スレッドは marking → relocation → remap の順に GC を実行し、 その間にアプリケーションスレッドも平行(concurrent) に動作する。 また 1回目の GC の remap phase と 2 回目の GC の makring phase も concurrent に重ね合わせることが可能だ。

注目すべきは Pauseless GC は「オブジェクトの移動」をやるタイプの GC だという点。 GC の別の分類方法では、 Mark & Sweep GC のようにオブジェクトを割り当てたら移動させず空き領域はフリーリストで管理する GC と、 Copying GC や Mark & Compaction GC のようにオブジェクトを移動させて 連続した空き領域を作る GC に分類することができる。

前者のオブジェクトの移動をしないタイプの方が GC 時間は短くなるし concurrent にもしやすいが、 どうしてもメモリ空間の断片化が避けられない。 生きているオブジェクトが飛び石のようにヒープ中に散らばるので、 プログラムが長い間 稼動していると 「100MBのメモリがあって 90% はフリーなのに 10K バイトのオブジェクトが割り付けられない」というような事態に陥る。 それじゃ困るので実用を考えると メインの GC が非移動型でも フラグメンテーションが進んだ場合の奥の手として移動型 GC を用意せざるえない。

一方、 後者のオブジェクト移動型 GC は メモリ空間に隙間がなくなりフリーな領域を有効に使用できるし、 空間内のオブジェクトの充填率が高い分 キャッシュヒット率も上げることができる。 ただしふつ〜のアーキテクチャでの GC 実装では、 relocation と remap は Java スレッドを停止させた状態で同時に行う必要がある(*3)。 そのため 1回の GC ポーズ時間がどうしても長くなる傾向にある。 しかし Pauseless GC の場合 ここも concurrent に動作させることができる のが凄いのだ。

もう一点すごいのはmarking が完全に concurrentな点だ。 Mostly concurrent ではない。 この実現方法が凄いと言うか、インチキというか... 鍵になっているのはハードウェア・サポートだ。

Marking を Java スレッドと GC スレッドで並列にやるのは難しい。 2つ問題がある。

1つは、 marking をしている間に Java スレッドがプログラムを進めてしまうと、 それまで生きていたオブジェクトが死んでしまう可能性があること。 そのため concurrent marking は「本当はガーベージなんだけど生きているとマークをつけてしまう」可能性がある。 ただこういう漏れガーベージは、効率が悪くなるがエラーにはならないので、無視することは可能だ。

もう1つはより深刻で、 「本当は生きているんだけどマークがつけられない」可能性だ。 マーキングした後のオブジェクトを Java スレッドが書き換えてしまうと問題が発生する。 図1のようなパターンは、 GC スレッドと Java スレッドがコンテキストスイッチによってタイムスライスしながら動いていると考えて欲しい。 GC スレッドが Step1 まで処理を進めた後で停止し、Java スレッドが Step2 の処理をしてしまうと、 Step3 で GC スレッドが再開してもオブジェクト E が未マークのまま放置されることになる。 誤ってガーベージと判定されてしまうのだ。 オブジェクト E を回収してしまうと、 エラーが発生することになる。

図1: マーキングを並列に行った場合の問題

Mostly Concurrent Marking

このマーク漏れの問題を Mostly Concurrent Marking は、 concurrent marking phase と serial makring phase の 2つに分けることで解決した。 最初、GC スレッドが concurrent marking phase を処理している間は Java スレッドに動作させることができるが、 concurrent marking phase が終了すると Java スレッドは停止させて GC スレッドだけが serial marking phase で塗り洩らしの解決をする。 つまり serial marking phase 中は STW だ。

塗り残しとなるのは、 Java スレッドによって参照が書き換えられたオブジェクトである。 そのため Java スレッドは write barrier を導入し、 参照の書き換えが起こったオブジェクトに専用のタグを打っていく。 Serial marking phase では、 「マーク済みであり」かつ「書き換えタグ」がついたオブジェクトを起点にして 2度目のマーキングを行う。 処理が完了すれば、生きているオブジェクトの全てがマーク済みになる。

図2: Mostly Concurrent の解決方法

だが mostly concurrent marking には serial makring phase でどうしても STW が必要になってしまう。 経験的には concurrent marking phase で大部分のマーキングを済ませることができ serial marking phase は残りの部分だけを行うので 大概の場合には STW 時間は短い。 ただしオブジェクトのリンク状態によっては serial marking phase に時間がかかることもある。 このため「最悪」の GC ポーズ時間は短くならない。

Pauseless GC の Concurrent Marking

Pauseless GC は別のアプローチを使う。 それは巡回したオブジェクトにマークをつけると同時に、 巡回に使った参照にもチェックをつけるという方法だ。 Java の参照は実装的にはメモリ上のオブジェクトの位置を指す「ポインタ」として実装されている。 Java オブジェクトは 64 ビット境界にあわせて配置されるので 「ポインタ」の下位3ビットは常に 0 になる。 常に 0 になっているビットというのは冗長なので、 このビットの一つを Not-Marked-Through (NMT) bit というタグに転用する。 GC スレッドは marking 中に巡回した参照(ポインタ)の NMT ビットを立て、 巡回・未巡回を区別していく。

同時に Java スレッドも concurrent marking に協力する。 Java スレッドがオブジェクトの参照をする時に read barrier を行う。 NMT bit がセットされていない参照(ポインタ)をロードすると、 Java スレッドは発見した未巡回ポインタを GC スレッドの queue に突っ込み、 (後で同じトラップに引っかからないように) NMT bit を立てて元の処理に戻る。 C++ であらわすと LoadReferenceWithReadBarrier のようになる。

Object* LoadReferenceWithReadBarrier(Object** address) {
  intptr_t value = (intptr_t)(*address);

  if (value & NMT_MASK) {
    return (Object*)(~7 & value);        // 下位3ビットのクリア
  } else {
    Object* pointer = (Object*)value;
    push_marking_queue(pointer);             // marking queue
    *address = (Object*) (value | NMT_MASK); // NMT bit をセット 
    return pointer;
  }
}

// メモリ上にあるオブジェクトのポインタ pointer を使用する時は LoadReferenceWithReadBarrier を通してから
extern Object* pointer;

Object* p = LoadReferenceWithReadBarrier(&pointer);
int fieldValue = p->getField(fieldDescriptor);

ところで NMT ビットのアイデアは昔からあったのだが、 このアイデアは GC の歴史の中に埋もれてしまっていた。 それはソフトウェアでこの処理をやろうと思うと かな〜り重い のだ。 NMT ビットの元アイデアも、 チップを一から起こした専用並列計算機の中で動いていた。

NAP はプロセッサに NMT bit チェック付きロード命令 を追加して この問題を解決している。 Java スレッドが参照オブジェクトをロードする時は、この専用ロード命令の方を使う。 専用ロード命令は NMT bit がセットされていない未巡回のポインタを読み込むと、 高速なトラップルーチンに制御を移す。 トラップルーチン内で read barrier 処理を完了すると、 元のプログラムに復帰する。 一方、 NMT bit がセットされている場合には 通常のロード命令として動作する。 この時の遅延はノーマルなロード命令より1サイクル余分にかかる程度なので、 全体としては非常に高速に NMT bit の処理を進めることが可能だ。

オブジェクトが生きているか死んでいるかが判断できた後は、 死んでいるオブジェクト(ガーベージ)を回収する必要がある。 NAP は以下のような原則で、ガーベージを回収する。

1. NAP はヒープメモリ空間をページで区切って使用している。 ページは TLB ページの数倍に設定されている。
   説明上、ヒープページ=TLB ページとする。
2. ページ内のすべてのオブジェクトがガーベージの場合、 そのページはフリーとなる。
3. 2. のルールでフリー化できるパターンは少ない。 そこで生きているオブジェクトが少ないページを選択し、 その中にあるオブジェクトを別ページに移動させ、ページ内を空にする。 その後でページのフリー化を行う。

もう一つ前提がある。 NAP は 64-bit プロセッサなので、かなり広い仮想メモリ空間を使用可能だ。 Java のヒープはこの広大な仮想メモリ空間上に配置される。 ただし実メモリは mmap/munmap の API を使って 適時貼り付けたり剥がしたりされる。 上のページのフリー化とは、実装的には実メモリを剥ぎ取る操作にあたる。

Forwarding Pointer

GC スレッドがオブジェクトの移動を Java スレッドと平行して行うのはかなりの難題だ。 オブジェクトの移動自体は、 オブジェクトをコピーして元のあったオブジェクトを破壊(回収)すればよいのだが、 元のオブジェクトを指している参照(ポインタ)を新しいオブジェクトを指すように書き直さなければならない (でないと dangling pointer だ)。

このようなオブジェクトの移動 & ポインタの張り替え方法として一般的なのは、 forwarding pointer と呼ばれる手法だ。 まずオブジェクトをコピーし、元のオブジェクトを潰して移動先のポインタを埋め込む。 そのためオブジェクトは「ノーマルな状態」と「Fowarding pointer が埋め込まれた fowardee 状態」の二態があり、 タグ等で区別することになる。 オブジェクトを参照する場合、 参照先が forwardee 状態かどうかを毎回チェックし、 fowardee なら forwarding pointer を手繰って移動先を確認し、 移動元のオブジェクトを指しているポインタを書き改めた後で、 移動先のオブジェクトを参照する。

図4: Forwarding Pointer

Object* CheckForwardingPointer(Object** address) {
  Object* pointer = *adress;

  if (pointer->is_forwarding()) {
    pointer = pointer->get_fowarding_address();
    *address = pointer;
  }
  return pointer;
}

このやり方はコストに大きな問題が残る。

• すべての参照操作で CheckForwardingPointer のようなチェックが必要になり、 とんでもなく重い処理となる。
• Forwarding pointer を仕掛けた移動元オブジェクトは、 元のオブジェクトを指すポインタがなくなるまで回収できない。 そもそもメモリが不足しているから GC を行うのに、 古いオブジェクトの領域と新しいオブジェクトの領域の両方を消費するのは非効率。

Pauseless GC の オブジェクトの移動

NAP のとったオブジェクトの移動方法は、 基本的には forwarding pointer の考え方に近い。 ただし ハードウェアサポート で問題を解決している。 肝となるテクニックはページ単位での TLB ページの属性変更だ。

元々 UNIX 系 OS の仮想メモリにはページ単位で読み・書き・実行の属性をオン・オフできる機能と プログラムから属性を指定可能な mprotect API があった。 NAP のプロセッサはそれに加えて TLB 機能を拡張し、特殊な属性を追加した。 前述の read barrier 付きロード命令で読み込んだポインタが、 この保護属性を指定したページを指している場合はトラップが発生する。 そのためこの TLB プロテクトされたメモリページは、 GC スレッドは自由に読み書きできるが、 Java スレッドにのみ影響を与える。

図5: NAP のオブジェクトの移動

GC スレッドは特殊な TLB プロテクトを掛けた後で、ずんずん勝手に作業を進める。 空にしたいページから別のページにオブジェクトを移動させる (この時 一緒にヒープの外側に移動元アドレス→移動先アドレスの変換表を作っておく)。 移動が終わると、 移動元のアドレスを保持している古いポインタを探し出して、 移動先アドレスに書き直していく。

一方、Java スレッドが移動中のオブジェクトを指すポインタを読み込むと、トラップルーチンに処理が移る(*4)。 トラップルーチンでは GC スレッドが作った変換表を参照して、 問題となるポインタの値を新しいアドレスに書き直してから実行を再開する。 トラップから戻ると参照(ポインタ)の内容は自動的に remap されていることになる。

このように Pauseless GC の remap phase は、 GC スレッドと Java スレッドの両側で進んでいく。

上のようなハードウェアサポートを用いて NAP は Puaseless GC を実現している。 一部の実装的な理由で STW が必要になるが、 それでも数ギガバイトのメモリを使って 30 ミリ秒程度の停止しかなく、 停止時間が秒のオーダーになることはないそうだ。 一方 Sun HotSpot VM だと Pentium4 3GHz 程度のマシンで 2Gバイトメモリを使用すると、 プログラムの性質によっては GC 停止時間が 1分を越えてしまう。 ならば、NAP の Pauseless GC の停止時間は実用上まったく問題ない短さであるといえよう。

とはいえねぇ。 この性能は ハードウェアサポート あっての賜物ですよ。 ふつ〜のプロセッサ (x86 / PowerPC / SPARC / IA-64) と ふつ〜の OS (Linux / Windows / Solaris) で これと同じアルゴリズムを実装するのはムリぽ。 でもアーキテクチャ屋としては、専用のプロセッサを起こしていじり回すのは楽しいだろうね。

1. JavaOne Tokyo 2005 The Pauseless GC Algorithm

2. Azul Systems: Pauseless Garbage Collection: Improving Application Scalability and Predictability

Azul 社が提供している Pauseless GC の資料。 読むためには PDF をダウンロードした後に認証が必要。

3. www.nminoru.jp: Mostly Concurrent Mark & Sweep の解説

4. Richard Jones & Rafael Lins Garbage Collection: Algorithms for Automatic Dynamic Memory Management

Jones 先生 の GC の教科書。 初歩的な歴史から相当なアドバンスまでが網羅されている。

*1

ネイティブコードは NAP 上では実行できないのでホスト側で実行することになる。
ホストマシンと NAP との間の通信が必要になるため、 ホストマシンだけで閉じた Java VM と比べると 100 倍以上遅くなるそうだ。

*2

Vega のベースは 32 レジスタを備えた 64-bit RISC CPU。
これに Java VM や .NET (CLR) を高速に動作させるための特殊な機構を備えている。
分かっている範囲では以下の3つの機構がある。

Pauseless GC のための read barrier 命令

これは本稿で説明したもの。

Stack Based Allocation のための write barrier 命令

Java はオブジェクトをヒープに割り付けるというセマンティクスになっているが、 特殊なパターンに限ると C# の struct 型のローカル変数のように スレッドスタックに割り付けを行うことができる。 スタックへの割り付けは他のスレッドとの同期が不要で、 ヒープを汚さないため高速化が可能だ。
ただしメソッド M の中で生成されたオブジェクト O がスタック割り付け可能なためには、 メソッド M から脱出する時に O の寿命が尽きている必要がある。 このオブジェクトの生存区間解析をエスケープ解析(escape analysis) と呼ぶ。 解析レベルが何段階があるが、 軽い解析ではスタックに割り付けられるオブジェクトが見つからず、 重い解析を行うと非常にコストの高い計算が必要になってしまう。

NAP では軽めのエスケープ解析とハードウェアサポートを用いて、 「投機的」なスタック割り付けを行う。 「このオブジェクトはスタックに割り付けられそうだ」と目星をつけて、 博打を打ってスタックに割り付けてしまう。 後はハードウェア・サポートによる write barrier 命令がこれを監視して、 スタック割り付けされたオブジェクトのポインタが領域外に脱出しようとするとトラップをあげる。 トラップルーチン内では、 「博打に負けた」オブジェクトはスタックからヒープに移動させられるという寸法 (この処理は STW を掛けずに可能だが、それなりにペナルティコストがかかる)。

Azul はいろいろなプログラムでテストして、 半分ぐらいのオブジェクトをスタック割り付けできることを確認している。

Java synchronized methods & blocks のためのハードサポート

これは詳細を知らないのだが cache 機構に絡むものらしい。
Intel が Prescott で導入した同期命令(MONITOR/MWAIT) のようなものではないかと予想する (2003/2/23の日記)。

また Chip-Multi-Processor で 1つのダイ上に 24 コアを持つ。 Azul Compute Appliance は最大 16 ダイを搭載し 384 コアで稼動させることができる。 Appliance の OS は Linux 2.6 & Debian をカスタマイズしたものを使っていて、 本当はふつうの UNIX マシンのようにログインすることもできるらしい。

*3

オブジェクトの参照がアドレスを直接保持する C のポインタスタイルの場合にはという但し書きがつく。 参照が間接ハンドラなどの方法で実装されていれば、 オブジェクトの移動とアドレスの書き替えを瞬時に行う方法はある。

*4

TLB プロテクトは GC に関係ないオブジェクトのアクセスは高速で行えるが、 プロテクトページにアクセスがあった場合はトラップが発動するため CheckForwardingPointer 以上にコストが高くなる。 ただし NAP の GC は、 生きているオブジェクトが疎なページを選択してオブジェクトの移動を行っているので、 TLB プロテクト領域へのアクセスは無視できる程度の頻度でしか発生しないそうだ。 そのため、この機構は十二分にペイする。

コメント