###### tags: `TransactionalInformationSystems`

# 20章 トランザクション制御の展望

## 概要

- 導入した重要な概念・アルゴリズムの振り返り
- データレプリケーションの取り扱い
- 発展的なeサービス/ワークフロー管理
- パフォーマンスと可用性の目標

## 振り返り

3レベルで分けて振り返る。

1. 既製品を欲する開発者
2. 実践的に最適な手法への知識を欲するシステムアーキテクト
3. 最先端を追求する研究者

### よく実用化された技術 for 開発者

正当性基準はCSRが便利で、それを実現でき、同時に復元や回復もサポートできる**S2PLやSS2PL**がベストなことが多い。

障害回復のために永続ログは必要で、それが大きくなり過ぎないように定期的なログ切り捨ても必要である。
回復アルゴリズムはredo-historyが効率的。メディアの回復は、バックアップの定期的な取得とアーカイブログの記録により実現する。それとRAIDのような誤り訂正符号による冗長化を併用する。

単一のデータサーバにおけるCCや回復については、確立された実装が利用できる。加えて、インターネットベースのeサービスやワークフローなどの分散アプリケーションでは、2PCを使ってデータの一貫性を保持する。各ローカルサーバではCOCSRやRGといった性質を守ることで、全体のglobal serializabilityを保証できる。

### 最先端のテクニック for システムアーキテクト

ロックの競合によるボトルネックを解消するために、マルチバージョンの同時実行制御が採用しうる。最も広く使われているのはROMV。

柔軟なロック粒度を実現するのも重要な課題になる。本書の時点では商用レベルではレコードレベルのロック粒度が基本だそうだが、特に大事で注目に値する追究対象はB+木などの構造を利用した高速なインデックスCC(9章)。

オブジェクトモデルのCCおよび回復も重要な課題。

確実な障害回復をユーザからは見えないように行えるメッセージキューベースのアプリケーション回復の実装や、あとはヘテロジニアスなシステムにおけるトランザクション管理と2PCの最適化も注視したい。

### 方法論および新しい問題 for 研究者

redo-winnersアルゴリズムであったりinterleaving specificationであったり、現在は実用的でなく採用されていないアルゴリズムも、どこが優れていてなぜ実用的でないかを論じてきた。システムの能力やワークロード特性、技術は移ろいゆくものなので、そうしたアルゴリズムも適時再評価して光を当てつつ改善していくべき。

本書のアルゴリズムの証明は概念的な部分の説明を重視して厳密性はあまり担保していなかったので、もっと踏み込んで詳しく証明してもよい。

## ユビキタスなアクセスのためのデータ複製

複数のサーバ上に同じデータアイテムの複製（レプリカ）を置きたい。このようなレプリカ間の一貫性を維持するためのアルゴリズムはreplication control（**複製制御**）と呼ばれる。

そのメリットは主に二つ。

- データの可用性。あるサーバが落ちてもアクセスできる。
- 応答性の速さ。様々な端末から高速にアクセスできる。

読み込みに関してメリットが大きいので、read-onlyなトランザクションの割合が大きいアプリケーションにおいて特に有用となりうる。特にWebページのアクセスやファイルの取得において、各国各地域のサーバに置かれたキャッシュを利用することで速度が劇的に改善する。

読まれたレプリカの同一性を保証するアルゴリズム（one-copy serializability）が重要な課題になる。データアイテムを読み書きするとき、全レプリカにロックをかければ自明にこれは保証される。だがこれは当然コストが大きいので、工夫された複製制御アルゴリズムが考えうる。特に、更新がレプリカに同期的に反映される積極的(eager)/同期的なアルゴリズムを最初に考える。

### 同期複製制御

最も単純かつ高速なのは**プライマリコピー法**。各データアイテムごとに最重要なレプリカ（プライマリコピー）を一つずつ定め、更新は必ずプライマリコピーに対して書き込まれる。レプリカへの更新の反映は遅延的に行われる。読み込みをしたいトランザクションは、プライマリコピーに対する直近の更新のタイムスタンプを受け取る。最も近い位置にあるレプリカにアクセスし、そのタイムスタンプを比較して古くなければ読み込みに成功する。

プライマリコピー法への批判は、プライマリコピーを保持するサーバが落ちたとたんに他のレプリカへのアクセスもできなくなってしまうこと。この問題を重要視した代替アルゴリズムはread-one write-all method(ROWA)。どのレプリカを読み込んでも大丈夫な代わりに、書き込み時には全レプリカを最新のバージョンにしなければならない。

プライマリコピーは読み込みにツケを、ROWAは書き込みにツケを払わせており、そんな極端じゃない中間の方法が欲しい。そこで**多数決法**(majority voting)が考案される。読み込みでも書き込みでも、存在するレプリカの過半数にアクセスしてレプリカの最新性を担保する。

多数決法が有効であることの本質は、衝突する操作(read-write, write-write)が共通して触るレプリカが少なくとも一つ存在するということである。

逆に言えば、read-writeとwrite-writeが少なくとも一つの共通レプリカに触ることを保証できさえすれば、多数決に限らずとも定数をある程度柔軟に設定できるということである。たとえば、レプリカ数$n$のとき、read定数を$\frac{1}{4}n$、write定数を$\frac{3}{4}n+1$にするとか。さらに、各サーバの障害レートや応答時間に応じて重みづけをすることもできる。このようなアルゴリズムは定数合意(quorum consensus)・重みづけ投票(weighted voting)と呼ばれる。

### 非同期複製制御

ここまで考えてきた同期的なアルゴリズムは、インターネット規模でレプリカ数が10や100の単位になった瞬間に実用性を失う。そのようなケースでは、レプリカへの反映が遅延を伴う非同期的な方法に頼らざるを得ない。この場合、レプリカへの変更の反映がバックグラウンドで遅延的に行われる。多少古い情報がユーザに見えてしまうことは甘受する。

複数のレプリカが同時に変更されたとき、それが伝播してきた各レプリカでどちらの更新を反映するのかという問題が生じるが、最終的なデータの一貫性を維持するため、基本的には実時間のタイムスタンプで最新のものを優先する。どれが勝つかはもっと柔軟にもできる。例えば、昼時間のタイムゾーンを優先するとか。

## eサービスとワークフロー

ワークフロー（複数のアクティビティからなる複雑なタスク）のお話で、既にみた内容なので割愛

## パフォーマンスと可用性の保証

パフォーマンスは主にこれまで定性的に評価してきたが、当然定量的な評価が必要になることもある。

指標としては

- スループット：単位時間あたり走らせられる最大トランザクション数
- 応答時間：トランザクションの開始からレスポンスを受け取るまでの時間
- 信頼性：与えられた時間の中でシステムが修復不可能な障害を経験しない確率
- 可用性：任意の時点でシステムが稼働している確率

分散システムでは可用性は一部のサーバダウン時にも100%になってしまうが、そういうケースにはパフォーマンスが低下するので、可用性とパフォーマンスを統合した概念のperformabilityという指標も有用になる。

特に応答時間は分析するのが難しい指標になる。システムの性能やアクセスパターンなどの特性に激しく依存するし、またユーザの利用が集中してメッセージがキューに入れられた際の遅延の影響を考慮する必要があるため。キューの使用は確率的なプロセスなので、確率モデルで分析するしかない。