システム負荷を軽減したスレッド化: 競合を低減させる

コンテンツ: 競合は、なぜそんなに問題になるのか? 技法1: 素早くでる 技法2: ロックの粒度を低減する 技法2をHashMapに適用する 技法3: ロックの折りたたみ 参考文献 著者について この記事の評価 関連dWコンテンツ: マルチスレッド化Javaアプリケーションの作成 IBM WebSphere Advanced Editionの楽観的なロッキング・パターン その他のdW Java参考文献

発想を切替えてアプリケーションのパフォーマンスを改善する

Brian Goetz (brian@quiotix.com)
Quiotix社　ソフトウェア・コンサルタント　
2001年9月　

本連載の第1回 で、私たちは、競合しない同期化のパフォーマンス・オーバーヘッドについて検討しました。 同期化メソッド呼び出しが、非同期化メソッド呼び出しより50倍も費用が高く付くとよく言われますが、この数字は実際、誤解を招きかねません。 JVMは、新バージョンが出るたびに全体のパフォーマンスが改善され、競合しない同期化のコストは低減してきました。これによって、競合しない同期化のオーバーヘッドに関する争点は、あまり問題にされなくなってきました。 しかし、競合する同期化は費用がかなり高く付きます。 さらに、過度の競合は、スケーラビリティーに大きな悪影響を及ぼします。 -- 競合する同期化の度合いが高いアプリケーションでは、負荷が増大するにつれて著しいパフォーマンスの低下を示します。本記事では、競合を減らして皆さんのプログラムにおけるスケーラビリティーを改善するための、各種の技法を紹介しています。

プログラムが「遅すぎる」という場合、これは通常、2つのパフォーマンス属性のどちらかを指します。すなわち、待ち時間とスケーラビリティーです。待ち時間 は、与えられたタスクを完了するためにどのくらいの時間を要するかということであり、一方、スケーラビリティー は、負荷の増大、または 与えられたコンピューティング・リソース の増加に伴ってどのくらいプログラムのパフォーマンスが変化するかを示します。 過度の競合は、待ち時間とスケーラビリティーの両方に悪影響を及ぼします。　

競合は、なぜそんなに問題になるのか?

競合する同期化には、複数のスレッドの切り替えとシステム呼び出しが含まれるため、どうしても時間がかかります。 複数のスレッドが同一モニターに対して競合すると、JVMはそのモニターを待つスレッドのキューを維持しなければなりません (このキューはすべてのプロセッサーに同期化している必要があります)。これは、JVMやOSのコードに費やされる時間が多くなり、ユーザーのプログラム・コードに費やされる時間が少なくなることを意味します。 さらに、競合は、スケジューラーに操作の直列化を強いるので、スケーラビリティーを悪化させます。 これは、空いているプロセッサーがあっても変わりません。 1つのスレッドが同期化ブロックを実行しているときには、そのブロックへの進入を待っているスレッドはすべて停止します。 他に実行可能なスレッドがなければ、プロセッサーはアイドリング状態になります。

スケーラブルなマルチスレッド・プログラムを書こうとするなら、まずクリティカル・リソースに対する競合を減らさなければなりません。 そのための技法は数多くあります。しかし、そのいずれかを適用する前に、ユーザーは、自分のコードをよく観察して、どんな条件のもとで共通のモニターを同期化しようとしているのか、十分に理解する必要があります。どのロックが隘路 (あいろ)になっているかを判別するのは、かなり困難な作業です。時としてロックはクラス・ライブラリーの中に隠れていたり 同期化メソッドを通して暗黙的に指定されていたりします。したがって、コードを点検しただけで隘路を確実に見つけることは難しいのです。　また、競合を検出するツール類の現状は、お寒いというほかありません。　

技法1: 素早く出る

競合の可能性を低減できる明白な技法の1つは、同期化ブロックを、できるだけ短くすることです。 スレッドが、与えられたロックを保持する時間が短ければ短いほど、そのスレッドのロックを、他のスレッドが要求する可能性は少なくなります。したがって、共用変数をアクセスしたり更新したりするために、同期化を使用しなければならない時は、通常、同期化ブロックの外側でスレッド・セーフな前処理や後処理を行うのが賢明なやり方です。

