MySQL-5.6のMRRにデッドロック回避の夢を見る
この記事は、はてなエンジニアアドベントカレンダー2016の7日目の記事です。
昨日は id:haya14busa さんのSum/Union/Variant Type in Go and Static Check Tool of switch-case handlingでした。
こんにちは、ドラゴンボールのヤムチャ状態になってるichirin2501です。
技術ネタとして何を書こうかと考えたのですが、
またMySQLでロックの話をする運びとなってしまいました。
技術ネタついでに今年最後の記事になると思われるので、
この1年のアウトプットを振り返ってみますと、
はてな・ペパポ技術大会 〜インフラ技術基盤〜
計算量と僕とWeb開発 / computational complexity and I and Web // Speaker Deck
Haten Engineering Seminar #6 〜インフラ編〜
MySQL運用とらぶるすとーり〜^2 / MySQL-Troubleshooting-Story // Speaker Deck
おお、なんと2つも。
MySQL芸人一歩手前などと冗談で言われたりしてますが、私は元気です。
斧もお待ちしております。
でも、そろそろMySQL以外の話がしたいと思ってる次第です。
目次
はじめに
MySQLの行ロックはインデックスレコードロックであり、異なるセカンダリインデックスからのロック獲得時にデッドロックが発生する問題があります。今回はMySQL-5.6で追加されたMRR(Multi-Range Read)機能によってそれを解決できないか調査した記事です。以前にも5.6で追加されたICP(Index Condition Pushdown)機能によるロック挙動を調査したことがあるので、興味のある方はそちらもご参照ください。気が付けば2015年10月に5.7が正式リリースされ、5.6の正式リリースは2013年2月らしいので既に3年以上経っていますね。はやいものです。
MRR(Multi-Range Read)とは
MySQL-5.6 から新しく追加された機能の一つで、なるべくランダムアクセスを減らしてシーケンシャルアクセスにする最適化のことです。HDDなどのランダムとシーケンシャルアクセス速度に差があり、その影響が支配的な環境下において効果がありそうです。
公式にも丁寧に書かれています。
セカンダリインデックスでの範囲スキャンを使用して行を読み取ると、テーブルが大きく、ストレージエンジンのキャッシュに格納されていない場合、ベーステーブルへのランダムディスクアクセスが多発する結果になることがあります。Disk-Sweep Multi-Range Read (MRR) 最適化を使用すると、MySQL は、最初にインデックスだけをスキャンし、該当する行のキーを収集することによって、範囲スキャンのランダムディスクアクセスの回数を軽減しようとします。続いてキーがソートされ、最後に主キーの順序を使用してベーステーブルから行が取得されます。Disk-Sweep MRR の目的は、ランダムディスクアクセスの回数を減らし、その代わりに、ベーステーブルデータの順次スキャンを増やすことです。
MySQL 5.6 リファレンスマニュアル | Multi-Range Read の最適化
確かにセカンダリインデックスと実レコードの順序には相関がないため、単純にセカンダリインデックスの走査順で引くとランダムアクセスになってしまいます。ただ、一旦ソートする必要がありCPUを使うのと、SSDだとアドバンテージが小さくなります。また、バッファプールに乗ってる状態なら効果も見込めないので、一般的にMRRによって改善が見込めるケースは少なそうな感触です。
MRRの機能を図にするとこんな感じのようです。
クラスタインデックスの図がないため、正確ではありませんが意図は伝わるかと思います。
この機能から何故ロックの挙動調査の話になるかと言うと、MySQL(InnoDB)のロックはインデックスレコードロックだからです。インデックスの走査順にロックを獲得するため、その周辺の挙動が変わるとロック順に影響すると考えたためです。
解決したいデッドロックについて
さて、当然セカンダリインデックスとクラスタインデックスにも順序の相関はありません。相関がないために発生するデッドロックがあります。
githubに挙げた例をそのまま持ってきますが、図も合わせて簡単に紹介します。
テーブル定義 CREATE TABLE `shadow_lock` ( `id` INTEGER unsigned NOT NULL auto_increment, `code_id` INTEGER unsigned NOT NULL, `token_id` INTEGER unsigned NOT NULL, `value` INTEGER unsigned NOT NULL, PRIMARY KEY (`id`), UNIQUE `shadow_lock_code_id` (`code_id`), UNIQUE `shadow_lock_token_id` (`token_id`) ) ENGINE=InnoDB DEFAULT CHARACTER SET utf8mb4; mysql> select * from shadow_lock; +------+---------+----------+---------+ | id | code_id | token_id | value | +------+---------+----------+---------+ | 1000 | 1 | 299 | 10000 | | 1001 | 2 | 298 | 20000 | | 1002 | 3 | 297 | 30000 | … | 1099 | 100 | 200 | 1000000 | | 1100 | 101 | 199 | 1010000 | | 1101 | 102 | 198 | 1020000 | | 1102 | 103 | 197 | 1030000 | | 1103 | 104 | 196 | 1040000 | | 1104 | 105 | 195 | 1050000 | | 1105 | 106 | 194 | 1060000 | | 1106 | 107 | 193 | 1070000 | | 1107 | 108 | 192 | 1080000 | | 1108 | 109 | 191 | 1090000 | | 1109 | 110 | 190 | 1100000 | | 1110 | 111 | 189 | 1110000 | | 1111 | 112 | 188 | 1120000 | ...
セカンダリ-クラスタインデックス間はデータ列の相関がなくランダムアクセスですが、理解し易い形にするために意図的に単純な逆順にします。
カラムA(昇順) -> id(昇順)=> code_id カラムB(昇順) -> id(降順)=> token_id
次にデッドロックになるようなクエリを用意します。
TA> BEGIN; TB> BEGIN; TA> SELECT * FROM shadow_lock WHERE code_id IN('100','101','102','103','104','105','106','107','108','109','110') FOR UPDATE; TB> SELECT * FROM shadow_lock WHERE token_id IN('190','191','192','193','194','195','196','197','198','199','200') FOR UPDATE;
上記のクエリがどのような流れでデッドロックになるのかを示した図が以下のものです。
shadow_lock_code_idを利用するのが上のセカンダリインデックス、shadow_lock_token_idを利用するのが下のセカンダリインデックスになります。後者だとクラスタインデックスのアクセス順は降順となり、お互いに被ってる部分でデッドロックが発生します。これを回避するためには、ロックを獲得するときのインデックスは共通させるなどの手が必要です。
ここで話を戻しましょう。仮にMRRによってクラスタインデックスのロックを獲得する前にソート処理が行われてるのだとしたら、異なるセカンダリインデックスを使ったロックでも順序が固定されてデッドロックが回避できそうですね!
ということで検証します。
MRRのロック動作検証
先程同様クラスタ-セカンダリインデックス間のデータ対応は逆順で初期データを用意します。
CREATE TABLE `player` ( `id` bigint(20) unsigned NOT NULL, `level` bigint(20) unsigned NOT NULL, `name` varchar(191) NOT NULL, PRIMARY KEY (`id`), KEY `idx_level` (`level`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4; mysql> select * from player; +--------+--------+--------------+ | id | level | name | +--------+--------+--------------+ | 1 | 100000 | i:1:l:100000 | | 2 | 99999 | i:2:l:99999 | | 3 | 99998 | i:3:l:99998 | | 4 | 99997 | i:4:l:99997 | | 5 | 99996 | i:5:l:99996 | | 6 | 99995 | i:6:l:99995 | | 7 | 99994 | i:7:l:99994 | | 8 | 99993 | i:8:l:99993 | | 9 | 99992 | i:9:l:99992 | ... | 99995 | 6 | i:99995:l:6 | | 99996 | 5 | i:99996:l:5 | | 99997 | 4 | i:99997:l:4 | | 99998 | 3 | i:99998:l:3 | | 99999 | 2 | i:99999:l:2 | | 100000 | 1 | i:100000:l:1 | +--------+--------+-----------------+ 100000 rows in set (0.08 sec)
MRR onなら図-xのロック順序から以下のように変わるはずです。
検証する環境を整えます。MRRはデフォルトでONですがオプティマイザによるコスト計算によるとほぼ?使われないようです。コスト計算を無視して条件を満たすクエリなら必ず使用するようにします。MRRが使用されるときはEXPLAINにUsing MRRと表示されます。
mysql> EXPLAIN SELECT * FROM player WHERE level IN(100,500,1000,5000,10000); +----+-------------+--------+-------+---------------+-----------+---------+------+------+-----------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+-----------+---------+------+------+-----------------------+ | 1 | SIMPLE | player | range | idx_level | idx_level | 8 | NULL | 5 | Using index condition | +----+-------------+--------+-------+---------------+-----------+---------+------+------+-----------------------+ 1 row in set (0.00 sec) mysql> SELECT @@optimizer_switch\G *************************** 1. row *************************** @@optimizer_switch: index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on,index_condition_pushdown=on,mrr=on,mrr_cost_based=on,block_nested_loop=on,batched_key_access=off,materialization=on,semijoin=on,loosescan=on,firstmatch=on,subquery_materialization_cost_based=on,use_index_extensions=on 1 row in set (0.00 sec) mysql> SET optimizer_switch='mrr_cost_based=off'; Query OK, 0 rows affected (0.00 sec) mysql> SELECT @@optimizer_switch\G *************************** 1. row *************************** @@optimizer_switch: index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on,index_condition_pushdown=on,mrr=on,mrr_cost_based=off,block_nested_loop=on,batched_key_access=off,materialization=on,semijoin=on,loosescan=on,firstmatch=on,subquery_materialization_cost_based=on,use_index_extensions=on 1 row in set (0.00 sec) mysql> EXPLAIN SELECT * FROM player WHERE level IN(100,500,1000,5000,10000); +----+-------------+--------+-------+---------------+-----------+---------+------+------+----------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+-----------+---------+------+------+----------------------------------+ | 1 | SIMPLE | player | range | idx_level | idx_level | 8 | NULL | 5 | Using index condition; Using MRR | +----+-------------+--------+-------+---------------+-----------+---------+------+------+----------------------------------+ 1 row in set (0.00 sec) # 検証に使うレコードの確認 mysql> SELECT * FROM player WHERE level IN(100,500,1000,5000,10000) ORDER BY id; +-------+-------+-----------------+ | id | level | name | +-------+-------+-----------------+ | 90001 | 10000 | i:90001:l:10000 | | 95001 | 5000 | i:95001:l:5000 | | 99001 | 1000 | i:99001:l:1000 | | 99501 | 500 | i:99501:l:500 | | 99901 | 100 | i:99901:l:100 | +-------+-------+-----------------+ 5 rows in set (0.00 sec)
準備が出来ました。期待通りのロック獲得順になるか確かめるクエリを発行していきます。3つのトランザクションを並行させて実験します。
TA> BEGIN; TA> SELECT * FROM player WHERE id = 99001 FOR UPDATE; +-------+-------+----------------+ | id | level | name | +-------+-------+----------------+ | 99001 | 1000 | i:99001:l:1000 | +-------+-------+----------------+ 1 row in set (0.00 sec) TB> BEGIN; TB> SELECT * FROM player WHERE level IN(100,500,1000,5000,10000) FOR UPDATE; # TAのid=99001のロック解放待ち # 仮にMRRによって事前にソートしてからロック獲得処理が走ってるなら、id=90001, 95001のロックが獲得済みのはず # 3つ目のトランザクションでid=90001のレコードがロックされてることを確認する TC> BEGIN; TC> SELECT * FROM player WHERE id = 90001 FOR UPDATE; +-------+-------+-----------------+ | id | level | name | +-------+-------+-----------------+ | 90001 | 10000 | i:90001:l:10000 | +-------+-------+-----------------+ 1 row in set (0.00 sec) # |'-') ........あれ?
TCでid=99901のレコードがロックされてることは別途確認しました。MRR-on/offによってロック順序が変化していないことが分かりました。そんな。念のためもう少し調べてみます。まずはソースコードを漁ってきてMRR周りの処理を見てみます。
https://github.com/mysql/mysql-server/blob/71f48ab393bce80a59e5a2e498cd1f46f6b43f9a/sql/handler.cc#L6648-L6704
DsMrr_impl::dsmrr_fill_bufferの最後のほうでソート処理が入っています。如何にもそれっぽいですね。
my_qsort2(rowids_buf, n_rowids, elem_size, (qsort2_cmp)rowid_cmp,
(void*)h);
このソート処理の前にロック獲得処理が入ってると、今回のような結果になります。
MySQLのソースコードを読むのは難しいので、雑にGDBによる動的デバッグで当たりをつけるためにコンパイルから始めます。
// Debian7 $ sudo apt-get install cmake libncurses5-dev $ tar zxvf mysql-5.6.25.tar.gz $ cd mysql-5.6.25 $ cmake -DWITH_DEBUG:BOOL=ON -DMYSQL_DATADIR=/var/lib/mysql $ make $ sudo make install $ sudo mkdir /var/lib/mysql $ sudo /usr/local/mysql/scripts/mysql_install_db --user=mysql --datadir=/var/lib/mysql -basedir=/usr/local/mysql $ sudo cp /usr/local/mysql/support-files/mysql.server /etc/init.d/mysql $ sudo service mysql start
GDBでアタッチしてMRRの処理周りとロック獲得周りにブレークポイントを仕込む作業をします。ソート処理部分の手前にブレークポイントをセットしたいので、事前にコード行数を確認します。
githubのsrcと行数が異なっていたので改めてMRRのソート部分のコードを載せます。
# sql/handler.cc 6199 6200 /* Sort the buffer contents by rowid */ 6201 uint elem_size= h->ref_length + (int)is_mrr_assoc * sizeof(void*); 6202 uint n_rowids= (rowids_buf_cur - rowids_buf) / elem_size; 6203 6204 my_qsort2(rowids_buf, n_rowids, elem_size, (qsort2_cmp)rowid_cmp, 6205 (void*)h); 6206 rowids_buf_last= rowids_buf_cur; 6207 rowids_buf_cur= rowids_buf; 6208 DBUG_RETURN(0); 6209 }
sql/handler.ccの6203行目で良さそうです。コード行数を確認したので仕込みます。
(gdb) b DsMrr_impl::dsmrr_fill_buffer Breakpoint 1 at 0x68715c: file /home2/ichirin2501/mysql-5.6.25/sql/handler.cc, line 6171. (gdb) b lock_rec_create Breakpoint 2 at 0xbcc558: file /home2/ichirin2501/mysql-5.6.25/storage/innobase/lock/lock0lock.cc, line 1803. (gdb) b /home2/ichirin2501/mysql-5.6.25/sql/handler.cc:6203 Breakpoint 3 at 0x6873be: file /home2/ichirin2501/mysql-5.6.25/sql/handler.cc, line 6203. (gdb) c Continuing.
mysql> SET optimizer_switch='mrr_cost_based=off'; Query OK, 0 rows affected (0.00 sec) mysql> SELECT @@optimizer_switch\G *************************** 1. row *************************** @@optimizer_switch: index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on,index_condition_pushdown=on,mrr=on,mrr_cost_based=off,block_nested_loop=on,batched_key_access=off,materialization=on,semijoin=on,loosescan=on,firstmatch=on,subquery_materialization_cost_based=on,use_index_extensions=on 1 row in set (0.00 sec) mysql> EXPLAIN SELECT * FROM player WHERE level IN(100,500,1000,5000,10000); +----+-------------+--------+-------+---------------+-----------+---------+------+------+----------------------------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+-----------+---------+------+------+----------------------------------+ | 1 | SIMPLE | player | range | idx_level | idx_level | 8 | NULL | 5 | Using index condition; Using MRR | +----+-------------+--------+-------+---------------+-----------+---------+------+------+----------------------------------+ 1 row in set (0.01 sec) mysql> begin; Query OK, 0 rows affected (0.00 sec) mysql> SELECT * FROM player WHERE level IN(100,500,1000,5000,10000) FOR UPDATE;
[Switching to Thread 0x7f8d26f16700 (LWP 121200)] Breakpoint 1, DsMrr_impl::dsmrr_fill_buffer (this=0x236dfe8) at /home2/ichirin2501/mysql-5.6.25/sql/handler.cc:6171 6171 int res= 0; (gdb) n 6172 DBUG_ENTER("DsMrr_impl::dsmrr_fill_buffer"); (gdb) 6173 DBUG_ASSERT(rowids_buf < rowids_buf_end); (gdb) 6175 rowids_buf_cur= rowids_buf; (gdb) 6176 while ((rowids_buf_cur < rowids_buf_end) && (gdb) 6177 !(res= h2->handler::multi_range_read_next(&range_info))) (gdb) 6176 while ((rowids_buf_cur < rowids_buf_end) && (gdb) Breakpoint 2, lock_rec_create (type_mode=3, block=0x7f8d2ca696c0, heap_no=641, index=0x236ff38, trx=0x239b338, caller_owns_trx_mutex=0) at /home2/ichirin2501/mysql-5.6.25/storage/innobase/lock/lock0lock.cc:1803 1803 ut_ad(lock_mutex_own()); (gdb) 1804 ut_ad(caller_owns_trx_mutex == trx_mutex_own(trx)); (gdb) 1805 ut_ad(dict_index_is_clust(index) || !dict_index_is_online_ddl(index)); (gdb) c Continuing. Breakpoint 2, lock_rec_create (type_mode=1027, block=0x7f8d2ca6a480, heap_no=308, index=0x236fc08, trx=0x239b338, caller_owns_trx_mutex=0) at /home2/ichirin2501/mysql-5.6.25/storage/innobase/lock/lock0lock.cc:1803 1803 ut_ad(lock_mutex_own()); (gdb) Continuing. Breakpoint 2, lock_rec_create (type_mode=547, block=0x7f8d2ca696c0, heap_no=640, index=0x236ff38, trx=0x239b338, caller_owns_trx_mutex=1) at /home2/ichirin2501/mysql-5.6.25/storage/innobase/lock/lock0lock.cc:1803 1803 ut_ad(lock_mutex_own()); (gdb) Continuing. Breakpoint 2, lock_rec_create (type_mode=1027, block=0x7f8d2ca6a740, heap_no=221, index=0x236fc08, trx=0x239b338, caller_owns_trx_mutex=0) at /home2/ichirin2501/mysql-5.6.25/storage/innobase/lock/lock0lock.cc:1803 1803 ut_ad(lock_mutex_own()); (gdb) Continuing. Breakpoint 2, lock_rec_create (type_mode=3, block=0x7f8d2ca69980, heap_no=496, index=0x236ff38, trx=0x239b338, caller_owns_trx_mutex=0) at /home2/ichirin2501/mysql-5.6.25/storage/innobase/lock/lock0lock.cc:1803 1803 ut_ad(lock_mutex_own()); (gdb) Continuing. Breakpoint 2, lock_rec_create (type_mode=1027, block=0x7f8d2ca6aa00, heap_no=34, index=0x236fc08, trx=0x239b338, caller_owns_trx_mutex=0) at /home2/ichirin2501/mysql-5.6.25/storage/innobase/lock/lock0lock.cc:1803 1803 ut_ad(lock_mutex_own()); (gdb) Continuing. Breakpoint 2, lock_rec_create (type_mode=547, block=0x7f8d2ca69980, heap_no=495, index=0x236ff38, trx=0x239b338, caller_owns_trx_mutex=1) at /home2/ichirin2501/mysql-5.6.25/storage/innobase/lock/lock0lock.cc:1803 1803 ut_ad(lock_mutex_own()); (gdb) Continuing. Breakpoint 2, lock_rec_create (type_mode=3, block=0x7f8d2ca69c40, heap_no=271, index=0x236ff38, trx=0x239b338, caller_owns_trx_mutex=0) at /home2/ichirin2501/mysql-5.6.25/storage/innobase/lock/lock0lock.cc:1803 1803 ut_ad(lock_mutex_own()); (gdb) Continuing. Breakpoint 2, lock_rec_create (type_mode=1027, block=0x7f8d2ca6acc0, heap_no=25, index=0x236fc08, trx=0x239b338, caller_owns_trx_mutex=0) at /home2/ichirin2501/mysql-5.6.25/storage/innobase/lock/lock0lock.cc:1803 1803 ut_ad(lock_mutex_own()); (gdb) Continuing. Breakpoint 2, lock_rec_create (type_mode=547, block=0x7f8d2ca69c40, heap_no=270, index=0x236ff38, trx=0x239b338, caller_owns_trx_mutex=1) at /home2/ichirin2501/mysql-5.6.25/storage/innobase/lock/lock0lock.cc:1803 1803 ut_ad(lock_mutex_own()); (gdb) Continuing. Breakpoint 2, lock_rec_create (type_mode=3, block=0x7f8d2ca69f00, heap_no=556, index=0x236ff38, trx=0x239b338, caller_owns_trx_mutex=0) at /home2/ichirin2501/mysql-5.6.25/storage/innobase/lock/lock0lock.cc:1803 1803 ut_ad(lock_mutex_own()); (gdb) Continuing. Breakpoint 2, lock_rec_create (type_mode=1027, block=0x7f8d2ca6af80, heap_no=239, index=0x236fc08, trx=0x239b338, caller_owns_trx_mutex=0) at /home2/ichirin2501/mysql-5.6.25/storage/innobase/lock/lock0lock.cc:1803 1803 ut_ad(lock_mutex_own()); (gdb) Continuing. Breakpoint 2, lock_rec_create (type_mode=547, block=0x7f8d2ca69f00, heap_no=555, index=0x236ff38, trx=0x239b338, caller_owns_trx_mutex=1) at /home2/ichirin2501/mysql-5.6.25/storage/innobase/lock/lock0lock.cc:1803 1803 ut_ad(lock_mutex_own()); (gdb) Continuing. Breakpoint 3, DsMrr_impl::dsmrr_fill_buffer (this=0x236dfe8) at /home2/ichirin2501/mysql-5.6.25/sql/handler.cc:6205 6205 (void*)h); (gdb) s my_qsort2 (base_ptr=0x2367a28, count=5, size=8, cmp=0x687118 <rowid_cmp(void*, uchar*, uchar*)>, cmp_argument=0x236dd60) at /home2/ichirin2501/mysql-5.6.25/mysys/mf_qsort.c:105 105 if (count <= 1) (gdb) c Continuing.
GDBからハンドリングが戻ってきました。
mysql> SELECT * FROM player WHERE level IN(100,500,1000,5000,10000) FOR UPDATE; +-------+-------+-----------------+ | id | level | name | +-------+-------+-----------------+ | 90001 | 10000 | i:90001:l:10000 | | 95001 | 5000 | i:95001:l:5000 | | 99001 | 1000 | i:99001:l:1000 | | 99501 | 500 | i:99501:l:500 | | 99901 | 100 | i:99901:l:100 | +-------+-------+-----------------+ 5 rows in set (7 min 46.36 sec)
最初のwhileループ内でロック獲得処理が一通り走りきった後にmy_qsort2を呼び出してます。残念ながらソート処理後にされるわけではないことが分かりました。
まとめ
MySQL-5.6で追加されたMRR機能におけるロック挙動の調査を行いました。期待した挙動とはならず、抱えていたデッドロック問題の解決には結びつきませんでした。ついでにBKAJによるJOIN先のロック順序も確認しましたが変化はありませんでした。MRRが前提のアルゴリズムなので振る舞いは同じようです。MySQL-5.6から入ったICPではセカンダリ-クラスタインデックス間のロック挙動が変わっていたので、MRRにも少し期待を寄せましたが、こちらは変わらず。実装を深く見てないですが、先にロック獲得しない/できない理由があると見たほうが自然かもしれませんね。
明日のアドベントカレンダーは id:cockscomb さんです!!