ぱと隊長日誌

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

トランザクションをもっと深く知るための資料集

はじめに

データベース(DB)を扱う方にとって、トランザクションは当たり前の存在です。そんな当たり前のものがどういった理論と技術で実現されているか、そしてそれらが今も進化していることをご存知でしょうか。

トランザクションをもっと深く知りたい方に向けて、参考となる資料をご紹介します。

資料は日本語で書かれたものを中心に紹介しています。また、Level設定は私の主観によるものです。

Level 0

トランザクションを深く学ぶための準備フェーズです。

まずは自分の得意なRDBのマニュアルもしくは本から、以下に関する章を読んでみてください。

現在のプロダクトにどのような技術が用いられているかを知ったうえで学ぶことで、その背景にはどんな理論があるのか、また研究レベルでどんな進化を遂げているのかを実感して学ぶことができます。そして、将来のDBの姿が見えてくるはずです。

Level 1

トランザクション理論への第一歩です。

この先へ進むにあたり注意していただきたいのが、ひとまず自分の知っている Serializable を忘れてください。一般的なRDBで設定可能なトランザクション分離レベルである SERIALIZABLE にとらわれると、実際の振る舞いと学術的な説明の差異に混乱するかもしれません。まずは資料の説明を素直に受け入れ、先に進むことで気づきがあると思います。

一人トランザクション技術 Advent Calendar 2016

一人トランザクション技術 Advent Calendar 2016 - Qiita

kumagiさん(@)による、とても分かりやすい記事集です。基礎的なとこから比較的最近の研究成果まで、一通り学ぶことができます。
kumagiさんの資料全般に言えることですが、難しいことをわかりやすく、時に図示して解説してくれます。

Level 2

トランザクションに関する用語と最近の研究成果のサマリを学びます。

トランザクションをSerializableにする4つの方法

kumagiさんの資料です。
「2015年12月18日に行われたビッグデータ基盤勉強会で発表する際に使った資料」とのこと。

Serializable で無いときに起こる Anomaly を取り上げ、それをどのように解決するかを解説しています。

この資料の「Serializableとは?」というスライドの内容に違和感を覚えるかも知れませんが、一旦受け止めて先に進んでみることをお勧めします。

キーワード:Serializable, Anomaly, 2PL, Silo

トランザクションの設計と進化

kumagiさんの資料です。
「2016年7月27日 Database Lounge Tokyoで話した内容」とのこと。

従来のリカバリ技法の前提にはメモリ容量 << ディスク容量がありました。ですが、時代は変わり、メモリ容量が大きくなったことで In-Memory DB が登場し、そのリカバリ技法も変わったことを解説しています。

キーワード:リカバリ, In-Memory DB, Silo

トランザクション入門

kumagiさんの資料です。

トランザクションの並行処理に着目して解説しています。

キーワード:Linearizability, 2PL

並行実行制御の最適化手法

中園さん(@)の資料です。

並行実行制御の性能向上手法についての概要を解説しています。

キーワード:2PL, Early Lock Release, Group Commit, Speculative Read

Level 3

ここからは覚悟が必要になります。学ぶ覚悟、そしてWeikum本(TX本)を買う覚悟です。
Serializable とは何なのか、ということを突き詰めていくことになります。

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

この本は技術書の中でも値段の高い部類です。Kindle版ですら1万円を超えます。
ですが、この先のレベルを学ぶのであれば、購入することをお勧めします。この先に出てくる資料では度々Weikum本の用語や記法が使われます。また、それらはググってもほとんど出てきません。用語がわからず延々とググって時間を無駄にするより(私のことです…)、購入して手元に置きながら学ぶことをお勧めします。

ハードカバー版とKindle版がありますが、ハードカバー版のほうが使い勝手がよさそうです(私はKindle版を購入していました)。Kindle版は検索が楽なのですが、頭から読み進める際は行きつ戻りつしながら読むことになるので、ハードカバー版のほうが読み進めやすそうです。

トランザクションの並行実行制御 rev.2

サイボウズ・ラボの星野さん(@)によるトランザクションの解説スライドです。

