Ｆｆ

Ｆｆ

Ｆｆ

Ｆｆ

☆2クリック 研究背景についてお話します 負荷が動的に変動し、上限を見積もりにくいWebサービスのバックボーンを中心に、スケールアウト可能なデータストアであるキーバリューストアが広く利用されています ☆ しかしキーバリューストアには一つのコマンドで一つのキーバリューペアにしかアクセスできないため ☆ そのため、複数のクライアントから並行してアクセスする際に一貫性を保てないという欠点があります

なぜならキーバリューストアにはCASコマンドというものが実装されているからです。 まずキーバリューペアがバリュー値とともにユニーク値を持っており、キーバリューペアを書き換えるたびに暗黙に更新されます。 まずゲッツコマンドでユニーク値を取得し、そのあとそのユニーク値と共にコンペアアンドスワップコマンドを発行します。 ユニーク値が一致した場合に限り保存が成功するので、ここでの1と2の間で値が更新されていない事を保証できます。 一言で言うと、アトミックな操作が可能です。

並行動作を行うためにはロックを用いるのが一般的です、並行してアクセスしたいキーバリューペアに加えてロックを意味するキーバリューペアを用意することは簡単です。

そのコンペアアンドスワップを利用してロックを実装することは可能ですし、うまく動きそうに見えます。 キーaに対してそれを守るロックと、キーbに対してそれを守るロックをそれぞれ用意し、ロックした上でアクセスを行い、そのあとでロックを解除すれば、通常のように並行動作を実現することは可能そうにみえます

しかしこの方法ではうまくいきません。 ☆なぜなら、クライアントが操作途中で離脱する可能性があり、その場合にそのキーバリューペアが永久にロックされてしまいます。 また、タイムアウトでアンロックを行ってもデータが一貫しないため、修復のための仕組みが必要になります。 クライアントの離脱はよく起こる問題であるため、システムを構築する際はクライアントの離脱も考慮に入れて設計をする必要があります。

☆4クリック そこで、キーバリューストア上にトランザクションを実装する手法を提案します ☆キーバリューストアのクライアントライブラリとして実装するため、キーバリューストア側にはflareやkumofsやmembaseなどの一般的な実装をそのまま用いる事ができます ☆そのため、基本的な読み書き性能や障害耐性はベースとなるキーバリューストアに依存します ☆また、トランザクションの最中にクライアントが離脱しても破たんしません ☆そしてトランザクションを実現できれば、それを利用して複数のキーバリュー操作時にも一貫性を保つことができます

☆1クリック そこで☆メモリの間接参照の代わりに、キーバリューストアに間接化を導入しました その間接化についてこれから説明します

6クリック キーバリューストアはキー☆に対してバリュー☆を1対1で保存するだけの単純なデータストアですが、このバリューBはキーAに対応したバリューであると同時に、Bをキーとして参照することで新たなバリューであるC☆を参照できます。 この図ではわかりにくいので、これを☆以下のように簡略化して図示します☆ 茶色い四角がキーを表し、茶色い矢印がそこからの参照、オレンジ色がバリューを表します

2クリック キーはただの文字列に過ぎないため、シリアライズすることで複数のバリューを保持できます。この図の場合はab,cd,efの三つのキーが格納されているので☆それぞれをキーとして用いてバリューを3つ☆参照できます。 なお、この図はこのページ以降では

このように図示します。 あずき色の四角がキー、そこから伸びる茶色い矢印がキーバリューペアの対応関係を表します

その間接化を用いて、トランザクショナルキーバリューペアというデータ構造を構築しました

☆10クリック トランザクショナルキーバリューペアとは、通常のキーバリューペアをトランザクションのために拡張したものであり、 普段ならば☆キーに対してバリューを直接参照していたのに対し ☆トランザクショナルキーバリューペアでは☆このような構造をもってバリューを参照します。 ここではキーに対応するバリューとして新たに3つのキーを埋め込んだ物を保存しています。 この中でも ☆オールドというのは古いバージョンの値を示し ☆ニューというのは新しいバージョンの値を示し ☆ステータスはトランザクショナルキーバリューペアの所有トランザクションの状態を意味します ☆これらはキーバリューストアに保存される際にはキーとしてユニークな文字列を使用し、たとえばこのオールドのキーバリューペアはこのようなユニークな文字列をキーとして、バリューに値を保持します。 ほかの二つも同様ですが☆説明の都合上その文字列は表記しません ☆この図の中にあるトランザクションステータスですが

