SILO再考〜次世代DBのアーキテクチャとして

大分たってしまったけど、ようやく時間が空いたので、db tech showcase Tokyo 2016 http://enterprisezine.jp/dbonline/detail/8466 で話した内容を記録的に書いておく。あとはSILOの解説を特に自分用に論文の4章を中心に整理しておく。あとはついでに自分の思うところも記す。

・SILO
元論文はこちら、執筆陣はMITのLiskov一派とEddie Kohler　現在のDB研究の第一線のメンバー。
http://people.csail.mit.edu/stephentu/papers/silo.pdf

SILO以降、大きくDBベースのアーキテクチャの考え方は変わりました。ほとんど全ての分散系OLTPはSILOを程度の大小はあるとはいえ、意識していると言っても過言ではないでしょう。前世代ではほぼ「空想か？」ぐらいの扱いだった分散transactionはほぼ現実のソリューションになっています。個人的には、ここ数年の既存RDBMSとNoSQL系のどっちが上か論争にほぼ決着がついたと思っています。というよりも論争自体が無効になったのが現在でしょう。今後10年で既存DBのアーキテクチャはほぼ全てSILOの「考え方」を採用したアーキテクチャに席巻されると思います。それは現在のRDBMSの延長でもないし、NoSQLに青息吐息でACIDを後付けで放り込んだNewSQLでもありません。

商用のメジャーなDB,例えば、Oracle SAP(HANA) SQLServer と言ったDBも大きくそのアーキテクチャ変えると思いますというか、現実にその辺を大きく変更する趣旨の論文が多数出そろいつつあるので、もう既定路線でしょう。SAPあたりについては、（DB屋から見ると）ほぼそこまで言うかレベルでの声明まで出しています。また、既存OSS系のRDBMSもNOSQL系も、流れとしてはSILO的な考え方に追随しなければ、パフォーマンスで文字通り圧倒的に遅れをとるし、そもそもメンテナビリティでも差がつきます。対応は不可避でしょう。

DBの製品群でも、入れ替わりが起きるでしょう。どのDBにとっても、ほぼアーキテクチャの完全な変更になるので、資金のないOSS系は対応できずに、むしろ新しくスクラッチで作られたOSSの分散OLTPにその座を明け渡すでしょう。既存プロプラ系DBはもうこれはどれだけ優秀な人材と金を突っ込めるかの勝負になります。

なぜか。非常に理由は簡単です。

理論的にSILO系の「やり方」は、今後のハードウェアのアーキテクチャの進化の流れと軌を同一にしており、そのパフォーマンスを最大限に引き出すことができるからです。言うまでもなく、ソフトウェアとハードウェアは車輪の両輪です。片方が釣り合わない場合は、前には進まず、そのまま同じ場所をぐるぐる回りつづけます。

コンピュータ業界における今世紀の最大のトピックは、クラウドでもAIでもIoTでもありません。ムーアの法則が限界に、それこそ物理限界につき当たったことであり、その代替手段の「発見」が文字通り時間切れになったことです。

結果として、コア出力は上がらないため、メニーコア化に拍車がかかっています。ごく普通に1サーバあたりの物理コア数が100近いマシーンが、秋葉原で簡単に買える時代に入りつつあります。HTであれば普通に200threadで、5台もスタックすれば、1000threadでの同時処理が可能です。これに加えてメモリーの高密度化が進んでいます。普通に数Tのメモリーも手に入る時代になりつつあります。メニーコア化とメモリーの大容量化は、当然ながらバスの高速化を要求します。コア間・メモリー・disk・NWのほぼ全てのバスで高速化が進みつつ有ります。

今までのコア数は4コアや2コアが標準でしたが、一気に桁があがります、サーバ単位で見たときには、場合によっては2桁変わる。一般にITは「桁が変われば、アーキテクチャを根本的に見直した方がよい」といわれますが、SILOはその典型でしょう。OracleでもSQLserverでもMySQLでもPostgresでもDB2なんでもいいのですが,今までの既存のDBでは、100コアどころか20コア行かないぐらいでパフォーマンスが、特にwriteの競合がある場合は飽和します。これは、既存のDBの作りがまずい、ということではなく、単純に環境の前提がそもそも違うからです。大量の分散並列処理＋大容量のメモリーは前提にしてないどころか、そもそも想定外です。

くまぎー先輩(そういうば最近無駄にロックフリーって言わなくなりましたな。)のスライドがよく出ていると思うので張っておきます。
http://www.slideshare.net/kumagi/ss-64459138

要するに今までのDBは「コア数は少なめで、というか基本一つで、メモリーは高価でサイズが小さく、できるだけ効率的に使いましょう」という、ハードウェアに対するスタンスが前提になっています。（なので、例えばundo logもdiskに書くという結果になりますね。この一点をとってしてもSILOの方がパフォーマンスもメンテも全然優れていると思います。）

SILO以降の分散DBは、理論的な裏付けとして、今までのRDBMの良質な蓄積を完全に養分としており、別に奇をてらった戦術を駆使しているわけではありません。今までの理論を踏襲すれば、「そりゃそうだわね」という感じで腑に落ちる考え方です。仮に、DBに「進化」という表現を当てはめるのであれば、まさに「環境変化に対する適者生存」という言い方がフィットすると思います。

ということで Section 4 の design から説明しますよ的な。

前書きはともかくここで分かっておけば、なんとかなる（とはいえ、いろいろ論文を通すために端折った部分が有り過ぎなので、その辺は実装みるなり、他の論文（例 Masstreeの詳細）を読んでください的なアレになっている。なんかたくさん書きすぎると査読が通りにくいそうで。大丈夫かアカデミア。）はず。たぶん。

SS４は以下の順序
4.1 Epoch
4.2 Transaction IDs
4.3 Data layout
4.4 Commit protocol
4.5 Database operations
4.6 Range queries and phantoms
4.7 Secondary indexes
4.8 Garbage collection
4.9 Snapshot transactions
4.10 Durability

SS4の前にSILOの前提を書いておく
1.型付きの命名されたレコードを管理。
要するにちゃんとしたDB。

2.one-shot requests
処理のwindowがあるということを意味する。すなわち、clientまで「常に状態を返し続ける」ということではない。serialization pointが存在できる可能性の一つの前提を提供している（overlapが永遠に続くわけではない）

3.MassTreeを利用
PKのindex treeで基本はB+。ただし、secondary keyは別treeになっている。したがって、secondary keyを利用する場合はtree traverseが二回になる。
「Each Masstree leaf contains information about a range of keys, but for keys in that range, the leaf may point either directly to a record or to a lower-level tree where the search can be continued. 」

4.requestの処理は各コアが担当
indexは共有メモリーを利用。

以下、解説的なメモ

4.1 Epoch
ほぼ動作単位のすべての基本になる。
・Global Epoch
全体の進行統括するepoch。Global Epoch Number(E)が設定される。管理threadがある。一種のバリアと機能する。SILOでは単位は40msec。

・各worker threadがlocal epoch(ew)をもっている
基本的にEを取得してセットするので、当然、Global Eよりは遅れる（ことがある）。GCのタイミングの判断として利用している。invariant: E-ew＜=1であり、すなわちepochで1単位以上遅れることはない。ローカルが進まないとEが進まない。なので、なのでロングtxの処理中はewをリフレッシュする必要がある。一種のグループコミットの「単位」として機能させる。コミットプロトコルのところで再解説する。

4.2 Transaction IDs
tx-IDはとにかくいろいろkeyになる。version check, lock制御, conflict検知とか。基本的にユニーク保証が必須なので、発行がボトルネックになる。のでいろいろ工夫する。

・分散処理でのtx-IDの割り当て
各workerでtxのcommit可能確定「後」に
　a.発行されたtx-IDよりも大きな値
　b.自身が選択したtx-IDよりも大きな値
　c.単一GlobalEpoch内部に閉じていること
以上の条件を満たすIDが選択される。

tx-IDの発行は単調増加「だけ」でよい。（分散処理可能）。たとえばr-wの検出だけなら、t1：read(x)→t2:write(x)のanti-dependencyの場合、t1<t2 t2<t1 の両方のID順序が発生する。なので、別にserial orderとtx-IDのorderが常に一致する必要はない。ただしepochまたぎは順序保証（serial orderと一致する必要がある）（尚、普通にt1：write(x)→t2:read(x)でserial orderが t1→t2ならTx-IDも t1→t2が必要）が必須。

4.3 Data layout
・以下の三つから構成されている
抽象化されたtxの各レコードは以下通り
TID : Transaction ID
Previous-version pointer : snapshot transactionで利用（後述）
Record data : 本体

本体については割と普通だと思う。普通にtupleを格納するpageモデルで、普通にin-placeなんで、RDBと同じスタイル

4.4 Commit protocol
外観：
Data: read set R, write set W, node set N, global epoch number E

// Phase 1
for record, new-value in sorted(W) do
lock(record);
compiler-fence();
e ←E; // serialization point
compiler-fence();

// Phase 2
for record, read-tid in R do
if record.tid != read-tid or not record.latest
or (record.locked and record !∈W)
then abort();
for node, version in N do
if node.version != version then abort();

commit-tid ← generate-tid(R,W,e);

// Phase 3
for record, new-value in W do
write(record, new-value, commit-tid);
unlock(record);

・個人的な解説：
4 phase approachで、これはほぼ業界デファクトっぽい。論文はcommitだけなら3 phaseに見えるが、実際はglobal epochでのphaseがあるので、4 phaseと見た方がよいと思う。今のところコレ以外のアプローチは、この手法のバリエーションしかない（気がする）。以下、順番に解説

Phase 1
[Write lock]
for record, new-value in sorted(W) do
lock(record);
compiler-fence();
e ←E; // serialization point
compiler-fence()

write setのロック処理
基本的にserializationは、2PL方式で処理する。ただしreadロックは取らず、2PLのread lockに相当する処理はversion checkで代替する。read lockを取らないので、OCCになりreadはブロックしない。fencingしてちゃんと同期する（epochの取得）。one-shot requestなので、epoch確定処理でserialization pointを決定する。同じくfencingしてちゃんと同期する・・論文では二回やってるがなんかこの辺fencingは一発でいんじゃないか？説あり

Phase 2
[Validation]
validationはread setのロック処理と同等の処理を行う。
for record, read-tid in R do
if record.tid != read-tid or not record.latest or (record.locked and record !∈W)
then abort();
自分の持っているread setのtx-IDが既に最新ではない（どこかで更新が入っている）か、または、そもそも自分のwrite setにはかぶっていないけどロックが取られている場合（他でロック）は abort。

for node, version in N do
if node.version != version
then abort();
treeのノードからphantomのチェックを行う（後述）