Deadlockを回避する手法についてスライドを割いて解説しています。

キーワード:Serializability, 2PL, Deadlock

中園さんの Scrapbox

Transactional Information Systems - nikezono

Weikum本を読み進めるための心強いガイドです。kumagiさんと同じく、難しいことをとてもわかりやすくかみ砕いて説明しています。

上記リンクから辿れるページ以外にも参考になる用語解説などがありますので、ぜひ参照してみてください。

Riccardo Rosati 教授の授業資料

Data Management for Data Science - Sapienza Universita' di Roma

Data Management for Data Science の授業資料が公開されています。英語です。

このうち、"DBMS transaction management and recovery management"というリンク(記事公開時点)の資料がトランザクションを知るうえで参考になります。Weikum本が入手できない場合は代わりに読むことをお勧めします。ただし、(記事公開時点の資料においては)FSR, VSR の説明が無いなど物足りない点があり、Weikum本の代替にはなりません。

[xSIG 2018]InvisibleWriteRule: Extended write protocol for 1VCC

中園さんらによる InvisibleWriteRule の xSIG2018 発表資料です。表紙は日本語ですが、中身は英語です。

InvisibleWrite は読まれることのない書き込み処理をスキップすることで性能を向上させる手法です。

キーワード:OCC, Serializable, Bloom Filter

Level 4

最近の研究成果を学びます。これらの研究成果が商用プロダクトに適用されるまでに何年かかるか(そもそも商用に適用されるのか)わかりませんが、先を見通したい方はぜひチャンレンジしてください。そして、私に教えてください…。

このレベルはほぼ神林さん(@)の独壇場です。

急がば回れ、選ぶなら近道

急がば回れ、選ぶなら近道

神林さんのブログです。トランザクションの論文を解説した記事を何本も掲載しています。
Weikum本と論文を片手に読まないとチンプンカンプンな、ついてこれる奴だけついてこいのスタイルです。でも、それが面白いです。

ブログはトランザクション以外の記事もあり、特にまとまってはいません。以前に私がトランザクション関連記事をまとめていますので、リンク集代わりにお使いください(最近の分はまだ反映できていません)。
急がば回れ、選ぶなら近道 TX記事 読解メモ - ぱと隊長日誌

A Critique of ANSI SQL Isolation Levels 再読

神林さんの発表資料です。

Isolation Levels とは何なのか。それはどう定義すべきものなのか。ということを提案した論文(A Critique of ANSI SQL Isolation Levels)について解説しています。

キーワード:Isolation Levels, 2PL, SI

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

db tech showcase Tokyo 2017 での神林さんの発表資料です。

Cicada の解説がメインとなります。

以前に聴講メモをまとめましたので、併せて参照ください。
DBTS2017「次世代DB / 分散OLTP(MVCC系)を可能な限り全力で解説」聴講メモ - ぱと隊長日誌

キーワード:OCC, MVCC, Serialization, Cicada, WBL

トランザクションの Strictness と Rigorousness の定義を再確認する

はじめに

トランザクションの Recoverability を理解するうえで Strictness (ST) と Rigorousness (RG) を避けては通ることができません。ただ、日本語の資料が少ないうえに用語の定義が若干あいまいなケースも見受けられました。そこで、本エントリでは資料をまとめつつ、定義を再確認します。

参考資料

本エントリで参照する資料と本エントリ内での略記をまとめます。

(1) TX本

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

言わずと知れたトランザクション技術に関する原典ともいうべき本。以降に紹介する資料もこの本を参考にしていると思われます。

(2) Rosati資料
http://www.dis.uniroma1.it/~rosati/gd/1-concurrency.pdf
Rosati教授の講義用資料のようです。
今回の内容は資料の "2.5 Recoverability of transactions" にまとめられています。

(3) kumagi資料
S2PLと永続化
@ さんがトランザクション技術について解説した「一人トランザクション技術 Advent Calendar 2016」のうち、今回のテーマに関する記事です。

(4) 星野資料

星野 喬 さんが筑波大学 集中講義で利用したスライドとのことです。

Strictness (ST) とは

まず、TX本(P393)から確認します。

