ぱと隊長日誌

ブログ運用もエンジニアとしての生き方も模索中

PostgreSQLマニュアルの「リピータブルリード分離レベル」における「制御レコード」とはなにか?

PostgreSQL(9.1以降)マニュアルの「13.2.2. リピータブルリード分離レベル」に以下の記述があります。

リピータブルリードモードでは、全てのトランザクションがデータベースの一貫した不変のビューの状態を参照することが保証されます。 しかし、このビューは常にいくつかの同じレベルの同時実行トランザクションの直列(一度に一つずつの)実行と一貫性を持つとは限りません。 例えば、このレベルの読み取りのみのトランザクションは、バッチが完了したことを示すために更新された制御レコードを参照することができますが、 制御レコードのより以前のバージョンを読み取るため、論理的にそのバッチの一部となる詳細なレコードの1つを参照することはできません。 この分離レベルで実行するトランザクションによりビジネスルールを強制しようとすることは、競合するトランザクションをブロックするために注意深く明示的なロックを持たないと、正確に動作しないことが多くあります。

13.2. トランザクションの分離

説明に「制御レコード」とありますが、その意味をこの記述から理解することは困難です。実際、PostgreSQLのMLにも同様の質問が寄せられており、その回答を以下のリンクで見ることができます。
Re: Confused by example in 13.2.2

回答ではドキュメントを理解するため、PostgreSQLWikiを紹介しています。
SSI - PostgreSQL wiki

この例では銀行の小切手処理を例に挙げています。ここではcontrolテーブルのdeposit_no列で処理対象のバッチ(小切手の集合)を制御しています。例えば、4/1に受領した小切手はdeposit_noは1、4/2なら2、といった具合です。受領した小切手の詳細はこのdeposit_noの値と共にreceiptテーブルに格納します。

Wikiの記載をベースに問題となるケースを説明します。

  1. 4/1の営業終了時刻間際に銀行の担当者が小切手の処理を行いました。トランザクションT1にてdeposit_no=1で小切手の情報をreceiptテーブルにinsertします。ですが、処理が遅れたため、この時点ではまだcommitしていません。
  2. 銀行の上役が営業終了時刻ちょうどに小切手の締め処理を行いました。これにより、トランザクションT2でdeposit_noは1→2へインクリメントされました。
  3. 小切手の締め処理が行われたことで、後続の小切手一覧出力処理が行われます。トランザクションT3でdeposit_no=1の小切手一覧を出力しますが、T1はcommitしていないため、この一覧に含まれません。
  4. ようやくT1がcommitされました。

本来期待していたトランザクションの依存関係はT1→T2→T3でした。ですが、T1のcommit前にT2, T3が行われたことで、T3→T1の依存が生まれました(この順でなければT3にT1の結果が含まれないことを説明できない)。となると、T1→T2→T3→T1という矛盾した依存が発生します。
また、一見すると奇妙なことですが、T1のcommit前にT3の Read Only なトランザクションが発生しなければ、上記の矛盾は生じません。この場合、期待していた結果通りとなります。

これは"Read Only Anomaly"と呼ばれているものです。以下の解説記事が分かりやすいです。
いろんなAnomaly - Qiita

冒頭のPostgreSQLマニュアルで「制御レコード」とはWikiの例でいえばcontrolテーブルのレコードであり、「詳細なレコード」とはreceiptテーブルのレコードのことになります。

NTTDATATC2017「本当は恐ろしい分散システムの話」聴講メモ

前書き

NTTデータ テクノロジーカンファレンス 2017 (NTTデータ テクノロジーカンファレンス2017 デジタルトランスフォーメーション成功のカギ~ Hadoop, Spark, ブロックチェーン | NTTデータのHadoopソリューション)
【テクノロジー】本当は恐ろしい分散システムの話
の聴講メモです。

スピーカーはNTT ソフトウェアイノベーションセンタの熊崎さん(@)です。

メモは口頭説明を中心にまとめています。私の理解不足でメモの内容に間違いが混入しないよう確認を行いましたが、おかしな箇所がありましたらご指摘ください。
念のため、Twitterのつぶやきを参考にした内容チェックも行いました。
#NTTDATATC since:2017-10-30 until:2017-10-31 - Twitter Search

【参考】としている個所は私が挿入しています(補足や参考資料など)。登壇者の講演内容ではありませんので、その旨ご了承ください。