リスト1には、 この技法が示されています。 このアプリケーションは、各種エンティティーの属性を表すために HashMap を維持しています。 そのような属性の1つとして許可されたユーザーが持つアクセス権のリストがあります。アクセス権は、コンマで分けられた権限リストとして保管されます。 メソッド userHasAdminAccess() は、グローバル属性テーブル内にあるユーザーのアクセス権をルックアップし、そのユーザーが「ADMIN」というアクセスを持っているかどうかを調べます。

  public boolean userHasAdminAccess(String userName) {
    synchronized (attributesMap) {
      String rights = attributesMap.get("users." + userName + ".accessRights");
      if (rights == null) 
        return false;
      else
        return (rights.indexOf("ADMIN") >= 0);
    }
  }

userHasAdminAccess の、このバージョンは、スレッド・セーフですが、ロックを必要以上に長く保持しています。 連結文字列 「users.brian.accessRights」 を作るために、このコンパイラーは、臨時のStringBufferオブジェクトを生成し、StringBuffer.append を3回呼び出し、次いで StringBuffer.toStringを呼び出します。これは、少なくとも2つのオブジェクト生成と幾つかのメソッド呼び出しを意味します。 さらに、コンパイラーは、この文字列を取り出すためにHashMap.get を呼び出し、次いで、必要な権限識別子を抽出するためにString.indexOf を呼び出します。 この方法では全作業に占める割合としては、前処理および後処理が、かなり大きくなっています。これらのプロセスがスレッド・セーフであるため、リスト2 に示すように、同期化ブロックから取り外したほうが合理的です。　

  public boolean userHasAdminAccess(String userName) {
    String key = "users." + userName + ".accessRights";
    String rights;

    synchronized (attributesMap) {
      rights = attributesMap.get(key);
    }
    return ((rights != null) 
            && (rights.indexOf("ADMIN") >= 0));
  }

一方、この技法は使い過ぎてしまうおそれもあります。 同期化を必要とする2つの操作があって、それがスレッド・セーフなコードの小さなブロックによって分離されている場合は、通常単一の 同期化ブロックを使用するほうが有利です。

技法2: ロックの粒度を小さくする

競合を減らすもう1つの有益な技法は、もっと多くのロックに同期化を分散させることです。 たとえば、リスト3に示すように、ユーザー情報とサービス情報を保管する1つのクラスが2つの別個のテーブルに入っていたとします。

public class AttributesStore {
  private HashMap usersMap = new HashMap();
  private HashMap servicesMap = new HashMap();

  public synchronized void setUserInfo(String user, UserInfo userInfo) {
    usersMap.put(user, userInfo);
  }

  public synchronized UserInfo getUserInfo(String user) {
    return usersMap.get(user);
  }

  public synchronized void setServiceInfo(String service, 
                                          ServiceInfo serviceInfo) {
    servicesMap.put(service, serviceInfo);
  }

  public synchronized ServiceInfo getServiceInfo(String service) {
    return servicesMap.get(service);
  }
}

ここで、ユーザーおよびサービス・データのアクセサー・メソッドは同期化されます。これは、両方が AttributesStore オブジェクト上で同期化していることを意味します。これは、完全にスレッド・セーフではありますが、競合の恐れが増え、現実的な利益は得られません。1つのスレッドが setUserInfo を実行しているということは、他のスレッドが意図どおりすべて setUserInfo と getUserInfo からロックアウトされるだけでなく、他のスレッドが getServiceInfo と setServiceInfo からもロックアウトされることを意味します。

この問題は、リスト4に示すように、共有が実際に行われているオブジェクト (userMap および servicesMap オブジェクト) 上でアクセサーを単に同期化させることによって回避できます。

public class AttributesStore {
  private HashMap usersMap = new HashMap();
  private HashMap servicesMap = new HashMap();

