2023-04-14

【読書メモ6】詳説データベース

はじめに
所感
個別の事項メモ

はじめに

エンジニアとして正式に就職した。目指すスキル感としては

データベース技術に特化しているが、
Web開発が問題なくこなせる程度に広い知識・経験も持っている

エンジニアになりたい。

ということで、今回は近年のデータベース技術を詳しく解説している「詳説データベース」を読み、DBMSの実装の詳細と、NewSQLのような新技術の内容について理解を深めていくつもり。

重要な観点として、以前に読んだ2001年の書籍である「Transactional Information Systems」からどの程度研究開発が進歩しているかという差分にも着目したい。 TISでも分散システムにおけるトランザクション管理と回復の話はなされていたが、今ではハードウェアスペックも比べ物にならないほど上がり、またデータの分散配置の重要性も跳ね上がっているので、一番注目する話題だろう。

u-ar.hatenablog.com

所感

個別の事項メモ

1章基本事項

DBMSの設計に共通する青写真はない。コンポーネントの境界は論文上や資料には存在していても、ソースコードではパフォーマンスの最適化、エッジケースへの対応、アーキテクチャ上の決定などを理由にして分離されていないことがある
DBMSでは通常データファイルとインデックスファイルが分けられている
- データファイルにはインデックス構成表・ヒープ構成表・ハッシュ構成表というバリアントがある
  - インデックス構成表はインデックス内部にレコードも格納する形式
  - ヒープ構成表はレコード間の順序を特に決めていない形式(たいていは書き込み順に配置する)
  - ハッシュ構成表はキーのハッシュ値に基づいて決めた位置のバケットに配置する形式
- プライマリキーに基づくインデックス(プライマリインデックス)に関連して、レコードにプライマリインデックスを介してアクセスするかどうかでトレードオフが発生する
  - プライマリインデックスを参照してからレコードへアクセスする場合、
    - データ書き込み時のオーバヘッドが少ない。セカンダリインデックスはプライマリキーをポインタとして保持すればよいため。
    - ただし読み込み時にプライマリインデックスを経由するオーバヘッドが発生する。
  - プライマリインデックスを介せず、直接ポインタでレコードアクセスする場合、これと逆の利点・欠点が発生する
ストレージエンジンに用いられるデータ構造は複数出てくるが、それらの評価項目は主に3つ
- バッファリング
- ファイルの不変性
- レコードの順序付け

2章 B木の基本

だいたい知ってる話
二分探索木はディスク上のデータ構造としては使える？
- ファンアウト(ノードの子の最大数)が2しかないので更新が多いし、検索の際にたどるノード数も多いためディスク上のデータ構造としては向かない
B木とB+木の違いは、B+木は葉ノードのキーにしか値を持たせない点
- なので、B+木では、内部ノードにあるキーと同一のキーが葉にも存在する
  - 葉の分割時には内部ノードにキーを昇格するとき、コピーするのに対し、
  - 内部ノードの分割時には単に移動する

3章バイナリエンコーディング

ファイルフォーマットの設計がディスク上のデータに対する操作の効率に影響する
スロット化ページ (PostgreSQLなど多くで採用される)
- ページをポインタと実際のレコードを格納するセルの領域に分ける
  - ポインタは各レコードが実際に格納されるセルを指す
  - ポインタはページの先頭側から、それが指すセルはページの終端側から詰め込んでいく
    - キーのソートを維持するにはポインタの方を並び替えればよいので、セルはそのままでよい
  - セルを削除して生じた空き領域は、メモリ上の利用可能リストに登録し、新しくセルを挿入するときにまず利用可能リストを参照して空きがあれば入れる
- 利点
  - オーバヘッドを最小に抑えながら可変長レコードを格納できる
  - 削除されたレコードが使用していた領域を回収できる
  - 実際の配置に関わらずページ内のレコードを参照できる

4章 B木の実装

B木をディスク上に実装する際の諸々
キーやレコードが大きくて1ノードの全てが1ページに収まらなかったとき、オーバーフローページを割り当てる
- プライマリページから始まる連結リストの形をとる
プライマリキーでB木を構成する場合、新しいデータは最も右にしか挿入されないのでノード分割の必要がない
- 単に新たに右の葉を作ればよい

5章トランザクション処理とリカバリ

多くのDBMSは0_DIRECTフラグを利用してファイルを開く→OSカーネル特有のページキャッシュをバイパスしてアクセスすることが可能
- OS側のエンジニアはカーネルの目をかいくぐるこのやり方に不満らしいが、
- DBMSは勝手にキャッシュを退避されたくないのでOSがもっと賢くなるまではこうするしかない
- キャッシュ機構の被りというのは実際気になってたことだったのだが、結局対立してて笑った
読書中...

2023-02-28

Transactional Information Systems 第６章演習問題解答

データベース

Transactional Information Systemsにおける第６章演習問題の自分なりの解答。

間違っていたらご指摘ください。

hackmd.io

6.1 Q

図6.12の2層スケジュールはtree reducibleか？

6.1 A

$t_1, t_3$ の高レベル操作 $Withdraw_1(a), GetBalance_3(a)$ が非可換であり、その一方、ページレベルではそれらの子の操作である $r_3(p), w_1(p)$ が逆向きかつ非可換なのでtree reducibleでない。

6.2

3層スケジュールを描く問題なので略。

6.3 Q

図6.2の2つのスケジュールについて、それぞれtree reducibleか？

6.3 A

一つ目はtree reducibleである。

ページレベルの $w_1(t), w_2(t)$ が非可換なので、reducibleになるとしたら $t_1 \lt t_2$ という順である。

$Withdraw_1(a)$ 直下の $w_1(p)$ や $w_1(t)$ はページレベルの可換性で手前に出せる。 $Deposit_1(c)$ は高レベルの可換性を用いて $Withdraw_2(b), Deposit_2(c)$ と入れ替えて手前に出せる。

二つ目もtree reducibleである。

根直下の $w_2(r) \lt w_1(r)$ から、reducibleになるとしたら $t_2 \lt t_1$ である。 $Withdraw_1(a), Withdraw_2(b)$ はそれぞれ部分木をisolatedにできるので、それらが可換なことを合わせて $t_2$ を手前に出せる。

6.4 Q

