トップ > database > innodb誕生までの歴史的な流れと内部仕様

innodb誕生までの歴史的な流れと内部仕様

database

業務の中でMySQLのバックエンドとして動くinnodbについて集中して調べる機会がありました。 innodbの歴史的な背景と、innodbの内部的な仕様についてメモを残しておこうと思います。

※ANSI SQL 92の話と、innodb独自の話は将来的に分けたい。

1. 前提条件

以下で解説の話は、 MySQL (innodb) かつトランザクション分離レベルが REPEATABLE_READ であることを前提にしています。 他のRDBMS、及びトランザクション分離レベルについてはスコープ外とします。

2. innodb誕生までの歴史

SQL92にてトランザクション分離レベルと Anomary が定義された。 その後、 論文 "A Critique of ANSI SQL Isolation Levels"*1 にて、新しいトランザクション分離レベルであるスナップショット分離が提唱された。

1981 MVCC

Philip A. Bermstein と Nathan Goodman による論文にて、Multiversion Concurrency Control (MVCC) のアイデアが提案された。*2

1992 SQL 92

トランザクション分離レベル及びそれと対となる Anomary の概念が ANSI/ISO standard SQL 92 で定義された。*3

1995 Snapshot Isolation

論文 A Critique of ANSI SQL Isolation Levels の中で、新しいトランザクション分離レベルである スナップショット分離(Snapshot Isolation) が提唱された。

参考 :A Critique of ANSI SQL Isolation Levels読んだ

2010 MySQL 5.5, Innodb

（スナップショット分離方式の実装として？）Multiversion Concurrency Control (MVCC) システムが搭載された、innodb 1.1が MySQL 5.5 のデフォルトのストレージエンジンとして採用された。*4

3. 主要な概念

innodbを理解するためのキー概念は3つある。

  • Anomary
  • トランザクション分離レベル (Transaction isolation level)
  • スナップショット分離 (Snapshot Isolation)

3.1. Anomary

SERIALIZABLE以外のトランザクション分離レベルを採用した場合に発生するconsistency的に問題のある状態を Anomary と呼ぶ。 SQL92では以下の3種類の Anomary が定義された。

  • Dirty Read
  • Non-repeatable Read
  • Phantom

その後、Fuzzy Read, Lost Update などが追加された。

上記で定義の Anomary はいずれも、「同一トランザクション内にてSELECT文を2回実行した結果に同じ結果が返されることを保証可能か？」という問題を扱っている。以下に具体例を示す。

  • 1回目と2回目でSELECTで得られるレコードの値が異なる
  • 1回目と2回目でSELECTで得られるレコードの行数が異なる

3.2. トランザクション分離レベル (Transaction isolation level)

wikipedia:トランザクション分離レベル

トランザクションは必ずしも安全に並列化できるとは限らない。そのためデータベース管理システムは各並行トランザクションが互いに影響を受けず分離された安全な範囲内でトランザクションを並行化する。あるいは、異常な振る舞い（anomalies）を起こしうる分離レベルが低い並行化を許容し、代わりに並行性を高めてトランザクション処理性能を上昇させる。 この安全性・一貫性と性能のトレードオフを生む、並行性トランザクションの分離具合がトランザクション分離レベルである

論文 : A Critique of ANSI SQL Isolation Levels

"(意訳) トランザクションを異なる分離レベルで実行することで、アプリケーション設計者は正確性とスループットのトレードオフに対し複数の選択肢を持つことができます。 トランザクション分離レベルを低くすると、トランザクションの同時実行性能は高まりますが、トランザクションの実行結果が曖昧(fuzzy)になったり、データの整合性が失われるリスクがあります。"

3.3. スナップショット分離 (Snapshot Isolation)

スナップショット分離は "A Critique of ANSI SQL Isolation Levels" にて提案の新たなトランザクション分離レベルである。レコードの情報をバージョン管理し、各トランザクションで別個に保持することでロックの取得を回避しつつ複数SQLの同時実行を可能にする。いくつかの実装が存在あるが、innodbではMVCCが採用されている。詳細は後述する。

4. Innodbの仕様

innodb の内部的な仕様について話を進めていく。

  • REPEATABLE READ 時の Anomary 特性
  • B+Tree周りのデータ構造
  • トランザクションの実行エンジン
  • システムバージョン番号 (System version number)
  • ロック制御
  • 一貫性非ロック読み取りとロック読み取り

4.1. REPEATABLE READ時のAnomary特性

  • 一貫性非ロック読み取り実行時
    • スナップショット分離により、ファジーリード及びファントムリードを回避
  • ロック読み取り実行時

参考：Innodb 中 RR 隔离级别能否防止幻读？

4.2. B+Tree周りのデータ構造