  public void setUserInfo(String user, UserInfo userInfo) {
    synchronized(usersMap) {
      usersMap.put(user, userInfo);
    }
  }

  public UserInfo getUserInfo(String user) {
    synchronized(usersMap) {
      return usersMap.get(user);
    }
  }

  public void setServiceInfo(String service, 
                             ServiceInfo serviceInfo) {
    synchronized(servicesMap) {
      servicesMap.put(service, serviceInfo);
    }
  }

  public ServiceInfo getServiceInfo(String service) {
    synchronized(servicesMap) {
      return servicesMap.get(service);
    }
  }
}

これで、サービス・マップにアクセスするスレッドは、ユーザー・マップにアクセスしようとするスレッドと競合しなくなります。(この場合、Collectionsフレームワークの 同期化マップ・ラッパー・メカニズムを使用するマップを作成することにより、同様の効果を得ることができます。このメカニズムは、Collections.synchronizedMap により提供されます。) この場合、2つのマップに対する要求が、等しく分散されると仮定すると、本技法によって、潜在的な競合の数は半分に減ります。

技法2をHashMapに適用する

サーバー側Javaアプリケーションにおいて最も一般的な競合の隘路は、HashMapです。アプリケーションは、あらゆる種類のクリティカルな共有データ(ユーザー・プロファイル、セッション情報、ファイルの内容など) をキャッシュするために HashMap を使用し、HashMap.get メソッドは、多くのバイトコード命令に相当しているかもしれません。たとえば、皆さんがWebサーバーを記述していて、キャッシュしたすべてのページを HashMap に保存すると、どの要求もマップ上のロックを取得し保持しようとするので、ここに隘路が生じます。

この状況に対処するため、私たちはロックの粒度技法を使用します。しかし、Javaメモリー・モデル (JMM) には、このアプローチに関連する潜在的な危険性があるので注意を要します。リスト5の LockPoolMap は、スレッド・セーフな get() および put() メソッドを開示していますが、ロックのプールに同期化を分散させているので、競合は大きく低減されます。

LockPoolMap は、スレッド・セーフで、簡略化された HashMapのように機能しますが、より魅力的な競合プロパティーを持っています。それぞれのget() または put() 操作でマップ全体を同期化する代わりに、バケット・レベルで同期化が行われます。各バケットにロックがあり、しかもロックは、読み書きのいずれかのためにバケットを横断する際、取得されます。ロックは、マップが作成される際、作成されます (そうでなければ、 JMMに問題があるはずです)。

多くのバケットを持つ LockPoolMap を作成すれば、多数のスレッドが同時にマップを使用でき、競合する可能性は激減します。しかしながら、競合は見返りなしに減少するわけではありません。グローバル・ロック上で同期化しなければ、size()メソッドのような、全体としてマップに作用する操作を行うのはずっと難しくなります。size()の実装は、各バケットのロックを順次取得し、そのバケットのノード数を数え、ロックを解放し、次のバケットへ移動するはずです。しかし、いったん前のロックがリリースされると、他のスレッドは、前のバケットを自由に変更できるようになります。size() が、要素の数の計算を完了する時点で、まったくこれが誤りであるかもしれません。しかし、LockPoolMap の技法は、共有キャッシュのような特定の状況では、うまく機能します。

import java.util.*;

/**
 * LockPoolMap implements a subset of the Map interface (get, put, clear)
 * and performs synchronization at the bucket level, not at the map
 * level.  This reduces contention, at the cost of losing some Map
 * functionality, and is well suited to simple caches.  The number of
 * buckets is fixed and does not increase.
 */

public class LockPoolMap {
  private Node[] buckets;
  private Object[] locks;

  private static final class Node {
    public final Object key;
    public Object value;
    public Node next;

    public Node(Object key) { this.key = key; }
  }

  public LockPoolMap(int size) {
    buckets = new Node[size];
    locks = new Object[size];
    for (int i = 0; i < size; i++)
      locks[i] = new Object();
  }

