Java の ConcurrentHashMap における同期化バッドケースとその対処法 2013 年 9 月湊隆行 1. はじめに表 1.1 に示すように Java の Collections Framework には 3 つの世代がありますバージョン 1.0 から存在するレガシー API バ

Size: px

Start display at page:

Download "Java の ConcurrentHashMap における同期化バッドケースとその対処法 2013 年 9 月湊隆行 1. はじめに表 1.1 に示すように Java の Collections Framework には 3 つの世代がありますバージョン 1.0 から存在するレガシー API バ"

れいなたけくま
5 years ago
Views:

1 Java の ConcurrentHashMap における同期化バッドケースとその対処法 2013 年 9 月湊隆行 1. はじめに表 1.1 に示すように Java の Collections Framework には 3 つの世代がありますバージョン 1.0 から存在するレガシー API バージョン 1.2 で追加されたロック機構を使わない API およびバージョン 5.0 で追加された同期化コストが低い API があります世代 API の例特徴 Java SE 1.0 から存在するもの Hashtable Vector 多くのメソッドに synchronized 修飾子がありスレッドセーフである反面同期化コストが高く速度性能が悪い Java SE 1.2 で追加されたもの HashMap ArrayList ロック機構を使わないため速度性能が良い反面スレッドセーフではないためプログラマーは多くの同期化処理を Java SE 5.0 で追加されたもの ConcurrentHashMap CopyOnWriteArrayList 表 1.1 Java Collections Framework の世代と特徴実装しなければならない同期化コストを下げて速度性能を向上させたスレッドセーフなクラスでありプログラマーは実装しなければならない同期化処理を軽減しているただしクラスがスレッドセーフであるかどうかに関わらずプログラマーは同期処理の実装から完全に解放されるわけではありませんなぜなら複数のスレッドから同時にアプリケーションの共通データを更新する場合共通データのクラスの更新メソッドがスレッドセーフであってもデータに矛盾が発生する可能性を排除できないからです特にオブジェクトの状態を更新する処理が 1 つでもあればそのオブジェクトに対する一連の呼び出しを 1 つのトランザクションとして同期化し他のスレッドから割り込まれないようにする必要がありますまたアプリケーションが 2 つ以上のオブジェクトを共通データとして持っていてこれらのオブジェクトが相互依存する関係にある場合複数のオブジェクトに対する一連の呼び出しも 1 つのトランザクションとして同期化しなければなりません本書では並列プログラミング初心者を対象とし ConcurrentHashMap を使用するプログラムについて初心者がおかしやすい 2 つのバッドケースを紹介しどのような対処が必要かを紹介します 2. バッドケース 1 図 2.1 のプログラムを見てくださいインスタンス変数 countermap は ConcurrentHashMap オブジェクトであり文字列 (String オブジェクト ) と整数値 (Integer オブジェクト ) を対とした key-value データを保持します incrementcounter() が呼び出されるたびに引数 key に対応する整数値をインクリメントするつもりのプログラムです class Sample1 { ConcurrentMap<String, Integer> countermap = new ConcurrentHashMap<>(); // インスタンス変数 1

2 void incrementcounter(string key) { int counter = countermap.get(key); countermap.put(key, ++counter); 図 2.1 同期化を行わないプログラム 1 countermap にはすでに "key1" と整数値 1 の key-value が格納してあるとしますそのとき図 2.2 のように 2 つのスレッドが異なるタイミングで incrementcounter("key1") を 1 回ずつ呼び出した場合最終的に countermap に整数値 3 を格納しますこれは期待通りの動作ですしかし図 2.3 のように 2 つのスレッドがほぼ同時に incrementcounter() を呼び出した場合最終的に格納する整数値は 3 ではなく 2 となるおそれがありますなぜならば複数のスレッドが同時に動作しているときどのスレッドがどのメソッドを先に呼び出すかは不定だからです図 2.2 では 1.1: get("key1") は整数値 1 2.1: get("key1") は整数値 2 を返しますしかし図 2.2 と違って図 2-3 ではスレッド 1 が 1.2: put("key1", 2) を呼び出す前にスレッド 2 が 2.1: get("key1") を呼び出している点が根本的な問題です結果スレッド 1 とスレッド 2 はともに整数値 2 を格納してしまうわけですこれは read-modify-write のシーケンスであり読み込んだ現在の値を更新し更新した値を書き出すという一連の処理を指します countermap.get() が read( 読み込み ) ++counter が modify( 更新 ) で countermap.put() が write( 書き出し ) に該当します ConcurrentHashMap のようなスレッドセーフなクラスを使う場合でもこの read-modify-write の処理全体を 1 つのトランザクションとして同期化する必要があります図 2.2 複数スレッドが異なるタイミングで incrementcounter() を呼び出す図 2

3 図 2.3 複数スレッドが同時に incrementcounter() を呼び出す図 3. バッドケース 1 の対処法バッドケース 1 の対処案を図 3.1 に示します countermap オブジェクトに対する処理全体を 1 つのトランザクションで行うように synchronized 節で囲んでいますこの対処により incrementcounter() を呼び出すたびに正しくインクリメントした値を格納するようになります class Sample1 { ConcurrentMap<String, Integer> countermap = new ConcurrentHashMap<>(); // インスタンス変数 void incrementcounter(string key) { synchronized(countermap) { int counter = countermap.get(key); countermap.put(key, ++counter); 図 3.1 バッドケース 1 の対処案 ( その 1) しかし synchronized や ReentrantLock などを使ったロック機構はコストが高く並行率が大きく低下します並行率とはプログラムの総実行時間のうち複数のスレッドが同時に動作した時間の割合のことです言い換えるとスレッドがブロック状態または待機状態になった時間が長ければ長いほど並行率が低下しますそこで別の対処案を図 3.2 に示します class Sample1 { ConcurrentMap<String, AtomicInteger> countermap = new ConcurrentHashMap<>(); // インスタンス変数 void incrementcounter(string key) { countermap.get(key).incrementandget(); 図 3.2 バッドケース 1 の対処案 ( その 2) 3

4 この対処案は図 2.1 のバッドケースのプログラムに対して次の 3 点を修正したものです 1) countermap の値を java.lang.integer クラスから java.util.concurrent.atomic.atomicinteger クラスに変更 2) AtomicInteger クラスの incrementandget() を使って整数値をインクリメント 3) countermap の put() 呼び出しを削除 1) の ConcurrentHashMap の値を Integer から AtomicInteger に変更したことが大きなポイントです AtomicInteger は CPU のアトミック命令を使って値を取得 / 更新するクラスですアトミック命令を使えばロック機構を使わなくてもスレッドセーフに整数値の取得と更新ができますこれにより図 3-1 の対処案より並行率が向上しますまた Integer オブジェクトは immutable( 不変 ) なため整数値を更新するたびに新しい Integer オブジェクトを生成し put() で格納し直す必要がありました対して AtomicInteger オブジェクトは immutable ではないため put() を実行する必要がなくなりました 4. バッドケース 2 2 つ目のバッドケースを紹介します図 4.1 のプログラムを見てくださいインスタンス変数 personmap は ConcurrentHashMap オブジェクトであり氏名と個人情報 (Person クラス ) の対を格納します updateaddress() では引数 updatetime が Person オブジェクトの lastupdatetime より大きな値である場合に限り郵便番号と住所を更新していますまた personmap.get(name) は null を返さないものと仮定し null チェックは省略していますなお getaddress() は引数 zipcode( 郵便番号 ) に対応する住所を他の Web サービスやローカルファイル等にアクセスして取得するメソッドです class Sample2 { ConcurrentMap<String, Person> personmap = new ConcurrentHashMap<>(); // インスタンス変数 void updateaddress(long updatetime, String name, String zipcode) { Person p = personmap.get(name); if(updatetime > p.lastupdatetime) { p.lastupdatetime = updatetime; p.zipcode = zipcode; p.address = getaddress(zipcode); // 郵便番号に対応する住所を取得 String getaddress(string zipcode) { : return address; class Person { long lastupdatetime; // 最終更新日時 String name; // 氏名 String zipcode; // 郵便番号 String address; // 住所図 4.1 同期化を行わないプログラム 2 4

5 このプログラムもバッドケース 1 と同様複数のスレッドから updateaddress() を呼び出した場合に問題が起きるおそれがありますあるスレッドが Person オブジェクトの lastupdatetime zipcode と address の各フィールドを更新している間に別のスレッドが同時にこれらのフィールドを更新すると各フィールドの値が矛盾します図 4.2 はスレッド 1 とスレッド 2 がほぼ同時に updateaddress() を呼び出したときの処理の流れです 1.x がスレッド 1 による呼び出しで 2.x がスレッド 2 による呼び出しです 1.1 と 1.2 の get(" 富士通太郎 ") が同じ Person オブジェクトを返すため 1.2~1.4 および 2.2~2.4 は同じ Person オブジェクトに対するアクセスになります郵便番号の本来の住所は神奈川県横浜市港北区新横浜ですしかし図 4.2 では 1.4 と 2.4 の呼び出し順序が逆になったために Person オブジェクトの address に神奈川県川崎市中原区上小田中を代入してしまっていますこのプログラムでは check-then-act と呼ばれるシーケンスつまり値をチェックしその結果に基づいて何らかの処理を行うという一連の処理を行っていますしかし Person オブジェクトの lastupdatetime フィールドのチェック (check) と各フィールドに対する更新 (act) を同期化していないために郵便番号と住所に矛盾が起きたわけです処理対象のオブジェクトがスレッドセーフであるかどうかに関係なく check-then-act の処理全体を 1 つのトランザクションとして同期化する必要があります図 4.2 複数スレッドが同時に Person のフィールドを更新する図 5

6 5. バッドケース 2 の対処法バッドケース 2 の updateaddress() の対処案を図 5.1 に示します void updateaddress(long updatetime, String name, String zipcode){ Person p = personmap.get(name); if(updatetime <= p.updatetime){ return; String address = getaddress(zipcode); synchronized(p) { if(updatetime > p.updatetime){ p.updatetime = updatetime; p.zipcode = zipcode; p.address = address; 図 5.1 バッドケース 2 の対処案この対処案のポイントは 2 つです 1 つめは if 節全体を synchronized 節で囲み Person オブジェクトに対する操作を同期化したことですこの対処により check-then-act 全体の処理を 1 つのトランザクションで行うようになります 2 つめは getaddress() の処理コストが高いことを想定して getaddress() の呼び出しを synchronized 節の外側で行うようにした点ですなぜなら synchronized 節の内側でコストが高い処理を行うと他のスレッドを長時間待たせることになり並行率が大幅に悪化するためです 6. まとめ本書ではスレッド間で共有しているオブジェクトの中身を更新する場合そのオブジェクトがスレッドセーフであってもなくても同期化しなければならないことを ConcurrentHashMap を題材にして紹介しましたその対処法として java.util.concurrent.atomic パッケージを使った低コストな同期化と synchronized を使った同期化を紹介しましたまた同期化する範囲を可能な限り狭めて並行率を高めることも紹介しました参考文献 Java 並行処理プログラミングその基盤と最新 API を究める Brian Goetz( 著 ) Joshua Bloch( 著 ) Doug Lea( 著 ) 岩谷宏 ( 訳 ) ソフトバンククリエイティブ ( 出版社 ) 商標について Java は Oracle Corporation およびその子会社関連会社の米国およびその他の国における登録商標ですその他の会社名および製品名はそれぞれの会社の登録商標もしくは商標です - 以上 - 6

HashMapからConcurrentHashMapへの移行

HashMapからConcurrentHashMapへの移行 HashMap から ConcurrentHashMap への移行レガシーアプリケーションにおける注意点 2012 年 1 月 4 日橋口雅史 1. はじめにアプリケーションではキーと値のマッピングが多用されます例えばユーザー名というキーにユーザーの情報をマッピングするといった用途で java.util.map インタフェースは広く使われています特にハッシュテーブルに基づいて高速にマップを検索

Java の ConcurrentHashMap における同期化 バッドケースとその対処法 2013 年 9 月湊隆行 1. はじめに表 1.1 に示すように Java の Collections Framework には 3 つの世代があります バージョン 1.0 から存在するレガシー API バ

Java の ConcurrentHashMap における同期化バッドケースとその対処法 2013 年 9 月湊隆行 1. はじめに表 1.1 に示すように Java の Collections Framework には 3 つの世代がありますバージョン 1.0 から存在するレガシー API バ