Redmineチケットが深い階層になっている時に稀にLock wait timeoutが起きる症状

Redmineチケットが深い階層になっている時に稀にLock wait timeoutが起きる症状があるらしいのでメモ。

【現象】
Redmine本家の下記のスレッドで、Redmineチケットが深い階層になっている時に稀にLock wait timeoutが起きる症状があるらしい。

How to reproduce "Lock wait timeout" on production.log - Redmine

Defect #19344: MySQL 5.6: IssueNestedSetConcurrencyTest#test_concurrency : always fails - Redmine

Feature #18860: Replace awesome_nested_set gem with a custom implementation of nested sets - Redmine

症状を再現させるには、MySQLのコンソール画面で、Issuesテーブルにテーブルロックを故意にかけた後、チケット更新すると、Lock wait timeoutが発生する。

begin;
select * from issues for update;

テーブルロックがかかっているのだから、デッドロックが起きるのは当たり前だが。
コミッタのまるやまさんによれば、Defect #19344: MySQL 5.6: IssueNestedSetConcurrencyTest#test_concurrency : always fails - Redmineで既に認識済みで、MySQLのVer5.6以上で発生するらしく、PostgreSQLを使った方がいいよ、と勧めている。

(引用開始)
MySQL >= 5.6 and MariaDB have problem (#19344).
I recommend you use PostgreSQL instead of MySQL and MariaDB.
(引用終了)

直接関係しないが、Redmineプロジェクトが3000個以上もありネストしている場合でも、似たような症状が稀に発生するらしい。

Defect #19976: Redmine can't work with 3000 projects - Redmine

【推測される原因】
普通は上記のような症状は発生しないが、DB更新や画面表示の性能が悪い時に、おそらくチケットの階層構造が深いチケットを更新しようとすると、デッドロックが起きているのではないかと思われる。
階層の個数が数十個というレベルではなく、数百、数千というオーダーではないか、と推測される。

【Redmineで無限の階層を実現している仕様】
Redmineのチケットの階層構造は、awesome_nested_setというRubyGemで実装されている。
これは、RDBにおける再帰構造を入れ子集合モデルで実現しているのが重要なポイントだ。
換言すれば、awesome_nested_setというRubyGemがあるから、チケットの階層を無限にする仕様で実装できたのかもしれない。

Railsでawesome_nested_setを使って階層構造を作成する - Rails Webook

collectiveidea/awesome_nested_set: An awesome replacement for acts_as_nested_set and better_nested_set.

RDBでは再帰構造を実現するのが難しく、階層を例えば5回までに限定するなど、無限回まで拡張することはやりにくかった。
だから、Oracleでは、connect by句のような特殊な方言を使って、再帰構造のデータをSQLで取得できるようにしていた。

しかし、RDBで再帰構造を無限階層まで実現する方法は、入れ子集合モデルで既にアイデアは公表されており、Redmineはそのモデルを実装している。
だから、Redmineでは、チケットもプロジェクトも無限の階層を作り出すことができる。
実際、Issuesテーブルにlft, rgtというカラムがある理由は、入れ子集合モデルを実現しているからだ。

Redmineチケットの階層化の実装方法: プログラマの思索

Redmineでトラブル発生！素人が原因を調査して解決するまでにやったことまとめ ・ DQNEO起業日記

入れ子集合モデルに関しては、下記の記事が分かりやすい。
また、「達人に学ぶDB設計 徹底指南書」でも詳しく説明されている。

第5回　SQLで木構造を扱う～入れ子集合モデル　（1）入れ子集合モデルとは何か ：SQLアタマアカデミー｜gihyo.jp … 技術評論社

入れ子集合モデルでチケットの階層構造を実現した時のボトルネックは、既存の深い階層構造を持つチケットのツリーに対し、1個のチケットを追加するとか、変更する場合、該当の階層構造のチケット全てのレコードに更新がかかるために、影響が大きいからだ。
つまり、Issuesテーブルのlft, rgtのカラム全てを再計算して更新し直すため、階層構造が深くなるほど、更新対象になるレコードも増える。
データ更新時間が長くなれば、デッドロックになる可能性も高くなる。
おそらく上記の現象は、階層構造が深くて、階層構造の配下にあるチケットの枚数がかなり多いのではないか、と推測される。

入れ子集合モデルの弱点はデータ更新の頻度が多くなり、更新の影響範囲が広い、ということだが、下記の記事では、Issuesテーブルのlft, rgtのカラムに有理数を設定可能にすることで対応できる、と紹介されている。
つまり、有理数の稠密性という特徴を生かせば、DB更新の影響範囲を狭めることができる、ということだ。

第6回　SQLで木構造を扱う～入れ子区間モデル　（1）もしも無限の資源があったなら ：SQLアタマアカデミー｜gihyo.jp … 技術評論社

上記のような話を踏まえて、階層構造が深い場合にデッドロックが起きる現象を考えると、Redmineはワークフロー設定のような画面操作だけでなく、入れ子集合モデルのようなデータ構造までよく考えて作られていることが分かる。

個人的には、Redmineのテーブル設計をきちんと調査して、どのような設計思想でどんなテーブル構造で作られているのか、を見てみたいと思う。