###### tags: `TransactionalInformationSystems`

# 19章-2 2相コミットの最適化

## 階層的な2相コミットプロトコル

2PCにおいて調整者をどのように選ぶかは考えてこなかった。

調整者の選択にはいろいろな側面が伴う。トランザクションの開始者はクライアントなのかアプリケーションサーバなのかデータサーバなのか、とか、各参加者がどれぐらいの信頼性を持っていて高速か、とか、参加者同士がどのようなプロトコルで通信していてどのような通信路トポロジーなのか、とか。

最もシンプルかつ自然な調整者の選択方法は、トランザクションの開始者を調整者にすることである。特に、それが**アプリケーションサーバであった場合は、信頼性が高く高速で他サーバによく接続されている**ので賢明な選択である。

開始者がクライアントであった場合は、関わっているデータサーバのいずれかに調整者を任せる方が良いことが多い。データサーバの選択はコミット直前に動的に行える。これは**参加者間のコミュニケーションが高速なLANにおいて有効**である。一方、そうでないインターネットなどのWANではコミュニケーションに基づく動的な調整者の決定は遅延を伴う。

#### トランザクション開始者を根とするプロセス木

トランザクション実行の間、関わるプロセスの間で開始者を根として木が形成される。リクエストーリプライの関係にある参加者どうしに辺が渡され、リンクが確立される。

調整者を選択することは、このようにして形成されたプロセス木の中から一つのノードを選択し、そのノードから他すべてのノードに直接の辺を張る(平坦化)ことに相当する。

#### 階層化されたコミット

この平坦化が許容できない場合（一部のプロセスが他のプロセスにネットワークアドレスを教えたくない場合や、コネクション確立のコストが大きい場合）、木を平坦化せず、階層的に2PCを実行することも考えられる。

階層的に2PCを実行する場合、各内部ノードが調整者と参加者両方の役割を果たすことになる。

具体的には、親から準備メッセージが送られてきたら、自身がpreparedログエントリを生成する前に自身の子に準備メッセージを送信する。自身を根とする部分木すべてから答えを得た時点で親に返信し、preparedログエントリを書き出す。決定フェーズにおいてもコミット/アボートメッセージと承認メッセージを同様に親と子の間で伝達する。

## 分散コミットの最適化

2PCのパフォーマンスを改善する方法は主に以下の3つになる。

1. 必要なログ書き込み、特にforceを要するものを減らす。
2. コミットの開始からローカルのロックを解放できるようになるまでのクリティカルパスを短くする。
3. ブロッキングの確率を減らす。できるだけ独立に回復できるようにする。

### ログ書き込みを減らす

$n$個の参加者&1個の調整者の場合、コミットの総コストは$4n$個のメッセージ+$2n+2$個のforceを要するログ書き込みである。なぜなら、

#### 基本2PCでforceする必要があるログエントリ

- 各参加者について、preparedログエントリとcommit/rollbackログエントリ
- 調整者について、beginログエントリとcommit/rollbackログエントリ
- endはforceする必要がない。ackを貰い直せば終了状態かどうか分かるため。

#### 基本2PCで必要なメッセージ

各参加者との間で、

- prepare
- yes/no
- commit/abort
- ack

このうち、調整者におけるbeginログエントリは無くすことができる。なぜなら、beginログエントリはそのトランザクションが存在することを記録に残すためのものだが、

- 調整者ログが参加者ログの中に含まれていたとき、beginエントリをわざわざ作らなくてもそのトランザクションの存在は記憶される。
- そうでなくても、beginエントリがなくても問題ない。そのトランザクションの存在が調整者に忘れられる。各参加者はタイムアウト後に調整者にトランザクションの現状を打診し、調整者がそれを認識していないと分かった時点でローカルにロールバックする。

これで$2n+1$個に減る。

このように、グローバルな決定についての情報が存在しない状況での各プロセスの想定動作を定めておくことでロギングのコストが減る。デフォルトの選択をコミットにするのかアボートにするのかでpresumed-abort(PA)とpresumed-commit(PC)が存在する。ちなみに、基本的な2PCはこのような想定に基づく選択をしないのでpresumed-nothing(PN)と呼ばれる。

減らせる可能性のある候補は

- 参加者のコミット/ロールバックログエントリのforce（調整者のログにその情報が含まれているため）。
- 参加者の承認メッセージ。

#### presumed-abortプロトコル

