JavaOne：Cliff Click氏がスケーラブルな非ブロッキングコーディングスタイルを語る

作者 Charles Humble , 翻訳者 編集部 投稿日 2008年6月1日

セクション

設計/アーキテクチャ,

デベロップメント

トピック

JavaOne 2008 ,

Java One ,

Java ,

言語 ,

Parallel Programming ,

プログラミング ,

パフォーマンス&スケーラビリティ

1967年Gene Amdahl氏が指摘したのは、基本であると思われることが並行コードを作成する速度を制限するというものであった。プログラム処理のわずかな部分のみ が、完全に並行して実行することができ、より多くのプロセッサーコアを備えたマシン上で直接拡大縮小することができる。残りのプログラム処理は、シーケン シャルである。アムダールの法則が強調している主な問題は、ロック競合であり、プロセッサーコア数が増加するにつれてこの問題は深刻になる。たいていの大 規模なCPU共有メモリハードウェアシステムは非常にに高速な並行読み取りをサポートするが、その速度は「書き込みにつき1回のキャッシュミス」または 「書き込みにつき1回のメモリーバスのアップデート」に制限されているので、同一のロケーションに書き込みをしているすべてのCPUを回避することが重要 である。リーダーライターロックでさえ、50から100CPU範囲以上を拡張縮小することは不可能である。マルチコア処理は、ますます業界のトレンドに なってきており、ほとんどすべてのハードウェア製造業者は、この将来性について見極めている。Azulは768コアのハードウェアを製造し、Sunの Rockはおよそ64コアそしてx86ベースのハードウェアでさえ、使用するコア数を拡大している。このように、パフォーマンスコードを書き込むことを検 討しているデベロッパにとって、ロック競合の問題は急務の問題になっている。

Azul Systemsの著名なエンジニアであるCliff Click氏が、今年のJavaOneで 講演をおこなった(スライドはこちら)(PDF・英語)。氏は、Javaでのスケーラブル、非ブロッキングコーディングスタイルに向けて大きく前進することを可能にした一 連の技法について説明した。広い意味では、氏のアプローチはある特定のスレッドをやめることは、全体的な進展を妨げないといった、非ブロッキングアルゴリ ズムを実装する。

Click氏による主なコンポーネントは、以下のとおりである。

1. 大規模で高速な配列で、データの迅速な並行読み取りを可能にし、並行、増分、同時コピーを可能にするすべてのデータを保持する。
2. これらの配列文字のアトミックアップデート(java.util.concurrent.Atomic.*を使用)。アトミックアップデートは、 Compare and Swap (CAS) (プロセッサーがAzul、Sparcまたはx86の場合) もしくはIBMプラットフォーム上ではLoad Linked/Store-conditional (LL/SC)を使用する。
3. アトミックアップデートでビルドされ、論理的に配列文字ごとに複製されたFinite State Machine (FSM)。FSMは配列のサイズ変更をサポートし、書き込みの制御に使用される。

このような基本的なエレメントが整っているので、Click氏はロックがない多くのFSMステップからアルゴリズムを構築する。すなわちそれぞれのCAS が進展する。CASの成功はローカルな成功である一方、CASの失敗は別のCASの成功を意味する。CASがうまくいけば状態マシンが前進するが、失敗し たCASは再試行する。

Click氏は、SourceForgeで 利用可能なコード(source)で2つの例(ビットベクトルおよびハッシュテーブル)を実装した。そして、3つ目(FIFOキュー)に取り組んでいる。一例を少し詳しく みると、ハッシュテーブルは偶数スロットにキーが、奇数スロットに値があるKey Valueのペアの配列である。それぞれの文字は別個に比較され交換されるが、状態マシンは両方の文字に及び、コピー時は両方の配列からの文字を含む。 ハッシュテーブルの実装は、並行挿入、テストの除去、サイズ変更およびConcurrentHashMap向けのJava Compatibility Kit (JCK)を渡す。Azulのハードウェアでは、768CPUまでリニアスケーリングを実現し、1秒につき10億以上の読み出しと同時に1秒につき1000万以上のアップデートが可能。

InfoQは、Click氏に自身の研究について詳細を尋ねた。JavaOneで の講演で、Javaにおけるハッシュテーブルの実装の記述に関わる問題のいくつかを強調した。そこで、この種の作業にJavaがどれほど適しているのかを 尋ねた。「実際、かなり適している。理解に優れたメモリーモデルがある(そして実装もうまくされている)。微調整の問題が不足している。多少パフォーマン スを犠牲するにつれ、無視することができる。この微調整の欠如(すなわち、direct ASM access)がたとえば、OS設計やデバイスドライバーなどの問題となる可能性があるが、パフォーマンスデータ構造の問題とはならない」。

また、データ構造の1つを使用するのは、いつが良いのかを尋ねた。氏のアドバイスは、「試行および真の」代替が遅すぎて有用でないときに使用すること、というものであった。

「1つのデータ構造が競合している場合、すでに java.util.concurrent.ConcurrentHashMapなどを試した。一般的にスタッフは、ロードがなければやや早い(であるから、それを使用する正当な理由がない)、そして非常によく作業する。
- 32以上のCPUの競合、または
- 書き込み対読み取りの高確率
当然ながら、メリットが変わる場合があるので、使用前にテストをする」。

現在、Javaでは並行性にまつわる活動が活発であり、Click氏はJava 7で検討されているフォーク/ジョインフレームワーク(参考記事・英語)と同様の問題に取り組んでいる。エキスパート集団の一員ではないが、定期的にClick氏は相談を受ける。

原文はこちらです：     http://www.infoq.com/news/2008/05/click_non_blocking