図6.6のスケジュールを実際に既約にせよ。

6.4 A

まず $CheckItem_1$ の部分木をページレベルの可換性で手前に出してisolatedにする。
同様に $Payment_2$ の部分木をページレベルの可換性で手前に出してisolatedにする。
枝刈り規則に基づき、のみが残り、それ以下の部分木は全て枝刈りされる。
- ここでは $CheckItem_1CheckItem_2Shipment_1Payment_2Payment_1$ となっている。
これらの高レベル操作は互いに可換なので並び替えて $CheckItem_1Shipment_1Payment_1CheckItem_2Payment_2$ を得る。

6.5 Q

図6.13の階層的なスケジュールについて、tree reducibleか？conflict faithfulか？

各層間スケジュールはそれぞれCSRか？OCSRか？

6.5 A

tree reducibleである。

$d_2(\mu')$ をisolatedにできるので、可換性に基づいて $d_2(\mu')$ を末尾にも先頭にも動かせる。よってtree reducible。

conflict faithfulである。

高レベル操作のうち非可換なのは $m_1(a), m_2(a)$ のみで、その直下の操作 $w_1(q), w_2(q)$ が競合しているため。

層間スケジュールはOCSR。

CSRは明らかだし、競合の順が出現順と矛盾することもないのでOCSR。

6.6 Q

返り値に基づく可換性の表を以下の操作について作成せよ。

increment：カウンタを加算し、上限を超えていないならOK、超えていたらカウンタを変更せずにNOを返す。
decrement：カウンタを減算し、下限を下回っていないならOK、下回っていたらカウンタを変更せずにNOを返す。
getvalue：カウンタの値を取得する。

6.6 A

	Inc:OK	Inc:NO	Dec:OK	Dec:NO	Getvalue
Inc:OK	○	✕	✕	○	✕
Inc:NO	○	○	✕	○	○
Dec:OK	✕	○	○	✕	✕
Dec:NO	✕	○	○	○	○
Getvalue	✕	○	✕	○	○

6.7 Q

FIFOキューが返り値可換性に基づいて高い並列性を実現できるようなスケジュールの例を考えよ。

6.7 A

最初から多くの要素を持つFIFOキュー $q$ において、多くのトランザクションによる $enq(q,~)$ と $deq(q)$ が大量に混ざったスケジュールを考える。

このとき、enqueueとdequeueは返り値がOKになるので相互に可換であり、enqueueどうし、dequeueどうしの順番さえ変えなければそれ以外の順番は自由に決めることができ、並列性が高くなる。

6.8 Q

semi-queue (dequeueにより取り出す要素が非決定的であるキュー) における操作の可換性を示し、これが高い並列性を実現するスケジュールの例を示せ。

6.8 A

	Enq:ok	Enq:one	Deq:ok	Deq:empty
Enq:ok	○	imp	✕	imp
Enq:one	✕	imp	✕	✕
Deq:ok	✕	✕	○	✕
Deq:empty	✕	✕	imp	○

通常のFIFOキューと比較すると、enqueueとdequeueが非可換になった代わりに、enqueueどうし、dequeueどうしが可換になっている。

したがって、多くのトランザクションによるenqueueだけが大量にあるスケジュールにおいて、どの順番で実行しても良いため極めて並列性が高くなる。dequeueについても同様。

6.9 Q

$s = enq_1(q,a)enq_2(q,b)deq_3(q)enq_1(q,c)deq_3(q)$

において、

(a) 一般の可換性に基づいて考えるとserializableか？

(b) キューの返り値可換性で考えるとserializableか？

6.9 A

(a) 一般の可換性で考えるとserializableでない。

一般の可換性では、 $enq(q,~), deq(q)$ は競合する操作であり非可換で、したがって逐次的なスケジュールにできない。

(b) キューの返り値可換性で考えるとserializableでない。

返り値も含めてスケジュールを書き直すと

$s = enq_1(q,a):one\rightarrow enq_2(q,b):ok\rightarrow deq_3(q):ok\rightarrow enq_1(q,c):ok \rightarrow deq_3(q):ok$

$deq_3(q)$ を $enq_1(q,c)$ と入れ替えて後ろに出す。その後、 $enq_2(q,b)$ は前後の $t_1$ の操作と非可換なので行き詰まる。

(c) semi-queueの返り値可換性で考えるとserializableでない。

$enq, deq$ が交互にあり、これらすべてsemi-queueにおいては非可換なので括り出せない。

結局どの可換性に基づいてみてもserializableでない。

6.10

メールボックスのADTをデザインせよ。略。

6.11 Q

預金の引き出し操作は、預金には下限が存在するため一般に非可換であると考えられる。

これを実質的に可換にするために、預金が0を下回った場合でも引き出しを許す代わりに一定額のペナルティを課すこととする。

relaxed_withdraw(x, delta) {
  x.balance = x.balance - delta;
  if (x.balance < 0) x.balance = x.balance - 10;
}

一般的な可換性のもとではserializableでないが、この緩和されたwithdrawのもとでserializableになるようなスケジュールを考えよ。

また、アプリケーションとしての観点から、銀行とユーザにとってこの変更が受け入れられるか考えよ。

6.11 A

$Withdraw_1(a,10)Withdraw_2(a,10)Withdraw_2(b,30)Withdraw_1(b,30)$

というスケジュールを考えると、一般的な意味の可換性ではこれはserializableでないが、緩和されたwithdrawのもとではserializableになる。

このような緩和の問題点は以下。

預金の下限を無くすことで無限の借金が可能になってしまっている。
- この方法で可換性を保証するためには、極論100億ドル一気に引き出されても断れない。
  - なので現実的に無理。
ユーザとしても、預金がマイナス時に引き出しの全てにペナルティがかかるのは困る。

u-ar.hatenablog.com

2023-02-27

Transactional Information Systems 第５章演習問題解答

データベース

Transactional Information Systemsにおける第５章演習問題の自分なりの解答。

間違っていたらご指摘ください。

hackmd.io

5.1 Q

以下の3つの履歴について、MVSRやMCSRに属するか、MVSRなら必要なバージョン数についても判定せよ。

$m_1=w_0(x_0)w_0(y_0)w_0(z_0)c_0r_3(x_0)w_3(x_3)c_3w_1(x_1)c_1r_2(x_1)w_2(y_2)w_2(z_2)c_2$

