Concurrency Control and Recovery in Database Systemsを読む勉強会です。

内容としてはロックのパフォーマンスに関してです。今回のポイントは競合の種類(Resource/Data)と競合を回避する手段(abort/block)がメインだと思いますよくわからない箇所があったので自宅で復習しました。

今回はp87から

3.12 LOCKING PERFORMANCE
- Resource and Data Contention
- Thrashing
- Blocking and Restarts
- Predeclaration
- A Bound on Workload
- MPL, Transaction Length, and Granularity
- Read Locks and Nonuniform Access

を読みました。次回は「3.13 TREE LOCKING」からになります。

Concurrency Control and Recovery in Database Systems

作者: Philip A. Bernstein,Vassos Hadzilacos,Nathan Goodman
出版社/メーカー: Addison-Wesley
発売日: 1987/02/01
メディア: ハードカバー
この商品を含むブログを見る

目次です

競合(Contention)に関して
競合に伴うパフォーマンス低下(Thrashing)について
競合の解決方法
- blockingとrestartsのパフォーマンスの比較
- 2PLの検討(Basic 2PL,Conservative 2PL)
性能限界 ~DC Thrashing ギリギリまでパフォーマンスをあげる~
他雑談

競合(Contention)に関して

競合には2種類ある。リソース競合とデータ競合。
- リソース競合(Resouce Contation):メモリやIO待ちなどのシステム的な部分
- データ競合(Data Contation):ロックに関連する競合
多かれ少なかれ多くのシステムは(物理上のスペックの上限があるので)リソース競合が発生しうる。
- リソース競合以外の競合としてデータ競合が定義できることは発展的な議論をするために便利な概念となる。
データ競合はリソース競合を緩和する可能性がある

Resource contention also hurts a pure restart policy more than a blocking policy. With the latter, some transactions are blocked in lock queues, so fewer transactions compete for resources. (Thus, data contention alleviates resource contention for a blocking policy.)

データ競合が起きてできることが少なくなると、リソースの利用率が下がる。

競合に伴うパフォーマンス低下(Thrashing)について

リソース競合,データ競合それぞれに応じてThrashingが発生する恐れがある
- DC Thrashing:ロックの取り合いによって生じるパフォーマンス劣化のこと(デッドロック含む)
- RC Thrashing:スタベーション,またはlive lockのこと
DCスラッシングに関してはDBMSのリソースが無限にあっても発生する恐れがある
DC Thrashing pointを超えてからトランザクションを増やすと、blockされていないトランザクションの数が減少する
- ブロック(ロック解放待ち)とデッドロックがDC Thrashingを引き起こす。特に後者は致命的。
- DC Thrashing point(Thrashingが起こり始める臨界点みたいなイメージ)
  - DC Thrashing point以降に1つのトランザクションの追加で複数(2以上)のトランザクションが平均的にブロックされてしまう
  - DC Thrashing pointを超えてロックキューが増加するとシステムの使用率がかなり低下する
- DC Thrashing point以降にシステムに負荷をかけるとパフォーマンスが大きく下がる

競合の解決方法

競合(Data Contation)の解決方法は2種類ある
- blocking戦略:ロックが解放されるまで待たせるロックキューを作る(waitさせる)
- restart戦略:専有しようとしたリソースがすでにロックされていた場合、トランザクションをabortして最初からやり直す
一般的なRDBMSの実装状況
- blocking戦略をとっているもの
  - MySQLはデフォルトは50秒待ち
  - MySQL Clusterは1.2秒
  - DB2は２分待ち
  - Oracleは永久待ち?
- restart戦略をとっているもの
  - SQLServerはabortしてredo(デフォルトは無限回試行する)
blocking/restartは設定で選べないのか?
- 中身の処理内容が全く違うので設定で切り替えるような問題ではない

blockingとrestartsのパフォーマンスの比較

restartする方が一見コストが高いように見える
- 再起動のコストを払う必要になるため
- 中断した箇所までのトランザクション処理の成果は捨てられるため
が実際にはblocking戦略の方が早く性能劣化(Thrashing)を引き起こす
blockingがrestartsより良いという理屈は次の状況が両方発生する場合に
- restartに時間がかかりすぎる → 実装によって回避可能
- リソース競合が頻繁に怒る → CPU数を増やすことによって回避可能
restartの方がblockingより応答時間は増える
- restert時にロック解放する必要があるため*1
ロックの取り合いをさせるくらいならアボートさせる方が良いというのが最近のDB界隈のトレンド
トランザクションは本来APエンジニアに見せるべきではない
- 本来ならAPエンジニアにはcheckpointを設定させるだけにするべき
ブロックは利己的
リスタートは自己犠牲的
abortは処理が重そうだけどlockの方が軽いのではというのが一般的だが、実態はabortさせてredoする方がパフォーマンスが良い。
- この本はrestart派
- 神林さんはblocking派
  - ただし単純なlockではなく後ろにずらす
    - 先日のsundialの論文の発表でも似たような事を言われていたような?
