Document

いつからFIFOが
スケールしないと
錯覚していた？
What is Lock-free ?
• 正確に言うと他のスレッドをブロッキングせず
に全体での進行が保障される特性のこと
• 詳しくは魔導書をば！
• 以後これを前提に話します
Lock-free Stack：Overview
struct Node{
Node* next;
int value;
};
Head
NodeA
ポインタという意味
•CASをHeadポインタに適用する
Lock-free Stack: Push
struct Node{
Node* next;
int value;
};
Head
NodeA
CAS
NodeB
NodeAを指してるなら
NodeBを指すようCAS
Push完了！
Lock-free Stack: Pop
struct Node{
Node* next;
int value;
};
Head
NodeA
CAS
NodeB
NodeBを指してるなら
NodeAを指すようCAS
Pop完了！
衝突時の挙動
PushとPushが衝突すると？
NodeA
CAS
Head
CAS
NodeC
失敗した！
NodeB
ぶつかるとどうなるか
• いくつもの操作が同時に行われると？
NodeA
Head
CAS
NodeC
NodeB
Lock-free Queueもできるのでは
• もちろん
• 一番簡単なMS-Queueを紹介
[出典] Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms
Maged M. Michael ら(1996)
初期状態
• HeadとTailが同一のダミーノードを指す
• 保持されている要素+1個のノードを持つ
Tail
Head
Dummy
エンキュー(1/5)
2回のCASを使う
① Tailのnextに新規ノードを繋げる
② Tailを新規ノードに繋げる
Tail
Head
CAS
New
Dummy
① CAS(&Dummy->next, Null, New);
エンキュー(2/5)
• 1ステップ目は更新出来るまで繰り返す
• しかしTailの更新②は先を越されて失敗しても放置
– 理由は後述
CAS(&Tail, Dummy, New);
CAS
Tail
New
② ←失敗しても無視
Dummy
Head
エンキュー(3/5)
• ①だけ終わった状態では下記のようになる
– この瞬間にプリエンプションされたとする
• ここで別のスレッドがenque,dequeしにきた場
合が問題
Tail
ひと休みするかー
CAS
New
Dummy
Head
エンキュー(4/5)
• この場合は後続のenque,dequeが訂正操作を行う
デキューしに来たんだけど
Tail->nextがNULL指してないの
気になっちゃうんだよねー
Tail
Head
CAS
New
Dummy
エンキュー(5/5)
• 1ステップ目の操作のみを線形化ポイントとす
る事で線形化可能性を満たしている
– (魔導書読んだ人向けの説明
Tail
New
Head
Dummy
デキュー(1/2)
•
•
•
•
Headの指している物のNext(つまりA)を確保
HeadをCASですげ替える(失敗したら①から)
確保しておいた物（つまりA）を結果として返す
Headが指していたもの（Dummy）を消す
Tail
Head
CAS
B
A
Dummy
デキュー(2/2)
• Stackとの違いに注意
• 直前にDequeueされたデータがHeadの指す先の
ノードに乗りっぱなしになるのが正しい挙動
• 次のデキューの際にこの古いAを乗せたノードが開
放される
Tail
Aがデキュー
された後の姿
B
A
Head
Lock-free Queueすごい！
• これってこれ以上速くならないの？
– CASを削減するなどの細かい改良は出ている
まだいける
Lock-free Stackをいじめると
• うわぁ…
CAS
Head
CASCAS
CASCASCASCAS
CASCAS
CAS
CAS
Cache is the new Disk!
• Headポインタの載った1本のキャッシュライン
を複数のコアが取り合う
• キャッシュのCopyとInvalidateのコストが全体
の速度を律速してしまう
• 特にCopyの要求を飛ばす事自体が他のス
レッドの足を引っ張る
対策
• ウェイトを入れる
– 具体的には
NodeA
Head
CAS
CAS
NodeC
NodeB
200クロックぐらい待とう…
[出典]A Scalable Lock-free Stack Algorithm
Danny Hendler ら(2004)
ベンチマーク
無駄な衝突が減ってスループットが向上する
Fast
待機あり
待機なし
これで最速？
そんな風に考えていた時期が僕にもありました
更なる対策
• Waitを挟むのなら、そのWaitの時間をもう少
し有意義に使えないか？
さらなる対策
• PushとPopのマッチングを行う事がStackの使命
• Headポインタを取り合うから悪い Push
• 待機中にマッチングすればよくね
CAS
CAS CAS
Stack
待機場所
CAS CAS
Pop
CAS
CAS
[出典]A Scalable Lock-free Stack Algorithm
Danny Hendler ら(2004)
Elimination Stack
• Elimination Arrayを導入
• 操作に失敗したスレッドはランダムな位置に陣取る
CAS
CAS
CAS
CAS
失敗した！
CAS
Head
EliminationArray：Push side
• Pushに失敗したスレッドはランダム待機する
• 待機開始時にEliminationArrayのランダムな位置
にCASして待機する
NodeA
CAS
しばらく
待つかー
Head
CAS
NodeC
NodeB
CAS(&EA[r], NULL, NodeC);
EliminationArray：Pop side
• Popに失敗したらEliminationArrayを舐める
• Push待ちの要素を発見したらCASを試みる
CAS
うほっ
いいノード
やらないか
NodeA
NodeB
CAS(&EA[r], NodeC, NULL);
NodeC
Head
EliminationArray：Pop side
• 配列の当該エントリーをNullにできたら成功
• Pushする側は待機終了時に再びCASで値を獲得しにくる
– そのときに要素が空だったら操作終了
Pushに戻ろうとしたら要素消えてる
きっと誰かが持っていったんだろう
仕事終わり！
もらい！
CAS(&EA[r], NodeC, NULL) => fail
NodeC
[出典]A Scalable Lock-free Stack Algorithm
Danny Hendler ら(2004)
ベンチマーク
Fast
Elimination
普通の待機
それって大丈夫なの？
• 大丈夫。線形化可能性（魔導書参照）の条件
をキッチリ満たしている
操作開始
Push()
操作終了
Pop()
pop()
Pop()
Push()
Push()
Push()
それって大丈夫なの？
• pushした0.1クロック後にpopしたと考えて良い
操作開始
Push()
操作終了
Pop()
pop()
Pop()
Push()
Push()
Push()
Elimination
なぜ速いの？
• Headポインタを取り合わなくても成功する
Push/Popの組がある
• キャッシュライン上でのコヒーレントトラフィック
削減
• NUMA向けにさらに地産池消を推し進めた階
層化Eliminationもあるけど今は扱わず
Stackでしか使えないじゃん？
いつからEliminationが
Stack専用だと
錯覚していた？
Elimination Queue(SPAA2005)
• Queueの一貫性を一切壊さず、Eliminationに
よってスケールアウトさせる
• 一貫性を壊さない＝線形化可能性を満たす
[出展]Using Elimination to Implement Scalable and Lock-free FIFO Queues
Mark Moir ら
Elimination Queue
• Queueの外にEliminationArrayを付ける
• Enqueueカウンタ、Dequeueカウンタを付ける
Enqueueカウンタ
Dequeueカウンタ
2
0
Tail
Head
B
A
Dummy
Elimination Queue
• 各ノードにはEnqueueを試み始めたときのカ
ウンタ値が載っている
Enqueueカウンタ
Dequeueカウンタ
2
0
Tail
Head
1
B
0
A
Dummy
Elimination Queue
• カウンタはEnqueue、Dequeueが成功するた
びにFetchAndAddでAtomicにインクリメント
Enqueueカウンタ
Dequeueカウンタ
23
0
Tail
Head
2
C
1
B
0
A
Dummy
Elimination Queue
• CASに失敗したらEliminationArrayに乗せる
2
B
Enqueueカウンタ
Dequeueカウンタ
3
0
Tail
Head
1
B
0
A
Dummy
Elimination Queue
• CASに失敗したらEliminationArrayに乗せる
2
B
Enqueueカウンタ
Dequeueカウンタ
5
2
Tail
Head
4
E
3
D
Dummy
Elimination Queue
• Dequeueしに来たスレッドはDequeueカウンタと
EliminationArrayに載ってるノードのカウンタ値を比較
• Dequeueカウンタが等しいか大きかったらそれを持っていく
2
B
Enqueueカウンタ
Dequeueカウンタ
5
2
Tail
Head
4
E
3
D
Dummy
何が起きるの？
• 早いタイミングでEnqueueしにきたスレッドは
充分に行き遅れた後は追い越して良い
• 仮想的に、早いタイミングでEnqueueが終わっ
たものと見なす
大丈夫なの？
• 線形化ポイントを並べるとこう
Enq(3)
Deq(1)
Deq(2)
Enq(1)
Elimination
Enq(2)
Enq(4)
まともに動いてないのでは？
• それが、まともにうごいてるんです
• 20歳から婚活を始めて、全くうまく行かず
50歳で急に結婚できたと思ったら既に子供
が3人居て大学卒業してるかのような状態
なぜ大丈夫なのか
• 生じた結果から動作を逆算するとこう
Enq(3)
Deq(1)
Deq(2)
Enq(1)
Elimination
Enq(2)
Enq(4)
まったく同じIO結果が出ている！
• これはまったく同じとみなしてよい！！！
– な、なんだってー！
見比べてみよう
物理的な状態
Enq(3)
Deq(1)
Deq(2)
Enq(1)
Elimination
Enq(2)
Enq(4)
見比べてみよう
論理的な状態
Enq(3)
Deq(1)
Deq(2)
Enq(1)
Elimination
Enq(2)
Enq(4)
結果が一致しているので問題ない！
• 歴史を書き換えるEliminationArray！！！
そしてパフォーマンスは？
• スケーーーーールする！！！

Download Report