このページでは、分散データベースの6つの透過性、セミジョイン法などのサイト間の結合方法、レプリケーションと2相コミットメント制御がわかります。
- 一言で言うと：
- 複数の場所（サイト）に分かれたデータベースを、1つのデータベースのように見せる話
- どこにあるかを意識させない透過性、離れたサイトの表を少ない通信で結合するセミジョイン法、複数サイトを同時に正しく更新する2相コミットメント制御が出てくる
1つに見せる（6つの透過性、DD/Dの配置）→ 離れた表をつなぐ（セミジョイン法、入れ子ループ法、マージジョイン法、ハッシュ結合）→ 離れた表をそろえる（レプリケーション、2相コミットメント制御）
覚え方の軸
- 透過性は「意識しなくてよいもの」の名前
- 位置・移動・分割・複製・障害・データモデルの6つ（分散DB）
- 分割には、行で分ける水平分割と、列で分ける垂直分割がある
- サイト間の結合は「送る量を減らす」工夫
- セミジョイン法は、結合列だけ送る。ハッシュセミジョイン法は、結合列のハッシュ値だけ送る
- 入れ子ループ法は二重ループで、計算量は O(n²)
- 更新の同期は「後でそろえる（非同期）か、すぐそろえる（同期）か」
- 非同期の代表がレプリケーション、同期の代表が2相コミットメント制御
- 2相コミットは「まず全員に聞いて、全員OKなら実行」
- 第1フェーズでCOMMITの可否を問い合わせ、各サイトはセキュア状態に
- 第2フェーズで、全員が可ならCOMMIT、1つでも否か無応答ならロールバック
- 弱点は、調停者が止まると参加者がブロック状態になること（対策は3相コミット）
分散データベースシステム：1つに見せる（★）
- 分散データベースシステムの目的：
- 複数のサイトに分散されたデータやシステムを論理的に統合して、1つのデータベースシステムであるかのように利用者に見せること
- そのためには、データ（表やビューなど）がどのサイトにあり、どのサイトに移動したかを意識せずに扱える“透過性”が必要
① 6つの透過性
- データの分散：
- 表やビューなどのデータは、アクセス負荷やネットワークのトラフィックなどを考えて、各サイトに分散される
- 1つの表を、各サイトが必要とする単位で分割することもある
- 水平分割と垂直分割：
- 水平分割は、行単位に分割する（例えば、顧客表を東京支店顧客表と大阪支店顧客表に分ける）
- 垂直分割は、列単位に分割する（例えば、顧客表の列A〜Eを、A・B・Dと、C・Eに分ける）
分散DBの6つの透過性（★）
| 透過性 | 意識しなくてよいこと |
|---|---|
| ①位置に対する透過性 | データの位置 |
| ②移動に対する透過性 | データの移動先 |
| ③分割に対する透過性 | 表が複数のサイトに分割されていること |
| ④複製に対する透過性 | 同じデータが複数のサイトに格納されていること |
| ⑤障害に対する透過性 | あるサイトで起こった障害 |
| ⑥データモデルに対する透過性 | 問合せ言語や、データモデル（データ構造）の違い |
- 不可欠な3つ：
- 分散データベースシステムでは、位置、移動、分割に対する透過性の実現が不可欠
- 透過性の例え：
- 全国チェーンの図書館の検索システム。本がどの分館にあっても（位置）、別の館に移っても（移動）、上下巻が別々の館にあっても（分割）、利用者は同じ画面で探して借りられる
② 透過性の実現（DD/D）
- データディクショナリ／ディレクトリ（DD/D）：
- 表の格納場所や表の構造などの情報を持つデータ辞書
- グローバルなDD/D：
- 透過性を実現するには、各サイトのDBMSが持つDD/Dに加えて、分散データベース全体を管理するグローバルなDD/Dが必要
- DD/Dをどのサイトに置くかの方式は、大きく分けて集中型と分散型
グローバルDD/Dの配置方式（★）
| 方式 | 中身 | 長所 | 短所 |
|---|---|---|---|
| 集中管理方式 | 1つのサイトにDD/Dを持たせる | 他のサイトを調べ回る必要がない | そのサイトに負荷が集中し、障害が起きると分散DB全体に影響する |
| 分散管理方式（重複保有なし） | 各サイトに自サイトのDD/Dだけを持たせる | 表の移動や表構造の変更は、そのサイトのDD/Dを変えるだけでよい | 自サイトにない表は、他サイトのDD/Dを調べ回る必要がある |
| 分散管理方式（重複保有あり：完全重複） | 各サイトにすべてのサイトのDD/Dを重複して持たせる | 自サイトのDD/Dを見れば、すべての表の位置がわかる | 表の移動や変更のときは、すべてのDD/Dを変更する必要がある |
| 分散管理方式（重複保有あり：部分重複） | 各サイトに、いくつかのサイトのDD/Dを重複して持たせる | − | − |
- DD/Dの配置の例え：
- 集中管理は、本部だけが全店の在庫表を持つ。本部に聞けば全部わかるが、本部が休むと誰もわからない
- 重複保有なしは、各店が自分の店の在庫表だけ持つ。他店の在庫は電話して回る
- 完全重複は、全店が全店の在庫表を持つ。すぐわかるが、1店の在庫が変わるたびに全店の表を直す
異なるサイト間での表結合：送る量を減らす（★）
① 表結合の方式
- サイト間結合の問題：
- 異なるサイト間で表結合をするには、基本的に、どちらか一方の表を他のサイトに送る必要がある
- でも、表全体を送ると転送コストがかかる
- セミジョイン法：
- 結合に必要な属性（結合列）だけを相手サイトに送り、結合に成功したものだけを元のサイトに戻して、最終的な結合を行う方式
- 異なるサイト間の結合アルゴリズムなので、通常の結合では使われない
- ハッシュセミジョイン法：
- セミジョイン法にハッシュ結合を組み合わせた方式
- 結合列の値のハッシュ値を送り、相手サイトでハッシュ結合を使って結合する
- セミジョイン法に比べ、転送コストを減らせる
- セミジョイン法の例え：
- 東京の顧客名簿と大阪の注文表を突き合わせたいとき、名簿を丸ごと送らず、「顧客番号の一覧」だけ大阪に送る。大阪で該当する注文だけ選んで東京に送り返してもらう
② その他の表結合方式
その他の表結合方式（★）
| 方式 | 中身 | 分散サイト間で使う場合 |
|---|---|---|
| 入れ子ループ法 | 単純に二重ループを回して結合する。例えば、外側のループで表Aから1行を取り出し、内側のループで表Bのすべての行と比べて結合する | 1行ずつ相手サイトに送り、相手サイトで1行ずつ順に結合する |
| マージジョイン法（ソートマージ結合） | 結合列の値でソートした2つの表を、先頭から順に突き合わせて結合する | ソート後の表を相手サイトに送り、相手サイトで結合する |
| ハッシュ結合 | 一方の表（行数の少ない表）の結合列の値でハッシュ表を作り、もう一方の表の結合列をハッシュ関数にかけ、ハッシュ値が等しいものを結合する | − |
- 入れ子ループ法の計算量（試験）：
- 試験では、入れ子ループ法の計算量が問われる
- 行数nの表2つを結合する場合の計算量は、O(n²)
- ハッシュ結合の制限：
- ハッシュ値で比較・結合するので、等価結合以外の結合演算には使えない
- 3つの結合方式の例え：
- 入れ子ループ法は、クラス全員の名簿の1人ずつについて、もう一方の名簿を最初から最後まで読む
- マージジョイン法は、両方の名簿を五十音順に並べてから、上から同時に読み進める
- ハッシュ結合は、片方の名簿で「出席番号の箱」を作っておき、もう片方の人を番号の箱に入れていく
例題（入れ子ループ法の比較回数）
- 問題：
- 行数1,000の表Aと、行数1,000の表Bを入れ子ループ法で結合する。比較の回数は何回か。また、両方の表が10倍（10,000行）になると、比較回数は何倍になるか
- 答え：
- 1,000 × 1,000 ＝ 1,000,000回（100万回）
- 10,000 × 10,000 ＝ 100,000,000回なので、100倍
- わかること：
- O(n²)なので、行数が10倍になると、手間は10² ＝ 100倍になる
ネットワーク透過性
ネットワーク透過性の種類
| 透過性 | 中身 |
|---|---|
| アクセス透過性 | 遠隔地にある異なる種類の資源に、手元にある資源と同じ方法でアクセスできる |
| 障害透過性 | システムや資源の一部に障害が起きても、それを認識することなく利用できる。障害透明性ともいう |
| 複製透過性 | 資源が複数の位置に複製されていても、それを意識せずに、1つの資源として利用できる。重複透過性ともいう |
| 規模透過性 | OSやアプリケーションの構成に影響を与えずに、システムの規模を変更できる |
| 移動透過性 | 資源が別の場所に移動しても、それを意識せずに利用できる |
| 位置透過性 | 遠隔地にある資源の位置を意識せずにアクセスできる |
| 性能透過性 | 性能向上のために再構成できる |
| 並行透過性 | 複数プロセスを並行処理できる |
分散データベースの更新同期：離れたデータをそろえる（★）
- 更新同期が必要な理由：
- 分散データベースでは、データを複数のサイトに重複して置いたり、複数サイトに分割・分散させたりする
- 一方のサイトが更新されても、他方が更新されなければ、データの整合性を保てない
- だから、サイト間でデータの同期をとる必要がある
- 同期の方法：
- 非同期型更新は、適切なタイミングでデータの同期をとる
- 同期型更新は、リアルタイムに同期をとる
① レプリケーション
- レプリケーション：
- 非同期型更新を実現するメカニズムの1つ
- マスタデータベースと同じ内容の複製（レプリカ）を他のサイトに作っておき、決められた時間間隔で、マスタデータベースの内容を他のサイトに複写する機能
- 複写の方法：
- マスタデータベースの全内容を複写する（差替え）方法
- 更新部分（差分）だけを複写する方法
- 同期型レプリケーション：
- レプリケーションには、同期型のものもある
- スナップショット：
- 稼働中のデータベースの表全部、あるいは一部を、ユーザが定義した間隔で自動的に複写する機能
- アプリケーションからは読取り専用になる
- レプリケーションの例え：
- 本店の価格表を、毎晩支店にコピーして配る。日中に本店で値段が変わっても、支店に届くのは夜
② 2相コミットメント制御
- 2相コミットメント制御：
- 同期型更新の代表例
- 2フェーズコミットメントともいう
- 2相コミットが必要な理由：
- 分散データベースのトランザクションは、複数のサブトランザクションに分けられ、複数のサイトで実行される
- だから、「更新 → コミットあるいはロールバック」という1相コミットメント制御では、トランザクションの原子性、一貫性を保証できない
- コミットメント制御：
- トランザクションのACID特性の原子性と一貫性を保証するための機構
- 2相コミットメント制御の考え方：
- 更新ができるかを確認する第1フェーズと、更新を確定する第2フェーズに分ける
- 各サイトのトランザクションを、コミットもロールバックも可能な状態（セキュア状態、中間状態）にした後、全サイトがコミットできる場合だけコミットする
- これで、トランザクションの原子性と一貫性を保証する
- 調停者：
- コミット処理を指示する主サイト側
- 参加者：
- 主サイトからの指示で、必要な処理を行うサイト側
2相コミットメント制御の処理手順（★）
- 第1フェーズ：
- ①調停者は、参加者に「COMMITの可否」を問い合わせる
- ②参加者は、調停者に「COMMITの可否」を返答する。このとき、各データベースサイトは、コミットもロールバックも可能なセキュア状態になる
- 第2フェーズ：
- ③調停者は、すべての参加者から「COMMIT可（Yes）」が返された場合だけ、「COMMITの実行要求」を出す
- 1つでも「COMMIT否（No）」の参加者があったり、一定時間以上たっても応答がない場合は、ロールバック指示を出す
- 第1フェーズで異常：
- 第1フェーズで異常が起きた場合は、第2フェーズでロールバックを実行する
- 図の記法：
- この手順は、UMLのシーケンス図の記法（要求者 → 調停者 → 参加者1・参加者2）で描かれることが多い
- 2相コミットの例え：
- 結婚式の「誓いの言葉」。神父（調停者）が2人（参加者）に「誓いますか」と聞き（第1フェーズ）、2人とも「誓います」と答えたときだけ「夫婦と認めます」と宣言する（第2フェーズ）。1人でも黙ったら、式は取りやめ
2相コミットメント制御の問題点（★）
- ブロック状態：
- コミットまたはロールバック指示の直前に、調停者（主サイト）側に障害が起きたり、通信障害が起きたりすると、各参加者（従サイト）には調停者からの指示が届かない
- だから、コミットかロールバックか判断できない状態に陥る。これをブロック状態という
- 出題傾向（試験）：
- 各従サイトがブロック状態になる、主サイト側の障害発生タイミングが問われる
- 答えは、「参加者がセキュア状態になった後（COMMIT可を返した後）、調停者がCOMMITかロールバックかを指示する前」
- 3相コミットメント制御：
- ブロック状態の問題を解決するため、セキュアの後にプリコミットを行い、その後コミットを行う方式
例題（2相コミットの判定）
- 問題：
- 調停者が参加者1・2・3にCOMMITの可否を問い合わせた。次の場合、調停者は第2フェーズで何を指示するか
- ①参加者1・2・3がすべて「可」
- ②参加者1・2は「可」、参加者3は「否」
- ③参加者1・2は「可」、参加者3からは一定時間たっても応答なし
- 答え：
- ①は、全員が「可」なので、COMMITの実行要求
- ②は、1つでも「否」があるので、ロールバック指示
- ③は、応答がないので、ロールバック指示
混同しやすいペア
- 水平分割 ／ 垂直分割
- 水平分割は、行単位に分ける（東京支店の顧客、大阪支店の顧客）
- 垂直分割は、列単位に分ける
- 位置に対する透過性 ／ 移動に対する透過性
- 位置に対する透過性は、データがどこにあるかを意識しない
- 移動に対する透過性は、データがどこへ移ったかを意識しない
- 分割に対する透過性 ／ 複製に対する透過性
- 分割に対する透過性は、表が複数サイトに分かれていても意識しない
- 複製に対する透過性は、同じデータが複数サイトにあっても意識しない
- 障害に対する透過性 ／ データモデルに対する透過性
- 障害に対する透過性は、あるサイトの障害を意識しない
- データモデルに対する透過性は、問合せ言語やデータ構造の違いを意識しない
- 集中管理方式 ／ 分散管理方式（DD/D）
- 集中管理方式は、1つのサイトにDD/D。調べ回る必要はないが、負荷集中と障害に弱い
- 分散管理方式は、各サイトにDD/D（重複なし、完全重複、部分重複）
- 重複保有なし ／ 完全重複
- 重複保有なしは、変更は楽だが、他サイトの表は調べ回る
- 完全重複は、すべての表の位置がすぐわかるが、変更のたびに全DD/Dを直す
- セミジョイン法 ／ ハッシュセミジョイン法
- セミジョイン法は、結合列を相手サイトに送る
- ハッシュセミジョイン法は、結合列のハッシュ値を送る（さらに転送コストが少ない）
- 入れ子ループ法 ／ マージジョイン法 ／ ハッシュ結合
- 入れ子ループ法は、二重ループ。計算量はO(n²)
- マージジョイン法（ソートマージ結合）は、ソートしてから先頭から突き合わせる
- ハッシュ結合は、行数の少ない表でハッシュ表を作る。等価結合だけ
- 分散DBの透過性 ／ ネットワーク透過性
- 分散DBの透過性は、位置・移動・分割・複製・障害・データモデルの6つ
- ネットワーク透過性は、アクセス・障害・複製・規模・移動・位置・性能・並行の8つ
- 非同期型更新 ／ 同期型更新
- 非同期型更新は、適切なタイミングで同期をとる（レプリケーション）
- 同期型更新は、リアルタイムに同期をとる（2相コミットメント制御）
- レプリケーション ／ スナップショット
- レプリケーションは、マスタの複製を作り、決められた間隔で複写する（差替えか差分）
- スナップショットは、表を定義した間隔で自動的に複写する。読取り専用
- 1相コミットメント制御 ／ 2相コミットメント制御
- 1相は、「更新 → コミットかロールバック」。分散環境では原子性・一貫性を保証できない
- 2相は、可否を確認してから確定する
- 調停者 ／ 参加者
- 調停者は、コミット処理を指示する主サイト
- 参加者は、指示で処理を行う従サイト
- セキュア状態 ／ ブロック状態
- セキュア状態（中間状態）は、コミットもロールバックもできる状態
- ブロック状態は、調停者の指示が届かず、コミットかロールバックか判断できない状態
- 2相コミットメント制御 ／ 3相コミットメント制御
- 2相は、調停者の障害でブロック状態になることがある
- 3相は、セキュアの後にプリコミットを入れて、ブロック状態を解決する
- 2相ロック方式 ／ 2相コミットメント制御
- 2相ロック方式は、同時実行制御。全部ロックしてから解除する
- 2相コミットメント制御は、分散DBの更新同期。可否を確認してから確定する