聴講メモ

BIG DATA LANDSCAPE 2017

このような資料は「カオスマップ」と呼ばれている。

【参考】

スライド内に記載の引用元リンクはこちらです。
http://mattturck.com/bigdata2017/

壊れにくいハードウェアを使えば良いのか?

壊れにくいハードウェアを使っていても、台数が多ければ壊れる。

CAP定理

CAPは定理と言い切っているが、証明できていないのはいかがなものか。

【参考】

2002年にMITのSeth Gilbertとナンシー・リンチがブリュワーの予想の厳密な証明を提出し、定理として確立した。

CAP定理 - Wikipedia

とあり、CAP定理は証明されているようです。

ここで熊崎さんが述べたかったのは、「"3つのうち2つ"という公式はミスリーディング」ということだったと思われます。
詳細は以下の記事を参照ください。
12年後のCAP定理: "法則"はどのように変わったか

Jepsen Test

【参考】

テストの名前の由来について熊崎さんの解説があったのですが、ほとんどメモできなかったので調べてみました。

スライドの画像の引用元リンクです。
Jepsen: On the perils of network partitions
この画像は Carly Rae Jepsen の "Call Me Maybe" のPV映像に歌詞をもじって重ねています。

テストの名前はこの歌手の名前から付けたようです。

なお、この曲のPVをYouTubeで見ることができます。きっと一度は耳にしたことがあるはず。

Partitionさせてみる

この実験の結果より、Redisはパーティションで作った分断に弱いということが言える。

ここまでのまとめ

異常系のテストは難しいし、正しく網羅的にできていないことが多い。

Fault Injection Testとは?

システムは複数のレイヤーで構成されている。そのレイヤーを攻撃するのが Jepsen Test だ。

HDDもSDDも壊れる!

ニアラインディスクはデータのバックアップ用。

【参考】
ニアラインディスクの詳細は以下の記事を参照ください。
ニアラインディスクの利用用途は | Tintri

実験設定

ディスク内のデータが少し化けただけでダメージを受けるシステムは多い。

「一度に化ける/壊れるエラーは一か所だけ」とは3多重であればその内の1つだけが壊れるということ。これをRedisでテストしてみた。

他のシステムたち

Cassandra は last-write-win で最後に書いたものが勝つ、という障害対応を行っている。だが、最後に書いたデータが化けていると悲惨なことになる(化けデータが伝搬する)。

その猿、凶暴につき

Netflixは障害系のテストのために本番で障害を起こす。

Chaos Kong はAWSのリージョンを丸ごと落とす。この場合は何日に実施するかを予告されている。避難訓練のようなもの。

NetflixのChaos Engineering

部署のレベルでフォールバックの仕組みを作っている。

カナリア分析のメトリクスの例としてはCPUやメモリなどがある。

サルと和解せよ

Chaos Engineeringの導入には、まず何が正しいかを定義し、段階を追って準備を進める。

所感

以下のtweetにまとめました。

このような素晴らしい資料を公開していただけたことに感謝いたします。

急がば回れ、選ぶなら近道 TX記事 読解メモ

はじめに

神林さん(@)のブログ(急がば回れ、選ぶなら近道)のトランザクションに関する記事を通読し、理解にチャレンジしました。このエントリはその過程でのメモです。

過去に何度も通読したのですが、理解できずに挫折を繰り返してきました。ですが、その間に積み上げてきた知識で少しずつ理解が進むようになりました。いずれまた読み返す際に道標となるよう、ここに記録を残します。まだ理解できなかった箇所も同様に記録を残し、いつかアップデートしたいと考えています。

なお、率直なところ、正確性には自信がありません。もし、不適切な箇所があればコメントやTwitter(@)等でご指摘ください。

記事を読む順番ですが、公開順に読むのが理解しやすいかと思います。このエントリの紹介順はほぼ公開順となっていますので、参考にしてください。

前提知識

トランザクションの基礎知識

トランザクションについて初めて学ぶ場合は熊崎さん(@)の以下の記事を一通り読むことを強くお勧めします。
一人トランザクション技術 Advent Calendar 2016 - Qiita

数学記号

数学記号が分からないときはWikipediaの記事を参照ください。
数学記号の表 - Wikipedia

iff

"iff"は"if and only if"の略です。

A if and only if B
条件 B のときに限り A が成り立つ。Aが成り立つのはそのときに限る。