$m_2=w_0(x_0)w_0(y_0)c_0w_1(x_1)c_1r_3(x_1)w_3(x_3)r_2(x_1)c_3w_2(y_2)c_2$

$m_3=w_0(x_0)w_0(y_0)c_0w_1(x_1)c_1r_2(x_1)w_2(y_2)c_2r_3(y_0)w_3(x_3)c_3$

5.1 A

$m_1$

モノバージョンスケジュール $t_0t_3t_1t_2$ とreads-from関係が等しいので $m_1\in MVSR$ 。適切な $t_\infty$ は $t_\infty = r_\infty(x_1)r_\infty(y_2)r_\infty(z_2)$ 。

$m_1$ からバージョン表記を取り除いてもreads-from関係が変わらないので $m_1\in VSR$ ですらある。

$m_2$

モノバージョンスケジュール $t_0t_1t_2t_3$ とreads-from関係が等しいので $m_2\in MVSR$ 。適切な $t_\infty$ は $t_\infty = r_\infty(x_3)r_\infty(y_2)$ 。

バージョン表記を取り除いた場合は、 $c_3$ を手前に出すだけで逐次的なスケジュール $t_0t_1t_3t_2$ になるので $m_2\in VSR$ ですらある。

$m_3$

モノバージョンスケジュール $t_0t_3t_1t_2$ とreads-from関係が等しいので $m_3\in MVSR$ 。適切な $t_\infty$ は $t_\infty = r_\infty(x_1)r_\infty(y_2)$ 。

バージョン表記を取り除いた場合は、もとから逐次的なスケジュールなので $m_3\in VSR$ ですらある。

5.2 Q

マルチバージョンスケジュール

$m=w_0(x_0)w_0(y_0)c_0r_1(x_0)w_1(x_1)r_2(x_1)w_2(y_2)w_1(y_1)w_3(x_3)$

について、 $MVSG(m,\ll)$ が閉路を持たないような $\ll$ が存在するか判定せよ。

5.2 A

$MVSG(m,\ll)$ において、reads-from関係に基づく辺は $t_0\rightarrow t_1\rightarrow t_2$ のみである。

これに辺が追加された際に閉路を生まないような $\ll$ を考えればよい。

MVSGにおける辺追加規則を振り返ると、 $w_j(x_j), r_k(x_j), w_i(x_i)$ があるとき

$t_j\rightarrow t_k$ は常にある (reads-from関係に基づく辺)

$x_i \ll x_j$ なら $t_i\rightarrow t_j$

$x_j \ll x_i$ なら $t_k\rightarrow t_i$

reads-from関係以外で辺を生じうる操作の組み合わせは

$w_0(x_0), r_1(x_0), w_3(x_3)$
$w_1(x_1), r_2(x_1), w_0(x_0)$
$w_1(x_1), r_2(x_1), w_3(x_3)$

$x_0$ がバージョン順で最小であることは自明である。よって、前者二つは $t_1\rightarrow t_3$ 、 $t_0\rightarrow t_1$ という辺を生む。

次に、3つ目の組み合わせは

$x_3 \ll x_1$ なら $t_3\rightarrow t_0$ という辺が生じる。閉路 $t_0\rightarrow t_1 \rightarrow t_3\rightarrow t_0$ が生じるのでダメ。
$x_1 \ll x_3$ なら $t_1\rightarrow t_3$ という辺が生じる。

よって、 $x_1 \ll x_3$ を満たすバージョン順ならば条件を満たす。

全順序を適当に定めて $x_0\ll x_1\ll x_2\ll x_3$ が答えになる。

5.3 Q

no blind writes モデル (データアイテムに書き込む前に必ず読み込まなければならないモデル) では $MCSR=MVSR$ であることを示せ。

5.3 A

$MCSR \subseteq MVSR$ は一般に成り立つので、追加で $MVSR\subseteq MCSR$ を示せばよい。

$m\in MVSR$ な $m$ を考える。逐次的なモノバージョンスケジュール $m'$ が存在して $RF(m)=RF(m')$ となる。

ここで、 $m$ がMCSRの意味でも $m'$ へ帰着できること、すなわち $r_j(x_k) \lt_m w_i(x_i) \Rightarrow r_j(x_k) \lt_{m'} w_i(x_i)$ を示せばよい。

$r_j(x_k)\lt_m w_i(x_i)$ だが $w_i(x_i)\lt_{m'} r_j(x_k)$ と仮定して矛盾を導く。

$m'$ において、 $t_i$ はno blind write性より、ある直近の書き込み $w_l(x_l)$ から読み込む。また、 $t_j$ は、 $r_j(x_k)$ があることから、直近の書き込み $w_k(x_k)$ から読み込む。仮定 $w_i(x_i)\lt_{m'} r_j(x_k)$ と合わせて、これら関連するトランザクションの逐次実行順は

$t_l\rightarrow t_i\rightarrow t_k\rightarrow t_j$

$m'$ がモノバージョンであることから、 $t_l\rightarrow t_i$ と $t_k\rightarrow t_j$ の間には $x$ の書き込みは挟まらない。

ここで $t_k$ はある直前の $x$ への書き込み $w_p(x_p)$ から読み込んでおり、no blind write性から $t_p$ もまた直前の $x$ への書き込みから読み込む。再帰的に考えて、すべてreads-from関係からなる連鎖

$t_l\rightarrow t_i\rightarrow t_{p_1} \rightarrow \cdots\rightarrow t_{p_q}\rightarrow t_k\rightarrow t_j$

が $m'$ において生じていることが分かる。 $RF(m)=RF(m')$ なので、このreads-from関係がすべて $m$ でも成り立つ。したがって

$w_i(x_i)\lt_{m}\cdots \lt_{m} r_j(x_k)$ であり、これは仮定 $r_j(x_k)\lt_m w_i(x_i)$ に反するため矛盾。

以上より $m\in MCSR$ である。 $\square$

5.4 Q

action モデル (各ステップは同一データアイテムへの読み込み＋書き込みからなる) ではMVSR=VSRであることを示せ。

5.4 A

$VSR \subseteq MVSR$ は既に示されているので、あとは $MVSR\subseteq VSR$ を示せばよい。

