社内勉強会で使用したスライドです

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に世代¹を持たせる
snapshotを取る時ルートの参照を違う世代のI-Nodeにする
snapshotは古いI-Nodeを見る

snapshot取得

snapshot取得はO(1)
snapshotが見ている世代1はimmutableで他のスレッドによって変更されない
参照するだけならrootも世代1のものを共有する

CAS(Compare And Swap)ではなくDCSS²(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 ↩