ストライピングロックを試す

マルチスレッドプログラミングでは、ロックの獲得が出来ずに待ち時間が発生し、パフォーマンス劣化の原因となることがしばしばある。そのような場合、まずは下記二点の検討を行う。

• ロックの粒度を下げる
• そもそもロックしないようなアルゴリズムに変える

もし上記二点をうまく実装できれば良いが、うまく行かない場合も多々ある。
この記事では、そのような場合の対策手法の1つ、ストライピングロックについて記す。

ストライピングロックとは

ストライピングロック、ロックストライピングなどと言う。ロックの獲得・解放による性能劣化を改善する手法。
ロック対象のオブジェクトを複数に分け、ロックの競合を減らす。このロックを複数に分け、それぞれがロック獲得・解放される様を縞々に見立て、ストライピングという名前がついた。

準備

今回は MyMap というインターフェースと、MyMap の2つの実装クラスによって実験を行う。
MyMap は簡易 Map で、2つの実装クラスというのはロック方法が通常のロックを用いるクラスと、ストライピングロックを用いるクラスを実装する。

ではその MyMap インターフェース。

public interface MyMap {
    // マップから値を取得する
    public Integer get(String key);

    // マップに値を挿入する
    public void put(String key, Integer value);
}

この記事ではこのインターフェースの実装クラスをテストする。

シンプルなロックを用いた実装でのテスト

MyMap の実装クラス SimpleLockMap のコード。自前で Map を実装するのはサンプルコードが複雑化するので、ここは楽して既存の HashMap を使っている。get, set 時共に内部の HashMap をロックしている。

public class SimpleLockMap implements MyMap {
    private Map<String, Integer> map = new HashMap<String, Integer>();

    public Integer get(String key) {
        // 内部マップをロック
        synchronized (map) {
            heavyProcess(); // 10ms スリープ
            return map.get(key);
        }
    }

    public void put(String key, Integer value) {
        // 内部マップをロック
        synchronized (map) {
            heavyProcess(); // 10ms スリープ
            map.put(key, value);
        }
    }
}

ただし HashMap に触る瞬間にだけロックするだけだとあまりにシンプルでロック獲得、解放が瞬間的すぎるので、意図的に重い処理を入れてある。heavyProcess メソッドだ。このメソッドの中身は下記の通り、10ms スリープするものだ。これを擬似的に同期化された領域内の重い処理として考える。

