Lock Striping についてとその実装

Java Concurrency in Practice の 5.2.1. ConcurrentHashMap にて Lock Striping というロックの方法が出てくる。 Lock Striping の説明と実装、および簡単にパフォーマンスを測ったのでそのメモ。

Java Concurrency in Practice

Lock Striping とは

Lock Striping とは Array や HashMap などのオブジェクトに対して、複数スレッドから書き/読み込む場合に、そのオブジェクト全体のロックを取るのではなく部分的にロックを取ること。 例えば、Array オブジェクトの 0 から 9 は Mutex1、10 から 19 は Mutex2 が管理するようにすること。 このようにすることで、依存関係のない操作を複数スレッドで実行する際 (上の例なら Arrayオブジェクトの index 1 と 11 への書き込みなど) に互いの操作を待たなくて良くなり並列度が上がり、パフォーマンスの向上が見込める。

1 つの Mutex オブジェクトでロックする際の問題

Array や Map などのオブジェクトに対して、複数スレッドから書き込み/読み込みがある時にロックが必要になる。 同じキーに対して複数のスレッドから書き込んでしまった場合にレースコンディションが発生するからである。 1 つのオブジェクトに対して 1 つの Mutex オブジェクトを使用すると、ロックの粒度が適切でない時がある。 たとえば、以下のように Map オブジェクト dict に Thread 1 (go の場合は goroutine) では "foo" というキーに 値 1 をセットし、Thread 2 では "bar" というキーに 2 をセットするとする。 この時 Thread 1 と Thread 2 の操作は互いに独立しており、並列に実行してもレースコンディションが発生しないためそれぞれの Thread を並列に実行できた方がパフォーマンスがよくなる。 しかし、dict に対して 1 つの Mutex オブジェクトを使用すると、互いに独立している操作であっても dict への操作は並列に実行することができなくなる。

dict := new(map[string]map)

// In Thread 1
dict["foo"] = 1


// In Thread 2
dict["bar"] = 2

実装

Lock Striping な辞書の実装。 キーは文字列、値は数字のみにしている。 hash 関数に FNV prime を使っている。 Hash値(とbucket sizeの剰余)ごとに bucket をもって、それごとにロックを管理している。 その為、ちがう bucket であれば並列に実行可能になる。

github.com

パフォーマンス

スペック

• OS: macOS Sierra
• Processor: Intel® Core™ i7-6567U CPU @ 3.30GHz
• Memory: 16 GB 2133 MHz LPDDR3
• go version: go1.8 darwin/amd64

計測したコード

github.com

結果

synchronizedDict~ が dict に対して 1 つのロックを取っている方で、 stripedDict~ が Striping Lock をしている方。 最後の数 (たとえば、synchronizedDictWriting1 の 1) は Write する Worker の数を表している (1,3,5 でためした)。 だいたい予想通りの結果になっているようにみえる。 write する worker が 1 つのとき (並列に実行していない時) は hash 値の計算などのオーバヘッドがあるから若干 stripedDict のほうが遅くなっている。 それ以外はロックが分散されて、並列度が上がったためパフォーマンスがよくなっている。

Elapsed Time in synchronizedDictWriting1: 43.632465ms
Elapsed Time in stripedDictWriting1: 35.341727ms

Elapsed Time in synchronizedDictWriting2: 62.054392ms
Elapsed Time in stripedDictWriting2: 48.307852ms

Elapsed Time in synchronizedDictWriting5: 172.436661ms
Elapsed Time in stripedDictWriting5: 89.864355ms