Asakusa 0.10.0
Asakusa 0.10.0について
あけましておめでとうございます。今年もよろしくお願いします。
のっけからアレですが、これはAsakuas Advent Calendar 2017のエントリーなわけ（個人的には12/31までがクリスマスとかそんな感じの年末催事なのでそのつもり：2017/12/30に追記）（って書いてたら、年が明けたけど、個人的にはあと3ヶ月は2017年の感じなので：2018/1/4にさらに追記）
Asakusaで、先日0.10.0をリリースしている。ある程度刻んでリリースして行く、というのがAsakusaのポリシーではあるが、今回のリリースはちょっとした節目にはなっている。
http://www.asakusafw.com/
◆一つの区切りとして
とうとうというか、今更というか、ようやくというか。MapReduceのサポートについて一つの道筋をつけた。Hadoop界隈では常識だが、すでにMapReduceは新規の開発はされておらず、プロトコルとしてはすでにその役割を終えている。”Goodbye MapReduce”と言われたのは2015年ぐらいだったので、もう2年は経過している。
それでも裸MapReduceでの鋭意開発中のプロジェクトなどもちょいちょい聞こえており、日本のSI屋の宿業(と書いて怨念と読む)については何をか言わんやである。
とまれ、MapReduceをどうするという問題であるが、Asakusaの立ち位置が業務システムをサポートする役割がある以上、OSS業界が「はい、さようなら」したからと言って、こちらも「はい、さようなら」というわけには行かない。なので、どう筋道をつけていくかが課題ではあった。
いろいろ議論があったけれども、結論は明確で、今後の「新機能」についてはMapReduceはサポートしない、という方針だ。これは別に「現状のAsakusaで書かれたアプケーションをサポートしない」ということではない。今後も現状（すなわち0.10.0以前）のAsakusaで書かれたアプリケーションはサポートするし、リコンパイルすれば今後サポートされるプラットフォームでも動くだろう。ただし、将来のAsakusaの言語拡張は現状のMapReduceでは動かない、ということになる。
広い意味でのDAGでの実行処理という意味では、本来はいろいろな実装選択が可能であり、MapReduceを前提するのではどうしても制約が強すぎるという面がある。MapReduceの制約は、現状の発展しつつある分散プラットフォーム上ではメリットよりもデメリットが大きい。今後の機能拡張を行うのであれば、それは外していきたい。
◆新機能
従来のMapReduceが前提であれば、実装できない機能で、要望の強いものを順次実装している。詳しくは、http://docs.asakusafw.com/0.10.0/release/ja/html/release-notes.html
になるが、Viewだとか、使い勝手をあげる演算子とか、環境周りの強化をおこなっている。開発効率は上がっていくだろう。
繰り言になるがAsakusaの後方互換性は維持される。したがって、現状の機能で構築されたAsakusaアプリケーションはメンテナンスしていくことは可能だし、プラットフォームを変更しても利用していくことは可能だ。
◆アプリケーションのライフサイクル
果たして、日本の業務系システムのライフサイクルとOSSミドルのそれは端（ハナ）から一致しない。今後この乖離は拡大することはあっても縮まることはないだろう。
システムとは作った人/運用している人、「そのもの」である。日本全体の老齢化は、そのまま「システムの老齢化」になり、それはそのまま延命化になる。その一方で、OSSミドルは巨大ユーザお抱えのコミッターが開発の主役になり、開発サイクルは特定ユーザの都合に左右される。概ね、OSSのライフサイクルそれ自体は短くなる。このギャップは広がる一方だろう。
世界のソフトウェアはITベンダーによる開発から特定ユーザによる開発に軸足が移りつつある。また、ITベンダーもそもそもその数を減らしつつある。日本国内に目を向ければ、SIビジネス圧力下では、ソフトウェアは付属品にすぎない。結果、投資回収の目処が立たず、商用ミドルウェアの開発はゼロに近くなっている。以前にもまして、F/N/H/NTTD各社は、実際は海外の少数特定ベンダー製品の利用か、またはOSSの依拠している。
すなわち、日本の企業ユーザは自社のシステムを維持するのであれば、ライフサイクルの異なるOSSに無理やり追随していくか、または少数ベンダーの寡占に付き合って高い税金を払っていくしか選択肢がなくなる。というか、実際そうなりつつある。
Asakusaの問題意識のひとつはこのギャップにある。DSLで書いていてくれば、その投資可搬性（portability）を保証することを、そのギャップの解決案の一つとして提示している。実際に効果も出ている。
◆実際のケースとして
Asakusaの主たるプラットフォームは年月を追って変化している。すなわちHadoop→Spark→M3BPだ。これはパフォーマンスとデータサイズのフィッティング、そしてサーバサイドのアーキテクチャの変更によるところが大きい。
当初のHadoopはそもそもの分散処理の導入が目的であった。現状では無駄に見えるオーバーヘッドを犠牲にしても、当時は分散処理の導入はメリットが大きかった。それほどまでに従来のバッチ処理は遅かった。
ある程度Hadoopが普及してくるとそのパフォーマンスの悪さが目立つ。そんな中でより無駄をなくしてスループットをあげる目的でSparkが登場してきた。分散処理のOSSもMapReduceも完全に廃棄され、現状のデファクトはSparkだろう。(とはいえ、現在のSparkも今後2-3年もすれば別の形になるか、または別の基盤にその道を譲るだろう）
Asakusaもそれに追随していった。そしてここ２年はサーバサイドのアーキテクチャがメニーコア・安価なメモリーによるメモリー大容量化が顕著だ。これを乗りこなす形でM3BPをサポートするようになってきている。
ノーチラスが直接サポートするお客さんの環境も、同様に変化しつつある。某小売さんのバックエンドはHadoopからSparkに移行が完了した。某食品製造のお客さんの環境はHadoop→Spark→M3BPに移行が終わっている。また某社の原価計算はSparkからM3BPに移行中だ。どれも再SIのコストはかかっていない。
特に某小売さんのバックエンドはレジ締め・テナント処理・仕入買掛・支払まですべて処理するバッチ処理の塊の大きなシステムで、実際のSIでは担当したSI屋では大赤字だった案件だ。現在、ミドルはウチで、作りの部分は当時の下請けのパートナーと運用・追加開発をしている。大きな規模のシステムなのでプラットフォームの変更は、大規模なストレートコンバージョンか、やり直しSIになり、どうしようもないコストになるのが普通だが、Asakusaで全面的に書かれていたため、保守+アルファのコストで移行ができた。
個人的には「大きな負債」になる可能性が大いにあったシステムなので、ほとんどコストがかからずに新しい環境に移行できているのは、ものすごくホッとしている。稼働して高々5-6年で「プラットフォームが完全に賞味期限切れなんで、新しいものに乗り換えませんか？ちなみに値段は云億円です」と言う羽目にならなくてホントよかった。
◆今後の方針
以前から書いているように今後のサーバアーキテクチャは、メニーコア・大量メモリーが基本になる。同時にまた、不揮発性メモリーの利用も視野に入ってくるだろう。そうなると、現在の、特にDBを始めとするミドルウェアは抜本的な「作り変え」が必要になるだろう。
特に現状のDBは、根底の前提がディスクベースになっているため対応することが非常に困難だ。この新しいアーキテクチャに対応したデータベースが登場してくるだろう。大規模OLTPや、またそのOLTPとOLAPを統合したHTAPにあたるようなものだ。今後のAsakusaの対応焦点はここになる。
- 大規模OLTP
これについては特段述べる必要もない。現在のRDBの次世代版であり、事実上、既存RDBのリプレースを担うミドルになる。Oracle, MS, SAP-HANAといった商用DBはすでに対応を始めているし、新しいOSSも試験的ながら開発されている。このようなOLTPのバッチ処理の高速化を担うことが今後のAsakusaの役割になると思う。
メニーコア・大量メモリーOLTPでのAsakusaの処理の肝要は、“個人的”には「Asakusaによる並列書き込みとDBサイドのトランザクション制御、とくにserializabilityの確保、との調和」になると思っている。現状のRDBでも次世代OLTPでも書き込み処理のパフォーマンスは常に戦場になる。(OLTPに関して言えば、OCCにおいてはwrite-lockからのvalidationが、MVCCにおいては、最良のケースでwrite-lock freeになるが、その場合で、も同じくvalidationのコストがかかる。現状のRDBとは“同じ書き込み処理”での戦いと言っても、その様相はかなり異なる)
これをAsakusaの目線で言えば、バッチ処理では「一斉書き込み」をシーケンスに行なっていてはスループットが上がらない。メニーコアを利用した並列書き込みが必須だが、処理自体はACIDなロングトランザクションに包含されなければならない。とはいえ、そのままトランザクションに放り込むと「まんまシーケンス処理」になり停滞する。ということでアレコレ工夫が必要になる。
果たしてAsakusaがOLTPに介入するとして、どのような方式でそれぞれのトランザクション・マネージャと連携していくかを模索する必要がある。OSSであれば、やっていることがわかるので、より下位レイヤーに、商用DBであればやっていることがよくわからないので、必然的に比較的上位レイヤーでの介入になると思う。いずれにしても、まぁ要するに簡単な話ではない。
ただし、この処理がちゃんとできるのであれば、現在の業務系のバッチ処理はトータルの処理時間が、いよいよ分から秒単位での世界になっていくだろう。従前では、データを分散クラスターに移してしまえば、数時間かかっていた処理は、Hadoop, Spark, M3BPの中で数分の処理にまで短縮することができていた。ただし、データをクラスターに移す、または元のシステムに戻すことに時間がかかり、トータルの時間コストはやはり短縮が困難であった。
OLTP上で分散バッチ処理が実行可能であれば、RDB上のデータを分散クラスター環境にETLする必要がない。データのダウンロード/アップロードはコストがかかっていたが、それが不要になるわけだ。これはいろいろとできることが変わる。
- HTAP
Hybrid Transactional and Analytical Processingの略で、要するに今までのOLTP(業務系・基幹系)とOLAP(分析系)の実行基盤を統合したものだ。外側からは透過的に一つのDBに見える。透過的、というのがポイントで、実際は「物理的に一つのデータベース」というよりも、OLTPコアとOLAPコアは別々に処理する複合的なアーキテクチャが主流だったりする。ただ両者の間は高速のインターコネクトで繋いでおり、データ更新のOLAPへの遅延はmsec程度のレンジに収まっている。OLAPの用途によってはほぼリアルタイムに見えるはずだ。（また、OLTPとOLAPの処理コアのみを分離し、データは共有メモリーに置くという方式もある。）
ノードやシステムを今までの「業務系」と「分析系」と分ける必要がない。特に今後は機械学習の結果やデータ分析の結果を自動的にシステムの挙動に反映させることが必要になるだろう。その場合には、分析系システムの業務系システムからのデータの取得、分析系システムの計算結果の業務系システムへの反映、といったタイムラグを可能な限り少なくすることが望ましい。現在のビックデータ・IoT・AIといったより高度な情報を探究する流れの中では、HTAPはその利用を最大限に活用するための必然的な仕組みであると言える。
もっとも、OLTPのデータ更新とOLAPのデータ参照の同期と言っても、簡単な話ではなく、今までと同じように様々な問題を解決しなければならない。
一つは耐障害性の話で、これは通常の分散ノードクラスターでの障害対策とロジックは通底する。OLAP側で複数のread replicaをつくり、OLTP側でwrite replicaをつくった場合に、それぞれが障害を起こした場合にどう対処するか？という問題だ。
今までの分散ノードクラスターとはレイテンシーの桁が違うので、従来のクラスターの耐障害性対処とはロジックは同じでも、処理アルゴリズムや実装は異なるものが必要になるだろう。いまのところはあまり冴えたやり方はない感じだ。間違いなく今後研究/開発の対象になる。どこも解決案を模索していて、「超高速ZK」とかコレじゃない感的なものが漂ったりしているのが目撃されています。正直、今までの分散合意とはちょっと異なる側面、例えば一種のone-side synchronization的な解決法がいるのでは？と個人的には思っている。
二つ目はconsistencyの話になる。透過的に一つのDBに見えるということは一貫性が担保されているということだ。普通に考えればOLTPからOLAPへのデータ同期はsnapshot isolationになるが、OLAPがread onlyであれば、まずwrite skewの問題が発生しない。・・ので問題ないじゃんと言いたいところであるが、やっかいなread-only anomalyが発生する。ので、さてどうしたもんかという話。
個人的にはOLTPとOLAPでのデータ共有のアーキテクチャは一種のmulti-versionと見ることが可能であるので、MVCC系の解決案にヒントがあると思っている。もちろんナイーブなMVTOの実装よりもより工夫されたものが必要になる。例えば、SSNの実装の一部はHTAP には有効だろう。
・・・さて、こう言ったHTAPに対するAsakusaの位置付けは、OLTP系の更新バッチ処理とOLAP系でのバッチ処理の統合ということになる。業務的な例で言えば、継続的なデータ更新をOLTPで行いつつ、同時にOLAP的なレポートも作成するというような処理群の透過的な管理になる。
個人的にはHTAPについてAsakusaがどういう方式で関与していくのか？はちょっと現時点ではっきりしていない。実装的な話としてはOLTP的な介入の仕方の延長戦場にはあるとは思う。
が、気になるのはOLTPサイドとOLAPサイドのセマンティクスのあり方が今ひとつ見えていないということだ。明らかにOLTPとOLAPでは「同一のデータモデルに対して異なる実装アプローチ」が採用されるはずである。そうでなければ、効率が悪い。このようなレイヤーにまで、どうアプローチするのか？がポイントになる気がしている。
これはHTAPを利用した独自の「アプリケーションのあり方」が登場するのか？または旧来のアプリケーションの「寄せ集め」になるのか？という点にもつながる。いまのHTAPの想定上位は、「旧来のアプリケーションの「寄せ集め」」に見えるが、これでは済まないように思う。これらの立ち現れ方によりAsakusaの立ち位置や介入方式も変わるだろう。
いずれにしろ、OLTP/HTAPが使われる時期はもうすぐそこまできており、その時分には「リアルタイムなデータの更新と高速なデータ処理」が普通に使えるようになるだろうし、そのような基盤としてAsakusaは提供されるようになるだろう。
■とはいえ結局は同じ
・・・とはいえ、ユーザ・アプリから見ると「今までのバッチ処理が、なんかすごく高速になりました」というだけの話でしかないのかもしれない。普通の一般人から見れば「いや、なんかそれすごいの？いままでできてなかったの？」ということになる。
まぁ、一般の人が考えている以上に今のITは制約が多いのですよ・・・ま、そんな感じのところに使われるのがAsakusaの将来像かと。別に世の中を変えると、disruptiveだとか、画期的だとか、なんかすげーって仕組みではないでしょう。
ただし、従来の仕組みからみると、その「下回り」はほぼ別物といってよいものであり、従前とはまったく異なるアーキテクチャになっている。結果として、「上物」はそれほどドラスティックに変化はないが、使い方が劇的に変わるということになる。（NTのメンバならわかると思うがANでのシミュレーション利用なんかが好例） その「つなぎ」ってのがAskausaの役割になってくると思う。
個人的に本来の技術のイノベーションというものは、こういった「よくわからないがいつの間にかすごく変わっていた」というものであるべきだとは思っている。僕自身のユーザ企業の経験から言って、そんな画期的な超絶凄いウルトラハイパーなものはいらないから、「普通に普通のことができてほしいかな」と思うわけです。
そんな感じ
客先常駐について
客先常駐は増加傾向に見える。
別に統計資料はないので、どちらかというと体感的なものだけど、ベンダーからユーザーへの常駐は増加している気がする。これはまぁスタイルはいろいろで、完全に委任契約のものから、継続SIを仕事として請負契約の形になっているが作業的には客先にずっといるというスタイルのものをある。ベンダーの人員というよりも、ベンダーの下請け・孫請けが常駐していることが多い。さらに、多くの場合、戦力になっているのは、フロントの一次受けではなくて、下請け・孫請けの部隊だったりする。そんなこともあるので、地方の中小企業の場合は、さすがにフロントのサヤ抜きが、馬鹿馬鹿しいので、直接に契約に切り替えることも多い。
いずれしても、SIという位置づけのものまで含めると、この種の「派遣の一種」のような常駐モードの人員は相当いて、SEから運用・コンサルまでITに関わる分野では、非常に幅広くかつ大きなビジネスになっている。
当然ながら、客先で常駐というのは、働いている方からするといろいろ問題がある。基本的にモチベーションは下がる。少なくとも、個々人としてはある企業で働く覚悟をもって就職というか、入社したわけで、最初から「派遣」全開を想定しているわけではない。派遣で2年や3年、ましては10年近くになるとモチベーションも下がる。まぁ、飽きも来る。いくら長いとはいっても他人の会社であるので、コミュニケーションもなかなか難しい。さらに、長い間客先常駐だと、そもそも自分のキャリアパスをどうするか？という点でもいろいろと前線低気圧で空模様も怪しい。唯一の楽しみとしては、先端系のことをやっているのであれば、そこで技術的なものを得るチャンスがあるぐらいであるが、これはそもそも本末転倒であり、「派遣元」の企業でそういう経験を積んだ上で、現場に出すのが筋である。そんなことも期待できないという、少々自虐的なスタンス有れば、まぁ多少の立つ瀬もある程度だろう。（意外に現実だったりするが）
残念ながら、この「派遣」構造が、きわめて需給にマッチしており、増えることはあっても減る事はない。
「派遣」する側：とにかく簡単に売上を上げることができることが大きい。さらに委任であれば、納品責任もないので、赤字になることもない。人を入れれば入れるほど、売上・利益があがることになる。数字が足りないのであれば、これ以上都合のよい仕組みもない。IT産業の大きなポーションがこの部分を占めている。SI屋から始まって、コンサルまで枚挙に暇はないだろう。しかし、これはとてつもなく自転車操業になる。プロダクト・サービス開発という意味では、手元にR&Dを行える人材がいなくなるので、とてもできない。また、派遣の規模が大きくなればなるほど、一旦、切られたあとの売上の落ち込みをカバーすることが厳しい。
IT企業の利益の源泉が「技術」であれば、派遣ビジネスはそもそも企業の目的の趣旨とはやっていることが違う。技術を売っているわけではなく、要するに「人」を売っていることになってしまう。そして、具合が悪い事に、これがうまく続くとそこからの転換は圧倒的に難しい。ほぼ不可逆に近い。
「派遣」を受ける側：とにかく使い勝手のよい人材をゲットする最短経路である。基本的に日本企業でITを司る部隊は間接部門・バックエンドであり、採用をするとキャリアパスの設定に四苦八苦する。どの会社も間接部門の人員は抱えたくないし、そのコストはできるだけフロントに振向けたいのが実態だろう。したがって、受けてみてスキルセットが違うのであれば「チェンジ」も可能であり、いざとなったら「お帰り頂くことが可能」な派遣は、とくにITに関しては願ったりかなったりだったりする。
あとはそもそもユーザ企業では、ITのスキルを持つ人間を採用・育てることが難しいという側面があり、派遣に頼らざるを得ないということがある。ITのスキルセットを身につけたいという人間は、最初からユーザ企業の一括採用に行くことは少ない。IT専業の企業に行くのが普通の発想だ。つまり、そもそも採用しづらい。中途で採用するにしても、質と数をそろえるのは困難を極めるので、体制含めて「任せざるを得ない」という実情もある。
というように、需要と供給の都合がうまくマッチするので、マーケットとしては固い。鉄板。いわゆる一般職的な派遣であれば、法律の枠があったりして、派遣問題がクローズアップしたりして、いろいろ社会的な問題になるが、ITについては、仲介的な派遣ではなくて、作業の効率上、IT屋の社員を客先におかせてもらって作業をしている、という感じになるし、賞与・昇級も一応、IT企業内部ではあるので、それほど大きな問題にはならない。当面は、増えることはあっても減る事はない。
ただし、働いている人員の擦り切れ感は、ちょっと人間としてどうなんだというレベルまで行っていることが結構ある。実態を見ていると、見てる方まで不健康になるレベル。「結局ユーザにしても、ベンダーにしても、エンジニアのことをモノ扱いしてないか？」と思うのよね。いや、そんなことはない、と言うとは思いますが、どの大きな開発現場にいっても、小さな机＋椅子＋ノートパソコンで、ずらっと人が押し込まれているのが現状で、これなんすか？と聞くと常駐ですよ、と。・・どこの強制収容所だよ、とか思うわけで。
んで、これ確実に疲弊するというか、物理的かつ精神的に摩耗するわけで・・・この現状の改善をSI屋の経営陣やユーザに期待するのはやはり難しい。
まず、別にSI屋の経営陣やユーザが「これがベスト」だとは全然考えていないことがポイント。「できればなんとかしたい、けど、どうにもやりようがない」ってのが、現実。確かに、「数字しかみない」って豪語するどうしようもない経営者もいるが、そういうのはやっぱり少数派で、どうにかして、こういうスタイルから脱却したいっていう経営陣がほとんどだ。しかしなんともできない、というのが現状。身動きがとれない。
さて、この袋小路の客先常駐ビジネスのデッドロックにさらに、しばしばセメントな要素が加わって、もうどうにもこうにもならない状態になることがある。「内製化」である。
まず、断って置くけど、個人的には内製化は進めるべきだと思っている。いろいろ理由はあるのだが、基本線は、SI屋の技術キャップがそのままユーザに転移するのが、現状のSIビジネスの大きな副作用なので、これを取り除くにはユーザが自力で技術要素を取り込めるようにすべきだ、というところである。
この内製化は本来インソースで賄うべきだが、現実には「SIパートナーからの常駐派遣」になっている。SIサイドから見ると委任契約なのでノーリスクだ。ユーザサイドからすると、結局のところ採用が困難かつ面倒なところに簡単にそこそこ優秀な人材が手に入る。願ったりかなったり。開発のイニシアティブをユーザが（実現可能性はおいて）握れるので、ユーザにしてみれば、まさに次世代型ITの投資がやっと主体的にできる、すなわち「先を見たITがウチもスピーディーにできるようになる。」
で、実はこの内製化はご想像の通りいろいろ炎上案件化しつつあるようだ。まず、内製化の炎上案件はめったなことでは表に出ない。ユーザは自己責任でやってるので、啖呵を切る相手もなく、炭火になるまで抱え込むしかない。大規模開発案件の内製化で失敗しようものなら、それこそ責任転嫁できないどころか、代表訴訟ネタだ。なので、表には成功しますた！とやるわけで。ベンダーからすれば「それ見たことか＋どんどん人なら出しますよ、お金はくださいね」的な展開なので静観の構え。
とはいえ、最後は「どーしてくれる」のユーザごり押しになる可能性もあるので、よく見ると、ユーザとベンダーのある種のチキンレースっぽい展開にはなってしまっていて、お互いどんどんレイズしている感じで、現場の人間はいい面の皮だ。内製化は人員の問題ではなくて、「（上から下まで含めた）企業のありかたの問題」だという意識がないので、普通に失敗する。
そんなこんなで、ITゼネコンは、文字通りにゼネコン以上にゼネコン化しつつあるわけで、それも肥大化しつつある。いろいろ厄ネタ満載で、そのまま人工衛星大気圏突入で黒焦げ。
・・・・・
こんなことがいつまで続くのだ、という話だが、やはり2020年〜2025年にひとつの峠がくるだろう、というのが一つの見方。大方の人間はほぼ同じ意見だと思うが、「景気はオリンピックの2020年までは、まぁこんな感じで続いて、その先はちょっとどーなるか読めないけど、いろいろ問題が噴出するだろうな」という感じだと思う。「大体、みんな同じ感じで考えている」というのがポイントで、そういう場合は自己実現的に動くことが多い。
この場合、理屈は簡単でユーザはコスト削減に舵を切る。
大幅・小幅の違いはあるだろうが、「過剰な投資」は普通に整理にかかる。まぁコアだけ残して人減らせ、という話になる。んで、全部撤収はほぼないだろう。それだけユーザの「情報システム部」のアウトソーシング化は歯止めがかからないところまで来てしまっている。したがって全面的に整理という形にはならないが、自社での人員のヘッドカウントはまずは減らせ、または「厳選しろ」という話にまず間違いなくなる。形式上は新規のPrjを一時縮小するとか、そういう形をとるだろう。ヲイヲイまじかよ、という展開になって一人当たりの仕事は、まぁ増える。いろいろまずい。
たぶん、修正をやるのであれば、ここが潮目になる。
とはいえ、その時点ではおそらく軌道修正の「原資」はない。これはSIサイドも、ユーザサイドも、そしてエンジニアサイドも同じだ。言ってみれば、三者三様にピンチではある。ただし、これはたぶん最後の「チャンス」になるだろう。現状の路線はどう逆さに振ってみても変更は不可能で、がっちりデッドロックしている。皮肉なようだが、なんらかの「縮小」または「整理・見直し」が唯一のチャンスになるだろう。ただ、もう一度言うが「原資」はない。もちろん、いろいろ事前に準備していれば、話は別だ。
ユーザ：まじめに「本当に内製化」をするなら、この時点でちゃんといろいろ見直すべき。ただし、ちゃんと根回しとか方針を決めておかないといきなりは全然無理だし、肝心のエンジニアには逃げられる。縮小気味のときこそ、ITが自社の背骨かどうかの試金石になる。そういうスタンスで臨めるように「今から」準備しておくことが肝要だろう。
SI屋：数字が下降気味になったときにどうするかは、その時に考えても遅い。ある程度売り上げが維持できている状態では、無理に勝負に行く必要はないが、弾は込めておいたほうがよい。先が見通せない状態ほど博打は打ちやすい。ただでたらめに撃っても仕方がないので、その時に最小のリソースで手が打てるように、今の時点先行して何かやっておくことが必要だと思う。
エンジニア：さてどうするか？という選択を落ち着いて行う時期になると思う。今の過熱気味の市況で動いたメンツは、やはり「easy-come, easy-go」になる。高コストで仕事がないメンバーと、低コストで地味ながら確実に顧客の心臓に握っているメンバーとどちらを雇用主がとるかは自明だろう。また、現場SEとしても、縮退はいろいろと負荷がかかる。常駐やら固定リプレースSIやらの専業で、特定業務のプロとはいいつつも、実際は潰しがまったく効かないノウハウをもったところで先がないだろう。5-6年はよい。いい経験にもなるし業務知識は血肉になるだろう。ただし10年は居すぎだ。給料も上がらない。
各自、プロとしてワンダーフォーゲル決め込むならばそれはそれでよし。また、これを契機に腰を据えて先を見た組織に移るもよし。いずれにしろ、手持ちのカードが複数あることが前提。ユーザもSI屋もいろいろ整理にかかるだろう。移動しても後腐れはない。
今のSI屋・ユーザの需給の歯車はがっちりかみ合ったまま進む。ただし、徐々に同床異夢が明確になるだろう。金の切れ目が縁の切れ目、それがいつ来るかは、容易に想像できるはずだ。そんな感じ。まぁ今はある意味だれにとっても本質的にはノーチャンスには見える。
SQLServer 2014 “Hekaton”再考
SQLServer2014「Hekaton」
MSの主要DB。論文がでているので、それをベースに自分の理解を書く。当然実装は公開されていないので、合ってるかどうかは知らない。また実際に製品にテストベンチを走らせたわけではないので、あくまで公表された論文ベースでの理解になる。まぁもう普通に使われているDBで、細かい機能云々についてはいろいろ資料がでているはず。そのあたりを見ればいいと思う。論文が公表されて、だいぶいろいろ手がはいっているとは思うので「アーキテクチャの設計」として読んでる。
■論文の構成
基本的に三つの構成になっている。全体の枠組み・Txの処理を詳細に記述したもの・およびその厳密な証明。このうち、全体の枠組みは、Tx処理詳細のあとで書かれているので、若干の不整合がある。これはIndex実装の追加の話なので、多分パフォーマンス向上のためにRange Indexを追加したようだ。トランザクション方式については変更はないように見える
Hekaton: SQL Server’s Memory-Optimized OLTP Engine
https://web.eecs.umich.edu/~mozafari/fall2015/eecs584/papers/hekaton.pdf
High-Performance Concurrency Control Mechanisms for Main-Memory Databases
http://vldb.org/pvldb/vol5/p298_per-akelarson_vldb2012.pdf
Addendum to “High-Performance Concurrency Control Mechanisms for Main-Memory Databases”
http://pages.cs.wisc.edu/~sblanas/proofsketch.pdf
■位置付け
2017年現在は大規模OLTPが開発競争中で、サーバ・アーキテクチャの大幅な変更（メニーコア化・ノードあたりのメモリー量の増大）を受けて様々な方式が検討されている。その中でHekatonはどちらかというと、旧世代の一番最後、というか新世代の一番最初のDB、というような位置づけになっている。この分野は毎年のように新方式・実装提案がされており、パフォーマンスレコードが常に更新される状態で、すでにHekatonはパフォーマンスでは最後尾に位置になってしまっている。最新の方式とはすでに最高で50倍近い差がでている。まぁ仕方がないところではある。
とまれ、商用DBではIn-memory/OCC/MVCC系をちゃんと実装しているので、そもそもどういう仕組みなのかはまとめておいたほういいので、そういう感じ。
個人的なフォーカスポイントと感想
■全体的な感想
よく頑張ってつくったな、とは思う。開発者の苦労がよくわかる。HekatonはSQLServerのDBEngineとして位置づけられており、外側の皮の部分や、一部利用可能な実装はそのままSQLServerを再利用している。これだけ大規模な商用DBだとおいそれと全面フルスクラッチというわけにもいかないので、あれやこれやレゴブロック状態だったと思う。最初からSQLServerがそういう作りを意図していれば、問題はないと思われるが、そんな風には見えない。開発陣は相当な妥協とストレスを押し付けられたのは想像に難くない。そのせいか、論文に時々支離滅裂な文言というか表現も散見されて、およそDBの学術論文とは思えないきわめてファニーな展開がそこかしこに香り漂い、味わい深い出来になっている。違いがわかるネスカフェゴールドブレンド。ぜひ、一読を勧める。（これだけいろいろと面白いDBの論文は過去に経験がない。）
論文を読む限りは「普通に普通のことを普通にやりました！文句ないですね！」という感じの4ドア・セダン・カローラという感じだ。パフォーマンスチューニング用のアーキテクチャ的な仕掛けは特に設定しているようには見えない。ので、普通に遅い。Foedus(OCC)にしろ、Cicada(MVCC)にしろ、パフォーマンスをあげるための仕組みをこれでもかのてんこ盛りで入れているのに比べると、淡泊というか、なにもしてないな、ぐらいには見える。Plain味・バニラ風味。まぁ2-3年前だとこんなもんだろうな、とは思う。逆に言うとここ数年の進歩がすごいということでもある。
トランザクション周りについて
Hekatonは新しいサーバ・アーキテクチャに対応する次世代のIn-memory MVCC/OCC型の商用DBだ。（現時点ではこれに対抗する商用DBはSAP-HANAだろう。本命のOracleはまだ登場していないが、もうそろそろ出てくると思う。）この意味で、どのようなトランザクション・ポリシーを持っているか、重要である。少なくと、商用とOSSでは装備の重さが違う。その意味では重装備だとこんな感じで、このポリシーでもある程度行ける、というのは情報としては重要で、その意味で整理しておきたい。
■ざっくりの構成
SQLServer2014は、従前からのSQLServer部分とエンジン部分のHekatonから構成されている。Hekatonは特にin memory用に特化したエンジンで、専用のtableやindexを持ちtransaction処理を行う。ストプロもサポートしている（Transact-SQL 以下T-SQL）。性能目標は従来からの10-100倍のパフォーマンスに設定されている。
基本方針は、Indexはオン・メモリー前提に設計・最適化し、ロックフリー(IndexとMVCC)が基本で、T-SQLでストプロ実行可能する、また、パーティションニングについてはコア単位でのパーティショニングはしない、大体こんな感じになっている。
■俯瞰的なアーキテクチャ構成
HekatonとSQLServer部分より構成されている
・Hekaton部分は以下三つから構成される
Hekaton storage engine : index+data HA/Recoveryのベース
Hekaton compiler：ストプロ関係
Hekaton runtime system：libその他
・元からあるSQLServer部分には以下の機能要素をもつ
Matadata/Security：Hekaton storageのメタデータ
Query optimization / Query processing :クエリー関連
Storage:永続化
まぁいろいろレゴブロック状態。
■Storage and Indexingについて
storageについては特に特記事項はない。従前の永続化の仕組みが前提で、NVMは視野にいれていない。
二種類のIndexをもつ。
・hash index lock free hash table
・range index Bw-tree ( lock free )
■クエリー周り
いわゆるT-SQLの実行計画についての改良がメイン。基本ステージングコンパイラ。流れは以下
・T-SQL -> Parser + Query Optimizer -> Query Plan
このあたりは普通にコンパイル（型とか名前処理）して、Query Plan作成。ここまでは今までのSQLserverをそのまま利用。
・Query Plan -> MAT
MAT=Mixed Abstract Treeでいったん中間的な表現に落とす。
・MAT + Metadata -> Pure Imperative Tree（PIT）
MATにHekatonのメタデータを追加的に利用して、具体的な実行計画に変換する。これはCへのコード変換のための準備も含むようだ。というかCへの変換用のIRっぽい。以下愚痴がいろいろ。
・CとT-SQLでは型システムとexpression semanticsが違いすぎる
・Date/Time type / fixed precision numeric type（decimalとかそんなんか）とかどうすんだよ
・NULL とかどうすんだよ
・arithmetic expression evaluation errorとかどうすんだよ
なので、PITを導入したようだ。Asakusaとかやってるとこういう話題は普通にあるので、社内では「心を無にして実装する」が基本スタンスだったりする。こういう愚痴を言ってるうちは魂のステージが足りていない。
・PIT -> Cのコードへ変換- > binary
んでバイナリーの生成
・Schema Compilation
テーブル情報のコンパイル。テーブルに対するコールバック関数を生成する。キーとレコートに対するhash関数とcompareの提供。レコードのlog bufferへのserial化を準備する。若干飛ばし気味に見える。
Instead, we collapse an entire query plan into a single function using labels and gotos to implement and connect these interfaces…By keeping all of the generated code in a single function, we avoid costly argument passing between functions and expensive function calls. Although the resulting code is often challenging to read due in part to the large number of goto statements…..ふむ。
■Transaction Management
商用の方は基本Multi-version(MV)になっている。論文では一応Single-versionも試験的に実装してベンチマークしている。MVでは、OCC-validationベースと、PCC-lockベースの両者が混載されている。
・MVCC
定義：a transaction is serializable if we can guarantee that it would see exactly the same data if all its reads were repeated at the end of the transaction
ベースはSIで、RFの維持ができれば、というざっくりした定義。
二つのスタイルを利用している
Optimistic : validationによる
Pessimistic : lockによる
Single versionのlockベース
実装としては3種類試している。
・Invariant
invariantは以下
1.Read stability
コミット時点でvisible versionがまだ見えていること。すなわちTがV1を読む時は、TのTx終了時点までV1はvisibleである。
- V1は他のコミットされたversionでリプレースされない
- これはread lockまたはvalidationで実装可能
- SIをベースに考えていることから推測するとvisible versionはコミット済みのものに限定してると思われる
2.Phantom avoidance
コミット時点でvisible versionに追加がないこと。すなわち、Tが終了するまで、Tでのscanは追加されたversionは返さない
- predicate指定の時にreadした対象が変わっていないこと
- deleteはversionの追加扱い
- これはscanされたindexとtableをロックするか、re-scanして追加がないかどうか確認することで実装可能
ちなみに下位のIsolationレベルは以下の通りで実装可能
- repeatable read -read stabilityの保証でよい
- read committed -単純に最新のコミットされたversionを読むだけ
- snapshot isolation -Txの最初にversionを読めばおしまい
・Timestamps and Version Visibility
1. Logical Read Time (RT)
基本Txの開始時刻。どのversionを読むか、ということの決定基準。IsolationレベルがSIの場合は必ずTxの開始時点になる。
BeginTime/Commit/EndTime
各versionはBegin field (BF) とEnd field (EF) を持っている。
Commit/EndTime でserialization orderを決定する。
2. ステータス
各Txは以下のステータスを持つ
・active Txを開始している。
・preparation コミットの準備。Validation中。
・committed コミット済み
・aborted アボート済み
3. Valid Time
versionのvisibleな期間：begin timeとend timeの範囲
begin time = versionが作られたTxのcommit time。BFに格納される。
end time = overwrite(またはdelete)したversionを作ったTxのcommit time。EFに格納される。
Overwriteされていない場合はinfに設定される。
4. Readsについて
VersionのValid Time spanにRTがヒットした時に、そのversionを読む。
各versionのvalid timeは重ならないので、最大でも一つのversionがアサインされる。
読んだ時点のrtsは打たないので、誰が読んでいるかはわからない。
5. Updatesについて
versionをinstallして、そのTx-IDを当該versionと上書き対象のversionに書き込む
new version の BF にセット。まだ未コミット状態で書く。コミット完了時にcommit timeに書き換える。
old version の EFにセット。 Tx開始のロックの代わりに利用。コミット完了時にcommit timeに書き換える。
したがって、write-writeは早いほうが勝つ。なお、write中のconcurrentはリードは可能。
■OPTIMISTIC TRANSACTIONS
ロックを取らずにvalidationでconsistencyを保証する。
◆Transaction Phaseの詳細
0. Txの開始
TimeStamp (TS)の取得
1. 読むversionを決める
indexからversionデータを取りにいく。
1-1 versionが一番最初のケース：
先行するversionがないのでBFはTx-ID
Tx-IDが自分自身の場合はversionのステータスはactiveでEFはinf
Tx-IDが自分自身でない場合は、他のTxが書いている、かつ
その「他のTx」のステータスがpreparationの場合は、コミット準備に入っているので、自分は投機的に読みに行く。この場合は、BFにはそのversionを書いているTxのTSが書き込まれるはずなので、その書き込まれるTSと自分のRTを比較してvisibleかどうかテストする。
その「他のTx」のステータスがcommittedの場合は、コミットはされたが、まだBFにまだTSが書き込まれていない。なので、そのTSと自分のRTを比較してvisibleかどうかテストする。
その「他のTx」のステータスがabortの場合は無視する。
1-2 versionのBFとEFにTSがセットされてる場合
自分のRTが収まる範囲のversionを見つける
1-3 versionのBFにTSがセットされていて、BF＜RTであって、かつ
1-3-1 BF(TS)-EF(inf)の場合
普通に最新のversionを読んでいるので、それを読む
1-3-2 BF(TS)-EF(Tx-ID)の場合
要するに上書きが始まっているような場合、でかつ
後続のTx（Tx-IDをもつ）のステータスが、activeな場合
後続のTxのversionは読めないので、普通に前のversionを読む。
後続のTx（Tx-IDをもつ）のステータスが、preparationな場合
後続TxのTSがわかるので、そのTSと自分のRTを比較する。
RT < TSならば、前のversionのEFはTSで、すなわち、BF < RT < EF = TSなので、前のversionを読む
TS < RTならば、もし、次のversionがコミットされた場合は、前のversionはそもそもvisibleではなくなる。しかし、abortの場合は前のversionが読める。なので、次のversionが確定するまで、当該Tx (自分自身)をブロックすることがよいが、できるだけnon-blockingにしたいので、投機的に前のversionを無視し(speculatively ignore)、次のversionに当該Tx (自分自身)がcommit dependencyを持つようにする。
後続のTx（Tx-IDをもつ）のステータスが、committedな場合
単にTSの書き込みが遅れているだけなので、普通にBF＜EF=TS＜infで、どこにRTが落ちるかテストして、visible versionを確定する。
後続のTx（Tx-IDをもつ）のステータスが、abortedな場合
自分がEFを読んだ後で、全然別の他のTxが前のversionを更新するかもしれない。この場合は他のTxは自分がEFを読んだあとで、EFを更新してかつactiveでないといけない。この「他のTx」のend timestampは自分がEFを読んだあとになるので、RTよりも後になる。よって、仮に他のTxが更新するとしても、自分が読むversionは前のものになるので、問題にならない
2. 更新Txの場合
更新できるversionはEFがinfかまたは、Tx-IDの場合は、そのステータスがabortedである場合のみ。w-w conflictをさけるためにfirst-writer-win ルールにしている。書きに行く時にEFに自分のTx-IDを書き込む。
作り出した新しいversionのBFに自分のTx-IDをセット
前のversionまた削除versionのEFに自分のTx-IDをセット
コミットする場合はend TSを取得し、ステータスをPreparationに変更
3. コミット可能かどうか判断する
Validation and Dependencies
コミット時点で読み込んだversionが更新されていないか、そのversionがvisibleかどうか確認し、phantomが発生していないかもう一度indexスキャンをしてverifyする。
validationはまずTxのend-timestampを取得する。このend-timestmapでserialization orderを決定する。validationを行うために各Txはread set(読んだversionへのpointerのリスト)と再スキャンに必要な情報をもつscan setを持つ。このvalidationはコストがかかると思われるが実際はL1/L2キャッシュに乗っているので、そうでもない。（と論文では言っているが実際はabortが頻発すると乗らなくなって極端に性能が落ちると思う）
validation phaseにあるTxで作られた（または削除された）versionを読む場合は、そのTxに対するcommit dependencyをとる。よってそのTxがcommitされるまでcommitされないし、そのTxがabortされた場合はabortする。
commit dependencyを取る場合は、dependしてるTxに通知し、自身のdependency countを増やす。依存先がcommitしたら、dependency countを減らす。依存先がロールバックしたら自身もロールバックする。基本、commit dependencyがクリアされるまでウェイトする。またclientにも通知されない。
4. コミット処理
コミット可能なら新しいversionと削除versionの情報をredo logにして永続化層に書き出し。その後にステータスをcommittedに変更。各Tx-IDをend TSに変更（前のversionのEFと新しいversionのBF）する。
なお、loggingはredoログのみ。SQLServer tx-logに格納
5. abortならば、ステータスをabortedに変更
abortの場合はBFとEFのそれぞれをinfにセットして読めなくしてGCする。
6. Tx終了
古いversionをGC。visibleでないversionはGC対象となる。
◆Checkpoint
・二種類のデータで構成されている。
インサートされたversion情報(data stream)と、それに関連した情報や削除されたversion情報についての情報(delta stream) 。それぞれSQLServerのシーケンシャルファイルに格納される。
なお、index操作はlogされない。復旧時に再構築。
・transaction loggingはWALではなくSILO方式で、dirty dataは書かずにgroup commitを利用してredo logのみを保持する。Logの処理は並列処理を想定して作られているが、実際はSQLServerがsingle log streamのみしかもっていないので、ちょっとアレだが、まぁ今のところは効率が良いので十分だ、と論文には書いている。が、そんなわけないだろう。
・リカバリータイムの短縮のために以下の二つ手法を利用
Continuous checkpointing
処理がピーキーにならないようにしている
Streaming I/O
RandomI/Oを減らしてパフォーマンスを上げている
・Checkpoint Filesについて
data stream (data file)
特定期間でinsertされたversion情報を持つ。append onlyで書いていてクローズしたらリードオンリーになる。リカバリー時点でversion情報をリロードしてindexを張りなおす。この時delta fileでフィルターする。
delta stream (delta file)
data fileとone for oneでdeleteされたversionの情報をもつ。
dataとdeltaでペアで持つことでリカバリーの並列処理ができる。ので効率がよいと言っているがそうなのかとは思う。別に一緒に書いても構わない気もする。
■PESSIMISTIC TRANSACTIONS
基本的にリードロックをとる。ロックの仕組みは以下
1.Lock
Lock Typesは二種類。
Record Lock
更新・削除は最新のversionのみが対象になるので、最新versionのみにリードロックをとる。
EFにロック領域をもつ。64ビット。MVの場合はTSかTx-IDになるがこれを利用する。
ContentType(1bit)をとって0の時はTS(63bit)。1の場合は以下の構成
・NoMoreReadLocks(1bit) lockがこれ以上許容できないよflag （また、リードロックが全部はずれて上書きのwriteがコミットに行くときに後からリードロックが来ないようにセットするときにも使う）
・ReadLockCount(8bit) number of read locks。よって255並列
・WriteLock(54bit) このversionへのwrite lockをもっているTx-IDまたはinf
Bucket Lock (Range Lock)
Phantom用のロックでBucketLockSetで管理する。
BucketLockSetは以下で構成
・ロック対象のhash backetへのポインタ
・LockCount このbucketに対するロック数のカウンタ
・LockList このbucketに対するロックを持つTx-IDのリスト
2. Eager Updates, Wait-For Dependencies
通常はリードロックに対するwriteはブロックされるが、これではスレッド・スイッチが発生してコストが高い。
なので、対象versionへのリードロックがリリースされるまでwriteのコミットを遅延させる。
先にwriteロックをとって、あとからリードロックがかかっても同じ。Bucketロックも同じ扱い。（wait-for dependency）
Dependencyのトラッキングの仕組みは以下
各TxObjがもつdependencyのデータ
・WaitForCounter 自分が待っている（incoming）Txの数
・NoMoreWaitFor もうこれ以上待てない数になったらフラグる
・WaitingTxnList 自身のコミットが待たれている (outgoing) TxのID
制御は簡単で、リードに行ったら普通にリードロックをとる。リードロックがかかっているversionを更新する場合は、writeロックをとってwait-for dependencyに入る。WaitForCounterがゼロになったらコミット。また、writeロックがかかっていても後追いでリードロック可能。write側はリードが済むまでコミットできない。
3. Dead lock
普通に起きるので、wait-forグラフをつくって検出する。個人的にはあまり役に立つ気がしないので、普通にtime-outでいい気もするが、wait-for dependencyの情報があるので、それを利用しているという感じか。
4. OPTIMISSTICとの違いは以下
・リード時点でロックをとる
・visibilityからのcommit dependencyは同じ
・コミット可能かどうかの判断はvalidationによるのではなく、単純にロックリリースがされているかどうかによる。
■Serializationの比較。
まずSerializationの証明について
Addendum to “High-Performance Concurrency Control Mechanisms for Main-Memory Databases”
http://pages.cs.wisc.edu/~sblanas/proofsketch.pdf
・Pessimistic
MV2PLであるという記述になっている。
The multi-version pessimistic (locking) scheme is in fact a MV2PL scheduler
そして、Tx本を引用しているが、間違っている。まずTx本の方はfinal stepでの処理を導入しているが、Hekatonの方は単純なロック処理になっている。ここは違う。ただし、Tx本でのfinal stepがwrite可能性の判断なので、意味は同じで手法が違うだけ。むしろ2PLのわかりやすさ、という意味ではHekatonの方式の方が圧倒的にわかりやすい。一番の違いは、Tx本の方はw-wは単純な待ちで終わるが、Hekatonはabortになる。同じではない。
・Optimistic
The multi-version optimistic scheduler behaves like a MVTO scheduler, with the changes described below
とあり、一応MVTOライクと言っていて違いは以下ということになっている。
Property 1: Timestamps are assigned in a monotonically increasing order, and each transaction has a unique begin and end timestamp, such that TxBegin < TxEnd.
Property 2: A given version is valid for the interval specified by the begin and end timestamps. There is a total order << of versions for a given datum, as determined by the timestamp order of the non-overlapping version validity intervals.
1と2でTSの保証と全順序。妥当だと思う。
Property 3: The transaction Tx reads the latest committed version as of TxRead (where TxBegin <= TxRead < TxEnd) and validates (that is, repeats) the read of the latest committed version as of TxEnd. The transaction fails if the two reads return different versions.
リードしたものの前に別versionが入ると失敗。
Property 4: Updates or deletes to a version V first check the visibility of V. Checking the visibility of V is equivalent to reading V. Therefore, a write is always preceded by a read:
if transaction Tx writes Vnew, then transaction Tx has first read Vold, where Vold << Vnew. Moreover, there exists no version V such that Vold << V << Vnew, otherwise Tx would have never committed: it would have failed during the Active phase when changing the end timestamp of Vold.
RMWしかwriteさせない。よって、そのリードは前述のリード条件と同じ、ということ。
Property 5: The transaction Tx logically writes at TxEnd, because the version is invisible to other transactions until TxEnd
concurrent writeのversionのvisibilityの定義
証明はほぼMVTOと同じ証明手法をそのまま利用している。Serializableであることには問題ない。
ただし、blind writeを認めていないため、MVTOよりもserializable空間は狭い。
■一般的なMVCC/CSRと比較してみる。
単純にconflictによる比較をする。（これは論文にはない）
MVCC（MCSR）
w-w not conflict : can commute
w-r conflict read from relation : cannot commute
r-w conflict only if w committed before r otherwise can commute
CSR
w-w conflict
w-r conflict
r-w conflict
HekatonOCC
w-w later w is aborted thus restrictive than CSR
e.g. w1(x1)w2(x2)c1c2 fails though in CSR committable
w-r conflict : read is determined as latest version or on the fly version and cannot commute
r-w conflict only if w is committed before r because it would updates version read by r
e.g. r1(x0)w2(x2) conflict in CSR and cannot commute but possible in HekatonOCC
w2(x2)r1(x0) に交換しても先にTx1がコミットしてれば成立するので、conflictではない
w-w more restrictive than CSR
r-w more relax than CSR
よってHekaton OCCはCSRと直交する。
HekatonPCC（Pessimistic）
w-w conflict : write lock but aborted
w-r conflict: read is determined as latest version or on the fly version and cannot commute
r-w conflict only if commited before r cause it would updates version read by r
r1(x0)w2(x2) conflict in CSR but possible in Hekaton w2(x2)r1(x0) r-read lock and write always has wait-dependency for read and delay thus commutable
w-w more restrictive than CSR
r-w more relax than CSR
よってHekaton PCCはCSRと直交
基本的にHekatonではOCCもPCCも同じ空間になっている。ただし、CSRよりも狭い部分もあれば、広い部分もあり、全体としてはMCSRには及ばない。通常のMVTOの空間にも及ばない。そもそもRMWしか認めてない段階で、concurrentな複数のsingle writeすらabortすることになる。ので、MVのコストを払った分のメリットをとるのは厳しい。
version linkにTx-IDを利用してwriteコンフリクトの蓋をするという段階でどうやってもconcurrent writeはabortは増える。これは小手先でどうにかなる問題ではなく、アーキテクチャ限界になる。読んでるversionの更新を許さないために、結果として不要なwriteのabortを発生させることになる。最近のメニーコア・大容量メモリーは容易にスループットが上がるため、abortのコストが相当高くなっている。ちょっとabortのコストを甘く見ていたかもしれない。本来MVCCのメリットは広いserialization空間によるabortの低減である。そのメリットがとれていない。その意味ではMVCCと言い切るには、個人的に無理があると思う。ただのMVだろう。これではsingle versionのOCCにはまったく勝てない気がする。まぁ、なんかパッチをあてて、write delayさせて・・・ということは緊急回避でできなくはないが・・
とはいえ、先人的な仕事としては非常に意味のある実装だし、論文だと思う。既存資産を引っ張った状態で、商用のin-memory MVCCに挑戦という意味では、ここまで詰めるだけでも相当なコストになるはず。そういう評価になると思う。
クラウドのためのクラウド〜VMware Cloud on AWSの意味
記事とか詳細とかはこっち
http://www.atmarkit.co.jp/ait/articles/1708/28/news097.html
https://cloud.vmware.com/vmc-aws
http://www.publickey1.jp/blog/17/vmwarevcloud_air.html
まぁ概ねこんな感じ
単純に見れば、AWS上でVMWareが使えるので、VMで動いているシステムがそのままAWSで使えるようになりました。便利ですね。はい、おしまいの話ではある。が、それは二重の意味で「表層的」な見方だ。そもそもVMWareがクラウドから撤退し、AWSの軍門に降ったというエポックメイキングなものとして見るべきだと思う。
・ハード調達の争いの決着
結局のところ、DCを含めたハードウェアの調達という点で、競争に決着がつきつつあるということかと。VMWareの規模をもってしてもAWSの調達コストを達成することは困難であったということが明確になった。もともとサーバの「生産台数」という意味ではGoogle・AWSが覇を競っていたわけで、さらにその他大勢との差が決定的になった証左だ。そもそも「サーバ」と言っても、Google・AWSの「サーバ」を市場に出ているサーバと同義で扱ってよいか、という問題もあるが、要は「計算リソースの調達」コストが段違いで差がついてしまっている、ということだ。まぁ桁が違う、というのが現状でしょう。
現在のところ、ムーアの法則の限界はむしろサーバ自体の高集約化、すなわちサーバアーキテクチャの変更の流れを加速させつつある。サーバの耐用年数はさらに短くなってきている。これも調達競争の「強者有利」の状況を作り出している背景にあると思う。償却がどんどん進むのであれば、数量が出せるので、バイイング・パワーはより強く働く。
今回のVMWareの白旗は、クラウド時代の一つのメルクマールになると思う。今後はさらに加速して割と一方的な展開に進むような気がする。AWS/GoogleにどれだけMSやOracleが迫れるか、というレースになる。そこそこの規模があっても自社インフラでクラウドサービスというのは競争力がなくなっていく。
こうなってくると今後は、サーバの分化がより激しく進む。すなわちクラウド用サーバとオンプレミス用サーバはもはや、ほぼ別物として見る方が正しいのではないか。クラウド用サーバはよりDCの「部品」としての性格が強くなるだろうし、オンプレ用として利用することは無理だろう。その意味ではコーナケース的な極端なワークロードを実行した場合、今後はクラウドとオンプレでは挙動が変わるということは想定すべきかもしれない。また、今後のサーバの生産でのクラウド用のものシェアがどんどん高くなれば、むしろオンプレミス用のサーバは、言ってみれば一種の特注の「専用サーバ」として、「逆ガラパゴズ」状態になる可能性もある。そんなこんなでいろいろ影響が徐々に出てくるだろう。
・焦点としては二つ。一つはN/W
クラウドの本質はネットワークだ。これについては異論は少ないと思う。クラウドの硬質な部分はここに集約される。DC内部・DC間のネットワークをどのように構築・運用するかがクラウドの背骨だろう。ここがこんがらがったり、SDNのようなメンヘラな話で突っ走ったりすると、トラブルが起きたときになにが起こったのか理解できないということになる。
この部分は、特許を含めてIP戦争の主戦場だったり、その一方で、人間のつながりでは一種のマフィアチックな「村社会」の様相もあり、簡単に資本と論理で切り込むことができるところではない。さらにグローバルな意味であれば、国家レベルの介入は実際普通にある。Googleがこのあたりで文字通り“エキゾチック”な動きをしているのは有名な話だ。クラウドのためのクラウドということの意味は、ネットワークでどこまで主導権をとれるか？ということの影絵でもある。AWSのその勢力図での位置づけも明確になってきたということだろう。
・もう一つは「DCのあり方」
AWSがひとつステージを上げたという意味では、今回ポイントになるのは、間違いなくDCの調達・運用・保守の「パッケージ化」だろう。AWSは「クラウドのためのクラウド」という、より低レイヤーでありながら、そのレベルをパッケージ化してVMWare等に提供している「B2Bのクラウドベンダー」だと思う。これは別にVMWareだけに提供を限定する必要はなく、自社に最適なミドルを構築運用できる能力、すなわち別段AWSのサービスを利用する必要もないレベルの構築能力のあるユーザにもそのまま提供しているとみるのが筋だろう。
「ハードの調達」の意味がやはり変わってきているのだろうな、と思う。どこまでが運用か、どこまではサービスか、というのは議論の分かれ目にはなるが、DCレベルまでスケールした、できるだけベアメタルなクラスターとNWとその保守・監視を合わせた意味での「ハードの調達のパッケージング」というスタイルが登場しつつあるのだろう。
ユーザから見れば「データや処理」がビジネスの肝要であり、ハードは極論すれば安ければ安いほどよい。またAWSにして見れば、実力のあるユーザに対してサービスレイヤーで喧嘩する必要はなく、ハードレイヤー以下で実をとれれば十分win-winの関係は構築できる。勿論、AWSからは低レイヤーのログを見ていれば、上で何をやっているのかは想像はつくだろう。AWSとしてはサービスをパクる気は満々だし、ユーザから見ればベアメタル的な利用はロックインの度合いが低いのでいつでも鞍替えできる状態だ。その意味ではwin-winとは言っても、お互いにいつでも背中を刺せる関係ではあると思う。というか刺す気満々な感じかな〜とも思う。
・専用クラウドとユーザのあり方の変化
もちろん、AWSの戦略としては、当面はVMwareのような「あすなろクラウド」の敗残兵の回収と、ミドル以上は自分でやるからいいよでAWSから逃げ出した一部のパワーユーザへの妥協案の提示であることは明々白々だ。
ただ、俯瞰で逆さまに見れば、クラウドのためのクラウドというビジネスが登場しつつあるということは、「DC調達を含めて、大量の良質の安いマテリアルを提供されて、それを調理できる”強い”ユーザ」の登場をも予感させる。
こういった自力でミドルまで含めて自社最適なプラットフォームを構築する、これを流行の内製化とみるか、はたまたDevOpsのひとつのスタイルとみるか、または「企業のソフトウェア化」とみるかは見方の問題でしかないが、こういった企業がどんどん登場してくるだろう。今後のAWSのSaaS/PaaSのライバルはこういった企業だろう。ひと昔まえ、パッケージ製品の競合はユーザ企業の情報システム部だ、という競合関係があったが、この相似形がそのまま現れる。
こう言った強い企業、・・・個人的には「強い」企業という言い方が一番しっくりくる。（例えばアルパインクライマーの実力の表現では、「技術ある」とか「スタミナがある」とか「足が速い」とかそういう個々の要素ではなく、シンプルに「強い」という言い方がよくされる。全般的に山に負けないというか、死ににくいというか、タフというか、単純な技術的な要素に還元されない「強さ」をもつ人をいう。そんな感じの企業かな）については、どうしてもIT屋的には還元主義的に評価することが多いが、そうではなくて、総合的に強いという俯瞰的な見方で観察したほうが良い。そういう企業が頭角を現してくるような気がする。
ITはやはり道具のひとつでしかない。ただ、その道具を単に使うのではなく、無意識のうちに極端な形まで使いこなすことができ、かつ場合によってはITを利用しないということすら功利的に判断できる、そういった企業、「包丁をもったら、全てが切れるものに見える」というシンドロームにかかるのではなく、「必要であれば、自社に合う包丁をつくることも辞さない」そういう柔軟な企業が、言って見れば「クラウドのためのクラウド」と共時的に登場し、「Private Dedicated Cloud」を使いこなすだろう。
・3層のクラウド
ユーザ側ともかく、ベンダー側から見るとクラウド・アーキテクチャのあり方は多層的になっていく。ユーザ・アプリケーション、従来型のクラウド、クラウドのためのインフラクラウドのような3層構造を想定していく必要がある。率直に言ってやりにくい、というのが実態にはなる。特にサポートという観点では絶望的に情報が取れなくなるだろう。SIという意味だと、一番上だけ見るような役回りだとトラブル時には厳しいだろう。
いわゆるクラウドインテグレーションという位置づけも変わる。Private Dedicated Cloudを扱う、ということであれば、必要な人材は正統派的な「下位レイヤーまでちゃんとわかるSE」ということになる。単純にAWSのAPIの使い方・ノウハウありますよ、という人材は、表面的なAWSのみで問題ない、というユーザ企業に対してはアピールポイントになるが、本気で「B2Bクラウド」を使おうとする強い企業には必要ない。結局、強い企業が必要する人材・サービスは、基礎のできる人間/組織になるという、ある意味当然の結果になる。
クラウドインフラの提供者という意味ではメガクラウド系はすべてそのチャンスがある。筆頭Google・Azureだろう。現時点では考えにくいが、facebookにも可能性はある。それぞれの色がでるクラウドインフラの提供は「新しいスタイルのクラウド」を生み出すことにもなる。Googleなんかはまた面白いだろう。WMとの提携がカウンターカルチャー的な衝突を越えて、なんか変なものが出てくればそれはそれで面白い。またOracleがどういう立ち位置で臨むのか。この近年のDBルネッサンスの中で進境著しいSAPがどういうスタンスをとるのか。いろいろと興味深い。そう言った意味で、今回のVMWareのAWS稼働は意味がおおきい。大きな地殻変動が一部表に出たと見るべき案件だろう。
・それでAWSの弱点はないのか？
最後にどうでもよい話題をｗ。ここまでAWSが支配的になってくると弱点がないように見えるが、個人的には（なんでもそうだが）思わぬところが死角になると思う。例えば、本体のAmazon.com。先日WFを買収したのは発表の通り。これはどう見てもCCがほしいだけで店舗とか興味ない気がする（あとはPBか。でも今更感しかないが）。んで、どうみてもこの背景はFreshの苦戦に見える。.Comの物流基本戦略はやはりDCなんで、チルドのTCとか今からXDつくるとかノウハウ・コスト的に無理筋だったのではと思う。チルドや生鮮等の類いはスケールメリットが裏目に出る。Amazonがその領域に手を出し始めて、苦戦しつつあるようにも見える。勿論、AWSとは何の関係もないが、そういうところからおかしくなるのは巨大企業ではよくある話ではある。(まぁ逆に言えばAWSそれ自体には死角はないように見える）
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を考えるとちょっと面倒。なのでここでは目をつむる。
