ぱと隊長日誌

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

PostgreSQL のシリアライザブル分離レベルにおけるスナップショットのタイミング

PostgreSQL 10 のマニュアルには以下の記載があります。

13.2.2. リピータブルリード分離レベル
リピータブルリードのトランザクション内の問い合わせは、トランザクション内の現在の文の開始時点ではなく、トランザクションの最初のトランザクション制御以外の文の開始時点のスナップショットを見る、という点でこのレベルはリードコミッティドと異なります。 従って、単一トランザクション内の連続するSELECT文は、同じデータを参照します。つまり、自身のトランザクションが開始した後にコミットされた他のトランザクションによる変更を参照しません。

13.2.3. シリアライザブル分離レベル
実際、この分離レベルは、(ある時点で)逐次実行可能なすべてのトランザクションにおいて、シリアライザブルトランザクションの同時実行の組が一貫性のないような振る舞いをしていないか監視することを除き、リピータブルリードと全く同じ動きをします。

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

この記載から、PostgreSQL のシリアライザブル分離レベルのスナップショットはリピータブルリード分離レベルと同様に「トランザクションの最初のトランザクション制御以外の文の開始時点のスナップショットを見る」ということが推測できますし、実際にそのようにふるまいます。例を挙げて確認します。

検証は PostgreSQL 10.3 で行っています。
トランザクションの略称として"TX"を用います。

(1)先行TX(TX1)のBEGIN直後に後続TX(TX2)が割り込んだ場合

-- TX1

=# CREATE TABLE valtab(value integer);

=# INSERT INTO valtab values (1);

=# BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;
-- TX2

=# BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;

=# SELECT * FROM valtab;
 value
-------
     1
(1 row)

=# UPDATE valtab SET value = 2;

=# COMMIT;
-- TX1

=# SELECT * FROM valtab;
 value
-------
     2
(1 row)

=# COMMIT;

TX1のBEGIN直後にTX2によってUPDATE/COMMITした内容を参照しました。つまり、シリアライザブル分離レベルにおいても参照するスナップショットはBEGIN時点ではないとわかります。

(2)先行TX(TX1)の操作後に後続TX(TX2)が割り込んだ場合

-- TX1

=# CREATE TABLE valtab(value integer);

=# INSERT INTO valtab values (1);

=# BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;

=# SELECT * FROM valtab;
 value
-------
     1
(1 row)
-- TX2

=# BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;

=# SELECT * FROM valtab;
 value
-------
     1
(1 row)

=# UPDATE valtab SET value = 2;

=# COMMIT;
-- TX1

=# SELECT * FROM valtab;
 value
-------
     1
(1 row)

=# COMMIT;

TX1のBEGIN直後のSELECT結果とTX2割り込み後のSELECT結果が同じとなっています(シリアライザブル分離レベルなので当然ではあります)。シリアライザブル分離レベルにおいても「トランザクションの最初のトランザクション制御以外の文の開始時点のスナップショットを見る」ことが分かりました。

トランザクションで w-w はなぜ Lost Update ではないか?

課題

db tech showcase Tokyo 2018 (db tech showcase Tokyo 2018 | db tech showcase)
でノーチラステクノロジーズ 神林さんが以下のテーマで講演されました。
MVCCにおけるw-w/w-r/r-wのあり方とcommit orderのあり方の再検討~Sundial: Harmonizing Concurrency Control and Caching in a Distributed OLTP Database Management Systemを題材に

講演の中で
w1(x1) w2(x2) c2 c1
※ r : read, w : write, c : commit, a : abort, x : item(添字は書き込んだトランザクションの番号)
が Lost Update ではないと説明がありました。ただし、その詳細については各自の宿題ということで解説はスキップされています。

これについて、私なりの理解をまとめます。結論として、これは Dirty Write であり、Lost Update ではありません。以下で説明します。

説明のベースとして "A Critique of ANSI SQL Isolation Levels" (以下、Isolation論文)を参照します。

Isolation論文のリンク:
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-95-51.pdf

神林さんによるIsolation論文解説スライド(今回の講演スライドではありません):

Dirty Write

Isolation論文で Dirty Write (P0) は以下の定義としています。

P0 (Dirty Write): Transaction T1 modifies a data item. Another transaction T2 then further modifies that data item before T1 performs a COMMIT or ROLLBACK. If T1 or T2 then performs a ROLLBACK, it is unclear what the correct data value should be.
(中略)
P0: w1[x]...w2[x]...(c1 or a1) (Dirty Write)

今回の課題のスケジュールである、
w1(x1) w2(x2) c2 c1
は P0 に合致します。

このスケジュールは1V、つまりアイテム毎に最新の値しか保持できないケースで困ります。元のスケジュール順で実行した場合、最後のc1はxの値がx1となることを期待しているはずですが、w2(x2)で上書きされてしまっているからです。