DEFINITION 11.7 Strictness
A schedule s is strict if the following holds for all transaction ti ∈ trans(s) and for all pi(x) ∈ op(ti), p ∈ {r,w}: if wj(x) <s pi(x), i ≠ j, then aj <s pi(x) ∨ cj <s pi(x).
Let ST denote the class of all strict schedules.

In words, a schedule is strict if no data item is read or overwritten until the transaction that wrote it last has ended (either by commit or by abort).

Rosati資料(P105)では式を使わずに説明しています。

We say that a schedule S is strict if every transaction reads only values written by transactions that have already committed, and writes only on transactions that have already committed

kumagi資料での説明を引用します。

Strictとは「あるトランザクションによる、ある値への書き込みが他のトランザクションの読み込み・書き込みより先なら、他のトランザクションの読み書きは最初のトランザクションのコミットかアボートより後になる」というルールである。

星野資料(P20)での説明を引用します。

Tx1 が write している data item を read/write しようとする Tx2 は Tx1 が commit/abort するまでそれを待つ必要がある

いずれの説明も同じといえます。

Rigorousness (RG) とは

今回取り上げた日本語の資料は Rigorousness の説明に補足すべき点があります。順に確認していきます。

まず、TX本(P394)から確認します。

DEFINITION 11.8 Rigorousness
A schedule s is rigorous if it is strict and additionally satisfies the following condition: for all transactions ti, tj ∈ trans(s), if rj(x) <s wi(x), i ≠ j, then aj <s wi(x) ∨ cj <s wi(x).
Let RG denote the class of all rigorous schedules.

In words, a schedule is rigorous if it is strict and no object x is overwritten until all transactions that read x last are finished.

Rosati資料(P107)を確認します。Strictness も含めた定義となっています。

We say that a schedule S is rigorous if for each pair of conflicting actions ai (belonging to transaction Ti) and bj (belonging to transaction Tj) appearing in S, the commit command ci of Ti appears in S between ai and bj.

kumagi資料での説明を引用します。

RigorousとはStrictの条件を守った上で「あるトランザクションによる、ある値への読み込みが他のトランザクションの読み込みより先なら、他のトランザクションの読み込みは最初のトランザクションのコミットかアボートより後になる」というルールである。

この説明には誤記があり、「他のトランザクションの読み込み」ではなく「他のトランザクションの書き込み」です。

正しく書き換えると以下の説明となります。
『RigorousとはStrictの条件を守った上で「あるトランザクションによる、ある値への読み込みが他のトランザクションの書き込みより先なら、他のトランザクションの書き込みは最初のトランザクションのコミットかアボートより後になる」というルールである。』

星野資料(P23)での説明を引用します。

Tx1 が read/write している data item を read/write しようとする Tx2 は Tx1 が commit/abort するまでそれを待つ必要がある

この説明には若干ミスリードな個所があり、Tx1 / Tx2 共に read のみであれば commit/abort 済みであるかは問題となりません。星野資料(P15)の「Conflict(競合)」の説明より、同じ data item に対する r-r は競合しないからです。

まとめ

Strictness / Rigorousness の定義は既に確認した通りです。今回の用語に限らず、改めてTX本を見直すことで発見があるかもしれません。

Strictness は w-r / w-w 競合を、Rigorousness は r-w 競合も対象としています。r-r は競合しません。

PostgreSQLの一部の関数はトランザクション分離レベルに従わない

はじめに

PostgreSQL 8.4.1 で pg_dump と index の再作成を同時に実行すると "ERROR: cache lookup failed for index" の発生することがあるのはなぜか?との質問に、tom lane さんがこんな回答をしていました。

pg_dump runs in a serializable transaction, so it sees a consistent snapshot of the database including system catalogs. However, it relies in part on various specialized backend functions like pg_get_indexdef(), and those things tend to run on SnapshotNow time, ie they look at the currently committed state.

PostgreSQL: Re: Cache lookup failure for index during pg_dump

pg_dump はシリアライザブルトランザクションPostgreSQL 9.1以降のリピータブルリードに相当)で実行されるが、pg_get_indexdef() のような一部の関数は現在のコミット済みの状態を返すとあります。