まず、情報がないときはとりあえずアボートにするPAプロトコルを考えてみる。

はじめに、敗者トランザクションを取り扱う場合、**コミット/ロールバックログエントリのforceも承認メッセージも無しで問題なく動作できる**。

承認メッセージが存在しないことからトランザクションが真に終了するタイミングが分からないので、ガーベジコレクションの正確なタイミングが分からない。よって、終わっていないトランザクションの調整者ログエントリを捨てることも許されることにしてみる。

調整者の決定（アボート）を受け取った後、ローカルのrollbackログエントリをforceする前に参加者がクラッシュしてしまったケースを考える。再開した参加者は、永続ログにrollbackログエントリがなく、状態が分からないため、調整者にトランザクションの状態を尋ねる。調整者は、調整者ログにrollbackログエントリがある場合には敗者であることを正しく伝えられるし、ログエントリが捨てられてしまっていても、想定動作がアボートであることから敗者であると正しく伝えられる。

グローバルに一貫した状態が保たれていることが分かる。ちなみに、そもそも調整者側もrollbackログエントリが必要ないことがここから分かる。

一方、勝者トランザクションを取り扱う場合には**コミット/ロールバックログエントリのforceも承認メッセージも必要**である。それが無ければ、調整者はコミットプロトコルの初期状態なのか決定フェーズ後なのか判定できず、一部の参加者はローカルにコミット済みなのに他の再開した参加者にアボートを命令してしまう不具合が起こりうる。

ここから、PAプロトコルの総体としては、

- 投票フェーズにおいて、preparedログエントリはforceする。
- 決定がコミットであった場合
- 調整者はcommitログエントリをforceする。
- 各参加者はcommitログエントリをforceし、承認メッセージを調整者に送り返す。
- 決定がアボートであった場合
- 各参加者は各々にロールバックするが、rollbackログエントリのforceは直ちには必要ないし承認メッセージを送る必要もない。

となる。

#### presumed-commitプロトコル

大多数のトランザクションはコミットされるわけで、ログエントリのforceやメッセージ送信回数を減らしたいのはどちらかといえばコミットされた方である。そこで、PAの双対としてpresumed-commit(PC)プロトコルを考えたくなってくる。

ただし残念ながら、単純に反転させる（決定がコミットだった場合にforceや承認メッセージを省略する）だけでは駄目で、もう少し複雑になってしまう。

そこで、勝者トランザクションについて、承認メッセージは送らないがcommitログエントリのforceは必要ということにしてみる。このケースでは調整者側のbeginログエントリも必須になる。こうしてPCを得る。

- 調整者はbeginログエントリをforceする。
- 投票フェーズにおいて、preparedログエントリはforceする。
- 決定がコミットであった場合
- 調整者はcommitログエントリをforceする。
- 各参加者はcommitログエントリのforceは直ちに必要なく、承認メッセージは送らない。
- 決定がアボートであった場合
- 調整者はrollbackログエントリをforceする。
- 各参加者はrollbackログエントリをforceし、承認メッセージを調整者に送り返す。

結論として、

- PAは
- アボートされたトランザクションについて$n$個のメッセージと$n+2$回のforceを削減できる。
- コミットされたトランザクションについては削減できない。
- PCは
- アボートされたトランザクションについては削減できない。
- コミットされたトランザクションについて$n$個のメッセージと$n$回のforceを削減できる。

PCは、階層的なコミットを採用する場合、各内部ノードでbeginログエントリをforceする必要があるため相性が悪い。そのため、標準規格XAには階層的なPAが採用された。それでもなお、平坦な通信トポロジーの場合には2PCの方が一般に優れている。

PA, PC, PN のいずれかを採用するかは、各トランザクション内で統一されてさえいればよいため、これらは同じ分散システム内で共存しうる。トランザクションのコミットを開始する段階で動的に決定することもできる。

PA, PC, PN のどの参加者にも対応できるpresumed-anyプロトコルを調整者で走らせることもできる。この場合、全部のプロトコルに対応できるように必要なログをもれなくforceし、PAやPCから該当する承認メッセージを受け取る。

### Read-onlyな部分木の最適化

トランザクションを実行してプロセス木を形成してみたところ、どこかの部分木ではデータの更新が行われていないというケースが起こりうる。この部分木はコミットだろうがアボートだろうが変更を要さないので、YES、NOに加えて、投票フェーズにおける専用の返信メッセージread-onlyを作ることにする。投票フェーズでread-onlyを返信した部分木は、決定フェーズでは無視され（コミット/アボートメッセージが送られない）、返信を送り返した瞬間にローカルなロックの解放を始めてよい。

