アンデルセン：高木誠一さん追悼
本来、僕がどうこう書くものではないし、しかるべき人がしかるべき何かのコメントを書くべきだと思う。とはいえ、時代的なものも含めて、後につながる人が「発掘」できるようにはしておきたい。追悼文を書く。これはとある事情で、たまたまこういうタイミングだったいうこともあるので書く。
アンデルセンの高木誠一さんが亡くなられた。昨年のことだ。ちょうど一年たつ。
アンデルセンというのは、インストアベーカリーの最大手であり、FC（リトルマーメード）も展開している。一般の人もお世話になっている人もいると思うが、要するにパン屋さんだ。高木誠一さんはその創業者に連なる方で、亡くなられるまでアンデルセンの方向性に関する最終的な責任者でおられた。日本のパン業界（というかベーカリー）においては、ものすごくインパクトを与えた人であることは間違いない。
アンデルセンさん（以下敬称とか適当）は、僕個人の関わりで言えば、前々職・前職・現職ですべてで取引先・得意先だった。もともとは自分の父のつながりの方が深いが、自分も高木さんには折り触れてお話を頂いたり、逆に現状のITの話などもさせていただいた。アンデルセンさんの原価計算やEDIは僕らのソフトウェアを採用していただいている。
ということで、アンデルセン社員の方々とはかなりの長い付き合いで、折りに触れていろいろな方といろいろな話ができた。とはいえ、あくまで一部の方であり、これから書くことがすべてに当たるものではないと思うし、あくまで僕の見たものでしかないことは留保させてもらう。その上で高木さんがなしたと、僕が思うところを記し、追悼としたい。僕個人は別段ベーカリーの人間でもないし、それこそ日本（というか世界（これは別にアナロジーでもなんでもない））のベーカリーについて、高木さんが残した功績は、その業界の方が記録すべきであると思う。
・高木さんは、会社に「文化」というものちゃんと落とし込めた希有の経営者だと思う。
もちろん、ベーカリー関係者であれば、留学制度の話、文化研究所の話や、農園や、そもそもデンマークとの国交レベルでの交流の話をはじめ、企業活動の枠を超えた、アンデルセンさんの、ベーカリーというものに対する基本的な在り方について、知らない人はいないと思う。これはもう一種の企業文化であることは誰しもが認めるところだと思う。
ここで僕が言いたいことは「それ」ではない。
通常、この手の「直接的な企業のキャッシュフローに加算されない」企業としての取り組みは、たいていの場合は“オーナーの「趣味」の延長線であり、俺たちの知ったことではない。道楽だろ”という意見がどの会社でも通奏低音で存在するのが常だ。その意義については「確かに意義は認めるが、俺たちの給料にどう関係するのか？」ということになる。また、無責任な「俺は従業員の味方だぜ」役員とか副社長あたりが、そういう支出は会社にとって意味があるのか？的な疑義を適当に出したりして、最後は代表訴訟のリスクもあります的な話まで持ちだしたりする。まぁ要するに非常に維持がしづらい。にもかかわらず、あそこまでのレベルまで「パンというものに対する文化的なスタンス」を企業活動として取り入れたのは、尋常ではない。
それはそれですごいが、本当にすごいのはそこではない。
・まずもって企業文化というものは大きく二つの形になる。見えるものと見えないものだ。
見えるものは、明確な制度的なもので、社訓や新人合宿、教育制度や留学制度、それこそ宣伝広告のスタンスや、「文化事業」への協賛金までのものであり、とにかくわかりやすい。アンデルセンさんの前述のデンマークとの国交レベルの交流など、そういうものはこのカテゴリーになり、まぁこの手の話は、前述のとおり「従業員にとって意味があるのか」問題になったりいろいろある。他のたいていの企業の場合は「企業経営者同士のゴルフコンペで話題にしたい」的な発想がメインなので、普通は仏作って魂入れずになる。とはいえ、そういうものがないと「ただの集金マシーンとしての会社」になるので、ないとまずいよね的な話は当然あるのは事実だ。なので、いろいろバランスの話になる。これはこれでいろいろあると思うのでいろいろ議論してもらえばいい。
で、もう一つは見えないものだ。
普通、日常会話で、「あのやり方があの会社の企業文化だよ」っていったときは普通はこれを指す。一種のエートスだ。
以降は「企業文化」という言葉は後者を指す。んで・・・
僕は努めて会社は法技術的なものだと思っている。金を集めて分配する機能を保持する「器」だ。形式上日本企業は株主のものということになっているが、株主が取締役や経営者ではない立場でオーナーとして会社に影響力を強く及ぼすということは現実的にはない。むしろそういうスタンスは所有と経営の分離とかなんとかで、あまりよい評判にもならないし、まぁそういうことだ。よって、会社の所有は株主のもの、というのはあくまで立て付けでしかなく、会社の実効支配は経営者と従業員による。または、経営者と従業員の都合、のための仕組みでしかないともいえる。
僕個人は、企業が「経営者と従業員の都合」のための仕組みという立てつけにおいて、「企業文化」というものは基本的には評価しない。できればそのようなものはない方がよいと思っている。理由は簡単で「企業文化」が“経営者と従業員のほどよい関係の維持”にとって極めて有害だからだ。
見えない企業文化は、大抵の場合、部課長あたりが良く言う「ウチのやり方は」的なものになったり、また、校長先生のお話的な役員の訓示あたりによく発露する。前者はまぁ大体その個人の考えだし、後者は現場から見ると局所的か、または高度感がありすぎて現実感がない。なお、最近トレンドの忖度なんかもこれに入る。
基本的に「企業文化」は組織防衛、あえて言うが過剰防衛、の一つの形であり、個々人にとってなんらかのメリットがあることは極めてマレであるどころか、大抵の場合は有害になる。とくに個々の家庭（人間としての最小単位）に対する干渉は過剰を越えて、結果、現状の日本においては社会基盤の存続自体に悪影響を及ぼすレベルになっていると思う。強制飲み会は序の口で、残業の話題やら、パワハラや果ては有給の取得やら勤務態度や、下手すると「普段の歩き方」まで来る。
ただし、「器の維持メンテ」という意味では有用で、その意味では「経営者と従業員の都合」というものが企業ではなく利害関係者の要請というものであれば、それなりの意味は持つので、結果的に有効なものではあると言えるが、所詮そのレベルの話でしかない。経営者-従業員間、経営陣の内部、従業員の内部間での自己都合のバーゲニングの材料になっているだけだ。それはそれで大事だという意見もわかるが、皮相的に言うならともかく、真顔で言われても困る。
この手の見えない企業文化はたいていの場合は、トップ/経営層/オーナーの「個人の恩讐」が組織にべったり貼り付いているものが多い。形式的にはいろいろ理屈はついてくるが、最終的にはそこに行きつく。これは往々にして一種の「呪い」になっている。ただし例外はある。
そして、その稀有な例外はアンデルセンさんだと思うし、高木さんの残したものだと思う。
端的に言うと。
「とにかく従業員・経営陣含めて「パンが好き」なのだ」
いや、もちろんそれは普通だろうという意見もあるとは思うが、フロントはともかく、バックエンドまでみんなそうなのだ。という、なんというか身も蓋もないが、そういうカルチャーが浸透している。ほぼ例外がない。それもちょっとわりと尋常ではない感じ。
これが、ではなにか企業のキャッシュフローに役に立つか？という意味ではたぶんなんの役にも立たないｗ。いやもちろんR&Dが盛んになるとか、現場の工夫が出てくるとか、まぁそういうメリットはあると思うけど、それはあんまり関係ないと思う。
ただただ「とにかく従業員・経営陣含めて「パンが好き」」なんですよ。ある意味無条件に肯定的。
今のトレンドは「企業文化」を“前向き”にして、なにか個々人・会社に意味があるものにするというのが、大絶賛でノウハウ本やネットですぐに話題になる。要するにこの手の話は、この資本主義というかグローバリズム＋新自由主義最強伝説の現在では、ほぼ功利的な位置付けでしか語られない。
某車屋の「カイゼン」とか最たるもので、アレはまぁ明示な制度的なものではなくて、目に見えないところに意味がある。そういう「企業文化」を持つところは「強い」会社とされているし、割と絶賛されて、目指すところも多い。ま、前述のとおり僕は個人的にはまったく評価しない。あんなものイラン。
本来は”文化的なもの”というものの解釈には功利的なものとは別の位置付けがあったはずだ。現在はまったくそうではない。
企業活動において、特にカリスマチックなやり方以外で「何か新しいもの」を考えていく、というためには、「意図的に効率性を追い求める“以外”の方法で、かつ“無条件で何かを肯定できる”企業文化をもっていること」が必要な気がする。現在の日本企業は効率性もままならない上に、肯定的な企業文化ではなく、制約的・干渉的な企業文化が主流だと思う。結果、日本の企業活動は、とくに国内に関しては、ほぼ絶望的に「未来」なくなりつつある。
アンデルセンさんでは「無条件で何かを肯定できる力」がある。
これを高木さんが意図した結果なのか、意図せざるものとしての結果なのかは、ついぞ聞けるチャンスはなくなってしまった。そして、この文化が今後どう生かされていくのか、もよくわからない。
ただ、こういう企業文化を残したというのは、記録されてよいと個人的には思うので、書いておく。
とかく「肯定的なもの」を残すことが難しい時代だと思う。
それができた稀有な経営者が高木誠一さんだった。
ということを記して、ご冥福をお祈りしたい。
書いててとりとめもなくなってアレなんだけど、そう思ったのでそう書いた。
本当にいろいろありがとうございました。
追伸：パン屋みんなそーじゃないのか？という話もあるが、（これはパン屋が（やればわかるが）かなりの重労働で結果、相当好きなやつしか居つけない説もある）現実に某最大手クラスのパン屋は別に全員がパンが好きな訳ではない（少なくとも僕の観測範囲ではニュートラルという人が多かった）ので、パン屋さん固有の話ではない。
AsakusaとOLTP（RDB）とバッチ処理
Asakusa Advend Calnderの最終として
現状
2018/12月の現在の自分のタスクは、DBのMVCCでのTX制御の理論・アルゴリズムの設計になっている。要するにDBを作りましょうということで、そのコア部分をどうにかしなさい、ということになっている。それで、その前提として、今回のDB-Prjでの最大の眼目の一つを「Writeの強いRDB（OLTP）」ということにしている。
現在のRDBはそもそも原理的かつそのツールとしての特性上WriteというよりもReadにパフォーマンスが振られている。結果として、一般に、書き込みヘビーの業務系大型バッチ処理がRDBでまぁほぼ全敗になる。これは常識のまま、そろそろ30年くらいになるし、この辺が改善する見込みはほぼない。ということで、大規模（といってもさすがに最近のトレンドの規模感からはそう簡単には大規模とは言いがたいが）で複雑な一貫性を担保する書き込み、という意味では、まぁあまりよいアイデアはない。
一方、自分らの飯のタネの一つは、複雑な業務系のバッチ処理の分散高速化で、これは基本的にデータはRDBにあるのが普通だ。それをクラスター/またはメニーコア＋大容量メモリーサーバに展開しつつ、分散処理で高速に処理して戻します、というのが基本戦術だ。現状のAsakusaはこういう用途で使う。
当たり前だが、RDBから抜く時間・戻す時間は無駄だし、バッチ処理は可能であればDB上で実行し、かつオンライン処理を止めずにバッチも動かしたい、というのが普通の発想だ。要するにDB上で複雑な結合処理をしながらドカドカ書き込めて、かつ普通にクエリーもストレスなく動いてほしいは、これはまぁ、別に特別でもなんでもない要請だ。普通に見れば「今時そんなこともできないのか？」ということになる。いいわけとしては「すべての用途に秀でた技術はありません」というのが、ありがちな言い訳になる。
で、そうも言ってられないので、いろいろやってみるか、という話になっていて、それで上記の通り、まずは「Writeの強いRDB（OLTP）」を、いくら待っても出てくるどころか、最近ではむしろDBの選択の余地がどんどん減っている状況なので、まぁ作ってみましょうか。とこういう風になっている。
ということで以下、仮にAsakusaをOLTPで動かす、ということを考えるのであれば、考慮しなくてはいけない点を、順にいろいろ書いておく。
えっと以下一応、Isolationレベルはすべてserializableを前提に書く。(なお、個人的にはRCレベルの話であれば特段DBを使う必要はなく、その辺のFSをちょっと工夫すれば実現できるので、それはDBとは思っていません。悪しからず。）
前提としてのSILO
SILOの登場以降、DBの世界はほぼ劇的に変わった。SILO以前・以降ではdatabaseというものはほぼ別物だと考えてよい。one-shot request / group commit / OCC（read lock free） / validation-phase / epoch basedはどのDBでも、その在り方・解釈はさまざまであるが、どれも踏襲している。今のところ、自分の観測範囲では、ただの一つも例外はない。この構成要素を持ったうえで、メニーコア・大容量メモリーで動かすというのが現在のDBのスタンダードだ。
よって、今後のWriteの強いDB（＋バッチ処理）を考える場合には、まずもってSILOを前提にする必要がある。
SILOベースでの課題
ということで、SILOでWriteの強化＋バッチ、ということになるのだが、これはまともに行くと絶望的にきつい。実装云々以前に、まずもって基本的な枠組みが、風向き的にアゲインスト。秒速40mクラス。雪山稜線であればシカどころか寝ぼけた熊まで飛ばされるクラス。普通に敗退。
Write lock
まず通常のOCC実装は1Vになる。よって普通にwrite lockをとる。このため、いろいろ書き込みが競合しだすとまず基本的にスローダウンか、abort祭りになる。in-place前提で、write-heavyであれば、これは実装とか理論以前の話として、普通に誰でも想像できる通りで、そして想像通りの結果になる。たしかにSILO/OCCは新しいアーキテクチャを存分に生かしたものではあるが、write特性については1Vである限りlockを取らざるを得ず、その意味では既存DB路線を踏襲している。ベースアルゴリズムがCSRという点もある。んで、んじゃーそのabort祭りをどうするか？ってので、可能な限り超効率的に物理で殴るという方針をとったのが、SILO-OCC-1Vだったりする。そんな感じだ。
SILO-OCC-1Vは、abort&retry勝負はショートレンジの処理であれば、まだ勝ち目はあるが、ロングバッチでは話にならない。まずはserializable云々の前に、とにもかくにも「書き込めます」という状態を確保しないと、そもそも土俵に上がれない。 なので、まずもって「最低限の前提」としてMV化していく必要がある。
MVであれば、とにもかくにもinstallはできる。よって、この場合、大事なのは「MV」である、ということではなくて、「write lockを取らない」ということが肝要になる。installそれ自体はロックされては手も足も出ないからだ。
なお、この目線で見た場合、SILO前提での昨今の“MVCC”-RDBでは、実は役に立たない。基本的にwrite lockをとる手法を採用している。結局は1Vチックな仕組みが主流であり、一応MVを称しているが、形だけmulti-versionといったところが否めない。・・・write lockをとる段階で、本当の意味でのMVCCではなく、単にversionがmultiなだけのDBに過ぎない。単純なw-wをconflictとしないところがMVの最大のメリットだ。その意味ではMVCCと称しながらwrite lockをとる実装は文字通り羊頭狗肉だと思っている。
ということで、MVを前提にして、かつ、可能な限りwrite-lockをとらない原理・実装を選択する必要がある。要するに「read lock free / write lock free」の実現だ。なんかちょっとSFチックな話にすら聞こえかねないが、ただ、これは「ちゃんとした」理論の枠組みと実装方針があれば、多少は勝算はあるとは思っている。
以上は、まずはSILOの枠組みの中の問題になる。すなわちepochな時空間での考え方が基本になっている。
epochベースでのserialization orderの「延長」
次のハードルがこれ。これもかなりキツイ。大体20msecがepochだとして、5minバッチだと、15000epoch。まぁこんなdurationで処理が継続するとはSILOは想定しない。物理GCクラスでの単位になる。epoch跨ぎをどうするか、それも複数跨ぎになるが、というのはちょっと問題としては大きい。これは既存のSILOの枠組みを超えるものになる。
端的に言えば、epochをまたぐバッチ処理中のread/writeとepochの中に閉じているtxとの整合性をどうするか？という問題にある。普通に考えれば問題は山積。
-read
上書きの処理。普通にロングバッチ処理中に読んだ値が、どんどんconcurrentに更新される。しかもこっちはepoch跨ぎなので、バッチ処理より先にcommitされる。同一epoch内であれば、deferred commitの手法を利用することでいくらでも処理可能だが、epochを越えるとなると、over-writeのtxのserialization orderを後ろに持ってくることはできないので、簡単に詰む。よって違う枠組みを導入しないと無理。
-write
バッチの処理中でのwriteを読んだconcurentなtxが先コミットになる。read-fromの要請、すなわちHerbrand semanticsの維持が面倒。定義の”occurs before”をどう解釈するか、という話もあるが、commit orderで逆順であれば、さすがに打つ手がない。これもepoch内部であれば、普通にdeferred commitで処理できる話ではあるが、読んだtxの方がserialization orderが前にくることが強制になるので、これも詰む。
read/writeの両者で手が詰む。
現在のところのアイデアとしては、readについては従来と違う枠組みを考える必要がある、一応ベースになるアイデアはあるので検討中。writeについては要はcommit orderが整合できないtxには読ませない、というプロトコルで対応する。ということでいろいろ検討中というのが目下の状況。まぁ普通に苦戦してる。
いずれにしてもSILO-OCCのようなシンプルに物理で殴るという方法ではなく、ある程度テクニカルな仕組みを理論的な枠組みから構築していくという方向になる。
必要な枠組みとしての検討事項
要するにAsakusa以前に、そもそもバッチ的処理をRDB(OLTP)で行う、ということのハードルが高く、そのための準備がかなり前人未到系になっているという感じだ。けだし、これは従来のRDBでも同じ問題はあって、MVCCよりも制約が強い既存の1VベースRDBではほぼ絶望的だと思う。（SQLをちゃんと書けばパフォーマンスが上がるので十分だ、それほど既存のSQLバッチは中身が悪いので遅い、という話もよく聞くが、consistent / concurrent / write heavyなバッチ処理は実装以前の話として、理論的な枠組みからして無理だろうな、というのが今の実感。）
今後の検討課題は以下
-serialzation空間としてはMVSRを前提にする。
個人的にはMVSRを目標とする。まともに行くとNP-完全なので、どういう制約をうまく利用するか？になると思う。時代の流れもこちらを向いている。真っ向勝負。
-read protocol / write protocol / commit protocol
基本3層protocolの構成をベースに検討。
特にread protocolは現在のところほぼ、read most recently程度の理論・実装しかない。これを整備して行く。もっともwrite protocolですらおそらくappend onlyが関の山なので、こちらも普通にいろいろ検討する必要がある。大抵の枠組みはcommit protocolだけなので、それではもうダメです。
-commit protocolの拡張
基本方針としては、deferred commitを利用する方針で、その拡張を行う。install-based orderとcommit-based orderは明確に分ける。epoch跨ぎを考えるので、concurrentな中にalready committedなものが発生するということになる。従来のコンセプトでは commit / to be committedのみだと思う。
-実装物理レイヤー
これは弊社および某Prjの超絶優秀なエンジニア諸氏にまずはお任せするしかないので、初手から「一番いいやつを頼む」としか言えない。てか、線形リストはもうダメな気がする。すんません、実装とか全部入りで最初から考えてたら、とても精神がもたないので、まじで勘弁してください。
その上で
以上が揃った上で初めて、AsakusaをOLTP上で動かす、ということを検討する、という段になる。
いやー、なかなか遠大な道のりだが、そんなもんだ。見ようによっては「たかだか、RDBでちゃんとバッチ動かします」ぐらいの話でしかないのだが。その上でのAskausaの話だ。
Asakusaは現在のところ、できてほぼ10年近くになるが、いまだに「業務系の複雑な処理を、SIを前提にして、分散処理環境で効率的に設計・実装・実行するフレーワーク」はAsakusa以外に存在しない。その意味では存在意義はあると思っている。実績・完成度もある上にOSSなので、これから別の商用プロダクトができるとは思えない。今後10年もその意義は続くだろう。なので、検討すべき価値が十分にあると個人的には思っている。その意味ではかなり迂遠は道のりであるが、そのOLTPの上でのバッチ処理→Asakusaの検討はありうると思っている。
仮に検討するので、あれば、上記のOLTPを前提として・・・
-I/O周りの再整理
このレベルになったら Wind gate / Thunder gateとかいうより なんかもっといろいろ別物になるくらいの勢いになると思う。Tx制御はもちろん、なんやらいろいろ。あとは、特にtest周りとかどーすんか？とか思うけど。どうすんだろ。初手から「一番いいやつを頼む」としか言えない。いろいろありすぎてちょっとなんとも。
-DSLの拡張
既存の枠組みではできなかったことも低コストでできるようになる「はず」なので、その辺の検討か。型・DAGあたりはまぁ基本だとして、それ以外で、という感じか。やり残りもあるので、その辺り含めてか。
-SQLとの「いろんな意味での再整理」
当然SQL処理との兼ね合いはどうするか？という話はいくらでも出てくる。そもそもストプロとはなんなのか？というところの議論からスタートか。
とかいろいろあるとは思う。ま、そんな感じ。いずれにしても 汎用機のバッチ無理→オープン化→RDBのバッチ遅い→Hadoop/Spark/M3BPの分散処理、というところからきてとうとう「やっぱ既存のDBだと無理から、一からつくるわ」ということになるとは、まさか思わなかった。
そんな感じ
Read only transaction anomaly 現代的な問題として
対象読者：
某Pjrに関わっている人全員。あとはSAPのHANAとかのHTAP系を使っている人。あとはDB系の人とかそっち系の人。
内容はRead only transaction anomalyがHTAPのなかでかなりの厄ネタになるという指摘と、その解決素案の提示になっている。前提知識はMVCC（MVTO、SSN、SSIとかその辺）。
■Read only transaction anomaly
MVが前提で発生するtransactionのanomalyのこと。整合的なsnapshotをとっていて、かつリードオンリーであるにもかかわらず、どのようなserialization orderをとっても論理的に起こり得ない状態を読み出してしまうskewを指す。
わかりやすい例をSSIの論文から持ってくる。
https://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/2009/Papers/p492-fekete.pdf
H: R2(X0) R2(Y0) R1(Y0) W1(Y1) C1 R3(X0) R3(Y1) C3 W2(X2) C2.
T1はR2(Y0)をT2コミット前にW1(Y1)で上書きする。また、T3のR3(X0)は、すでに走っているT2のW2(X2)でT3コミット後に上書きされる。
よってanti-dependencyは
yについてT2→T1
xについてT3→T2 になっている。
またR3(Y1)は直前のT1でコミットされたY1を読んでいる。
よって、通常のdependency(w-r)は yについてT1→T3 になる。
よってT1→T3→T2→T1で循環する。
このときT3について注目すると、R3(X0) R3(Y1) C3であり、yについては直前にコミットされた値と読み、xについてはT2が未コミットであるから当然コミット前のx0を読んでいる。普通にT3としては最新のコミットされた値をリードしており、なんら問題はない。・・・ように見えるが実際は「論理的に起こりえない状態」を読んでいることになってしまっている。
具体的には
H: R2(X0, 0) R2(Y0, 0) R1(Y0, 0) W1(Y1, 20) C1 R3(X0, 0) R3(Y1, 20) C3 W2(X2, −11) C2.
が例になっている。
T2が読んだ値は X=0 Y=0 で X=-11をセット
T1はY=0を読んで、Y=20をセット
仮にserialization orderを考えると、T2→T1でもT1→T2でも X=-11 Y=20 （T1→T2だと、T2ではY=0が読めないので成立しないが、concurrentで考え、T2ではY=0を読んでいるものとする）
ここでT3ではX=0 Y=20で読んでいるが、
本来T3の読む値は
T3→T2&T1であれば、X=0 Y=0
逆にT2&T1→T3であれば、X=-11 Y=20になる
仮にT2→T3→T1であれば、T3はX=-11 Y=0
T1→T3→T2であれば、T3はX=0 Y=20で読めるが、そもそもT2のY=0が読めない、というか矛盾するのでありえない。
つまり、どうやってもX=0 Y=20をT3で読むことはできない。つまり「本来読むことが論理的にできない値を読んでいる」ことになる。
以上は普通にread only transaction anomalyの話であり、ここでの論点は以下のようにHTAPでの扱いだ。周知の通り通常の範囲では、これは相当のプロトコルで排除できるというか、するので問題にならない。
■HTAPでの問題点
現状のHTAPはパフォーマンスを出すためにOLTPで処理するデータセットとOLAPで処理するデータセットの構造をかえて、変換のつなぎをsnapshotで行うことが多い。この時のsnapshotはふつうにconsistent snapshotをとる。
SIでの2大skewの、もう一方のwrite skewについてはそもそもOLTP側の更新処理で衝突するので検出が可能であり、あまり問題になる気がしない。が、OLAP側でのread only transaction anomalyは ”consistent snapshot”をとっていて、OLAP側では更新処理もおこなっていないにもかかわらず、不整合を発生させる可能性がある。そもそも作成したconsistent snapshotが、OLTPサイドではありえない状態を写している可能性があるということだ。（この点では、これはHTAP固有の問題ではなく、オンラインでsnapshotでリードレプリカをとるものはすべて問題になるとも言える。）
例示されているケースではT3がOLAPレプリカでの処理だと考える。
OLTPサイドとOLAPサイドで分けて見てみる。
- H:OLTPサイド: R2(X0) R2(Y0) R1(Y0) W1(Y1) C1[T1] W2(X2) C2.
- 時刻T1でOLTPからOLAPにlog ship。コミット済みのY1がreplicated
- 前提としてOLAPサイドでは初期のX0, Y0のsnapshotレプリカはとってある。
- H:OLAPサイド: [T1]R3(X0) R3(Y1) C3
この場合、OLAPサイドでread only transaction anomalyが起こっている。
（なお、consistent snapshotは本来閉じた系の中でのメッセージの到達・未達を考慮したうえでの一貫性のある系自体のsnapshotのことであり、ACIDの意味でのConsistencyとは関係がない。）
このanomalyをHTAPのような仕組みの中でどう防ぐか？が問題になる。
■どーすっか？
1. 非同期バッチ処理でreplicaをとる
要はconcurrentが走っているtransactionがまったくなくなった段階（quiescent）で、その隙をねらってreplicaをとるという方式。あるタイミングでtransactionの開始を一時的にストップすることができるのであれば可能ではある。普通は流量の少なくなった段階で全部キューに放り込んで待たせて(delayed write)、その間にsnapshotをとるか、そもそも本日の業務終了で受けつけないという例の夜間バッチ処理的な方法をとるかする。ただこれだと、正直HTAPである必要はあまりない気がするわけよ。
メリット：read replicaの整合性が確実に担保される
デメリット：concurrentなwriteがどかどか走ることが続くといつまでたってもreplicaが作れない。
とりあえず最終手段として残しておく案だと思う。
2. writeのabortで処理
これはOLTPサイドでのr-wの検出による形になる。ある意味一番の王道。これを検討してみる。
・単純なMVTO方式の場合
偽陽性上等で循環可能性が少しでもあれば即ハネる。通常のMVCCでのMVTO実装を考える。実装方式はいくつかあるが、lockベースか、validationベースの二つで、validationだとpre-validationか、王道のcommit時点でやるか、の2方式がある。
・もうちょっと賢くやる方式
循環の可能性をもう少し高くなったところでハネる。これはSSNの方式になると思う。この場合は偽陽性の可能性が若干低くなる。
さて、
通常のsnapshotだけととる場合や、ノード内処理に閉じる場合であれば、このふたつの案でいいと思う。ところが、HTAPの上記ようなケースではうまくいかない。
XをOLAP側で読んでいるという情報はOLTP側には行かない。なので、W2(X2)はコミットされる。よってこのままだと上記のMVTOまたはSSN方式は役に立たない。
要は、そもそも読まれているという状態をwrite側が知ることができないのでabortのしようがない。(さらにそもそも時刻同期の問題もあるが、それは置いておく) 、もちろん、リードレプリカ側で読んだ時に、これ読んでるからとwrite側に通知することはできなくはないが、それでもそもそもなんのためにリードレプリカをつくったのかわからない。全部通知する羽目になる。
また、逆にwriteの持ち回りをread replicaにもっていってコミット可能かどうかを確認してからコミットするという方法もある（言ってみれば、RSSIがこの方式である）が、ターンアラウンドがかかりすぎて無理筋すぎる。
なので、HTAPのような場合は、単ノードMVCCのようにwrite側abortだけというのは実は結構厳しい。
メリット：従来の枠組みを利用できる。
デメリット：readの通知をOLTPに送り返す必要があるため、現実的ではない。
3. readのabort
これはOLAPサイドでのr-wの結果を受けての処理になる。replica側に「今write走っているよ」というnoticeすることが前提。
この場合、まず、飛ばすwriteの通知は、snapshotを取っている「最中」のconcurrentなwriteのログだけでよい・・はずだが・・・OLTPサイドでは何がOLAPで呼ばれているかなぞ知ったことではないので、結局対応するwrite log全部送るという羽目になる気がする。（またはOLAPサイドで「今からこれ読むけど、まさか絶賛更新中じゃないよね？」という問い合わせをやる方法になるが、これは上記のように読む値を全部放り投げることになるので、無理筋。）
それでもOLTPサイドは書き込みが続行できるので、それはそれでOKで、もらったOLAPサイドの問題になる。
OLAPサイドでは、readコミット時に、timestampでチェックをして、overlapしているconcurrentな未コミットwriteがある場合は、abortするということになる。続行はどうするかはアプリケーション次第だが、普通はretryしてsnapshotの取り直しになるはず。ただし、この場合、すでにwrite logが来ているはずなので、取り直さなくても良いと思われる。
ただし、readサイドはいちいち読むたびに更新中フラグのチェックを行うことになるので、write heavyの場合は割りに合わない可能性がある。write heavyなレコードあれば、ガンガン更新がかかるので、read側は整合性確保のために、writeコミットまでウェイトかabort & retryさせる必要があるが、これだとロングバッチ処理での更新が絡んだ段階でreadがストップするので、問題になる可能性がある。とはいえ、不整合なデータを読んでも意味がない、という話もある。
メリット：writeのabortが発生しない。read replica側からOLTPへの通知が不要
デメリット：write heavyなワークロードの場合はread abortが多発する可能性が高い
4. read するときに意図的に古いversionを読む。
これはいままでのDBの手法では想定されていない手法になる、と思う。
前述の例だと、
H: R2(X0) R2(Y0) R1(Y0) W1(Y1) C1 R3(X0) R3(Y1) C3 W2(X2) C2から
anti-dependencyは yについてT2→T1 xについてT3→T2
R3(Y1)は直前のT1でコミットされたY1を読んでいる。
通常のdependency(w-r)は yについてT1→T3 。
よってT1→T3→T2→T1で循環する。ので
例えば、w-rのT1→T3をぶった切ってやればよい
T3→T2→T1ならば問題ない。すなわち、R3(X0) R3(Y1)をR3(X0) R3(Y0)にすればよい。
さて、これは表面的にはT3では「今Xの値が更新中で、このままいくと不整合が起きるから、Yの一つ前のversionの値を読め」という、一見言っていることがよくわからない、という感じになる。これはこれで対処療法としてはアリだと思うが、そもそも、場当たり的すぎる。
ということで、少し定式化してみる。
version orderを考える。
・x x0＜＜x2
・y y0＜＜y1
version orderは論理順序なので、ここで合成されたsnapshot空間Sn(xn, yn)を想定する。
初期値S0と終了値S∞を想定し、空間遷移をcommit orderで決定することができる。
commit orderがc0＜c1＜c2の条件であれば
S0(x0, y0) ＜＜ S1(x0, y1) ＜＜S2(x2, y1)
commit orderがc0
- projected H:OLTPサイド: R2(X0) R2(Y0) R1(Y0) W1(Y1) C1W2(X2) C2.
anti-dependencyはyについて、T2→T1
このときのserialization order での「論理的なcommit order」はc2
S1’:H: R2(X0) R2(Y0) R1(Y0) R3(Y0) W1(Y1) C1 W2(X2) C2 R3(X2) C3
S2:H: R2(X0) R2(Y0) R1(Y0) W1(Y1) C1 W2(X2) C2 R3(X2) R3(Y1) C3
以上で確かに可能。
なお、この場合にどこにreadを入れるか？はSの遷移のトリガーにより決定されるので、
S0 (x0, y0) ＜[c2]＜ S1’(x2, y0) ＜[c1]＜ S2(x2, y1)より
S0については、c2/c1の前であればどこでもよい。
S1’については、x2はc2の後、y0はc1の前であればどこでもよい。
S2については、c2/c1の後であればどこでもよい。
実際、S0のケースであれば、
S0:H: R2(X0) R2(Y0) R1(Y0) R3(Y0) R3(X0) C3W1(Y1) C1 W2(X2) C2以外でも、
S0:H: R3(Y0) R3(X0) C3R2(X0) R2(Y0) R1(Y0) W1(Y1) C1 W2(X2) C2とか、
S0:H: R2(X0) R3(Y0)R2(Y0) R1(Y0) R3(X0) C3W1(Y1) C1 W2(X2) C2 とかなんでもよい。
ちなみに、所与のR3(X0) R3(Y1)は到達可能ではないので、棄却される。（これは今後の課題にはなるが、MVTO的な手法とは「別の方法」でread-only transaction anomalyを検出できる可能性があるということを意味すると思う）
こんな感じで読めるversion制約は、論理的なversion orderによるsnapshot空間の遷移とトランザクションの論理制約(serialization order)を解くことで解決する。あとは遷移のトリガーとreadの実行タイミング（たぶんtimestamp）を比較して、読むべき論理空間Sを決定すればよい。
ということで別段、古いversionを読まなくても「論理的に整合性のとれるversion」を読めばいいという手法を導入することで、解決する。
これは例えば、「write heavyの処理を実行している最中でも、完全なlockフリーでread heavyなロングバッチを一貫性を担保したまま、同時に走らせることができる」ということになる。これはこれで凄いはず。
・・・ということで理屈上は解決できるが、実装上でどうするか？は結構考えないといけない。
・まずS空間とか全部挙げてたら、間違いなく即死する。
・そもそもどのタイミングでどう判定するのか？
・論理的に可能なSが実際に存在する保証が必要（というか多分自明だけど要証明。たぶん分散系のロジックで行くと思う。）
・普通に探査はNP完全の予感（そもそもこの手のグラフ系のアレ）
ということでいろいろある。
くどいようだが、上の例は、あくまで例の一種で、選択可能なsnapshotを適切に選ぶことで、anomalyを回避できるということが論理的には可能だと言っているだけである。
この延長線上には、read-onlyはともかく、OLAPサイドでなんらかのwriteを行った場合はどうなるのか？も問題になってくる。これはread-only transaction anomalyとはいえないので、別の話題にはなるが、例えば、更新処理をstreaming的にOLTPサイドで行いつつ、OLAPサイドでレポートを同時に作成するような場合、レポート作成時の値をどこに書いておき、どう整合性を持たせるか？ということも視野には入ってくる。
メリット：write abortもread abortもしなくてよい。
デメリット：理論も実装も今のところはない。論理的に可能だと思われるというレベル
■うむむ
いままでの通常の解決は1だったはず。これは一種のETL処理を間に挟むことになるわけで、期せずしてread only transaction anomalyをたまたま除去していたにすぎない。しかし、サーバ・アーキテクチャの変化とともに低レイテンシーなノード間通信が普通になってきて、HTAPのようなwriteノードとreadノードのレプリカ間のlog shipが数十msecになる現在、いままで顕在化してこなかった、こういう問題が顔を出すことになる。
write側をノンストップで更新して、readレプリカをポンポンとるような仕組みであれば本来、問題になったはずだが、なかなかそういうイケてる仕組みは環境の制約でパフォーマンスが出ずに現実的ではなかった。なので、あまり問題視されなかったのだと思う。（あるいは単に気づいてなかっただけかもしれない(白目)）・・・これはconcurrentな条件で意識的にテストケースを書かないと検出できないヤツなので、たぶん「なんか値がおかしいから、分散処理でのタイミングでのバグでしょう。もう一回やったら問題ないし」とかで実装ではスルーしている可能性が高いと思ってる。
実際の解決の方向としてはどうか？ということであれば、やはり、read abortか 適切なsnapshotの選択の二択だと思う。まぁRead Or Dieだな。読子・リードマンだ。
とはいえ、まずread abortについては、そもそもあまり理論的な枠組みがない。現行（2018年現在）のMVCC-OLTPではあくまで単ノードの立て付けで、write abortしか考えていないのが現状で、こういうHTAPでの「read-abort」も一緒に考えるという理論はまだ開発どころか、研究もされていない。普通にabort & retryがどうなるかはやってみないとわからないし、頻発する場合の手法も現状では只の力技しかないだろう。それなりになにか考えるしかないと思う。
次の選択的なsnapshotでの解決はjust ideaベースでしかないので、やるのであればこれから模索という感じになる。理論的には一番エレガントに見えるが、これ普通に実装すると即死するのは目に見えているので、実践するには別の考え方でのエンジニアリングがいると思う。
そんな感じなんで、要は、今のところはpracticalなものはない、というのが実態でしょう。選択的なsnapshotでの解決はアプリレイヤーでも実装ができそうなので、HATPを現実に使う（たとえばSAP）のような場合では、なんらかのフレームワークを実装するというが現時点の解だと思う。
■完全に私見だが
そもそもMVCCはread-lock-free / write-lock-freeが理想であり、「適切なversionをread することさえできれば（＝correct）、何をやってもいい」というのが本来の理論的な到達点のはずだと思っている。蓋し、その意味ではMVCCにおけるanomalyは、writeで発生する物理制約と、read（view）で発生する論理制約のギャップによるものにすべて還元できる。今回はその典型的な例だと思ってる。
最後の案の、適切なsnapshotを選択する、という方法は、翻って見れば、これは単一ノードにおいても、readするversionの選択が適切であれば、anomalyは除去できるということにもなる。すなわち、この限りにおいてはMVTOのプロトコルは完全に偽陽性。勿論write skewの除去は必要なので、その意味ではr-wでの追い越しでvalidationは意味があるが、SSNの指摘も含めて、やり過ぎということになる。
HTAPを契機にして、従前な形でのwrite abortだけを前提にするのではなく、readサイドでも見直しをすることで、より豊かな理論的な枠組みが得られると思う。
こんな感じ。
Serial Safety Net 再考
SSN
Serial Safty Net
原論文は以下
https://pdfs.semanticscholar.org/ecf9/821e0c4f1f28fb7eb42c5eaa8a92cf16ade9.pdf
Txのserializabilityを判断する、いわゆるcertifierになる。実際はDBのTx処理のvalidatorの実装として組み込まれることが通常だと思う。ERMIA(
http://www.cs.sfu.ca/~tzwang/ermia.pdf
)ではそうなっている。想定としては下位レイヤーにSI(Snapshot Isolation)またはRC(Read Committed)な実装を想定している。
原理はTxのdependencyをトラックして、コミット時点でvalidationを行い、dependency cycleが発生する可能性が高いかどうか判断する。リードが大半を占めるようなケースでも、過剰なトラッキングを行わないため、いろいろなワークロードでパフォーマンスを劣化せずにserializablityのテストが可能になる。
個人的な観点としては・・・現状のMVCC/OCCの現状の最大のボトルネックはabortの高さだ。パフォーマンスを落とさずに、このabort率をどう低減させるのかが最大の課題だ。個人的にはCicadaのようなpre-validationが有効だと思っている。その意味ではSSNのようなものをpre-validationに利用することが効果が高いのではと思っている。
ざっくりまず理解にするに当たってのガイドラインを書いておく。念のために断っておくが論文自体はものすごく丁寧にかかれて詳細まで検討されている。が、その分「暗黙の理解」が省かれているので、なんとなくわかった感じで読み進めると、なにがなんだかさっぱり君になる難解さを持っている。
尚、近年のTxはOCCとMVCCまたはその中間的な議論が多く、SSNはそのなかでは若干異色の存在になっているように見える。ただし、この仕組みは理論的な実りが多く、今後のMVCCを見て行くにはさまざまヒントがあちこちに見て取れる。今後専門的にDBに関わる人間であれば、内容の理解を強く勧める。2016/2017年で間違いなくTx理論では、トップエンドの内容だと思うので、普通の人は特にわからなくともいいと思う。
■ガイドライン的な
1. commit orderと dependency orderが正順（P.Bernstein流に言うと「左から右に一直線に」）になっている場合はdependency graphは循環しない。よってserializableになりうる。というか
「serializableではない可能性がない」（←これ大事）
2. すなわち「serializableではない可能性がある」のは、少なくともgraphのひとつは「commit orderと dependency orderが逆順である」ことである。すなわちdependency orderとは逆順の commit orderが存在する必要がある。これが可能なのはr-wのdependencyにおいて、そのコミット順が逆であること、すなわちリードしている最中に別の書き込みのコミットが先にあった場合「だけ」になる。
2-1 w-rにしろw-wにしろ、先行がwの場合は先コミットが先行のwでなければならない。ここはmulitiversionが暗黙の前提になっていて、w-rが逆コミット順（逆順）だとrは別のversionを読む羽目になるし、w-wの場合はそもそも順序が逆になるだけになる。つまり、commit orderに正順のdependency orderをつくることになってしまう（というか勝手にできる）。かつ、r-wが逆順の場合はそもそも2.のケースになる。r-wが正順の場合は、循環もへったりくりもないのは自明だ。つまり、「serializableではない可能性がある」ことになるのは2の場合だけだ、という結論になる
2-1-1 w-rのコミット順については、表面上はw1r2c2c1が可能であるが、これはRCを満たさないのでアウト。一般にはcommit dependencyの形をとることが多い。理屈ではdirty readの防止ということになるが、理論上はリカバリーのコンテクストで要件とされることが多い。一見、正常系のserializableの理論では現れない黙示の制約になることが多い。留意が必要。
3.ただし、2があったからといって、それが「serializableではない」かというとそうではなくて、循環する可能性があるだけであり、それだけでは広すぎて偽陽性になる（これがMVTO）。なので、もう少し狭める条件があるはずだ、ということでSSNが以下を提案している。
4.validationするTxについて、そのr-wエッジの先端のTxのコミットタイムをπ（T）とし、通常のdependecyエッジの先端のTxのコミットタイムをη（T）とすると、Txのdependencyで先行するTxのUについて、 π(T) < c(U) < η(T)であれば、「よりserializableではない可能性がある（＝循環グラフをつくることができる）」条件を絞ることができる、という理屈だ。これがSSNになる。
3-1. ということで3を見ただけでも、SSNがMVTOよりもスケジューリングパワーが広いことがわかる。ただし、下位のCCスキームが刎ねてしまえば、元の木阿弥でなんの意味もない。
○概説
以下、論文に沿ってSNNを概説していく。手元に論文があることが望ましい。
■大枠
一応前提らしきものを提示しておく
・SIまたはRC(Read committed)レベルのconcurrency controlがあること。
・SSNはdependencyをトラッキングしてコミット可能かどうか判断する。ただし偽陽性がある。
・2PLやSSIよりもRC＋SSNやRCL（RC w/lock-base）+SSNの方がconcurrencyが高い。
・既存のディスクベースでも可能ではあるが、一応multi-versionのメモリーベースの実装を想定している
・global なユニークなtimestamp。できればcentralizedがいいが、centralから一括で割り当てられたものをローカルで振り当ててもよい。
一応特徴としては・・・
・下位のRCLやRCLの実装バグからフリー
・phantomも除去可能
・read mostlyで重い処理でも、別段read setの中の最近更新されていないレコードをトラッキングする必要がない
等々
・低い競合状態でもCCの邪魔はしないし、高い競合（write-intensiveでもread-onlyでも）パフォーマンスを劣化させない。
□SSNは主に以下のふたつのパーツで構成されている
・π(T)の計算
通常Tのあとにserialization orderが来るべきだが、Tの前にコミットされてしまうdangerousなtxの最小基準値（ts）をさす。SSNでは low watermarkと表現している。
・validation test
あるTをコミットするとき(c(T))に、(本来はTの後にコミットされるべきだった)Uがすでにコミットされており、Tとconflictを持っているとすると、π(T)<=c(U)
- T read a version Ti created (Ti ←w:r T)
- T overwrote a version Ti created (Ti ←w:w T)
- T must be serialized after Ti
普通の依存関係、書いたものを上書きするか、書いたものを読む。
Serialization orderはTi -> T
2. T ←r:w Tj (read anti-dependency)
- T read a version Tj overwrote
- T must be serialized before Tj
Anti-dependency：読まれているversionを上書きする。
Serialization orderは T -> Tj
Notation
T ← U : serial dependency
T ←w:x U or T ←r:w U 表記として TはUのdirect predecessor UはTのdirect successorとする。通常の教科書的な表記と向きが逆になっていることに注意。
この依存関係でグラフ(G)を形成する。
GにおいてTi < TjというときにはTiはTjの前にorderされている。すなわち Ti ←…← Tjが成立している。
このとき、TiはTjのpredecessor で、TjはTiの successorになる。
それで、Ti < Tj < Tiになったときに、serialization failureになる。
Failureの最も単純な類型は以下の三つになる
T1 ←w:x T2 ←w:x T1 : T1とT2がお互いのwriteを読む（あるいは書く）
T1 ←w:x T2 ←r:w T1 : T1はT2のwriteを読んでいるが読んでる端からT2が書いてる
(T1 ←r:w T2 ←w:x T1は単に順番の入れ替え)
T1 ←r:w T2 ←r:w T1 : お互いに読んで書いているものが循環している(write skew)
Tがpre-commitに入った時刻をC(T)とする。コミットタイムで全順序で、グラフGについて、
predecessorが先にコミットした場合はforward edge
successorが先にコミットした場合はbackward edge
とする。
ややこしいのですが、要はdependency orderとコミットorderは違うものですよ、ということです。
forward edgeの時は、T ←w:x or r:w Tでどのタイプでもよい T ←f T
(コミットされたものでなければ読めないし、書けない)
backward edgeの時は、必ずT ←r:w Tのanti-dependency T ←b T
(コミットされたものを読むわけではない)
forward / backward edgeは簡略ができて
T ←f T ←f T ….. ←f T ←f T であれば T ←f* T
T ←b T ←b T ….. ←b T ←b T であれば T ←b* T
(論文ではこのあと引き続きRC/RCL/SI/SSIを説明するが、既知でいいと思うので省略)
以上で道具立て。
■SSN:
Serial Safety Net
Dependency graphにおいて潜在的な循環をつくるようなコミットを防止する。
前提ではあるがRCが保証されていることが下位レイヤーに要求される。
・Preventing dependency cycles
SSNはC(T)に加えて、π(T) η(T)を利用する。
π(T)：Tの、backwardなエッジをたどって到達できる最も古いsuccessorのU、そのUのコミットタイムをπ(T)とする。
すなわち
π(T) = min(c(U) : T ←b* U)
これを再帰的に適用することができるので
π(T) = min( (π(U) : T←b U) ∪ c(T) )
したがって、π(T)を求めるにはdirect successorだけを見ればよくて、いちいち再計算する必要はない。
留意点はπ(T) < c(T)であり、Tのコミットが決まった段階で、c(T)が決まりπ(T)も決定する。πは変更されない、なんとなればTはコミットされるので、そのsuccessorはforward エッジしか発生しないから。
DEFINITION 1. A dependency edge U ← T in G (or alternatively, transaction U) violates the exclusion window of T if π(T) <= c(U) < c(T).
すなわち、SSNは、Tがコミットする場合にdirect predecessor Uのexclusion windowから外れた場合はコミットさせない
不等号条件は、先にコミットされるTのpredecessorのUがTのsuccessorになる可能性の排除になる。（排除しないと循環）。実装上は、処理を簡潔にするために二つの手法を使う
1. T以前にコミットされたpredecessorのみを対象とする、というのはTのpre-commitの最中にチェックが完了するから。
2. T以前にコミットされたpredecessorのうちで最新のもののみ見ればよい。これはη(T)を使い、π(T) <=η(T)であれば、Tをabortする。すなわち
η(T) = max (c(U):U←f T)∪(-∞))
以下、順番に論文のFigを解説する。図は縦軸がcommit order（すなわち時間軸）で横軸がdependency order（すなわち理論上の依存順序）を表している。普通はtが横軸で、dependency orderは正順での依存記述になるので、いろいろ逆向きに書いてあるが、要は基準となるwatermarkをhorizontalに表現したかったのではないかと思う。これはこれでまぁ慣れればわかりやすい（というか慣れればなんでもわかりやすい）ので、いいかなとは思うが。
forward edgeが下向きになる。コミット順。T5 ← T1
backward edgeは上向きになる。dependencyがあとのものが先にコミット。 T4 ← T3
T1がT2のexclusion windowに違反している。
チェック対象はT2 (T5, T4, T1, T3 と来て次がT2 : commit order)
1よりT2のpredecessorであるT1を対象
π(T2)はc(T5)で η(T2)はc(T1) になる。π（T2）＝c(T5) < c(T1) = η(T2)
より、π（T2）< η(T2) よってT2はabort
イメージ的にはr-w r-w・・・r-wのdependencyで最後のwが最初のコミットになっていたとして（C(T5)）、最初のr-wのrが読んでいるTxが、C(T5)すなわち最後のwを書いているものよりも、後にコミットしているとそれを読んでいる（または上書き）可能性があると、コミットのチェーンが循環する可能性があるので、まずい、ということになる。
T2については、それ自身の情報のみで判断できる。T1のpredecessorを知らなくてもよくて、単純にT1がsuccessorになるかも知れないということが想定できればよい。
これは問題のないケース。π(Tx)より先にT3がコミットされている。よってTxのsuccessorになることはできないので、Txで循環をクローズすることはできない。
これは偽陽性。T3は循環が生じる可能性がないが、abortになる。ただし、T1のpredecessorがT4にdependencyをもつとアウトなので危険といれば危険。
・Safe Retry
Tが、Uがexclusion windowに違反するためにabortした場合で、ただちにT’としてretryした場合、T開始前にUはすでにコミットされているので、その場合T’はUが作ったversionをanti-dependencyではなく読むことができる。よって、UはT’のabortの原因にはならない。
この手のsafe retryの属性はもっと注目されるべき。2PLだとdead lockになる可能性（前でdeadlockでabortしたとして、今度はそのdead lock winnerとdead lockになる）もあるし、OCCではread setのvalidationでまたこける（writeのoverwriteが終わっていない場合もありうる）可能性もある。
・Correctness
SSNの正当性の証明
・serial dependency graphが循環しなければserizaliable (これは前提でよい)
・下位にRCレベルのCCスキームをもつので、lost updateとdirty readは防止できている
・あるスケジューラーがserializableでないスケジュールを生成するとして、そのスケジュールのdependency graphにある、SSNのターゲットになるdangerous edgeを特定し、そのエッジが該当スケジューラーが生成する任意のdependency graphに存在することを証明する。すなわち、あるスケジューラーがserializableでないスケジュールを生成する場合は、必ずdependency graphの中にexclusion windowに違反するエッジが最低一つはある、ことを証明する。（対偶の証明）
証明
あるスケジュールがserializableでないとすると、それは最低でも2以上のTxを含み、かつ循環をもつ。
その循環の最初のTxにおいて最初にコミットされるものTnとする。
すなわち、Tn←T1←T2←...←Tn-1←Tnになる。
このとき、Tnは最初にコミットされているので、T..←Tnのエッジはbackwardになる。
ここで、Tk ←b* Tnになる最小のkを選ぶとすると、π(Tk) <= c(Tn)になる。
さらに、Tkのpredecessor、すなわちTk-1(またはk=1の場合はTn）へはforward エッジになる。
以上により π(Tk) <= c(Tn) <= C(Tk-1) < C(Tk)
よって、常にTkが存在し、Tkのexclusion windowsに違反するpredecessorが存在する。
すなわち、あるスケジューラーがserializableでないスケジュールを生成する場合は、必ずdependency graphの中にexclusion windowに違反するエッジが最低一つはある
- TkからTnへのdependencyに注意：r-wのbackward edge
- U←Tにおけるπ(T) <= c(U) < c(T)で見ると、UがTnで、TがTkになる
- Tnがコミットされていて、次にTkがコミットしようとする、という流れを想定できる
・追加的な議論のポイント
他のCCのスキームとの比較を図で行う
SSNは当然許可。2PLも問題ない。すべてのCCスキームで処理できる。
2PLのみアウト。2PLはbackward edgeが許容されない。SSNでも問題ない。
SSIがしばしば棄却する。通るのはbackward edgeの最後がread onlyでかつ十分に古い（コミットオーダーが、少なくともforward edgeの二番目にTxの更新より前）であるとき。
SSNは通す。
SSIではアウト。backward edgeの終端の前に、forward edgeのTxがコミットしている。
SSIでは問題ない（r-wの段階で先行は全部コミット済み）。SSNも通る。
SSIでは、Tがその前のpredecessorがdependした段階で、r-w/r-wの持ち回りのチェックでアウトになる。SSNでもアウト。これは擬陽性
次は時系列の分析
(a)については、破線を越えた段階でたいていのCCではどれかがabortになる。
（たいていはt1w(A)がt3r(A)で読んでいるものを上書きしているのでアウト）
SIであれば問題ない
(b)はSI下での(a)の図示
(c)は同じくSIだが、T3が先にコミットのケースでSSNではアウト
(d)はRCでのケース
2PLのデッドロックについて
デッドロックの例としては、(a)を書くと・・・
・T1がBをリード
・同時にT1はT2（Bを書きにいく）をブロック
・T2はT3（Bを読む）をブロック
・一方、T1はAの書き込みをブロックしようとして・・・
・T3はAにリードロックをとっている
SIベースだとどうなるかというと、T3のBのリードはT2が書く前versionを読む。よって
・T3 ←b T2 T1も同じなのでT1 ←b T2
・SIの場合は、単一のbackward edgeでabortするので、すくなくとも一つはabort
・SSIの場合は、T3 ←r:w(A) T1 ←r:w(B) T2で、かつT2が先にコミット（Bの書き込み）して、T3がリードオンリー（Bを読む）なので、dangerous structureができてabortする。
一方、SI＋SSNだと、これは(b)のdependency graphになって実行可能
もっともこれは完ぺきではなく、たとえば、T1がT3の後の最後にコミットしようとすると、
π(T1) <= c(T2) < c(T3) < c(T1) になるので、exclusion windowに引っかかってアウト。これは(c)のケースになるが、実際はserializableである。
RC+SSNの場合は、dependencyグラフは(d)になるが、
・T3のリードは、T2のコミット済みのものを読む
・なのでdependency graphはT2 ←f T3
・またT3 ←b(A) T1 ←b(B) T2 よってπ(T3) = c(T2) になる
・T2はT3のpotential successorなので π(T3)=c(T2)
- まず前提的に
・multi-versionを前提
・versionとTxの、SSN用のメタデータを格納する必要がある
・single versionのCCのオーバーレイとしてversion管理のためのlock制御が必要になることがあるかもしれない。lock-basedなSSNについてはとりあえず置いておく
- 基本プロトコル
必要な空間と計算量は実行中のw/rのフットプリントにほぼ線形で比例し、かつversionごとに追加で一定のスペースが必要。dependencyの管理はtimestamp(以下TS)を利用する。実行中および最新コミットのTxについてのTSはTxのコンテクストに格納されるが、それ以前の古いTxについてのTSはversionの中に保存される。
Tx Tがversion Vをつくるときに Tx RとTx WがそれぞれVを読む、または 書く（上書き）するとすると、以下が定義できる
c(V) = c(T)
π(V) = π(W)
η(V) = max({ c(R) : T ←f R} ∪ c(T))
これらのversionについてのTSの情報はversionに記録される。なお、dependencyの情報は複数のTxが同時に存在した場合、特にvalidationでかぶったときのみ必要になる。
VersionとTxのメタデータ以下になる
なお、versionのメタデータはversionが有効な間は保持される、またTx自体はTxが完了すれば必要ない。
- 下位CCレイヤーとの連携
下位レイヤーではTxが読むべきversionを特定する。したがって、SSNのread/writeでは引数として下位CCが返すversionをとる。このversionのスレッド間の同期はCCの責任になる。たとえばSIがCCの場合は、versionトラバースをして最新のversionを返す責任はSI実装側にある。SI実装によっては、未コミットのversionを返すこと（その場合はc(V)にはversionを作成したTxIDを格納することが多い）もあるが、その場合は読んでいるversionをスキップして次をとりに行く。コミットする場合は、versionを生成するTxがTx-IDを実際のTSに書き換える。なので、SSN側では常にコミットされてimmutableなversionを読む。
SSN側のwriteは時にconcurrent writeをハンドルする必要もない。下位のCCが新しいversionの追加できるかどうか、たいていはversion chainのラッチかTxのTSの比較によって、判断する。
成功した場合はCCのwriteのプロトコロとして、v.prevに上書きされたversionへのポインタをセットする。それからTxがSSNのwriteを利用してTSを更新する。下位のCCレイヤーではTx最中の新しいversionを見せないようにすることを保証する必要がある。（例えば生成TxのTx-IDをc(T)に埋め込むとかして）
なお、commitについてはread/writeと違ってTx間で適切な同期処理が必要になる
- Read
vは下位のCCから取得する。Tx tが読むべきversion vになる。
・tのwriteセットとreadしたvが交差している場合はrepeated readなので処理はしない。(自分で書いたversionを読んでいるだけ) 以下交差していないことが前提。
書かれたversionを読んでいるので、vはコミット済み。そのvについて
・η(t) < v(c) ならばη(t)を更新する。自分のforward edgeが伸びる。w-rの依存になる。
・さらにそのwriteの上書きがある場合とない場合
ない場合はv.successorがないので、π(v) = inf これはそのままreadセットに追加する。
ある場合はv.successorが存在して、π(v)には値がある。コミット済みのvを読んだ時に、同時にそれに更新をかけているTxがあるということ。すなわちr-wのanti-dependency（自身はr）が起きている。wが先にコミットの場合はπ(v) < π(t) になるのでπ(v)を自身にセットする。自分の backward edgeが伸びる。r-w依存になる。
注意：後続がない場合の普通のr-wで考える。vをrして、同時にvをoverwriteするのみとする。
v.c(T)はセット済み。vのsuccessorはないとすると、v.sstamp = t.cstamp = c(T)がセット済み。overwriteしているtwがコミットする段階で、overwriteするversionが作られて、post-commitで v.prev.sstamp = tw.sstampでセットされる。すなわち、最初の読まれたvのsstampが更新される。
最後にexclusion windowのチェックを行う
- Write
普通にversion(v)を加えるだけ、pstampは前のものの方が新しければ引き継ぐ。ただし、コミット時点で他のTxへanti-dependencyを引き起こす可能性があるので、そのためにwriteセットを保持する。
- Commit
commitはpre-commitとpost-commitに分かれる
- pre-commit
π(T)とη(T)を確定して、コミット可能かexclusion windowのテストをする。以下のステップで処理する
・c(T)の取得
・c(T)確定以降はread/writeは禁止
・π(T)の計算（c(T)の前にoverwriteされているリード対象のVのπ(V)のみ考慮すればよい）
・η(T)の計算
ただしdependencyとしてはreadとoverwriteの二種類になる
overwriteの場合は、他のreadに対してdependencyを発生させることに注意
・π(T) < η(T)のチェック
・問題がなければステータスをcommitに変更
- post-commit
・versionのc(V)を更新
・π(V)の更新
・η(V)の更新
- Latch-free parallel commit
上記のpre-commit/post-commitは基本Latchベースになっている。これはin-memory型の仕組みではスケールしない。なので、latch-freeにする
main-memory OLTP systemsが前提。全部のワーキングセットがメモリー上で、Txの処理は単一スレッド内部で完結する。また、メニーコアが基本で中央管理的なロック機構は使わない。
- Finalizing π
Latchベース
Parallelベース
latchベースだと、v.sstampの取得にロックがかかる。すなわちconcurrentなwriteからのv.sstampのoverwriteが許容されない。ロックフリーの場合は、リードしている最中にconcurrentにどんどんoverwriteされることがある。この場合overwrite側のc(T)は、リード側のc(T)よりも前か後ろのどちらの可能性もある。overwrite側が早い場合は、リード側はsstampを（overwriteした側のsstmapで）更新する。
下位CCがSIの場合、Tx-IDがversionのcstampにセットされないと読み出せない。overwriteの場合は、上書きのversionのinstallが終わった段階で、overwriteしたVのsstampに自分のTx-IDをセットしないといけない。SSNだとpost-commitでのv.prev.sstamp = t.sstampの処理になる。んで結果として、concurrentなリード側は正しいsstampとTx-IDが読める。（先に終わるまでspinして待つ。注意：一種のcommit dependencyの処理だと思う）
尚、シングルスレッドの場合はSSNのコミットプロトコルではTxのステータスは別段concurrentなTxに提供する必要はない。順序実行されるだけなので。
尚、上書きのc(T)がTxのc(T)よりも遅い場合は、ウェイトせずにそのまま実行しておしまい。
- Finalizing η
Latchベース
Parallelベース
まず基本的な違いは、Tの処理中に、V(T書き込むv)については最大で一つoverwriteがありうるということ。（当たり前だが複数はない、それはoverwriteのoverwrite。）
また、prev.v(書き込む前のversion)を読んでいるreaderは複数で、そのpstampを更新する必要がある。とくに、自身の前にコミットしているもの(r.cstamp < t.cstamp)についてはSSNではreaderトレースの実装としてはarrayではなくbitmapを利用している。(注意：r-wのdependency)
- 具体例として、三つのスレッドを考える
Thread1 v1を作成してコミット済み
Thread0 はappendしてv2を作成しているが、まだpre-commitに入っていない。
Thread2 v1をリードして、v1.readerの最後から3ビット目のフラグを立てる。
Thread0がコミットしようとする時点で、v1.readerからThread2がリードに入ってることがわかり、
かつ、Thread-Tx mapping tableからv1のcstampもわかる。
尚、versionのreaderからcstampを取得して自身のpstampを更新することができる。このときのbitmapからのThreadIDの取得は実装としては、BSR(Bit Scan Reverse
War on Theism: x86 Instruction Set Reference
)利用している。
上書きをする場合は、前のversionのreaderのpre-commitが終わってcommit tsを取得するまでspin-waitする。それからそのversionのcstampを利用して、自身のpstampを更新する。
尚、bitmapの場合は本当にreaderが存在するかどうかが保証はされないため、concurrentなリードを見に行く必要がある。この場合はηはより大きくなる可能性があるのでその分偽陽性の可能性もあがる。この確認のコストよりもbitmaを利用する方がメリットが大きい。（注意：通常は多分TSでソートしてポインタを張る）
- Post-commit
π・ηがクローズしたあとは、exclusion testをして必要ならabortする。問題なければpost-commitを行い、
読んでいるversionのpstamp/stampを更新し、新しいversionのための初期化を行う
ちょっと整理：後ろがTになる
r-wでc(r) < c(w) 通常のDependency finalize η(自分が書いているvを読んでいるrを確定)
w-rで c(w) < c(r) 通常のDependency finalize Π(自分の読んでるwに割り込みのwがあるかどうか) -> なければpost-commitのみ
w-wで c(w) < c(w) 通常のDependency finalize ηでそのまま抜ける post-commitのみ
r-w で c(w) < c(r) anti-Dependencyの上書きをする側 finalize ηで if ( r.cstamp < t.cstamp)でヒットしないので抜ける
■オーバーヘッドの削減
スケールのさせかたとmultiversionとヘテロワークロードへの対応についての考慮。
SSNはπとηのメタデータのコストがかかる。ほぼTx（readとwrite）の量に比例してかかる。特に、read-onlyやread- mostな場合にリードセットの確認のコストが馬鹿にならない。基本的な最適化の方針は、read-onlyに対するdependency trackingの除去とread-mostlyに対するコールドデータのtrackingの除去になる。
1.既存の利用
まず基本的にどんなMVCCでも、cstamp (c(T))とv.prev(前のversionに対するポインタ)は必ず実装されているので、追加で必要になるのはv.pstampとv.sstampになる。pstampはversionができた時点でセットされ、上書きがされる前にすべてのリーダーにより更新される。上書きがされた時点で更新はできない。一方、sstampは上書きする側のはコミット時点に更新され、そのリーダーは自身のsuccessorのtimestampの更新に利用する。つまり、pstampとsstampは単一のwordに格納することができる。
また各Txはpre-commit終了時点でcommittedと見なせるので、visibleになる。このときリーダーはTのTIDでステータスを取得し、利用可能ではある。
2.Safe snapshots and read-only queries
• Safe snapshots: (Serializable Snapshot Isolation in PostgreSQL)
http://vldb.org/pvldb/vol5/p1850_danrkports_vldb2012.pdf
A read-only transaction T has a safe snapshot if no concurrent read/write transaction has committed with a rw-antidependency out to a transaction that committed before T’s snapshot, or has the possibility to do so
という定義になっている。実装上は単純でsnapshotを作る段階でr-wのTxを全部記録して、そのTxが全部終わったらread-onlyの処理を走らせるという仕組みになっている。現実にはconcurrentとは言いがたいと思うが、一種のバッチ処理的な扱い。
これに対してSSNはより”active”な処理をしている。まずsnapshotの取得は普通にリードのTxと見なす。当然concurrentなwriteについてはanti-dependencyになるので、write側は普通に処理する。snapshotの対象のversionも普通に更新できるが、snapshot前のversionにr-wのanti-dependencyが発生する場合はabortする。ってこれ普通にread-only anomalyの除去でしかない気がするので、何か別に特別なことをやっているわけでもなんでもないと思われる。
注意：要はread-onlyの時のリードのオーバーヘッドが軽減されるか？ということなんだが、一応、We adapt the safe snapshot to free read-only transactions from dependency trackingって書いてあるんだが、そうは読めないので、今度本人に聞いてみる。普通にtrackingしてる気がする。
3.Read-mostly transactions
要は大半はリードだが、ちょこっとだけ更新する場合の処理。SSNではアルゴリズムを見るようにreadセットを全部チェックする必要があるのでコイツが面倒事になる。なので、その負担を減らす。
ポイントのひとつは、この場合の大抵のリードセットはかなり大きく、そのうちconcurrentに更新されるレコードはそれほど多くないということ。（注意：と言っているがそうでもない。単純にリアルタイム集計を考えればわかるがガンガン更新はかかる。ガンガン更新がかかるからリアルタイム更新の存在意味があるわけで。更新があまりないなら適当なタイミングでの定期バッチでも業務的には十分。）そこで、まず、最近上書きされていないversionはstaleと見なす（thresholdあり）。それでread trackingを行わない。こういう戦術をとる。
この場合問題点は二つで、
1. readがトラッキングしないので、write側は最新のpredecessorのステータス、pstampがわからない。
2.read側からはconcurrentなwriteがわからなくなる。また、これはreadのsuccessorがserializableにならない可能性を残したままreadのコミットができることになる。
ここでRead-mostlyはあくまで一つのスレッドで処理される、という点を利用する。各versionにstampすることなくコミットできるようにする。その代わりにスレッドそれ自体にcstampを記録させる。（図のtransaction tabaleのlast cstampを利用する）
・・・自分自身のThreadに自分のcstampを記録する。がvの値は更新しない。→結果πは大きくなる→偽陽性になる
1. T（thread t1）がtrackingなしでVを読む
2. Tはv.readersのビットフラグをセットしてt1のlast cstampを更新してコミットする。このときにビットフラグはリセットしない
3. Tが「コミットした後で」U(thread t2)がVをoverwriteする
4. このときすでにthread1は別のTx Rを走らせているとし、かつRのフットプリントはTまたはRに重ならないとする
5. Uはpre-commitの時点でv.readerをチェックしてRを見つけて、abortする可能性がある。これはもちろん擬陽性になる。
このあたりはパフォーマンスと偽陽性判定によるabortペナルティーとの完全なトレードオフに見える。現実的には選択実装の形にした方がよいと思う。このスタイルの利用はおそらく応用性が高い。個人的にはSSNの中ではもっとも「なるほど」と思ったところではある。とはいえ、実際どのくらいの効果があるかは、アプリケーションとより具体的なワークロードに依存する。
■ロックとphantom除去について
SSNでは階層ロックとロックエスカレーション、これに加えてキーとpredicate lockを利用した方式が親和性が高い。
- Hierarchical dependency tracking
dependency trackについては階層ロックの仕組みを利用する。
readの場合：tableの大部分を読むような場合は、R-lockをとってtableのpstampを更新する。
writeの場合：tableについてIW-lockをとり、個別レコードでW-lockをとる。v.sstampを更新するだけだが、tableとversionの両者のpstampを確認してconflictを検出する。
- Predicates and phantoms
Phantomの検出については、scanの場合はとにかくtableをみてR-lockとIW-lockがconflictしていないかどうか確認して検出する。
あとはgap-lockをSSNに利用する方法もある。この場合は、キーのレンジとgapのペアをどう処理するかによる。キーとgapのペアごとでconflictの検出に利用する。
まぁざっくりこんな感じ。あとはsimulationの話とパフォーマンスの実測の話になっている。
SSNの大枠の理解（理論とアルゴリズム）はこんな感じいいと思う。
本人も言っていたが、やはりCCの下回りの実装がポイントなることがあるようだ。どちらかというとcertifierというよりも、実装として組み込んでしっかりしたDBとしてintegrateした方が、パフォーマンスもでると思う。考え方と実装のヒントはこんな感じなので、これをどう扱って行くかが、今後のポイントになると思う。
そんな感じ。
一発go throughして簡単にわかる内容ではないので、折に触れて読み返すといいと思う。自分もそのつもり。
特に実装部分についてのParallelな処理は、今後いろいろ参考になると思う。
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に挑戦という意味では、ここまで詰めるだけでも相当なコストになるはず。そういう評価になると思う。
