multi-versionの基礎
multiversionの基礎
自分用のMulti Version Concurrency Controlのまとめ
MVCCの基礎理論をまとめておく。今後はここを参照する。
基本的にTX本とCC本から必要な部分をまとめている。
（一回まとめてるけど、Multi-version Conflict Serializability - 急がば回れ、選ぶなら近道
前回はそもそもCSRとの混線を防ぐという意味だったので、今回はもっと基本的なところからさらに。今回はCSRとの関係はガン無視。）
前置き：自分の考えを記録的に
基本的にMulti Version Concurrency Control （以下MVCC）は理論先行だった。これはMVCCのオーバへードがsingle-versionのパフォーマンスを凌駕できなかったことによる。以下の理由によりMVCCが今後は伸張すると考えている。
1.メモリーの進歩と低コスト化
特にメモリーの大容量化と高密度化が大きい。これによりIn placeの相対的なメリットが落ちる。single-versionの方が効率がよい、という前提がなくなりつつある。In placeは資源の効率的活用という意味では有効だが、前提が崩れると不必要に面倒な実装ということになりかねない。メモリー資源が貴重でなれければ、どかどかページの更新を書き足していくだけという手法も検討に値する。なお、当然GCもあり方を変える必要があると思う。より簡略化される可能性が高いと個人的には想像している。
2.Single-versionの限界
現在の分散OLTPでは、MOCC/Foedusに見るように、Single-versionの仕組みではabort率の高止まりが壁になっている。エンジニアリング的手法で乗り切るという考えかたも見られるが、single-versionの無駄（validation時点での偽陽性）が許容限界に近づいているともいえる。serializableの点から言うと、scheduling powerそのものは間違いなくMVCCの方が上で、そもそもabortが少ない。その意味ではMVCCのメリットが大きくクローズアップされると思う。
MVCCとsingle-versionの根本的な考え方の違い
端的に言えば、single-versionはin placeだ。“したがって”writeの競合が最大の課題になる。readについては、選択の余地はなく、直前のwrite(コミットの有無にかかわらず)を読むのみであり、検討課題には基本的にはならない。対して、MVCCはin placeではない。writeの競合はハナから問題ですらない。その代わりreadについては、どのversionを読むか？という選択が発生し、最優先に検討すべき事項になる。結果両者で理論のフレームワークが異なる。
1.“Read From” Relation(以下RF)
まず、RFを定義する。これはどのreadがどのwriteを読んでいるか、ということを表す。
Read from Relation
RF(m) := (ti,x,tj | rj(xi)∈op(m))
すなわちhistory m に含まれる手続き、でかつtransaction（以下tx） jに含まれるreadが、tx i で生成されたxを読む、ということを意味する。同一tx内部のwriteは当然readできるものとする。この場合は特にRFでは定義しない。
2.View equivalence
RFによりviewが生成されるので、同一のRFが存在するhistory間では、viewの互換があるものと考える。これをView equivalenceとする。
View equivalence m to m’について、RF(m)= RF(m’)が成立
Serializableを導入する。基本線としては、serialなスケジュールと同一のviewが提供できるのであれば、すなわちview equivalenceであれば、それはserializableである。これは一般的にView Serializableといい、VSRと称されることが多い。
ここで、multiversionに拡張する。
multiversionの定義として
Let T = {t1, . . . , tn} be a (finite) set of transactions.
1. A multiversion history (or complete multiversion schedule) for T is a pair m = (op(m), ＜m), where ＜m is an order on op(m) and
(a) op(m) = h(∪i=1→n op(ti)) for some version function h (h has been canonically extended from single operations to sets of operations)
：すべてのopはなんらかのversionに割り当てる。
(b) for all t∈T and all operations p, q∈op(t) the following holds: p ＜t q ⇒ h(p) ＜m h(q)
：同一tx内部ではop順はversion順
(c) if h(rj(x)) = rj(xi ), i != j, and cj is in m, then ci is in m and ci ＜m cj .
：なんか読んでいるとすれば、読まれているものが先にコミットされる（注意：されているではない）。
2. A multiversion schedule is a prefix of a multiversion history.
multi-versionでのserializability：
自分のスケジュールと、同一のステップで構成される「serial」な「monoversion」において、同一のRFがある場合、（正確には、自分のスケジュールのステップを利用して、RFが同一な「serial」な「monoversion」を作成することができる場合、かつそのときに限り）、その自分のスケジュールをserializableあると言う。これを一般にmultiversion view serializableといい、MVSRと略す。
この「serial」な「monoversion」のserialになるtxの論理的な順序がserialization orderになる。後述するがこれが、multiversionのversion orderに一致する（corollary）（正確には一致ではなく包含が正しい）
以下：mono-versionの定義と、RFについて補足をしておく
◇monoversion
直前のwriteされたものを読むこと（コミットの有無は関係ない）。versionは全部dropしている。
・直前の定義はなにか？version orderに乗っ取った直前のもの、という意味ではないか？
そうではない。単純に直前のwrite stepを見る。具体的なMVTOを見ると、version orderに乗っ取ったものにする、というように見えているが、これはプロトコルの結果による。コミットの有無、すなわち、コミットのオーダーになるときもあるがそれはプロトコルによる。単純に直前のwriteを読むという理解でよい。serialなmonoversionということであれば、普通にコミットのorder（場合によってはversion order）になるのは結果であって、定義ではない。
◇RF
そもそもRFとは何か。基本的に単純にviewである。ただし、そのviewの結果が「どう使われるか」で拡張ができる。
・読んだ結果、何らかの値を書いた場合（同一txでなんらかのwriteが発生。なお、別段読んだ値を上書きするとは限らず、なんらかの値を書く場合）、これをusefulとする。
・さらにusefulなRFにおいて、その影響の結果が最後のDBの状態にまで影響を及ぼす場合（すなわちRF-usefulのclosureがtx∞まで及ぶ場合）、これをaliveとする。逆に、その影響の結果が最後のDBの状態に影響を及ぼさない、すなわち当該txが書いた値をまったく別のtxが上書きされる場合、これをdeadとする。
usefulの概念はDBそれ自体に影響を及ぼすことを意味する。単に読んだ「だけ」ではDBの内部には影響はない。もちろん外部での影響から見た場合にはそうではない。DBの内部の状態に着目し、あるhistoryについて、usefulなRFのうち、aliveなものだけのRFがserialなhistoryと互換である場合、そのhistoryをfinal state serializableといい、FSRと称する。すなわち VSR-dead useful RF=FSRとなる。RFについて全部の互換をとる必要はなく、usefulでかつaliveなのものだけの互換をとればいいので、当然FSRの方が、VSRよりスケジューリングパワーは強い。
anomalyからの補足として
FSRではlost updateは排除可能。最終的の書き残るページについてのコンテクストが変わるので。
r1(x)r2(x)w1(x)w2(x)c1c2→これはFSRではない。w0(x)r2(x)w2(x)がaliveなusefulRF（以下LRF）
t1t2 r1(x)w1(x)r2(x)w2(x)c1c2 w0(x)r1(x)w1(x)r2(x)w2(x)のLRF
t2t1 r2(x)w2(x)r1(x)w1(x)c2c1 w0(x)r2(x)w2(x)r1(x)w1(x)のLRF
どれとも一致しないので、FSRにはならない。
ところがinconsistency readは排除できない
s=r2(x)w2(x)r1(x)r1(y)r2(y)w2(y)c1c2 で LRFは w2(x)r1(x) w0(y)r2(y)w2(y)
t2t1 r2(x)w2(x)r2(y)w2(y)r1(x)r1(y)c2c1 LRFは w2(x)r1(x) w0(y)r2(y)w2(y)r1(y)
で同じセマンティクスよってFSRが成立。FSRのセマンティクスだとserializable
しかし、r1(y)は sではw0(y)からで、t2t1ではw2(y)なので違うものを読んでいる。
sのFSRでは、w0(y)r1(y)r2(y)w2(y)だけど、w0(y)r1(y)がw2(y)で上書きされるので、dead stepであり、LRFにカウントされない。FSRは書いて（含む初期）読んで、その状態が最後まで影響するか、または、読んでそのtxで書いてその状態が最後まで影響した、もののみ意味があるとカウントされるので、途中のリードで、その結果が最後に影響しないものは考慮されない。すなわち、読みのコンテクストが違っても、結果に影響がでなければ、正しさの判定には影響しない。なので、inconsistency readは排除できない
つまりFSRは現在のanomalyベースの考え方では有用ではない。何を読もうが最終の状態とそれにまつわるコンテクストが保存されればよい、というsemanticsであれば意味がある。その分スケジューリングパワーもある。一般に VSR⊂FSRである。差分の例は上記の通りのinconsistency read等になる。
multiversionにおけるFSR
上の結果からいうと簡潔で、multiversionにおいては FSR＝VSRになる。要はdead stepの扱いの違いにある。multiversion においては上書きは常に別 versionの生成になる。すなわちdead stepが存在しない。よってFSR＝VSRになる。言ってみれば MFSR=MVSR。
MVSRについて
・従来からのAnomalyの排除
典型なanomalyとして lost update, inconsistency read, dirty read, write skewで検査する。直感的どれもRFはserialなものとは互換性はないだろうな、というのはわかる。うざいけど、どの教科書にもないので、sanitization的にやっておく。 （まぁ言って見ればANSI SQL92 Critics のMVCCバージョンだ）
lost update
S=r1(x)r2(x)w1(x)w2(x)
RF: w0→r1 w0→r2 w2→r∞
t1t2 r1(x)w1(x)r2(x)w2(x) RF w0→r1 w1→r2 w2→r∞
t2t1 r2(x)w2(x)r1(x)w1(x) RF w0→r2 w2→r1 w1→r∞
まったく一致しない。よって検出可能。
inconsistency read
S=r2(x)w2(x)r1(x)r1(y)r2(y)w2(y)
RF x:w0→r2 w2→r1 y:w0→r1 w0→r2 w2→r∞
t1t2 r1(x)r1(y)r2(x)w2(x)r2(y)w2(y) RF x:w0→r1 w0→r2 w2→∞ y:w0→r1 w0→r2 w2→r∞
t2t1 r2(x)w2(x)r2(y)w2(y)r1(x)r1(y) RF x:w0→r2 w2→r1 y:w0→r2 w2→r1
上の順序だとyは一致するがxが不一致、下の順序だとxは一致するがyが不一致。よって検出可能
dirty read
S=r1(x)w1(x)r2(x)w2(x)a1c2
RF w0→r1 w1→r2 w2→r∞
t1t2 r1(x)w1(x)a1r2(x)w2(x)c2 tx1はabort RF w0→r2 w2→r∞
t2t1 r2(x)w2(x)c2r1(x)w1(x)a1 tx1はabort RF w0→r2 w2→r∞
abortされたものを読むRFがオリジナルにあるので、これはserialになれば存在しない。よって検出可能
write skew
S=r1(x)r2(y)w1(y)w2(x)
RF x:w0→r1 w2→r∞ y:w0→r2 w1→r∞
t1t2 RF r1(x)w1(y)r2(y)w2(x) RF x: w0→r1 w2→r∞ y: w1→r2
t2t1 RF r2(y)w2(x)r1(x)w1(y) RF x: w2→r1 y:w0→r2 w1→r∞
一致しない。よって検出可能。
正直、まぁそうだろうなというのは直感的にわかる。anomalyはほぼviewの誤謬によるものになることを考えれば当然とも言えるからだ。余談だが、これはそもそもMVSR以前のVSRレベルで排除できる話なので、例のANSI SQL92 Criticsの整理も当時は仕方がないとはいえ、RFをちゃんと定義していれば普通に整理できた話ではある。そのanomalyの残滓を現状のRDBは引っ張って、いわゆるIsolation levelの定義があいまいなまま、すなわち formalizeされないまま、残っている。個人的には非常によろしくないと思っている。現状のDBを利用したインテグレーションでは、Isolationレベルの設定が「よくわからない」ために、まずパフォーマンスがでるレベルとしてread committedあたりを適当に設定して、なにかと面倒なところは個別にlock制御をアプリ側で行う（実際は2PL）ということが多いように見受けられる。やる気あるのか。
・MVSRそれ自体について
・VSR⊂MVSR
これについては異論はないと思う。VSRが単一のversionのみを参照制約があるのに対して、MVSRはより広いversionを参照することができるので、スケジューリング・パワーが広いことは自明だ。証明は簡単なの省略する。逆向きの反例はm = w0(x0)w0(y0)c0r1(x0)w2(x2)w2(y2)c2r1(y0)c1 MVSRだとt0＜t1＜t2でserialize可能だが、VSRではr1(y0)がr1(y)になってしまい解決できない。
・VSR/MVSRの問題点
まずVSRの問題点だが、判定の一般解がNP完全になるということだ。まぁ普通に考えてもグラフの総当たり作戦になるのでアウト。ということはより制約が緩いMVSRは少なくともNP完全同等であることが容易に推定できる。ということで、MVSRはほぼ無敵のツールではあるが、その一般的な判定手法は、結局無理ゲーになる。（厳密にはVSRの判定はPolygraphの非循環の検出問題になる。）
なお追加だが、VSR系の問題点として、monotonicではないことが挙がるが MVSRでは当たらない。さらに、そもそも実装上はone-shotリクエストが前提であれば、さらに問題にならない。
一般解は無理ゲーなので、ある程度制約をつけて、heuristicに持っていきたいので、もう少し定式化をする。
Serialなmonoversionで同じRFのものがあれば、mはMVSRにはなる。ただ、これだけだと判定がNP完全なので・・・
(wi(xi), rj(xi))において ti→tj)のグラフGを考える ここでのconflictはRFなので w-rのみ
m ≈v m′→ G(m) =G(m’) ただし逆は成立しない。
これを定式化して、version orderを導入する。
■MVSG
スケジュールm version order ＜＜ において conflict graph G(m)をつくる(MVSG)
Vertex：Tx Edge：Tx→Tx
rk(xj ) and wi (xi )で if xi＜＜xj , then (ti, tj ) ∈ E, otherwise (tk, ti ) ∈ E.
m∈MVSR iff there exists a version order ＜＜ such that MVSG(m ＜＜) is acyclic.
注意：MVSGの引数がm(RF)と＜＜(version order)。よってグラフのedgeは「二種類」存在する。RFによるedgeとversion orderによるedge。
MVSG非循環であるようなversion orderがあれば、そのスケジュールmはMVSRである。（そしてそのときに限る）すなわち、mとおなじRFをもつ、serial monoversion historyが存在する。留意すべきはversion orderは単一ではない、ということだ。あるversion orderではcyclicで、別のversion orderであればacyclicであることはありうる。
・version orderについて
あるスケジュールであるデータが書かれる”論理的な”順序。実行ステップとは関係ない。論理的なserialization orderになる。すなわち、実際のスケジュールからserialなmonoversionと整合的なversion orderがとれればよい。wi wj のステップ順でも wj ＜＜ wiにversion orderをとってもRFについて違いがないようなケースも当然ある。（ただし、ありがちなプロトコルの結果として基本的に各Txの開始時点のtime stampでorderを取ることが多い。この場合は読めるversionについてちゃんと証明することが必要で、それによってMVSRの証明に容易にもってこれる）
注意：補足すると、そもそもversion orderをどうつくるか？という話があって、これはserialization orderのつくりかたと同じ。
考え方としては・・・
1. まず天下り的にtransactionなり commitなりの順序をとりあえずorderとして設定し（ただし普通はTO）、そこにいけるかどうかで判断する方法：実はこれがMCSR（プロトコルだけではそう見えないが、論理的には同値）
2. そうではなくて任意のorderをつくって（つくれればserialなmonoversionができる）と、評価するhistoryで整合性がとれるかトライする方法：これがMVSRの本筋
以上の2通りがあって、それぞれがプロトコル依存になる。広いのは当然後者で、その分計算量が増える。
結局version orderを事前に制約として決めれば、あとの整合性確認はコストが低いが、当然abort率があがる。version orderを広くとれた方が scheduling powerがあるので、abort率は低い。ただし、その分の計算量が増えるし、そもそものversion orderの管理コストが余計にかかる。（この説明はTx本のみでありCC本ではここまで述べていない）
補足すると、たとえば、実行順序がwj(xj) rk(xj) wi(xi)であったとして この場合はmustでtj → tkは必ずdependency (conflict)存在する。（これはRF）
この時、xi ＜＜ xj ならば ti → tj よって ti→tj→tk。このスケジュールのmonoversionが存在するとすればそれは必ずwi(xi)wj(xj)。この場合はtk → ti依存関係の維持は必要ない。すなわちMCSRではない（version orderはxi→xjがmust）
また、xj ＜＜ xi ならば tk → ti よって tj→tk→ti んで、このスケジュールのmonoversionが存在するとすればそれは必ずwj(xj)wi(xi)になる。この場合はtk → ti依存関係の維持が必要であり、すなわちMCSRになる。そしてversion order xj→xiがmust。wj(xj)wi(xi)を維持する必要があって、これはrk(xj) wi(xi)の順序維持で必要。（たとえば、ひっくり返そうwj(xj)rk(xj)とするとwi(xi)wj(xj)rk(xj)になり、version orderがxi ＜＜ xjになる）
大事なのは証明なので ifはともかくonly ifなかなか面倒だが、この定理は例の2PL＝serializableと同じくらい重要。証明はTx本より、Phil.B御大のCC本の方がわかりやすいのでそちらから引く
Theorem 5.4: An MV history H is 1SR iff there exists a version order ＜＜ such that MVSG(H, ＜＜) is acyclic.
dependency(conflict)が循環しないようなserial graphにおいてversion orderが存在すれば、それはserializableで、かつその時に限る。
注：1SR=one copy serializable
Proof: (If) Let Hs be a serial MV history Ti, Ti1..Tin, where Ti1,Ti2,..Tin is a topological sort of MVSG(H, ＜＜).
Since C(H) is an MV history, it follows that Hs, is as well.
Since Hs has the same operations as C(H), by Proposition 5.1, Hs == C(H).
注意：C(H)はcommitted projection
Prop5.1
Two MV histories over a set of transactions are equivalent iff the histories have the same operations.
It remains to prove that Hs is l-serial.
Consider any reads-from relationship in Hs, say Tk reads x from Tj, k!=i.
Let wi(xi) (i!=j and i!=k) be any other Write on x.
If xi ＜＜ xj, then MVSG(H, ＜＜) includes the version order edge Ti -> Tj,
which forces Tj to follow Ti in Hs.
If xj ＜＜ xi, thenMVSG(H, ＜＜) includes the version order edge Tk -> Ti,
which forces Tk to precede Tj in Hs.
Therefore, no transaction that writes x falls in between Tj and Tk in Hs. Thus, Hs is l-serial.
(Only if) Given H and ＜＜,
let MV(H, ＜＜) be the graph containing only version order edges.
Version order edges depend only on the operations in H and ＜＜ ;
they do not depend on the order of operations in H.
Thus, if H and H’are MV histories with the same operations, then MV(H, ＜＜)=MV(H’,＜＜) for all version orders ＜＜,
注意：version orderが所与でoperationが同一ならgraphは一致。一瞬うっ ってなるけど冷静に。
Let Hs be a l-serial MV history equivalent to C(H).
All edges in SG(Hs) go“left-to-right;” that is, if Ti ->Tj then Ti precedes Tj in Hs.
Define ＜＜ as follows:
xi ＜＜ xj only if Ti precedes Tj in Hs.
All edges in MV(Hs,＜＜) are also left-to-right.
Therefore all edges in MVSG(Hs, ＜＜) = SG(Hs)∪MV(Hs,＜＜) are left-to-right.
This implies MVSG(Hs, ＜＜) is acyclic.
By Proposition 5.1, C(H) and Hs, have the same operations.
Hence MV(C(H), ＜＜) = MV(Hs, ＜＜).
Proposition 5.2: Let H and H’ be MV histories. If H== H’, then SG(H) = SG(H’).
By Proposition 5.1 and 5.2
SG(C(H)) = SG(Hs). Therefore MVSG(C(H), ＜＜) = MVSG(Hs, ＜＜).
Since MVSG(Hs, ＜＜ ) is acyclic, so is MVSG(C(H), ＜＜), which is identical to MVSG(H, ＜＜).
■MCSRの定式化
rwのdependencyのみでconflict graphをつくる。すなわちri (xj )のwk(xk) ステップについて、ri (xj )＜m wk(xk)の依存関係をconflictとする。このrwのコンフリクトが、同じ順序で出るmonoversionができればMCSRになる
s = r1(x0)w1(x1)r2(x0)r2(y0) w2(y2)r1(y0)w1(y1)c1c2
version order x t0→t1 y t0→t2→t1 r-w：r2(y0) → w1(y1) 当然yのversion orderは t0<<t1
s’= r2(x)r2(y)w2(y)r1(x)w1(x)r1(y)w1(y)c1c2
r-w: r2(y)→w1(y)さらにr2(x)→w1(x)のconflictが発生するが、t2→t1で元のスケジュールと互換なので問題ない
ちなみにri (xj )<m wk(xk)について、そもそもmultiversionとしての成立条件、すなわち、ri(xj)でciが存在するのであれば、cj<ciがあることに留意する。
例えば、s“ = r1(x0)w1(x1)r2(x1)r2(y0)w2(y2)r1(y0)w1(y1)c1c2 としてみると（せっかくなのでconcurrentに走って先行しているt1のxの書き込みをt2で読むとする）
version order x t0→t1 y t0→t2→t1 r-w：r2(y0) → w1(y1)
serial monoversionで r2(x)r2(y)w2(y)r1(x)w1(x)r1(y)w1(y)c2c1
r-w r2(x)→w1(x) r2(y)→w1(y) なので、t2→t1で成立するように見える、が
このmonoversionでr2が読んでいるのはx0なので、そもそもx1を読んでいたもとのversionとは異なる。これはr2(x1)が存在する段階で c1<c2がhistoryとしての成立条件になるので、t1→t2が必須になるので成立しない。尚、sの場合はそれがないので、t2→t1でもよい。
・MCSR⊂MVSR
上記のとおりで、MCSR→MVSRは特に問題はない。RFの互換性がある。
MVSR→MCSRではない例を示す。これはMVSRであるので本来はserializableではあるが、MCSRではそうではない。すなわち偽陽性になってしまう。
s = w0(x0)w0( y0)w0(z0)c0 r2(y0) r3(z0)w3(x3)c3 r1(x3)w1(y1)c1 w2(x2)c2 r∞(x2)r∞(y1)r∞(z0)c∞
この場合で、r1(x3)w2(x2)について x: t1→t2になっている。他方、r2(y0) w1(y1)なので、 y:t2→t1になる。よって、monoversionが成立しないので、sはMCSRではない
ただしこれはversion orderからみると
version x t0→t3→t2 y t0→t1 なので、t0→t3→t2→t1→t∞でそもそも問題ない。
version orderを選択することで、MCSRでのconflict x t1→t2の依存関係を排除することができるはず。
実際、s’ = w0(x)w0( y)w0(z)c0 r2(y) r3(z)w3(x)c3 r1(x)w1(y)c1 w2(x) c2 r∞(x)r∞(y)r∞(z)c∞ で問題ない。要は、MCSRではコンフリクトだがMVSRではそうではない。
翻って見るに、MCSRでは判定にversion orderは直接触っていない。tx orderのみで判定している。したがって実装上はより簡易に処理することができるが、その分狭くはなる。本来のmultiversionのパワーを完全に生かすのであれば、やはりMVSRが望ましいのは間違いない。かつ通常のVSRよりもよりスケジューリングパワーがあることは間違いない。
現実的な実装としてはMCSRでvalidation checkしてアウトの場合はversion orderの変更でいけるかどうかという確認を行うやり方があるかな、と思う。（そんなことよりはback-offのretryで十分だとかいう説もある。）個人的には「でもどうせ読んでないんだから、そのままversion維持やればいいじゃねーの、そもそもそれがmultiversionのいいところだろう。」とは思うんですがね。serial historyの時にread txの後ろに順序できることがわかればそれでおしまいのはず。人間が見れば直感的にわかるので、まだまだ人類の知らない近道があるのは間違いないのだが。
とりあえずこんなもんでMVCCの基礎理論はいいと思う。
「パブリッククラウドvsプライベートクラウドの終わり」の始まり
遅めですが明けましておめでとうございます。そんな感じで。
基本的に社内向け。あとは特定のお客さん向け。
自分の意見を詳記しとく。あとこれは日本の話で、海外の状況は知りません。
■「パブリック」クラウド
ここでは、大規模メガクラウドを指す。よって、AWS・Azureあたりを考えている。国内クラウドとは明確に規模・技術力で差がついており、はっきり分けるべきと思っているので、ここではAWS・Azureとしている。多分SalesforceとかIBMのやつも入るとは思う。Googleのクラウドについては技術はぶっちぎりだけど、一般民間人には意図していること天才すぎて理解できる気がしないので範囲外とする。
基本的に「所有より利用を」コンセプトにし、使いやすさと低コストを全面に打ち出し、トレードオフとして共有故の仕組み/運用の「ある種の不透明性」を要求する仕組み。なお、不透明性ってのは、これは提供者の企業風土の問題もあるが、大規模分散システムの共有化の孕む技術的な課題が本質としてある。なのでトレードオフになる。*1
■前提として
基本的に、自分個人は「クラウド推進派」だ。まぁ可能であればクラウドは利用したほうがよいというスタンスは5年以上変わっていない。
今後の日本では若年層が減少する。結果、トータルで一人あたりのアウトプットは低減する。これをカバーするためには、ITについては運用だとかの守りの部分にはマンパワーを割かずに、より前向きの試行錯誤に人を入れるべきで、そのためにクラウドを利用すべきだというスタンスは変わっていない。
ただし、西鉄ストアさんの基幹をAWSに上げてもう5年以上経過している。そういう意味では5年の歳月で、いままで明確でなかった部分がいろいろクリアになってきた。サポートの話とか監査の話は、そのうちの一つに過ぎない。システムの「在り方それ自体」が以前よりも際立って来たというのが実感として大きい。
単純なロジックとしてクラウドを使いなさいよ、という基本線はあるが、それほど話は単純ではない。結果として、クラウドそのものが変貌してきていることも大きい。
■「パブリック」・クラウドの位置づけ
まず、逆説的だが、妥協的な実際のユースケースから、その中での「パブリック」クラウドの位置づけが明確に掘り下げられつつあると思う。
現状の特にエンプラでのクラウドの使い方は、やはり「Webの置き場」「モバイルへの発信元」「不特定多数との応答の手段の確保」等が主流であり、バックエンドまで含めてクラウドに置くというのは少数派にとどまる。また、バックエンドという意味ではなく、「計算資源の利用で」っていうことでのクラウドの使い方ってのはあるけど、日本市場では「大量データを大量の計算資源を使って分析し、かつそれを利用して直接的に収益を上げる」ということでは成功例はきわめて少ないのでその意味でのユースケースは“まだ”メジャーではない。残念ながら。
すなわち、エンプラマーケットで見たときに「パブリック」クラウドは「インターネット」に対する橋頭保として利用されつつある。ただし、これはある意味、エンプラにおける「インターネット」に対する力点の置き方の結果という、一種の皮相的な、あるいは混迷の結果でもあるとも思っている。
要するに、意図せざる結果として、エンプラでは「パブリック」クラウドは、物理的なNWの位置づけとして「インターネット」に近づきつつあるように見える。閉域網から見た「フロント」であり、その外側をつなぐものとして、という意味で。逆に言うとそれ以上の意味は見いだしにくい。
■クラウド/オンプレの線引きルールの無効化
現実的な有り様から“クラウド”の位置づけが変わりつつあるように感じる。クラウド・オンプレのあり方については、まじめに再検討した方がよい。
クラウドとオンプレミスのそもそも位置づけは「利用による共有」と「所有」という位置づけだったと思うが、よりクラウドが現実的に使われるようになった現在ではこの視点での境界は曖昧だと思う。
どこまでが利用で、どこまでが所有か、という線引きは、多層的なリスク管理の位置づけのなかで間主観的に決められているに過ぎない。これは元来IT資産全般に言える話でもあるが、特にクラウドがその論点の精鋭化を進めていると思う。
・所有の考え方の再整理
基本的に所有という考え方については、その背後には必ず所有による「リスク」が存在する。資産が毀損したりするリスクから始まり、管理維持する責務、資産投資として認識しリターンを獲得する義務、等々のその資産がもたらす幅の広い、一義的には記述しえない義務や権利が存在する。もちろん、投資コストリスクは存在するが、それは一要素でしかない。
IT資産の管理は、そもそも経営資源の管理としては頭の痛い問題であり、できれば所有したくない、という考え方は常にあり、その一方でうまくコントロールすればレバレッジを効かせることができる資産という見方も常にある。ただ一般的には不透明なブラックボックスである、というのはほぼ共通認識であり、さらに昨今のバズワード的ソリューションの伸長は、その傾向に拍車をかけている。
結果として、このブラックボックス化は、IT資産の所有を考えた時に、客観性の欠如に繋がり易いと同時に、IT担当者やベンダーの主観的な取り扱いを超えて、その存在は極めて間主観的なものになっている。要するに、各ステークホルダー間での議論や考え方を通じて、その意味がはじめて浮き彫りになることが多い。
例えば、CEO/CTO CFO/CTO CTO/現場 現場/ベンダー等々、それぞれの場とコンテクストで定義づけすなわち取り扱いが異なる。これは現実によくある話だし、SIの現場では「政治ネタ」と揶揄されるぐらい、場合によっては局所的には矛盾するロジックが普通に転がっている。
・クラウド利用の見通しへの甘さ
所有から利用へ、すなわちオンプレからクラウドへの移行インセンティブは、これらの資産を持つことのリスクの低減だったはずだ。資産管理のコストを含むリスクを減らし、身軽になること。これが狙いだった。この考え方は現在も有効だし、間違っているとは思えない。
しかし、現実にはリスクは低減してない。
そもそも、IT資産の位置付けに対するリスクの複雑さを軽く見すぎたのと、多少の不透明さは許容できるだろうという全般的な甘さ、クラウドの実装が本質的に持つ分散処理の複雑さ、これに加えてメガクラウドの各企業の非公開性の企業風土が相まって、全体的にリスクは減っていない。確かに運用負荷の低減という意味ではメリットはあるが、それ以上にブラックボックス化による結果としての多層性・間主観性の不必要な増大が激しく、結果、意思決定のスピードに影響している。この辺りは、自分も正直見通しが甘かったなと反省している。
こういったオーバーヘッドはできれば排除したいのが実態だ。勿論、いろいろ面倒なので、「使えればいいだけなんだから、トップダウンの鶴の一声決定で進めれば良い」という意見もあると思うが、まぁ乱暴な意見にしか聞こえない。
・透明性というクライテリア
IT資産のあり方として、仮にオンプレミス・クラウドという選択肢を検討するのであれば、可能な限りリスクコントロールが容易な選択をすべきであるし、そうせざるを得ない。前述のように、リスクの増大はステークホルダー間でのストレスを増やす結果になり、さらに組織全体の意思決定のスピードを遅らせる。これはITを簡素化しろという意味ではない。いわんや、シンプルなコンプライアンス云々の課題でもない。
IT全般について言えることだが、今後は一方的にブラックボックス化が進む。ITに関わる人間の今後のミッションのひとつは、一種のリバイアサン化するブラックボックスの透明化という、「かなり旗色の悪いゲームへの強制参加」だ。ビックデータだ、IoTだ、AIだ、クラウドだ、なんだかんだは全部そんな感じだ。要は「要するになんか取り組まないとまずいのはわかるけど、なんかあったら中身がわかるようにしとけよな」って話だ。それは無理ゲーだろ、というのは普通の感覚。仮にそんなことやったらコストが増大してメリットが取れないよ、・・・ということは、“そもそもコストの見積もりが甘かった”ということの裏返しなんだけどね。便利だけど不透明ってのは、実は「便利」じゃないんだよね。多少不便だけど「正確に内容がわかる」方が実はトータルで見ると「便利」だったりする。
すなわち、クラウド・オンプレは所有・利用で区分ではなく、リスク管理の容易性・端的に言えば透明性のクライテリアでの判断になる。その意味では、「パブリック」クラウドの所有から利用という掛け声の隠された前提の「安さと引き換えの不透明さ」は極めてそぐわない。
■ではオンプレなのか？
ということで、透明性という意味ではオンプレミスの資産の方が手元にあるということで透明性が高い。ので、全部オンプレで良いか、というとそういう話でもない。
・調達コストの増大
もはやPC/タブレット等の端末系の販売は完全に頭打ちで、半導体メーカの大きなマーケットはDCに軸足を移しつつある。結果として、企業が個別にサーバをオンプレミス的に取得するコストはDCレベルでの一括取得のコストに対して一方的に上がりつつある。現状ですでに3倍はあり、今年はおそらく5倍を超える。ここまで調達コストが変わってくると、おいそれと「んじゃオンプレで」という判断もしづらい。DCだと普通に4桁オーダーでの発注はあるので、数台くださいの発注ではそれはコストは全然変わる。
なので、単純なオンプレ回帰か、というとそういうわけにもいかない。
今後は、リスク管理の意味で、クラウド的な調達メリットと、オンプレ的な透明性の確保容易性の、それぞれの要望を併せ持った形態が主軸になると思う。これはユーザ・サービサーの両者の模索の中から生まれてくると思う。
■透明性の確保としてのオンプレ的なあり方の例
透明性という点では、Dedicatedという考え方は一つの例にはなると思う。すなわち占有（専有）だとか、専用だとかいう形で、ユーザに情報・コントロールを可能な限り渡すスタイル。ベアメタルもその一つだろう。限りなく一種のターンキーに近い契約スタイルもこれに入ると思う。所有ほど強いコミットではなく、しかし利用というほどの弱いコミットでもない。占有という形も、そもそも専用サーバにクラウド的な機能を割り当て実現するのか、それともクラウド的なクラスターの一部の専用物理サーバを割り当てるのか、あるいはその両方か。手段は様々だろう。これは、クラウド的な調達メリットと、オンプレ的な透明性の確保の一つの妥協点にはなる。大規模なものだと（多分）VMWare Cloud。外に出ているスライドとかよく見ればわかるけど、あれは「AWS」ではない。AWSの調達能力を活かしたVMWare向けのdedicated cloudにしか見えない。
こういった形態の「サービス」が主流になると思う。このあたりだと所有とか利用という区分はあまり有効でないのは自明だろう。むしろ、「専有って、んじゃーどこまでコントロールできるのか？」のクライテリアの話である。*2
日本のクラウドベンダーは同じようなサービスが展開可能には見える。さくらさんなら、専用サーバとクラウドの混合的なものだし、同じようなサービスはIIJさんでもNTTComでも提供可能だろう。各社ある意味レガシーサービスとして行なっていたところでもあるので、クラウド的な技術を使いつつ、オンプレミス的なサービスを行うというのは、うまく融合できれば面白いとは思う。まぁこの辺は真面目に技術力の話なんで、おいそれとはできないと思うが、ターゲットを絞ればできる可能性はある。*3
要するにあの手この手で、どこもやっていることではある。整理することで時代の要請に合わせたサービスが提供できる可能性がある、ということだ。模索は間違いなく始まりつつある。
■結論的には
ベンダーもユーザも、もう一度「クラウド的」なものを、バスワードやマスコミや一部のベンダーの過剰な露出といったメディア的なものとは別に再評価するべき時期だ。その軸はかなり多層的・間主観的なもので構成されるので、単純ではない。丁寧に整理・腑分けして「あり方」として再認識する必要がある、と思う。
ま、NT的にどうだという意味では、可能な限り透明性を確保しましょうというオチにしかならないけど、単純にメガクラウドは「使いやすいから」ってのはハマりますよってことで、自戒しといてねってこと。クラウドについては、そんな簡単な話じゃねーな、ってのは、ほぼ社内での共通認識だとは思いますが、自分の考えは以上でございます。
以上、ちゃんとした人なら「何を今更」だとは思うが、せっかくなんで書いといた。
*1:トレードオフにならないような大規模分散システムは現人類では開発できていない。
*2:メガクラウドでもDedicatedあるよっていうそういう簡単な話ではなく、それではどこまでメガクラウドのDedicatedはコントローラブルなのか、中身がわかるのか？って話がポイントになる。
*3:念のために言っておくと・・・SI屋さん的には“それやってるもんね”という意見もあるだろう。日本のSI屋がユーザをパブリッククラウドに逃がさないために、苦肉の策で展開している手法。すなわちメーカリスクでサーバを顧客のために準備するが、ユーザはあくまで利用ベースの従量課金を払えばよい、というパターンだ。DCにどんどんサーバを置いて、利用ベースでユーザに提供する。確かにコストスキームだけは同じだけど、ミドルレイヤーについてはまったくお話にならないので、別物でしょう。
Asakusaとメニーコア
アドベントカレンダーのエントリーなんで、軽めに。
AsakusaはもともとHadoopでバッチ処理を開発・実行するためのフレームワークだ。これは別に今でもかわっていない。ただし、実行基盤は増えているし、推奨基盤も変わりつつある。現在のところの推奨基盤はバッチあたりで利用するデータ処理の規模が単ノードで完了するような場合はM3BPで、そうでない場合すなわち複数ノードにまたがるような場合は、Sparkを推奨している。これは僕らが経験した「すべてのワークロード」でSpark/M3BPがHadoopの特にMapreduceでの実行結果を凌駕しているためだ。AsakusaDSLはどのプラットフォームでも完全互換なので、コンパイルし直すだけでそのまま動く。MapreduceからSparkの移行は非常に簡単だ。ということで可能ならSpark/M3BPの方が速いので、そっち方がいいのではないでしょうか、とそんな感じだ。
現状の実際の案件のワークロードは、徐々にM3BPに近づきつつある。これはノード出力の向上による、すなわちメニーコア化の進展とメモリーの大容量化によるところが大きい。この出力の向上はさらに進んで、おそらく来年はノードあたりのスレッド数は100を越え、メモリーも1Tあたりが標準になってくるだろう。
Asakusaだとやはり業務系の処理が多いので、一バッチあたりのデータサイズが1Tを越えるということはほとんどなく、実際の実行は1サーバで間に合ってしまう。ノード間通信もなく、M3BPがメニーコアを使い切り、かつ不要なdiskへの書き出しを行わないので、（逆にいうとOOMだと潔く落ちる）パフォーマンスは非常に出る。8~16コアで64Gメモリーとかそんなスペックのマシーンで8~10時間かかっているバッチが、44コアw/ 512Gとかそんなマシーンで普通に2分で終了とか、そんな感じになる。
これはそもそもバッチの作り方の問題というよりも、現行のRDBMSのアーキテクチャでバッチ処理を行った場合、8~16コアですらすべてをきれいに使い切ることが困難であり、対して、M3BPは現状の物理スペックを分散処理できれいに使い切るので、単純に比例したコア数以上の結果がでることによると思う。コア数が増えてくればこの差はもっと開く気がする。
この状況と今後のハードスペックを見れば、まぁM3BPのようなメニーコアへの移行は魅力的だ。特にAsakusaだと移行といってもリコンパイルだけなので、それほど負荷もない。
さて、それでは今後のメニーコア環境を具体的にどうみていくか？ということだけど、Asakusa的には、これはもう積極的にやっていくという方向になると思う。とにかく処理が速いということとハードの開発がそっちに進んでいるということはやはり大きい。ことバッチに関しては速さは正義で、時間単位でかかっていた処理が、分とか秒とかのオーダーになる段階で、通常のバッチ処理とは違ってきて、なにかと使い勝手が上がる。
で、そういうレンジになると、そもそもデータをどうするって話には当然なる。
■データ層の問題
なので、メニーコア化という話と永続化層をどうするか？ってのは実は今後を見たときに大きい。
確かに現状では単ノードで処理になっているが、処理がembarrassing parallelにできることは多い。この場合、データのpartitioningが行えるのであれば、普通に複数ノードをたてて、片っ端からjobを突っ込むというのはありだと思うし、その辺りは目標にして動きつつある。5-10台程度のメニーコアマシーンでクラスター組んで、さぁデータをどうするという話だ。
・HDFSなのか？
まぁ普通にHDFSという選択肢はある。現状のHadoopの主たる機能コンポネントは、HDFS（またはそのAPI）だと個人的に思っている。YARN云々とか、まぁいろいろあるとは思うが、そもそもHadoopがHDFSとMapreduceのペアリングで支えられていたフレームワークであった過去を考えれば、各distributionもなんか普通にSpark押しになっている現状では、Hadoop本体自体としては片肺状態で、HDFSがほぼレガシー化しつつあるように見える。これは他に代替がない、ということでしかない。要するに分散fsとしては枯れてるから、それ使えばいいでしょって話だ。実際、5-10台程度でもHDFS、ウチのケースだとMapRfsがファーストチョイスにはなっているが、を利用するというスタンスは普通だ。まぁ、これでいいのではないかというスタンス。
ただし、このままメニーコアにすすんで行くと、そもそも大きなノード数はいらないし、HDFS自体も本当にいるのか？ということになる。実際に単ノードで終わるケースであれば、まったく不要だ。
・RDBMSの時代なのか？
単ノード＋α的な話であれば、まぁ普通にRDBMSでしょう、という話はある。問い合わせアドホッククエリーはRDBMSで処理して、バッチ的にデータを作るところではAsakusaという感じの組み合わせになる。まぁそんなにでたらめな感じもしない。そもそもjoinに必要なデータは業務的にはRDBMSに格納されているのが普通なので、合理的ではある。
ただし、メニーコア＋大量メモリーへの対応という意味では、現状のRDBMSは根本的なアーキテクチャで齟齬があり、パフォーマンスが十分に引き出せない。今後を見るのであれば、相当のアーキテクチャの変更が必要であり、その意味では大量の人員や資金を投入できるOracleといった商用RDBMSが、まぁ本命として妥当な感じがしている。OSS系は、外から見ていると機能追加についてはレイムダック状態であることに加えて、アーキテクチャ変更への投入資源が確保することが厳しい気がする。
・第3の選択肢
今後を見るのであれば、分散OLTPが最有力候補だと思っている。言ってみれば、メニーコア・大量メモリーNativeなので、そりゃそうだろう。新しい酒は新しい革袋に。ただし、現在そんなものがどこにあるのか？といえば、現状ではR&Dの内部でしかない。もっとも、どこも必死で実装中で、TPC-Cレベルでは十分パフォーマンスは出ており、場合によってはフライング気味でリリースしてるところもある。要は、開発は進んでいるが、なかなか商用で普通にというレベルではもう少し時間がかかる、という感じだろう。
要するに「明快なベストがない」というのが現状。Asakusa的には、まぁ仕方がないので、ユースケースに応じて採用していく、という考え方しか現状では取り得ない。分散OLTPがそもそもまだできていない状態では、HDFSかRDBMSの二択にはなる。どちらにもしてもAsakusa的な準備はある程度できているので、まぁ無難にということになるけど、まぁ過渡期だよね、というのが本音。会社云々はともかく、自分個人の将来の方向性という意味では、この辺りを見ているということで、来年色々動いていきましょう、という感じですね。
「ソフトウェアの時代」について
まぁなんか適当に思うことを。
■ハードの限界の露呈
ムーアの法則の限界はITのあり方を根本から変えると思う。この四半世紀、ITの現場レベルでは「困ったらハード増強」が一つの基本政策であったことは間違いない。ハードウェアの進歩は結果として、IT全体のパフォーマンスを上げ、結果として社会における有用性を増した。その一方でハードウェアの高進はソフトウェアの進化を止めていた側面は確かにある。
ソフトウェアのレイヤー、とくにミドルレイヤー〜アプリケーションのレイヤーでは、通信にしろ、分散処理にしろ、DBにしろ、OSにしろ、「業界全体としてトコトンできるレベルまでやったのか？」という意味では、実際はやっていないと思う。もちろん、各セグメントではそれなりに追求はしたけど、ドカドカ、金突っ込んで全部ひっくり返すというまでには至っていない。これはIT全体に言えることだけど、ソフトウェアにコストをかけるよりもハードを向上させたほうが費用対効果が文字通り単純に高かったことにつきる。特にエンタープライズとか、業務系とか言われるセグメントでは顕著だ。
現状のソフトウェアは実は、かなり昔からのハードウェアの制約故の制限をそのまま引きずっている面がある。これはこれでメリットはあって、ハードそれ自体の性能があがれば、前提を変えずにパフォーマンスを上げることで急場はしのげる。ただ、結果として「ま、これでいいか」的な話で放置されがちになり、実際放置されてきた。アプリケーションについては、わりと見えやすいのでSIの現場でも割とわかりやすいが、実はミドルレイヤーも同じ事情は抱えている。
今までのソフトウェアの前提というか制約は、「少数の非常に高い高性能のCPUと貴重なメモリー」である。ムーアの法則はこの伸長にストップをかけつつある。少なくともCPU（一コア）の出力は上らない。他方、メモリーの高集約化はどんどん進み、貴重なメモリーは容量的にはそれほど貴重ではない。こんな感じで前提が変わりつつある。
現在、ソフトウェアは前提を変えて「作り直す」ことで、桁違いの性能を出すことが実はできる。その意味では、あまねくITがいきわたったIT依存度の高い（と思われている）現状が「ソフトウェアの時代」ではなく、今からこそが「ソフトウェアの時代」が来る、というか来る可能性がある、というか来ないと先がまったくない。（苦笑
■前提を変えて作り直す？
現状のソフトウェアの前提、すなわち「少数の非常に高い高性能のCPUと貴重なメモリー」の前提、を言ってみれば「覆す」ことは、ミドル以上のほぼすべてのソフトウェアレイヤーにまたがって可能だ。
「コア数は一気に桁違いに増える、メモリーそれほど貴重ではない」という前提変更は、簡単に言えば「限られたリソースを使い切る」ことが目標ではなく「少々パワーロスは問題でない、むしろ有り余ったリソースにどういうビジョンを実現するか」という風に考えることが必要になる。考え方が180度違う。
たとえば、発想変えずに、現状のアプリケーションレイヤーの考え方から無理矢理やるとすれば、現行のままでマルチスレッド化を強烈に推し進めて、disk的な扱いの領域をそのままメモリーに移行するのが関の山だ。動くには動くがパフォーマンスは、想定よりもかなりイマイチな上に、障害発生時には「なんかこれ無理がないか？」ということになる。実際に経験をしている人も多いと思う。漠然とそもそもなんか根本的に間違ってないか？という感覚が普通だ。
要するに、現行のまま単純に使うリソースをどかどか増やすということでは、いろんなところにボトルネックが出てむしろ効率は落ちるので、ビジョンはもちろんのこと、使い方そのものも見直すことが必要になる。
SIオンリーの現場的にはあまりピンと来ないかもしれないけど、実体験的に分散ミドルやメニーコア対応のミドル・アプリから見たときの今の、ソフトウェアの基本的なあり方は、「根本的に合ってないよな〜」の一言につきる。OS・DB・VM・各種フレームワーク・分散制御・・すべてにおいて「そもそも前提がズレまくっている」という印象だ。小手先のパラメーターチューニングでどうにか動かすというのが現在で、いろいろメトリクスとったり、アーキテクチャを見たりすると、もう「そもそも論」になっている。特にプロダクトベースでいろいろやってると顕著に感じる。まぁとにかくコア数が増えても使い切れないし、メモリーも使い方がいろいろ効率が悪い。
仮にこれら全てに手をつけた場合、そのコストはきわめて膨大になる。人・モノ・金のすべての面でリソースが必要になるほどに。まぁ、それが故にどちらかというとソフトウェアを抜本的にやり直すよりも、ハードウェアでなんとか解決という道筋が選択されていたわけなんだけれども。
今後はすぐにメニーコア化＋大容量メモリー化が来て、それでその後にすぐメニーコア化の限界が来て、また多ノード化に進むと思う。ここ10年は、スケールアウト→スケールアップ→スケールアウトの「一見すると円環に見える流れを螺旋のように上がる」進み方をするだろう。どちらにしても「少数の非常に高い高性能のCPUと貴重なメモリー」はもはや「なんの話だ？それは？」という扱いになる。
■コンピューターサイエンスにも影響する。
また、前提変更はそもそも、コンピュータ・エンジニアリングだけではなく、コンピュータ・サイエンスにも及ぶと思う。
現状のコンピュータ・サイエンスは割と実証的になってきていて、純粋理論だけという論文はほとんどない。これがいいか悪いか別として、ある意味、研究自体が既存ハードウェア環境に依存していた。
前提が変わってくると、開発すべきアルゴリズムも変わる。特に実証的であれば、あるほど変わってくる。なるほどビッグデータ的なものだとそもそも環境が大手のクラウドベンダーに限られるので、そもそも研究がやりづらいというところはあるとは思うが、メニーコア・大量メモリーが比較的入手しやすくなると、その流れもかわってくるだろうし、実際変わりつつあるようにみえる。
今後は、新しいアーキテクチャに沿った、よりスマートなやり方・考え方・実装手法が考案され検討されていくことが加速すると思う。その意味では先端系の流れも見ていて損はない。（ただし前提知識が必要になるけど）
■では「ソフトウェア」にどう向き合うか？
そもそも汎用機->オープン化->分散処理/クラウドという大きな変化の波が来ているのは、誰もが薄々感じていることだ。たぶん、地殻変動的なものが来るのはこれからで、クラウド勢(Google, FB, AWS, などなど)は勿論、巨大パッケージベンダーであるOracleやSAPあたりもいろいろ先に手は打っているが、ちょっとこれは・・・と感じているのが現実ではないだろうか。
こういう流れは、ベンダーにしろ、ユーザにしろ、またエンジニア個人にしろ、どんな風にとらえて行くか？が「大きな判断」だと思う。表面上はビックデータ・IoT・AIとかなんかそんな感じのバズワードが百花繚乱になるとは思うけど、その下の地層レベルでは相当な変動がおこっている訳で、それを睨みながら、自分たちの立ち位置を確認して行く事が大事だ。
組織にしろ個人にしろ多少はリスクとって前に踏み出してもいい気がする。これだけ社会が低成長だと、事を起こすってのは博打としては分が悪いのが普通だけど、IT屋としてはベースが変わるって意味ではソフトウェア・エンジニアリングに張るのは、時期としては悪くない。
■エンジニアサイドから見て：
○保険としてのSI
そんな意味づけから見たときに、悪評名高いSIの位置づけも変わってくる気もする。要するに個人的・組織的に、博打打ちの保険としてSIを見ておくということがそれほど無茶な話ではない。SIについては、今後先行きには諸説いろいろあるけど、日本のIT市場は大半がSIからできており、いままでもそうだったし、今後もそうでしょう。まぁほぼ半永久的にそうでしょう。規模は縮小気味にはなるとは思いますが、あと3億年ぐらいは続くと思う。なので、組織にしろ、個人にしろ、ある程度SIにコミットして、「SIにおける自身の有用性」をもっておけば、一時的にそこを抜けても、最悪保険としてもどってくる事ができる。市場は絶対ある。3億年分ぐらいある。
SI市場をどうとらえるかは、ITで生きる人間であればある程度考えなければいけないわけだが、自分はもう「失業保険」としてかんがえるほうが良いように感じている。エンジニアが最低限生活するための手段ですね。その辺出入りしながら、技術的に「ソフトウェア・エンジニアリング」に張っているところにちょこちょこ参加するのがよいのではないかな、と。組織としてものめり込むのではなく、保険的に見ていくというのはありでしょう。
（なお、SI自体の質や方法については、とりあえず打つ手はないので適当にさばくしかないと思う。これはユーザのマネージメントや、SI屋のマネージメントが双方「大きな問題」とそもそも認識している「にもかかわらず」、この状態に「なってしまっている」ことが課題。一種の累積的不均衡過程になっている感があるので、ステークホルダーがバカだとか罵倒してもどうにもなりません。個人的には行政・立法の介入しかないと思ってます。）
○自己研鑽
クラウドのノウハウとか、開発方法論とか、特定言語のlibに通じるとか、MLにつえーとか、そういうのはまぁ有るには越した事はないけど、それより、もっと基礎的なところを習得した方がよいと思う。自分もそうしている。
物理レイヤーとかそういう話ではなくて、もっとソフトウェアの基本的なところかな、という気がする。どちらかというと純粋エンジニアよりもサイエンスに近いエンジニアリングの手法あたり。DB系はほとんどそうだし、OS系VM・GCあたりはそういう感じだと思う。
例えばJVMひとつとっても、根本的に作りを変える必要がある。ここについては多分異論は少ない。ただ、その場合はそもそもjavaでいいのかという議論もでる。残す根拠はレガシー資産しかないと思うけど、それ汎用機時代のCOBOLと何が違うの？という議論も再燃する。そもそもjavaの広義のインターフェイスもそれ自体が相当変更にはなるはず。また、それだったら自力で特定の目的にあったVM（というか言語も含めた実行環境ですかね）があっても良いという人も出てくるだろうし、使う側より作る側の方が面白いということであればいろいろチャンスもでる。
DBについては言うまでもない。今のトレンドは完全に分散OLTPであり、普通に100万TPSでACIDが達成できてる。これはOracleでもPostgresでもMySQLでもない、まったく新しいDBエンジンで次々に考案・検証されている。もういろいろ変わりすぎて目が眩むレベルだ。
いろいろと打つ手が必要だと認識はどこも強い。ただしこれらの話を理解するには、やはり、サイエンス＋エンジニアリングが必要になる。
■ユーザー企業的に見て：
いいかげんハードリプレースでは限界があるよ的なことは自覚した方がいいと思う。ムーアの法則云々は、別段特別な話ではなく普通にその辺の雑誌には書いてある話だ。そもそもウチはあんまり関係ないな、というのは大きな勘違いで、日本企業の8割はムーアの法則のお世話になっていた。本人が気がついていないだけだ。
どこにどう影響がでるかははっきりしていて、要は業務系のアプリケーションのあり方で、パフォーマンスを上げようとすると、ゴンと金が投資にかかる、ということになる。「ソフトウェア」での全面再構築になるから。まぁやりたくないな、というのは普通の感覚で、それは正しい。投資に対するリターンも見えづらい。
とはいえ、これは、たとえて言えば、舗装道路・高速道路ぐらいしかインフラの発展のしようがないですよ、って時にオイラのところは馬車でいいや、間に合ってるから高い車は要りません、って話に近い。まぁ馬車は馬車なりに便利なところは多分あるはずなんで、それは意味があるので、そういうのはそれでいいと思う。それもまた選択ではある。
それはさすがにってところは「んじゃー、車買ってなんか意味あるの？」は明確にしないとまずい。圧倒的にスピードが上がって便利になりますってだけでは、さすがに通らない。ガソリンも食うし。このへんの説得策については、個人的にはあんまりよいアイデアはない。システムを人質に強迫するか、まじで利益にヒットする（コスト削減は無理ですよ。下がんないから）仕組みを真剣に考えるしかない。・・・というかそもそも最初から真剣に考えろって話ではありますが。
いずれにしろ、ユーザ企業様においては、いわばムーアの法則という一種のフリーランチでしのいでいたところで、それが有料になるので、コストという痛みは発生する。こればっかりは、「すみません、これから有料なんで払うもの払ってください」としかアドバイスのしようがない。
■結論的には
日本においては、非常に難しい時期にきたなと思う。ソフトウェアの基本的なアーキテクチャの変更は、想像以上にコストがかかる。人・もの・金、すべてにおいてかかる。現在のユーザ企業が、この超高齢化・超低成長・低消費時代にそれだけのコストを負担する決断ができるようには思えない。なので、ソフトウェアの時代がきますよ、といってもバラ色というわけではない。
ただ、ソフトウェア・エンジニアについては面白い時期に来るのは間違いないだろう。さて、どうしてやろうか？と考えをまとめながら、先端系の論文でも読んでいると色々と考えが広がる感じがする。とかく微妙な手詰まり感がある世間だが、ソフトウェア、という意味では面白い将来が待ち構えているのは、間違いないと思う。いろいろと悲観的な世相だけれども、道が細いとはいえ、準備をし、賭けるには足る環境になりつつあるのは良いことだと思う。頑張りましょう。そんな感じの2016年の年の瀬ですわ。もう年末かよ。はえーよ。勘弁してくれ。
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とコードをまったく変更せずに対応することが可能になっている。数件程度のデータの「バッチ処理」も数秒以内で終わり、かりにそれが数億件まで増加しても、そのままスケールアウトし、数十分で処理を終わらせる事が可能になる。
