目次
- 目次
- はじめに
- 前提知識
- 参考資料
- 本エントリでの表記
- Welcome back to the TRANSACTION!
- A Critique of ANSI SQL Isolation Levels再読
- A critique of ansi sql isolation levels 解説公開用
- Making Snapshot Isolation Serializable 再考
- 全IT関係者が知っておくべき「1-copy-snapshot isolation」
- Replicated Serializable Snapshot Isolation解説
- Multi-version Conflict Serializability
- SILO再考～次世代DBのアーキテクチャとして
- multi-versionの基礎
- MVTO (multi-version timestamp ordering)
- Cicada：Dependably Fast Multi-Core In-Memory Transactions
- 大規模分散OLTP 次世代DB / 分散OLTP（MVCC系）を可能な限り 全力で解説
- SQLServer 2014 “Hekaton”再考
- 今後の更新について
- 更新情報
はじめに
神林さん(@okachimachiorz1)のブログ（急がば回れ、選ぶなら近道）のトランザクションに関する記事を通読し、理解にチャレンジしました。このエントリはその過程でのメモです。
過去に何度も通読したのですが、理解できずに挫折を繰り返してきました。ですが、その間に積み上げてきた知識で少しずつ理解が進むようになりました。いずれまた読み返す際に道標となるよう、ここに記録を残します。まだ理解できなかった箇所も同様に記録を残し、いつかアップデートしたいと考えています。
なお、率直なところ、正確性には自信がありません。もし、不適切な箇所があればコメントやTwitter(@pato_taityo)等でご指摘ください。
記事を読む順番ですが、公開順に読むのが理解しやすいかと思います。このエントリの紹介順はほぼ公開順となっていますので、参考にしてください。
前提知識
トランザクションの基礎知識
トランザクションについて初めて学ぶ場合は熊崎さん(@kumagi)の以下の記事を一通り読むことを強くお勧めします。
一人トランザクション技術 Advent Calendar 2016 - Qiita
数学記号
数学記号が分からないときはWikipediaの記事を参照ください。
数学記号の表 - Wikipedia
iff
"iff"は"if and only if"の略です。
A if and only if B
if and only if - ウィクショナリー日本語版
条件 B のときに限り A が成り立つ。Aが成り立つのはそのときに限る。
Serializabilityの選択
神林さんのブログ及びスライドでは、Serialization空間が広いほど(MVSR > MCSR > VSR > CSR)、abort率が減るため望ましいとしています。
参考：Dbts 分散olt pv2
これに対し、熊崎さんの記事でFSR, VSRはそれぞれ課題があって実用的ではない、としています。
結局のところ、どのSerializabilityが望ましいのかという回答は以下が説明しています。
FSRは現在のanomalyベースの考え方では有用ではない。何を読もうが最終の状態とそれにまつわるコンテクストが保存されればよい、というsemanticsであれば意味がある。その分スケジューリングパワーもある。一般に VSR⊂FSRである。差分の例は上記の通りのinconsistency read等になる。
multi-versionの基礎 - 急がば回れ、選ぶなら近道
つまり、どのSerializabilityを選ぶかはそれによるメリットとsemantics次第ということです。これは現在の Isolation Level でも同様といえます。例えば、SERIALIZABLE ではなく REPEATABLE READ を選んだのであれば、パフォーマンスと引き換えに Phantom Read Anomay を許容するsemanticsがある、といえるでしょう。
Isolationレベルの設定は、漏れてしまうanomalyを明確に意識して手当することが主たる目的です。これもまたcorrectとアプリケーションサイドでどう担保するか？、consistencyをどう担保するか？という問題そのものです。
Welcome back to the TRANSACTION! - 急がば回れ、選ぶなら近道
predicate
指定した条件に合致するアイテムの集合に対し、read/write 等の操作を行うことです。
predicate read の定義として以下の記載があります。
We define a predicate read as an operation which identifies a set of items in
http://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/2009/Papers/p492-fekete.pdf
the database, based on the state of the database.
詳細は上記の引用元資料を参照ください。
install
On commit, a transaction's final versions are said to be installed, or written, in the database state.
http://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/2009/Papers/p492-fekete.pdf
この記述を見ると、コミットされたときにトランザクションの最終バージョンが "install" された、としているようです。
ただ、ブログ記事を読んでいると、コミットの前後を問わず、アイテムの新しいバージョンを生成した時点で "install" としているようにも読めます。
TX本(P441)の説明を読んでも確証を持ち切れずにいます。
Updates of uncommitted transactions create new versions, and the commit of a transaction moves all versions that were created by the transaction into the cached database. Similar to shadowing, pointer switching techniques may be employed on a per-object basis for "installing" the new versions, or physical copying of versions if neccessary.
いずれが正しいのかはまだ確証を持てていませんので、上記に留意してご確認ください。
参考資料
本エントリで参照する主な資料と本エントリ内での略記をまとめます。
(1) TX本
- 作者: Gerhard Weikum,Gottfried Vossen
- 出版社/メーカー: Morgan Kaufmann
- 発売日: 2001/05/24
- メディア: ハードカバー
- クリック: 2回
- この商品を含むブログ (2件) を見る
(2) Rosati資料
http://www.dis.uniroma1.it/~rosati/gd/1-concurrency.pdf
TX本は量が多すぎて読み切れないという方はこの資料から入ると読みやすいかもしれません。大学の講義用資料のようで、ポイントがわかりやすくまとめられています。
Welcome back to the TRANSACTION!
Welcome back to the TRANSACTION! - 急がば回れ、選ぶなら近道
複数のTXの全ステップをシャッフルして、一つのスケジュールをつくった場合に、各TXのcorrectnessが保証される、すなわち一貫性が保証されることが必要です。
Welcome back to the TRANSACTION! - 急がば回れ、選ぶなら近道
ここでの「シャッフル」とは同一TX内のステップ順を入れ替える、ということではなく、同一TX内のステップ順を維持しながら、他のTXとのステップ順を並べ替えるということを意味しています。
つまり、r1(x)w1(x)r2(y)w2(y)というTXがr1(x)r2(y)w1(x)w2(y)のように並べ替えることを言います。w1とr2が入れ替わりましたが、r1w1及びr2w2の順序に変わりありません。
もっとも基本的なrecoveryスケジュールであるrigorousness（通称RG）のルールを守った場合は、そのスケジュールはCOCSRであることが保証されます。（これは実はRG＝SS2PLであることも背景にはあります。）
Welcome back to the TRANSACTION! - 急がば回れ、選ぶなら近道
Serializability と recoverability は直交する概念です。詳しくは以下の資料を参照ください。
http://www.dis.uniroma1.it/~rosati/gd/1-concurrency.pdf
資料の "2.5 Recoverability of transactions" です。
rigorousness の説明については別エントリにまとめましたので、ご参照ください。
トランザクションの Strictness と Rigorousness の定義を再確認する - ぱと隊長日誌
記事には『RG＝SS2PL』とありますし、TX本にも以下の記載があります。
THEOREM 11.6
String two-phase locking (SS2PL) generates exactly the class of rigorous schedules, i.e., Gen(SS2PL) = RG.
ただ、rigorous は Recoverability の話であり、2PLはプロトコルの話なので、領域の違う内容を等しいと言って良いかは少し疑問があります。Rosati資料 P117 の図にあるように、rigorous ⊂ SS2PL とした方が妥当にも思えます。
A Critique of ANSI SQL Isolation Levels再読
A Critique of ANSI SQL Isolation Levels再読 - 急がば回れ、選ぶなら近道
記事内の元論文へのリンクが切れています。以下にあります。
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-95-51.pdf
「r-w系 Inconsistent Read (Phantom)」をAnti-Dependencyと呼ぶこともある、としています。これは後の記事でも出てくる用語なので、この定義を覚えておく必要があります。
Wikipediaの「命令レベルの並列性」の説明（命令レベルの並列性 - Wikipedia）でもAnti-Dependencyの説明が出ています。まとめると、「反依存（anti-dependency）は、命令が後で更新される値を必要とする場合を指す。命令の順番を変えたり、同時に並行して実行すると、最終的な結果が期待したものとは変わってしまう可能性があるため、逐次的にしか実行できない。」ということです。
対象が CPU or transaction と違いはありますが、意味はおおむね同じものと思われます。
この記事で"r1(x)r2(y)w1(x)w2(y)"のような表記が登場します。
rはread、wはwriteを意味しています。r/wの後の数字はTXを識別します。()内は操作の対象とする値を指しています。
つまり、"r1(x)r2(y)w1(x)w2(y)"は以下の意味です。
- TX1がxをreadする
- TX2がyをreadする
- TX1がxにwriteする
- TX2がyをwriteする
A critique of ansi sql isolation levels 解説公開用
本節の小見出しはスライドのタイトルと合わせています。
（解説）Serializeしたものと同じ「意味」ってなんですか？
この節は文字がとても見辛いですが、エルブラン・セマンティクスを説明しているようです。別記事にまとめましたので、参照ください。
エルブラン・セマンティクス(Herbrand Semantics)理解メモ - ぱと隊長日誌
ANSIの定義の曖昧性の指摘
この節ではPn/Anの比較をしています。ANSIだとcommit/abortの順番を明示していないため、Pnのように解釈可能だし、そうなると本来問題ないケースまで問題ありと判定してしまうことがあります。なので、Anのようにすべきだ、ということを主張しています。
P1の定義で考えると4パターン考えられますが、実際に Dirty read で問題になるのはNGとした2パターンです。「OK→OKではまずい」の2パターンは本来 Dirty read でないのに、そう判定されてしまうという問題があります。
P2はNon-Repetableなので、w2(x)の後にr1(x)がないと定義としておかしいと考えたのですが、論文でもスライド同様の記載でした。これは実際に2回目のreadがあったかは関係なく、commitもしくはabortの前提としていたxの値が c1 OR a1 の時点でw2によって書き換えられていたことが問題、ということなのでしょうか？これについては今後調べてみます。
P3/A3の定義などに登場するr1(P), W2(y in P)の"P"は "predicate" を意味しています。
H3:r1(P)w2(insert y to P)r2(z)w2(z)c2r1(z)c1
A critique of ansi sql isolation levels 解説公開用
たとえば、有効な従業員のリストをとって、その数をカウントするような場合、TX1で有効な従業員のリストを取得、そのあとでTX2が新規の従業員を追加してカウントを更新し、そののちTX1でカウント数を取得する場合、不整合が発生する。
この例では集合の条件であるPを「有効な従業員」としています。
2PLでserializabilityになることの証明
LEMMA 1 ではトランザクションでitem（値）の操作を2PLに則って行うためのルールを定義しています。
また、LEMMA 2 ではLEMMA 1 を前提として conflict graph を考え、それがacyclic（非循環）である→serializableである、ということを導いています。
つまり、2PLはserializabilityを保証する、ということになります。
ProofはLEMMA2の(1)-(3)に対しての証明です。分かり辛いところを説明します。
(2)は数学的帰納法で証明しています。つまり、
pu1(x) < qln+1(y)
が成り立つということは、
pu1(x) < qln(y)
も成り立つということです。
(3)は背理法で証明しています。つまり、Gが循環すると仮定して証明を進めると矛盾が導かれるため、Gが非循環である、ということになります。
TX本には以下の記載があります。
THEOREM 3.10
Let s be a history. Then
s ∈ CSR iff G(s)
is acyclic.
Gが非循環ということは 2PL が CSR であり、"well-formed two-phase locking guarantees serializability" といえます。
Making Snapshot Isolation Serializable 再考
Making Snapshot Isolation Serializable 再考 - 急がば回れ、選ぶなら近道
MVCCはTX発生時点では、そこまでにwriteされたversionを読むことが可能であって、commitの有無は理論上は直接制限されません。(SIが有名になりすぎて、MVCCと混同されている方も居ますが、MVCCはもっと広い概念です。) しかし、SIの方は明確に、「読む込む時点で直前にcommitされたversionを読む」という制限がかかります（強制）。
Making Snapshot Isolation Serializable 再考 - 急がば回れ、選ぶなら近道
このMVCCとSI(Snapshot Isolation)の違いは重要です。 「MVCCはもっと広い概念」ということを理解しておかないと、例えばPostgreSQLがMVCCなのにcommitされたversionしか読まないのはなぜ？と混乱するかもしれません。
PostgreSQLはSIを用いてMVCCを実現しています。そして、PostgreSQL 9.1 以降はSSI(Serializable Snapshot Isolation)を適用して Serializable 分離レベルを実現しています。詳細は以下の記事を参照ください。
PostgreSQL のトランザクション & MVCC & スナップショットの仕組み
R1(X0,70) R1(Y0,80) R2(X0,70) R2(Y0,80) W1(X1,-30) C1 W2(Y2,-20) C2
Making Snapshot Isolation Serializable 再考 - 急がば回れ、選ぶなら近道
Wn(Xn,mm)の意味はTXnがmmの値をXに書き込んだ、という意味です。XnはTXnが書き込んだ値、という意味であり、Xの更新順序を意味しているわけではないことに注意ください。
item-write-read dependency ＝ Tm ->(i-wr)-> Tn
Making Snapshot Isolation Serializable 再考 - 急がば回れ、選ぶなら近道
（mで値を生成し、nで読む。i-rwはitem read write dependencyの表記）
item-write-write dependency ＝ Tm ->(i-ww)->Tn
（mで値を生成し、immediate successorのnで別バージョン生成）
item-read-write dependencyまたは item-anti-dependency ＝ Tm->(i-rw)->Tn
（mで値を読んでおり、immediate successorのnで別バージョン生成）
predicte-write-read dependency ＝ Tm ->(pr-wr)-> Tn
（mで値を生成し、nのpredicate readで読む。ただし、nの開始前に、mでコミットされていること）
predicate-read-write dependencyまたは predicate-anti-dependency ＝ Tm->(pr-rw)->Tn
（mで値をpredicateで読んでおり、nで別バージョン生成。nのコミットは、mの開始後）
この表記は覚えておいた方がよいです。この後の別記事でも Ti→wr→Tj のように記載されています。この時に「iで値を生成し、jで読む。」と読めないと、内容を理解できないです。
predicate writeは存在しないので、入っていません。
Making Snapshot Isolation Serializable 再考 - 急がば回れ、選ぶなら近道
この根拠がまだ理解できていません。ただ、元論文から本件について説明していると思われる箇所がありましたので、引用しておきます。
It is important to avoid a common misconception with set-oriented operations: in our model there is no such thing as a Predicate Write operation to conflict with a Predicate Read. A SQL operation
http://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/2009/Papers/p492-fekete.pdf
UPDATE T SET T.col1 = :y WHERE T.col2 = :x;
will be modeled as a Predicate Read which returns the relevant fields, followed by a succession of item write operations which modify each returned col1 field to the new value y. The concept of a Predicate Write has not been used since the prototype System R demonstrated that estimating intersections of set-oriented update data item collections with set-oriented read data item collections led to unnecessary conflicts (as explained in Chamberlin et al. [1981], near the end of Section 3). Instead, in our model, a predicate read can conflict only with an item write which changes the state of the database in such a way as to change the list of items returned by the predicate read. For example, the WHERE clause conflicts with any write that produces a new version of some col2 field, if the new version has value x and the old version did not, or if the new version has a different value while the previous version was equal to x.
その上でサンプルとしてExample 2.1のグラフが提示されます。
Making Snapshot Isolation Serializable 再考 - 急がば回れ、選ぶなら近道
W1(X1)W1(Y1)W1(Z1)C1W3(X3)R2(X1)W2(Y2)C2R3(Y1)C3
（serializable orderはT1-T2-T3になりますね。ボールドがrw-dependencyになります）
この説明に対応する論文の箇所を引用します。
For example, recall the SI history presented in Example 2.1 (a user-oriented history):
http://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/2009/Papers/p492-fekete.pdf
H1: W1(X1)W1(Y1)W1(Z1)C1W3(X3)R2(X1)W2(Y2)C2R3(Y1)C3.
We note W3(X3) precedes R2(X1), implying this is a multiversion history. But here is the scheduler-oriented equivalent:
H1': W1(X1)W1(Y1)W1(Z1)C1R3(Y1)R2(X1)W2(Y2)C2W3(X3)C3.
In the history H1', W3(X3) takes place after R2(X1), and indeed the entire SI history requires only a single value of any data item at any time. Note that the reads of T3 take place prior to the reads of T2 in H1' and the writes of T3 take place after the writes of T2; thus, the two transactions are concurrent, but there is no conflict so this is fine.
H1'はMVSRで serializable order は T1-T2-T3 です。この順で考えるとボールドの部分は R2(X1)W3(X3) となります。ここから W3(X3)R2(X1) が rw-dependency になるということが分かります。
serializable order をこう考えることもできます。W3(X3) の後に R2(X1) がくるということは、serializable order が T2-T3 でないと R2(X1) を説明できません。もし、T3-T2 とすれば、R2(X3) となっていたからです。
記事では論文の引用としてRemarks, Lemma, Theorem, Proofといった用語が出てきます。これらの意味は以下の資料を参照ください。
https://www.math.nagoya-u.ac.jp/~namikawa/download/LA06s-01.pdf
| 用語 | 意味 |
|---|---|
| Remark | 注意（補充説明） |
| Lemma | 補題（補助の命題） |
| Theorem | 定理 |
| Proof | 証明 |
なので、RemarkとLemmaを前提に置いたうえで、TheoremをProofで証明する、という構成になっています。
それらの循環の中には、三つの連続するTransactionが存在する
Making Snapshot Isolation Serializable 再考 - 急がば回れ、選ぶなら近道
- ただし三つのうち最初のものと最後のもの同一でもよい
というのは定理をTX1, TX2, TX3というTransactionで定義するけれど、TX1 = TX3、つまりTX1(TX3), TX2という２つのTransactionでもこの定理は適用できるよ、と言っています。その具体例を Write Skew の例として挙げられています。
全IT関係者が知っておくべき「1-copy-snapshot isolation」
全IT関係者が知っておくべき「1-copy-snapshot isolation」 - 急がば回れ、選ぶなら近道
eager / lazy という用語が出てきますが、以下を参考にすればよいと思われます。
1つ目はeager（同期性）レプリケーションで、これは、全てのレプリカに対して入ってきた変更をコミットがクライアントに戻される前に同時に伝播するものです。2つ目のlazy（非同期性）レプリケーションは、レプリカを受け取った時だけ非同期的に変更を行い、受け渡すものです。
NoSQLデータベース：調査と決定のガイダンス（その2） | POSTD
primary-backup / update-anywhere / ROWA については、調べるためのキーワードが以下のスライドに登場しています。
某石割り先生のように「No ACID is No Interest」と言い切るのアレすぎるとは思いますが、似たような人は多いかと。
全IT関係者が知っておくべき「1-copy-snapshot isolation」 - 急がば回れ、選ぶなら近道
「某石割り先生」とはマイケル・ストーンブレーカー(Michael Stonebraker)のことです。
マイケル・ストーンブレーカー - Wikipedia
正確には「No ACID is No Interest」ではなく「No ACID Equals No Interest」のようです。
Why Enterprises Are Uninterested in Nosql | blog@CACM | Communications of the ACM
Replicated Serializable Snapshot Isolation解説
Replicated Serializable Snapshot Isolation解説 - 急がば回れ、選ぶなら近道
記事内の元論文へのリンクが切れています。以下にあります。
http://www.vldb.org/pvldb/vol4/p783-jung.pdf
単純にAnti-dependencyのあるTXの情報を持ち回ってチェックすればいいのですが、特にReadSetの持ち回りは対象がまるまるテーブル一つになったりすると、相当やばいことになります。
Replicated Serializable Snapshot Isolation解説 - 急がば回れ、選ぶなら近道
Anti-dependencyはr-wなので、判定にはReadSetが必要となります。ただ、大きいテーブル全体を読み込んだような場合、当然ReadSetも大きくなり、それを他のノードに送信して（もしくは受信して）判定せねばならず、現実的ではないということを説明しているようです。
また、これはReadSetと比較してWriteSetが小さいという暗黙の前提を置いていることが次の説明から読み取れます。
したがって、暗黙のうちに、細かいWriteがバラバラ来るという処理が多いというドメインを前提にしています。全データの一斉更新とかはさすがに無理ですね。
Replicated Serializable Snapshot Isolation解説 - 急がば回れ、選ぶなら近道
記事では ws / rs という略語が出てきますが、Write Set と Read Set の略となります。
Algorithm1 の疑似コードについての解説を理解することができませんでした。今後の宿題として残します。
Multi-version Conflict Serializability
Multi-version Conflict Serializability - 急がば回れ、選ぶなら近道
RDMA は Remote Direct Memory Access のことです。
Remote Direct Memory Access - Wikipedia
この記事で「順序は全順序が前提」としています。全順序の定義は以下を参照ください。
全てのトランザクションはある全順序(total order)による逐次的な実行として現れる。これはトランザクションは他トランザクションから分離実行されることを意味する；すなわち、トランザクションにおける各個の操作は別トランザクションにおける各個の操作とインターリーブされて現れない。
（翻訳）C++トランザクシショナル言語構成要素のドラフト仕様 V1.1 ［§1-2のみ］ - yohhoyの日記
MVSGのグラフのエッジは以下の条件により作成される
あるxについて、wj(xj), rk(xj), wi(xi)を想定した場合、まずrk(xj)があるので、
- tj->tkの依存エッジが必ず存在する。
- xi->xjのversion orderの場合
wi(xi)->wj(xj)が存在し、よってti->tjのエッジが存在する
Multi-version Conflict Serializability - 急がば回れ、選ぶなら近道
または
xj->xiのversion orderの場合、
wj(xj)->wi(xi)となり、そもそもwj(xj)->rk(xj)であるので、xj->xiならば、必ずrk(xj)->wi(xi)になる。
よってtk->tiのエッジが存在する。
この説明の一部をもう少しかみ砕いて説明します。
"rk(xj)"はTXjの書いたxの値をTXkがreadする、ということです。つまり、TXj->TXkの順ということであり、「tj->tkの依存エッジが必ず存在する」ということになります。
「wj(xj)->wi(xi)となり、そもそもwj(xj)->rk(xj)であるので、xj->xiならば」それはwj(xj)->rk(xj)->wi(xi)ということであり、「tk->tiのエッジが存在する」ということになります。
なお、自明のことではあるのですが、「xi->xjのversion orderの場合」と「xj->xiのversion orderの場合」が同時に成り立つわけではありません。どちらかです。つまり、この説明ではtj->tk->ti->tjでgraphが循環しているケースを挙げているわけではありません。
「4. MCSRの定式化」の直感的な説明をまだ理解できていません。
例えば、
2.wj(xj)-rk(xj)がなぜ依存関係ではないか？
Multi-version Conflict Serializability - 急がば回れ、選ぶなら近道
仮にrとwを交換しようがしまいが、version orderには影響がない。
とありますが、"rk(xj)-wj(xj)"は成り立ちませんし、rとwの交換が何を意味しているのか分かりませんでした。ネットで情報を探しても見つからず、ここはTx本を読まないとダメかもしれません。
「5. SIの定式化」で"wh(x)"とありますが、これはTXhのwriteの意味です。添字がi, jときて次はkになると思いきや、でした。
SIはMVSRよりもwrite-setの交差を制限するという意味でより制限的である一方で、MSVRで要求されるread-fromの要件、すなわち該当するserialな単一versionでのスケジュールでのread-from（w-rのconflict）との互換性は、要求されない。この点でMVSRよりも制限的ではない。
Multi-version Conflict Serializability - 急がば回れ、選ぶなら近道
MVSRではserialな単一versionのスケジュールでcommitの有無に関わらず、直前のwriteを見ることを要求されます。ですが、SIは「各readに対するversionの割当は当該readのTxが開始される時点で、最も最近にコミットされたwriteのものを割り当てる」つまりSnapshotのversionを読むことができます。これが「MVSRよりも制限的ではない」の意味です。
最後の節に出てくる「オンサイト」「フラッシュ」はクライミング用語です。
オンサイト onsight 初見。または初見で（テンション、フォールなしに）完登すること。
最新クライミング用語集 | 山と溪谷社のクライミング・ボルダリング総合サイト CLIMBING-net クライミングネット
フラッシング flashing 本来は（オンサイトも含めた）1 回目のトライで完登すること。のちにオンサイトの概念が確立され、区別するために「他人の登りを見たあと、初めてのトライで完登すること」を指すようになった。
SILO再考～次世代DBのアーキテクチャとして
SILO再考〜次世代DBのアーキテクチャとして - 急がば回れ、選ぶなら近道
この記事はSILOの論文を片手に読まないと理解が進みません。記事冒頭に論文へのリンクがありますので、ぜひ一緒に読み進めてください。
TXのcommit可能確定後にtx-IDは割り当てられます。このため、「t1:read(x)→t2:write(x)のanti-dependencyの場合、t1<t2 t2<t1 の両方のID順序が発生する。」ことになります。つまり、t1<t2であればt1が先にcommit可能確定したということであり、t2<t1であればその逆となります。
t2<t1のとき、障害復旧時にログからorderに沿って正しく戻せるのか？と疑問に感じたのですが、REDOログに書き込むのは更新情報のみなので、t2のwriteのみがログとして残り、t1のreadはログとして残りません。よって、anti-dependencyにおけるtx-IDの順は問題にならないということだと理解しました。ただし、w-wはorderを考慮する必要があるため、「普通にt1:write(x)→t2:read(x)でserial orderが t1→t2ならTx-IDも t1→t2が必要」ということになります。
「epochまたぎは順序保証が必須」というのはepochがグループコミットの「単位」として機能していることと絡んでいると思うのですが、理解しきれていないので、今後整理してupdateしたいと考えています。
2.one-shot requests
SILO再考〜次世代DBのアーキテクチャとして - 急がば回れ、選ぶなら近道
処理のwindowがあるということを意味する。すなわち、clientまで「常に状態を返し続ける」ということではない。serialization pointが存在できる可能性の一つの前提を提供している（overlapが永遠に続くわけではない）
論文では one-shot requests について以下の説明をしています。
- リクエスト開始～終了まで、呼び出し元とはやり取りしない。
- このモデルはOLTPワークロードに適している。
- トランザクションの一部で通信遅延が発生すると、同時更新によるアボートの可能性が高くなるが、この方式であればその可能性を低減できる。
- 任意のアプリケーションロジックを含んだ、１つもしくは複数のシリアライズ可能なトランザクションで構成される。
記事で出てくるwindowとは（論文ではこの表現を使っていません）、「リクエスト開始～終了まで、呼び出し元とはやり取りしない」この期間のことを指しています。
もし、トランザクションがクライアントからのcommit/rollbackで終わるとするならば、これを言い換えるとcommit/rollbackなしにトランザクションは終わりません。すると、TXiとTXjがoverlapしたとき、いずれかがcommit/rollbackしないままになると、serialize するためのスケジュールを決定できません。one-shot requests であればリクエスト1回でトランザクションが完結するため、リクエストが有限の時間で処理を終えれば、overlapが永遠に続くわけではないといえます。これが"処理のwindowがある"ということです。
論文のFigure1では"Transaction Logic"として以下の例を記載しています。
T = FIND(A.x, >10) foreach t in T: UPDATE(t.x, 10)http://people.csail.mit.edu/stephentu/papers/silo.pdf
この例を見る限り、単なるSQLというよりはPL/SQLやPL/pgSQLのような手続き言語に近い印象を受けます。この表現力があれば、トランザクション中にクライアントとやり取りできないという制限も受け入れられそうです。
3.MassTreeを利用
SILO再考〜次世代DBのアーキテクチャとして - 急がば回れ、選ぶなら近道
PKのindex treeで基本はB+。ただし、secondary keyは別treeになっている。したがって、secondary keyを利用する場合はtree traverseが二回になる。
論文のFigure 1から察するに、クラスタインデックスの構造に見えます。「secondary keyを利用する場合はtree traverseが二回になる」ことの説明含め、以下の解説記事が参考になります。
漢(オトコ)のコンピュータ道: 知って得するInnoDBセカンダリインデックス活用術！
Next-Key locking で phantom read を防ぐ方法については、以下の解説スライドを参照ください。
http://dbstudy.info/files/20140907/mysql_lock_r2.pdf
"4.8 Garbage collection"で"RCU"という用語が出てきますが、これは Read Copy Update と呼ばれる同期機構のことです。大まかなイメージを知るには以下の記事を参照ください。
RCU(Read Copy Update)をちゃんと知る（1）-1 ほんとの概要 - tkokamoの日記
"4.9 Snapshot transactions"をまだよく理解できていません。
あとはalignの方法の問題。snap(e) = k・floor(e/k)で、k=25 で eのインターバルが40mなんで snapshotは1sec
SILO再考〜次世代DBのアーキテクチャとして - 急がば回れ、選ぶなら近道
とあるのですが、これが何を意味しているのか、論文の該当箇所を読んでも理解できませんでした。これは今後の課題とします。
multi-versionの基礎
multi-versionの基礎 - 急がば回れ、選ぶなら近道
"In-Place"とは、トランザクションがページを書き戻す際、ページを読んだ場所にそのまま上書きすることを指します。single-versionであれば以前の値を残す必要がないため、In-Placeに更新することができます。対して、MVCCは過去のバージョンを参照する可能性のあるトランザクションがなくなるまでは上書きできないため、In-Placeにできません。
参考：ARIES
記事だとmultiversionの定義がやや見辛いですが、オリジナルは"Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)"にあるようです。
ほぼオリジナルの表記に近いmultiversionの定義を以下の資料で見ることができます。6ページ目です。
http://www.inf.uni-konstanz.de/dbis/teaching/ss09/tx/Sebastian.pdf
single-versionとmono-versionの違いについて。同じ意味かと思ったのですが、記事内でも混在していることがあり、使い分けがあるような…？
ただ、定義の違いを記事内では説明しておらず、ネットで探しても説明した資料は見つかりませんでした。そこで、記事から推測するに、single-versionは値が対象で、mono-versionはスケジュールが対象という違いがあるのかもしれません。
例えば、以前の記事ではmono-versionについて以下の説明をしています。
mono-versionとは単一のバージョンによるmulti-versionのスケジュールをさす。
Multi-version Conflict Serializability - 急がば回れ、選ぶなら近道
この定義に従えば、mono-versionはmulti-versionの特殊なスケジュールといえます。
これに対して、single-versionは値に単一のバージョンしかないことを意味しているように思われます。例えば、あるスライドではsingle-versionとmulti-versionの違いを以下の例で説明しています。
s = r1(x)w1(x)r2(x)w2(y)r1(y)w1(z)c1c2：single-version
Dbts 分散olt pv2
s = r1(x0)w1(x1)r2(x1)w2(y2)r1(y2)w1(z0)c1c2：multi-version
single-versionとmono-versionが同一なのか異なるものなのか、はっきりした際にはアップデートします。
r1(x)r2(x)w1(x)w2(x)c1c2→これはFSRではない。w0(x)r2(x)w2(x)がaliveなusefulRF（以下LRF）
multi-versionの基礎 - 急がば回れ、選ぶなら近道
t1t2 r1(x)w1(x)r2(x)w2(x)c1c2 w0(x)r1(x)w1(x)r2(x)w2(x)のLRF
t2t1 r2(x)w2(x)r1(x)w1(x)c2c1 w0(x)r2(x)w2(x)r1(x)w1(x)のLRF
どれとも一致しないので、FSRにはならない。
少し見辛いですが、１行目のスケジュールがFSRでないことをserialなhistory(t1t2, t2t1)のRFと比較して確認しています。下表に整理しなおします。
| TX順 | スケジュール | LRF |
|---|---|---|
| オリジナル | r1(x)r2(x)w1(x)w2(x)c1c2 | w0(x)r2(x)w2(x) |
| t1t2 | r1(x)w1(x)r2(x)w2(x)c1c2 | w0(x)r1(x)w1(x)r2(x)w2(x) |
| t2t1 | r2(x)w2(x)r1(x)w1(x)c2c1 | w0(x)r2(x)w2(x)r1(x)w1(x) |
オリジナルとt1t2, t2t1のLRFを比較すると一致しないことから、FSRでないといえます。
個別にlock制御をアプリ側で行う（実際は2PL）
multi-versionの基礎 - 急がば回れ、選ぶなら近道
「実際は2PL」というのは FOR UPDATE でレコードをロックし、トランザクションの完了後にロックを手放す、ということです。これはS2PLの定義を満たしています。
参考：Two Phase Lock
ここでも証明を理解しきれなかったので、後日再挑戦します。
MVTO (multi-version timestamp ordering)
MVTO (multi-version timestamp ordering) - 急がば回れ、選ぶなら近道
"stale record"は"stale"（新鮮でない、古くさい）であり、"steal"（盗む、こっそり取る）ではないことにご注意ください。
MVTOの実装プロトコルの説明で『「readするときは必ず最新のversionを読んでいる」ということ「だけ」が保証されていれば良い』とあります。
この説明だけを見ると、read処理さえこの条件を守ればよいと見えますが、実際にはwrite処理も条件があります。それが、『書く方は「readするときは必ず最新のversionを読んでいる」と言う不変条件を満たさないときはabortし、それ以外には何も考えずに書き込める。』です。
つまり、readの不変条件を満たすためにwriteも条件が課せられる、ということです。
Cicada：Dependably Fast Multi-Core In-Memory Transactions
Cicada：Dependably Fast Multi-Core In-Memory Transactions - 急がば回れ、選ぶなら近道
1VCCは"single-version concurrency control"の略です。
(2) Temporary clock boosting provides short-term correction.
https://www.cs.cmu.edu/~hl/papers/cicada-sigmod2017.pdf
When an abort occurs due to a conflict, Cicada sets the clock boost to a fixed quantity that is larger than the possible residual skew after one-sided synchronization (1 µs in our implementation). The boost is reset to zero upon a commit.
論文で競合によってabortした場合はクロックブーストするとしています。
これは私の推測となりますが、スレッド間でtsの乖離が大きくなったために競合が発生したと仮定し、クロックブーストでそのスパンを狭めようとしているように見えます。
"external consistency"の定義は以下を参照ください。
あるトランザクションが終わった後に始まったトランザクションは、前に終わったトランザクションより必ず大きいタイムスタンプを得る、という言葉に直すと何を当然の事をと言いたくなるような一貫性保証の事をExternal Consistencyと呼ぶ。
Spanner
external consistencyについてはmin_wtsがコミット済みのtsよりも大きくならないと（注：コミットされているものが先のtsを持つことを保証する。）アプリ側にコミット成功を通知しないことで対応している。
Cicada：Dependably Fast Multi-Core In-Memory Transactions - 急がば回れ、選ぶなら近道
- スレッドのwtsはスレッドが持っている現在時刻(ts)です。
- min_wtsは「全てのスレッドのwtsの最小値」です。
- 「read-writeのtxはthread.wtsをtsとして利用」します。
この3つの定義を踏まえて考えると、min_wtsがコミット済みのtsよりも大きくなるということは、それ以降に開始するread-writeのTXのtsはコミット済みのtsよりも必ず大きくなります。これは先に挙げた"external consistency"の定義を満たすといえ、対応しているといえます。
この定義からは"(min_wts-1)=thread.rts=tx.ts"となります。
となると、read only TXのtsはコミット成功した最後のTXと同じtsとなり得るということであり、"external consistency"の定義を満たせていませんが、read onlyなので問題になりません。
OCSRは以前の記事で解説しています。定義を抜粋します。
TXの順序実行が保証されるという制限をつけたCSRのサブクラスをOrder-Preserving Conflict Serializablityと言います。通称 OCSR。
Welcome back to the TRANSACTION! - 急がば回れ、選ぶなら近道
causal consistency（因果一貫性）については以下の引用及び引用元資料をご参照ください。
causal consistency（因果一貫性）
http://www-higashi.ist.osaka-u.ac.jp/~nakata/mobile-cp/chap-06j-1.pdf
- 因果関係があるwrite操作群の順序は、各プロセスで同じ順で観測される
- 因果関係があるwriteの例
- プロセスP1がxに値aをwrite
- プロセスP2はxをreadし、読み込んだ値aから計算をした結果bをyに書き込む
- → W1(x)aとW2(y)bは因果関係にある
(注：v.wts<tx.ts<v.rtsでabort。普通にMVTO)
Cicada：Dependably Fast Multi-Core In-Memory Transactions - 急がば回れ、選ぶなら近道
この記述は以前の記事の以下の記述に対応しています。
2. write step (wi(x))は以下の順で処理
MVTO (multi-version timestamp ordering) - 急がば回れ、選ぶなら近道
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
RMWは論文中で"read-modify-write"の略としています。この意味ですが、一般的には以下の説明をなされることが多いようです。
この++countのような操作を、リード・モディファイ・ライト（read-modify-write，読んで・変更して・書き戻す）操作と言います。それは、結果のステートが前のステートに基づいて得られる操作です。
引用：Java並行処理プログラミング ―その「基盤」と「最新API」を究める―
ただ、この記事での用語の使い方からすると、あまり適当ではない気がするので、より適切な意味を探してみます。
記事の以下の章については理解できなかったので、今後論文から読み直す予定です。
- Serializable Multi-Version Validation
- Optimizations for Efficient Validation
証明の理解については今後の課題として残します。
大規模分散OLTP 次世代DB / 分散OLTP（MVCC系）を可能な限り 全力で解説
ここまでの記事の内容を補足しながらまとめたスライドです。
本スライドに関連して、以前に書いた記事を紹介します。
DBTS2017「次世代DB / 分散OLTP（MVCC系）を可能な限り全力で解説」聴講メモ - ぱと隊長日誌
第一段階終了：多段ロケット方式
この証明は以前の記事でも取り上げられていました。
MVTO (multi-version timestamp ordering) - 急がば回れ、選ぶなら近道
ただ、こちらのスライドのほうが若干読みやすく感じましたので、こちらにメモを記載します。
rk(xj), wi(xi)があるということは、wj(xj)もあります。
また、値はxi, xjしか現れないため、この2つの version order で証明を進めています。
In case(2)でProperty3のi=kを考慮しないのは、冒頭で"i, j and k are distinct"としているからです。
この証明に関してわからなかったことを以下(a-c)に挙げます。
(a)
「最初のケースは前提(Property2,1)からありえないので、(2)のケースのみ成立。」とありますが、なぜあり得ないといえるのか？ということ（導き方）が分かりませんでした。
(b)
MVSGが非循環であることの証明に"rk(xj), wi(xi)"のケースだけを考える理由が分かりませんでした。他にもw/rの組み合わせパターンはあるのに、なぜこのケースだけでよいのか？
この理由として、以下の仮説を立ててみました。MVTOは Property 1-4 のいずれもが成り立ちます。そのうちの一つである Property 3 を前提として（かつ値もその中で現れるものだけに仮定して）証明すれば、MVTOのMVSGは非循環といえる、ということではないのか？ただ、この仮説に対する根拠を提示できません。また、今回調査した本や資料から、冒頭のケースのみを考慮する理由を説明するものは見つけられませんでした。
(c)
「(2)のケースのみ成立」ということから「トポロジカルソート可能。というかMVSGは非循環」と導ける理由が分かりませんでした。
SQLServer 2014 “Hekaton”再考
SQLServer 2014 “Hekaton”再考 - 急がば回れ、選ぶなら近道
ここまでの記事を理解していれば、シンプルで読みやすい記事です。よって、補足はほぼありません。
"blind write"は値をreadせずにwriteすることです。
参考：Blind write - Wikipedia
今後の更新について
現在までの記事は一通り書き上げましたが、今後新たに公開されれば追加していきたいと考えています。
今後の更新では本エントリを分割するかもしれません。キーワードを検索しやすいようにと、あえて1エントリにまとめていたのですが、想定よりも長くなって読み辛くなってしまったためです。
私の理解が足りず、課題となっている箇所は今後調べていきます。
特に証明を理解できていないケースが多いです。これには論理学を理解できていないことに一因があると考え、以下の本で勉強してから再度取り組んでいるのですが、なかなか理解が進みませんでした。
- 作者: 金子洋之
- 出版社/メーカー: 産業図書
- 発売日: 1994/10/01
- メディア: 単行本
- 購入: 2人 クリック: 22回
- この商品を含むブログ (7件) を見る
更新情報
2017/10/08
前提知識
章を追加しました。
全IT関係者が知っておくべき「1-copy-snapshot isolation」
マイケル・ストーンブレーカーについての説明を追加しました。
Multi-version Conflict Serializability
説明を新規作成しました。
説明を新規作成しました。
2017/10/14
前提知識
なぜSerialization空間を広くしたいのかについて解説を追加しました。
multi-versionの基礎
説明を新規作成しました
MVTO (multi-version timestamp ordering)
説明を新規作成しました
Cicada：Dependably Fast Multi-Core In-Memory Transactions
説明を新規作成しました
大規模分散OLTP 次世代DB / 分散OLTP（MVCC系）を可能な限り 全力で解説
説明を新規作成しました
SQLServer 2014 “Hekaton”再考
説明を新規作成しました
今後の更新について
章を追加しました。
2017/10/22
前提知識
「Serializabilityの選択」に補足を追加しました。
MVTO (multi-version timestamp ordering)
実装プロトコルの説明補足を追加しました。
2017/10/29
A critique of ansi sql isolation levels 解説公開用
「2PLでserializabilityになることの証明」を追加しました。
その他
説明に影響しない文章の修正を行いました。
2017/11/04
前提知識
"iff"について追記しました。
「処理のwindow」について、説明を見直しました。
@arumumu さんからご指摘をいただきました。ご指摘の内容は以下で見ることができます。ありがとうございました！
https://twitter.com/arumumu/status/925309846286561280
https://twitter.com/arumumu/status/925310987665682432
大規模分散OLTP 次世代DB / 分散OLTP（MVCC系）を可能な限り 全力で解説
証明についてメモを追加しました。
今後の更新について
現状を踏まえて更新しました。
更新情報
更新情報の見出し設定によって目次が見辛くなってしまったため、スタイルを見直しました。
2018/08/19
前提知識
"predicate", "install" について追記しました。
参考資料
章を追加しました。
Welcome back to the TRANSACTION!
rigorousness について追記しました。
A Critique of ANSI SQL Isolation Levels再読
predicate に関する説明が誤っていたため、削除しました。
A critique of ansi sql isolation levels 解説公開用
predicate に関する説明を見直しました。
「2PLでserializabilityになることの証明」の説明を見直しました。
Making Snapshot Isolation Serializable 再考
predicate write が存在しない、という記述に関して補足を追記しました。