PCでは、read-onlyな部分木でもbeginログエントリのforceが必要になってしまい旨味が得られない。そういう意味では、read-onlyな部分木でのログforceを一切なくせるPAとの相性が良い。

read-only最適化は、各参加者がPreparedになった後のコミット直前に追加の操作（制約チェックなど）を許されている場合には不正な状態を引き起こしうるため利用できない。

### 調整者の変更

トランザクション開始者以外の参加者を調整者に選ぶこともできる。この場合、プロセス木のトポロジーはそのままで、新たに選んだ調整者を根とするように辺の向きが変更される。

これを用いて、プロセス木が単一のパスで構成されているとき、トランザクション開始者の反対側にいる、**最後にトランザクションに参加した参加者を調整者にするリニア2PC**を考えることができる。

トランザクション開始者は、コミット準備ができたとき、
- preparedログエントリを書き出すと同時に
- 隣接したプロセスに調整者を委譲しつつ
- 同時にYESを送信する。

調整者を委譲された参加者は、パス上の次の参加者へ向けて同じことをする。

これを繰り返すと、最終的にパスの末尾の参加者が調整者に決定されるので、調整者は投票結果に応じてコミット/アボートメッセージを送信する。

このような調整者決定プロセスを踏むことで、準備メッセージとそれに対する返信が一つのメッセージに統合されるため、総メッセージ数が削減される。

メッセージ伝播の途中でコミットできないプロセスに到達したとき、その参加者が調整者になってパス上の親と子に向けてNOメッセージを伝播させ、トランザクション全体がロールバックされる。

---


---

リニア2PCの本質的なアイディアは、「他の参加者が全てpreparedであることを最初に知ったプロセスを調整者にすることで、投票フェーズのコストを減らす」ということである。したがって、このアイディアをより一般のプロセス木に応用することもできる。

**動的2PC**は、「他の参加者が全てpreparedであることを知るプロセス」をできるだけ早く発見するため、準備ができたプロセスが親と子のどちらにも投票を送れるようにする階層的な2PCである。具体的には、以下の手順を踏む。

あるノードは、隣接する$k$個のノードのうち$k-1$個からYESメッセージを受け取り、かつ自身が永続ログにpreparedログエントリを書き出し終わったなら準備完了と考え、残る1つの隣接ノードにYESメッセージを送る。

これにより、メッセージの伝播方向が変則的になり、葉が調整者になることもある。その場合、その葉が最も早く他の全参加者がpreparedであることを知ったということである。

### ブロッキングの削減

コミットの協調にあたってブロッキングを完全になくすことはできないが、起こる可能性を減らすことはできる。

#### 3相コミット(3PC)

3つのメッセージラウンドからなるコミットプロトコルを考える。

1. 投票フェーズ：参加者に準備メッセージを送り、prepared状態にさせる。
2. 周知フェーズ：投票の結果を各参加者に周知する（新しく追加されたフェーズ）。
3. 決定フェーズ：結果に基づいてコミット/アボートメッセージを送る。

Committed/Aborted状態に完全に移行する前に、周知フェーズのおかげで各参加者は投票の結果を知っているわけで、これに基づいて独立に回復することができる。ただし、独立な回復が可能なのは障害が1つしか起こらない場合に限定される。それ以上同時に起こったら、メッセージのやり取りは必須になる。

ただし、特定の状況でのブロッキングの可能性を減らすという恩恵が、メッセージラウンドが増えるというコストに釣り合っていないため、3PCの実用性は低い。

#### 協調終了

各参加者が投票の結果を早く知ってブロッキングを解消したいとき、参加者間でコミュニケーションをとってコミット/アボートメッセージがどれかに送信されたかどうかを共有することも考えられる。もちろん、参加者リストを各参加者が持つ必要がある。

#### ヒューリスティックコミット/アボート

調整者からの指示がしばらくない場合、勝手にローカルにコミットもしくはアボートしてしまうという極端な方法でもブロッキングは回避される。

かなり粗暴な方法ではあるが、例えば頻繁に終了するクライアントPCが調整者だったりした場合にもしかしたら実用性があるかもしれない。

例えば銀行預金であれば、預入れではデフォルトでコミット、引き出しではデフォルトでアボートにすれば比較的安全ではある。