PostgreSQL 9.1 以降はトランザクション分離レベルが変更されていますが、これによって挙動の変化はあったのでしょうか?本エントリで確認結果をまとめます。

検証

検証環境・方針

PostgreSQL 10.3 で検証を行いました。

トランザクション1(T1)でインデックスを drop し、トランザクション2(T2)で pg_get_indexdef() を実行して挙動を確認しました。また、以下の条件を組み合わせています。

  • DROP INDEX コミット前/後
  • リピータブルリード/シリアライザブル

今回の検証ではリピータブルリード/シリアライザブルで結果に差異がありませんでした。そこで、検証結果はシリアライザブルの例でまとめます。

DROP INDEX コミット前に pg_get_indexdef() を実行する

-- T1

=# CREATE TABLE index_test(value integer);

=# CREATE INDEX value_idx ON index_test(value);

=# BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;
-- T2

=# BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;

=# SELECT oid FROM pg_class WHERE relname = 'value_idx';
  oid
-------
 16929
(1 row)

=# SELECT pg_get_indexdef(16929);
                         pg_get_indexdef
-----------------------------------------------------------------
 CREATE INDEX value_idx ON public.index_test USING btree (value)
(1 row)
-- T1

=# DROP INDEX value_idx;
-- T2

=# SELECT oid FROM pg_class WHERE relname = 'value_idx';
  oid
-------
 16929
(1 row)
-- DROP INDEX 発行後もOIDが取得できる。
-- スナップショットを利用するため、この挙動は妥当といえる。

=# SELECT pg_get_indexdef(16929);
-- レスポンスが保留される。
-- T1

=# COMMIT;
-- T2

保留されていたレスポンスが戻り、
"ERROR:  cache lookup failed for relation 16929"
と表示される。
インデックスが削除された状態、つまりT1コミット後の状態を見ている。

DROP INDEX コミット後に pg_get_indexdef() を実行する

-- T1

=# CREATE TABLE index_test(value integer);

=# CREATE INDEX value_idx ON index_test(value);

=# BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;
-- T2

=# BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;

=# SELECT oid FROM pg_class WHERE relname = 'value_idx';
  oid
-------
 16931
(1 row)

=# SELECT pg_get_indexdef(16931);
                         pg_get_indexdef
-----------------------------------------------------------------
 CREATE INDEX value_idx ON public.index_test USING btree (value)
(1 row)
-- T1

=# DROP INDEX value_idx;

=# COMMIT;
-- T2

=# SELECT oid FROM pg_class WHERE relname = 'value_idx';
  oid
-------
 16931
(1 row)
-- DROP INDEX 発行後かつコミット後もOIDが取得できる。
-- スナップショットを利用するため、この挙動は妥当といえる。

=# SELECT pg_get_indexdef(16931);
 pg_get_indexdef
-----------------

(1 row)
-- CREATE INDEX 文を取得できない(T1コミット後の状態を見ている)が、エラーにはならなかった。

まとめ

PostgreSQL 10 かつ シリアライザブル分離レベルであっても、pg_get_indexdef() はスナップショットではなくコミット済みの状態を返しました。また、DROP INDEX のコミット前後によって pg_get_indexdef() の挙動が変わることもわかりました。PostgreSQL 10 以外のバージョンでも同様にふるまう可能性が高そうです。

冒頭で紹介した回答にはこんな記述もあります。

The right fix for this is to make all those inquiry functions use the calling query's snapshot; but duplicating a lot of backend infrastructure is going to be a major pain in the rear, so the discussion has kind of petered out every time it's come up in the past.

PostgreSQL: Re: Cache lookup failure for index during pg_dump

今回のふるまいについてマニュアルを確認しましたが、該当する記述を見つけられませんでした。TRUNCATEのようにMVCCセーフでないとマニュアルに明記されているコマンドもありますが、記載がなくともトランザクション分離レベルに従わないふるまいをする関数があるということです。

また、該当する関数を直接使わずとも、pg_dump のように利用しているケースがあります。今回のようなケースがあることを頭の片隅に入れておくとよいでしょう。