- 社内勉強会で使用したスライドです
lock-freeの前にまずスレッドセーフなデータ構造についておさらい
- 基本的にmutableなデータ構造をスレッドセーフにする場合はロックを取る必要がある
- Javaでは一つのロックでコレクション全体を管理するものを同期化コレクション、分散ロックを使用するものを並行コレクションと読んでいるっぽい
- 同期化コレクションに同時にアクセスできるスレッドは一つのみ他はロック獲得待ちになる
- 並行コレクションでもロックが競合するとロック獲得待ちになる
- ロックが競合するとスレッドは待ち状態になる
- fork-joinアルゴリズムとスレッドがブロックする可能性がある並行コレクションは相性が悪い
- immutableなデータ構造は自明にスレッドセーフになる
lock-freeとは
- マルチスレッドでロックを使用しないアルゴリズム
- CAS (Compare And Swap) 命令を使う
- 前回の値と等しい場合は新しい値をsetし、異なる場合は失敗とみなす
- 他のスレッドに値を変更されている時はcas命令は失敗する
- CAS命令に失敗した場合、他のスレッドと競合したものとみなし、自スレッドの操作をabortしてもう一回初めから行う
- 他のスレッドの操作を打ち消さないようにしてアルゴリズム全体が進行
- 悪意のあるスレッドスケジュールによって自スレッドの操作が常に失敗する可能性はある
- 悪意のあるスレッドスケジュールでも規定ステップ内で自スレッドの操作が完了する事を保証するものをwait-freeと呼ぶ
- wait-freeは複雑でスループットが落ちるのであまり使われない(？)
//CAS命令を用いた擬似lock-freeカウンタ-
class CasCounter {
val value: CAS[Int]
def increment(): Int {
var oldValue = value.getValue()
// 成功するまでcasを繰り返す
while (value.compareAndSwap(oldValue, oldValue + 1) != oldValue) {
oldValue = value.getValue()
}
oldValue
}
}
ScalaのTrieMap
- ノンブロッキング
- O(1)でスナップショットを取得
- ロックを取らないにも関わらずある時点でのiteratorを取得できる
どうやって実現しているのか
HashTableの復習
適当な長さの配列を用意して なるべく配列に均等に振り分けらるようにハッシュ値を計算するキー衝突が多発したらより大きな配列にコピーする
ScalaのimmutableなMap実装
ナイーブなHashテーブルはimmutableなMapと相性が悪い
keyを追加したり更新したりする度に配列の全コピーをしなければならなくなる。
ScalaのimmutableなMapでは木構造を取ることで全体のコピーを回避している
hashキーをどのように木構造に割り当てているのだろうか
Hash Array Mapped Tries(HAMT)
hashの下位5bit毎に比較する。
hashの部分bit == 配列のindexとなるのでアクセスが高速
hashの部分bitが衝突したら次の下位5bitを使用した配列を作成する
木構造かつ木の深さのmaxがあるので、更新、検索が実質O(1)
ただしこれだとnull要素が多く無駄がある。
よって配列のnull要素を0、要素があるものを1にしたbitmapを作って各配列に持たせて圧縮する。
(32要素あるのでbitmapにすると32bit整数 == Integer)
CAS命令を使ってHAMTをスレッドセーフなmutableなMapにする(なぜmutableなMapにもHAMTを使うのかは後で説明する)
update時にCAS命令、
keyを用いて検索する時は@volatileを使用する。
(key-valueは省略)
他のスレッドが先に書き換えてなければ、CAS命令は成功する
失敗した場合は成功するまでCASを繰り返す。
一見これだけで良さそうだが。。
異なる深さのnodeを変更する場合
CAS成功後
同時にinsertすると一方の操作が失われてしまう。
これを防ぐためにTrieMapではI-Nodeを木の各node間に置いている
CAS成功後
I-Nodeを置く事で両方ともinsertできた。
古いnodeはGCされる。
個別のnodeを操作するinsert, update, delete, find などの操作はこれで問題ないが、
一つのスレッドが全体を走査している間に他のスレッドが書き換えてしまうため
map, size, iteratorなどのTrieMap全体に対する操作は上手くいかない
解決策
- 一貫した操作を諦める
- 悲しい
- ロックを使う
- lock-freeとはなんだったのか
- 世代管理によってsnapshotを取る
- 各I-Nodeに世代1を持たせる
- snapshotを取る時ルートの参照を違う世代のI-Nodeにする
- snapshotは古いI-Nodeを見る
snapshot取得
- snapshot取得はO(1)
- snapshotが見ている世代1はimmutableで他のスレッドによって変更されない
- 参照するだけならrootも世代1のものを共有する
CAS(Compare And Swap)ではなくDCSS2(Double Compare Single Swap)なのは
i-nodeだけではなくmain-nodeも変更されていないか比較しなければならないから。
DCSSの詳しい説明は難しいので割愛する
- insertする場合は世代1をrootから見てimmutableなものとして扱う
- HAMTを採用したのはこの為
- insertする時に見ている世代が古い場合、作成したコピーを参照する
- rootから辿れない古い世代のnodeはsnapshotを使い終えたらGCされる
- CASする前にrootの世代を変更されてsnapshotを取られたら?
- 世代が変更されたのを知らずにimmutableな筈のsnapshotを変更する危険性
- rootの世代を変更されたらCASを失敗させたい
- 各node変更する前に必ずDCSSを行う？
- 正しく失敗するが毎回DCSSは重い
GCAS
- Generation Compare And Swap
- 普通にCASした後にrootの世代を確認、世代が異なる場合CASをabortさせる
- 各nodeを読み込む時にGCASが完了しているかチェックする
- GCASはCAS, rootの世代チェックと二段階踏むため
- CAS後 root世代と等しい場合はprevにnullを代入する
- 古いnodeはGCされる
- prevがnull以外の時GCASはまだ完了していない
- root世代と異なる場合はGCASを失敗させて前のnodeに戻さなければならない
CAS後
- prevをfail nodeに変える
- CASして元に戻す
- 最初からinsertをやり直す
最後に全てのCASをGCASに全てのreadをprevがnullかどうか確認するGReadに変更すればok
まとめ
ScalaのTrieMapはlock-freeかつ一貫したO(1)snapshotを実現している事が分かった
lock-freeアルゴリズムはJavaのfork-joinスレッドプールのタスクキューやakka-actorのメッセージキューにも使われているので、参考になれば
(というかlock-freeを紹介するのだったらlock-freeキューの方がよかったかも。。？)
参考
http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf
https://www.slideshare.net/AleksandarProkopec/ctrie-data-structure/
https://www.cl.cam.ac.uk/research/srg/netos/papers/2002-casn.pdf
-
世代と言っても被らせない為に数字ではなく適当なobjectを生成しアドレスチェックで管理している ↩
-
https://www.cl.cam.ac.uk/research/srg/netos/papers/2002-casn.pdf ↩