MySQL InnoDB Record Lock
先日 InnoDB Record Lock による Deadlock と見受けられる事象にあたって調査することになった。その際に整理した InnoDB の Index Tree および Record Lock の挙動・実装をここにまとめる。
How InnoDB stores Index
まずは InnoDB が Index をどのようなデータ構造で扱っているかについて説明する。
InnoDB indexes が B-tree (B+-tree) で実装されているのは有名な話だと思う。InnoDB が実装され始めた 1990s 年代当時、SSD は主流ではなかったはずで、一方全てのデータが Memory に乗り切るはずもなかった。そこで、Disk 上でいかに効率的にデータを保存するか、ということで B-tree が選択されたのだろう。
厳密には、2 種類の Index が存在する。... Clustered Indexes と Secondary Indexes と呼ばれる。 Clustered Indexes は primary-key を node key とし、leaf nodes には実際のデータの値を格納する。すべての MySQL はこの Clustered Indexes を持つことになる。
一方、Secondary Indexes はいわゆる index を設定したときに作成される Index tree で、leaf nodes には Clustered Indexes の primary key node への reference を持つことになる（実データを持つわけではない）。Secondary Indexes によって、特定の検索パターンに対する検索効率を高める目的で使われる。
InnoDB Index Tree
COLUMN: All changes made to the index tree are stored to WAL (Write Ahead Log), or Redo Log in InnoDB terminology. This is the append-only logs which store all the history of changes. Thanks to this Redo Log, InnoDB can ensure consistency of data before/after the outage.
Record Locks
Latest Transactions を確認する場合 SHOW ENGINE INNODB STATUS の出力結果が使える。Latest Transactions の他にも、foreign key errors, detected deadlocks, transactions, File I/O などが確認できる。
ここで、Record Lock が具体的には何を表すかを考えてみる。Record Lock とは、先程述べた Index Tree の leaf nodes に対する共有ロックまたは排他ロックのことである。
Record Lock Behaviour
COLUMN: InnoDB supports other types of lock as well, for example "Gap Locks" and "Next-Key Locks". Their behaviours can be easily understood once you find out that InnoDB stores indexes as B-tree and lock happen there. For example, Gap Locks is the mechanism to acquire locks between one index record and the another (that is why it is called "gap"). As for Next-Key Locks, it is
(Gap Lock) + (Record Lock of the next key).
Lock mode
Lock には、Shared lock (S) and Exclusive lock (X) の 2 種類の Lock Mode が存在する。
要するに、Shared lock はロックしている Index record を読み取るために複数のスレッド間で共有することができる。一方で、Exclusive Lock が Index record に対するロックを獲得している間は、他のスレッドはいかなる操作もできない。
例えば、transactions A/B が特定の Index record に対してロックを獲得しようとする。この時、transactions A, B それぞれがいずれの Lock mode を使った時、結果として Index record への操作が Conflicts するかどうかを示した条件テーブルである。いずれかのスレッドが Exclusive Lock を獲得している場合、必ず片方のスレッドは待たされることになる。
| transaction A \ transaction B | acquire S | acquire X |
|---|---|---|
| acquire S | Non-blocked :) | Conflicts :( |
| acquire X | Conflicts :( | Conflicts :( |
Implementation
実際のロックの実装は、"latch" を用いて実装されている。そのデータ構造は、実際的には自前で実装されているRW lock によるものである。
storage/innobase/lock/lock0lock.cc
そのラッチは、複数の rw_lock_t インスタンスで複数の cache lines で負荷を分散するために sharding されている。であるがゆえに、Sharded_ という prefix がついている。紛らわしいが、Sharead Lock の "Shared" の typo では無い点に注意。
storage/innobase/include/sync0shared_rw.h
興味深い点としては、Shared Lock/Exclusive Lock をこの RW-Lock を用いてどのように実装しているかという点である。内部的には、この RW-Lock を複数有する Array として表現していて、Exclusive lock はこの Array 内のすべての RW-Lock を獲得すること、Shared lock はこの Array 内のいずれかの RW-Lock を獲得すること、というように実装している。