冬のLock-Free祭り

DSIRNLP @kumagi

辻Lock-free Lock-freeと発言した人に文脈を無視して きなり@を飛ばす行為 い

僕と一緒に Lock-free!

CPUの系譜のおさらい 無限に続くかに思われたCPU加速戦争 周波数が勝手に上がるので「システムを高速化し て欲しいという案件は半年遊んでからマシン買い 換えさせればいいや」とまで言われた 周波数加速はPentium終盤から雲行きが怪しくなる AthlonX2やCore世代の台頭 AMD「周波数あげるの無理だからコア数増やそうぜ」 Intel「そだねー」

CPUの系譜のおさらい CPUの製造コストのためチップ面積を節約し たい 少ない面積で高い性能を出す方法はないか？ ポラックの法則 「2倍のシングルスレッド性能を得るためには4倍 のリソースが必要になる」というintelの中の人の 経験則 逆手に取れば「半分の性能で良ければ4個のコア を積める」

ポラックの法則 半分の性能のコアなら1/4の面積 ¼の面積なら同じ面積に４個積める！ ½の性能 × 4コア = 2倍の性能！！ 1/2 1/2 1/2 1/2

それ活かしてパワフルなの作れば？ 1/3の性能なら1/9の面積だから9個積める。 それなら合計で3倍のパワーが出る 既にあります

Intel Many Core 驚きの48コア搭載 最大消費電力125W 同規模のCPUの約3倍のエネルギー効率 今年の秋ごろから世界中の研究機関に試作品が 送られて使い方を研究してる 知ってる範囲だと東大と京大には納入されてる

なんで普及しないの？

We are the Bottleneck! 情報工学の発展が追い付いていない！ ヽ('ω')ﾉ三ヽ('ω')ﾉもうしわけねぇもうしわけねぇ

マルチコアを使い倒して スーパープログラマへ！！

そして タダ飯の時代よ今再び！

マルチスレッドは簡単じゃない 同時に実行するということは、発生する実行の組み 合わせが指数的に爆発する 通常はロックを用いて調停を行う そしてBlockingする

What is Blocking? ビーチフラッグを例に CPU

What is Blocking? 排他すると ロック OK! クリティカルセクション

What is Blocking? クリティカルセクションは危険がいっぱい クリティカルセクション

What is Blocking? クリティカルセクションは危険がいっぱい クリティカルセクション

What is Blocking? コアが増えるほどに問題が顕著に！ 早くしろよ… 早くしろよ… 早くしろよ… 早くしろよ… 早くしろよ… 早くしろよ… 早くしろよ… 早くしろよ… 早くしろよ… クリティカルセクション

そこで Lock-free クリティカルセクションを 作らないので 他のスレッドを足止めしない！

Lockを用いないとどうなるか CPU内部では処理は複数のステップで行われる ++x; 1.xを読み出す 2.読んだ値に +1 3.xを保存する

Lockを用いないとどうなるか 複数スレッドが同時に行うと x==1 スレッドA スレッドB 1.xを読み出す(1) 1.xを読み出す(2) 2.読んだ値に +1 2.読んだ値に +1 3.xを保存する(1) 3.xを保存する(3) OK! x==3

Lockを用いないとどうなるか 複数スレッドが同時に行うと破綻する場合がある x==1 スレッドA スレッドB 1.xを読み出す(1) 1.xを読み出す(1) 2.読んだ値に +1 2.読んだ値に +1 3.xを保存する(2) 3.xを保存する(2) 数が合わない x==2

道具の紹介 「targetが期待通りの値だったら置換」を一気に行 う命令 以後ではCASと略します bool compare_and_swap(int* target, int expected, int newval){ if(*target == expected){ *target = newval; return true; } return false; }

CASを使ってみよう Lock-free共有カウンタの例 int x; void add1(){ int old,new; do{ old = x; new = old+1; }while(!cas(&x, old, new)); } 失敗してたらやり直す

CASを使ってみよう CASのお陰で衝突しても破綻しない x==1 スレッドA スレッドB 1. xを読み出す(1) 2. 読んだ値に +1 3. 値が1なら2へCAS 4. 失敗したので再挑戦 5. xを読み出す(2) 6. 読んだ値に +1 7. 値が2なら3へCAS 1. xを読み出す(1) 2. 読んだ値に +1 3. 値が1なら2へCAS 数が合う！ x==3