commit-tid ← generate-tid(R,W, e);
コミット用のTx-IDの発行

Phase 3
[Pre-commit]
for record, new-value inW do
write(record, new-value, commit-tid);
writeの書き出し

unlock(record);
lockのリリース。phase4が存在するので、いわゆるearly lock release。この辺がいろいろスタイルが存在する。最終的にcommitの永続化や、H/Wの想定性能も考慮して決まっているように見える。

Phase 4
[Durable commit]
■明示的には論文には書いていないが、・・・PersistentのPhase Durableのセクションより

・When a worker commits a transaction, it creates a log record consisting of the transaction’s TID and the table/ key/value information for all modified records.
とりあえずcommit時の全部ログは持つ

・This log record is stored in a local memory buffer in disk format.
ただし、それはメモリー上（なんで消える可能性あり）

・When the buffer fills or a new epoch begins, the worker publishes its buffer to its corresponding logger using a per-worker queue,
bufferがヤバイか、epochを進めるときに書き出す

・and then publishes its last committed TID by writing to a global variable ctidw.
んで、自分の担当分の最終commit tx-IDを発行（ここで完了）

■基本的にepochベースのグループcommit（に近い）
one-shot requestが前提。validationでcommit可能であっても（というかcommitなんだけど）durable（すなわちlogが終了するまでは）になるまではclientにはcommitは返さない、加えて、loggingが終わるまではsnapshotのinstallは行われない。なので、実際はcommitableなんだけど、読ませないので、SIとしてはちょっとだけstaleになる可能性がある。というか、これgroup commit系には必ず発生する問題にはなると思う。
client(というかapplication)的には、そもそもcommitが見えてないので、group commitでこけた場合は、handlerとしてはabortとして処理できる。この時、残っているのはredo logなので復旧が超っぱや。これはすごく重要。尚、個人的にはこれは事実上のstaleとのtrade-offになっていると思う。・・逆に言うとこれは、アプリサイドにはあんまり選択の余地はない。
あとは、結果、基本snapshotについてはreplicaになるので、どーやってlog shipするかは結構マニアな課題になると思う。

■このcommit protocolはserializableなのか？
普通に2PL。
We verify in Phase 2 that the record’s TID has not changed since its original access,and that the record is not locked by any other transaction.This means that S2PL would have been able to obtain a read lock on that record and hold it up to the commit point.
よって、普通にS2PL（と理論的に同等）

■分散処理だが、barrierはどうするのか？
epochで処理するという理解でいいと思う。phase1でepochの状態をfensingする

4.5 Database operations
Read/Write
省略〜前述のcommit protocolでほぼ説明可能

Delete
Snapshot txでtreeをたどるときに必要なので、論理削除は可能だが、物理削除はできない。absentフラグを設定する。ただしGCの当然、問題になる。

Insert
commit protocolの「前に」先にinsert処理をしておく(treeに追加）。その直後のcommit protocol のread setとwrite setに加える。この辺が特にphantomの除去について妙技になっている。(後述)

4.6 Range queries and phantoms
Siloではrange queryもサポートしている。ということで当然phantomもクリアしている。基本的にはNext-key lockingで対応しており、割と古典的な手法を使っている。最初になかったヤツが現れる場合は、確かにNext-key lockingは割と行ける。が。最初に有ったヤツが消える場合、すなわち、readでヒットしているケースだが、ここでlockはreadロックになるので無理・・・なのでNext-key lockingはそのままではまずいわけですね。SILOでは、treeのnode自体にversionを持たせて対処する。read setに対応する node setを持たせる。これでversionを確認するわけよ。

これはinsertでの structural modificationにも対応できる。insertはcommitの前に行われる・・ので、node setにcommit protocolに加える処理をする。すなわち、node setのversionが更新して、abortさせる(phantom)

■Node-setでの制御
「これは割とイマイチな気がするのは多分俺だけじゃない」ということでいろいろ議論になっている気がする。treeの制御がやっぱり面倒な感じがするので、パフォーマンスが結構アレな感じになる（と思う）。特にDelete系は鬼門に見える。

結構、tree制御とcommit protocolが割と密接に絡んでいるのは、ひとつの特徴とも言える。個人的にはあんまり美しくないと思うけど・・・とはいえ、現実解としては優秀とは言える

4.7 Secondary indexes
普通に対応している。省略
まぁ実装は面倒だと思う。論文はあんまりまじめに書いてないけど、実際は結構大変だと思われる。「Secondary key は別treeになっている。したがって、それを利用する場合はtree traverseが二回になる」（再掲）この辺はもういいのではないでしょうか的な展開になっている。まじめに書いてない。（多分書けるけど書くと査読がうるさいという理由だと思われる）

4.8 Garbage collection
発生するgarbageは以下。
・tree node（B+)
・record
GCについては、RCUで、epochベースでのreclamation スキームを導入している。参照カウントだと全writeが共有メモリーにアクセスして厳しいので使わない

たとえば・・・
削除（別にrecordでnodeでもよい）実行する場合
・対象とreclamation epochをコア毎に登録
・reclamation epochを経過したらごっそり消す
例としては、各ローカルのepoch numberで考える。epochの進み方から e<=min ew-1なるeをtree reclamation epochと想定してGCする。

4.9 Snapshot transactions
Read-only snapshot transactionを想定。
とりあえずconsistent snapshotを取る必要があって、この時の考慮点はconsistencyとreclamationになる。（consistent snapshotはいわゆる分散環境下のconsistencyのこと）両者に対してはSnapshot Epochというものを考える。要するboundaryをepochで管理する。そもそもepochがserial orderの管理なので、これは正しい。あとはalignの方法の問題。snap(e) = k・floor(e/k)で、k=25 で eのインターバルが40mなんで snapshotは1sec

まず、Global Snapshot Epochを導入(SE) SE←snap(E-k)んで各ローカルのsewを設定sew←SE　最新のsnapshotのversionは epoch <= sew

read/write処理では基本的に直接versionは触らない。ただし、phase3で snap(epoch(r.tid)) = snap(E)ならば、そのまま上書き。そうでなければ新しいverisonをinstallして、前のものへのポインタをprevious-versionにセット。このあたりを見ても4phaseアプローチに見える

reclamationについてはSnapshot reclamation epoch(min sew-1)が進めば破棄できる。このときは別にprevious-versionは気にしなくてもよい。dangling pointerは参照されない（epochが進んでいる）から。

Deleteは簡単ではない。absentのフラグが立っている状態で管理。Snapshot reclamation epochで「消してもいいよ状態にまずセット」次にtree reclamation epochで処理する。むーん。

4.10 Durability
recoveryの単位の問題になる。epochベース（durable epoch D)で処理をする。serial orderを維持。いろいろ書いてあるけど、要するにLSNの管理の代わりにepoch使うということ。・・・だから4 phaseぢゃないですか・・・あとは読めばわかるので省略

総括

・MVCCが基本になる
Snapshot Isolationが基本になるけど、SSIではなくてS2PLで処理。その上でそもそもsnapshotをどう作るのか？というところも解決している。

・Epochベース
barrierの一つで同期処理のラウンドに似ている。時差（ローカルとグローバル）を入れるのは良いアイデアに見える。割といろんなところでepochを利用する。

・RDBMよろしくtree構造でいろいろ
実装ベースのノウハウはうまく使うのはあり。B+というかMassTreeが基本。要勉強。

・PreCommitのコンセプト
返答してなければ「なかったこと」にできる。結果、リカバリーが劇的に楽＋速い。パフォーマンスに大きな影響があって、今後の分散DBの肝になる。どの単位で書き込むかも含めて、実際はハードウェアにも依存すると思う。NVM：高速→reclamationが重要 / SSD：低速→あんまりreclamationは考えなくてもよいかも

・感想
DB屋的には、アーキテクチャを理解する必要があると思う。運用、特に対障害設計を考えるときに諸処わからないと厳しい。実際にこの手のモノが出てきたら、チューニングが大変になると思う。

アプリケーション屋的には、「できること」と「できないこと」をどう理解するか？がポイントになる。トランザクション・セマンティクスの理解は必須だと思うし、最低でも少なくともログの話は抑えないと厳しい。

その他関連する情報
FaRM：
MS：マルチノードでの本気の分散OLTP
アプローチはSILOに近いが、かなり違う。
https://www.usenix.org/system/files/conference/nsdi14/nsdi14-paper-dragojevic.pdf