private void heavyProcess() {
    try {
        Thread.sleep(10);
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
}

では早速、複数スレッドからこいつを使ってみよう。テストコードは記事の最後に載せてあるが、特に面白みのあることはしていない。MyMap クラスの実装クラス、SimpleLockMap に対して 8 個のスレッドからそれぞれ 500 回、計 4000 回、ランダムな文字列の出し入れを行なっている。test メソッドから返される値は処理時間だ。

public static void main(String[] args) throws InterruptedException {
    long time = test(new SimpleLockMap());
    System.out.println("SimpleLockMap : " + time);
}

// 実行結果
SimpleLockMap : 81406

SimpleLockMap では、約81秒かかることがわかった。

ストライピングロックを用いた実装でのテスト

では次に、新たな MyMap の実装を行い、再度測定をする。今度は StripingLockMap というクラスで、その名の通りストライピングロックを行う。ポイントは、内部で保持する Map が複数あることだ。複数保持することでロックの競合を減らすことを目的とする。挿入、取得の操作時に getSegment というメソッドを使って、ハッシュ値を元に自分のセグメントの番号を取得する。あとは、その番号のマップのみをロックして挿入、取得を行えば良い。今回は、マップを内部的に4つにストライプしてある。

public class StripingLockMap implements MyMap {
    private static final int NUMSTRIPES = 4;

    // 内部には NUMSTRIPES 個のマップを保持
    private Map<String, Integer>[] maps = new Map[NUMSTRIPES];

    public StripingLockMap() {
        for (int i = 0; i < NUMSTRIPES; i++)
            maps[i] = new HashMap<String, Integer>();
    }

    // key を元にセグメントの位置を返す
    private int getSegment(String key) {
        if (key == null)
            return 0;

        int seg = key.hashCode() % NUMSTRIPES;
        return Math.abs(seg);
    }

    public Integer get(String key) {
        int seg = getSegment(key);

        // 複数のマップのうちの、自分のセグメントに関するものだけロック
        synchronized (maps[seg]) {
            heavyProcess(); // 10ms スリープ
            return maps[seg].get(key);
        }
    }

    public void put(String key, Integer value) {
        int seg = getSegment(key);

        // 複数のマップのうちの、自分のセグメントに関するものだけロック
        synchronized (maps[seg]) {
            heavyProcess(); // 10ms スリープ
            maps[seg].put(key, value);
        }
    }
}

行数的には SimpleLockMap の二倍程度までふくれあがっているが、コードをよく見れば複雑性はそれほど上がっていないことがわかるだろう。これだけのコードでロックの競合が抑えられるのだ。

さて、こいつも先ほどと同様にテスト。

public static void main(String[] args) throws InterruptedException {
    long time = test(new StripingLockMap());
    System.out.println("StripingLockMap : " + time);
}

// 実行結果
StripingLockMap : 24904

約25秒。単一ロックの SimpleLockMap が 81 秒だったので、実行時間は大体 30% 程度に抑えられたことになる。StripingLockMap は内部のロックのストライプ数が 4 つなので、ロックを最高の効率で行えたとすると実行時間は元の 25% 程度になる。理論値が 25% で、このテストでは 30% 程度なのでまぁまぁ良い結果だろう。

では次に、StripingLockMap の内部のストライプ数を 8 に増やしてみよう。

public class StripingLockMap implements MyMap {
    private static final int NUMSTRIPES = 8; // 4 から 8 に変更
    ...
}

再度テストすると、今度は 17 秒だった。

ストライプ数とテストにかかった時間を下記にまとめる。

ストライプ数	所要時間
1	81.5秒
2	43.6秒
4	25.8秒
8	17.6秒
16	13.5秒
32	11.7秒
64	10.9秒
128	10.6秒
256	10.4秒
512	10.3秒

この表から読み取れる事はいくつかある。
まず、64分割以降はほとんど効果が無いという点だ。つまりストライプ数は増やせば増やすほど良いというものではない。シチュエーションによって大きく異なるが、適切な値の検討がつかない場合は稼働させるマシンのコア数と同等にしておけばよいだろう。コア数を超えて増やすと、ある程度は性能の改善が見られるがその分メモリ消費量が増える等のマイナス面もあることに注意。

次に、単一ロックの場合に比べておよそ8倍程度高速に処理を終えている。アルゴリズムの切り替えのようなチューニングでは8倍はたいしたことの無い数値だが、ロックに関するチューニングは内部がそのままクリティカルセクションであり、なかなか高速化できないところだという点を考慮すると8倍でもありがたい数字だ。

最後に、ストライプ数を 1、つまり分割無しの状態だと SimpleLockMap とほぼ同等の時間であることがわかる。わずかにオーバーヘッドはあるだろうが、ロック解放待ちの時間に比べたら微々たるものだ。

まとめ

チューニング時にロック関連で困ったら分割ロックやストライピングロックを考慮すべし。
(注意点:分割ロックとストライピングロックは異なるものである。)

ストライプ数を無闇やたらに増やさないこと。

ストライピングロックが使えそうにないなら Lock-freeとWait-freeアルゴリズム が使えないか検討すること。

補足1

今回は 1CPU, 4物理コア(8仮想コア)のマシンで動かした。
コア数が異なると今回の結果とは異なる結果が出る点に注意。

補足2

テストに使ったコード

public class MyMapTest {
    // MyMap の負荷テストを行うメソッド
    private static long test(MyMap mymap) throws InterruptedException {
        List<Thread> threads = new ArrayList<Thread>();
        long s = System.currentTimeMillis();

        // 8 個の runner を走らせる
        for (int i = 0; i < 8; i++) {
            Thread t = new Thread(new Runner(mymap));
            t.start();
            threads.add(t);
        }

        // 終了まで待つ
        for (Thread thread : threads)
            thread.join();

        long e = System.currentTimeMillis();

        // 最後に処理時間を返す 
        return e-s;
    }

    public static void main(String[] args) throws InterruptedException {
        // SimpleLockMapを実行
        test(new SimpleLockMap());
    }
}

// MyMap の負荷テストを行う際に使うクラス
class Runner implements Runnable {
    private MyMap mymap;

    public Runner(MyMap mymap) {
        this.mymap = mymap;
    }

    @Override
    public void run() {
        // ランダムな文字列を500回出し入れする
        for (int i = 0; i < 500; i++) {
            String key = RandomStringUtils.random(20);
            mymap.put(key, i);
            mymap.get(key);
        }
    }
}