ですが、このスケジュールは S2PL で T1 → T2 の Serializable になります。
ここではロックをl、Unlockをuとします。また、xの添字を外します。

オリジナルのスケジュール:
w1(x) w2(x) c2 c1

S2PL:
l1(x) w1(x) c1 u1(x) l2(x) w2(x) c2 u2(x)

これが講演スライドの「勝手にロックが働く」の意味となります。

Lost Update

Isolation論文の Lost Update (P4) の定義と例をまとめて引用します。

P4 (Lost Update): The lost update anomaly occurs when transaction T1 reads a data item and then T2 updates the data item (possibly based on a previous read), then T1 (based on its earlier read value) updates the data item and commits. In terms of histories, this is:

P4: r1[x]...w2[x]...w1[x]...c1 (Lost Update)

The problem, as illustrated in history H4, is that even if T2 commits, T2's update will be lost.

H4: r1[x=100] r2[x=100] w2[x=120] c2 w1[x=130] c1

Dirty Write との違いは Lost Update の定義に r1[x] がいることです。これにより、P4は Serializable になりません。

r1[x] は w2[x] の前に実行されています。当然、T2のupdateはlostすることになります。
H4の例でみると、T1は x+30 、T2は x+20 なので、T1, T2 が順に実行されれば x=150 になるはずですが、x=130 となってしまいました。

今回の課題のスケジュールに r1[x] に相当する操作はなく、Lost Update ではないとわかります。

Dirty Write と Lost Update の比較

Dirty Write と Lost Update の定義を再掲します。
P0: w1[x]...w2[x]...(c1 or a1) (Dirty Write)
P4: r1[x]...w2[x]...w1[x]...c1 (Lost Update)

Dirty Write の場合、仮に先行する w1[x] がなかったとしても(T1のUpdateがLostしたとしても)、DBの最終状態には何も影響を及ぼしません。
ですが、Lost Update の場合、T2->T1 で実行された場合と、P4のorderで実行された場合とでDBの最終状態に違いが現れます。それはT1が参照すべきT2のupdateがLostしたからです。

この違いは r-w が conflict の肝だ、という話につながっていくように思うのですが、さて…?

DBTS2018「今後のDBのトランザクション処理のあり方について徹底討議する」パネラー参加記録

始めに

db tech showcase Tokyo 2018 (db tech showcase Tokyo 2018 | db tech showcase)
今後のDBのトランザクション処理のあり方について徹底討議する ~"InvisibleWriteRule: トランザクションの書込み最適化" を中心に
にパネラーとして参加してきました。その記録を残します。

きっかけ

きっかけは神林さんからの Twitter DM でした。それまでは私から神林さんを一方的に存じ上げているだけでしたので、神林さんから DM が来た時には何事かと、以前にまとめた記事(急がば回れ、選ぶなら近道 TX記事 読解メモ - ぱと隊長日誌)のことで何かお叱りを受けるのではないかと、ビクビクしていました。

実際には今回の討論会に参加しないか、とのお誘いでした。それにしても人違いではないかと心配していたのですが、人違いではないし、トランザクションに興味があって勉強していれば十分とのお言葉があり、せっかくのチャンスに乗ろうと決意しました。

伝えたかったこと

今回のパネルで話せたこと、話せなかったことも含め、私の意見をまとめておきます。
引用及びリンクは参考にした資料や記事などです。

InvisibleWriteRule (IWR) の説明で用いられたスライドです(ただし、多少中身の異なる点があります)。

IWR はスライドで補足されている通り、UPDATEでしか有効とならない。だが、競合の発生率が低い場合でも性能が向上している。なので、適したワークロードの範囲は広いとみている。

スライドには Update-Heavy な例として Database for Sensor Network が挙げられている。これが適用される分野としてIoTが思い浮かぶ。センサーのデータは残す(INSERT)ケースが多いのではと思っていたが、実例を見ていると捨てている(UPDATE)ケースもある模様。こういうアプリケーションであれば向いているのではないか。
また、神林さんが触れていたようにステータス管理等ではとてもマッチするはず。

また1工場あたり1日のデータ量がペタバイトクラスになるデータのほとんどは蓄積していない。インテルはデータ分析をエッジ部で実行し、そのPC が製造装置を監視し、装置の正常稼働状態が維持できていることを確保している。すべてが正常と判断されれば、データ蓄積は行わない。ただ統計的工程管理(SPC)の目的用途としてのみこれに要するデータを残している。

工場への機械学習・AI 導入の9ステップ-インテルIoT ワークショップ報告(2) | ARC Advisory Group

