InnoDBのChange Buffer(MySQL Server Blogより)

免責事項

この記事はMySQL Server Blogの投稿をユーザが翻訳したものであり、Oracle公式の文書ではありません。

THU, 2015/6/4 by Annamalai Gurusami

ストレージエンジンを設計するとき、最大の課題となるのは書込み操作の途中のランダムI/Oである。 InnoDBでは、テーブルは1つのクラスタインデックスを持ち、0またはそれ以上のセカンダリインデックスを持つ。インデックスはいずれも、B-treeである。 レコードがテーブルに挿入されるとき、レコードはまずはじめにクラスタインデックスに挿入され、それからそれぞれのセカンダリインデックスに挿入される。 その結果、結果として発生するI/O操作はディスクにランダムに分散する。I/Oパターンは更新、そして削除操作で同様にランダムである。 この問題を軽減する為に、InnoDBストレージエンジンは、変更バッファ(change buffer)(以前は、挿入バッファとして知られていたもので、これは一方でibufとIBUFという様々な内部名で利用されるのを見ることがあるだろう)と呼ばれる特別なデータ構造を持っている。

変更バッファはB-treeとは同種だが異なるもので、どんなセカンダリインデックスのレコードも保持することができる。ソースコードではユニバーサルツリーと呼ばれる。 変更バッファはInnoDBにただ1つ存在し、システムテーブルスペースに永続化される。 変更バッファのツリーのルートページは、システムテーブルスペース(スペースID 0)内の、FSP_IBUF_TREE_ROOT_PAGE_NO(4である)に固定されている。 サーバーが起動されたときに、変更バッファのツリーはこの固定ページ数を使ってロードされる。詳細に関してはibuf_init_at_db_start()関数を参照してほしい。

変更バッファの総サイズはコンフィグ可能でメインメモリ上に全ての変更バッファツリーが保持できるように設計されている。 変更バッファのサイズは、innodb_change_buffer_max_sizeシステム変数を利用して設定される。

変更バッファの概要

変更バッファはノンユニークセカンダリインデックス(NUSI)のみに適用できる。 InnoDBはNUSIへの3種類の操作、挿入、削除のマーキング、そして削除、をバッファリングする。これらの操作は、InnoDBでは、ibuf_op_tによって列挙されている。

バッファされる操作

/* Possible operations buffered in the insert/whatever buffer. See
ibuf_insert(). DO NOT CHANGE THE VALUES OF THESE, THEY ARE STORED ON DISK. */
typedef enum {
        IBUF_OP_INSERT = 0,
        IBUF_OP_DELETE_MARK = 1,
        IBUF_OP_DELETE = 2,

        /* Number of different operation types. */
        IBUF_OP_COUNT = 3
} ibuf_op_t;

変更バッファがリーフページ指向であることは、重要なポイントであり記憶にとどめておくべきである。 NUSIへの特定の操作は、関連するNUSIのノンルートリーフページがバッファプールで利用可能でない場合に限り、バッファリングされる。 これは、バッファされる変更はInnoDBシステム内のNUSIの特定のリーフページに事前定義されることを意味する。 これによってNUSIのリーフページ内の利用可能な空き領域を追跡することが必要となっている。 この追跡は、NUSIリーフページへのバッファされた操作をマージするときに、B-treeページが分割されたり、マージされることにならないように必要である。

特殊変更バッファフィールド

NUSIレコードが変更バッファにバッファリングされたとき、NUSIレコードの最初に4つの特殊な変更バッファフィールドが追加される。 4フィールドおよびそれぞれの内容については下記で説明する。変更バッファツリーにおける主キーは、{space_id, page_no, count}であり、countは特定のページに対して変更がバッファされた順序を保持するために利用される。変更バッファの列フォーマットは、時とともに進化してきており、MySQL 5.5以降の情報を次のテーブルに示す。

変更バッファレコード自体の列フォーマットは常にREDUNDANTである。

変更バッファビットマップページ

各ページの空き領域情報は、変更バッファビットマップページと呼ばれる事前定義されたページで追跡される。これはibufビットマップページとしても知られる。 これらのページは常にエクステントの記述ページを追っている。次のテーブルは変更バッファビットマップページのいくつかの事前定義されたページを示す。

ページ番号1は、FSP_IBUF_BITMAP_OFFSETとも呼ばれる。 この変更バッファビットマップページは次の質問に素早く答えるのに助けとなるだろう。

• そのページにibuf(挿入/変更バッファ)ツリーにバッファされた変更があるのだろうか？ページがバッファプールに読込まれているときにこれが問われる。バッファされた変更はバッファプールに反映される前に、実際のページにマージされる。
• そのページは変更をバッファする為の十分な空き領域があるだろうか？NUSIのリーフページを修正しようとし、バッファプールですでに利用できなくなっているときにこれが問われる。

次の節では、上記の質問に答える助けとなるibuf bitmap pageに格納される情報についてみてみよう。

変更バッファビットマップページに格納される情報

変更バッファビットマップページはそれぞれのページを表すのに4ビット(IBUF_BITS_PER_PAGE)使う。この配列は"ibuf bitmap"(挿入/変更バッファビットマップ)と呼ばれる。 この配列はIBUF_BITMAP(94である)のオフセットにあるページヘッダの後から始まる。ページ番号が与えられれば、そのページに関する4ビットの情報を含むibuf bitmapページは、 次のように計算される。ulint bitmap_page_no = FSP_IBUF_BITMAP_OFFSET + ((page_no / page_size) * page_size)