  private final int hash(Object key) {
    int hash = key.hashCode() % buckets.length;
    if (hash < 0)
      hash *= -1;
    return hash;
  }

  public void put(Object key, Object value) {
    int hash = hash(key);

    synchronized(locks[hash]) {
      Node m;
      for (m=buckets[hash]; m != null; m=m.next) {
        if (m.key.equals(key)) {
          m.value = value;
          return;
        }
      }

      // We must not have found it, so put it at the beginning of the chain
      m = new Node(key);
      m.value = value;
      m.next = buckets[hash];
      buckets[hash] = m;
    }
  }

  public Object get(Object key) {
    int hash = hash(key);

    synchronized(locks[hash]) {
      for (Node m=buckets[hash]; m != null; m=m.next) 
        if (m.key.equals(key))
          return m.value;
    }
    return null;
  }
}

表1では、synchronized HashMap、unsynchronized HashMap(スレッド・セーフではない) および LockPoolMap の3つの共有マップの実装を比較しています。非同期化バージョンは、競合のオーバーヘッドを示すためにのみ採りあげられています。　ランダムの put()および get() 操作をマップ上で行うテストを実行しました。これは、Sun 1.3 JDKを使用するデュアル・プロセッサーのLinuxシステム上で、可変数のスレッドを使って行われました。表では、各組み合わせごとに実行時間が示されています。このテストは、いくらか極端な事例であり、テスト・プログラムはマップにアクセスする以外何もしません。このため現実のプログラムで起こるよりも多くの競合が起こるでしょうが、このテストは、競合によるパフォーマンス上の不利益を示すために設計されているものです。

すべての実装では、多数のスレッドに対して類似のスケーリング特性を示していますが、一方、HashMap 実装では、1つのスレッドを2つにすると、パフォーマンス上の不利益が非常に大きくなることを示しています。これは、1回の各 put() および get() 操作ごとに1回の競合が起こるためです。2つ以上のスレッドでは、LockPoolMap 技法を用いると、HashMap 技法に比べ約15倍の速さになります。この違いは、スケジューリング・オーバーヘッドとロックを取得するために待機したアイドル時間のために喪失した時間を反映しています。もっと多くのプロセッサーを備えたシステムでは、LockPoolMap の利点がさらに大きくなるでしょう。

技法3: ロックの折りたたみ

パフォーマンスを改善するもう1つの技法は、「ロックの折りたたみ」と呼ばれます(リスト6参照)。 Vector クラスのほとんどすべてが同期化していることを思い出してください。String 値の Vector を1つ持ち、最長の String を探す場合を想定します。さらに、要素は、末尾だけに追加され、要素は削除されないことがわかっており、getLongest() メソッドに示されるように、データへ (おおむね) 安全にアクセスできるものとします。このメソッドは、単に Vectorの要素間をループし、各要素をリトリーブするためには elementAt() を呼び出します。

getLongest2() メソッドもこれと良く似ていますが、ループを開始する前に Vector に対してロックを取得する点だけ違います。この結果、elementAt() がロックを取得しようと試みたとき、JVMは、現在のスレッドが既にロックを取得しており、競合しないであろうということを認識します。 この技法は、同期化ブロックを長くします。このことは、「素早く出る」原則と反対のように見えますが、多くの潜在的な同期化を避けるので十分速くなり、スケジューリング・オーバーヘッドのための損失時間は少なくなります。

Sun 1.3 JDKを実行するデュアル・プロセッサーのLinuxシステム上で、getLongest2() の呼び出しを単にループさせるだけの2つのスレッドを持つテスト・プログラムは、getLongest() を呼び出すテスト・プログラムと比べると10倍を超える速さになりました。プログラムは、両方とも同程度に直列化していますが、スケジューリング・オーバーヘッドに失われる時間は非常に少なくなりました。これも極端な例ですが、競合のスケジューリング・オーバーヘッドは、少なくありません。1つのスレッドで実行する場合でさえ、折りたたみバージョンは、30%速くなります。自分が既に保持しているロックを取得するほうが、だれにも保持されていないロックを取得するよりかなり速くなります。

  Vector v;
  ...
 
 public String getLongest() {
    int maxLen = 0;
    String longest = null;

    for (int i=0; i<v.size(); i++) {
      String s = (String) v.elementAt(i);
      if (s.length() > maxLen) {
        maxLen = s.length();
        longest = s;
      }
    }
    return longest;
  }

  public String getLongest2() {
    int maxLen = 0;
    String longest = null;

    synchronized (v) { 
      for (int i=0; i<v.size(); i++) {
        String s = (String) v.elementAt(i);
        if (s.length() > maxLen) {
          maxLen = s.length();
          longest = s;
        }  
      }  
      return longest;
    }
  }