Foedus
HP Labの木村さん
SILOの進化版(って言ったら怒られる気がするけど、本人もSILOぐらい知っとけ的な感じなのでいいかなと）
http://www.hpl.hp.com/techreports/2015/HPL-2015-37.pdf

ERMIA
Sigmod2016
http://www.cs.toronto.edu/~tzwang/ermia.pdf
SSIからの挑戦→SILO的なものと融合？（まだまじめに読んでない）

MOCC
ERMIA遅いよね的な反撃
http://www.labs.hpe.com/techreports/2016/HPE-2016-58.pdf

以上すべて、SILO的な展開のうえでの発展

大体以上がまとめ、んで、その上で、ですが・・・・

そうそう単純にSILOクラスのDBが商用に出てくるということではありません。DBが「使い物になる」というのは、過去の実績からみても5年単位の時間がかかります。さらに、特に日本企業のように、新しい技術の採用に比較的慎重な風土病があるところでは、新しいアーキテクチャのDBの採用は時間がさらにかかります。内製化が企業の急務とはいえ実態のSI依存体質が強いのであればなおさらでしょう。

経験的には、ここでのSILO的なDBが実際の企業の基幹バックエンドに使われるのは2030年以降だと個人的に思う一方で、（欧米では5年待たずに導入されるとは思いますが。）Oracle・MS・SAPもこちらのアーキテクチャに変更してくるのは必然なのでOracle頼みの日本企業のバックエンドも強制的に移行せざる得ないかもしれません。今も昔も外圧頼みのところは変わらないので、そういうオチかもしれませんね。はてさて。

そんな感じ。次はFoedusとかの解説とか書く予定。その前にFaRM書くかも。いやまて。

ビットコインとブロックチェーンと分散合意

先日、分散システムをいろいろやっているメンバーで集まって、話題のブロックチェーンとかビットコインやらの勉強会をやってので、まとめておく。

いろいろ意見はあると思うけど、勉強会では問題意識は大体、共有できたと思う。まずは、キーノートやってもらったS社のMさんに感謝申し上げます。すごくわかりやすかった。やはり分散系をやっている人からの解説は、視点とか問題意識が同じなので参考になる。

以下、自分の個人的見解。合っているかどうかはシラン。

1.　現状の「ブロックチェーンとビットコイン」（以下オリジナルとする）は、そのままでは分散合意とは関係ない。

これはクリアだと思う。端的にいうとビザンチン将軍問題とは「まったく関係ない。」　だから「ブロックチェーンとビットコイン」がビザンチン将軍問題の解決になっているという話は、まずは「まとはずれ」だと思う。現状の「ブロックチェーンとビットコイン」は、分散合意は提供も担保もしない。

そもそものトリガーはMarc Andressenのpostが引き金だと思う。
http://blog.pmarca.com/2014/01/22/why-bitcoin-matters/
「Bitcoin is the first practical solution to a longstanding problem in computer science called the Byzantine Generals Problem.」って言ってるけど、これは少なくともオリジナルについて言及しているのであれば、200%間違っている。

まずブロックチェーンの仕組み自体は手段でしかない。改ざん防止を強固に提供しているに過ぎない。それを使って合意システムを作るというのであればわかるが、ブロックチェーン自体が合意の仕組みを提供しているわけではない。実際、ブロックチェーンを利用した文書の改ざん防止のソフトウェアは、従前から提供されているが、別に合意の仕組みを提供してわけではない。まさに単純な改ざん防止の提供しているだけである。（どの部分の改ざん防止なのか、たとえばコンテンツなのか、通信経路なのか等々についてはいろいろあるとは思うけど。）

次に、ブロックチェーンのアプリケーションである、ビットコインは合意の仕組みを提供しているか、という話であるが、これは結論としては提供していない。より長いチェーンが登場した段階で、短いものについては常に反駁される可能性は理論的には排除できないので、合意は理論的には成立しない。

たとえば、思考実験的に考えてみる。

・あるビットコインの系とその系を構成する部分系Aが存在する。
・その部分系Aとそれ以外の部分系!Aとの通信がA->!Aの単方向にのみ天文学的に無制限に遅延するとする。
・その部分系Aの内部だけで高速にチェーンをつくられるとする。
で、
・それ以外の部分系!Aで作られたTxが一部分岐して、間違った（syntaxとlocalのsemanticsは整合しているがglobalなsemanticsが不整合のような）Txが部分系Aに流れたとする。例によくでるdouble spendingなどがこれに当たると思う。
で、
・天文学的に時間が流れたあとで、なぜか一時的に単方向遅延が解消したとする。
すると、
・かなりの確度でその以外の部分系!Aのチェーンは否決される。(各ノードのlocalなsemanticsが整合している場合は単純にチェーンが長い方を採択するルールによる）
・遅延が解消した時点で合意とか勘違いする人は、天文学的な時間を無限（かならずいつかは到達はするが、時間は無限）とするともっとわかりやすいかもしれない。非同期の分散合意理論では普通に措定される仮定である。

こういうモデルは今のビットコインでは成立することができる。

基本的にビットコインは非同期モデルであり、しかも合意を提供しているわけではない。（合意を提供しない段階で、sync/asyncもへったくりもないのだが、系全体を統括するバリアーがないという意味でasyncに近い）。現実を考慮すれば、単純に、自分のノードの値が否定される確率が時間の経過とともに限りなくゼロになる仕組みと言える。ただしゼロにならないので、（ゼロになるということは、その系で参加している全ノードが同一の値をもつということであり、これが合意(consensus）になる。）よって、合意ではない。

また、確かに障害の種別としてビザンチン障害的なものを想定していて、それを克服？しているように見えなくもないが、そもそもビザンチン障害はすべての障害を含むので、当然にcrashやomission（含む遅延障害）も含む。これらを全部克服しているわけではない。

要するに「ブロックチェーン/ビットコイン」はビザンチン将軍問題を解決もしていなければ、ビザンチン障害も克服していない。そもそもまったく関係がない。

注）改ざんがなければ、最終的に合意する（できる）という間違いについて
ブロックチェーン系の論文で良く見かけるのが、系の中でメッセージの正当性・正確性が明確であれば、最終的には合意できる、という主張だ。場合によってはeventually consistentだといういい方すらある。これは明確に間違いで、まず分散合意はある一定の時間内でどのノード（processes）も同一の値を出力するというのが原則だ。この時間は無限・無制限ではない。必ず(非同期系であっても）定義される。そもそも遅延やcrash障害が各ノードで発生しても、そういったfaulty processesを検出して、non-faultyなprocessesは「すべて」同一の値(またはvector)を出力することがconsensus（合意）であって、それ以上でも以下でもない。「なんかしらんが最終的に合意する」というのは、そんなものは合意でもなんでもない。仮に「いや、でも値は一つしかないのであれば、手続きはどうであれ最終的には合意できるはずだ」という方は、各ノードがそれぞれ遅延とか故障とか起こすとして、であれば「どのようなステップ」で、そのような合意の状態に至るのかを明確にすべきだろう。実は、これが分散合意の理論そのものであり、何十年も研究・試行錯誤されている課題である。そして、ある条件下でなければ合意は担保できないということが証明されている。

2.　それでも「合意が」という議論について
総じて、ビット・コイン/ブロックチェーンの現状の議論は、分散システム屋から評判が悪い。たいていの人は「なんだか違和感がある」というのが普通だと思う。

これは、たぶん、「ビットコイン/ブロックチェーン」のオリジナルと、そのalternativeといわれるそのほかのフレームワークとの違いの混同によるものだと思う。現状の「ビットコイン/ブロックチェーン」が合意の仕組みを提供しない以上、普通に考えれば、合意の機能はユーザとしてはほしいし、alternativeにしてもオリジナルに対して、技術的にも優位な機能に見える。

なので、alternativeは、「合意」仕組みの提供に血道を上げるし、そういうアピールをしている。確かに合意が提供できれば「ブロックチェーンをベースにしたビットコインのalternativeが、ビザンチン障害を克服し、分散合意の問題をも解決した次世代の仕組みを提供する」という言い方は筋が通るし、実際にできれば画期的でもある。

この時点で、初めて「ビットコイン/ブロックチェーン」はByzantine agreementを相手にすることになる。ということで、メンバーシップどうするんだとか、failure detectorどうするんだとか、遅延どーすんだとか、まぁ数十年にわたり、決めてのない問題を処理する羽目になる。現実には低遅延の仕組みですらそこそこ制限がかかってなんとか合意できるのが現状の技術水準であり、インターネッツのように遅延が大きようなケースでは、制限なしでは不可能というのが現実だ。

ところが、良くある議論は、オリジナルとalternativeをごっちゃにして、おなじ「ビットコイン/ブロックチェーン」として語っていることが多い。それはそうだろう。「ビットコイン/ブロックチェーン」の実績という意味では、alternativeはほとんど実績がなく、現実に影響力をもっているのは、オリジナルの方なのだから。これらを切り離して整理した途端に、実績という意味では、alternativeはメッキが剥がれることになってしまう。

オリジナルは合意は形成せず、しかし、alternativeは合意を売りにしている。合意の有無は、分散システムを少しでも囓ったことがある人には自明だが、javaとjava scriptほど違う。その意味で、オリジナルとalternativeは、同じ「ビットコイン/ブロックチェーン」と称しているが、実際はまったくの別物だ。分散理論では、非同期の分散合意は制限がない場合は理論上できないことが証明されている（FLP定理）。合意をとるのであれば、現実的には、同期モデルにして各種のfailureに対応することが必須であり、かなりの制約が発生する。普通は、信頼性の低く、かつ、高レイテンシーでの系では現実的には絶望的にスケールしないのが普通だ。

要するに、alternativeは、閉鎖した低レイテンシーの環境下ならともかく、インターネッツでは実績がでるどころか、そもそもちゃんと機能して、ある程度の低レイテンシーを維持しつつ、スケールするかは怪しいと思う。しかし、もはや、かなりのお金が「ビットコイン/ブロックチェーン」には動いてしまっている。いろんなところの株価にも影響してしまっている。いまさら、alternative勢は後には引けない。意図的にオリジナルとごっちゃにしていかにも実績があります、という風に見せる以外に逃げ延びる道はない。なので、わざと議論を混乱させるキライがある。（さらに、「改ざん防止をちゃんとやれば、合意しますよね。」というように合意の問題を改ざん防止に巧み置き換える議論もよく見る。これは意図的だと思う。）

そもそも、オリジナルの「ビットコイン/ブロックチェーン」の面白いところは、分散合意の困難さの解決を、むしろ結果として積極的に放棄するところにあると思う。「合意できない」というデメリットを逆手にとって、「最終的に反駁できる可能性がきわめて低い」という形に利用している。これはP2Pの一つの「形」のように思える。確かにこの方法は、ある一定のセグメントでは有用に思える。（そして、これは多分意図した結果ではない。たまたまハマったという風に見える。その意味でも非常に面白い。）金融のように、とにかくシステムで一意に担保する、ということが必要な仕組みであればまったく役には立たないが、ざっくりでいいので「100%の保証ではないけれど、ある程度、値の担保ができればよい」というものには役にはたつと思う。他方alternativeはこの奇貨をむしろスポイルする方向に見える。しかも、技術的な難易度は非常に高い。はてさて・・・

3.　おまけ：オリジナルの「ビットコイン/ブロックチェーン」については過度に政治的なものになっているようにも見える。
ついでの話だが、上記の例では思考実験ということにしているが、実はモデルがある。以下は個人的には面白いなと思っている。

・部分系Aを中国とする
・そのほかの系!Aを欧米・日本とかの金融機関とする
・現状Minerの大半が中国である、ので、中国内部では活発にBitCoinが志向されているのは明らか
・で中国当局は、自国の金融商品・通貨の持ち出しは規制したいとする
・中国当局はインテーネッツとか人力で制限できるとする。

んで、どうなるかってのが、個人的な興味である。基本的にasyncであるので、中央集権的に否定することは理論上できない。今の中国国内の「お金持ち」が何を考えるか？は容易に想像はできるが、・・・・実際はこういう話ではないと思うけど、思考実験としては面白いなと思っている。すくなくとも、現在のMinerの大半が中国というのは、いろいろ考えると興味深い。

・・ま、いずれにしろ、「ビットコイン/ブロックチェーン」はいろんな意味で確実にババヌキの展開になっていると個人的には思う。
（以上は自分の個人的な見解なんで。読んでる人は各自自分でちゃんと考える事をお勧めします。コレを機に分散合意についていろいろ調べるといいかもしれません。・・とにもかくにも、合意（consensus)の話がいつの間にか改ざん防止の話になっていたら注意したほうがいいとは思いますよ。）

以上です。

Asakusa 0.8 with M3BP

Asakusaが新規に高速実行エンジン（M3BP）をサポートした。M3BPはメニーコア特化型のC++で実装されたDAGの実行エンジンになる。ノーチラスとFixstarsの共同開発のOSSで、単ノード・メニーコアでの「処理の高速化」に振っている。いわゆるIn-memoryの実行エンジンで、ノードのCPUコアを使い切ることを目標しており、余計な機能はすべて削った。データがサーバ・メモリーに乗るクラスのバッチ処理であれば、ほぼ物理限界までパフォーマンスをたたき出す。

http://www.asakusafw.com/release/20160412.html

実際のベンチマークは以下のwhite paperにある。
http://www.asakusafw.com/wp/wp-content/uploads/2016/04/M3forBP_WP_JA_2016Apr12.pdf

ベンチマーク対象のバッチ処理は、BOMの組み上げ再計算を行うもので、RDBMではかなり苦しい多段結合のフルバッチになっている。
・MapReduce　2218sec
・Spark 229sec
・M3BP 112sec
（これはAzureでの比較で16コアでの結果だ。コア数を増やした場合はM3BPは40コア近辺で60sec程度までさらに短縮している。）

使ってみて「とにかく速い」につきる。ほぼコア・メモリーバンドと使い切っているので、データがノードに乗る限りにおいては、これ以上のパフォーマンスを出すのはなかなか難しいレベルまで来ている。（あとはどう効率的なDAGを組むかという話しかない）

これは以前のエントリーで書いたように、先のRSAを睨んだかたちでの、足下のメニーコアでの最速化を見ていることが背景にある。
http://d.hatena.ne.jp/okachimachiorz/20151225/1451028992

データフォーマットは当然だが、HDFS・CSVあたりは普通にサポートしている。HDFSクラスターに一台サーバを追加して、そこで処理を実行することができる。Hadoop/Sparkでは処理が遅いjobをM3BP上で実行することにより処理時間を大幅に短縮することができる。結果としてのHadoop/Sparkの用途も広げることになると思う。

なお、2016年4月の時点で、現状のメニーコアは
http://news.mynavi.jp/news/2016/04/01/020/
にあるとおり、1CPUで22コアである。ノードはアーキテクチャが通常2ソケットであるので、ノードコアは物理44コアになる。サポートメモリーは1T（もっと上か？）程度になる。たいていの業務系のバッチ処理は、経験的にはこのサイズで収まる。まだ分析用途のためのHDFS上のデータであっても、いったんクレンジングし、適当なGroupByをしたあとであれば、同じような規模に収まると思う。

M3BPをサポートした結果、Asakusaはこれで以下の三つの実行エンジンをシームレスにサポートすることになった。Asakusaで書いたコードは、リコンパイルするだけで、一切修正することなく、各実行エンジンで走る。Asakusaの目標のひとつは、One size does not fit allを前提にしたうえでの、トータルで線形のスケーラビリティなので、各エンジンを使い分けることで、それにほぼ近づきつつある。データは普通にHDFSにあればよい。

・M3BP
C++の最速実装。処理データが1ノードで収まる場合はもっとも高速で効率が良い。

・Spark
ジョブ実行時の処理データのサイズが、1ノードで収まらず複数にまたがる場合はSparkでの実行が高速になる。

・MapReduce（Hadoop）
データサイズが巨大で、大規模なGroupByを行うような処理はMapReduceが最速になる。（それ以外はSparkのほうが高速）

「Asakusaの使いどころを大幅に広げた。」というのが、結果としての、個人的な率直な実感だ。用途的には、従来のAsakusaとはほぼ別物にまで進化していると思う。何ができるのか？という意味では以下が面白いと思っている。

■RDB/分散クラスターの隙間を埋める
RDBでは処理性能が足らないが、かと言って分散クラスターでは過剰というケースでは、M3BPで処理をすることで高いパフォーマンスを得ることができるようになった。ここはいままでの分散処理基盤では完全にエアポケットになっていた。

■HDFSに溜まったデータの処理の利用可能性を広げる
HDFSでのデータ連携も当たり前だが普通にできる。ある処理で、データはHDFSにあって、そもそもは大きなデータだが、ジョブ実行時に処理の途中からサイズが絞られて、結果Hadoop/Sparkのオーバーヘッドにコストがかかり、トータルでみると処理効率が悪い、というケースによりよい解決を提案できる。でかい処理はMapReduce/Sparkで行い、途中からM3BPに切り替えればよい。

■「"リアルタイム"・バッチ処理」という選択肢の提供
とにかくデータサイズが許容される範囲では処理が速い。RDBで4-5時間のバッチ処理が、Hadoopで20分程度まで短縮し、Sparkで5分程度になり、M3BPが1分を切るというレンジになってきた。バッチ処理のタイム・スケールはHourlyからMinutelyを経てSecondsの単位になってきている。こうなってくると、バッチ処理と"リアルタイム"（まぁ厳密には全然リアルタイムではないが）の違いがだんだん無くなってくる。結果、業務側でできることが格段に変わる。メニーコアの能力を使い切ることで、今までとは違うことができる。

■分散並列処理の敷居をさらに下げる
特にエッジ・ロケーションでの処理ではよい選択肢になる。1ノードなので、コストも場所も取らない。プレクレンジングの処理ではよりよい解決を提示できる。いままで、分散並列処理ということであれば、すぐに分散ノードということになっていたが、その前にまずは単ノードでの導入が可能になる。その後データが増加するにつれてクラスター構成にすればよい。

・今後
個人的には、あとはRSA的なものへの対応になる。今後のロードマップを見据えて開発する予定だ。その段階で「非同期処理（データを投げて、同期を取らずすなわち処理の終了を待たずに、次に処理を行う処理）」の実行基盤については、分散並列環境に限って言えばかなりの完成度になると思う。

やはり現状の分散並列環境、特にHadoopは、大規模データ向きである。これはこれで素晴らしい仕組みだと思う。ただし、世の中のすべてのデータ処理というセグメントでみれば、やはり過剰である部分は否めない。無論、データがPBクラスを越えるであれば、何も考えずにHadoopを使うべきだし、それは今後も変わらないだろう。TBの上位であれば、HadoopよりもSparkの方がほぼすべてのワークロードでは優位だろう。ただし、もっともメジャーであるのは、GBの上位からTBに届くかどうかレベルであり、かつ、RDBではやはり御しきれない、というデータボリュームだろう。ここに対応できるの実行エンジンがM3BPになる。Asakusaはこれらの実行基盤を透過的に使いこなし、データ処理をフルレンジでカバーする。

Asakusaで処理を記述しておけば、M3BP→Spark→MapReduceとコードをまったく変更せずに対応することが可能になっている。数件程度のデータの「バッチ処理」も数秒以内で終わり、かりにそれが数億件まで増加しても、そのままスケールアウトし、数十分で処理を終わらせる事が可能になる。

ITは必要悪か？その2

大規模会社、特に社会インフラ系の会社で売上も兆に届くところでのITのあり方は、中小規模の会社とは全く違います。システム構築、とくにSI的な観点からは、実際のプロジェクト単位で見たときに大規模システムと中小規模システムを便宜的に一緒にして考察することが多いのですが、俯瞰したときのあり方は、まったくの別ものです。

大規模な会社では情報システムは、大きな組織のバックエンドの一部であると同時に、企業を動かす歯車として欠くことできない存在になっています。「ITがない」という選択肢は企業活動としてありえません。システムのあり方が大企業と中小企業では異なるため、中小企業でITの必要性という点と、大企業でのITの必要性では意味が大きく違います。明確に区別する必要があります。

■あり方
大規模企業の内部において、情報システムはその企業が存続するための重要な機能を担っており、それなしでは企業は成立しません。大規模な企業運営において、顧客・内部組織同士に対して、ある程度の均質的なサービスの提供を効率的に行うためには、個人のオペレーションで品質・水準で誤差がでることを積極的に防止する必要があります。そのためのシステムです。中小企業では、こと日本企業においては、構成人員の同質性（とくに言語とベースの考え方）が高いため、かなりの程度まで、「システム抜き」の人員で、サービスの均質性をカバーアップできる（できてしまう）ため、事情が異なります。別にシステムじゃなくても人手でやればいい、という発想が根強く、また、それが実現できているのが実際です。（今後はわかりませんが）

■特徴
社会インフラ系企業のシステムの特徴は以下になります。

・規模が非常に大きい
基本的にシステムの規模は大きい。データが大きいというよりも、非常に多くのシステム・サブシステムが構成されていて、全体的に強度に複雑です。また同時に関わる人間も非常に多く、その人間間の「仕組み」も複雑です。

・システムに関わる意思決定が奇々怪々になりがち
基本的にシステムに関わる意思決定は多層的になります。たまに例外がありますが、例外は例外です。大方針でこうだ！とぶち上げたところで、全体的なブラックボックス化が進んでいるので、末端まで来るとやるべきことが真逆になっているという、この時代になんの糸電話ですか？ということは、ものすごく普通にあります。要するになんでこうなった？がよくわからないという状態が非常にしばしば（特に末端に行けば行くほど）観察できます。

・普通に肥大化する。
企業規模が大規模になるほど複雑さは、リニアではなく、ログリニアで増大します。企業規模が1000億円企業と1兆円企業では、複雑さの違いは10倍ではなく、100倍近くはあります。結果として、システムが肥大化します。

・メンテナンスが追いつかない
肥大化したシステムの維持管理は、非常にコストがかかります。結果として、新規に開発する、つくるというよりも、維持し、回すという方向に力が働きます。

・にもかかわらず企業の存続という点でミッション・クリティカルなITになっている。
企業活動自体のITへの依存度は実は中小企業よりも高いです。文字通りシステム全体としてはtoo big to failになっています。いろいろ問題が発生して、騒ぎがでかくなると報道機関に記者会見、監督官庁にご報告とか普通にやる羽目になることもあります。基本的に止めるということはできません。結果として投資金額も非常に大きい。

まぁ、上記の話は、普通に社会インフラ系の大規模企業のシステムとしては普通の話で、特に異論もないでしょう。要するに「無い」という選択肢はないし、またかなり大規模複雑になっている、ということです。

■問題点
・実態として「全体の制御」がきわめて難しい
このクラスになると、どれだけ力（政治力・技術力・予算力）があったとしても、システムのあり方は個人でどうにかなるという話（カリスマ的な社長であったとしても）ではありません。システム自体が徐々に“リバイアサン”化してきます。

・多くの人が巻き込まれることになる。
意思決定の多層化、システムの極度の複雑化は、結果としてITの問題を、むしろ積極的に人力で解決するというパラドキシカルな状況になります。多くの人員が関わるので、システムに多少問題があっても修正することが困難です。たとえばこの種のシステムの大規模開発では、開発中止は勿論、計画変更も相当困難です。結果、大抵の人が、これは問題がある、と思っていても手の出しようがない状況にしばしばなります。アジャイル信者の人には良く誤解がありますが、これは「開発方法論」の問題ではありません。意思決定が多層化し、システムが極度に複雑化している場合は、どうしても、すべての動作を「細かく切る」ということがそもそもできません。なんとかしたいので、コンサル頼んで「いろいろと整理する」ということもやっても、そもそも整理作業自体がさらに問題を複雑にすることすら起きます。

・結果としていろいろ消耗する。
本来であれば、企業活動のためのシステムが、逆転して、システムのための企業活動を誘発します。顧客や従業員のためのシステムが、いつのまにやらシステムのための顧客や従業員になるというやつですね。これは結果として関係者（顧客・従業員・IT部門・ITベンダー）を消耗させます。どう控えめに言っても「人には優しくない」ですね。

大規模会社におけるシステムは、取り扱いが困難であり、かつ一種の不経済を発生させる一方で、組織運用には欠くことができない、という意味で、一種の「必要悪」という見方もできます。この手の怪物をどう制御するか？が問題になります。

■組織の問題
結論的に言うと、たいていの場合、この規模のシステムの問題は、組織の問題に帰着します。要するにITとは関係がない部分が大きい。場合によっては「ITとは全然関係ない」ということすらあります。ややこしいのは、IT自体がブラックボックス化するので、この手のシステムの課題が「いかにもITの問題」に見えてしまう、という点です。

中小企業においては、ITはある程度ツールとして割り切ることが可能で、独立した「IT自体の問題」として考えることが可能ですが、社会インフラ系ではそういうことになりません。システムとは組織維持の仕組みそのものであり、ITは「ツール」ではありません。

システムの扱い方は、そもそも大規模な組織をどうしていくか？という問題に近いです。

肥大化した組織運営の効率化は、普通に「分割統治」であることは論を待ちません。意思決定の透明化・簡略化は組織運営自体のスピード・効率を上げ、不要なコミュニケーションの減少は、関係者のストレスを軽減します。なので、システムを組織的に分割して、組織としてメンテできるようにサイズを落としていくという方向が望ましい、

と思うじゃん？（ワールドトリガー風味）

■コストメリット
ところが、ITのような一見「資本集約的な仕組み」（本当は違う）は、できる限り一元化したほうが、コストが安くなります。特に調達コストは普通に単価の桁が変わります。ひどいときには単価が2桁変わることすらあります。開発工数も同じものを複数つくるよりも、単一のもので使いまわしたほうが、少なくとも開発コストは減少するように見えます。

コスト・リダクションという観点で見ると、システムは統合したほうが、確実にメリットがあります。社会インフラ系企業のM&Aでお題目のようにシステム投資の削減といわれるのは、別に根拠がないわけではないです。

よって、システム分割は大企業においては、集約メリットを放棄することに近く、コストメリットが取りづらいのが普通です。なので、通常はむしろ逆に「統合システム」をつくることに執心します。企業内の複数の組織で、“同じような機能”のシステムを開発・メンテすることはコスト的にはデメリットになります。

要するに、システムはそんな簡単に「分割統治」はできないわけですよ。

そこで、例えばITインフラ統合して、その上のアプリケーションを個別開発すればいいじゃん、という形にもっていくのが普通です。ほぼ、すべての社会インフラ系企業のITはこういう形になっていますし、この形であればスケールメリットもとれるし、個別対応のオーバーヘッドを軽減できます。

と思うじゃん？（A級槍使い(ry

■統合システム？
ところがところが、インフラとアプリってのをキレイに腑分けできる、というのはあくまでプログラムの話で、関わっている人間の意図・考え方はうまく手当してあげないと、お互いに伝わりません。ドキュメント・APIで伝わるのは基本的に手段の話であって、考え方ではありません。考え方や考え自体を言語化するトレーニングはIT関係者は普通受けていません。（考え方はAPIとかドキュメントから“読み解け“ってのが普通です。冷静に考えればおかしいのですが、おかしいと思わないところがトレーニングをうけていないサガですね。）

IT屋のドキュメントは生成の仕組みまで含めて「How」の記述に特化しています。肝心の「What・Why」は記述されません。誤解のないように言いますが、ちゃんとしたIT屋は「What・Why」はちゃんと考えます。かなり相当考えます。ただし、業界として、「What・Why」の記述方式にコレといったものがないのと、記述の手法の訓練をIT屋が受けていないことが課題です。

結果、人間系が入らないとトータルにパフォーマンスを出すことが難しくなります。というか、全然パフォーマンスが出ないので、人間系で情報共有を密にやるという話になりがちです。とどのつまりは、組織的には全然分割統治になりません。一見、システムはばらけているように見えても、遠目で人間系の組織とみると、全体的な有機体になっています。

要するに、スケールメリットを安易にとりに行くと、どんなに頑張ってもシステムが実質的にガンガン肥大化するのは防げませんよ、とこういうことです。なので、スケールメリットの享受を捨てても、ある程度、システムを細切れにした方がスピード感や透明性を保つということが可能になり、うまく回すということが可能となります。（細切りにしたからと言って無条件に見通しが良くなるというわけではありません、念のため）とはいえ、細切りにしすぎると、今度はコストがやはり増加します。

■結局
要するにバランスの問題です。

この時に考えるべき一番の要素は「人」です。個々人のあり方、チームのあり方、能力・コストを勘案し、かつそれらを時系列で判断しながら、「適切なサイズにシステムを押さえ込んで行く」ということが必要です。んで、大体できてません。

大規模システムのあり方は、徹頭徹尾、組織論です。開発方法論とか、フレームワークとか、特定実装とか、ERPとか、パッケージで行くとか、クラウドとか、AIとか、そんな話はまったく本質ではありません。勿論、これら技術要素がわからなければ、組織的な適合性が判断できないので、技術要素をちゃんと正確に把握していることは必須条件です。その上で、個々人の有り様・チームビルドのあり方（大事なのは時系列で見るということだと思います。）を、一定のビジョンをもってくみ上げていく、ということが、肥大化するリバイアサンを御することができる唯一の手段に見えます。

んで、そういうことができる人間はなかなかいないので、大抵の大企業ではシステムは人を食い殺していますね。これが現実。

要するに、大規模システムでの設計も実装も運用もわかって、最新の技術要素もわかって、人員の状況も把握し、今後の展開とシステムの在り方を時系列で把握・予想できて、組織運用のイロハがわかっていて、いざとなったらオーバーコストも辞さない覚悟をもっているスーパーマンを情報システムの頭に据えて、相当の権限を与えないと、大規模システムという内なる怪物とは戦えないですよ、ってことです。間違ってないでしょ？（ま、こんなのがいたら普通に営業総責任常務執行役あたりになりますがね）

ITは必要悪か？その1

もともとは2016年の年の初めに書こうかと思っていたことですが、時間も経ってしまっていたところ、アリエルの井上さんとの対談 　IT屋はバズワードを使ってはいけない……のか？ (1/5)：EnterpriseZine（エンタープライズジン） も あって、ちょうどいいので記録的に思うところを書いておきます。

・前提
ここではITと言う漠然とした言い方になっていますが、日本で最もマーケットの大きい、いわゆる業務システムを対象にしています。いわゆるSIの対象になるところです。と言っても一概に言えないので、売上2000億円程度の大規模企業の、下の方から、中小企業までの話にしています。売上が兆円単位の規模の社会インフラ系のシステムは、その2 ITは必要悪か？その2 - 急がば回れ、選ぶなら近道 で考えます。業務システムなのでコンシューマーものは考えてません。

・ITは必要悪という認識
基本的にユーザ企業においては、ITはコストがかかるが必要であり、できればない方がよい、という考え方が主流です。要するにITは必要悪と見なされることが多い。自分が小売流通にいた時には、営業系役員から「この「50円のもやし」と必死で売っている一方で、お前らは5000万、5億という投資を簡単にする。どうなのか？」というのは、よく言われました。それはそうだと思います。業種は異なっても、同じ事を営業系・商品/製造系の役員から言われるCIO的なまたは現場の情報システム部の人間は大勢いるでしょう。

「ITに投資しても売上は上がらないし、それならIT以外の営業資産に資金はつぎ込んだ方がいい」というのが、日本のそこそこの大企業から中小企業以下の経営陣のほぼ共通認識でしょう。間違ってはいないですね。一部のWeb系ならともかく、普通の企業がITに投資したからといって、それが直接売上げにつながるということはきわめてレアケースでしょう。

もっとも、IT以外に投資すれば売上が上がるかと言えば、現状の日本市場は、人口の高齢化もあり、消費自体が伸びていないので、ITでなかろうと、なんであろうと、素直に売上があがるということはありません。が、高齢層の企業の経営陣としては経験的な先入観がどうしても強く、ITは金食い虫で、しかも売上げ貢献が低い、というのは本音ベースでの共通認識でしょう。勿論、ITなしではいろいろ業務は回らない、ということぐらいはわかっています。

・ITの企業における位置づけ
日本のITは、というか、日本の企業はベースとしてITをその中に入れる事を拒んでいる、というか失敗しています。表向きの話はともかく、実態としてITをビジネスの中心においている企業はほぼありません（勿論、Web系の例外はありますが、企業数としては圧倒的に少数です。・・あとは、前述のように、大規模な社会インフラ系企業はのぞきます）。

営業資産はともかく、企業の主たる構成要素の「人間」を見れば、割と簡単にITの取扱がわかります。一般の企業で、ITをそのキャリアの中心（下手すればITのキャリア“だけ”で）にすえて、トップマネージメントになった人間は非常に少ないでしょう。経営層は勿論、現場でもITスタッフのためのキャリア・パスはユーザ企業ではあまり準備されていません。基本的にITはバックエンドの延長線でしかなく、経理・人事・財務とほぼ同じセグメントにあります。よって、その流れのなかでしかキャリア・デザインは提供されません。

現状のITの人材にたいする、ユーザ企業の扱いは、「基本的にアウトソースで調達する」です。主にSI屋・コンサルからの事実上「人材派遣」がベースで、ITリソースを調達しています。よほどの例外を除き、この種の派遣ベースの人間がその企業のコア人材になることはありません。勿論、情報システム部は社内の人材で構成されている、ということが多いとは思いますが、言ってみれば「アウトソースのコントローラ」であり、トータルのデザイン力・細かい設計力・実装力・運用力・障害対応能力・最新のITに対する知見について、専門家ではありません。そもそもITのプロになるために、そのユーザ企業に入社したわけではないので、当然そうなります。

「いまや、ITは社会の隅々まで行き届いて、云々」という話は、毎日のように聞きますが、普通の企業活動で必須か？無いと倒産するか？と言われれば、そうでもないので、まぁそういう取り扱いですよね、って話です。

余談ですが、このあたりが、特に米国のITとのあり方の違いになっている、というかこの20年で大きく開いたところだとは思います。Google, Amazon, Facebookの初期の頃や、AirBnB, Uberあたりもそうですが、彼らはベースがITであり、ビジネスと深く結びついているし、そもそも「必要悪」という発想はありません。Amazonと同じ業種の日本の小売業を比べて見れば、自明でしょう。米国では、ITはむしろないと死ぬぐらいに考えているし、というか過剰すぎるぐらいの企業もあるように見えます。

・で、だから何？って話
その上で、ここ最近のITのバズワードを見てみましょうって話です。ビックデータ・IoT・人工知能で、もう次はFintechですね。これらはそもそも単純な要素技術ではなく、ある種の考え方をベースにおいたITの利用方法でしかないです。ITを血や肉にして、体内の企業の遺伝子としてもっている企業が使う技術とも言えます。ITを必要悪としてしか見なせない日本企業では通り一遍のメリットすら得ることすら難しいでしょう。なにしろ、人材も組織も企業としての考え方も含めて、使いこなすベースがありません。

では現状ではどうしたらよいか？という話でして。そもそもベースがないので、ITのバズワードに乗ったところで大半の日本企業にはメリットはありません、という話なんですが、それでは身もふたもないので。そもそも論から少し考えてみましょうというのが本論。

・そもそも日本企業でITをどう考えるのか？
まず、既存企業でもう少しITを軸におけないか？という話があると思いますが、これはまず無理でしょう。企業は人で構成されています。資本や設備ではありません。従って、人の考え方が変わらない限り、企業は変わらないし、変われません。大抵の企業で働く人間、特に経営層は、ITは基本的にいらないわというよりも無くてもいいわ、と思っているので、ベースのカルチャーは「IT必要悪文化」になっています。具合が悪い事に、企業文化は一種のホメオスタシスとして機能するので、人が一人二人「いやITはコアビジネスに必須だろう」と変わったところで、「是正」が勝手に働きます。

なので、ITをコアにできない、というのはユーザ企業の今までですし、今後も企業の構成人員が変わらない限り、変わりません。つまり、現状の組織構成要素では、ITが血肉になることはまずありません。別にこれはこれでいいと思いますよ。なんども言いますがITに投資しても現状の日本では売上は上がりません。投資効率としてはあまり良くなくて、そんな金があったら、従業員の賞与に回すわ、というのは経営判断としては、多分正しい。

それでもなんとかしたい、ということであれば、以下の二つの考え方があると思います。

・必要悪のITとどう取り組むか？

1)徹底してツールとして見なす。

バズワードが完全に無視する。ITのトレンドは一切無視して、「自分に必要な武装」は何かを自社のなかでちゃんと考える。コンサルとか、ベンダーの提案とか全部無視して、ちゃんと徹底的に考える。惰性ではなく、本当にITは必要なのか？というレベルから見直す。そもそもITが自社のDNAでもなんでもなく、必要悪であれば、徹底的に無くせるところでまで考えて、考えて、必要な部分のみを精錬して利用する。いらないならスパッと捨てる。

カッコつけて「ITは我が社の背骨である」とか言わない。そうなると、他社は？とかトレンドは？とか気にし始める。もともとコアでないものに、なぜ気をつかう必要がある？

削りに削って、どうしても残ったものがあったとする。そこで、それはそもそもなぜ残ったのか？を考える。そこまで残ったにも関わらず「自社の遺伝子」でないとすれば、それはなんなのか？を考える。そこがスタート地点になる。

こういう考え方をしてみるのも手でしょう。

そうなると例えば、「ITは業務の効率化」の手段という発想も逆になります。極端に言えば、「ITで業務を効率化することが、会社の目的です」というぐらいになる。この段階で本当にただのツールか？という話になります。そこから「必要悪」ではなく、「必要なIT」を絞っていくということができると思います。

2)DNAを作る。

ITがないと死ぬ、ぐらいのビジネスモデルを「逆に考えて」会社・企業をつくる。完全独立の子会社？（若干、語義矛盾っぽい）位で、人事交流もないぐらいで作る。そもそもITはツールです。ツールを目的にすることは本末転倒ですが、その本末転倒を敢えてやる。

経営的には、多少IT的に芽が出そうだっていう時点で、案件ごと、自社から完全に切り離して、投資金額とランニングのキャッシュをフリーハンドで渡して、かつ人事的に経営的に完全に分離させることが最低限必要でしょう。バックエンドは面倒なのでシェアードで提供することはありだと思いますが。

これでも成功率は5%以下だと思いますので、こういった試みを20回程度はやらないと駄目でしょう。それだけやれば、ひとつふたつはものになると思います。実はこれはITに限らず、既存企業が新しい市場に対応するために、よくやってきた手です。後付けで「多角化」とか言ってましたが、実際は、市場拡大のための片道切符を渡して、従業員・役員ともども一か八かという賭け。大半は沈没船ですが、気がつけば子会社の方が全然大きくなった、と言う企業もあったりします。生き延びて成長している企業ではありがちな話です。

かなりハードルが高いのですが、そうそう荒唐無稽な話でもない。これだけやればさすがに無理矢理IT軸のDNAを作っていくことはできると思います。

ただしこれは既存組織と完全に切り離すことが必要です。たとえば小売流通だと、これだけAmazonに文字通り「こてんぱん」にやられて、オムニチャネルだと大騒ぎしているにもかかわらず、ITを軸にしたECは全然パッとしません。別に無視しているわけではなく、そこそこ金と人は突っ込んでいるですよね。ところが、順調にいくどころか、大炎上案件や売上としては苦戦するばかりです。なぜか？基本的に人の問題と企業の遺伝子の問題で、「日本の小売流通業」ではITは本質的に必要という認識はないからです。発想が既存の考え方に無意識のうちに制限されてしまいます。・・・そもそも店舗連携とか中途半端なこと言ってる段階で終わってるわけですよ。最後では店舗で巻き取ればいいやというオチになるので、そうなると店舗運営側は「余計なものもってきやがって」となりますわね。既存ビジネスとの分離ができてません。新しい「組織の遺伝子」がやはりできない。これは小売流通の例ですが、同じようなことは他の業界でも枚挙暇がないでしょう。

トップからエンドまでの人間が、少しでも「ITなくてもウチの会社つぶれないし、回そうと思えば回るからね〜」という考えが頭をかすめた段階でもう無理です。AirBnBとかUberとかあたりでは「ITなくてもウチの会社つぶれないし、回そうと思えば回るからね〜」なんて考えはトップからエンドまで1ミリも出てこないことは簡単に想像できると思います。要するにそういうことです。

・結局
上記二案はそれなりに、覚悟のいる話ではあります。

ITに死ぬ気でコミットできないなら、バズワードに踊らずに、「道具としての練度」をあげて、ちゃんと「必要なところだけ使え」って話です。んで、使い方がわからんなら、金かけず、スパっと捨てろってのは、別に普通だと思いますよ。・・・ただし、社会インフラ系はそうは行かないので、これは別掲。

あとは、ITは必要悪だろうというのは、重々承知の上で・・・現状の日本では「どこに賭けても負けゲーム」です。であれば、ITに張っておいても、文句は言われないでしょう、どうせ分が悪いから。・・・ということ、DNAというか企業文化の再構築を試みるのは手だと思います。中途半端に張ってもそもそも失敗するのは明らかなので、本腰いれてやったほうがよい。

実際問題として、それなりの風は吹いていて、今後のITは残念ながら（？）アプリケーションを握っていることが強点（Strong Point）になります。内製・インハウス主体で、がっちりやり込むということのメリットが従来よりも大きくなります。

これは技術的な理由です。

現状ではやはりムーアの法則の限界は物理的にあきらかで、コンピューターリソースの向上は、メニーコア・多ノード化に進み、同時にあらゆるバスの高速化が進みます。これは要するに分散処理技術に「しか」アーキテクチャ的には未来がない、ということです。そして残念ながら分散処理技術は、非常に難度が高く、まだ人類には若干早い。ただし、これは汎用ミドルという点から見た場合で、実は特定のユースケースに限定して、利用する技術を制限的に利用すれば、素晴らしいパフォーマンスをたたき出します。・・これはつまりアプリケーションをちゃんと知っているということが必要ですよ、ということです。あととは簡単に環境の構築・維持ができるクラウドも追い風になります。

ここは実はSI屋では無理があって、ただでさえ技術的に追いついていないところに、パフォーマンスを叩き出せるようにアプリからやり直せってのは、ものすごくオーバーコストになります。だからできないし、やらない。

ユーザが主体で、しっかりアプリケーションを作り込むということが、非常に大事になります。また、ちゃんと徹頭徹尾やりこめばパフォーマンスを出すことができるようになります。（もっとも、踏み込みすぎて自分でミドルの役回りまで作り出すと、ものすごく簡単に破たんします）

こんな感じで軸をつくって、会社として回るようになれば、そこそこにはいくはずです。難易度が高いので、あまりおすすめはしませんが。

追記）そーいえば組み込み・FAはどーなんだ、みたいな話もあるわね、というところですが、そもそもユーザはそれITって意識してるのか？とか、最近だとIoTとごっちゃになって、その意味では必要悪というか、むしろ不要という話もあるみたいで、はて〜という感じです。すんません。

Storage Class Memory

ACMの2016 Jan.の会報の記事に上がっていたので、面白かったのでちょっとまとめておきます。
http://cacm.acm.org/magazines/2016/1/195724-non-volatile-storage/abstract

前提として、SCM（Storage Class Memory）について書いておくと、いわゆる不揮発性メモリー(Non-Volatile memory)で、次世代の主流になるだろうとは言われています。DRAMまでのレイテンシーは出ていないので、DRAMのリプレースにはならないと思われる（のが今の常識）ですが、ストレージとしては最速で、一般にDiskの1000倍（3桁）は速い。が、値段は30倍と言われていますね。

・ハイライトハイライトは以下
・The aged-old assumption that I/O is slow and computation is fast is no longer true
要するに「I/Oが遅いものだ」という今までの前提はあまり通用しないということかと。特にSCMを考えればそれはそうなるとは思います。まぁ今までは、メモリーと比較されるレベルのレイテンシーのストレージというものは、そもそも想定しませんからね。

・The relative performance of layers in systems has changed by a factor of a thousand over a very short time
これは特にSCMでのパフォーマンスの向上が1000倍とかそんな単位ですぐに来てしまうので、システムレイヤーでのパフォーマンス・ギャプの絵面が変わるという意味ですね。

・Pile of existing enterprise datacenter infrastructure – hardware and software – are about to become useless (or, at least, very inefficient).
結果として、特にDCの既存資産は、まぁゴミになると言っています。割と極端なものいいですが、それだけSCMのインパクトが強いということでしょう。

・概要
詳細は直接エッセイを読んでもらうとして、内容を要約すると大体以下の考え方になっています。

・SCMのレイテンシーはかなり低減されていて、Diskは遅いという話は過去のものになるだろう。概ね、既存Disk比で1000倍（IOPS)は違う。（このあたりは、そもそもSSDでもその位は行っていた気がするので、それよりも向上していると思いますけど）

・SCMを導入するときに問題になるのはコスト。これが高い。特に対CPU比になると、従来はCPUが高くてDiskが安い、という話が前提だったが、むしろ逆転するレベル。すなわち「CPUの方が安い」ということになる。この場合は、投資対効果（特にDCのような場合）を考えると、どれだけSCMのIOを使い切れるのか？ということの方が重要になってくる。

その上で、以下の四つのポイントを提示しています。

1.Balanced systems
まずボトルネックがストレージI/OからCPUに移ることになる。処理待ちのデータをメモリーに保持するために、かなりのRAMを必要になってしまう。というかRAM上のデータが単純に処理待ちで手持ちぶさたになる。CPU仮想化のようにストレージの仮想化が必要になるかもしれない。ストレージの利用率を上げることが必要になるので、ワークロードに見合ったバランスのよいCPUや適切なメモリーが提供されることが必要になる。ただ、まぁこれは結構難しい。

2.Contention-free I/O-centric scheduling
ハードウェアのバランスが整っても次に時間軸の問題がある。これはNWの高速化の時のスループットを上げる手法と同じように、できるだけinterruptedさせない手法もやり方としてはあるだろう。勿論複数のコアで並列処理はするようにはなるとは思うが、できるだけ競合しないようにスケジューリングする必要がある。うまくシリアル化しないと、簡単にロックしてパフォーマンスがでない。SCMドライブのサチュレーションをさせながら、クライアントとのやりとりを邪魔しないやり方が必要になる。

3.Horizontal scaling and placement awareness
これは単一ストレージではなくて、まとめてクラスター的に扱った場合の話で、JBODのような単純な仕組みではなくて、分散ストレージ的に扱わないと無理って話です。

4.Workload-aware storage
SCMの特性が実際のワークロードには当然合わない、ということがあるので、うまくtiringした方がよい、という話です。まぁNUMAのように同じデバイス層で複数のレイテンシーがある場合は、データ管理はある程度階層化するのは普通にある話です。シーケンシャルな処理が得意なストレージとの組み合わせも確かにあるでしょう。

いずれにしても、今までのように「単純なストレージ・デバイス」として扱うと、コストに見合うだけのパフォーマンスが得られない。したがって、可能な限りの工夫をしなければならない、というのが趣旨です。

・思うところ
SCMの導入により、ストレージのレイテンシーやスループットは今までのIOボトルネックを（というか、他にボトルネックが他に移るほどに）解消できるほどに向上するが、その分コストがあがる、よって、それを「使い切る」アーキテクチャにしなければ、見合わないという考え方は、面白いと思います。

コストあたりで見たときにストレージのI/Oを使い切るために、うまくCPU資源の利用を考える、という発想はあまりなかったと思います。（正確にいうと大昔にはあったと思いますが。・・そもそも高速ストレージ自体が貴重だった時代には確か、そんな話があったとうっすら記憶しています。もっともおそらく30年以上前ではないかと思いますが・・・）

ここ10数年の流れは、ストレージ（disk）はどんどん安くなるからデータはどんどん置いておけ、というコンテクストが主流でした。そのなかでビックデータとかIoTとか、クラウドとか、そういった「アーキテクチャ」の台頭があったと思います。そのアーキテクチャの一環として、増えたデータを一気にロードする仕組みとしてHadoop/Sparkとかその手の仕掛けが出てきたことには異論はないでしょう。

その流れが変わりますよ、とそういう話ですね。

正直、個人的にはNVMはストレージとして見るのは、ちょっと割が合わないなぁ〜とは思っていました。“超高級”超高速SSDじゃねーの、と。SCMは大量のデータの置き場としては、コストが全然ペイしないでしょう。むしろミドルの、今までのストレージではパフォーマンス的に合わないクリティカルな部分への導入にちょうどいい(たとえばlog管理・snapshotの置き場)ぐらいで、他に用途はないだろうと思っていたので、ここまでの発想はちょっとありませんでした。

また、ストレージに対して「相対的にCPUコアのコストが下がる」というのは、そもそも従来の発想とは真逆の考え方だと思います。CPUは貴重だし、処理能力も高い。よって、割と単純な単一タスクだけでは割が合わないので分け合いましょうというのが、今までの流れです。汎用機時代のTSSや、現在の仮想化技術も同じコンテクストにあるでしょう。

翻って見れば、ムーアの法則の限界は、コア出力の向上の終焉になります。他方、確かにストレージメモリーの技術は進化が進んでいます。この半世紀はCPUコアの出力の伸びに対して、ストレージの向上は相対的には微々たるものでした。まぁ、そのストレージがメモリー並のパフォーマンスになるまで向上するのであれば、今後の考え方にも影響があるでしょう。

その意味では今後主流になるアーキテクチャがバス周りやストレージ周りを強化する方向に倒れるというのは、必然で（代表的なものがRSAみたいなものですね。）、かつ、そのときにコスト構造のコアがNVM・SCMである、という読みは多分正しいと思います。確かに高いですよ。むしろCPUは安い。

データの有りようも、基本的に「Small Big Data」のような感じになっているのがまぁ常識になっている現状で、この中でSCMを考えるのであれば、なるほど、どうコストを回収できるように使い倒すか？というのは考え方としてはアリでしょう。

ど安めのストレージにだらだらデータを放り込んだところで、結局、利用する場合は絞ってレイテンシー勝負になるのは、もうその辺にいくらでも転がっている話です。テープの代わりにDiskを使って適当にクレンジングしたあとはSCMにベースをおいて、スピード（レイテンシーもスループットも）勝負という図式は、特にビジネスのレスポンスを上げるという意味では普通に考えることでしょう。

この進展の場合、いろいろポイントがあると思います。

1.基本的にミドルとアプリの問題はでかい。

まず、現時点でSCMをきっちり使い倒すミドルウェアがないですね。一応、この手のバス強化の話の研究は死ぬほどあり、どの実装も工夫はしていますが、現実にパフォーマンスが一気に1000倍あがるというような場合は、既存のものは全く役に立ちません。ので、いろいろ再検討になります。使えなかった方式が復活したり、新しく別のコンセプトが出てくると思います。当然、ミドルは全面見直しです。アプリレイヤーからさらに、という話であれば、現状ではあまり現実ではないと思います。

ミドル屋から見るとこれは相当危なっかしい話にも見えます。この手のアーキテクチャはいままでの通例だとH/W依存が高いので、結果アプライアンスや特定パッケージにソリューションが集中するようにも見えます。この場合、ユーザサイドから見た場合は、あまり選択の余地がない可能性にもなると思います。アーキテクチャの大きな曲がり角では、主導権争いは常に起きるものですが、どうなるかはちょっと見えない感じです。

普通に考えるのであれば、まずは小回りの効く割と単純な仕組みで、まずは組み上げて、うまく特定のアプリケーションに乗せる、というのが一番近道には見えます。ツボにはまれば凄まじいパフォーマンスをたたき出す「システム」が構築できると思います。（それが構築仕切れないユーザーは、ウン十億払って割と中途半端なアプライアンスを買う羽目になるかな？）

2.DCの問題はある

既存のDCでは問題になると思います。オンプレで個別に構えている場合は、まぁこの手のアーキテクチャの変更は、ある意味エイヤでやれますが、特にクラウドになってくるとそうは行かないでしょう。

まぁ単純に超速いIO（桁が3っつ違う）が提供されて、それをうまく共有化できる仕組みができて、その上でサービス化（たとえばDB）されれば、ま、普通にそっち使うだろうって話です。単価が高いのでどう使い倒すかが鍵になるでしょう。

ある程度、資本力の差がでるかな、と思います。既存のハードを相当一気に入れ替えることができないと、「入れかえることができるクラウドベンダー」に対して、価格どころか、そもそもユーザに提供できるパフォーマンスが、おそらく平均で2-3倍は違うということになるでしょう。これは厳しい。しかもハードを単純に入れただけではペイしないので、うまく使い倒すミドルを開発？する必要が出てくるでしょう。（某国のクラウドベンダー群の実態を見る限り、これは絶望的に厳しい）

3.　いずれにしても

それなりに課題があるので、そうそうすんなりいかないと思います。ただし、数十年にわたって、ITを縛り続けてきたムーアの法則、というかムーアの呪いが、解けた現在、その影響は普通に考えて地殻変動なみに出てくるだろうな、と思います。これもその流れの一つだろうなとは思いますし、その意味では注意はしておきたい。

奇しくも、データ爆発の流れで分散処理やクラウド的なものが一般化（というか精神的なハードルが下がった）し、同時期にムーアの法則が終焉しているという事情は、汎用機→オープン化に続く、大きなパラダイムシフトの幕開けと見て、それほど間違いではないでしょう。

そんな感じ。

Multi-version Conflict Serializability

1.目的

今後の分散DBでは、前提が分散ノードから分散コアに主体が移る。ムーアの法則の限界は、メニーコア化とノードの高密度化を推し進める。分散のノードではリードロックの問題とノード分散の相性の良さでSnapshot Isolation(以下SI）がほぼ前提であったが、RDMA等のハードウェアの技術革新でレイテンシーが改善されるのであれば、SILOのような(表面上は）単ノードのS2PLの改良版も有りになってくる。

そうなってくると理論的な背景も、SIを前提という話ではなくて、通常のConflict Serializability (以下CSR)も頭に置きながら話をおっていかないと理解が厳しい。

SI「だけ」であれば、なんとなくまぁセオリーでr-w依存での循環グラフだよね、ということを前提において議論を追いかけて、r-w依存はあとで復習して調べとけばなんとかやり過ごせる。が、通常のCSRも混線してくると、そもそもなんでr-wなんだっけということが、スルッと出てこないといちいち話を巻き戻す形になって、議論についていけなくなる。要するに途中でわけがわからなくなる。

結論から言うと、SIの理論はmulti-versionになっていて、Multi-version View Serializability (以下MVSR )が下敷きになっている。なので、conflictはr-wの話になる。その一方で例えばSILOのようなものは一見するとr-wのconflictの話をしているように見えるが、実際は通常のCSRでの延長で話をしている。そのためにS2PLが持ち出されているし、そこで決着をつける形になっている。(ただしSILO自体はそんな単純な話ではないので、それはまたあとでまとめる）

実装はCSRでもMVSRでも両者ともどもエッジグラフでのvalidationになるので、結果としては「同じ」read-setとwrite-setのintersectionの話になっているところがややこしい。やっていることは似ているが、導かれているクライテリアは異なるということだ。(大抵の教科書はCSRまでの定式化までしかしないので、その理屈だけで行く人が多いと思うが、そうなると議論についていけなくなる。)

なので、SIをserializabilityの議論のなかで、しっかり定式化して置く事が肝要になる。これを身につけておかないと、今後のTx系の論文の深いところの理解は覚束ない。ので、ちゃんと整理しておく。

2.Multi-versionでの serializability
multi-versionのserializabilityは、通常の単一スケジューリングのserializabilityとは異なる。通常の単一スケジューリングでは、CSRが基本になるが、multi-versionでは、VSRすなわち、View Serializabilityが基本になる。SIの話にしろ、なんにしろ、multi-versionの話になったときに、correctnessのクライテリアはVSRですよね、とガツンと路線を切り替えないと話が脱線する。

特にVSRの場合、read-fromの依存関係がserializabilityのキーファクターであり、これは「どのreadが結局はどのバージョンのwriteを読むか？」ということに依存することを考えれば、multi-versionのコンテクストでは、CSRよりはむしろVSRのcorrectnessのクライテリアに近い事は容易に想像できる。

multi-versionでのserializabilityは、通常multi-versionでのconflict serializability、すなわちMulitiversion Conflict Serializability（通常MVCRと略する）のことをさすが、このconflict serializabilityは、通常のCSRのスケジューリングのconflict ではなくて、VSRでのconflictの延長にある。通常のCSRでのconflictは w-w w-r r-wの三種類になるが、MVCRではr-wだけになる。これはVSRの延長から来ていることによる。

以下表記は、ri(xj)は、transaction iにおいて、verion jのxをreadするということを意味する。wi(xi)は自明であるが、mono-verisonと区別するためにxiを記述する。なお、順序は全順序が前提。

3. MVSRの定式化

3-1 version order と mono-version

version orderとはそのversionが作られた順番そのものではなく、serialization orderを決定する際に利用される、各書き込まれたversionの順序をさす。

mono-version とは単一のバージョンによるmulti-versionのスケジュールをさす。要するに普通のスケジュールになる。multi-versionでreadが直前のupdateのversionを読む制約を加えるとmono-versionと同じ属性を有することになる。multi-versionにおいて、read-fromの依存関係を維持したままで、各operationをスケジュール内で交換し、mono-versionに投影した時にserialなmono-versionのスケジュールを作る事ができれば、それはserializableということになる。

3-2 Serializability

判定はMulti-version Serialization Graph (MVSG)を利用する。このグラフはread-fromの依存関係からtransactionの依存グラフ(dependency graph)を作成し、そのgraphが非循環かどうかで判定する。非循環の場合はトポロジカルソートにより、serialなスケジュールを作る事が可能になる、というかできるはずという事になる。

MVSGのグラフのエッジは以下の条件により作成される

あるxについて、wj(xj), rk(xj), wi(xi)を想定した場合、まずrk(xj)があるので、
1. tj->tkの依存エッジが必ず存在する。
2. xi->xjのversion orderの場合
wi(xi)->wj(xj)が存在し、よってti->tjのエッジが存在する
または
xj->xiのversion orderの場合、
wj(xj)->wi(xi)となり、そもそもwj(xj)->rk(xj)であるので、xj->xiならば、必ずrk(xj)->wi(xi)になる。
よってtk->tiのエッジが存在する。

4. MCSRの定式化
MVSRのサブクラスになる。グラフがより簡易になるので、整理しやすい。
ややこしいのは、MCSRは以下の通りSIとは異なる。なので、ここでは本筋ではないが附随的な議論として置いておく。今後MCSRがロジックとして持ちだされた場合に必要なので、その理解のために整理しておく。

MVSRのサブクラスとして、MCSRを定式化する。
これはMVSRのdependencyをさらに簡潔にする。dependencyとして考慮するのは、rk(xj)->wi(xi)だけになる。MVSRの依存が、wj(xj), rk(xj), wi(xi)で判断することに対して、wj(xj)を判断しない形になる。まぁ、rk(xj)があるということは、wj(xj)が先行している（はず）と考えておく。先行していない場合は初期値(すなわちj=0）を除けば、そもそもスケジュールとして成り立たない。

なお、このグラフをMulti-version Conflict Graphといい、このグラフが非循環の場合をMulti-version Conflict Serializable といい、通常MCSRと称する。

直感的な説明は以下

1.そもそもwi(xi)-wj(xj)がなぜ依存関係ではないか？
これは後続のreadの対象の問題であるので、別段、xiとxjになんらかの関係があるわけではない。（これはMVSRも同じ）

2.wj(xj)-rk(xj)がなぜ依存関係ではないか？
仮にrとwを交換しようがしまいが、version orderには影響がない。よって、依存関係があるわけではない。そもそもスケジュールで読めていたということはread-fromが成立しているということなので、そのようにverison orderを維持することが可能だ。
（厳密にいうと、readの前に既にwriteがあるので、r-wに交換しても それがserializableならば そもそもw-rもserializable になるはず。readできる選択肢は交換することで減る。）

3.rk(xj)-wi(xi)
r-wについては、仮に交換すると、rの前にwを持ってくることになる。この場合、交換前のversion orderと異なるversion orderを「強制的に」つくることができる。要するに”壊す”ことが可能になる。読めるversionを「追加」することになるので、後続readでいくらバージョンを指定しても、事前にあったversion orderを、交換後の操作で上書き(versionではなくてversion orderの上書き）する事が可能になってしまい、version order自身を維持（というか担保）する事ができない。よってconflictになる。

2017/7/29追記：正確にいうとversion orderを維持したスタイルでのserializablityの確保のプロトコルをとった場合に、である。version order自体は可変であるので、別のversion orderをとってかつGraphが非循環になるのであれば、問題ない。ただし、その判定がかなり面倒なので、version orderを維持するため（すなわち”壊す”ことができないように）順序を維持する、という言い方がより正しい。

ただし、abort検出の際にMVSRにできるがMCSRではないものを擬陽性で検出するリスクはある。wi(xi)wj(xj) rk(xj)の形が取れて、かつそもそもversion orderがserialに作れれば、MVSRになり、実際はserializableになる。これは、MCSR＜MVSRの例。（偽陽性といえば偽陽性ではあるが、これは判定コストの問題をどう考えるかによる。）

（なお、個人的感想だけど、この部分のちょっと（かなり）わかりづらい。Tx本の解説でも本自身が認めている有様だ。この部分に関してはグレード的には辛めに見ても5.13はあると思う。とほほ）

5. SIの定式化

1.各readに対するversionの割当は当該readのTxが開始される時点で、最も最近にコミットされたwriteのものを割り当てる。
ri(x) mapped wj(x) であるときに
wj(x)＜cj＜bi＜ri(x) かつ（ wh(x)＜bi and cj＜ch＜bi ）であるwh(x) chは存在しない cはcommit bはbegin

2.二つのconcurrentなTxのwrite setは交わらない
任意のtiとtjについて、bi＜bj＜ciまたはbj＜bi＜cjであれば、tiとtjは共通のobjectについて書き込みをしない

SIはmulti-versionである。「あるreadに対して特定のwriteのversionの割当を行う」という意味でSIがMVSRの特殊ケースである。ではあるが、SIはMVSRよりもwrite-setの交差を制限するという意味でより制限的である一方で、MSVRで要求されるread-fromの要件、すなわち該当するserialな単一versionでのスケジュールでのread-from（w-rのconflict）との互換性は、要求されない。この点でMVSRよりも制限的ではない。これらの意味で、非互換である。

依存グラフすなわちSnapshot Isolation Serialization Graphは以下に定式化できる。

1.すべてのrj(xi)について ti->tj

2.すべてのrk(xj)とwi(xi)について
ci->cjであればti->tj
cj->ciであればtk->ti

ここでMVSRと比較してみる。

1.についてまったく同じである。これはmulti-versionに共通のconflictである。

2.SIではcommit orderであり、MVSRではversion orderであるので、本来であれば別物であるが、
MVSR: xi->xjであればti->tj　または xj->xiであればtk->ti
SI: ci->cjであればti->tj または　cj->ciであればtk->ti

readしたものを後続（ここの後続の意味がSIとMVSRで違う）の別のTxがwriteする場合は、readのTxとwriteのTxでの依存関係が発生し、commit orderまたはversion orderが逆順の場合は、write Txとread するversionを書いたTxについての依存関係が発生するという意味では同じである。すなわち、メタレベルのセマンティクスは同一であることがわかる。

6. まとめ
以上のように、MVSR/MCSR/SIのserializationには、一定の共通したセマンティクスがあることがわかる。これは単一スケジュールのCSRとは別物であることも明快だ。今後MV系のTx処理が展開される場合には、この路線の上で議論はまずまちがいなく展開されるだろう。（逆にこれがわからないと話にならないと思うので、なんか分散TxでMV系の話が合わないなと感じたら、このブログを参照してもらえばいいかもしれない。ほんとかよ。）

上記のように、SIといってもMVSRと交差するコンセプトであり、かつおそらくMVSRの方が広い。証明はともかく、直感的にはcommit orderを考慮しない方がconcurrentなhistoryの選択の余地はある（と思う）ので、例えばLTT(long-time transaction)とSIの共存にMVSRを取れば、変なlockをとらなくてもserializableにできる可能性もあると思う。可能になればDBの使い勝手は非常に広がる。このように現行のDBは最先端であっても、まだまだ発展途上で有ると思う。transactionはベースが数理論理学なので、理論的には可能だがまだ道が発見されていない、または発見された道が割とイマイチ、というものが簡単に見つかる。個人的には本当に興味が尽きない。

なお、上記の元ネタはほとんどが、Tx本なので、そこを参照してもらえればよいけど、MVが5章で、SIが最終章なので、鬼の3-4章を突破して、さらに最後まで読まないと無理なので、がんばってください。白状しますと、なんとか3-4章はクリアした後の、5章の特にMCSRの下りは初見では、「まったく」理解できませんでした。あの部分は本当に難しいと思う。あそこがオンサイト一撃（フラッシュは駄目よ）の人は、間違いなく一種の才能があるので、ウチで採用するので連絡ください。まじで。