###### tags: `TransactionalInformationSystems`

# 4章-1 Concurrency Control アルゴリズム

## 本章の目標と概要

複数の並列トランザクションに対し、conflict serializableなスケジュールを割り当てるためのスケジューリングアルゴリズムを考える。この際中断が考慮に入っていないが、それは第3部で議論する。

アルゴリズムの着目点

1. 安全性、つまり出力スケジュールが全てCSRに属するか。
2. 強力さ、つまりCSRの中のより幅広い種類のスケジュールを出力しうるか。(CSRのサブセットしか出力できないなら能力が限定されている＝弱いスケジューラ)

スケジューラの大別

1. ロックベースのスケジューラ。高速に動作するし実装が容易で多くの設定に一般化可能、実用的な場面が多い。
2. ロックを使わず、それを例えばタイムスタンプやバリデーションといった概念で代用するスケジューラ。
3. 1と2を組み合わせたハイブリッド。

## スケジューラ設計の基礎

概念的に、スケジューラと協同するためのコンポーネントはTransaction Manager ( TM ) として
- クエリ実行レイヤとアクセスレイヤ、もしくは
- アクセスレイヤとストレージレイヤ

の間に配置する。上のレイヤからの呼び出しを一時停止し、CCのための必要な操作を実行したのちに下のレイヤへパスする。

それ以下のレイヤで行われるデータ操作の詳細はTMには知り得ず、その部分を仮想的に単一のコンポーネントData Manager(DM)とみなす。

TMは、trans, active, commit, abortそれぞれのリストを管理し、アクティブなトランザクションについては実行待ちのステップを保持し、それらを適当に並べた入力スケジュールをスケジューラに投げる。スケジューラはこれをserializableな出力スケジュールに変形することが仕事になる。

さらに、TMはトランザクションの終了に関しても以下を請け負う。

1. $t_i$がTMから見て正常に処理されてCommit命令を受け取ったとき、スケジューラに$c_i$を投げる。
2. $t_i$がエラーを起こすかRollback命令を受け取ったとき、スケジューラに$a_i$を投げる。

加えて、スケジューラは「どうやってもserializableでない状況」になったとき、**それ自身でトランザクションをabortすることもできる**。

スケジューラは$r,w,c,a$の4種類のステップを入力スケジュールから受け取り、以下のうち一つのアクションを起こす。

1. Output：受け取ったステップをすぐに出力する。つまり、出力スケジュールの末尾に即座に付ける。$r,w,c,a$のいずれのパターンでも許容。
2. Reject：受け取ったステップを出力しない(そのステップがserializabilityを破壊する場合)。$r,w$の場合のみ起こり得て、当該のトランザクションはabortされる。
3. Block：受け取ったステップを延期する。$r,w$の場合のみ起こりうる。($c$を許容する場合もある。COCSRにしたい場合など)

出力スケジュールに従ってDMは各操作を順番に実行する。$c$のときはトランザクションの変更を永久化するための操作を実行、$a$のときはトランザクションを巻き戻すための操作を実行する。

---

スケジューラの構造

scheduler():
var newstep, step;
state := initial_state;
repeat
    on arrival(newstep) do
        update(state);
        if test(state,newstep) then
            output(newstep);
        else
            block(newstep) or reject(newstep);
        endif
    end
end

スケジューラの出力はCSRになることを期待するわけで、もともとCSRであるような入力スケジュールは変更なくそのまま出力される、すなわちCSRのスケジュール群はスケジューラの固定点集合となることが期待される。

スケジューラの動作ではっきりさせる必要があるのは
1. スケジューラの「状態」をどの情報に基づいて定義するのか、その状態をどのように更新するのか
2. 次に起こすアクションをどのように決定するのか

受け取ったステップに対するアクションの決定方法として、たいていのステップを通しほとんどブロックしない「楽観的な」スケジューラ、多くをブロックして最悪serialにまでしうる厳しめの「悲観的な」スケジューラがある。

ロックベースのスケジューラは悲観的に属する。つまり衝突を検出したらステップを積極的にブロックする。

スケジューラの安全性を理論的に評価するための定義をしておく

### 定義：CSR安全性

スケジューラが「CSR安全」であるとは、任意の出力スケジュールがconflict serializableであることとする。

$S$をスケジューラとしたとき、$Gen(S)$をスケジューラ$S$が出力しうる全てのスケジュールの集合とする。この定義の下で、$S$がCSR安全 $\Longleftrightarrow$ $Gen(S)\subseteq CSR$