if and only if - ウィクショナリー日本語版

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! - 急がば回れ、選ぶなら近道

本エントリでの表記

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の順序に変わりありません。

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)"は以下の意味です。

  1. TX1がxをreadする
  2. TX2がyをreadする
  3. TX1がxにwriteする
  4. TX2がyをwriteする

この記事には"predicate"という用語が出てきます。例えば、次のように使われています。

尚、snapshotは値(というかpredicateで取ってくるので値とは限らない)を一回コピーしてしまうので、当該transactionの利用データセットをisolateするという原理ですね。

A Critique of ANSI SQL Isolation Levels再読 - 急がば回れ、選ぶなら近道

この"predicate"は「述語」を意味しています。述語(predicate)については以下の記事を参照ください。
SQLの中の述語論理
参照記事ではこうも述べています。

変数には数しか代入できませんが、変項には数以外の要素も代入できるので、変"数"ではなく変"項"という言葉が使われています。

SQLの中の述語論理

これは「値とは限らない」ということと対応しているように思えます。私がまだ理解しきれていないため、あいまいな説明となりましたが、今後の調査のために残しておきます。

A critique of ansi sql isolation levels 解説公開用

本節の小見出しはスライドのタイトルと合わせています。

(解説)Serializeしたものと同じ「意味」ってなんですか?

この節はフォントの問題なのか、すごく見辛いです。時間があるときに同等の説明をしている本や記事を探したいと考えています。

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"を意味しているようです。
ここでの"predicate"の意味ですが、後のスライドで参考になりそうな説明がありました。

H3:r1(P)w2(insert y to P)r2(z)w2(z)c2r1(z)c1
たとえば、有効な従業員のリストをとって、その数をカウントするような場合、TX1で有効な従業員のリストを取得、そのあとでTX2が新規の従業員を追加してカウントを更新し、そののちTX1でカウント数を取得する場合、不整合が発生する。

A critique of ansi sql isolation levels 解説公開用

この説明を読むと、この例でPは「有効な従業員」を意味しているようです。つまり、predicate(述語)は集合の条件(WHERE句)を意味しているように思えます。

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)
も成り立つということです。

(2)では item x, y しか仮定していませんが、証明では item z を仮定しています。item z を仮定して証明することの妥当な理由を確証もって説明できないのですが、証明の過程でこそ item z を利用しても、最後の結論では item z が消えています。つまり、item z は結論に影響しないため仮定してもよい、ということのように思えます。仮定を落とすという手法が∃除去則に近いと思うのですが、うまく説明ができませんでした。

(3)は背理法で証明しています。つまり、Gが循環すると仮定して証明を進めると矛盾が導かれるため、Gが非循環である、ということになります。

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
(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の開始後)

Making Snapshot Isolation Serializable 再考 - 急がば回れ、選ぶなら近道

この表記は覚えておいた方がよいです。この後の別記事でも Ti→wr→Tj のように記載されています。この時に「iで値を生成し、jで読む。」と読めないと、内容を理解できないです。

その上でサンプルとしてExample 2.1のグラフが提示されます。
W1(X1)W1(Y1)W1(Z1)C1W3(X3)R2(X1)W2(Y2)C2R3(Y1)C3
(serializable orderはT1-T2-T3になりますね。ボールドがrw-dependencyになります)

Making Snapshot Isolation Serializable 再考 - 急がば回れ、選ぶなら近道

この説明に対応する論文の箇所を引用します。

For example, recall the SI history presented in Example 2.1 (a user-oriented history):
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.

http://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/2009/Papers/p492-fekete.pdf

H1'はMVSRでserializable orderはT1-T2-T3です。ここからW3(X3)R2(X1)がrw-dependencyになるということが分かります。

記事では論文の引用として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という2つの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解説 - 急がば回れ、選ぶなら近道

単純にAnti-dependencyのあるTXの情報を持ち回ってチェックすればいいのですが、特にReadSetの持ち回りは対象がまるまるテーブル一つになったりすると、相当やばいことになります。

Replicated Serializable Snapshot Isolation解説 - 急がば回れ、選ぶなら近道