☆3クリック このトランザクションステータスによって、クライアントが読みだすべき値が変わります ☆コミッテド状態であればnewのキーバリューペアが指している情報を読み出します ☆アボート状態であればoldのキーバリューペアが指している情報を読み出します ☆アクティブ状態だった場合の挙動は後述します。

なおこのトランザクショナルキーバリューペアはこのような形でキーバリューストア内に保存されます。 キーに対してこのように間接化されたキーがバリューとして３つ保存され、それぞれのキーについてこのようにバリューが対応します。 なおこのトランザクショナルキーバリューペアは

なお、トランザクショナルキーバリューペアは以後このように省略して図にします この三つの四角は、左からオールド・ニュー・ステータスを示し、ステータスがコミッテド状態であるため、このトランザクショナルキーバリューペアはニューの指しているこの値が読みだされるべき最新の値となります。

さて、ここまでで説明したトランザクショナルキーバリューペアを用いてトランザクションを実際に行う様子を追ってみます。 ここで行うトランザクションは、aというキーに1、bというキーに2、cというキーに3を保存するトランザクションです。 これらをキーバリューストアの命令を用いて三つのトランザクショナルキーバリューペアを一括で書き換えます

これがトランザクションのフロー図です。 トランザクションはすべてこの流れに沿います。 まずステータスを保存することで初期化を行い 必要なトランザクショナルキーバリューペアを更新し ステータスをコミット状態へ遷移させる事でトランザクションが行われます それぞれのステップについて順を追って説明します。

☆2クリック まずトランザクションの初期化処理を行います☆ この処理では、自身のステータスをアクティブとしてキーバリューストアに新たに保存します。 キーとしてランダムな文字列を生成して利用します。☆ ここでは説明の都合上、ほげという文字列がたまたま生成された事とします。これによりこの一連のトランザクションをほげと呼びます。 キーバリューストアに対して行う操作はセットほげ、アクティブです。

次に更新操作を行います。この処理では必要なトランザクショナルキーバリューペアを更新します

☆3クリック さて、トランザクショナルキーバリューペアですが、これはステータスの値によって最新の値が変わるものです。 この図で見れば、上のaというトランザクショナルキーバリューペアは所有者がcommited状態であるため、newの値を読み出すことになり、aに対して8という値を読み出します。 下のaというトランザクショナルキーバリューペアは所有者がabort状態なので、oldの値を読み出すことになり、aに対して4という値を読み出します。

☆11クリック さて、更新処理ではトランザクショナルキーバリューペアを今の持ち主から奪って自分のものにします。 ☆これが先ほどのステップで保存しておいた自分のステータスです☆ まずここではセットA,1☆を発行して新たに書き換えたいキーバリューペアを保存します。 ☆ここでのキーバリューペアは前述したとおりランダムな文字列をキーとして使っています ☆次にキーエーに対応するバリューを書き換えます。☆前の持ち主の状態がコミッテドなので、もともとのニューが指していた値をこれからのオールドが指すようなにaのバリュー値を書き換えます。この2命令の発行で更新操作は完了です。 (ここまでで6クリック) ☆アボート状態のときも同様にして☆新しいバリューを書き込んで☆ トランザクショナルキーバリューペアの所有権とともにオールドがこれまでの最新の値、ニューが先ほど書き込んだキーバリューペアを指すよう☆書き換えます☆ 元々のトランザクショナルキーバリューペアの所有者の状態によって、これまでの最新の値が異なっている事に注意してください。オールドが最新の値を指すようにトランザクショナルキーバリューペアは書き換えられます。

