omidとMegastoreのトランザクション戦略の違いなど

Hideyuki Kawashima @h_kaw

@kumagi @oza_x86 申し訳ございません．当方，データストアは初心者ですので，このような重要なお話に的確にお答えできません．ちょっと調査してみます．後日お返事させて頂きます．ストリームならわかるのですが．．．

Hideyuki Kawashima @h_kaw

@oza_x86 @kumagi そうですね．2PCはスケールしませんね．Megastoreの方式は直感的ですのでスケールすると思います．この技術のポイントは，EGの効率的な作成手法と，複数人のEG共有に関する制御でしょうが，論文では見事に隠蔽されていますね．さすがはG社です．

oza @oza_x86

@h_kaw @kumagi 2PC は規模一定でリクエスト数が増加すると衝突確率が上がってスケールしませんが，超大規模かつデータが増える一方という条件下であれば衝突確率が下がってスケールすると理解しております．

Hideyuki Kawashima @h_kaw

@oza_x86 @kumagi なるほど...そういう解釈もありますね．ただノード数をkとし，データが全ノードに分散されている時，kの増加につれて性能は劣化するかと思います．理由はメッセージ数が単調増加するからです．評価指標次第かと思います．

くまぎ @kumagi

@oza_x86 @h_kaw はい、パフォーマンスについては仰る通りだと思うのですが、書き込む側と書き込まれる側が同一でない場合には書きこむ側がprepareさせたままとか中途半端にcommitを発行したまま音信不通になったりするわけでしてそこをどうするのかと。

Hideyuki Kawashima @h_kaw

@kumagi @oza_x86 とても素敵な御研究ですね．素晴らしい成果を期待させて頂きます．直列等価性は view等価性をやはりお使いかと存じます．kung-robinsonは効率が悪いので，いつかその辺りぜひご教授頂けたら幸いです．

くまぎ @kumagi

@h_kaw @oza_x86 あまり深く考えていないのですが今の僕の研究ではview等価なスケジュールを許容している気がしないので改良したいところです。競合の方も「厳格」まで逃げてるので、これを「回復可能」まで緩めればスループット上がりそうとか思ってるところです。

くまぎ @kumagi

@h_kaw @oza_x86 そして大変泥縄ですがkung-robinsonをググりました。僕の研究はDSTMが素ですが、kung-robinsonはSTMの中でもTL2っぽい流れですね。こちらはview等価なスケジュールを許容するのでしょうか？

Hideyuki Kawashima @h_kaw

@kumagi @oza_x86 kung-robinsonはおそらく最も単純なOCCかと思います．validation phaseでconfilct-serializabilityに基づくラフな競合検出を行います．ラフすぎるのでちょっと頭に来ます．

くまぎ @kumagi

@h_kaw @oza_x86 ひょっとして、北川先生の本の8章のタイムスタンプのところの「楽観的な競合解決手法」のところで紹介されているものでしょうか…リードセットとライトセットの∩がφとかそんな説明に見覚えが…

Hideyuki Kawashima @h_kaw

@kumagi @oza_x86 こちらの本の17章になります．初歩的な話で申し訳ありません．当方余り詳しくなくて．．． http://t.co/xsCxwZgi

拡大

Hideyuki Kawashima @h_kaw

@h_kaw @kumagi @oza_x86 view等価になるか，相当調査不足なため，わかりません．勉強して出直してきます．ただ，KLは弛緩に過ぎるので，極限への性能向上を考えたいと少し思ったりも致します．

くまぎ @kumagi

@h_kaw @oza_x86 極限への性能向上というのは、トマスの書き込み規則のような「writesetとreadset被ってるけど問題ないパターン」をきちんと許容するようにする、などといった事を指すのでしょうか？データベースが無学過ぎて申し訳ないです。

Hideyuki Kawashima @h_kaw

@kumagi @oza_x86 Thomas write ruleは一般的な規則ですよね．OCCのvalidation phaseにアプリの情報を導入することで，ある種のアプリにおいてはどこまで緩和可能であるか，多少興味がございます．緩和する程性能が向上することは自明ですので．

くまぎ @kumagi

@h_kaw @oza_x86 それと、view等価か競合等価かはともかくとして、回復可能・連鎖アボート回避・厳格という分類で言うと最後にまとめて競合解決を行うという点でこれは厳格へ分類されるのでしょうか。

Hideyuki Kawashima @h_kaw

@kumagi @oza_x86 「厳格」の意味を当方無学にてわからないのですが，recoverable scheduleのためにはcommit順序を制御する必要はあるかと思います．

くまぎ @kumagi

@h_kaw @oza_x86 「厳格」というのは北川先生のhttp://t.co/MYkTpjoo に書いてある物と同じで「書き込みを行なってからコミットまでの間に割り込まれない」です。文中ではもう少し厳密な表記でしたが。

拡大

Hideyuki Kawashima @h_kaw

@kumagi @oza_x86 成程．．．勉強になります．ありがとうございます．OCC自体と「厳格」は独立した概念ですね．OCCのwrite phase(last phase)にて「厳格」が適用されるならば，スケジュールは recoverable かと思います．

くまぎ @kumagi

@h_kaw @oza_x86 はい、本の中にも、厳格ならば必ず連鎖アボートを回避する上に回復可能である、と明記されております。逆は必ずしも成り立たないらしいですが。

Hideyuki Kawashima @h_kaw

@kumagi そういえば，DSTM, OSTMに関する書籍へのポインタなど頂けましたら大変嬉しく思います．当方無学にて勉強したいと考えております．

くまぎ @kumagi

@h_kaw DSTMは Software Transactional Memory for Dynamic-Sized Data Structures です。英語がバリバリ読めるのならおすすめです。ノンブロッキングSTM界に多大な影響を与えた論文です。

Hideyuki Kawashima @h_kaw

@kumagi ありがとうございます．英語は苦手ですが，頑張って取り組んでみたいと思います．すみません，そろそろ体力の限界ですので，本日は失礼します．貴重な情報，どうもありがとうございました．お礼申し上げます．

くまぎ @kumagi

@h_kaw あ、英語が苦手なら僕のhttp://t.co/1GN9FEIO とか、これから書こうかと思っているブログ記事を見ていただけるとわかりやすいと思います。他にDSTMを日本語で解説しているものを見かけないのです…

くまぎ @kumagi

@h_kaw いえ、こちらこそ大変勉強になりました。またいつでも声を掛けてください！

くまぎ @kumagi

@h_kaw OSTMは、DSTMでのコミット完了後のデータを読みだす際にも3回の間接参照が必要な事を問題視し、コミット完了後にCASにて間接参照を1回にする（というか通常のポインタ参照にしてしまう）というアイデアなのでDSTMが分かれば理解はすぐです。