Anti-dependencyはr-wなので、ReadSetが無いと判定できず、その対象が大きいテーブルだとネットワークが大変なことに…ということのようです。素人考えでは各ノードでreadされる可能性のあるSnapshotのバージョンを全て保持しておき、dependencyの判定はそのバージョン情報とRead/WriteのSQLだけやりとりすれば判定できそうに思えたのですが、それができないということは自分が根本的に理解できていないのか、アーキテクチャ的に無理ということなのでしょう。

記事では ws / rs という略語が出てきますが、Write Set と Read Set の略となります。

Algorithm1 の疑似コードについての解説を理解することができませんでした。今後の宿題として残します。

Multi-version Conflict Serializability

Multi-version Conflict Serializability - 急がば回れ、選ぶなら近道

この記事で「順序は全順序が前提」としています。全順序の定義は以下を参照ください。

全てのトランザクションはある全順序(total order)による逐次的な実行として現れる。これはトランザクションは他トランザクションから分離実行されることを意味する;すなわち、トランザクションにおける各個の操作は別トランザクションにおける各個の操作とインターリーブされて現れない。

(翻訳)C++トランザクシショナル言語構成要素のドラフト仕様 V1.1 [§1-2のみ] - yohhoyの日記

MVSGのグラフのエッジは以下の条件により作成される

あるxについて、wj(xj), rk(xj), wi(xi)を想定した場合、まずrk(xj)があるので、

  1. tj->tkの依存エッジが必ず存在する。
  2. xi->xjのversion orderの場合

wi(xi)->wj(xj)が存在し、よってti->tjのエッジが存在する
または
xj->xiのversion orderの場合、
wj(xj)->wi(xi)となり、そもそもwj(xj)->rk(xj)であるので、xj->xiならば、必ずrk(xj)->wi(xi)になる。
よってtk->tiのエッジが存在する。

Multi-version Conflict Serializability - 急がば回れ、選ぶなら近道

この説明の一部をもう少しかみ砕いて説明します。

"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)がなぜ依存関係ではないか?
仮にrとwを交換しようがしまいが、version orderには影響がない。

Multi-version Conflict Serializability - 急がば回れ、選ぶなら近道

とありますが、"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 初見。または初見で(テンション、フォールなしに)完登すること。
フラッシング flashing 本来は(オンサイトも含めた)1 回目のトライで完登すること。のちにオンサイトの概念が確立され、区別するために「他人の登りを見たあと、初めてのトライで完登すること」を指すようになった。

最新クライミング用語集 | 山と溪谷社のクライミング・ボルダリング総合サイト CLIMBING-net クライミングネット

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
処理のwindowがあるということを意味する。すなわち、clientまで「常に状態を返し続ける」ということではない。serialization pointが存在できる可能性の一つの前提を提供している(overlapが永遠に続くわけではない)

SILO再考〜次世代DBのアーキテクチャとして - 急がば回れ、選ぶなら近道

ここは論文を読まないと、"one-shot requests"の意味がつかみにくいです。

まず、windowとは(論文ではこの表現を使っていません)ウィンドウ制御の「ウィンドウ」の意味で使っているようです。
ウィンドウ制御については以下の解説記事を参照ください。
3 Minutes Networking No.41

※コメント
上記記載は誤っていたため、内容を訂正します。周知を兼ねて、2週間程度は取消表示とし、以降の更新タイミングで削除を予定しています。
本件について、@ さんからご指摘いただきました。詳細は更新情報に記載します。

論文では one-shot requests について以下の説明をしています。

  • リクエスト開始~終了まで、呼び出し元とはやり取りしない。
    • このモデルはOLTPワークロードに適している。
    • トランザクションの一部で通信遅延が発生すると、同時更新によるアボートの可能性が高くなるが、この方式であればその可能性を低減できる。
  • 任意のアプリケーションロジックを含んだ、1つもしくは複数のシリアライズ可能なトランザクションで構成される。
    • SILOデータベースの提供する読み書きのためのステートメントを用いて、C++で作成する。
    • SQLでも記述できるが、実装していない。


記事で出てくる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/SQLPL/pgSQLのような手続き言語に近い印象を受けます。この表現力があれば、トランザクション中にクライアントとやり取りできないという制限も受け入れられそうです。

3.MassTreeを利用
PKのindex treeで基本はB+。ただし、secondary keyは別treeになっている。したがって、secondary keyを利用する場合はtree traverseが二回になる。

SILO再考〜次世代DBのアーキテクチャとして - 急がば回れ、選ぶなら近道

論文の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 - Qiita