☆5クリック 先ほどと同様の手順で、同一のトランザクションステータスを指すようトランザクショナルキーバリューペアを操作します。 必要なだけ☆トランザクショナルキーバリューペアを書き換え更新操作を行います。 ☆（一番下の分） これにより、a,b,cすべてのトランザクショナルキーバリューペアの持ち主がトランザクションほげになります。

最後にコミットを行います。

コミット操作では、ステータスがアクティブであることを確認した上で☆コミッテド状態へ書き換えます

☆4クリック 複数の値を操作するトランザクションでも、コミット時に書き換えるべきステータスは☆キーバリューペア一つです その書き換えにより一斉に複数のトランザクショナルキーバリューペアのnewが最新のコミッテドな値となります☆ ここでは所有しているトランザクショナルキーバリューペアの個数に依存せず1つのキーバリューペアに対する操作のみでコミット操作が行われている点に注意してください☆

ここまででコミットが成功していれば操作は終了しますが、失敗した場合は再びトランザクションをはじめからやり直します。

コミットに失敗する場合とは、ステータスがアボート状態に書き換えられている場合です。その場合は☆コミット操作は成功せずリトライを行うことになります。 では☆アボート状態に書き変わっているというのはどういう状況でしょうか。

これは先ほど出した説明の中で、アクティブ状態のトランザクショナルキーバリューペアをオープンしようとした際に発生します。

☆8クリック 例としてトランザクションが競合する場合を考えて見ます。 まずトランザクションほげが初期化を行い☆、トランザクショナルキーバリューペアのエー・ビーを書き換えたところで別のトランザクションが開始され☆初期化を行い☆トランザクショナルキーバリューペアビーに手を出した☆とします。その値は既にトランザクションほげが触っており、トランザクションほげがアクティブ状態なので、競合が発生します☆　ここではトランザクションほげが所有権を奪われる場合の操作を説明します☆

☆12クリック ここでトランザクションふがは☆bの値の獲得を試みるのですが☆既にbはトランザクションほげによって獲得され、そのほげがまだアクティブなためトランザクショナルキーバリューペアを横取りできません。☆ そこでトランザクションほげのステータスをアボートへ書き換えます☆書き換えが完了すると☆オールドが最新のコミッテドな値となるので☆ （ここまで6クリック） 先ほど述べた手順のとおり、新しく値を☆保存した状態でトランザクショナルキーバリューペアの情報を書き換えて所有権を獲得します。 ☆ここで、トランザクションほげがアボート状態になったことの影響で、☆保持していた値が自動的にすべてロールバックされます。 この一連の操作をへて、トランザクションふがは無事にbを獲得できます。 ☆このあとトランザクションほげはコミット前に自身がアボート状態に陥ったことに気づきリトライを行います また、☆トランザクションふがは無事に自分の操作を続行できます。 オープンしようとしたトランザクショナルキーバリューペアの所有者がアクティブだった場合には☆そのトランザクションの所有者の状態をアボート状態に書き換えます☆ それによりそのトランザクショナルキーバリューペアのオールドの指している値が☆ダーティーでない最新の値となるので☆、通常のオープン操作で☆トランザクショナルキーバリューペアを獲得できます。 ☆なお実際には即座にアボートさせるのではなく、タイムスタンプやバックオフでの待機時間を目安にアボートさせますが省略します

クライアントがトランザクションの途中で離脱した場合、アクティブなステータスのまま停止するので、他のトランザクションによりいずれabortさせられます。これにより編集途中のダーティなデータは削除され、ロールバックされます。

冬のLock-Free祭り DSIRNLP @kumagi

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

僕を呼ぶ声が聞こえる！

僕と一緒に Lock-free!

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

CPUの製造の話 シリコンウェハにチップを物凄い精度で現像 ウェハを長方形に切り分ける パッケージングして足をつけてできあがり！ 30cm ウン万円する！

CPUの製造の話 製造のボトルネックになるのはウェハの価格 チップが小さい方が1つのウェハから沢山作れる 小さいチップのほうがより成功率が上がる

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

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

それ活かしてパワフルなの作れば？ 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; xを読み出す 読んだ値に +1 xを保存する

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

