Azul Systemsの著名なエンジニアであるCliff Click氏が、今年のJavaOneで 講演をおこなった(スライドはこちら)(PDF・英語)。氏は、Javaでのスケーラブル、非ブロッキングコーディングスタイルに向けて大きく前進することを可能にした一 連の技法について説明した。広い意味では、氏のアプローチはある特定のスレッドをやめることは、全体的な進展を妨げないといった、非ブロッキングアルゴリ ズムを実装する。
Click氏による主なコンポーネントは、以下のとおりである。
- 大規模で高速な配列で、データの迅速な並行読み取りを可能にし、並行、増分、同時コピーを可能にするすべてのデータを保持する。
- これらの配列文字のアトミックアップデート(java.util.concurrent.Atomic.*を使用)。アトミックアップデートは、 Compare and Swap (CAS) (プロセッサーがAzul、Sparcまたはx86の場合) もしくはIBMプラットフォーム上ではLoad Linked/Store-conditional (LL/SC)を使用する。
- アトミックアップデートでビルドされ、論理的に配列文字ごとに複製された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氏は相談を受ける。
原文はこちらです：