- 最近はトランザクションの量が多いので、キャッシュの汚染率が高い
  - 定説としてこの本に書かれている内容から時代が変わっている
    - ただこの本が古いという訳ではなく、lockとrestartのコストはアーキテクチャに依存するので随時計測する必要がある。

2PLの検討(Basic 2PL,Conservative 2PL)

Basic 2PLとConservative 2PLについて地球で一番わかりやすい解説はこちら

qiita.com

※以後Basic 2PLをB2PL,Conservative 2PLをC2PLと略します

理屈上はB2PLの方がC2PLよりロックを保持している時間が短い
一見B2PLの方がパフォーマンス上メリットがありそうである
ただしこれはデータ競合の発生が少ない場合のみ。
データ競合の発生が激しくなるにつれC2PLの方がロックを保持している時間が短くなる

この節p91の「Predeclaration」ですがなぜデータ競合が多いとC2PLが勝るのか、根拠がよくわかりませんでした。

結論としてはC2PLを導入することによって - デッドロック回避 - DCスラッシングの阻止(軽減) のメリットある。(後者の方が期待度が高い)

性能限界 ~DC Thrashing ギリギリまでパフォーマンスをあげる~

リソースが無限と考えても、トランザクションを増やしたり、並列化するとスループットは上がるが、どこかで下がるポイント(DC Thrashing)がある。

DC-thrashing thus defines an operating region the combination of parameters that affect the performance.

実はこれは計算で算出可能

N:MPL(multiprogramming level)多分トランザクション数
k:一つのtransactionが要求する平均lock数
D:データ資源

の時DC Waolkoad $W = k^{2}N/D \lt 1.5$

だから性能限界は

$k^{2}N/D \lt 1.5$

となる。が、これは

DBアクセスが一様的である前提
- ピークとかない。増減しない平均的な接続が常に発生するイメージ
リソース競合を考慮していない

なのでかなり楽観的な数値である。あくまで1.5というのはこの規模の数字である、という参考を示しているにすぎない。

MPLについて

MPL(並列化するプロセス数)は1.5D/k²以上あげるべきではない。
- N(MPL)をあげるとデッドロックが発生する率も上がる
- restartのコストが高い場合はさらにNを下げる必要がある

Long Transactionについて

以下の事象はスループットを下げる要因となる

トランザクションあたりのロック数
トランザクションが長い

そもそもトランザクションよりもロックが増えることによる影響が大きいのでトランザクションを分割することでworkloadをあげることができる

例えば

トランザクション数N,ロック数kを分割して
トランザクション数2N,ロック数k/2にする

前述の式

$W = k^{2}N/D$

に当てはめると

$(k/n)^{2}(2N)/D = k^{2}N/2D$ となり、これは分解前の $W=k^{2}N/D$ より倍よくなっている。

Granularity(粒度)について

Granularityの定義はchapter1のp2に書いてある

The size of the data contained in a data item is called the granularity of the data item.

小さいD(荒い granularity)は大きな範囲にロックがかかる
大きいD(細かい granularity)は小さな範囲にロックがかかる

Granularityが性能に及ぼす要因は3つある

1.ロックオーバーヘッド
- granularityが細かいほどロックが必要=オーバーヘッドが増える
2.データ競合
- granularityが荒いほどデータ競合が起こる可能性がある
- ただし、granularityが細かければ良いという訳ではない
  - 一般的にgranularityが細いほどロックが増える傾向にある
  - ロックが増えるともちろんロックの衝突(Data contation)も起こりやすくなる
3.リソース競合
- 前述したが、データ競合はリソース競合を改善する可能性がある
  - ranularityが荒いとリソース競合が起きにくい。
  - ranularityが細かいとリソース競合が起きやすい

上記の3要因を踏まえるとGranularityによるスループットの変化は以下のグラフのようになる

f:id:yuyubu:20180928005540p:plain — Granularityとスループットの関連。p95から引用したものに補足説明したもの

ただしこのグラフのようなスループット増減を必ずとるわけではない
- 例1:データベースの大部分にアクセスする長いトランザクションの場合
  - 粒度を細かくしても結局ロックが増えるだけなのでDの増加に対してkが伸び悩まないため①の性能劣化より後のスループット変化が起こらない
- 例2:短いトランザクションに関してはDの増加に伴うkの伸び悩みが早く起こるので①の性能劣化が現れない
  - いきなり右肩上がりのグラフになる
Read Lock
- 今まではWrite Lockを前提に考えてきたが、lockの何割かがread lockと考えるとパフォーマンスは工場する
アクセスの偏り
- アクセスの偏りが発生しているとworkload(負荷)増加の恐れがある