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