one-shot request はストアドプロシージャをイメージするとよい。リクエストをまとめて投げて、レスポンスをまとめて受け取る。これまでのインタラクティブな(SELECTを投げてその結果に応じてUPDATEするような)実装が変わってくるはず。ただ、変化を受け入れない現場が想像以上に多い中で受け入れられるか?

トランザクション分離レベルを開発者が意識し、それを適切に扱うのはやはり困難ではないか。Serializable がデフォルトで、それでもパフォーマンスが出るような時代が来てほしい。
セッションの最後に中園さんがそういう未来を目指しているとお話ししてくれたことは本当にうれしい。

  • 「世の中一般にはserializableは遅いので使うな」という言い方がされることがあるが、DB屋的にはこれは普通に屈辱(のはず。)
    • lockレスで、そのまま放り込めば、concurrentなままserializableなスケジュールを組みあげるというのが、最適な実装。
A critique of ansi sql isolation levels 解説公開用

現実的なアプリケーションのパフォーマンスをどう測定すべきか?今のメジャーなベンチマークが現実に即していないとするならば、何を持ってすれば測れるのか?ベンチマーク最適な研究が進んでしまったりしないか?
ベンチマークスペシャル - nikezono

理論の段階からロングトランザクションへの考慮をしてほしい。アボートした時のペナルティが大きすぎる。かといって、アプリが合わせに行く、例えばトランザクションの粒度を小さくして、自力でリカバリ処理を行うというやり方は本末転倒だと思う。

Abort rate は数字の大小よりその中身が重要だと思う。ロングトランザクションを犠牲にしてショートトランザクションをバンバン流せば Abort rate は見かけ上よくなる。でも、それが評価として正しいとは思えない。
Fariness の研究が進むことに期待したい。

我々のような開発者やDBAも、DB研究がどのような方向に進み、5年後か10年後かそれ以上先かもしれないが、どんな形で商用化されるかをイメージし、そこに備えておく必要がある。

参加してどうだったか

今回求められていたポジションは現場で活躍されているDBAの皆様と同じ目線でコメントしてほしいとのことでした。とはいえ、理論について議論しているところに現場の話を持ってくるというのは中々に難しく、前半は苦しいコメントとなってしまいました。
後半は若干開き直り、多少テーマを外れても好きにしゃべることにしました。「(理論の)現状の問題点」を「現場の現状の問題点」に言い換えてしゃべったときはさすがにまずいかと冷や汗かいていましたが、隣にいた神林さんがウンウンとうなずきつつ、それでいい、とつぶやいてくださり、ホッとしました。

現場とつなぐ、という意味で初見ではわかりにくいところを補足できればよかったな、というのが反省点です。例えば、 R∞設定 とか one-shot request とか、いきなり言われてもよくわからないですよね。間違った解説をしても周囲がプロなので速攻訂正されたでしょうし、やってみてもよかったなと思っています。

慣れてきた後半はリスナーの方の様子を見ながら話していたのですが、うなずきながら聞いてくれる方のありがたさをひしひしと感じました。分かってくれる方もいるんだ、と思うだけで不安とか緊張がかなり解消されました。

スピーカーの皆さんのすごさ

論文の読み解き方

私のレベルでも字面を追って理解した気にはなれます。ですが、スピーカーの皆さんのレベルになると、その記述に込められた意味まで的確にくみ取っていました。その具体例が神林さんのブログ(急がば回れ、選ぶなら近道)なり発表に現れています。

関連研究の知識の広さと深さ

手法の議論をする際にあれと一緒だよね、でお互いに伝わっていました。

そして、知らないことは知らないといえること、それに対して教え合う姿勢があることも素敵でした。誰もググれなんていいません。その打ち合わせに臨む以上、準備はしてきているはずだし、それで知らないのであれば教え合おう、という雰囲気があったように感じました。

課題への取り組み方

事前打ち合わせを2回実施しましたが、1回目での課題をそのまま次回へ持ち越す事はありえませんでした。それまでに課題に対して調査と検討を行い、自分なりの答えを持って次回に臨まれていました。
当たり前のことかもしれませんが、中々できないことではないかと。

最後に

お誘いを受けた時は自分の力量不足に自覚があり、迷惑をかけるのではないかと悩みましたが、今となっては参加できて本当に良かったです。

特によかったのが、トランザクションに興味を持つ方のコミュニティに参加できたということです。今まではわからないことを延々と悩んでいましたが、考え抜いてもわからなかったことを相談できる、というのは大変ありがたいことでした。

参加するにあたり、自分の知識・経験不足を言い訳にしないことを決めていました。それは甘えでしかありません。それよりも、セッションが終わるその瞬間まで、自分がやれる精一杯のことをやるべきだと考えていました。それを貫き通せたことは自信にもつながりました。

今後も、研究と実務の間の橋渡し役として、微力ながら貢献させていただきます。