Read Papa本 Chap.1

この本の Chap.1 を復習する。 この読書会に参加した。 勉強会の当日は1章を読みきらなかったのでここには予習となった部分も含まれる。

1章では、データベースの概要や役割と並行制御がなぜ大事なのかを説明してからトランザクションやスケジューラの形式化に進む構成になっている。

ここでも概要と形式化(モデル)の説明に分けて書く。

データベースと並行制御

だいたいおさらい。

データベースが扱うデータは大きく2つの特徴がある。

• 互いに複雑な関係を持つようなデータの集約を扱う
• データは比較的長い寿命を持ち永続化される

これらのデータを高水準で統一的に扱う。 物理的なデータフォーマットと高水準の論理モデルを繋ぐシステムが必要となる。 このシステムをデータベースマネジメントシステムと呼ぶ。 SQL とかの関係論理を基礎にしたデータベースシステムを RDBMS(リレーショナルデータベースマネジメントシステム) と呼ぶ。

古い教科書でもありテープ・ストレージを永続化に想定していた(適用できるかも知れないがNVRAMは考えてなさそう)。

モデル

データベースの状態・トランザクション・トランザクションの解釈・スケジュール・スケジューラを定義する。

定義の準備

データベース(E)

データベースをエンティティ($e$)の可算集合(countable set: $E$)として定義する。

エンティティ

エンティティは以下を満たすデータベースの構成要素に対応する。

• アトミックに読み書きを行える
• 互いに共有部分が存在しない
• 分解できない
• それぞれドメインに紐づいている

上記を満たすのであれば、物理としても論理としても考えて問題ない。

ドメイン

ドメインは各エンティティに紐づく可算集合(enumerable set)で取ることのできる値を表している。 なぜデータベースは countable set でドメインは enumerable set として書かれてるかは疑問が残った。

データベースの状態

データベースの状態は、データベースの全てのエンティティに紐づくドメインに関する直積の要素として定義される。

$$s \in \Pi_{e \in E}D_e$$

シンボル	意味
$s$	データベースの状態
$D_e$	エンティティ$e$のドメイン(値域)

ここで$\Pi_{e \in E}D_e$は$D_e$の直積集合を指す。

制約

データベースの全てのエンティティに紐づくドメインの直積の部分集合。

$$C \subseteq \Pi_{e \in E} D_e$$

consitent(一貫した)

データベースの状態$s$が制約$C$の要素であることを指す。

$$s \in C$$

モデルの定義

データベースはアプリケーションと通信をする。トランザクションはその通信によって生成されると捉えて形式化している。

トランザクション: Def. 1.1

トランザクション$A$はステップ$a_i$の順序(sequence)で異なるトランザクションはステップを共有しない。

$$\begin{aligned} A &= \{a_1, a_2, ..., a_k\} \\ &a \in A \rightarrow a \notin B \\ &b \in B \rightarrow b \notin A \end{aligned}$$

ここで$A,B$はトランザクションだ。

そして全てのステップは$\{R, W\}$に紐づけられる。また同じようにエンティティ$e \in E$に紐づく。

$$\begin{aligned} &\operatorname{ACTION}(a_i) = \{R,W\} \\ &\operatorname{ENTITIY}(a_i) \in E \end{aligned}$$

この関連を含めてトランザクションは以下のような略記がある。

$$A = R(x)W(y)W(z)W(x)$$

最後に、正しいトランザクションはデータベースをコンシステントな(一貫した)状態からコンシステントな(一貫した)状態へ遷移させる。

インタプリテーション(解釈): Def. 1.2

トランザクション$A=a_1,a_2,..a_n$について以下のように解釈を定義する。 まず最初に、あるステップ($a_j$)の前に読まれているエンティティの集合($B(a_j)$)を以下のように定義する。

$$B(a_j) = \{x \in E: i \leq j, \operatorname{ACTION}(a_i) = R \land \operatorname{ENTITY}(a_i) = x \}$$

これを使ってインタプリテーションを以下のように定義する。

$$\begin{aligned} I &= (D, F) \\ D &= \underset{e \in E}{\Pi}D_e \\ F &= \{f_a: a \in A,\operatorname{ACTION}(a) = W\} \\ f_a &= \underset{x \in B(a)} {\Pi} D_x \rightarrow D \_{ \operatorname{ENTITY} (a) } \end{aligned}$$

このなかの$F$はトランザクションの影響を表現する関数の値域と定義域を表している。

