勉強会について
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) がドメイン Dx である。integrity constraints C は Dx のデカルト積 (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 ti be a transaction program. A chopping of ti is a decomposition of ti into ordered pieces ti1, ... , tik (k ≥ 1, most often k ≥ 2) such that every database operation invoked by ti 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.
s1 = r1(x)r2(x)w1(x)w2(x)c1c2
s1 は Serializable でないため、TX2を abort することになります。
s2 = r1(x)c1r2(x)c2w3(x)c3w4(x)c4
s2 は TX1 → TX2 → TX3 → TX4 で Serializable となります。
ですが s1 の TX1 が s2 の TX1, TX3 に、 s1 の TX2 が s2 の TX2, TX4 に分割されていたとしたら、それは correctness といえるでしょうか？トランザクションの処理が在庫数の read と write だとすれば、s2 は実際の在庫数と矛盾してしまうかもしれません。
Definition 1.1 はエルブラン・セマンティクスを厳密に定義している。
"current value" という記述から、single version を前提としているかもしれない。
Definition 1.2 もエルブラン・セマンティクスのことをいっている。
Πは直積集合を意味していて、ここでの直積集合は a 以前に read した値の全てを指している。
[memo]
エルブラン・セマンティクス(Herbrand Semantics)理解メモ - ぱと隊長日誌
write する値はそれまでに read した値とアプリケーションのセマンティクスで決まる。
セマンティクス（もしくは interpretation）とは以下の定義といえる。
- Definition 1.2 の fa の決め方を与えるもの
- 何をどうする、という指針を与えるもの
- 「writeする値を決めるルール」を決めるルール（メタ）を決めるもの
関連記事
The Theory of Database Concurrency Control - nikezono
中園さんの読書メモ。
serializableとconsistent state - すぴすらのろぐ
@dev_supisula さんの考察メモ。
Theory of Database Concurrency Control 読書会 第1回ノート - Yabu.log
@yuyabu2 さんの読書会ノート。
更新情報
2019/05/19
セクション「参考」を「関連記事」に変更しました。
また、関連記事に記事を追加しました。
