MemoSTM関係のことをメモっていこうと思います。この広告は、90日以上更新していないブログに表示しています。2013-05-13セマンティクスは全人類を救うこの記事は安ワインを煽りながら勢いで書いたので一切の正しさを保証しません。分散システムで良く出る課題として障害耐性がある。性能を増やしたい→台数を増やせばいい→一台でも壊れたら全体が死ぬので脆弱になった→一台死んだぐらいで全体が死なないような仕組みにしろ→複数台でデータを複製するしかないという変遷は自然で、ここから一歩踏み出そうとして大量の屍が量産されたのがここ50年ぐらいの歴史。逆に言うとここまでは50年以上前には到達していて、その50年で何も成果が無かったわけじゃない。中でも大きな成果だと思っているのがLinealizablityの定義。これは分散システムに対して結局のところ人類が何を望んでいるのかを明文化した点で大きな貢献があった。僕の覚えている定義はこう。クライアントが要求した順番とシステム内で実行される順番は等しい。クライアントが要求を発行した全順序と系を跨いだ実時間での半順序も等しい(全順序)行われた操作の引数と戻り値の組の羅列はシステムにとって等価な逐次実行順序を持つ。CPUを相手にした場合とは定義が異なるので要注意。ここでポイントなのは、これらは一切実装には言及していなくて、システムが外からどう見えれば良いかを表現している事。何らかの実装を行なったシステムが吐き出す半順序の実行順が、どうにかしてこの法則を守っていれば良い。推理ゲームでよくあるような、例えばマラソンを題材にして「AさんはBさんより先にゴールした」「CさんはBさんに一度も抜かれなかった」「Cさんはスタートから一人も抜いていない」という証言からA,B,Cのゴール順を考えつくという題材のように、複数のスレッドが実行を終えた際に、それぞれのスレッドが何をして何を得たかを突き並べ、一つでも納得のいく実行順序が常に出てくる事を保証できるならLinealizable。複製環境でそれを実現するだけならReadとWriteでギチギチに同期で固めれば可能。パフォーマンスは出ない。Consistencyなんだけど説明めんどいので簡単に言うと。Writeを非同期にした上で操作の追い越しをアトミックブロードキャストプロトコルなどで禁じれば簡単に一例は実現可能でそれなりの実用性はあるが系を跨ぐと死ぬ。系を跨いだ全順序性を消したので当然だ。これらが何故尊いかというと、複製を作った場合のセマンティクスの変化に影響されないからだ。linearizableとか呼んだりする。ユーザーに複製を意識させないというのはシステムの複雑さをその段階でシャットアウトできるし、ロジックの開発性や移植性に優れる。尊いのは、そこからパフォーマンスを高めようとして何かを妥協すると即座にその防壁が無くなる事を世に知らしめたからだ。Consistency(ユーザーは複数の一貫性のない値を読んでアプリケーションのレイヤーで対応する必要がある)なんかが提案されている。これらは並のプログラマが書くべきものではない。Writeを対象として一貫性を守ろうとすると直ぐにパフォーマンス的な障害にぶち当たり、パフォーマンスの壁を乗り越えようとするとプログラムの記述が複雑になったりアプリケーションのレイヤーに食い込んで来たりするということ。いうハイパフォーマンスな並行システムに於いては先人が居る。CPUは酷く強烈な高速化の圧力に押されて新しい手法の開発に延々と駆られて来た。操作のパイプライン化やスーパースカラー、それに伴って必要なデータのフォワーディングなどあの手この手で高速化をこなしてきた。その高度に非同期並行化していく中でもメモリ操作の非同期化という壁にぶち当たった時に至った答えであるメモリバリア命令とJMMという拡張は慧眼だと思う。(実際の順序は全く違うと思う)プログラム言語のレイヤでコンパイラがそのreleaseやacquireの必要な箇所を洗い出し、プログラムのセマンティクスを壊さないようにしながら、最大限の並列化を行えるように多くの複雑さを隠蔽した。後は起動さえ速くなれば言うこと無いのに。Writeにそれを満たさせるのは効率悪いしReleaseとか書きたくないよね!マルチバージョンされたのをどうにか訂正するのなんて最悪だ。Writeなんか忘れてもっと粗い粒度で物事を考えなよ、俺が裏でよしなにしとくからさ。あ、これvolatileだからよろしくね」という形で歩み寄ったJVMのアプローチは本当に慧眼だ。Writeのセマンティクスからユーザーをひっぺがした例としてSQLがある。これは本当に成功しているのだけどまだ一つのクエリがさほど並列化されない物も多く、最近日立と東大とで「IOを非同期化して1000倍高速化」と言っているのでやっとそのあたりが実装されつつあるという感じに見える。Writeを包む並行性の為の粗粒度化としてvolatileより素敵だと思う。Writeの為にLinealizableな一貫性制御は行なっておらず、個々の読み書きではEventualに行い、トランザクションの単位ではそのEventualな部分が見えないように括っている。SQLより下のレイヤーはSQLを使う限り見なくていいし、ユーザーからはSerializableだかSnapshotだかの分離レベルでしか物が見れないので問題にならない。Isolationという分離レベルがよく使われていて、高い認知度がある。Isolationは複雑な非同期実行をセマンティクスの向こうに追いやるのには最高の隠れ蓑として機能することが期待される。この流れは分散システムがこの先進むべき道を示しているようにも見える。簡潔に言うと、もっと粒度の粗いセマンティクスを考案して、より多くの複雑性をその向こうに追いやる事こそが最高のパフォーマンスを合理的に得る手段だという事。その粗いセマンティクスの一つが機械学習だと思っているし、その点に素早く目を付けた0xdataのH2Oは本当に凄いと思う。SQLを超える何かもたぶん近いうちに誰かが思いつくと思う。今SQLで書くときにみんなが腐心するデザインパターンが予め組み込まれて心配無用な何かになるんじゃないかと期待している。Consistencyより更に緩い(そして更にパフォーマンスの出る)何かもその中に追いやって複雑性を隠蔽できるかも知れない。逆に進むべきではない道は隠蔽する気のない複雑なセマンティクスをユーザーにそのまま押し付けるようなシステムだ。最終的にどんな粒度の処理の向こうにその複雑な手続きを追いやればいいかを考えずに、局所的な書きやすさや局所的なパフォーマンスを追求する研究は筋が悪いと感じる。セマンティクスの清廉化より先に、汚いセマンティクスをユーザーに押し付けた上でその裏の最適化手法を考えてもその成果が生かされる道は遠い。僕がdisらなくてもそんな研究は「哲学がない」などと揶揄されるのだけど。先人たちの屍は無駄ではなかった。いうか僕が最近気づいただけでコンピュータ業界でも偉人と言われる人たちは30年以上前からこの点に気づいて居たのだと思う。Spanner」の実力は?』についてこんな記事が目に入った。その4引き続き分散システムのデザインパターンの話をしていく。月別アーカイブはてなブログをはじめよう!kumagiさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。