本では、単純化のためにトランザクション内であるエンティティの読み込みはたかだか1回で書き込みの前に行われるという仮定を導入していた。 勉強会ではトランザクションごとにキャッシュを使えば簡単に実現できると話していた。

あるトランザクション$A$を生成したアプリケーションの動きに対応したインタプリテーション($(D,F)$)が設定できる。 逆に、インタプリテーションを定めることでトランザクションを生成したアプリケーションの意味を定義する。

トランザクションに含めるべき依存性をトランザクション外でアプリケーションが扱ってしまうと、データベースが管理できない暗黙の依存関係ができてしまうと注意されていた。 「そりゃそうだなぁ」と思っていた。

でも勉強会ではトランザクションとしては分けたいけど依存を入れたいようなことがある。 この部分は形式化が簡単に出来ないから避けてるように思える声も出ていた。 その時は「どういうことだろう」と思ったけど考えてみると、DBMSとのセッションでトランザクション順序の保証が欲しかったりする状況はこの形式化では扱えないかもと思った。

スケジュール: Def. 1.3

(ここからは予習の話)

いくつかのトランザクション$A_k$をシャッフルしたものをスケジュールと呼ぶ。 ただしスケジュール$s$は以下を満たす。

$$\forall a_i, \forall a_k, ..., a_i, ..., a_k, ... = s, i \lt j, a_i = b_k \in B, a_j = b_l \in B \rightarrow k \lt l$$

これはスケジュールの各ステップが同一トランザクション内での順序を守っていることを表している。 (この式は自作で本には書いてないので注意)

例えば、トランザクション$A,B$からなるスケジュールの具体例として以下のようなものがある。

$$s = a_1, b_1, a_2, b_2, a_3, a_4, a_5, b_3$$

続いてトランザクションのインタプリテーションを元にスケジュールのインタプリテーションを定義する。 インタプリテーション$I$はスケジュールを構成するk個のトランザクションのインタプリテーションと一貫したドメインを元に作られる。

$$I = \underset{t \in \operatorname{TRANSACTION}(s)}{\Pi} (D, F_t)$$

ここでドメイン$D$は全てのトランザクションで共有される。

スケジュールの計算はインタプリテーション$I$と初期状態$X \in \Pi_{e \in E}D_e$を組み合わせて計算する。

シリアルスケジュール

シリアルスケジュールは含まれるそれぞれのトランザクションで、各ステップが隣接している様に構成されるものを指す。トランザクション$A,B$に対して

$$s = a_1,a_2,a_3,a_4,b_1,b_2,b_3$$

といったものを指す。

シリアルスケジュールは、トランザクションが正しい(correct)のであれば、データベースを一貫した状態から一貫した状態へ遷移させる。 データベースを一貫した状態に保つことは並行制御の観点で重要なためシリアルスケジュールも重要な概念になる。

スケジューラは入力スケジュール(到着したイベント列)を受け取り、出力スケジュール(確定したリクエスト列)を生成する。これによりデータベースの並行実行での正しさを保証する責任を持つ。

単純な解決としては、あるトランザクションが完了するまで他の全てのトランザクションの進行を待てばシリアルスケジュールが生成できるため安全であるが、これは並行実行とは言えない。 どのように解決するかなどを議論する基礎を作るのが、この本の主題になる。

帰り道の話と感想

ちょっと離れるけど帰り道の雑談でMVCCでスケジュールを確定させる話について形式化などの提案はまだないよねって話があがった。

ゆるい制約の並行制御(MVCC)を実現してアボートを減らそうというのが今の流れだ。

例えば、スケジューラが DAG を維持してそれぞれのトランザクションの READ でアサインする値を調整したりする。 しかし放っておくと DAG は入力スケジュールに応じて無限に大きくなり続ける。 スケジューラが使うメモリが大きくなり、いつまでも DAG 内の様々な箇所についてトランザクションが挟み込まれる可能性が残る。

そのためどこかの時点で出力シュケジュールを確定させたい(トランザクションを挟み込まない部分を作りたい)。 でも、その方法についての提案や形式化はあまり研究されてない(ほとんどない?)らしく仕事が残っているねって話しをした。

あと、勉強会の人たちは読み終えてるけど自分はサボったり都合がつかなかったりで読めてない幾つかの教科書がある。 それらの知識を手に入れるために、ちゃんとそいつら(下の3冊)も読まなきゃなぁと思った。

• Concurrency Control and Recovery in Database Systems
• Distributed Computing: Principles, Algorithms, and Systems
• Transactional Information Systems: Theory, Algorithms, and …

$$$$