冬のLock-free祭り マルチスレッドReadyでありながらロックを用いない データ構造 話す予定のおしながき Lock-free Stack Lock-free Queue Lock-free List Lock-free Hashmap Lock-free SkipList Lock-free Btree Dynamic STM(Obstruction-free STM) ？？？

Lock-free Stack Compare And Swapの正しい使い方

Lock-free Stack ↓ポインタ A Head CAS 「Headが指している物を指したノードを作ってCAS」

Lock-free Stack B A CAS CAS CAS Head C D 失敗した！

Lock-free Stack A B また失敗した！ C CAS Head CAS D

Lock-free Stack A Head CAS C B D

Lock-free Stackからpop A Head CAS C D B

ね。簡単でしょ！ Lock-free怖くない！ いわゆるABA問題は今日は扱いません どしどし行きます！

Lock-free QUEUE 不変条件に手を加える

Lock-free Queue の Deque Tail Head

Lock-free Queue の Deque Deque操作は簡単 Lock-free Stackと同じ挙動なので

Lock-free Queue の Deque Tail Head CASCAS

Lock-free Queue の Enque Enque操作 1. Enqueしたい要素eを用意する 2. 末尾のノードが指すポインタがeを指すようCAS 3. Tailポインタがeを指すようCAS 2ステップ必要

Lock-free Queue の Enque Tail CAS CAS Head

Lock-free Queue の Enque Tail CAS Head 構造が破綻 CAS CAS CPU1 1. 要素eを用意する 2. 末尾をCAS 3. TailポインタをCAS CPU2 1. 要素eを用意する 2. 末尾をCAS 3. TailポインタをCAS

不変条件を考える アルゴリズムは必ず何かしらの前提が必要 マルチスレッドプログラムでもそれは同じ 常にその条件を満たし続けるのは無理→ロック 条件守ってる！ 条件守ってる！ 時間軸→ 条件守ってない！

不変条件を守る 他のCPUが思いもよらない変更を加えてくる 危険な瞬間 CPU1 CPU2 CPU3 CPU4 時間軸→

不変条件を守る ロックを用いて排他する CPU1 CPU2 CPU3 CPU4 時間軸→

不変条件を守る ロックのおかげで危険な瞬間がなくなる CPU1 CPU2 CPU3 CPU4 時間軸→

ロックの目的と効果 普通にプログラムを書くとどうしても不変条件を 破壊する瞬間が生まれてしまう そこはロックで守るのが普通 void queue::enque(const T& v){ node* const new_node = new node(v); node* const tail = que_tail_; tail->next = new_node; que_tail = new_node; } ↓時間軸 危ない

ロックの目的と効果 Lock-free Stackは不変条件を満たさない瞬間を外 部から観測されないように最小化してCASで片づ けられた CPU1 CAS CPU2 CAS CPU3 CPU4 CAS CAS CAS CAS CAS

ロックの目的と効果 Lock-free Queueは2度CASが要るのでタイミングに よって危険 危険な瞬間 CPU1 CAS CPU2 CAS CPU3 CPU4 CAS CAS CAS CAS CAS CAS CAS CAS CAS CAS CAS CAS

Lock-free Queueはどうするのか 不変条件 Headがキューの先頭を指す Tailがキューの末尾を指す Tail以外のノードは必ず有効なノードを指す 条件を緩める 不変条件 Headがキューの先頭を指す Tailがキューの末尾を指さないかもしれない Tail以外のノードは必ず有効なノードを指す

Tailが末尾を指さないとは？ 末尾を指してる Tail Head 末尾を指してない Tail Head

解決 「Tailが遅れてたらみんな手伝ってあげてね」 「Tailの更新に失敗してもみんな気にしないでね」 Tail Head CAS 破綻しない！ CAS CPU1 1. 2. 3. 4. CPU2 要素eを用意する Tailが遅れてたら進める 末尾をCAS TailポインタをCAS(失敗) 1. 2. 3. 4. 要素eを用意する Tailが遅れてたら進める 末尾をCAS TailポインタをCAS