innodb は B+Treeを採用している。*5 Primaryキーはクラスタ化インデックスとして構成される。Primaryキー以外にインデックスを持つカラムがある場合セカンダリインデックスとして構成される。*6

物理ページのデータ構造は下図のようになっている。*7

InnoDBの物理ページのデータ構造

InnoDB Lock Monitorでの同様のデータ構造を確認できる。

InnoDB Lock Monitorでの物理ページの表示結果
UPDATE が実行されると、更新対象の行をコピーした新しい行が作成される。更新前のレコードはロールバックセグメントに Undo log として格納され、新しく作成されたレコード内の db_roll_ptr カラムからポインタが張られる。そして、この機構によりMVCC / Snapshot Isolationが実現される。*8

INSERTしたレコードを2回UPDATEした時のデータ構造

ロールバックセグメント, Undo log周りの実装レベルの詳細なデータ構造はこちらのスライドで解説されている。 DELETE は一度論理削除として実行され、その後パージされる。 論理削除を実現するために削除済みフラグ的な特殊なビットが用いられる

InnoDB は内部的に、データベース内に格納された各行に 3 つのフィールドを追加します。6 バイトの DB_TRX_ID フィールドは、行を挿入または更新した最後のトランザクションに対して、トランザクション識別子を指示します。また、 行内の特別ビットが削除されたとマークするように設定されている場合、削除は内部的に更新として処理されます。 https://dev.mysql.com/doc/refman/5.6/ja/innodb-multi-versioning.html

4.3. トランザクションの実行エンジン

全てのトランザクションは、最終的に COMMIT または ROLLBACK される。

またinnodbでは、トランザクションの実行に際し Undo log とロールバックセグメント(ロールポインタ)が利用されるレコード更新型アーキテクチャを採用している。

  • トラザクションID

4.4. システムバージョン番号 (System version number)

  • Innodbにおいて内部的に保持＆トランザクション実行の度に採番されるトランザクションIDのことを システムバージョン番号(System version number) と呼ぶ
  • (恐らく)各レコードの trx_id 欄に格納される
    • 削除ビットが立っていない時は、「最後にINSERT または UPDATEを実行したトランザクション」を示す
    • 削除ビットが立っている時は、「最後にDELETEを実行したトランザクション」を示す
  • 単調増加する方式なので、システムバージョンの大小を比較することで、複数のトランザクション間の時系列的な前後関係を判定することができる

4.5. ロック制御

4.6. 一貫性非ロック読み取りとロック読み取り

  • SELECT 実行に際し、2種類の動作モードが存在する。いずれのモードが採用されるかにより SELECT にて読み取れるレコードの範囲(対象)が変わる
  • トランザクション内にてSELECT実行時に
    • FOR UPDATE LOCK IN SHARE MODE を使用の場合：ロック読み取り( Locking Reads ) が実行される
      • 共有(S) ロックを取得のレコードに対し、排他(X) ロックを取ろうとすると衝突したレコードのみ 排他(X) ロックに変わる？
    • 上記以外： 一貫性非ロック読み取り( Consistent Nonlocking Reads ) が実行される

4.6.1. 一貫性非ロック読み取り (Consistent Nonlocking Reads) / スナップショット読み取り(snapshot reading)

4.6.1.1 スナップショット

4.6.2. ロック読み取り (Locking Reads) / 最新レコード読み取り (current reading)

  • ロック読み取り (Locking Reads)の際は、MVCCは使われず従ってスナップショットも参照されない
    • 常に、最新レコードのみが取得される。そのために、current readingと呼称されることもある。
  • ロック読み取り (Locking Reads)を利用することで、LostUpdate Anomaryを回避することができる。(反面ロックを取るので並行処理の性能は犠牲となる)

*1:A Critique of ANSI SQL Isolation Levels

*2:Concurrency Control in Distributed Database Systems

*3:ANSI/ISO standard SQL 92

*4:"InnoDBはMySQL 5.1が最初にリリースされたときから、2回アップデートが行われている。MySQL 5.1がGAになった後でいったんInnoDB Pluginバージョン1.0がリリースされたのだが、その名が示す通り既存の（ビルトインの）InnoDBと置き換えて利用するプラグイン形式のストレージエンジンであった。MySQL 5.5ではInnoDBのバージョンがInnoDB 1.1となり、ビルトインのストレージエンジンとなっている。" MySQL 5.5新機能徹底解説

*5:B+Tree index structures in InnoDB

*6:ソシャゲエンジニアの自分が開発に必須だなと思った知識（MySQL編）

*7: The physical structure of records in InnoDB

*8:MVCCとInnoDBでの実装について

*9:実践ハイパフォーマンスMySQL 第2版

/* https://sunrise033.com/entry/hatena-blog-how-to-hierarchicalize-categories */