$m\in MVSR$ を考える。逐次的なモノバージョンスケジュール $m' = t_1t_2\cdots t_n$ が存在して、 $RF(m)=RF(m')$ である。actionモデルであることから、各データアイテムへのactionについて、直前のactionと直後のactionとの間にreads-from関係が必ず存在する。

これが $m$ でも成り立つことから、 $m$ からバージョンを落としたスケジュール $s$ でもこの関係が変化せず、また $m'$ もモノバージョンスケジュールなのでバージョンを落とした $s'$ でも関係が変化しないので $RF(s)=RF(s')$ である。したがって $m \in VSR$ 。 $\square$

5.5 Q

バージョンの定義されていない古典的なスケジュール

$s=r_1(x)r_2(x)r_3(y)w_2(x)w_1(y)c_1w_2(z)w_3(z)r_3(x)c_3r_2(y)c_2$

がマルチバージョンの意味でserializableなことを示し、適切なバージョン順を与えよ。

MVTOや2V2PLプロトコルではどのように処理されるか？

5.5 A

そのままだとreads-from関係が閉路を作るのでVSRでない。

一方、バージョン関数を与えて

$s=r_1(x_0)r_2(x_0)r_3(y_0)w_2(x_2)w_1(y_1)c_1w_2(z_2)w_3(z_3)r_3(x_0)c_3r_2(y_1)c_2$

とすればモノバージョンスケジュール $t_1 t_3 t_2$ とreads-from関係が等しいのでMVSR。

MVTOでの処理

開始順から $ts(t_1) \lt ts(t_2) \lt ts(t_3)$ 。

操作に適宜バージョンが割り当てられていき、

$r_1(x_0)r_2(x_0)r_3(y_0)w_2(x_2)$ → $w_1(y)$ が拒否されて $t_1$ が中止 → $w_2(z_2)w_3(z_3)r_3(x_2)c_3r_2(y_0)c_2$

と進む。

2V2PLでの処理

$t_1$ のコミット時点で、 $x$ へのread lock、 $y$ へのwrite lockを保持し、certify lock待ちで $t_3$ にブロックされる。 $w_2(z)$ が実行され、write lockが競合するので $w_3(z)$ はブロックされる。ブロックされていないのは $t_2$ だけになるが、これも $x$ のcertify lock待ちで $t_1$ にブロックされ、デッドロックとなる。

5.6 Q

$s=w_1(x)c_1r_2(x)r_3(x)c_2r_4(x)w_3(x)c_4c_3$

はMVTOでどのように処理されるか？

5.6 A

開始順から $ts(t_1) \lt ts(t_2) \lt ts(t_3) \lt ts(t_4)$ 。

$w_1(x_1)c_1r_2(x_1)r_3(x_1)c_2r_4(x_1)$ まで実行され、 $w_3(x)$ は $r_4(x_1)$ が既にスケジューリングされているので不正、 $t_3$ が中止される。最後に $c_4$ 。

5.7 Q

$s=r_1(x)w_1(x)r_2(x)w_2(y)r_1(y)w_2(x)c_2w_1(y)c_1$

は2V2PLでどのように処理されるか？

5.7 A

$w_1(x), w_2(y), w_2(x), w_1(y)$ の順で並んでいるので、write lockによるデッドロックが起こり、どちらかが中止される。

5.8

MVTO, 2V2PL, ROMV の正当性。HackMD読書ノートに記載している。

5.9

ROMVにおいて、updaterトランザクションのスケジューリングを緩和した際の正当性について。HackMD読書ノートに記載している。

u-ar.hatenablog.com

2023-02-26

Transactional Information Systems 第８章演習問題解答

データベース

Transactional Information Systemsにおける第８章演習問題の自分なりの解答。

間違っていたらご指摘ください。

hackmd.io

8.1 Q

述語ロック (predicate locking) はOR条件や結合条件にどのように拡張できるか。

ORの例：

select name from emp 
where position = 'manager' or department = 'research';

結合の例：

select emp.name, emp.department from emp, dept
where emp.position = 'manager' and dept.city = 'Toronto' 
and emp.department = dept.department;

8.1 A

ORの方は、position='manager'とdepartment='research'に同時に述語ロックをかければよい。

結合については、empをposition='manager'で、deptをcity='Toronto'でロックすればよい。

8.2 Q

IDM トランザクションにおいては、履歴の各リレーションへの射影がserializableでも全体がserializableになるとは限らないことを、以下の反例を用いて示せ。

$t_1=m^R(A=1;A=2)m^S(C=5;C=6)$ $t_2=m^R(A=2;A=3)m^S(C=4;C=5)$ $s=m^R_1(A=1;A=2)m^R_2(A=2;A=3)m^S_2(C=4;C=5)m^S_1(C=5;C=6)$

8.2 A

スケジュール $s$ のRへの射影、Sへの射影は逐次的だが、 $s$ そのものは $t_1, t_2$ の競合が閉路を作っているのでserializableでない。

8.3 Q

IDM トランザクションから、Modify操作を除外してInsert, Deleteのみのモデルを考える。

(a) Modify操作はDelete+Insertで代替できないことを示せ。

(b) $s=i_1(1)d_2(1)i_2(2)d_1(2)i_3(1)i_3(2)\in FSR_{IDM}-CSR_{IDM}$ を示せ。

8.3 A

(a) Modify操作はDelete+Insertで代替できないことを示せ。

もともと存在していないタプルをModifyする操作をDelete+Insertに置き換えてしまうと、
- 本来のModifyでは新しいタプルは作られない
- Delete+Insertでは新しいタプルが作られてしまう

(b) $s=i_1(1)d_2(1)i_2(2)d_1(2)i_3(1)i_3(2)\in FSR_{IDM}-CSR_{IDM}$ を示せ。

$t_1t_2t_3$ を逐次的に実行した場合と最終的な状態が同じ (タプル1も2も存在する) なのでFSRに属する。

一方、 $i_1(1)\rightarrow d_2(1), i_2(2)\rightarrow d_1(2)$ がそれぞれ競合しているのでCSRでない。

(c) IDトランザクションのみの場合、 $FSR_{IDM}$ の所属は多項式時間で判定できることを示せ。

与えられたスケジュールの実行結果と同じ結果を生む逐次的なスケジュールを見つけたい。多項式時間で判定するには、全ての並びを総当たりで調べることはできない。

そこで、必要な最終結果に矛盾しないトランザクションを貪欲的に選び、それを最後に実行するよう順次スケジュールすることを考える。

まず、与えられたスケジュールを先頭から末尾までスキャンしてみて、挿入されたタプルの集合Iと削除された (挿入されなかった) タプルDを分類する。
すべてのトランザクションの中から、InsertをD内のタプルに行わず、かつDeleteをI内のタプルに行わない (=最終結果と矛盾しない) トランザクションをなんでもいいので一つ選び出し、それを最後に実行することに決める。このトランザクションがInsertしたI内のタプル、およびDeleteしたD内のタプルは、それ以前のトランザクションではどう扱ってもいいので、新たに任意操作可能なタプルの集合Nに分類し直す。
残りのトランザクションも、InsertをD内のタプルに行わず、かつDeleteをI内のタプルに行わないトランザクションを任意に選んでスケジュールしていく。Nにいったん分類されたタプルに対してはどんな操作でもよい。
この過程ですべてのトランザクションを選ぶことができたら、実行結果がもとのスケジュールと矛盾していないのでFSRに属する。
逆にそのようなトランザクションを選ぶことができなかったら、どのような並べ方をしても少なくとも一つ矛盾する結果になるタプルが存在してしまうのでFSRに属さない。

貪欲的にトランザクションを選択しているので多項式時間で実行可能である。一つスケジュールの順を決めるたび、すべてのトランザクションについて、すべての操作が矛盾しないか判定するわけなので、時間のオーダーとしてはざっくり $O(n^3)$ を超える。

8.4

冒頭に記載のHackMDリンク先の読書ノート、８章のページに記述している。

8.5 Q

IDM トランザクションについて以下を示せ。

(a) $FSR_{IDM}$ が単調でないこと。

(b) $FSR_{IDM}$ が prefix commit closed でないこと。

(d) $ECSR_{IDM}$ が単調であること。

(e) $CSR_{IDM}$ も $ECSR_{IDM}$ も prefix commit closed であること。

※Aが単調：Aに属する任意のスケジュールについて、すべての射影がAに属すること。 ※Aがprefix commit closed：Aに属する任意のスケジュールについて、コミット射影の任意のプレフィクスがAに属すること。

8.5 A

(a) $FSR_{IDM}$ が単調でないこと

$s=m_1(1;2)m_2(2;3)m_1(3;4)d_3(1)d_3(2)d_3(3)d_3(4)$

は最終状態が $t_1t_2t_3$ と等しいのでFSRだが、 $t_3$ を除いた瞬間にFSRでなくなる。よってFSRは単調でない。

(b) $FSR_{IDM}$ が prefix commit closed でないこと

(a)より。

(c) $CSR_{IDM}$ が単調であること

射影により、conflict graphにおける頂点が減るだけなので非閉路存在性は単調である。

(d) $ECSR_{IDM}$ が単調であること

(c)と同じ。

(e) $CSR_{IDM}$ も $ECSR_{IDM}$ も prefix commit closed であること

conflict graphにおける頂点と辺が減るだけなので、もとでacyclicならコミット射影のプレフィクスでもまたacyclic。

8.6 Q

IDM トランザクションモデルにSELECT操作を導入し、適切な可換性を追加で定義せよ。

8.6 A

タプル集合 $C$ をSELECTする操作 $s(C)$ を新たに定義する。

最終状態には一切関係しないためFSRには影響を与えず、またlost updateなどの可能性があるため適切でもない。

一方、操作間の可換性に基づくCSRの定義は、 $s(C)$ を含むように拡張することが可能である。

$s(C_1)i(C_2)\approx i(C_2)s(C_1)~(C_1\cap C_2=\emptyset)$
$s(C_1)d(C_2)\approx d(C_2)s(C_1)~(C_1\cap C_2=\emptyset)$
$s(C_1)m(C_2;C_3)\approx m(C_2;C_3)s(C_1)~(C_1\cap C_2=\emptyset, C_1\cap C_3=\emptyset)$
$s(C_1)s(C_2)\approx s(C_2)s(C_1)$

8.7 Q

例8.13のトランザクションにおいて、 $t_{11}$ のさらなる分割はもはや正当なトランザクション分割を生まないことを示せ。

8.7 A

分割して $t_{111}, t_{112}$ にすると、 $t_2$ との間でsc閉路が生じるので正当でない。

8.8 Q

$t_1 = r_1(x)w_1(x)r_1(y)w_1(y)$

$t_2 = r_2(x)$

$t_3 = r_3(y)w_3(y)$

$t_1$ を3つのトランザクションに分割せよ。

8.8 A

$t_1 = r_1(x)|w_1(x)|r_1(y)w_1(y)$ が正当な分割。

8.9 Q

定理8.5を示せ。

（分割グラフがsc閉路を持たないとき、そのトランザクション分割が正当であること）

8.9 A

対偶を示す。トランザクション分割が正当でないと仮定する。このとき、各トランザクション片がCSRスケジューラに基づいて制御されたスケジュールのうち、逐次的なスケジュールとconflict equivalentでないようなものが存在する。

これは、各トランザクション片を独立なトランザクションとみたときにはconflict graphに閉路が存在しないが、同じトランザクションに由来するトランザクション片の頂点を全て縮約すると閉路が生まれることを意味する。

これを分割グラフで見ると、異なるトランザクション間の競合に由来する $c$ 辺だけでは閉路が存在しないが、それに同じトランザクションに由来する片間に引かれる $s$ 辺を加えると閉路が生まれることを意味する。少なくとも一つずつ $c$ 辺も $s$ 辺も含まれるので、sc閉路が存在する。

8.10 Q

分割されたトランザクション群がsc閉路を持つとき、トランザクションをそれ以上分割しても分割グラフはacyclicにならないことを示せ。

8.10 A

sc閉路に属するトランザクション片をさらに分割しても下図のケースのいずれかになり、結局sc閉路は存在する。

8.11 Q

パラメータを持つプロシージャpurchase(i,p)を考える。

if (p > cash) rollback;
else inventory[i] = inventory[i] + p;
cash = cash - p;

どのような条件、どのような範囲でトランザクション分割が適用できるか？

8.11 A

inventory[i] = inventory[i] + p; と cash = cash - p; の間で、p + q < cash かつ i≠j であるような purchase(j,q) を混ぜることは許容される。

u-ar.hatenablog.com

2023-02-25

Transactional Information Systems 第１９章演習問題解答

データベース

Transactional Information Systemsにおける第１９章演習問題の自分なりの解答。

間違っていたらご指摘ください。

hackmd.io

18.1 Q

単一障害仮定の下で独立な障害回復を達成する2PC(2相コミットプロトコル)の状態遷移図を描け。

18.1 A

本書では上図の状態遷移で可能って書いてあるけれど、これでは矛盾しない独立な障害回復は無理では？

具体的な反例として、全参加者(Participant)で準備が完了してyesメッセージを送信してPrepared状態に遷移し、調整者(Coordinator)がそれを受け取ってBuffer状態に遷移した状況を考える。

ここで、調整者が送ったcommitメッセージを参加者1が受け取る前にクラッシュしたとする。このとき、参加者1は回復時に独立にAbortedに遷移し、それを検知した調整者もAbortedに遷移するが、commitメッセージを受け取った他の参加者はCommitted状態に遷移してしまい、これは最終状態なので後から変更されることはない。

→障害が参加者1でしか起こっていないのに矛盾した最終状態になっている。やっぱり駄目では？何かご存知の方、お教えいただければ幸いです。

19.2 Q

プロセス木が以下の図のように形成されていたとき（PC：クライアント、TA：旅行代理店、TW：Travel Wholesaler(旅行業者？)、RC：レンタカー会社、AX：航空会社）、

(1) 階層的な2PCにおけるメッセージの流れと作成されるログは？

(2) どのような最適化を施せるか？

(3) 調整者の役割がTAに委譲された場合、2PCのコストはどうなるか？

(4) 階層的な2PCにおいて、A3がコミットできずnoを投票した場合の処理は？

(5) presumed-abort(PA)の2PCにおいて、A3がコミットできずnoを投票した場合の処理は？

19.2 A

(1) 階層的な2PCにおけるメッセージの流れと作成されるログは？

根ノードのPCから開始し、矢印を辿りながら各プロセスにコミット準備を要求していくことになる。返信は逆向きに根へさかのぼる。

最適化を考えない基本的な2PCにおいては、以下のような流れを辿る。緑がログエントリのファイルへの書き出し、橙がプロセス間のメッセージを指す。

PC：force-begin
PC→TA, RC：prepare
TA：force-begin
TA→TW, A3, A4：prepare
TW：force-begin
TW→A1, A2：prepare
A1, A2：force-prepared
A1, A2→TW：yes
A3, A4, TW：force-prepared
TW, A3, A4→TA：yes
TA, RC：force-prepared
TA, RC：yes
ここまで投票フェーズ、ここから決定フェーズ
PC：force-commit
PC→TA, RC：commit
TA, RC：force-commit
TA→TW, A3, A4：commit
TW, A3, A4：force-commit
TW→A1, A2：commit
A1, A2：force-commit
A1, A2→TW：ack
TW, A3, A4→TA：ack
TA→PC：ack
PC：end

ログのforce-writeは18個、メッセージは28個となる。

これを一般化すると、ノード総数が $n$ 、内部ノード(葉でないノード)数が $i$ とするとき、

force-writeは個
- force-beginが $i$ 個
- force-preparedが $n-1$ 個
- force-commit/abortが $n$ 個
メッセージ数は個
- prepareメッセージが $n-1$ 個
- yes/noメッセージが $n-1$ 個
- commit/abortメッセージが $n-1$ 個
- ackメッセージが $n-1$ 個

(2) どのような最適化を施せるか？

presumed-abort(PA)とpresumed-commit(PC)の2種類でロギングとメッセージングのコストを減らすことを考える。それぞれ、最終的な決定に関する情報が手に入らないときのデフォルトの挙動を決めておくことでコストを減らす手法であり、PAはデフォルトでアボートするバリアント、PCはデフォルトでコミットするバリアントである。

PA
- ロギング
  - beginログエントリのforceが不要になる。回復時に無かったらアボートにして問題ないため。
  - preparedログエントリのforceは必要である。
  - commitログエントリのforceは必要だが、rollbackログエントリは不要である。回復時に無かったらアボートにするため。
- メッセージ
  - コミットの際は基本2PCと同様、commitメッセージとackメッセージの返信が必要である。
  - アボートの際はabortメッセージは必要だが、ackメッセージの返信は不要である。メッセージが届いたことを確認しなくてもアボートしていることを期待できるため。
PC
- ロギング
  - beginログエントリのforceは必要である。無い→ログがGCされているのでデフォルトの動作としてコミットしたものとして取り扱う、あるが終了していない→投票を再開する、と動作を分岐させる必要があるため。
  - preparedログエントリのforceは必要である。
  - commitログエントリのforceは、根でのみ必要である。これは投票の結果がコミットになり決定フェーズに移ったことを記録するため。他のノードは全てデフォルトでコミットすればよいのでforceする必要がない。
  - rollbackログエントリのforceは全ノードで必要である。
- メッセージ
  - コミットの際はcommitメッセージが必要だが、ackメッセージの返信は不要である。
  - アボートの際は基本2PCと同様、abortメッセージとackメッセージの返信が必要である。

これをすべて踏まえて以下を得る。PNはpresumed-nothing、何もデフォルト動作を定めない基本の2PCのことを指す。

PN	commit	abort
force-log	$2n-1+i$	$2n-1+i$
message	$4(n-1)$	$4(n-1)$

PA	commit	abort
force-log	$2n-1$	$n-1$
message	$4(n-1)$	$3(n-1)$

PC	commit	abort
force-log	$n+i$	$2n-1+i$
message	$3(n-1)$	$4(n-1)$

内部ノード数 $i$ はよほど直線的な木でない限りはそれなりに小さくなること、トランザクションはコミットされるものがほとんどであることを踏まえると、ロギング・メッセージ双方の観点でPCプロトコルが優れていると考えられる。

(3) 調整者の役割がTAに委譲された場合、2PCのコストはどうなるか？

内部ノード数が $i=3$ のままなので、ログとメッセージの数自体は変わらない。ただし、木の最大深さが2と浅くなるので、メッセージが往復する時間がやや短くなる可能性がある。

(4) 階層的な2PCにおいて、A3がコミットできずnoを投票した場合の処理は？

A3→TA：no
TA→PC：no
PC：force-rollback
以下abortメッセージの通知とforce-rollback、ackメッセージの返信の繰り返し

(5) presumed-abort(PA)の2PCにおいて、A3がコミットできずnoを投票した場合の処理は？

(4)と違い、force-rollbackは行われないしackメッセージも不要。

19.3 Q

深さ $n$ の完全二分木 (ノード数 $m=2^n - 1$ ) において、PN/PA/PCの各コストを求めよ。

(1) 全ノードが書き込み操作を含むときのコミット/アボート時のコスト。

(2) 根以外のノードがすべてread-onlyなとき、コミット時のコスト。

(3) 葉ノードがすべてread-onlyなとき、コミット時のコスト。

19.3 A

(1) 全ノードが書き込み操作を含むときのコミット/アボート時のコスト

内部ノード数 $i=2^{n-1}-1 = \frac{1}{2}(m-1)$ なので、これを前問の表に代入して

PN	commit	abort
force-log	$\frac{1}{2}(5m-3)$	$\frac{1}{2}(5m-3)$
message	$4(m-1)$	$4(m-1)$

PA	commit	abort
force-log	$2m-1$	$m-1$
message	$4(m-1)$	$3(m-1)$

PC	commit	abort
force-log	$\frac{1}{2}(3m-1)$	$\frac{1}{2}(5m-3)$
message	$3(m-1)$	$4(m-1)$

(2) 根以外のノードがすべてread-onlyなとき、コミット時のコスト

根以外のノードがすべてread-onlyなとき、投票フェーズにおけるすべての返信がread-onlyメッセージになる。それ以降はやり取りが行われないので

	PN	PA	PC
force-log	$\frac{1}{2}(3m-1)$	$m$	$\frac{1}{2}(3m-1)$
message	$2(m-1)$	$2(m-1)$	$2(m-1)$

(3) 葉ノードがすべてread-onlyなとき、コミット時のコスト

commitメッセージは葉ノードの手前まで送られ、PAにおいてはそこからackメッセージが根まで返信される。葉ノードの数が $i+1=\frac{1}{2}(m+1)$ 個であることも含めて

	PN	PA	PC
force-log	$2(m-1)$	$\frac{3}{2}(m-1)$	$\frac{1}{2}(3m-1)$
message	$3m-5$	$3m-5$	$\frac{1}{2}(5m-7)$

19.4 Q

last-agent最適化を施し、調整者を委譲していく際のPC/PA プロトコルのシーケンス図を描け。

19.4 A

ブログ上で見やすいように解答を加工するのは疲れるが楽しさもある。

u-ar.hatenablog.com

2023-02-25

Transactional Information Systems 演習問題解答まとめ

データベース

Transactional Information Systems の演習問題解答をまとめたエントリ。

章ごとに1エントリ使って解答していて、投稿順もばらけているので、整理して一括でアクセスできるページを改めて整備する目的。

1章、2章は導入部なので解答略。20章には演習問題がない。

よって3-19章を揃えることが最終目標になる。グラフィカルに解答する必要があるものも多いので時間はかかる。

Transactional Information Systems 第１８章演習問題解答

データベース

Transactional Information Systemsにおける第１８章演習問題の自分なりの解答。障害回復の章は重そうなので後回しで、分散トランザクションの話題から。

間違っていたらご指摘ください。

hackmd.io

18.1

例示された半順序スケジュールの実行手順を記述する問。グラフィカルなので略。

18.2 Q

CSRでないグローバルなスケジュールが分散2PLに従って処理される例を記述せよ。

18.2 A

アイテムxを持つサーバ1とyを持つサーバ1にまたがるグローバルトランザクション $s=r_1(x)w_2(y)w_2(x)r_1(y)c_1c_2$ はこれ自体CSRではない。

各サーバでの処理順は

サーバ1： $rl_1(x)$ → $r_1(x)$ → $wl_2(x)$ がブロックサーバ2： $wl_2(y)$ → $w_2(y)$ → $rl_1(y)$ がブロック

両者ブロックされたことでxとyでデッドロックが検出されるのでどちらかがアボート、最終的に逐次的な実行順になる。

18.3 Q

図18.10で示されたwaits-forグラフにおけるpath pushingアルゴリズムの手順を記述せよ。

18.3 A

AがBにパス $(t_1\rightarrow t_3)\rightarrow$ を送出
BがCにパス $t_1\rightarrow t_3\rightarrow t_5, t_1\rightarrow t_3\rightarrow t_6$ を送出
Cで閉路 $t_1\rightarrow t_3\rightarrow t_5\rightarrow t_1$ が検出

18.4 Q

例18.8, 18.11, 18.12でのOptimistic Ticket Method(OTM)の挙動を記述せよ。

18.4 A

例18.8

$s_1=r_1(a)r_3(a)r_3(b)w_3(a)w_3(b)r_2(b)$

$s_2=r_2(c)r_4(c)r_4(d)w_4(c)w_4(d)r_1(d)$

$r_2(b),r_1(d)$ どちらかの実行時点でチケットグラフは $t_1\leftrightarrow t_2$ となって閉路になるため、どちらかのトランザクションがアボートされる。

例18.11

$s_1=w_1(a)c_1r_3(a)r_3(b)c_3w_2(b)c_2$

$s_2=w_2(c)c_2r_4(c)r_4(d)c_4w_1(d)c_1$

$t_1, t_2$ は同じデータアイテムへの書き込みを行わないが、take-a-ticket操作によって強制的に競合を作成される。よって、例18.8と同じく閉路 $t_1\leftrightarrow t_2$ が作られてアボートされる。

例18.12

$s_1=r_1(a)w_3(a)w_3(b)r_2(b)c_1c_3c_2$

$s_2=w_4(c)r_1(c)r_2(d)w_4(d)c_2c_4c_1$

そもそも $c_1,c_2$ の順が各ローカルスケジュールで逆転してしまっており、OTMで管理していたらこのようなスケジュールにはならない。コミット順を無視するにしてもチケットの閉路 $t_1\rightarrow t_3\rightarrow t_2\rightarrow t_4\rightarrow t_1$ が生じるためいずれかがアボートされる。

18.5 Q

定理18.5を証明せよ。

( $s_i\in COCSR$ かつ、グローバルトランザクションのコミット順がサーバ間で統一されていれば、 $s$ はglobally serializable)

18.5 A

コミット順が統一されているので、これを全順序としてみれば、この全順序は $s_i\in COCSR$ のためローカルの逐次実行順に矛盾せず、したがって定理18.1より $s$ はglobally serializable。コミット順と競合する操作の順は全て一致するので $s\in COCSR$ でもある。

18.6 Q

$s \in COCSR$ なら $\Pi_i(s)\in COCSR$ を示せ。

18.6 A

サーバ $i$ における競合もグローバルなコミット順に沿って生じるのでこれは明らか。

18.7 Q

$s\in ECOCSR - COCSR$ をみたすスケジュールの例を挙げよ。

※ $ECOCSR$ : グローバルなトランザクション間でだけ競合に則したコミット順を要求する正当性

18.7 A

$s=r_1(x)r_1(y)w_2(y)c_2c_1$

$s_1=r_1(x)c_1$

$s_2=r_1(y)w_2(y)c_2c_1$

はグローバルトランザクションが $t_1$ のみなので明らかにECOCSRに属するが、yにおける競合がコミット順に則さないのでCOCSRではない。

18.8 Q

各プロトコルにおいてチケットを取得する操作の適切なタイミングを考えよ。

18.8 A

2PL：チケット操作には排他ロックが必要になるので、保持している期間をできるだけ短くしたい。よって、ロックの取得フェーズから解放フェーズへの転換点で実行するとよい。
S2PL, SS2PL：2PLと同じ理由で、排他ロックが解放されるタイミングであるコミット直前に実行するとよい。
BOCC, FOCC：validation(検証)フェーズの開始直前、write setに基づいて各サーバでチケットを取得する。
ROMV：タイムスタンプとチケット取得タイミングを可能な限り同期させるため、
- updaterトランザクションはコミット直前、
- read-onlyトランザクションは開始時にチケットを取る。

18.9 Q

各ローカルスケジュールのMVSR性が保証されている状況でOptimistic Ticket Method(OTM)を考えることはできるか？どんな条件が必要か？

18.9 A

MVSG(Multi-Version Serialization Graph)におけるグローバルトランザクション間のパスがローカルスケジュールによって作られるなら、それがローカルなトランザクションを介した間接的なものであってもチケット上の辺として観測できなければならない。

今やチケットもマルチバージョンであることを踏まえると、チケット取得操作を定義しなおす必要がある。現在アクティブなトランザクションによって書き込まれたバージョンのチケットをすべて読み込み、新しいバージョンを書き込むようにし、読み込んだ全バージョンに応じた辺をチケットグラフ上に作る。

18.10 Q

ローカルスケジュールがsnapshot isolationを満たすとき、グローバルトランザクションについては何が言えるか？

18.10 A

ローカルスケジュールにおいて現在アクティブなトランザクションとwrite setが互いに素な時、グローバルで見ても全く同じことが言える。また、直近のコミットされたバージョンを読み込むという条件も満たされる。

以上より、ローカルスケジュールがsnapshot isolationを満たしているとき、グローバルなsnapshot isolationも達成される。ただし、コミットタイミングが同期されていることは必要である。このことからパフォーマンスは高い。

18.11

グラフィカルなので略。

概要としては、ロックを要求する際、ロック権限を全ページのhomeであるサーバCに要求する。要求した権限が排他ロックで、かつそのページへの権限を他のサーバが持っていた時に限り、サーバCは他サーバへコールバックリクエストを送り、コールバックが承認された時点で改めてロック権限を引き渡す。

u-ar.hatenablog.com

はじめに

所感

個別の事項メモ

1章 基本事項

2章 B木の基本

3章 バイナリエンコーディング

4章 B木の実装

5章 トランザクション処理とリカバリ

6.1 Q

6.1 A

6.2

6.3 Q

6.3 A

一つ目はtree reducibleである。

二つ目もtree reducibleである。

6.4 Q

6.4 A

6.5 Q

6.5 A

tree reducibleである。

conflict faithfulである。

層間スケジュールはOCSR。

6.6 Q

6.6 A

6.7 Q

6.7 A

6.8 Q

6.8 A

6.9 Q

6.9 A

(a) 一般の可換性で考えるとserializableでない。

(b) キューの返り値可換性で考えるとserializableでない。

(c) semi-queueの返り値可換性で考えるとserializableでない。

6.10

6.11 Q

6.11 A

5.1 Q

5.1 A

5.2 Q

5.2 A

5.3 Q

5.3 A

5.4 Q

5.4 A

5.5 Q

5.5 A

MVTOでの処理

2V2PLでの処理

5.6 Q

5.6 A

5.7 Q

5.7 A

5.8

5.9

8.1 Q

8.1 A

8.2 Q

8.2 A

8.3 Q

8.3 A

(a) Modify操作はDelete+Insertで代替できないことを示せ。

(b) を示せ。

(c) IDトランザクションのみの場合、 の所属は多項式時間で判定できることを示せ。

8.4

8.5 Q

8.5 A

(a) が単調でないこと

(b) が prefix commit closed でないこと

(c) が単調であること

(d) が単調であること

(e) も も prefix commit closed であること

8.6 Q

8.6 A

8.7 Q

8.7 A

8.8 Q

8.8 A

8.9 Q

8.9 A

8.10 Q

1章基本事項

3章バイナリエンコーディング

5章トランザクション処理とリカバリ

(b) $s=i_1(1)d_2(1)i_2(2)d_1(2)i_3(1)i_3(2)\in FSR_{IDM}-CSR_{IDM}$ を示せ。

(c) IDトランザクションのみの場合、 $FSR_{IDM}$ の所属は多項式時間で判定できることを示せ。

(a) $FSR_{IDM}$ が単調でないこと

(b) $FSR_{IDM}$ が prefix commit closed でないこと

(c) $CSR_{IDM}$ が単調であること

(d) $ECSR_{IDM}$ が単調であること

(e) $CSR_{IDM}$ も $ECSR_{IDM}$ も prefix commit closed であること