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

勉強会について

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

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

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

Theory of Database Concurrency Control

作者: Christos Papadimitriou
出版社/メーカー: Computer Science Pr
発売日: 1986/07/01
メディア: ハードカバー
この商品を含むブログを見る

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

1.1 DATABASES AND CONCURRENCY

この本のベースはスケジューラの話となっている。

database (DB) はデータを長い期間保持する。また、この本ではデータをディスクやテープに保存すると想定している。

データは物理 (physical) と概念 (conceptual) の2層構造となっており、これを繋ぐのがDBの役割だ。

本の記述に "query language" とあるので、SQLを想定している。だが、APIでデータ操作を行うことも可能だろう。

"database management system" (DBMS) の主な機能は物理と概念のデータ構造をマッピングすることだ。それ以外にも security や concurrency control (CC) がある。

The Problem of Concurrency

DBはエンティティ (entity) で構成されている。エンティティはデータ構造をこれ以上分割できないところまで分割したものだ。

ステート (state) はエンティティに対して何らかの値をアサインする。

実世界での制限 (real-world restrictions) を integrity constraints と呼ぶ。これは一般的なDBが「制約」と呼ぶものよりも広い定義かもしれない。
実世界での制限とは銀行の預金残高がマイナスになったり、飛行機の座席数を超えて予約を受け付けてしまうことを防ぐことだ。

[memo]
Oracle Database 11g の用語集では "integrity constraints" を「整合性制約」と訳していました。
Oracle Database 11g 用語集

DBの状態（エンティティの値の組み合わせ）が integrity constraints を満たしているときを consistent state と呼ぶ。

残高の増減や飛行機の予約などで DB の状態が変わることを state transitions と呼ぶ。

many similar state transitions are grouped together and implemented by an application program.

" application program" とあるが、もっと広く処理全般を指し示しているか？

プログラムにも状態がある。
プログラムもDBも correct つまり consistent state でないとダメ。途中は inconsistent でいいが、最後は consistent にならないといけない。

プログラムを並行 (concurrent) に実行することでスループットを上げられるが、トランザクション間の予期せぬ相互作用により深刻なエラーが発生することもある。

Example 1.1 は Inconsistent Read Anomaly の例だ。

[memo]
Inconsistent Read Anomaly については以下の解説記事を参照ください。
いろんなAnomaly - Qiita

プログラム A, B が以下の処理を行うとする。
A : x := x - 1; y := y + 1
B : x := 2 * x; y := 2 * y
integrity constraints として "x + y = 0" があるとする。

A, B の順に処理すれば integrity constraints を満たす。

step	X	Y
---	-1	1
x = x - 1	-2	1
y = y + 1	-2	2
x = 2 * x	-4	2
y = 2 * y	-4	4

だが、A の処理中に B が割り込んだような場合に integrity constraints を満たさなくなることがある。

step	X	Y
---	-1	1
x = x - 1	-2	1
x = 2 * x	-4	1
y = 2 * y	-4	2
y = y + 1	-4	3

この本で Anomary の話をほとんどしていない。Papadimitriou は Anomary の定式化に価値を見出してないということかもしれない。

Example 1.1 は Serializable にこだわっておらず、結果的に consistent であればよいとしている。

OSとDBのCCは異なるものだ。
OSのCCは並行するプロセスのリソース競合の調停であり、リソースを使用するプロセスを優先度で決めたり、他方を待たせたりする。これに対し、DBのCCはトランザクションの分離 (Isolation) だ。
もう一つの違いは操作する対象だ。OSの操作するリソース（プリンタ、メモリ、プロセッサ）は "robustness" であり、やり直しがきく。だが、DBの操作する対象はデータであり、一度壊れるとやり直しがきかない。

1.2 THE MODEL

The fact that there are infinitely many entities is rather inconsequential; it will soon be clear from our model that at any instant only a finite number of entities can be relevant.

ここで言いたいことは、永遠の時間ではエンティティが無限個でも、ある有限の時間では有限個である、ということではないか。

エンティティは重ならないし分割できない。update に副作用がない。
副作用が無いと言うことは明示的に update したときだけが update になる。

各エンティティの取り得る値 x の可算集合 (enumerable set) がドメイン D_x である。integrity constraints C は D_x のデカルト積 (Cartesian Product) の部分集合 (subset) だ。
この記述はページモデルとかオブジェクトモデルといったものを無視している。

Transactions

database step の read はエンティティの現在の値をプログラムの変数にアサインする。write はエンティティの現在の値をプログラムが計算した値に変更する。

write an entity (i.e., change the current value of the entity to a value previously computed by the program)

"change the current value" は Read Modify Write 前提なのか？だとすれば、update はよいが insert（つまり change ではない場合）をどう扱うのか？ここでのモデルだと初期値がある前提となっており、またその初期値は read できなくても良いのではないか？もしくはここでの change には insert も含んでいるのではないか？

[memo]
トランザクションを分割することを "Transaction Chopping" というそうです。 Weikum本から定義を引用します。

DEFINITION 8.8 Transaction Chopping
Let t_i be a transaction program. A chopping of t_i is a decomposition of t_i into ordered pieces t_i1, ... , t_ik (k ≥ 1, most often k ≥ 2) such that every database operation invoked by t_i is contained in exactly one piece, and the order of operation invocations is preserved.
Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

トランザクションの分割では "hidden restrictions" を考える必要があります。

A transaction is a unit of consistency, a grouping together of several database steps, the combined execution of which is known to preserve the integrity constraints. A consequence is that there can be no "hidden restrictions" on inter-transaction behavior.

s₁ = r₁(x)r₂(x)w₁(x)w₂(x)c₁c₂
s₁ は Serializable でないため、TX₂を abort することになります。
s₂ = r₁(x)c₁r₂(x)c₂w₃(x)c₃w₄(x)c₄
s₂ は TX₁ → TX₂ → TX₃ → TX₄ で Serializable となります。
ですが s₁ の TX₁ が s₂ の TX₁, TX₃ に、 s₁ の TX₂ が s₂ の TX₂, TX₄ に分割されていたとしたら、それは correctness といえるでしょうか？トランザクションの処理が在庫数の read と write だとすれば、s₂ は実際の在庫数と矛盾してしまうかもしれません。