Lock-free Queueかっこいい！
EnqueとDequeの共同作業！
void enque(const T& v){
const Node* const node = new Node(v);
while(1){
const Node* const last = mTail;
const Node* const next = last->mNext;
if(last != mTail){ continue; }
if(next == NULL){
if(compare_and_set(&last->mNext, next,
node)){
compare_and_set(&mTail, last, node);
return;
}
}else{
compare_and_set(&mTail, last, next);
}
}
}

T deque(){
while(1){
const Node* const first = mHead;
const Node* const last = mTail;
const Node* const next = first->mNext;
if(first != mHead){ continue;}
if(first == last){
if(next == NULL){
while(mHead->mNext ==
NULL){ usleep(1); }
continue;
}
compare_and_set(&mTail,last,next);
}else{
T result = next->mValue;
if(compare_and_set(&mHead, first, next)){
delete first;
return result;
}
}
}

Lock-free Queueかっこいい！
EnqueとDequeの共同作業！
void enque(const T& v){
const Node* const node = new Node(v);
while(1){
const Node* const last = mTail;
const Node* const next = last->mNext;
if(last != mTail){ continue; }
if(next == NULL){
if(compare_and_set(&last->mNext, next,
node)){
compare_and_set(&mTail, last, node);
return;
}
}else{
compare_and_set(&mTail, last, next);
}
}
}

T deque(){
while(1){
const Node* const first = mHead;
const Node* const last = mTail;
const Node* const next = first->mNext;
if(first != mHead){ continue;}
if(first == last){
if(next == NULL){
while(mHead->mNext ==
NULL){ usleep(1); }
continue;
}
compare_and_set(&mTail,last,next);
}else{
T result = next->mValue;
if(compare_and_set(&mHead, first, next)){
delete first;
return result;
}
}
}

閑話休題 Lock-freeよくある質問と答え そんな複雑な事しなくても Message-Passingなら完璧だよ

MessagePassing 「メッセージを渡す」という哲学に基づいて、操作 の実行順序をメッセージ順にしてしまうこと ですよね？ Deq Enq Deq Deq Enq Queue

Lock-free 例えるならこんな感じ！ Deq Enq Deq Deq Enq Queue

どういうこと？ スケールする！ FASTER Single-lock Lock-free

あなたも一緒に Lock-free!

発展話題 今のアルゴリズムで実装されてるのが boost.lockfreeのqueue リソース管理がもう少し複雑 IntelのTBBやらFastFlowとかいうライブラリでもこ のlock-free queueだったような… このアルゴリズムは発明者の名前を取って MS-Queueと呼ぶ

Lock-free List ポインタに情報を詰め込め

ConcurrentList 複数のスレッドから同時に読み書きできるList いろんな粒度のロックがあるので順番に紹介

粗粒度ロック 全体を排他するだけ もちろんスケールしない Head

悲観的ロック ノードごとにロックを用意 ロック・アンロックしながら「歩く」 Head • かなり遅くなる • 他のスレッドのイテレーションを追い越せない

楽観的ロック 必要になるまでロックを取らない Head これでいいんじゃない？

楽観的ロック だめなんです 私の安定性…低すぎ… ロックを2つ取って おりゃ！ これ消すぞー！ Head Segmentation Fault これ消すぞー 消したぞー

楽観的ロック ロックした後に、リストの先頭からきちんと到達可 能であることを確かめてから消す必要がある つまり安全のためリストを2回舐めることになる Head

つまり 単一ロックだとスケールしない 細粒度ロックだと 悲観的にロックすると遅い 楽観的にロックすると二度見のコストがつく Lazyな消去を導入する事で改善可能だけど省略

さぁLock-freeだ

挿入処理 • リストの繋ぎ替え処理にCASを使用して衝突を回避し、 検索の邪魔をしない • 道路封鎖せず道路工事してる感じ CAS

挿入処理 CASを使う事によって、同一の場所に同時に複数 の挿入が発生しても 大丈夫！ CAS CAS CAS 失敗した！

削除処理 挿入処理と同様に、ポインタをCASで繋ぎ変える CAS 追い出しに成功したスレッドがdelete

このアルゴリズムにはミスがある

問題が 連続したノードを同時に削除しようとするとデータ 構造が破壊される CAS CAS Segmentation Fault

問題が 削除と挿入がぶつかっても破壊される CAS CAS Memory Leak

解決策 ノードの削除を「マーキング」「ポインタ繋ぎかえ」 の2段階に分ける マーキングされてたら誰でも削除を手伝う ポインタ繋ぎかえに失敗しても気にしない マーキング前と後の2状態に対して操作を記述

マーキングはどこに？ ポインタの1bit目をマーキング対象に 動的確保したメモリは4の倍数ぐらいにはAlignされてる つまり1bit目は通常0 マーキング処理もCASを用いる ココ！ 順序づけ大事 なぜそんなところに埋め込むの？ １回のCASで１word分しか操作できない 何とかして削除マークとポインタをAtomicにしたい

正しい削除手順 2回CASを使う CAS CAS

さっきのはどうなるか CAS CAS CAS CAS CAS マーキングにより CAS失敗する

さっきのはどうなるか CAS CAS CAS マーキングにより CAS失敗する

素晴らしい！！

Lock-free Hashmap バケットがアイテムの間を動く

Hashmap便利ですよね いわゆる連想配列 O(1)でアクセスできるみんなの人気者

細粒度Lock Hashmap 0 1 2 3 4 5 6 7 全部のバケットにロックを取り付けてやる方法 実はあんまり効率よくない

Striped Lock Hashmap 0 1 2 3 4 5 6 7 固定数のLockをmoduloでバケットに割り当てる スレッドの数が膨大にならない限りロックそのものが増えて も恩恵がないため バケットごとに対応するロックが縞模様になるのでStriped

java.util.concurrent.ConcurrentHashMap 0 1 2 3 4 5 6 7 volatile final 基本的にStriped Lockだけど、成功する検索はwaitfree 失敗する検索はロックを取ってもう一回行う 削除はチェインを部分的にまるっとRCU バケットの拡張は再帰的にロックを全て獲得しながら行う

Lock free?

Lockの無くし方を考える 0 1 2 3 4 5 6 7 線形リスト部分はLock-free Listを使えばいい バケット部分の拡張が鬼門

どうするバケット拡張 あらかじめ充分巨大なバケットにしてしまう 富豪的過ぎて実用的でない CASでバケット列を複製 複製作業中に挿入・削除が走る 一貫性無理☆ 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7

バケットの拡張が 困難

そうだ バケットの中身の移動が必要ない設計になれば いいんだ！

全体図 内部を昇順のLock-free List一本で集約 番兵ノード 00000010 ↓ 01000000 データノード 00 0 1 2 3 02 40 48 00000001 ↓ 10000000 6d 7f 80 8a 00000011 ↓ 11000000 c0 74 Hashmapのインデックス値を逆順にしてリスト に投入

どういうこと？ 普通はバケットにデータを吊るしてる 0 1 2 3 02 48 6d 7f 8a 74 こっちはデータの間にバケットの目印を吊るす 0 1 2 3 1本のList 02 00 40 48 80 c0 6d 8a 74 7f

データの挿入 1. 対象となるデータのハッシュ値を算出→2 2. ハッシュ値に対応するテーブルにアクセス 3. テーブルに番兵ノードへのポインタが書いてあるため対 応するノードへジャンプ 4. 番兵ノードの指すポインタをたどっていけばHash値の昇 順にデータが並んでいるため、対応する場所に挿入 5. リストが昇順に並んでいるという前提は崩れない！ 00 69 0 1 2 3 02 40 48 6d 7f 80 8a c0 74

テーブルの拡張 番兵ノードの間に挟まるアイテムの数が一定数を超え た場合にテーブルを拡張する 左のテーブルは工夫してあり、基本的に初期化以降 immutable 詳細な部分は論文で 00 0 1 2 3 4 5 6 7 02 40 48 6d 7f 80 8a c0 74

テーブルの拡張 5. 拡張操作はテーブルを大きくするだけでおしまい(CASでも可能) テーブル拡張後は新規探索は新しいテーブル上で行う テーブルが未初期化ならその一個左の番兵ノードから探索 番兵ノードが挿入されているべき個所を見つけ次第、番兵ノードを 挿入する 目的の場所を見つけたら挿入 6. リストが昇順に並んでいるという前提は崩れない 1. 2. 3. 4. 00 62 0 1 2 3 4 5 6 7 02 40 48 60 6d 69 7f 80 8a c0 74

ロックなしで並行動作する！ 何があっても リストが昇順に並んでいるという前提は 崩れない 挿入と拡張が同時に走っても 削除と挿入が同時に走っても 大丈夫！

FAST 驚異的なスケーラビリティ

FAST Lock-free java.util.concurrent.ConcurrentHashMap 性能負けてる！！！ スレッド数

Lock-free Hashmapかわいい！

Lock-free SkipList 線形化ポイントはどこ？

SkipList ご存じ・・・ですよね？

SkipList 順序関係のあるデータをO(log n)で検索・挿入・ 削除ができるデータ構造 2分木とモロ被り 乱数に依存するため木と違いリバランスする必 要が無い 平衡2分木を平衡に扱うにはリバランス専用のスレッドを別に 立てる方法が現時点で一番高いスループットの出る方法だっ たような… LevelDBの中で使われていてちょっと話題に

SkipList 昇順に並べた普通のリスト に高レベルなリストを加えたもの レベル1上がる毎に1/2のノードが間引かれる -∞ -∞ -∞ -∞ -∞ -∞ 3 3 3 8 8 33 12 33 12 33 64 12 33 51 64 12 16 33 51 64 12 16 29 33 51 64 ∞ ∞ ∞ ∞ ∞ ∞

SkipListでの検索 高いレベルから順に辿っていくだけ 新幹線・特急・快速・鈍行と乗り換えるイメージ 29どこー？ -∞ -∞ -∞ -∞ -∞ -∞ 3 3 3 8 8 33 12 33 12 33 64 12 33 51 64 あったー！ 12 16 33 51 64 12 16 29 33 51 64 ∞ ∞ ∞ ∞ ∞ ∞

これをどうLock-freeにするの？ まずはLock-basedなSkip Listの実装を見ましょう

Lock-based Skip List ノードごとにロックを用意

Lock-based Skip List 1. ここに挿入したいとする 2. そこ以前のリンクの状態を記憶 3. 昇順にロックを獲得 4. 2の時に記憶した内容と現在の内容が一致していることを確認 5. 全部一致したら下から順にリンクを繋ぎ変えていく

Lock-based Skip List できました！ 実際は線形化ポイントを確定するためFullyLinked ビットを用いて線形化します 詳しくはgithub.com/kumagi/sl

さあ Lock-freeだ

具体的な戦略 Lock-free Listと同様に、ポインタに削除bitを導入 一番下のリストへの操作をSkipListへの操作と見なす それ以上のリストは高速化のための「飾り」

Lock-free SkipListへの挿入 1. 最下位リストへの挿入を行う 2. 下のレベルから順に上位リストのリンクを繋ぎ変える 3. 繋ぎ変える途中で他人に書き換えられてたら前後の情報を再 確認して繋ぎ変えを続行

Lock-free SkipListへの挿入 1. 最下位リストへの挿入を行う 2. 下のレベルから順に上位リストのリンクを繋ぎ変える 3. 繋ぎ変える途中で他人に書き換えられてたら前後の情報を再 確認して繋ぎ変えを続行

Lock-free SkipListでの削除 1. 対象物の前後の関係を洗い出す 2. 上位ノードから順番に削除マークを振っていく 3. 上位ノードから順に追い出していく

そんなので平気なの？ 詳しく追ってみましょう

挿入・挿入の衝突 やりなおすだけ 割り込んだ 最下位レベルで割り込まれた場合は初めからやり直す 通常のLock-free Listと同様の作法

挿入・挿入の衝突 割り込んだ 最下位以外で割りこまれたらそこから再開 最下位以外は厳密に一貫している必要はないのでOK

挿入・削除の衝突 削除開始 削除はLock-free Listと同じくマーキングによってCASが失敗する 仕組みになっている そしてやり直すだけ

ポイント 削除・挿入ともに「一番下のリストへの操作の成 功・失敗」を全体の成功・失敗と見なす 挿入は下のリストから。削除は上のリストから。 リストのイテレートが上のレベルからなので衝突した際 に複雑な手続きにならないようにした配慮 Java.util.concurrentのファミリーに居る クレイジーな人はコードを読んでみよう☆ DougLea先生…

Lock-free Btree 恐るるに足らず！

みんな大好きBtree 18 28 16 5 7 13 16 22 25 33 HashMapと並ぶデータベースの基礎技術 O(log n)のアクセス速度で大量のデータに向く

普通のBtreeの挿入操作 26 18 28 25 16 28 足りない！ 5 7 13 16 22 22 25 26 33 Split ノードに余裕がなくなった時にSplit操作を行う 余裕のないノードしかSplit操作は行われない 削除はノードの中身が半分を割った時にmerge操作

Lock-free!

Lock-free化 Root CAS 複製 複製 複製 ここに挿入したい 必要なデータをすべて複製してしまえばいい

Lock-free化 Root Split 必要なデータをすべて複製してしまえばいい SplitやMergeも全く同様。部分木を丸ごと作り直す

Lock-free化 Root 割り込んだ別スレッド 割り込まれたので CAS失敗→初めから やりなおし 必要なデータをすべて複製してしまえばいい SplitやMergeも全く同様。部分木を丸ごと作り直す 衝突したらそのスレッドは初めからやり直し すべての操作はRootに対するCASで直列化

超☆遅い まともなアルゴリズムが他にあるはずなのでまた調べてきます…。

話題 BtreeがLockFreeになって喜ぶ人は案外少ない Btreeの部分ロックをDBの論理的競合解決に使ってる ロックがなくなったら上のレイヤーで競合解決しないと いけない たいてい性能が出ないとかなんとか…

Dynamic Software Transactional Memory 何千箇所でもCASだけで同時に！

Lock-freeはすごいけど・・・ CASだけで操作するのは疲れたよ・・・ 複数個所を一気に更新できたら簡単なのに・・・

Lock-freeには限界がある Lock-freeなデータ構造は単体で扱う分には 頑健で強固でスケーラブル! でも、あなたが欲しかったのは 本当にそれでしょうか？

あなたが本当に欲しかった物 トイレのカギを考えましょう この姿じゃ男子トイレ から出れない…！

あなたが本当に欲しかった物 今をときめく男の娘に必要なのは 「堅牢なだけのトイレの鍵ではない…！」 いくらデータ構造が強固でスケーラブルになって も実地で使えなければ意味がない…！ 「Composabilityがない」とも言う コードを使いまわせないのはソフトウェア工学の敗北 世の中のすべてのロックを 生まれる前に消し去りたい 過去と未来のすべてのロックをこの手で

そこでSoftwareTransactionalMemory 複数の操作をSerializableな分離レベルで実行 1ワードのCASのみを使う 単一ロックよりもスケールする タダ飯の時代の再来！？

SoftwareTransactionalMemory 外部からこのように見える場合を想定 A B

SoftwareTransactionalMemory 内部ではこのように扱う A Old New Owner Commit B Old New Owner Abort

SoftwareTransactionalMemory どういう意味か A Old New Owner Commit スレッドの ステータス B Old New Owner Abort

SoftwareTransactionalMemory ステータスは Commit （既に作業を終えた） Abort （一時的に作業を止めた） Active （現在作業中である） のどれかの状態をとる Commit状態ならNew )を読みだす! Abort状態ならOld Commit スレッドの ステータス Abort Active状態なら競合解決（後述）へ

SoftwareTransactionalMemory つまり これらが最新の値 A Old New Owner Commit B Old New Owner Abort

SoftwareTransactionalMemory A,Bの２つを一気に更新する事例 A B Commit Abort

SoftwareTransactionalMemory 自分のステータスを保存 A B Active Commit Abort

SoftwareTransactionalMemory Active CAS A Commit CAS B Abort

SoftwareTransactionalMemory CAS Commit Active A 最新の値 B

邪魔が入る場合 Active A B欲しい… Active B

邪魔が入る場合 Active Abort CAS A 最新の値 Active B Bを獲得！

どう凄いのか A B C D E 複数個所の最新情報 がCAS1回で変わる Commit Active Abort

／人◕ ‿‿ ◕人＼ 「その壮大過ぎる祈りを叶えた対価に、STMが 背負うことになる呪いの量が分かるかい？」

The Art of Multiprocessor Programming 読みましょう！ 略称TAoMP本

Transaction on Key Value Store 僕の修士論文(予定)

研究背景 Webサービスを支えるためにスケールアウト可能 なデータストアであるキーバリューストアが広く利 用されている memcached, flare, cassandra しかしキーバリューストアは一度に一つのキーバ リューペアにしかアクセスできない 複数のクライアントから並行してアクセスする際 に一貫性を保てない

キーバリューストアでのCAS すべてのキーバリューペアがバリュー値と共に uniq値を持っていて、書き換え時に更新される 1. Getsコマンドでuniq値を獲得 2. CASコマンドでuniq値を指定しながら保存 3. uniq値が一致した場合に限り保存が成功 成功なら1～2間で値が更新されていないことが 保証される アトミックな操作ができる

キーバリューストア上でのロック 並行制御を実現するための一番素直な実装 ロックを保持するキーバリューペアを用意 キーバリューストアのCASコマンドで可能 キー バリュー K V

ロックを実装すると 上手く動きそうに見える キー a b バリュー lock(a); lock(b); set(a, 1); set(b, 2); unlock(a); unlock(b);

ロックを実装すると クライアントが離脱すると破綻する タイムアウトでアンロックしてもデータが一貫しない キー a b lock(a); されたまま されたまま lock(b); set(a, 1); 離脱 set(b, 2); unlock(a); unlock(b); 永久にロック バリュー 永久にロック

提案 キーバリューストア上にトランザクションを実装 キーバリューストアには手を加えず、クライアントライブラ リとして実現 基本的性能や障害耐性はキーバリューストアの実装に依存 サーバが落ちても大丈夫な分散KVSなら信頼性も安心 クライアントが離脱しても大丈夫 トランザクションを用いて一貫性を保つ トランザクション キーバリューストア

基本方針 Dynamic STMを応用 メモリの間接参照の代わりに、キーバリューストア に間接化を導入 トランザクショナルキーバリューペアというデータ構 造を構築

キーバリューストアでの間接化 キーは文字列なのでバリューの中に挿入できる A キー バリュー A B B C B C

複数のキーを格納 複数のキーを格納する事もできる キー バリュー A ab|cd|ef ab value1 cd value2 ef value3

複数のキーを保持 以後はこのように図示 A ab cd ef value1 value2 value3

提案手法 ソフトウェアトランザクショナルメモリの一つで あるDynamic STMを応用 メモリの間接参照の代わりに、キーバリューストア に間接化を導入 トランザクショナルキーバリューペアというデータ構 造を構築

トランザクションナルキーバリューペア(TKVP) ◆ 通常のキーバリューペア(KVP)をトランザクションの ために拡張したもの key value 古い値 key Sde93A u40F... トランザクション ステータス 新しい値 oMel1di Ldsa... 8Yu4naplE2 saFASFD... old new status value value’ active

トランザクショナルキーバリューペア statusの値によって読み出し方を分岐 commited:Newの値を読み出す abort:Oldの値を読み出す active:競合を解決する(後述) key old new status value value’ commited abort active

トランザクショナルキーバリューペア(TKVP) キーバリューストアにはこのように保存される キー key Sde93A u40F... oMel1di Ldsa... 8Yu4naplE2 saFASFD... バリュー Sde93Au40F... oMel1diLdsa... 8Yu4naplE2saFAS FD… value old value’ new active status

トランザクショナルキーバリューペア key old new status value value’ commited commited 省略して表記

トランザクションの実例 トランザクションを用いて Transaction{ set(a, 1); set(b, 2); set(c, 3); } を実現する // a=1 // b=2 // c=3

トランザクションの概観 ステータスを初期化 初期化 必要なTKVPを更新 更新 ステータスをコミット へ コミット 成功？ yes 終了 no

初期化 自身のステータスをActiveとしてキーバリュー ストアに新たに保存する この際のキーはランダムな文字列を生成する Transaction{ set(a, 1); // a=1 set(b, 2); // b=2 set(c, 3); // c=3 } set(hoge，active) hoge active

トランザクションの概観 ステータスを初期化 初期化 必要なTKVPを更新 更新 ステータスをコミット へ コミット 成功？ yes 終了 no

TKVPの最新の値(おさらい) Statusの値によって最新の値が変わる a commited 4 8 commitedならa→8 a 最新の値 abort 4 8 abortならa→4

更新操作 TKVPの所有権を奪って Transaction{ set(a, 1); // a=1 set(b, 2); // b=2 set(c, 3); // c=3 } oldが「これまでの最新の値」 newが「これからの最新の値」 をそれぞれ指すよう書き換える ◆ commitedなら a old new hoge aaaa 4 ◆ CAS 8 abortなら 1 CAS a old new hoge aaaa 4 8 1 commited set(fEe09d, 1); cas(a，[old,fEe09d,hoge]) active abort 初期化時に保存 したステータス set(fEe09d, 1); cas(a，[old,fEe09d,hoge]) active

複数のTKVP更新 同一のトランザクションステータスを指すよう 複数のTKVPを書き換える Transaction{ 1 a } hoge CAS b c set(a, 1); // a=1 set(b, 2); // b=2 set(c, 3); // c=3 2 hoge CAS 3 hoge active

トランザクションの概観 ◆ ステータスを初期化 ◆ 必要なTKVPを更新 ◆ ステータスをコミットへ 初期化 更新 コミット 成功？ yes 終了 no

コミット ステータスがactiveであることを確認して commitedへ書き換える Transaction{ set(a, 1); // a=1 set(b, 2); // b=2 set(c, 3); // c=3 } cas(hoge, commited); hoge CAS Active commited

コミット 書き換えるステータスは必ずキーバリューペ ア一つ 一斉にnewの指している物が最新になる 1 a 個数制限 なし b c hoge 2 CAS Active commited hoge 3 hoge 最新の値

トランザクションの概観 ステータスを初期 化 必要なKVPをオー プンしながら更新 初期化 更新 コミット ステータスをコミッ ト状態へ 成功？ yes 終了 no

アボート コミット時にステータスがabortに書き換えられてい たらコミット失敗。トランザクションを始めからやり直 す abortに書き変わっているというのはどういう状況か hoge commited abort

トランザクショナルキーバリューペア ステータスの値によって読み出し方を分岐 commited:Newの値を読み出す abort:Oldの値を読み出す active:競合を解決する key old new status value value’ active

競合する場合を考える トランザクションhoge Transaction{ set(a, 1); set(b, 2); トランザクションfuga Transaction{ set(b, 999);

TKVPの所有者がactiveだった場合 所有者のstatusをabortへ書き換える トランザクションfuga TKVPを奪う a Transaction{ set(b, 999); hoge 8 aはロールバック b 1 cas(hoge,abort) CAS fuga hoge active abort リトライ CAS 7 最新の値 2 999 b欲しい bを獲得 active 続行

クライアントが離脱した場合 トランザクション途中で故障などによって離脱 したらいずれ誰かからabortされる。 CAS 離脱 abort active

性能測定中…

問題点 ゴミが増え続ける もともとDynamicSTMはGC前提 ゴミ commited active a b commited active commited active active c

解決策 双方向化により参照カウンタGC ここ実装途中 github.com/kumagi/kvtx2 a b commited active commited active commited active active c

Future Work 強い一貫性を実現できるのでKVS上にインデック ス用にBtreeを構成しても大丈夫 トランザクションと範囲検索ができればSQLだって捌け るかも CassandraなどのEventual Consistentな環境でもク ライアント側の論理クロックを付与すればいけそ う まだ絵に描いた餅ですが…

まとめ Lock-free Stack, Queue, List, Hashmap, SkipList, BtreeとDynamicSTMのアルゴリズムを解説 腑に落ちない所は懇親会で 実装の具体例は僕のGithubや懇親会で ブログ記事で読みたいネタがあったら懇親会で 分散環境に応用しようと取り組んでます