ぱと隊長日誌

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

Database Concurrency Control Papadimitriou 読書会 第15回 議論メモ

勉強会について

Database Concurrency Control Papadimitriou 読会 第15回 - connpass の議論メモです。

自分のメモをベースにまとめています。発言の聞き間違い、解釈違いの可能性があることをご了承ください。

特記の無い引用は本で議論した箇所を示しています。

Theory of Database Concurrency Control

Theory of Database Concurrency Control

[memo]は私のメモです。勉強会で議論された内容ではないことにご注意ください。

2.6 CONFLICT SERIALIZABILITY

this notion is free from negative complexity results such as those in the previous section.

ここでの "negative complexity" とは NP-complete のこと。

conflict if the following is true: Both steps read or write the same entity, and not both are read steps.

conflict とは異なるトランザクションのステップが同じエンティティに対して以下の条件を全て満たすである。

  • read or write している。
  • 両方とも read ではない。


[memo]
Example 2.5
R1(y) R3(w) R2(y) W1(y) W1(x) W2(x) W2(z) W3(x)
スケジュール A2A1A3 と view equivalent であることを確認します。
A1, A2 は A2 → A1 となる必要があります。オリジナルのスケジュールでは A1, A2 共に y の初期値を読んでいますが、A1 → A2 だと A1 が y に値を書き込み、A2 がそれを読んでしまうためです。
また、A3 はスケジュールで最後になる必要があります。A1, A2, A3 共に x へ値を書き込んでいますが、VSR が FSR も満たす必要があることを考えると、オリジナルのスケジュールで最後に x へ書き込んだ A3 が最後になる必要があります。
よって、A2A1A3 が唯一 view equivalent な serial schedule とわかります。

MVで全てのバージョンを保持できるとすれば、「最終状態」が複数ありうると考えるのが妥当なのではないか。今の理論は「最終状態」が一つに決まる前提を置いているのが気になる。

MVSR ではTXの順序が重要となるケースを考慮していない。
同じTX群を同じプロトコルに投入したとき、deterministic であれば同じ結果になる。ただ、現実の世界では物理レベルの微妙な latency を無視することができず、異なる結果となることがある。
それでもTXの順序を守る必要があるなら、ミドルかアプリがやるしかない。だが、それはパフォーマンスを落とすことになる。
そもそも、TXの順序が重要であればDBを使う必要があるのかを考える必要がある。突き詰めればファイルでも良いのではないか?
例として株取引がある。これはDBのTXではなく、他に定められたプロトコルで約定が決まる。となると、必ずしもTXの順序を守る必要があるとは言えない。

DBは「よしなにやってくれる」とみんなが思っているが、「よしな」とは何かをちゃんと理解せずに使っている。

Oracleが「Snapshot Isolation は serializable」と言ってしまったがために未だ誤解されている。

赤い会社「完全にserializableですよ。」
その他大勢「いや、SIではfull-serializableにはならないし。」
赤い会社「いや、ほぼ同じだし。」
その他大勢「なんだよ、ほぼ同じってww」
赤い会社「だからこのベンチマークTPC-C)でちゃんとanomalyなしだし」
その他大勢「いやだから、そのベンチマークがそもそもだな・・・」
あれやこれや・・・
(以上、脚色なし)

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

We can test in O(n2) time whether a schedule is conflict serializable.

O(n2) の n は node、つまりトランザクションの数だ。cycle を発見するために最悪 O(n2) かかるということだ。

Conflicts and Commutativity

reflexive-transitive closure は「反射推移閉包」と訳される。
reflexive closure(反射閉包)かつ transitive closure(推移閉包)なもの。

関係Rの反射推移閉包とは、Rを含み反射性と推移性の両者を満たす最小の関係のことです。

ソフトウェアの基礎

∼* を ∼ の reflexive-transitive closure とする。これは non-conflicting な step を交換したということだ。ここでの交換は step order を前提としている。

関連記事

papa本第15回参加メモ - 誰にも見えないブログ
@yuyabu2 さんの読書会ノート。

JRきっぷの発売日と学割利用の注意点

JRのきっぷ(乗車券)を購入しようとしてはまったポイントを記録しておきます。

きっぷの発売は原則として乗車当日のみ

原則としてお乗りになる日から有効な乗車券を発売します。指定券と同時にお求めの場合は1カ月前から発売します。

きっぷの発売日:JR東日本

これは原則として乗車券を乗車当日に発売するということです。乗車日を指定して事前に購入できるという意味ではありません。ただし、指定券と同時に購入するのであれば、1カ月前から乗車券も購入可能です。

私の場合、「お乗りになる日から有効な乗車券」を誤解し、「乗りたい日から有効な乗車券」を事前に購入可能と思い込んでしまっていました。指定券と同時購入なら1か月前から、という説明に違和感を感じればよかったのですが…。

学生割引のきっぷは代理で購入可能

学生割引のきっぷ(乗車券)を購入するには、あらかじめ学校で学割証(学生・生徒旅客運賃割引証)の発行を受けてください。発行された学割証に必要事項を記入し、駅や旅行会社の窓口でお買い求めの際に提出してください。
学生割引のきっぷをお買い求めいただく際には学生証を呈示いただく必要はございません。ご家族など、代理の方でもお買い求めいただけます。
一方、学生割引のきっぷをご利用の際には、必ず学生証を携帯してください。