スレッドB スレッドA Lockを用いないとどうなるか 複数スレッドが同時に行うと破綻する場合がある xを読み出す(1) 読んだ値に +1 xを保存する(2) x==1 xを読み出す(1) 読んだ値に +1 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)); } 失敗してたらやり直す

スレッドB スレッドA CASを使ってみよう CASのお陰で衝突しても破綻しない xを読み出す(1) 読んだ値に +1 値が1なら2へCAS 失敗したので再挑戦 xを読み出す(2) 読んだ値に +1 値が2なら3へCAS x==1 xを読み出す(1) 読んだ値に +1 値が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) ？？？

余談 期待した値ならばそのままSwapを発動してしまうので交通事故が発生する 一致を期待しなかった場面で運悪く一致するとか いわゆるABA問題

余談 CASの類似品のLL/SC命令 Load-Linked, Store-Conditional LL命令でデータを読み出し SC命令でデータを書き込む ここの間で書き換えが起こっていたら値が一致していようがSCに失敗する

余談 LL/SC命令 ABA問題を回避するために作られた命令（MIPSなど） 実際はキャッシュのフラッシュや問題ないスレッドのコンテキストスイッチなどなどのせいで書き換えられていないのにSCが失敗する場合がある PowerやAlphaやMIPや一部のARMにしかないので大半の人は使う機会がない

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

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

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

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

Lock-free Stack Head A B D CAS

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

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

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

Lock-free Queue の Deque Head Tail

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

Lock-free Queue の Deque Head Tail CAS CAS

Lock-free Queue の Enque Enque操作 Enqueしたい要素eを用意する 末尾のノードが指すポインタがeを指すようCAS Tailポインタがeを指すようCAS

Lock-free Queue の Enque Head Tail CAS CAS

要素eを用意する 末尾をCAS TailポインタをCAS Lock-free Queue の Enque Head Tail CAS CAS 構造が破綻 CPU1 要素eを用意する 末尾をCAS TailポインタをCAS CPU2 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 CPU2 CPU3 CPU4 CAS CAS CAS CAS CAS CAS CAS

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

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

Tailが末尾を指さないとは？ 末尾を指してる Head Tail Head Tail 両方の状況を想定して処理を記述 末尾を指してない

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

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; } } } }

大事な考え方 CASの前後で状態が遷移していること Tailが間に合ってる状態と遅れてる状態の2つを許す それぞれのステートに対して全操作を定義する Mステート×N操作パターン書けば大丈夫！ なんでもイケそうな気がしてきましたね どしどし行きます

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

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

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

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

あなたも一緒に Lock-free!

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

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

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

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

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

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

楽観的ロック だめなんです Head 私の安定性…低すぎ… これ消すぞー 消したぞー ロックを2つ取って おりゃ！ これ消すぞー！ 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 固定数のLockをmoduloでバケットに割り当てる スレッドの数が膨大にならない限りロックそのものが増えても恩恵がないため バケットごとに対応するロックが縞模様になるのでStriped 0 1 2 3 4 5 6 7

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

Lock free?

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

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

バケットの拡張が 困難

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

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

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

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

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

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

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

驚異的なスケーラビリティ 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 8 12 16 29 33 51 64 -∞ ∞

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

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

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

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

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

さあ Lock-freeだ

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

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

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

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

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

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

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

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

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

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

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

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

Lock-free!

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

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

Lock-free化 必要なデータをすべて複製してしまえばいい SplitやMergeも全く同様。部分木を丸ごと作り直す 衝突したらそのスレッドは初めからやり直し すべての操作はRootに対するCASで直列化 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 B Commit Abort

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

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

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

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

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

Active A B CAS CAS SoftwareTransactionalMemory

Active A B Commit CAS 最新の値 SoftwareTransactionalMemory

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

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

Active どう凄いのか 複数個所の最新情報がCAS1回で変わる

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

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

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

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

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

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

ロックを実装すると 上手く動きそうに見える 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); a キー バリュー b 永久にロック されたまま 永久にロック されたまま 離脱

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

性能測定中…

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

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

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

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