Cicada：Dependably Fast Multi-Core In-Memory Transactions
Cicada: Dependably Fast Multi-Core In-Memory Transactions
https://www.cs.cmu.edu/~hl/papers/cicada-sigmod2017.pdf
SIGMOD2017で発表されている。現状の分散OLTPのアーキテクチャをうまくまとめて、欠点をうまくカバーアップし、言って見れば次世代MVCCの一つの形を提示している。その上で、現在世界最高のパフォーマンスを叩き出している。現時点で世界最速DB（ただし自称）。
現状の分散OLTPは大きな流れは、SILO/Foedus/MOCC/等のOCC系、すなわち2PLをベースにした実装で理論上はmonoversionでのserializableの実現を行っている方式と、Hekaton/HyPer/Bohm/ERMIAといったMVCC系、すなわちMVTOの派生をベースにしてmultiversionでのserializableの実現を行っている方式の二つがある。
現在のところはOCC系の方が若干優位で、ベンチマークも含めてパフォーマンスがでている。MVCC系は劣勢ではある。そんな中で、CicadaはMVCC系のリファレンス実装として提示され、OCC系を上回るパフォーマンスを出している。
まず、論文のOCC/MVCCのまとめを再整理し、Cicda自体の中身も整理する。以下の記述は論文を参照しながら自分の意見も書いているので、Cicadaの論文通りではない。なお、以降は、論文を片手に読むことを強く推奨する。最低限の前提はMVCCとMVTO。
■OCC/MVCCまとめ
整理はChapter2になる。
□Optimistic Concurrency Control
基本的に3phaseアプローチで、read phaseで共有メモリーからreadとローカルメモリーへのwriteを実行、次のvalidation phaseでconsistencyをチェック、最後のwrite phaseでコミットを実行する。実行後に他のtransaction(注：以下tx)から値が見える。(注：ただしglobalな非同期barrierのepochを設定している場合は実際は4phase)
最近のOCCは1-version-in-placeのアーキテクチャになっていて、GCをきわめてライトにしている。なお、read-only用にconsistent snapshotは準備する（ただし、少しだけstaleにはなる）。またwriteはin placeだがメモリー上は別の場所を確保し、古い値はそのままGCする。
Strength
・Lock free read
Validation phaseで多少時間をとるが、基本的にreadはwriteにブロックされない。当然concurrencyも上がる。特にmany-core/in memoryでは、uncommittedではあってもlocalに値がcacheされるので、cache missが減る。また 1-version-in-placeはオーバーヘッドが少ないので、特に競合がない状態では高いパフォーマンスを出す。（注：このあたりは同じくreadはロックしないとはいえ、versionサーチで手間取るMVCCよりも原理的に高速）
Weakness
・Frequent aborts
楽観処理なので当然競合が上がればabort率はあがる。また1VCCだと最新versionだけが扱われるので、ますますコンフリクトを起こす。abortはコストが高い。CPUは食うし、キャッシュラインが汚れる。さらにOCCだとオーバーヘッドがない分どんどんretryするので、さらにヒドイことになる。
今のところはちょっと有効な手立てがない。TicTocはtransaction orderを柔軟に変更することでabortを抑えているが、concurrentな更新があると以前のversionへのアクセスができなくなる。
Read-only snapshotは抜本的な解決にならない。r-wなtxでは当然使えない。また得られるメリットが10%向上程度なので、そもそもOCCの低いオーバーヘッドには見合わない。snapshotの作成インターバルが1secぐらいの粗い粒度なのでstalenessが高く、利用価値が薄い。
・Extra reads
あんまり知られてない欠点。ロックしないのでread phaseで同時書き込みが可能になる。in-place updateの場合、何もしないと、パーシャルライトを読んだり、repeatリードで違う値を拾ったり、可変長データで不正アクセスしたりするので、そうしないように リードするときにローカルコピーをとる。これはextra readになりレコードセットが大きい場合はコストになる。
・Index contention
新しいレコードを生成する（write）とき、indexに登録して、当然コミットされるまでは他から見えないようにロックをとる。このearly index updateはユニークキー制約の保証の仕組みになるし、indexの変更を現在は走っているtxに見せるときに簡潔に処理できる。しかし、abortされるような変更があったりする場合は競合が発生する。いずれにしろ、read phaseでのindex updateはそもそもglobal updateを避けよという原則に反するので、いろいろ問題。
基本的にOCCの弱点はそもそも1VCC由来。OCCはコア間の通信削減に有用だし、ハイスピードなin-memory DBには重要。高いabort率もメモリー競合・キャッシュラインが汚れなければコストを最小化できる。Extra readsは1VCC固有の問題。Index contentionもそもそもearly index updateをしなければよい。（・・・とはいえ、それでパフォーマンスがでるか？という問題もある。）
□Multi-Version Concurrency Control
複数のversionを利用してコンフリクトを回避する。仮に更新があったとしても、前のversionを利用したtxが可能。version の管理はtimestamp(以下ts)を利用して行う。tsのアサインはtxの開始時点で行われる。各versionのwrite timestampはversionが有効(valid)になった時を示し、read timestampはそのversionが無効(invalid)になったか、または有効(valid)のままであるかを特定する（注：と論文には書いてあるが、ここでの無効と言うのはそのts以前のwriteは無効と言う意味で、そのまま有効というのは単にリードしてまっせという意味だと思う。普通にはread txがそのversionを読んだ時に「読んでるよ」のマークとしてtsをおく）tsを利用してvisibleな利用可能なversionを特定する。versionのtsはtxの開始時点のものか、またはcommit時点のものか、どちらかを利用する。
Strength
コンフリトが少ない。更新処理があっても別に関係なくレコードにアクセスすることが可能。
Weakness
弱点はmulitiversionのオーバーヘッド。以下
1. Computation and storage overhead of searching and storing multi-version records
特にIn memoryな高スループットな環境では、searchとstoreのコストはCPUを食う。storeの空間コストも大きい。大抵のMVCCではlistや配列の中のversionのsearchに間接参照利用する。これはキャッシュミスやワーキングセットがCPUキャッシュに乗らない場合は特にハイコストになる。最近のMVCCでは最後のversionでは間接参照を利用せずにin placeでの処理を行う方式もあるが、これは1-VCCと同じくextra readの問題を引き起こす。
2. Large footprint
multiversionなのでfootprintが大きくなる。ワーキングセットが大きければキャッシュヒット率は下がるし、処理のパフォーマンスも落ちる。頻繁にGCすることでfootprintを小さくすることもできるが、効率よくやる必要がある。
3. Writes to the shared memory
大抵のMVCCでは共有メモリーに書き込むが、これはメニーコア環境では悪手。
4. A bottleneck at timestamp allocation
tsの発行に、centralizedな方式で、atomicにshared counterを増やす形をとるとワークロードの競合状態に関係なくパフォーマンスに制約を発生させる。1-VCCよりも桁違いに悪くなる。今後のメニーコア環境ではますます悪化する。
以上の問題点は現在のMVCCでは部分的に解決はしている。しかし、MVCCのベースのオーバーヘッドはやはり大きく、low-contentionでは1-VCC-OCCの後塵を拝し、競合環境でも1-VCCを一貫して上回るというパフォーマンスを見せるには至っていない。
あとは付随的に
2.3 Constrained Parallel Execution
2.4 Hardware Transactional Memory
にまとめているが省略する。
以上はCicadaの論文における1-VCCとMVCCのPros-Consの分析になる。MVCCの弱点については、これらの弱点を一気にCicadaが解決するぜ、って話の前振りなのでちょっとくどい感じもするが、全体的に概ね合っていると思う。1-VCC(というかOCC)との比較で言えばOCCの軽さ＋エンジニアリングが、MVCCの重さ＋理論的なabort率の低さの合計を上回っているのが現状。
■Cicada本体
以降Chapter3以降は、上記のMVCCの弱点を補う形で、割とMVTO的な実装とそれにまつわる若干のエンジニアリングを提供している。またベンチマークも同様に提示している。以下、この実装(cicada)についての解説になる。
個人的に2017年現在のメニーコア・大規模メモリーを前提とした大規模OLTPのMVCCベースの参照実装としては「一つのモデル」になると思っている。もちろん、これがそのまま商用ベースになるとは思えないが、ただ今後の大規模OLTPを見るのであればチェックしておくべきポイントは提示されていると思う。
パフォーマンス・ベンチはTPC-C/YCSBの鉄板。MVTO(MVCC)ライクの素直な実装での比較としては意味があるので、そういう風に見るべきだと思う。以下ポイントごとに
■Design
・Multi-Clock Timestamp Allocation
tx開始時点にtsを決定する。tsはどのversionが使われるかの決定に利用し、serialization orderの確定に利用される。tsはsoftware clockで発行される。
tsのアサインはボトルネックになりやすいのでそれを排除する。メニーコア環境下でのハードウェアでの時刻同期は高コストになりやすい。各ワーカースレッドがローカル・クロックを持ちts発行前に時刻をインクリメントする。実装はTime Stamp Counterを利用し、各ローカルでのインクリメント幅（最大・最小）のみを保証している。もっとも早い時刻への同期をone-side(注：スレッド間のbarrierは取らない)でできるようにしている。
tsの発行は以下の3要素による
・ローカルの現在時刻
・クロックのブースト(abort時点でのスレッドあたりのクロックのブースト量)
・スレッドID（タイ・ブレーカー）
ローカル時刻にブーストを加えて、64bitのtsを作成し、下位56bit をとってスレッドIDの8bitを加える。
各スレッドは二種類のts（wtsとrts）をもつ。wtsは上記の発行時刻利用する。rtsは全てのスレッドのwtsの最小値(min_wts)から1を引いたもので、これをリーダー(leader)スレッドが定期的に更新する。なお、同様にmin_rtsも計算され、これはGCに使われる。read-writeのtxはthread.wtsをtsとして利用し、read onlyのtxはthread.rtsを利用する。特段にread-setをvalidateしたり、追跡はしない。
先行または同時に走るread-writeのtxのtsがmin-wtsとローカルのthread.rtsの間にあるようにして（see no earlier than min_wts and later than thread.rts）整合性を保つ。
Cicadaでは時刻同期は多少甘くても許容する。tsの物理時間での順序保証は想定しない、ユニーク＋単調増加であればよく、加えてスレッドID suffixと時刻の単調増加を持っていれば良い。
とはいえ、問題もあって、早すぎるtsは、競合writeのabort率があがる（注：スレッド間でtsの乖離が大きくなると同時刻のスパンがひろがりすぎる。だから競合になりやすい。）。なので、時刻異常訂正にlong-lastingとshort-livedの仕組みを利用する。(注：早い奴はそのまま生かして、遅い奴を一方的に修正、という意味だと思う) 以下の手法を利用
1 One-sided synchronization
各スレッドがround-robinで他のスレッドの時刻を見て自身の時刻よりも早ければ、そちらに時刻を合わせる。
プロトコルはcache coherencyなものを利用する。タイミングは100μsごと。これは遅いものを早いものに合わせるので、早すぎるものは修正できない。全部のスレッドで行うのでそれなりに有効。
2 Temporary clock boosting
abort発生時に、クロックブーストを行なって他に遅れている時間分＋アルファで時刻を進める。
時刻は基本的にwrap-roundなので一回りすると元に戻る。その時は意図的に新しいversionを挿入して時刻をリセットしてセットし直す。だいたい10日に一回。read-onlyの場合は関係ない。かつ、このwrap-roundの回数をeraとして記憶しておく。（全順序確保）
基本的にCicadaはスレッド間を超えたexternal consistencyは保証しない。（注：OCSRではない。serializableではある）あるスレッドのコミット後に、別スレッドでのコミットが前の時刻で来ることはありうる。ただ、これは滅多に問題にならない。dependencyがある場合は、厳密にorderingされる。external consistencyについてはmin_wtsがコミット済みのtsよりも大きくならないと（注：コミットされているものが先のtsを持つことを保証する。）アプリ側にコミット成功を通知しないことで対応している。これは100 μsぐらい遅れるけど、その程度を遅らせる処理は他にもあるので許容する。
causal consistencyだけであれば、先行するtxの最大のtsよりも時刻をインスタントに進めてtsを発行すればこと足りる。
・ Multi-Version Execution
データレイアウトは拡張可能な配列で二層構造のページになっていて、各レコードは配列のインデックス(レコードID)でアクセスする。各レコードのversionは単方向リストの構造でheadノードから始まりversionノードが続いている。headはinlined versionの場合がある。
各versionの構成は以下
1. wts : versionを作成したwrite txのts
2. rts : コミットした（またはする予定）のread txのtsの最大のもの
3. レコード本体
4. コミットステータス（validationの結果）
5. NUMAのnodeIDとかversionサイズとかのアロケート情報
この単方向リストはheadから順にwtsでソート済み（注：論文に図があるのでそっち参照）
versionがreachableになるのは、validation phaseで version listに追加(install)された時点から。フィールドはrtsとstatus以外はimmutable。rtsはリードにより更新される。statusは最初はPENDINGでwrite phaseに入ってCOMMITTEDか ABORTになる。削除はゼロ・レングスのversionにしてdeleteのコミット時にDELETEDになりGC対象になる。
各txはtx.tsを持っていて、version listを最新のものから遡ってスキャンして、使う対象versionにアクセスする。自分より新しいtsのversionは無視(注：このへんがMVCCの面目躍如)する。(v.wts>tx.tsでハネて、もっとも最新のものをみつけて)それからstatusを確認。PENDINGならspin-wait。ABORTであれば一つ前のversion、COMMITEDならそのversionで確定。これが要するにそのtxからのvisibleなversionになる。(注：ということはcommit済みのものだけでなくdirtyだが possibly committedなものを読んでいるということ。)
PENDINGがblockになるけど、まぁ時間がvalidationの時間だけで短いし、そもそもearly consistency checkを通っているので、COMMITTEDの可能性が高いので、投機的に無視するのはちょっとリスクがある。もちろんabortされることはあるがこれで投機的に実行するとCascading abortになる。なので、他のMVCCと違って、投機実行はせずにspin-waitsする。
(注：PENDINGは普通にabortの可能性がある(validationに時間がかかっているのはそういうこと)ので、投機的にabortとしてretryの方がスループットが出ると言うのが他の実装の話で、Cicada的にはこれはどうよ？と言う問題提起。後段になるがCicadaでは事前にpre-validationするので、この段階でのabort率は低い。)
Cicadaはversionサーチの間に、パフォーマンス上げるために、いかにもabortされるだろってtxをearly abortさせる。writeでvisible version vについてv.rts＜= tx.tsのチェックをする。そうでなければabortする。
(注：v.wts＜tx.ts＜v.rtsでabort。普通にMVTO)
Cicadaはread-own-writeもサポートしている。スレッドローカルなversionについては同じレコードであれば、同一txからはアクセス可能。スレッドローカルなhash tableを持っていてローカルversionへのポインタを
持っている。(注:このポインタっつーのがよくわからん。原文はpointerでmeta dataに対してってことなのだが・・実装見ないとよくわからん)
・Best-Effort Inlining
best-effort inliningでオーバーヘッドと競合のコスト抑えている。(注：head nodeが単純にarrayに順に配置されている＝inlined。これはなるほど、と思う。) txはまずheadのinlined version用に事前にアロケートされた場所を利用しようとする。inlineを利用するかどうかはレコードへのwriteが行われるときに決定される。まず最初にUNUSED ならCASでPENDINGにして、成功したらinlined versionを作成する。失敗したら non-inlineのversion作成。inlineは小さなデータ(216byte)のみで利用する。大きなデータだとメリットが薄くなる。
可能な限りInline化する。条件は
1. read txがinlineでないversionをvisibleとして読む
2. そのversionは十分早い。v.wts＜min_rts
3. かつinline化されてない
その場合はread txだけどRMWして同じレコードだけどinlne化する
inline化の競合を避けるために、inline化は滅多にまたは全く変わらないread-intensiveなレコードに限定する。もしwriteが多ければむしろオーバーヘッドが高いのでメリットが薄いし、そもそもreadされないのであればパフォーマンス向上に意味がない。
・Serializable Multi-Version Validation
1. Pending version installation
まず先にPending versionとしてwriteをinstall。wtsでソート
2. Read timestamp update
必要であればreadされているすべてのversionのrtsの更新。v.rts>=tx.tsの保証
3. Version consistency check
(a) readされるレコードセットの、今まで見えていたversionが現在でも見えているversionで かつ、(b)writeされるレコードセットの今見えているversion vが v.rts＜=tx.ts (注：追い越し禁止)を満たす、ことを確認。
(注：MVTOプロトコルそのもの)
pending versionのinstallは同じvisible versionを共有し、かつtx.tsよりもあとのtsをもつconcurrentなtxをブロックする(注：早い方を先に書く)。もし、visible versionを共有していてもtx.tsよりも前のtsであれば、自身のpending versionはそのままinstallし、自身をabortにするかまたはconcurrentな方をabortすれば良い。これはearly abortと同じで、今見えているversionについて v.rts＜=tx.tsを満たせない場合に現在のtxをabortさせる。
（注1：visible versionを共有ということはr-w r-wでのw-wの競合になる。w-wだけであればMVでは競合にならないがr-wはRFなので普通にorderが競合。一応後述で単純writeでちゃんと区別していてRMW以外も考慮ずみ）（注2 : 処理フロー図だとwtsのソートがPENDING installationの前にあるけど、これは他のconcurrentなtxの結果がinstallされているのでそれを見るということだと思う。自身のwriteはsort段階ではまだinstallされていない、ので、abortするべきものはすれば色々汚れない）
read timestamp updateは、その他のtxにこのversionはtx.tsと同じくらい「遅れて」見られていると言うことを通知している。(注：validation時点で最遅＝最近のtsのnotify)
validation checkについては(a)今見えているversionより新しいversionはないこと、と(b)該当txが早すぎるversionをコミットしないことを保証している。特に後者はRMWじゃなくて単純writeのconcurrencyも向上させる。(注：単純writeとはblind writeを指すと思う。write concurrency向上は単にブロックしないってことでいいかと。ただしこの部分は他のMVCOO系とは違う部分なので重要。)
validationの後は、logにtxのts, read, write, insertのセットを渡す。logに失敗すればabortできるし、アプリがコミット済みtxを保持できるかどうか次第だがretryでlogすることも可能。(注：one-shot requestが前提。)
roll backの場合はversionがすでにできている場合にのみstatusをABORTにする。そうでなければGC。
特にABA問題(注：CASで別スレッドが参照先を変えてしまう問題)もない。同じようにrecord IDも再利用される。
read timestamp updateはwriteが条件付き(conditional)なので速い。rtsがtx.tsよりも遅かったら別に更新する必要もない(注：そもそも前のversionを読んでいるので意味ない)。28コアマシンで単一レコードに対して秒間23億の更新が可能で、これは条件付きでないただのatomicなfetch and addsが秒５千５百万しか処理できなかったことと対照的。
・Optimizations for Efficient Validation
Validationの効率化は以下の通り。総じて、MVCCの弱点を認識した上で、細かい手当をしかるべき形でやっている。いろいろ参考になると思う。
1. Sorting the write set by contention
validationの前にやってabortの負担の減らす手段。valdiationでは、最新（listの最初の）のversionのwtsを見る。これが大きい（新しい）ほど競合の可能性が高い。よってこれを降順にpartial sortしておく。この場合Top-kは総数nの場合は、n log kで終わる。このソートにより多数のpending versionをinstallしたり、相当のメモリーにアクセスする前にconflictを検出することができる(contention-aware validation)
これはOCCではできないか、またはやってもコストが高くつく。SILO/TicToc/Foedus/MOCCではvalidation phaseのロックでデッドロックを避けるためにすべてのwrite setでグローバルでのソートが必要になる。これでは柔軟なロックの順序(flexible locking order)を許容することができず、全ソートにn log nかかってしまう。Cicadaはデッドロックがないので、この制限がなくpending versionのinstallはtxのts、すなわちdependncy cycleを避ける形で優先処理される。
2. Early version consistency check
write setのソートの後に実行される。これはvalidation checkの version consistency checkと同じで、GCにかかるようなversionがinstallされる前に大抵のabortを検出する。これはTicTocのpreemptive abortを真似たもの。
上記の二つの最適化は、低競合状態では別段パフォーマンス向上につながる訳ではなく、不必要なオーバーヘッドでしかない。なので、直近のtxがコミットされるような状態ではこのステップは両方ともオミットされる。（実装では一行で五つ(5 in a row)コミットがあればオミット）
3. Incremental version search
version searchのコストを下げる。pending version installにしても version consistency checkにしても version listをトラバースする必要があり、これはread phaseでも同じことをやるので重複している。こういうversion searchはローカルのCPUキャッシュにない新規に挿入されたversionを渡り歩かないといけないため高コストになる。このsearchの繰り返しのコストを低減するため、read phaseでの最初のversion searchの時点でtx.tsの直後のwtsを持つlater_versionを記憶しておく。このlater_versionは新しいversionが次のversion searchでヒットした時に更新される。version listがwtsの降順でソートされているので、現在のtxをabortできるような新しいversionはversion listの中ではlater_versionの次に現れることが保証される。なので少なくともversion searchの繰り返しはlater_versionからはじめて問題ない。(注：これはなかなかよくできている細工だと思う。)
・Indexing
Cicadaではindexとストレージは分離している。primary indexを含むすべてのindexはテーブルとは別のデータ構造になっている。64bitのレコードIDをindexとして持っており、レコード本体や生のポインタは持っていない。Cicadaのこのmultiversion indexesは以下の二つの問題、すなわちphantom回避とindex競合の低減を解決する。
1. Avoiding Phantom
index node validationの一種で回避する。index nodeに全部wtsとrtsをつける。range query, delete, insertとともに validationの前にindexが変わったかどうか判断できる。Cicadaの場合は標準のtable構造をそのまま利用できる。(注：要するに本体でのデータ構造でのチューニングメソッドをそのまま利用している)
2. Low index contention
OCCがread phaseでindex構造を変化させるのと違って、Cicadaではスレッドローカルでのindex nodeのwriteをtxのvalidationが終わるまで繰り延べる。これは自分のindex更新にread-own-writeの仕組みを利用することで達成している。あと一応single-version用のindexもCicadaはサポートしているがindex updateの繰り延べをやらないとindexでの競合が起きる。（注：まぁ確かにabort連発の場合は事前にindexを更新するのは賢くないのでdeferredの手はある。とはいえrecoveryとかそういう話もあるので、そうそう簡単かというとそうでもない気がする）
・Durability and Recovery
使っているのは、並列log書き込みと CheckPoint(CP)。CPはtransaction-consistent checkpointingが使えるといいなというレベル。（Low-overhead asynchronous checkpointing in main-memory database systems. K. Ren, T. Diamond, D. J. Abadi, and A. Thomson. 2016）
基本的なデザインは以下参考Fast databases with fast durability and recovery through multicore parallelism. W. Zheng, S. Tu, E. Kohler, and B. Liskov. 2014
（注：ということでCALC(Checkpointing Asynchronously using Logical Consistency)がよいのでは、という提案になっているけど、個人的にはWBLの方が全然よさげなんで、ここでは省略。CALCはconsistent snapshotを特定のコミットのタイミングをトリガーにしてとる感じの手法。）
基本的にNUMAノード単位の複数スレッド単位でloggerスレッドがredo logを作る。validationが終わったら、loggerにlog record(write/insertのnew version のwtsとdate)を送る。loggerはlog fileにappend(スレッド単位に存在)する。それからversionのstatusをCOMMITTEDにマークし直す。普通のブロックデバイスならgroup commitでamortize(まぁ均等償却ってことでしょう)するが、NVMならbyte addressで直書きして低レイテンシーで行う。この場合はgroup commitのような手法は用いない。
checkpointについては別スレッドで動く。各テーブルをpartitioningしてその単位で、スレッドごとのcheck point fileに最新のcommitted versionを保存する。この処理はロック無しで非同期に行われる。安全なメモリーアクセスを確保するために、checkpointerはmin_rtsのメンテナンスに参加し、min_rtsの更新がわかるようにthread.rtsの更新する。（注：min_rts以前のものを触る）
recoveryは最新のcheckpointとredo logから行い、メモリー上にレコードの最新versionがinstallされているようにする。削除については全部の復旧が終わった後に最新のtsでdeletedレコードを作り直す。
(注：このあたりはわりといろいろやれることがまだまだ有るように見える。NVMが前提であるので、WBLあたりがかなり有効だと思う。)
Space management
redo logはchunk化されている。checkpointの生成単位でmin_wtsよりも古いckeckpointと古いlogが破棄される。
・Rapid Garbage Collection
GCはフットプリントを小さく保つために、割と回数多めでconcurrentに行う
1. Frequent garbage collection
通常のDBでは 数十msで行うが、それではMVCCではworking setがでかくなりすぎる。
例）80ms (Siloは40ms [EBR : Epoch Based Reclaimation] )でGCとして、YCSBのwrite-intesiveなケースでtxあたり800byteの書き込みを想定する。TPSで3.5Mのパフォーマンスで、txあたり1KBのstale recordができる。これでworking setは 80ms x 1KB x 3.5M/s だと凡そ280MB。これではCPUのキャッシュサイズに乗らない。stale recordが場所を取りすぎる。
よってCicadaではEBRとQSBRの派生手法を利用する。回収対象のversionをcoarse-grainedではなく fine-grainedで行う。
・最初のステップで各スレッドは最後のtxでコミットされた新しいversionのmetadataを記録する。
・visibleではなくなったversionはゴミになる。
・各スレッドは各versionへのポインターとv.wtsのコピーをまとめてキューに放り込む
・それから各スレッドがquiescent stateに入りフラグをセットする。(10 μsごと)
・リーダースレッドがフラグが立つを見るたびに全てのフラッグをリセットしてmin_wtsとmin_rtsを単調増加させる。その値がグローバルなthread.wtsとthread.rtsの最小値として各スレッドに保存される。
・quiescent終了後、各スレッドはローカルのGCキューを見て、キューの最初のアイテムが v.wts＜min_rtsかどうか判断する。もしそうなら全部、回収可能。現在・将来のtxはv以降のversionを使うから。
・チェックに失敗すれば、それ以降のキューは見る必要がないv.wtsはキューの中では単調増加なので。
2. Concurrent garbage collection
複数スレッドで異なったレコードのversionの回収が可能。
レコード単位で、GCロックとminimum write timestamp(record.min_wts)(注：レコードlistの終端)を持つ小さなデータ構造を本体とは別に持っていて、GC対象になるときにフェッチされる。
・GCロックに成功 -> 失敗した場合はGCで競合しているのでfailで良い
・(v.wts) > (record.min_wts) -> vについてのdanglingはないので、version listの残りをvからデタッチして、record.min_wtsを更新、GCロックを行って、GC対象にする。
・最後に、デタッチされたversion listのversionローカルメモリーに返却
・Contention Regulation
Early abortやearly version consistencyを講じてもabortは発生する。
Backoff
単純に失敗したtxをsleepしてリトライする。そもそもbackoffの時間はワークロード・システムによって最適解が様々。Cicadaはグローバルなコーディネートによるmaximum back-off timeを利用するrandomized backoffを使ってる。
リーダースレッドは5msごとに各スレッドのコミットされたtxの数を総計しスループットを算出する。直近の期間とその前の期間でのスループットの変化（スループットの変化を、変化させたmaximum back-off timeで割って勾配を見る）を見て、正（負）なら0.5 μsの固定量を増やす（減らす）。ゼロまたはUndefinedの場合は方向はランダムに決定。
以降は実際のベンチマークになる。論文を直接参照で。
■最後に、serializabilityの証明
Appendix Aより
ただ証明もってきても仕方がないので、MVTOと比較する。まずMVTOのpropertyを持ってきておく。
Property1.For each Ti, there is a unique timestamp ts(Ti); That is, ts(Ti)= ts(Tj)iff i = j.
TSの定義。注意すべきは別段startimeにはしていない。順序があれば良い。
Property2.For every rk(xj)∈H, wj(xj)
(Case 2) Suppose tx′ reads a committed version v′′ that is earlier than v.
tx already passed the version consistency step by observing v, so tx′ also observes v, which makes tx′ fail the version consistency check step because v, not v′′, is the current visible version.
This again makes a contraction to the assumption that tx′ is committed.
では、仮にtx’がvよりもっと前のv’’を読むとすると・・・txがvを読んでいるので、tx’もvを読む。vがvisible versionなので、tx’がvalidationが通らない ->成立しない
(Case 3) Suppose tx′ reads a committed version v′′ that is later than v.
We substitute tx and tx′ with tx′ and tx′′. Reapplying this lemma reaches Case 1 or Case 2 in finite steps, precluding the existence of v′′ if tx′ is committed.
最後にtx’がvより遅いv’’を読むとすると、txとtx’をtx’とtx”に置き換えていくと結局前の二つのケースになり、
tx’がコミットするとv”が存在ことができない
Consequently, this makes a contradiction to the assumption that tx′ is committed.
Therefore, no such tx′ exists. v is the visible version to tx.
従って、そう言うtx’は存在しない。
上記より、tk(rj)について読んでいないxiのversionがあったとして
(j.wts) < (i′.wts) < (k.ts)のi’が存在しないため
ts(Ti) < ts(Tj) or (b) ts(Tk) < ts(Ti) となりProperty3は満たす。
Property4については
Property4. If rj(xi) ∈ H, i != j, and cj ∈ H, then ci < cj.
これはCicadaはci < tj_start_timestamp <cjなので成立する
よってCicadaはMVTOのPropertyはすべて満たす。
したがって、Cicadaが上記のProperty以外の制約を課さないのであれば、スケジューリングパワーはMVTOと同等である。
個人的にちょっと、そこで問題になったのは以下の条件。
The pending version installation step blocks concurrent transactions that share the same visible version and have a higher timestamp than (tx.ts). If a concurrent transaction using the same visible version has a lower timestamp than (tx.ts), it may proceed to install its own pending version, aborting either this transaction itself or that concurrent transaction. Similar to early aborts, this step aborts the current transaction if the current visible version v fails to satisfy (v.rts) <= (tx.ts)
自身が早い（相手がより大きいtsをもつ＝遅い）場合は、相手をブロック(block)して、自分をinstall。そうでない場合、自分をinstallして自分自身かまたは相手をabortする、という制約だが、これは、自分より早い場合はそのまま書ける。ただし相手をブロックする。ブロックされた側から見ると、”自分”が追い越しのinstallになるので、かつ相手（”自分”）がinstall済みになるので、それがコミットされるとすると自分をabortする羽目になる。また、自分が遅い場合は、相手をinstallさせて、自分を一旦installさせて、自分か相手をabortする。これは相手が追い越しになるので、相手がタイミングによってはabortになる。r-w r-wの競合になるので、それを解決する。
この時、後側のwriteをblindとするとr-w-wでwは競合にならないので、「見なかったことにする」のであれば実はserializableになる。visible versionの割り当てを強制しないのであれば、制約にならないが、強制割り当て（書くときには確認＝blind write禁止）をするのであれば、serialization空間は狭くなる。論文では明確ではないが、途中明示的にblind writeに言及している（ように見える）：Note that the latter check uses the currently visible version to increase the concurrency of write-only (not RMW) operations that do not depend on the previous record data. ので、そうではないと思われるので、制約になっていない。よって問題ではない。すなわち、MVTOと同等と思われる。
なお、最後の定理、すなわち
THEOREM 1. Any schedule for committed transactions in Cicada is equivalent to the serial schedule that executes the committed transactions in their timestamp order.
PROOF. A committed transaction creates at most one version for a record.
By Lemma 1, each version’s write timestamp following the transaction’s timestamp is unique within a record.
With Lemma 2, every committed transaction reads the uniquely determined visible version of the record as it would in the serial schedule.
Therefore, any schedule of committed transactions in Cicada is equivalent to the serial schedule.
これは問題ない。
人工知能狂騒曲
最近はさすがに落ち着いてきた。もちろん一部では「人工」の「知能」という言い方に拘泥している一群もあるが、基本的に所謂「人工知能」は、SF的な人工知能ではなく、機械学習やそれに関連した統計的手法を利用したなんらかの仕組みである、ということのコンセンサスはとれつつある。現在言われている「人工知能」が「知能をもつ」とおもっているまともなIT屋はひとりもいない。（言いたいのは対偶）
そもそも、知能の定義については、諸説いろいろあって、普通のIT屋だと一般にチューリングテストみたいなの持ち出すことが多い。冷静にみれば、あんなものが定義になるわけはなくて、個人的にはアレは天才チューリングをもってしても知能をformalizeできなかったギブアップ宣言とみている。ということで、そもそも何が知能か？という定義は個人的には難しいと思っている。
普通になんらかのデータのインプットがあって、プログラムがなんらかの推論処理を施し、ユーザに有用なアウトプットがでればそれで充分「人工知能」でしょう。別にエクセルのマクロでも問題ない。実際、ひと昔前のルールベースの人工知能とやらはエクセル・マクロと大差はなかった。
以下は話を業務用の用途に絞る。「人工知能」の利用は業務用の他にコンシューマー向けの方も活発であるのは周知の通り。家電や自動車の自動運転などがあるが、見ている限りは現時点ではR&Dの域を出ていないか、または投入したとしても「おまけ」の位置付けになっているように見える。専門家以外の不特定一般第三者にAIサポートを無制限に使わせるには、特にクリティカルな利用ではさすがに厳しいだろう。現状有望なAIの用途は専門家のサポート、すなわち業務向けのサポートシステムだろう。
◇マーケットの外観について
話を業務用に絞った上での話ではあるが、現状の「人工知能」のマーケットは確立していない。マーケットどころか、まずその人工知能的な「ツール」をどう開発するか？そもそも役にたつ「ツール」なのか？というところにとどまっている。往年のゴールドラッシュに例えていえば、そこに金鉱「らしき」ものがあるのに、そのまえにまず「俺のスコップの方が掘れるはずだ」「いやこっちの新型ディープラーニング印のスコップの方が」「いやいやなんといってこのワトソン印の」とやっている感じ。
もちろん一部ではすでにここに金鉱があるはずだ、であたりをつけて掘り始めているところもあるが、いや、ちょっとなんかこれ勝手が予想より違うんだけど、というかそもそもこれ金鉱なのまじで？という感じになりつつある。いや、そもそもスコップじゃ無理じゃね。という展開だ。
もちろん掘れば「天然資源」は出てくるので、鉄鉱石やら石炭やらはでてくるとは思うが、金鉱か？というとちょっとそれ、そもそも根拠なんだっけそれ？という話になりつつもある。一般に「この山には金鉱がある」ということをいう詐欺師のことを山師というが、まぁ人工知能推進派と山師はあんまり違いがない雰囲気も一部では見受けられる。もちろん、「金鉱っぽい」のを見つけているかもと言うところはあるが、やはり例外。
◇現実のインフラの状況やビジネス
AIを提供する側からみると、実は機械学習を「試す」ための環境はすでに十分提供されている。いわゆる触ってみる、ということだけであればたいていのクラウドベンダーはGPGPUの環境は提供しつつあるし、もっとユーザビリティをあげるという意味でSaaS相当のサービスも提供している。んで、実際のこれらのビジネスはどうか？というと、全くお金になっていない、お試しユーザが数はまぁいるにはいて、ごく極めて少数のユーザが相当金を突っ込んで使っている感じだ。
インフラに投資している方からは、懐疑的かつ恨み節的なコメントまで聞かれる始末だ。曰く、本当に儲かるのか？これ？である。仕方がないので、極めて少数のユーザの取り合いですでにダンピングまがいのことまで起きているようだ。現状は相当厳しい。クラウドビジネスの初期が、結局（というか多分今も）特定ゲーム・プラットフォーマーの取り合いになっていたのとほぼ同じ。
要するに、まともに使いこなして「人工知能をお金に変えている」ユーザはほとんどいない。これは提供側からも透けて見える。一般的には「いまは儲からないけど、そのうち儲かるはずだ」状態でなんとか言い訳している状態になっている。
◇何が足りないのか？
機械学習・「人工知能」については、それなりに用途があることは、特に異論はないと思う。ある程度、機械側で推論してあげて、割と無駄な作業は減らしましょうというのは、合理的だし、人手がたらないこの世相では役に立ちそうに見える。ただなんかコレじゃない感がいろいろと漂っていて、ピースが足りない感が強い。それも複数足りない。
1.人の問題か？
よく機械学習等を使いこなす人材の不足が指摘される。ちょいと前まではデータサイエンティストだった。たしかに機械学習の使い手は足らんわなという印象は強い。基本的なところができていないとどうしようもないので、「すぐに手を動かせる」人材は必要だし、不足気味だ。ではそういう人材が輩出したとして、市場が立ち上がるか？といえば、それだけでは厳しいように見える。
今や、この辺りは、もうすでに「データサイエンティスト」からの鞍替え組も含めて、玉石混合。抜いた、抜かれたのごぼう抜きで、「君、ちょっと機械学習できるよね？」という感じになっている。もちろん統計処理の分析と機械学習は「まったく違う」のだが、そのへん無視しての人材取り合い。そろそろいい加減にした方がいいと思う。札束で殴るような人の抜き方は端から見ていて閉口する。ブームが過ぎ去った後、お互いがどうなるのか。
ま、そもそもそれが使える人材なのかを判定する人工知能がいるんじゃないかという陰口はともかく、人が足らないという意味では足らない。ただ、IT業界で人が足りているということは有史以来なかったので、これも所詮、そのレベルの話ではある。SI市場だって人は足りてない。
2．SI屋の問題か？
日本のほとんどの企業はITの開発維持管理はSI屋に依存している。内製化といっても、SI屋からの派遣で賄っているところが多数で、主導権争いの話でしかない。ごく少数で採用からやっているところもあるが、採用後のキャリアパスがはっきりしない上に、特に技能の向上策については準備されていないため、4-5年でタコツボ状態になっている。要するにほぼ日本全体でSI屋依存から脱却はできていない。
よって機械学習やら「人工知能」をユーザ企業が利用するのであれば、SI屋頼みになるが、これは、ほぼ絶望的に厳しい。「やったことないから、やり方がわからない。ユーザさんが教えてくれたら、その通りにやるから教えてください」である。ほぼ例外はないだろう。
要するにSI屋サイドもかけ声だけで、実態としてはどうしていいかわからないのが現実に見える。これはまぁ、ビックデータでもIoTでもなんでも同じなんで、これも以前からある。今更感も強い。
果たして「人工知能（以下AI）」ビジネスがイマイチの理由は、IoTとかビックデータとかそういうのが割とイケテいない理由とかなりカブるので、多分今後も問題のままだろう。そこについてごちゃごちゃ言っても仕方がないので、そうではなくてもっと「人材をある程度確保してSI問題もある程度クリアした先に、“まだある”本当の課題」について書いておく。
3.人間の仕事をアシストする、ということ。
冷静に考えてみればわかるが、「システムを使って人をアシストする」というのは別に人工知能に始まった話ではなく、そもそもIT自体の主たる目的の一つである。特別な話ではない。だからAI、AIと騒いだところで何かが劇的にかわるわけではなく、システムを積極的に使いこなしているところは、その延長線を延ばすだけだし、また、使いこなしてないところはAIだからといって何かができるわけでもなく、そのまま、あいかわらずITとは縁遠いままで終わる。
で肝心の問題は、割とちゃんと取り組んでいるところでの「考え方」だ。
■これから直面すると思われる本当の問題。
それなりにちゃんと取り組みつつあるというところが、頭を悩ませる問題がある。これは、今の日本の縮図そのものになるのだが、「では一体どこまで人にやらせるのか？」という問題だ。現状の日本の産業のほとんどは労働集約的だ。資本集約的な産業ですら、日本国内ではいつのまにか労働集約的になってしまっている。よって必ず、人の問題にぶつかる。
「なるべく創造的な仕事に人を回したい。無駄な作業は軽減したい」というのが経営陣の大体、共通見解。そのために推論的なサポートを入れたい。ところが、現実は「そういう創造的な人材は枯渇しつつあり、結局単純作業＋αが現状の人材の標準レベル」になってしまっている。IT的なサポートは必要な情報を適宜に提供するという方向にして、情報を集める事務的なコストを削減し、人はむしろそのサポートを生かしてより創造的な仕事に注力させたい。しかし、そもそもそういった情報を生かしてクリエイティブなことができる人材がいなくなりつつある。「AIのサポートを活かし切ることができない」また「判断に必要なデータが提示されたところで、そもそも判断ができるかどうか怪しい」こんな嘆きがかなり多い。
結果どうなるかというと、ITはむしろ自動化の方に振ってしまって、可能な限り現場には判断させないでほしい、という要望になる。そして、どうしても自動化できないところに人を入れる、という結論になる。とはいえ推論エンジンで全自動化は無理がある。よって自動化を進めると「人間が推論エンジンを助ける」という妙な役回りになる。人間をサポートするはずのITを、逆に人間がサポートすることになる。
「より賢いITに業務をサポートをさせようとすると、サポートするべき人間が見つからない」という話がちょくちょく出てきている。そんなバカな話はない・・・のだが・・・どうしてこうなった？というのがAI的なものを導入しようとするときの本当に壁になる。
■AI的なもの いやシステムのサポートは総じて全て「過去の経験の延長」でしかない
AIのような仕組みは基本的に過去データをベースに推論する。大抵のIT系サポートはなんらかの過去データに基づいていることが基本になっている。そのサポートを生かす、ということは過去のデータを参考にして、より良い結果、いままでとは違う結果、を上げていくことだ。
現場からすると、上記の話は当たり前のことで、そもそもAI以前の話だ。それをやろうと思ってもレポート作成やら本社や偉い人の指示やら会社の方針とやらで、やらせてもらえなかったというのが本音だろう。ところが、実際にそういうサポートが受けられるようになり、ある程度の判断を要求されるようになったときに、果たして結果をだすのが結構難しいどころか、できる人間がほとんどいないということになってきている。
「昔はそうではなかった。今は現場のレベルが下がった。」こういうことを言う経営者・マネージャーも多い。個人的にはまぁそーかなーとは思っていた。個人的な経験で、データを参照しながら、新しいアイデアを出して、それを実行計画におとして、先にすすめるという人はそれなりに居たし、結果も出していた。そういう人が減ったんだろうな〜とは思っていた。なかなかめんどくさい世の中になったからな〜、と。そもそも結果も出づらい。
ま、レベルが下がったなら、なんとか戻すとかすればいいのでは、とそう思っていました。が。
■本当にレベルが下がったのか？
それで、遠目で見ていると、・・・そもそも創造的な仕事ってのは、個人の資質なんじゃないか？と言う疑問がよぎる。そもそもそういう創造的な仕事をやれるような仕組みを会社がつくっていたのではなくて、才能ある個人が勝手に頑張っていて、それに会社がよりかかっていただけではないのかと、そんな考えがチラチラ浮かぶ。別に定量化しているわけでもなんでもないのですが。
そもそもバイタリティや想像力＋実行力がある人は、実は社内政治に弱い。当たり前で、そういう新規の試行錯誤をやる場合は、成功するより失敗することの方が多い。んで、これは普通はいろいろコスト増になる。コスト増を追い落とすのは簡単だ。なので、そういう個人はいつの間にか排斥される。いなくなるというか、辞めていく。
そしてとうとう居なくなったのではないかな？ そんな気が最近します。レベルが下がったと言うか、そもそも維持する努力をしてなかったのでは？
■過去とは違うことをやる、ということ
冷静に考えてみればわかるが、「過去データの出した結果」を上回る、より新しいことをやる、より上手くやるというのは簡単ではない。仕事を効率良く、ノーリスクでやるのは、過去の成功と同じトレースを「とりあえず」やることがもっとも近道だ。Expertな人がExpertであるゆえんは、過去の実績と現状を見た上で、自分なりの工夫を足していくからであり、いつまでも同じことをぐるぐるやっているのはプロというより初心者のアマチュアだ。
AIなりデータサポートなりを使いこなせない、むしろ自動化した方がよい、というのは、単に担当者がアマチュアなだけではないのか？人材がいない、というのは実はそういった「自分なりの工夫」をすることを会社の文化としてちゃんと支援してこなかったツケにみえる。いや、むしろ、会社の方針やら大人の事情やら「俺の経験」やらを押しつけて、本人の向上の余地をリスク回避やらコンプライアンスを理由に積極的に押さえこんできたのではないのか？
そもそも、別段上からの圧力がなくとも、「何が起きているのかの把握と過去データの収集・整理」で気がつけば時間の大半をとられ、その説明と言い訳、会議の根回しが通常業務になっていれば、これは確かに「過去を越える」などということはとてもできない。
仮に企業の個々人がAIなりデータなりいろんなサポートを受けるに値しない、ということであれば、それは実は、本当に意味でのプロフェッショナリズムが失われているということだと思う。AIの業務系の導入の本当の壁は、こういうところにあるように見える。
AIは過去のデータをストレートに「素早く」出してくれる。それに向き合うことができるかどうかが本当に課題だ。機械学習の人材を集め、SIの問題を解決しても、結局「新しいことができる人材」がいない限り、“AIビジネス”は、一握りの企業のバブルで終わり、永遠に離陸することはないように見える。ま、体感的にそんな感じ。
MVTO (multi-version timestamp ordering)
MVCC系の実装プロトコルの代表例。
そのほかにMV2PL（実際は2V2PLが多い）とMVSGTがある。なおMVTOにも様々なバリエーションがある。理論自体は1980年後半から存在している。version無制限というのは、従来のH/Wでは非現実的だったが、近年のノードあたりのメモリーの大容量化やNVRAMの登場によってそれほどデタラメな前提ではなくなりつつある。適切にGCをかけることやversion traverseを工夫することでパフォーマンスを維持することができる。その結果最近のMVCC系のプロトコル実装はMVTOが多くなっているように見受けられる。というよりもほぼMVCC＝MVTO一色の様相だ。実際、ベンチマークも数字は出ている。
（修正：MVCCの中にOCCではあるがMulti-versionを利用する形式のものをあり（MVOCC)、それもMVCCとすれば、MVCCはMVOCC+MVTOになる）
■MVTOのメリット・デメリット
1 メリット
・シンプルでわかりやすい
その他のプロトコルに比べて、ぶっちぎりでわかりやすい。ということは実装する場合はバグが出にくいというメリットがある。ただし理屈はちゃんと理解するとかなり深いところまで必要になる。実装は簡単だが理屈は深い。コンピュータ・サイエンスのお手本のようなプロトコルだ。(念のために言うと「簡単」というのは「動かすだけなら」と言う意味で。パフォーマンスを出そうとするとそう簡単ではない。)
・後で追加的な修正がしやすい
実際SSNのように仕組みをあとから追加することが容易だろう。MV2PLやMVSGTあたりに後から何か実装追加するのは、あまり現実的とは思われない。実際、2017年現在のMVCC実装である、Hyper Cicada Bohm等々はそれぞれ独自の味付けをしている。この辺りは別の機会にするが、ざっくりの印象としては、HyPerはそもそも新しい手法を提案しているし、CicadaはむしろMVTOを実直に行いエンジニアリング寄りに振った形、Bohmはできるだけシンプルにもってくるように感じる。骨格がはっきりしているので、肉付けが色々できると言う証左だ。
(修正：HyPerについてはMVTOではなくてMVOCC（ほぼOCC)という話もあるのであとで検証）
・read lock free
これはもはやDBMS界の常識なのでいまさらではあるが、readがブロックされない。ただし、これはMVCC固有のメリットではない。OCCも同じメリットはある。
なお、validationをロックと見るかどうかにもよるが、writeについてもmultiverisonなのでw-wの競合は発生しない。基本的にwriteについても2PLタイプのいわゆるlockは存在しない。
2 デメリット
・timestamp(以下ts)の維持がちゃんとできるか？
これができないとそもそもいろいろ崩壊する。ただ、これはTrueTimeである必要なくmonotonic increasedであれば十分である。現在の事情ではそれほどデメリットとはいえない。とはいえ、ボトルネックにはなりやすい。tsの管理は、一体、(a)どのtsを使うのか、(b)どうtsをとるかがポイントになる。各実装を見る時には、この2点に絞って違いをみていく必要がある
・versionの管理をどう捌くか？
もともとmultiversionのコストの大半がversion管理なので、この問題は常に顕在化する。
課題としては大きく以下の二つ。
1. versionトラバース
基本戦略はversionトラバースをさせない。だらだらトラバースさせると時間を食うし、キャッシュラインが汚れる。うまくキャッシュを使う方法や、そもそもトラバースさせないようにする手法などが使われる。
2. GC
基本version数は無制限なので、どこかでGCする必要がある。いつ・どうやって行うかが手間になる。現状のMVCCはとにかくスループットが跳ね上がるので、普通に 3 million TPSあたりが普通の基準になる。数10msであっという間にstale recordが数百MByteになったりする。うまくやらないとあっという間に何もできなくなる。
・ロングバッチが走ると絶望的にabort率があがる。
これは、OCCも同じであり、むしろtransaction一般の問題に近い。MVCC固有の問題とするのは酷だろう。対処は基本リトライになる。よって以下にうまくリトライさせるか？がポイントになる。そもそも単一の仕組みでは対応できない気が個人的にはしている。
OCCの比較や、より細かい話になるとまだいくらでもあるが、ざっくりのポイントとしては上記が代表的な論点になっている。
■MCSR
後段のように事実上version orderが事前に決定するので、validation phaseでの論理的なMVSG(Multi-Version Serialization Graph)がすべてのMVSRをカバーするわけではない。ということは偽陽性がある。single-versionのOCCよりも理論的にはabort率は低いとはいえ、もっとabort率を低減する手段はheuristicではあるが存在するはず（一般解はNP完全）。なので、追加的に色々措置を講ずるのはありだとは思うが、今のところその有効な手段を人類はまだ発見していない。
MVTO自体のserialization空間はMCSRよりも狭いと思われる。
・w1(x1)w2(x2)r3(x1)c1c3c2だと、r3の時にtx2が追い越しになるのでtx2はabortになるが、tx1-tx3-tx2でserializable
要は追い越したときに
・MVSR：前後にversion orderを変更
・MCR：後ろにversion orderを変更
・MVTO：abort
になっている。とはいえ、MCSRの一部は実行可能で
CSR＜MVTO＜MCSRだと思われる。
■実装プロトコル：
Tx本より引用する。
1. read step (ri(x))は自身ts以前（含む）でかつ、最大のtsをもつversionを読む。
すなわち ri(x)→ri(xj)でts(tj) ＜= ts(ti): j = Max version number of x
2. write step (wi(x))は以下の順で処理
2-1 そのwriteが生成するtsよりも後のtsをもつreadが、そのwriteが生成するversionよりも前のversion（そのwriteのtsよりも前のtsをもつtxで生成されたversion）を読むことになりそうな場合は、abortする。
すなわち、rj(xk): ts(tk) ＜ ts(ti) ＜ ts(tj)が存在する場合は、wi(x)はabort
2-2 でなければ普通にwi(x)を実行する
3. readのコミットはそのreadが読んでいるversionを生成するwriteを含むtxのコミットが終了するまで遅延させる。これはdirty readの防止＋リカバリーの保証になる。
日本語で書くとちょっとわかりづらいが、要するに「readするときは必ず最新のversionを読んでいる」ということ「だけ」が保証されていれば良い、というプロトコルである。たったそれだけでfull-serializableである。
書く方は「readするときは必ず最新のversionを読んでいる」と言う不変条件を満たさないときはabortし、それ以外には何も考えずに書き込める。*1
以下論点
■最新のversionとは何か？
MVCC系では、この「最新のversion」というのを（単純にlatestって言うと後から割り込んだversionがlatestになるので）、あるTxから見た「visible version」という言い方をすることが多い。場合によっては定義なしでvisibleという言い方もしたりするので、その場合は確認した方が良い。
Cicadaの場合の定義を貼っておく
The visible version of a record for a transaction is a version whose write timestamp is the latest (highest) among all committed versions of the record and is earlier (smaller) than the transaction’s timestamp.
ただ、MVTOではdirty(possible committed)なwriteも読むことができるようになっている。基本的にはCommitted Projectionが前提になっているので、commitされる前提（ただしrecoveryのことがあるのでcommit orderは決まっている）は敷いている。なお、実装的には上記にある通り、committed versionを使うのが主流なので、一見するとSnapshot Isolationの制限版と同じに見えるが理屈が全くことなる。
もちろん念のために言っておくと、字義どおりにcommittedだけを対象にすると自分が書いたものを読めなくなるので、そうならないようにどの実装も工夫はしている。
■serializablityの証明
CC本から引用する。
まずformalization
The following properties describe the essential characteristics of every MVTO history H over (T0, . . . Tn).
Property1.
For each Ti, there is a unique timestamp ts(Ti);
That is, ts(Ti) = ts(Tj) iff i = j.
tsの定義。注意すべきは別段startimeにはしていない。順序があれば良い。
Property2.
For every rk(xj)∈H, wj(xj) ＜ rk(xj) and ts(Tj) ＜= ts(Tk).
読むべきものは書かれていること。ここは普通はcommitであるが、別段installでも良い。
Property3.
For every rk(xj) and wi(xi)∈H, i!=j,
either (a) ts(Ti) ＜ ts(Tj)
or (b) ts(Tk) ＜ ts(Ti)
or (c) i = k and rk[xj] ＜ wi(xi).
version orderの属性。(a)はvisibilityの属性(kは判断されない) (b)はvalidationの基準（kとiが交差するとき）(c)はまぁ常識で
Property4.
If rj(xi)∈H, i!=j, and cj∈H, then ci ＜ cj.
読む場合は必ずコミット順がある。
そしてProof
Theorem : Every history H produced by MVTO is 1SR.
1SRはone-copy-serializableのこと、少なくとも一つのmonoversionでserialなスケジュールと同一のsemanticsが保てるということ。
Proof:
Define a version order as follows : xi ＜＜ xj iff ts(Ti) ＜ ts(Tj).
version orderの定義
We now prove that MVSG(H, ＜＜) is acyclic by showing that for every edge
Ti -> Tj in MVSG(H,＜＜), ts(Ti) ＜ ts(Tj).
証明のターゲット MVSGが非循環であれば良い。
Suppose Ti -> Tj is an edge of SG(H).
グラフのエッジ＝dependency
This edge corresponds to a reads from relationship.
この段階でのdependencyはRF
That is, for some x, Tj reads x from Ti.
By Property2, ts(Ti) ＜= ts(Tj).
By Property1, ts(Ti) != ts(Tj). So,ts(Ti) ＜ ts(Tj) as desired.
全順序
Let rk(xj) and wi(xi) be in H where i,j,and k are distinct, and consider the version order edge that they generate.
あるxについて読み書きがぞれぞれ別にあるケースは以下になる
There are two cases:
(1) xi ＜＜ xj, which implies Ti -> Tj is in MVSG(H, ＜＜);
and (2) xj ＜＜ xi, which implies Tk -> Ti is in MVSG(H, ＜＜)
全順序なのでversion orderが形成できて、その場合はどちらが先になるので、それぞれのケースでMVSGのエッジが形成される。
In case (l), by definition of ＜＜, ts(Ti) ＜ ts(Tj)
In case (2), by Property3, either ts(Ti) ＜ ts(Tj) or ts(Tk) ＜ ts(Ti)
The first option is impossible, because xj ＜＜ xi implies ts(Tj) ＜ ts(Ti). So, ts(Tk) ＜ ts( Ti) as desired.
Since all edges in MVSG(H, ＜＜) are in timestamp order, MVSG(H, ＜＜) is acyclic.
最初のケースは前提(Property2,1)からありえないので、(2)のケースのみ成立。よってトポロジカルソート可能。
あとはMVSG一般の証明
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で、かつその時に限る。要は、MVSGが非循環あれば（かつその時に限り）1SRである。
証明はこちら。multi-versionの基礎 - 急がば回れ、選ぶなら近道
要はこの定理がまずは前提になっているということ。
以上終了。
ちなみにこのMVSRはrk(xj) とwi(xi)において、ts(Tk) ＜ ts(Ti)の維持なのでMSCRになる。（つまり偽陽性はある。）基本的にr-wを維持する形になっている。MVTO⊂MVSRなのは上記の通りで良いとして、MVSR != MVTOの例は簡単にわかる。
w1(x1)w1(y1)w1(z1) r2(x1) r3(y1)w3(x3) w2(x2) r4(z1) w3(y3) r4(x3)w4(x4)c1c2c3c4
でMVTOはアウトだが
w1(x)w1(y)w1(z)c1 r2(x)w2(x2)c2 r3(y)w3(x)w3(y)c3 r4(z)r4(x)w4(x)c4
でserializable。要は追い越しで書いても後続で追い越しの値しか読まないのであれば別に問題ないということだ。（通常は書き込むその値を事前に読まずに書くということはまぁないのでMVTOでも良いという考え方もあるが、ある値が一義的に別の値で決定されるときには別に読まずにノータイムで書けるはずなので、そのようなケースがはねられてしまう。）
プロトコルを見れば、恐ろしく簡単で、しかもreadは全てブロックされない。writeのみがvalidationがかかって、readとその読んでいるversionに「割り込む」場合のみabortすれば良い、ということだ。それでserializableが保証される。
ちなみに実装はrecordにwriteのtsとreadのtsを打っておけば、それでほぼ判別できるので、そういう形が多い（BOHMはちょっと工夫している）
余談だが、MVTOは2017年のVLDBのCicadaで実装されているプロトコルで、公称ではFoedus/MOCC/TicTac等を軒並み抑えるパフォーマンスを出している。前述のようにCicada, BOHM, HyPer, ERMIAあたりはこの方式が根っこである。今後MVCCを見ていくときは上記のMVTOはほぼ前提になっているので、理解しておかないと真面目にわからなくなる。
例えばMSのSQLServer2014 (Hekaton)はMVCCですぜ、と論文を出しているが、背景に想定しているプロトコルは MVCCではない。BOCCを想定している。高速化や使い勝手の問題で形式はmultiversionを利用している。これをMVCCというかどうかは本来であれば議論が別れるところであると思う。
なるほど、形式がmultiversionであれば広義のMVCCだという言い方も可能ではある。ただしそれを言い出したら、極論すればbefore image/after image方式も2versionのmultiversionになるので、この手のリカバリー方式をとっているDBは全部MVCCになる。そんな馬鹿な話はない。
Hekatonの場合はBOCCであり、よってserializationのセマンティクスはCSRである。一般にMVCCのserializationのセマンティクスはMCSR（またはそれに同等）であるので、スケジューリング・パワーという意味ではHekatonはMVCCの広さほどにはない。
スケジューリング・パワーの差は偽陽性の範囲にかかわり、今の分散OLTPの争点の一つがabort率である以上、看過できない論点のはずだ。個人的はMCSR同等のスケジューリング・パワーがあって初めてMVCCを名乗る資格があると思う。その意味ではHekatonはMVCCというよりもOCCに近い。（正直、この辺りがわかっていてVLDB/SIGMODあたりに採択されているのか多少疑問を感じる）
確かにTPC-CやYCSB前提であればそれほど問題にならないかもしれない。が、実際のアプリケーションの適用時点でパフォーマンスに差が出て来る可能性はある。実際 (MCSR-CSR)なスケジュールが多数出るようなアプリケーションの場合は、極端に差が出るだろう。両者共にserializableのisolationの設定であるにもかかわらずである。
そんな感じ。
(前回はMVCCの一般の話を基本にまとめた。今回はそれをベースに実装プロトコルをまとめた。次にそのreference implとしてCicadaを解説する（予定）。)
*1:と書くと正確ではない。より前に遡ってversionをつくるということも実は可能で、この場合はMCSRではないMVSRになる。ただし、これは全部がconcurrentに走っている前提があるので、commit orderを考えるとちょっと面倒。なのでここでは目をつむる。
クラウドに基幹を移行して5年超経過
もう5年か、まだ5年というべきかちょっと判断に迷う。大抵の業務系のシステムがクラウドを始めるのは現実的には今年来年以降になるので、今の自分達の状況は多分、今後の業務系システムをクラウド移行したユーザの近未来になると思う。ので、予想的にまとめておく。本格的にクラウドを利用した業務アプリケーションの5年がどうなるかの一つの指針になるかと。
以降は別に統計データでもなんでもなく5年間を眺めてみて自分の印象。
・障害：大規模は５年で2-3回程度。一度は業務に影響が出て客先にお詫びに行った。AWSだったけど、サポートからは「もう回復してるのでチケットクローズね」みたいな話だったと記憶している。その後は大体四半期に一回程度のN/W障害。障害は普通に起きているし、オンプレと比べてどうか、という比較では細かい障害件数は減った気はしていない。ただし、「ドカンと来るでかい障害」は確実に減った。
・データ増加対応：問題ない。物理容量が足りませんということはあまりなく、単純に予算があれば普通にデータ増加には対応できている。もちろん作りの問題はあるので、計算時間がデータ量に対して非線形に増えるようなケースではアウトだと思うけど、別にそんなnewbな作りはしないので、この辺は本当に無問題。
・パフォーマンス：向上している。これはクラウドは「間接的」に寄与していると思う。自分たちだと稼働基盤をHadoopからSparkに変更しているところが大きい。Asakusaの最大のメリットであるポータビリティの高さによると思う。裸MapReduceとかHiveあたりで無理やりやっていたら、即死か移行コストが青天井だったと思う。（そもそも業務系バッチ中心のシステムなので裸MRとかHiveはありえないのだが、この期に及んで未だにMRだとか錯乱気味のプロジェクトはある）その意味ではあんまりクラウドは関係ないけど、同コストでそれなりパフォーマンスがでる環境に移行が容易というのはクラウドならでは。
・アプリケーションの寿命：確実に伸びた。後述するが、ハードサポート切れという「寿命を切るトリガー」がないので、ソフトウェア自体の耐用年数は実質的には長くなったと思う。特に機能にあまり変化のないものについては、自分たちのケースだと例えばEDIだとかは業界の共通プロトコルが変わらない限り、真面目に今後20-30年は保つのではないかと思う。
・コスト、特にTCO：
特にTCOは間違いなく低減した。だいたい20%程度はオンプレに対して人件費を含めたトータルのコストは減少している。クラウド移行のメリットはコストであることは、この5年で明確になった。ただしこれはシステムの性格やクラウドの使い方によるところが大きい。割と頻繁に手を入れるシステムで、細かい障害対応が必須であれば、クラウドのメリットは低い。これは相対的なもので、単純に開発/運用人件費の人件費の総工数に対する割合が高いことによる。機能変更・追加があまりなく、障害対応も最悪リトライでなんとかカバーできるというシステムについてのみコストが下がる。ただし、別に半減するとかそういう感じではなく、20%-30%程度の低減になる。
一部の「クラウド推進派」はコスト削減がクラウドのメリットではないと言っているが、プラグマティックな主張とは言えない。割と明確にコストが下がることが明確に見込まれるものについて、ちゃんと見積もってクラウドに移行することが正しい。現状のクラウド移行は一種の「政治利用」の側面の方が強いが、これはエンジニアリングでもなんでもない。その意味で一部の「クラウド系意識高い系エンジニア」はエンジニアは廃業して政治家になった方が良いと思う。
・DevOpsとかは関係ない
海外はともかく日本では関係ない。ユーザのシステムの「実装主体」がユーザのプロパーでない限りはどんなに頑張ってもDevOpsはできない。現状のユーザ環境は優秀なエンジニア（リサーチャではない）にとっては、特にそのキャリアパスから見て魅力的ではないので、優秀なエンジニアはユーザ企業に定着することはない。したがって、クラウド環境だからDevOpsとかそういう話はあまり関係ない。
□大きな印象：以下はあくまで自分の印象。極端だなという意見もあると思うが、割と悲観的に見てる。
やはり、大きなと感じるのは「ハード保守期限切れトリガー」によるSIは確実に減るということだ。これは今後のクラウドに業務系システムが本格的に移行するのであれば、SI市場には影響があると思う。
1.クラウド化によるハード保守期限切れからの解放は、システム自体の寿命を伸ばす。そして「それに纏わるいろんなもの」の寿命も伸ばす。
クラウド化はハード保守期限切れによる強制システム更改を事実上なくす。結果、クラウドに乗ったシステムに対する大規模SIの機会は間違いなく減少する。その結果はいろいろな余波を生む。
ハード・リプレースは往々にしてシステム全体の刷新の良くも悪くもチャンスであり、表に出なかった不都合もそのまま「闇から闇に葬る」ことが可能であった。これは別段システムそのものの話だけではなく、システムに纏わる人の在り方、組織の在り方にも当てはまる。
IT投資は全てがクリーンという訳ではない。いわんや、従前よりも複雑化し、理解するために習得すべき技能も格段にレベルアップした現在のITでは、ユーザから見たときのシステムのブラックボックス化・不透明さは格段に増している。その中に押し込んだ、技術選択の機微から始まってユーザ社内の政治まで含めて、「大人の事情」はいくらでもある。システム更改はそういったものをうまく洗い流す機会であることは間違いない。そういう機会は減って行くだろう。
特に構築という意味では、クラウド化したところで、ユーザのSI屋依存と、IT業界のSIビジネス依存の共依存の構造には変化が起きているわけではない。基本的にはハード調達のあり方が変化したに過ぎない。結果として、そのままユーザ・ベンダー双方の関係もそのまま残るだろう。仮にそれが一種のもたれ合いだった場合には溜まる澱もそれなりに増える。
逆説的だが、ユーザのSI屋依存と、IT業界のSIビジネス依存の共依存の構造は「クラウドでむしろ強化」されるだろう。いいか悪いかは色々ある。「もたれ合い」と「コミュニケーションの容易さの確保」は表裏一体だ。が、ハード・リプレースの外圧的な変更要素の減少は、まかり間違うと腐った温床をいい塩梅に隠蔽することになるのは間違いない。
2.広い意味での「ミドル/環境」サポートが目につくようになる。
ハードの次にサポート問題になるのは果たしてミドルウェア/ソフトウェア環境になる。今ままではハードサポートが切れてハードをリプレースするタイミングで、ミドルや環境も「ついでに入れ替え」ていたのであまり顕在化しなかった。今後は「ミドルも次のハード・リプレースまで頑張って持たせろ」というゴリ押しが効かなくなる。
現状のSI屋のR&D投資余力は底をつきかけていて、ミドルウェアの開発はOSSにシフトしている。加えて、ユーザも「OSSでコストが安くなる」という幻想を持っているので、OSSの業務系への採用が進んでいる。OSSのvupのスピード感や下位互換性への無愛想さは、通常のプロダクトでは比にならない。もちろんOSSの下位互換サポートを売りにするSI屋も出てくるが、当然高コストになる。（そういうSI屋のエンジニアのモチベーションは置いておく）
クラウド化とOSSの普及はユーザにミドルサポート・環境まわりの「賞味期限」に目を向けさせるようになるだろう。例えばセキュリティパッチだったり、メニーコア対応のAPI変更だったり、従来のフレームワークのサポートのdepreciatedだったり、JVMのversionだったり、ユーザからすると「なんでそんなことの変更でシステムの変更になるの？」という今まであまり目立たなかったところが徐々に目につくようになるだろう。
その結果はアプリ側としてどれだけポータビリティを持たせるべきか？ということにもなる。これはアプリの資産性確保にどれだけ投資するか、ということに最後はつながる。ソフトは「ハードのおまけ」の慣習から抜けきれないところはこのコスト負担には承服しかねるだろう。ハード・リプレースSIのコストに埋没していた「ソフトウェアのコスト」がフリーランチではなくなる。どう考えるかユーザの考え方次第だろう。
3. 曖昧にしていたIT投資のあり方が問われる。
単純に「シャチョウ〜、もうハードがサポートできないとファミ通が言っております！仕方がないので一からつくり直さないとまずいっす。（なので金くれ）」攻撃ができなくなるということだ。運用投資や再構築投資の影に隠れたR&Dは基本的にやりづらくなる。さらに現状では、日経ビジネスあたりに「シニア世代を生かせ！」みたいな記事が出ておりまして、IT投資での効率化より、シニア層でピラミッド作った方が効率良い、という主張も容易になってしまっている。こうなってくると「効率向上のため」のIT投資のROIが真面目に問われるようになる。
実験的なITに、より金をかけての本番投入は減るだろう。おもしろいものを本番に投入していくということがゲリラ的にできなくなる。IT投資でリターン「だけ」を錦の御旗には現実はなかなか厳しい。ハード・リプレースの後押しは強力だった。・・・不思議なもので本来クラウドは小規模スタートを手軽にやるということが最大のメリットだったわけだが、ハード・リプレースの欠如によるシステムの延命化は、硬直した組織構造と相俟って「冒険のコスト」をさらに押し上げ、そのメリットを消し去るかのようだ。山のようなPoCは行われるが、本番にいざ使いますという壁はより高く、いつの間にかビックウォールと化す。
4.「現行」クラウドの位置付けがより明確に見えるようになる。
クラウド化は本来拡張性を担保する仕組みではあったはずだが、現状の日本ではまず間違いなく「既存システムの延命措置」としての機能する方が、残念ながら「効率が良い」ということになりそうだ。拡張性や今後の方向性という意味ではやはり、コストや仕組みも含めてエンプラでのシステムあり方そのものから見直さないとクラウドでの「システムの拡張性」は生かせないように思う。
クラウド・ネイティブって言い方はもはや語弊しかないので、良い言い方ではないが「クラウドでしかできない仕組み」を作って初めてエンプラシステムのクラウド化のメリットが取れたと言える気がする。既存を「徐々にクラウドに移行して行きます」というのは、そう言っているその時点でアウト。単なる延命措置に終わるだろう。クラウドという最新に思われた技術がむしろシステムの刷新の壁になるというのは皮肉なものだが、まぁ世の中そんなものかもしれない。
クラウド環境は確かに拡張性が高く、いろいろなトライができる最適な環境といえる。特に開発環境を簡単に構築・パージできることはITへの試行錯誤の機会を大幅に増やすことが可能になる。ただしこれは、「どう試行錯誤するか？」について明確なイメージを事前にもっていることが前提で、そうでなければ、クラウド環境は実は既存システムの「非常によくできた生命維持装置」として機能するにとどまるだろう。
まぁ当たり前の話だが、システムに投資するなら「ハード・リプレース」という隠れ蓑は使わずに、ちゃんとリターンが客観的にわかる形で行いなさいよ、とこうなるわけだ。経済が右肩さがりの状況で、思い切った投資がさてできますか？ クラウド化したシステムからはこういう試金石が投げ返されることになる。日本の高齢化はシステムの高齢化であり、クラウドはどうやらその流れを加速させるかのようだ。はてさて。
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的な準備はある程度できているので、まぁ無難にということになるけど、まぁ過渡期だよね、というのが本音。会社云々はともかく、自分個人の将来の方向性という意味では、この辺りを見ているということで、来年色々動いていきましょう、という感じですね。
