MySQL 8.0.3 にて Innodb の default にされたロックスケジューラ CATS について調べたので、自分なりにまとめてみる
CATS のはなし #
CATS の略 #
Contention-Aware Transaction Scheduling の略
日本語訳すると、コンテンションを意識したトランザクションスケジューリング。
ロックスケジューラについて #
ロックスケジューラーは、複数のトランザクションが同一のオブジェクトのロックを取ろうとした時、どれが最初にロックを取るべきかを決定する。
どのトランザクションを優先すべきかはグラフの依存関係の解決が必要であり、NP困難となる例が多い。そのため 8.0 より前の MySQL や多くの database system では、 FIFO(First-In-First-Out)系のアルゴリズムを採用している。要は最初に要求がきたトランザクションにそのロックを与える方式で、これはシンプルである。
CATAS は上記従来のアルゴリズムよりレイテンシーを減少させ、スループットを向上させるアルゴリズムとして提案された。
CATS の仕組み #
CATS はひとつの単純な直感に基づいている。
「全てのトランザクションは等価ではなく、全てのオブジェクトも等価ではない」
あるトランザクションが既に多くのトランザクションが待っているオブジェクトのロックを取っているなら、そのトランザクションが新たに要求するロックは、優先的に与えられるべきである。何故なら、このようなトランザクションのロックを優先して開放していく事は、全体としてより多くのロックを開放する事に繋がるからである。
例えるなら同じコーヒーの行列に並ぶタクシー運転手とバスの運転手。バスの運転手に優先してコーヒーを提供する事は、結果的により多くの人をより早く目的地に到着させる。
ただし、CATS は常に適用されている訳ではなく、待機しているトランザクションが 32 を超える場合に適用される。この数字はテストによって決定された。
( 確かにパフォーマンス比較をみると、 client 数が 64 を超えない限りは FIFO と CATS に差がない、比較はブログ参照 )
以下、読んでいて感じた疑問と、その解決
疑問1. タクシーの運転手、永遠にコーヒー飲めない問題 #
個人的疑問としては、この手のスケジューリングの問題として、結果優先度が低いやつが永遠に待たされる問題がよく挙げられる。
と思って調べたら、既にブログで質問がされていた。
===
スタベーションの問題はどう扱っていますか？
例に挙げられているバスとタクシーではバスを優先する事は理にかなっていますが、常にバスのキューが2つ並んでいると、タクシーには順番は回ってきません。このようなケースは自然に解決されますか？
Peter Zaitsev
===
この質問への回答は、
1. バスとタクシーの例はあるが、実際には全てのトランザクションはタクシーである
確かにこれは例えの罠で、トランザクションがロックを取った時点では、そのトランザクションを待っている大量のトランザクションというのは存在しない。時間経過と共に増えていくので、常に大量のトランザクションを待たせた奴が来続けるという状況は多くはないのか。
2. 色々対策のアルゴリズムも入っている
挙げられているものは、
- ロックの待機時間が長いトランザクションの優先度を上げる
- ロックキューに時々バリアを入れて、バリアの前のキューを捌くようにする
などなど、今後新たに導入される奴もあるらしい。
疑問2. トランザクションの優先度の観点の問題 #
トランザクションの全体での優先度の観点について、待っているトランザクションの数を重要度として採用する事の根拠を知りたかった。
この辺は、論文を読んだ所ある程度書いてあった。
トランザクションの依存関係グラフからリアルタイムに正確な優先度を求める事は難しいので、ヒューリスティックに優先度を求める必要がある。そこで論文では以下のように色々な観点を比較している。
案1. 取得しているロックの合計数
Most Locks First(MLF)と呼ばれる。
最も多くのオブジェクトをロックしているトランザクションを優先する手法。この観点は、各オブジェクトの人気度を反映していない。例えば誰も参照しないオブジェクトをいくらロックを取っても全体の処理効率に影響は少ない。
案2. トランザクションを待たせているロックの合計数
MostBlocking Locks First(MBLF)と呼ばれる。
案1と違って、他トランザクションを待たせていない不人気なオブジェクトのロックは無視されている所が改善。ただし、トランザクションを待たせているか否かのゼロイチであるので、さらにその後ろにどれだけ待っているかは考慮していない。
案3. 依存関係サブグラフの深さ
DeepestDependency First(DDF)と呼ばれる。
案1,2 は水平競合と呼ばれるものに焦点を当てている一方、DDFは垂直競合に焦点を当てている。グラフが深いほどに待たせているトランザクションが多い事が期待されるが、正確ではない。
案4. サブグラフ内の依存関係の数(提案手法)
Largest-Dependency-Set-First(LDSF)と呼ばれる。
依存関係のサブグラフにおいて、もっとも依存関係が多いサブグラフを持つトランザクションを優先する。これは、そのトランザクションの下に吊り下がっているトランザクションの合計値で表す事ができる。
案その他
各トランザクションの実行時間などは問題の単純化のため考慮していないが、今後機械学習とか導入して、ロックのアクセスパターンや実行時間を考慮できると良いよね、程度に触れている。
参考 #
Contention-Aware Transaction Scheduling Arriving in InnoDB to Boost Performance | MySQL Server Blog
Contention-aware lock scheduling for transactional databases | ACM