結論

同期化が競合状態になると、プログラムのスケーラビリティーに深刻な影響を与えることがあります。悪いことに、開発やテストの過程で現実に即した負荷テストをしておかないと、競合に関するパフォーマンスの問題が発見できないことがあります。 この記事で解説した技法は、プログラムにおける競合コストを削減し、かつ非線形スケーリングの振る舞いの兆候が現れる前に、プログラムがさらに大きな負荷に耐えうるようにしてくれる効果があります。しかし、この技法を適用する前に、まずプログラムを分析して、競合が発生する可能性のある場所を判別する必要があります。

このシリーズの最後の記事では、Thread APIの機能で省みられることの少ない ThreadLocal を検証する予定です。ThreadLocal を用いれば、各スレッドに特定のクリティカル・オブジェクトのそのスレッド自身のためのコピーをし、競合を減らすことができます。続報をお読みください。

参考文献

• システムの負荷を軽減したスレッド化の第1回で、競合しない同期化は、広く信じられているほどパフォーマンスへの影響がないことを解説しています。
• 「Java Performance Tuning」(Jack Shirazi著、O'Reilly &Associates社、2000年) には、Javaプラットフォームにおけるパフォーマンス上の問題を解決するための方法が示されています。
• 「Java Platform Performance: Strategies and Tactics」(Steve Wilson、Jeff Kesselman著、Addison-Wesley社、2000年) には、迅速かつ効果的なJavaコードを構築するために必要となる、熟達したJavaプログラマーのための技法が示されています。
• 「Java Performance and Scalability, Volume 1: Server-Side Programming Techniques」(Dov Bulka著、Addison-Wesley社、2000年) には、アプリケーションのパフォーマンスを向上させるヒントが数多く示されています。
• Brian Goetzの最近の記事、"Double-checked locking: Clever, but broken" (JavaWorld、2001年2月) は、JMMの詳細の検討、および特定の状況下での同期化の失敗による驚くべき結果を示しています。
• 「Concurrent Programming in Java、Second Edition」(Doug Lea著、Addison-Wesley社、1999年) は、Javaにおけるマルチスレッド・プログラミングに伴う難解な問題に関する優れた著作です。
• Alex Roetter氏は、同氏の記事マルチスレッド化 Javaアプリケーションの作成 (developerWorks、2001年2月)で、Java Thread API紹介し、マルチスレッド化に伴う問題を概説し、一般的な問題解決策を提示しています。
• IBMから寄せられたこの記事では、Optimistic locking in WebSphere (WebShpereの楽観的なロッキング) によって、異なるトランザクションが同時に同じ状態を読みこみ、更新時にのみデータ保全性を確認する方法について説明しています。
• IBM Thomas J. Watson Research Centerの performance modeling and analysis チームは、パフォーマンスおよびパフォーマンス管理の分野で幾つかのプロジェクトを研究しています。
• その他のJava参考文献に関してはdeveloperWorks Javaテクノロジー・ゾーン を参照してください。

著者について

Brian Goetz氏は、過去15年間ソフトウェア開発者としての経験を持つソフトウェア・コンサルタントです。彼は、カリフォルニア州ロスアルトスにあるソフトウェア開発コンサルティング会社 Quiotix のPrincipal Consultantです。業界で出版された、評判のよい著作および記事 のリストを参照してください。連絡先は brian@quiotix.com です。