学生割引のきっぷを購入するには、どうすればよいですか。:JRおでかけネット

JR西日本のヘルプページですが、JR東日本の駅でも同様の説明を受けました。

JR各社のヘルプページに学生割引の説明はあるのですが、代理購入可能であることや、きっぷ利用の際には学生証が必要なことなどを説明しているページは他に見当たらなかったので、参考になさってください。

なお、学生割引は適用対象に条件があることもご注意ください。

学生割引は、片道の営業キロが100キロを超える乗車券に適用され、運賃が2割引となります。片道の営業キロが600キロを超える往復乗車券の場合は、往復割引と学生割引を重複して適用いたします。
特急券・グリーン券・寝台券などは、学生割引の対象となりません。

学生割引はどのようなきっぷに適用されますか。:JRおでかけネット

PostgreSQLはトランザクション内で制約を一旦外して戻すことができる

はじめに

こんな tweet を拝見しました。

遅延制約(DEFERRABLE)を使えば制約を一旦外す必要がないのですが、技術的な可否が気になり、調べた結果をまとめます。

ドキュメント調査

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

DDLコマンドの中には、現在はTRUNCATEとテーブルを書き換える形のALTER TABLEだけですが、MVCCセーフでないものがあります。 これは、DDLコマンドをコミットする前に取得したスナップショットを使っていると、切り詰めまたは書き換えのコミット後に、同時実行トランザクションに対してテーブルが空に見えることを意味しています。

13.5. 警告

この具体例は以下の記事を参照ください。
PostgreSQL のトランザクション & MVCC & スナップショットの仕組み

マニュアルには『テーブルを書き換える形のALTER TABLE』とあり、『制約を書き換えるだけの ALTER TABLE』は対象外に思えますが、動作検証で試してみます。『テーブルが空に見える』ということなので、空に見えなければOKとします。

動作検証

PostgreSQL 11.4 で確認しました。

検証手順は遅延制約について解説した記事での手順をベースにしています。
PostgreSQLで遅延制約を使って一意制約カラムを一括更新する - Qiita

これに対して制約のDROP/ADDを追加するとともに、MVCCセーフであるか(テーブルが空に見えないか)?を検証する手順としました。

手順では2つのトランザクションを用いており、TX1/TX2で記載しています。

-- TX1

=# CREATE TABLE posts (id integer, CONSTRAINT posts_pk PRIMARY KEY (id));

=# INSERT INTO posts VALUES(1);
=# INSERT INTO posts VALUES(2);
=# INSERT INTO posts VALUES(3);

=# BEGIN ISOLATION LEVEL SERIALIZABLE;

=# SELECT txid_current();
-- TX2

=# BEGIN ISOLATION LEVEL SERIALIZABLE;

=# SELECT txid_current();

=# ALTER TABLE posts DROP CONSTRAINT posts_pk;

=# UPDATE posts SET id = id + 1;

=# ALTER TABLE posts ADD CONSTRAINT posts_pk PRIMARY KEY (id);

=# COMMIT;

=# SELECT * FROM posts ORDER BY posts;
 id
----
  2
  3
  4
(3 rows)
-- TX1

=# SELECT * FROM posts ORDER BY posts;
 id
----
  1
  2
  3
(3 rows)

PostgreSQLではトランザクション内で「一旦制約を外す ⇒ 操作する ⇒ 制約を戻す」ことが可能であるとわかりました。
また、SELECT結果からトランザクションの順序 (TX1 → TX2) も想定通りであることが確認できました。

注意点

動作検証のTX1の最後の状態でpsqlの\dコマンド(オブジェクトの概要表示)を対象のテーブルに使うとエラーになります。

=# \d posts
ERROR:  cache lookup failed for index 0
STATEMENT:  SELECT c2.relname, i.indisprimary, i.indisunique, i.indisclustered, i.indisvalid, pg_catalog.pg_get_indexdef(i.indexrelid, 0, true),
    pg_catalog.pg_get_constraintdef(con.oid, true), contype, condeferrable, condeferred, i.indisreplident, c2.reltablespace
  FROM pg_catalog.pg_class c, pg_catalog.pg_class c2, pg_catalog.pg_index i
    LEFT JOIN pg_catalog.pg_constraint con ON (conrelid = i.indrelid AND conindid = i.indexrelid AND contype IN ('p','u','x'))
  WHERE c.oid = '16537' AND c.oid = i.indrelid AND i.indexrelid = c2.oid
  ORDER BY i.indisprimary DESC, i.indisunique DESC, c2.relname;

今回の記事の目的からは若干外れるので深追いしていませんが、PRIMARY KEY 制約を DROP/ADD したことで index が再生成され、トランザクション分離レベルに従わない関数によってエラーを起こしたのではないかとみています。
PostgreSQLの一部の関数はトランザクション分離レベルに従わない - ぱと隊長日誌

まとめ

PostgreSQLは制約の操作(ADD/DROP)もトランザクションに含めることができます。
ただし、全てのDDLコマンドや関数がMVCCセーフとは限らない点に注意が必要です。
実務では制約を操作するのではなく、遅延制約での実現を検討するのが良いでしょう。