記事だと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
s = r1(x0)w1(x1)r2(x1)w2(y2)r1(y2)w1(z0)c1c2:multi-version

Dbts 分散olt pv2

single-versionとmono-versionが同一なのか異なるものなのか、はっきりした際にはアップデートします。

r1(x)r2(x)w1(x)w2(x)c1c2→これはFSRではない。w0(x)r2(x)w2(x)がaliveなusefulRF(以下LRF)
t1t2 r1(x)w1(x)r2(x)w2(x)c1c2 w0(x)r1(x)w1(x)r2(x)w2(x)のLRF
t2t1 r2(x)w2(x)r1(x)w1(x)c2c1 w0(x)r2(x)w2(x)r1(x)w1(x)のLRF
どれとも一致しないので、FSRにはならない。

multi-versionの基礎 - 急がば回れ、選ぶなら近道

少し見辛いですが、1行目のスケジュールが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 - Qiita

ここでも証明を理解しきれなかったので、後日再挑戦します。

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.
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.

https://www.cs.cmu.edu/~hl/papers/cicada-sigmod2017.pdf

論文で競合によってabortした場合はクロックブーストするとしています。
これは私の推測となりますが、スレッド間でtsの乖離が大きくなったために競合が発生したと仮定し、クロックブーストでそのスパンを狭めようとしているように見えます。

"external consistency"の定義は以下を参照ください。

あるトランザクションが終わった後に始まったトランザクションは、前に終わったトランザクションより必ず大きいタイムスタンプを得る、という言葉に直すと何を当然の事をと言いたくなるような一貫性保証の事をExternal Consistencyと呼ぶ。

Spanner - Qiita

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"の定義を満たすといえ、対応しているといえます。

  • rtsは全てのスレッドのwtsの最小値(min_wts)から1を引いたもの
  • read onlyのtxはthread.rtsを利用する

この定義からは"(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(因果一貫性)

  • 因果関係があるwrite操作群の順序は、各プロセスで同じ順で観測される
    • 因果関係があるwriteの例
      • プロセスP1がxに値aをwrite
      • プロセスP2はxをreadし、読み込んだ値aから計算をした結果bをyに書き込む
      • → W1(x)aとW2(y)bは因果関係にある
http://www-higashi.ist.osaka-u.ac.jp/~nakata/mobile-cp/chap-06j-1.pdf

(注:v.wts<tx.ts<v.rtsでabort。普通にMVTO)

Cicada:Dependably Fast Multi-Core In-Memory Transactions - 急がば回れ、選ぶなら近道

この記述は以前の記事の以下の記述に対応しています。

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

MVTO (multi-version timestamp ordering) - 急がば回れ、選ぶなら近道

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エントリにまとめていたのですが、想定よりも長くなって読み辛くなってしまったためです。

私の理解が足りず、課題となっている箇所は今後調べていきます。
特に証明を理解できていないケースが多いです。これには論理学を理解できていないことに一因があると考え、以下の本で勉強してから再度取り組んでいるのですが、なかなか理解が進みませんでした。

記号論理入門 (哲学教科書シリーズ)

記号論理入門 (哲学教科書シリーズ)

そこで、まずはわかったこと・わからなかったことを記録として本エントリに残しておき、今後の再チャレンジの足掛かりとすることにしました。読者の方でこうしてみたら?というヒントをお持ちの方がいましたら、ご連絡いただけますと幸いです。

更新情報

2017/10/08

前提知識

章を追加しました。

全IT関係者が知っておくべき「1-copy-snapshot isolation」

マイケル・ストーンブレーカーについての説明を追加しました。

Multi-version Conflict Serializability

説明を新規作成しました。

SILO再考~次世代DBのアーキテクチャとして

説明を新規作成しました。

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"について追記しました。

SILO再考~次世代DBのアーキテクチャとして

「処理のwindow」について、説明を見直しました。
@ さんからご指摘をいただきました。ご指摘の内容は以下で見ることができます。ありがとうございました!
https://twitter.com/arumumu/status/925309846286561280
https://twitter.com/arumumu/status/925310987665682432

大規模分散OLTP 次世代DB / 分散OLTP(MVCC系)を可能な限り 全力で解説

証明についてメモを追加しました。

今後の更新について

現状を踏まえて更新しました。

更新情報

更新情報の見出し設定によって目次が見辛くなってしまったため、スタイルを見直しました。