完全な計算方法についての詳細な情報が欲しい場合は、ibuf_bitmap_page_no_calc()を参照するとよいだろう。同じように、ページ番号が与えられれば、変更バッファビットマップページ内のオフセットには計算に簡単に利用できる4ビットの情報がある。これは読者への宿題としようと思う(詳細はibuf_bitmap_page_get_bits_low()を参照のこと)。次の表には4ビットに関する詳細な情報を記した。

これはそのページの2ビットだけが空き領域の情報を格納することができることを示している。これは0, 1, 2, 3の4値しか取りえない。 この2ビットを用いて、ページに対する空き領域の情報をエンコードをしてみる。次のような規則で、だ - 最低でも UNIV_PAGE_SIZE / IBUF_PAGE_SIZE_PER_FREE_SPACE バイトの変更バッファの空き領域があるべきである

/** An index page must contain at least UNIV_PAGE_SIZE /
IBUF_PAGE_SIZE_PER_FREE_SPACE bytes of free space for ibuf to try to
buffer inserts to this page.  If there is this much of free space, the
corresponding bits are set in the ibuf bitmap. */
#define IBUF_PAGE_SIZE_PER_FREE_SPACE   32

ページの空き領域の追跡

挿入操作(IBUF_OP_INSERT)がバッファされる前に、ターゲット内のNUSIのリーフページの利用可能な空き領域が変更バッファのビットマップページの利用できる情報を使って概算される。この変換は、ibuf_index_page_calc_free_from_bits()関数を利用して実施され、次の公式が利用される。

if (ibuf_code == 3) {
    ibuf_code = 4;
}
free_space = ibuf_code * (page_size / IBUF_PAGE_SIZE_PER_FREE_SPACE);

次の表は、変更バッファのビットマップページ内のエンコードされた値から意味のあるバイト値への変換を提供する。

この情報を用いて、バッファされるレコードがページ内におさまるかどうかを決めることができる。十分な領域がない場合挿入はバッファされる。このアプローチを利用して、これらのレコードをNUSIにマージするときにページが分割されないようにしている。

空き領域の情報の更新

挿入または削除操作をバッファした後に、変更バッファのビットマップページ内の空き領域の情報は、それに応じて更新されなければならない(削除マーク操作は、空き領域の情報を更新しない)。空き領域の情報を更新するには、空き領域をIBUGのエンコードされた値に逆に変換する必要がある。これはibuf_index_page_calc_free_bits()関数で次の式を用いて実施される。

ibuf_code = max_ins_size / (page_size / IBUF_PAGE_SIZE_PER_FREE_SPACE);
if (ibuf_code == 3) {
     ibuf_code = 2;
}
if (ibuf_code > 3) {
     ibuf_code = 3;
}

上記の式では、max_ins_sizeはページが再構成された後でそのページで利用可能な最大挿入サイズ(最大空き領域)である。

NUSIリーフページのレコード数のカウント

パージ操作(IBUF_OP_DELETE)の場合、NUSIのリーフページのレコード数が0とならないことを確認する必要がある。 なぜならばInnoDBでは、B-treeのリーフページが空になることが許されないからだ。 最低でも1レコードは存在する必要がある。NUSIページのレコード数は未知数であるから（バッファプールにまだロードされていないため）、バッファされた挿入操作が考慮される。1つの挿入操作がバッファされれば、NUSIのページは1レコードは持つと思われる。2つの挿入操作がバッファされたなら2レコード持つと思われ、以下同様である。このようにして対象のNUSIのページは計算される。 ここで計算されたレコード数に基づいて、パージ操作がバッファされたりされなかったりする。これは挿入または削除マーク操作がバッファされていない場合は、パージ操作はバッファされえないことを意味する。

バッファされた変更の対象NUSIページへのマージ

NUSIリーフページへの変更はNUSIリーフページがバッファプール上になくなっている場合、変更バッファにバッファされる。これらのバッファ操作は様々な状況下で実際のNUSIにマージされ元に戻される。

1. NUSIリーフページがバッファプールに読込まれ、バッファがマージされるとき。NUSIリーフページはインデックスのルックアップ、インデックススキャンまたは先読みでバッファプールに読込まれる可能性がある。
2. InnoDBのマスタースレッドが、ibuf_merge_in_background()の定期呼出しでバッファをマージするとき
3. 特定のNUSIリーフページに多数の操作のバッファが発生したとき
4. 変更バッファツリーがその許容される最大サイズに達したとき

変更バッファのマージ操作は、ibuf_merge_in_backgroud() または ibuf_contract() 関数を呼ぶことで初期化される。 変更バッファのマージはフォアグラウンドでもバックグラウンドでも実施される。 フォアグラウンドの変更バッファのマージは、DML操作の一部として行われ、その結果エンドユーザーが体感する性能に影響する。 バックグラウンドの変更バッファのマージは、サーバー内でのアクティビティーが少ないときに定期的に実行される。

変更バッファによりB-treeのページが分割されたり、ページのマージ操作が起こらないようにする。またリーフページが空になってもならない。対象のNUSIリーフページがバッファプールに格納される前に、バッファされた変更が適用される。ページにバッファされた変更がマージされれば、変更バッファビットマップ内の関連する4ビットの情報も更新される。

結論

この記事ではInnoDBの変更バッファのサブシステムの概要について記載した。 セカンダリインデックスのレコードには、それが変更バッファ内に格納される前に付与される追加のフィールドについて説明した。これは変更バッファが変更バッファビットマップページを活用することにより、どのようにNUSIのリーフページの空き情報を追跡し続けるかに関する情報を提供した。また、NUSIリーフページ内のレコードが空にならないようにするため、その数を計算する必要があることを説明した。

この記事をレビューしてくれ、正確なものにしてくれたMarko Makelaに感謝します。質問があれば下記のコメントに気軽にコメントをポストして欲しい。

以上。MySQLをご利用いただき感謝！