B+Treeインデックスに関してよく出る言葉の正誤とその解説

お決まり

はじめに

  • B+Treeインデックスって意外とちゃんと知られてないなぁという印象があり、ふと考えた所具体例が意外と出てないので理解されにくいのではないかと仮説を立ててみたので用意してみた次第です。
  • 新しい技術とか書きたくなるのですが、たまにはこういう基礎系もいいよね。
    • そろそろ社会人エンジニア歴5年目になるので、後輩に向けて書くという側面も持ってます(予防線)

B+Treeインデックス?

①「主キーで検索することが最も速い」

  • 例えば以下の様なテーブルがあったとします。
CREATE TABLE `users` (
  `id`          int(11)     NOT NULL AUTO_INCREMENT,
  `name`        varchar(32) NOT NULL,
  `created_at`  int(11)     NOT NULL,
  `updated_at`  int(11)     NOT NULL,
  PRIMARY KEY (`id`),
  KEY `created_at` (`created_at`)
)
id name created_at updated_at
1 AAAA 1481100000 1481600000
2 BBBB 1481100000 1481700000
3 CCCC 1481200000 1481800000
4 DDDD 1481300000 1481900000
5 EEEE 1481400000 1482000000
6 FFFF 1481500000 1482100000

同じ1件を取得するときの動作の違いを比較する

1. PRIMARY KEYでの検索
SELECT * FROM users WHERE id = 4;

f:id:gotyoooo:20161219210936p:plain

  • ここで重要なのはレコードデータはPRIMARY KEYインデックスのリーフノードに紐付いているということ
2. SECONDARY KEYでの検索
SELECT * FROM users WHERE created_at = 1481300000;
  • ここで重要なのはSECONDARY KEYインデックスにはPRIMARY KEYが紐付いているということ

f:id:gotyoooo:20161219213203p:plain

結論

  • 図を見て分かる通り「主キーで検索することが最も速い」は正しい
  • SECONDARY KEYインデックスにはPRIMARY KEYが紐付いているため、内部では最終的にPRIMARY KEYによる探索が入るため

②「SELECT *が遅い」

  • ①のテーブルでSELECT id,created_at FROM users WHERE created_at = 1481300000; のようにSECONDARY KEYで検索をかけたとします
  • すると必要なデータがSECONDARY KEYインデックスのみで完結するため、COVERING INDEXとなりPRIMARY KEYによる探索がかかりません。 f:id:gotyoooo:20161219220555p:plain

結論

  • SELECT *が遅い」は正しい。
  • だがしかし、今回の例でnameやupdated_atのINDEXが貼られていないカラムのデータを必要とする場合は、「*」でも 「id,name,created_at」のように直接指定しても探索手法は変わりません。

③「インデックスを貼るとINSERT/UPDATE/DELETEが遅くなる」

  • 先程の①で利用したブランチノード・リーフノードは以下のようになっているとします。 f:id:gotyoooo:20161220134422p:plain
  • ココに次のレコードをINSERTしたとすると、かなりざっくりかつイメージですが以下のようなロジックでインデックスの更新が入ります。
    • あとに入ったレコードのcreated_atが最大値になることとかないかと思いますが、今回は説明のためなのでご容赦ください。
    • 実際にはありえませんが、ブランチノードの容量は3つで一杯になるとして話をすすめます。
id name created_at updated_at
7 GGGG 1481450000 1481450000

f:id:gotyoooo:20161220143138p:plain

PRIMARY KEYインデックスの更新

f:id:gotyoooo:20161220144015p:plain

SECONDARY KEY(created_at)インデックスの更新

f:id:gotyoooo:20161220144913p:plain

結論

  • 今回は2つインデックスがあったので上記2つの更新が入ります。
  • インデックスが増えれば増えるほどこの更新数が増えるため「インデックスを貼るとINSERT/UPDATE/DELETEが遅くなる」は正しい
  • 定期的にそのインデックスは本当に利用されているかを見ることが重要ですね。

最後に

  • 今回は3つ書きましたが、他にも「フルテーブルスキャンは悪」とか色々あるのでまた書きます。
  • 結局はちゃんと知ることと、改善が重要なわけです。
  • SQLアンチパターン 12章にも書かれていますがMENTORの原則が重要です。お忘れなきよう
    • Measure(測定)
      • スロークエリログとか取ろうね。
    • Explain(解析)
      • EXPLAIN 構文叩いて実行計画ちゃんと見ようね。
    • Nominate(指名)
      • 実行計画見るなりして修正方法考えようね。
    • Test(テスト)
      • 修正して実行して改善されているか確認しようね。良くなるまでMENを回そうね。
    • Optimize(最適化)
      • インデックスの容量を見て、できるだけキャッシュにのせようね。
    • Rebuild(再構築)
      • WindowsデフラグツールみたいにインデックスもOPTIMIZE TABLEとかでメンテナンスしようね。

アドベントカレンダーのお決まり

ISUCON5予選(1日目)にPHP7で参加。そして惨敗してきた。

  • ISUCON5予選に参加してきました。
  • 今までブログとか書いてこなかったので、振り返りにやっぱり書いたほうがいいなと始めました。
  • チーム名は「 < ruby>災骸円錐< rt>代官山のPHPおじさんたち< /rt>< /ruby> 」です。
    • 最初は「代官山のPHPおじさんたち」単体だったのですが、おもしろくないので 二つ名メーカー で付けました
    • PHPがなぜかバカにされてしまうのをなんとか止めたくてこんなチーム名にしてみた

ISUCON?

isucon.net

  • お題となるWEBサービスを「いい感じにスピードアップコンテスト」です。

    お題となるWebサービスを決められたレギュレーションの中で限界まで高速化を図るチューニングバトル、それがISUCONです。過去の実績も所属している会社も全く関係ない、結果が全てのガチンコバトルです。

  • 賞金も半端ない

    優勝賞金は今年もドドンと100万円!そしてなんとなんと準優勝も賞金30万円(予定)と超ウルトラ太っ腹コンテストとなっております!

  • 個人的には去年の雪辱を果たしたかった。

チームメンバー

  • 社内のメンバーで組みました。
  • @gotyoooo
    • 本人。本職はインフラ。ISUCONでも基本はインフラ周り
  • @keitarouhoge
    • 後輩。サーバサイドのエンジニア。ISUCONではアプリケーション実装周り。
  • @ut96
    • 先輩。サーバサイドのエンジニア。ISUCONでは同じくアプリケーション実装周り。去年も同チーム

事前準備

  • GitHubのプライベートリポジトリつくった
  • ISUCON用のrsa鍵ペア作った
  • Chatworkグループの部屋作った
    • 社内がChatworkなので
  • ISUCON4予選問題をUbuntu14.04で再現し、各自が練習できるようにしておいた
    • ここでPHP7化を試した
  • アクセスログの解析、MySQLのSlowLogの解析がぱっとできるようにした。

作戦

  • ISUCON4の問題でPHP5.6からPHP7(7.0.0RC3)にしただけでスコアがかなり伸びたのでPHP7でやろうと決めていた
    • 1.5倍ぐらいのスコアになったと記憶している(明確なスコアは記録していない…)
    • PHP7がなぜ高速なのかは、今回言及しない
    • sessionまわりの挙動が若干違うぐらいで、ほかは特に問題なかった
  • PHP7化、インフラ周りの最初のセットアップが終わった時点で作戦会議をしようと話す

直前

  • 社内の会議室をフルに使って戦いに備える f:id:gotyoooo:20150928110509j:plain

  • スタートが11:00からになったので軽く作戦の見直し

  • モンスターエナジー注入
  • 昼買いに行くの面倒だろうからピザの注文
    • これ大正解でした。
  • Node.js実装がなくなったことで、ほかのチーム大変そうだなーとか軽い気持ちで考えてた
    • フラグでした
  • サポート用チャットのidobataが不調で中の人の心配したり遊んでた

スタート直後

  • 衝撃が走る

    またPHPについては、実装を用意したものの整備が十分でなく、ベンチマークが期待する動作をせず、現時点で参加時の使用に耐えません。

  • さらに衝撃が走る
$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=15.04
DISTRIB_CODENAME=vivid
DISTRIB_DESCRIPTION="Ubuntu 15.04"
  • 追い打ちがかかる

    各言語実装は systemd で管理されています。基本的には systemctl stop/start ならびに systemctl enable/disable で制御します。

  • しばらく私はsystemdやらもろもろ環境周りで戦うことになった

    • systemctlをまだ全然触っていないことを後悔というか懺悔レベル
  • その間にPHP実装を動かすところまでを2人に頑張ってもらった

    • どうやらisset()まわりが全く入っておらず「undefined index」がでまくっていたようだ
    • @keitarouhogeいわくRubyっぽい書き方されてるとのことでした。(Rubyだったらそもそもない変数でもNULL返すもんね)
  • この辺をざっと片付けてスタートラインに立った感があったのが12時過ぎ頃だったと記憶している

実際にやったこと

  • 時系列は記録していなかった・・・

PHP環境まわり

  • PHP7.0.0RC3をインストール
    • phpenv, php-buildで入れた
  • systemd に PHP7でphp-fpm起動するようなスクリプト置く
  • sessionをmemcached

カーネルやらOSや接続周りもろもろ

Nginx

  • Nginxで静的ファイルをキャッシュ
  • Nginxでいくつかの静的ページを返す(以下の様な感じ)
    • ベンチマークからの静的ページアクセスはあまりなかったので効果は薄かった
location = /login {
  if ( $request_method = 'GET' ) {
    rewrite ^ /html/login.html last;
  }
}

MySQL

  • MySQLのmy.cnfをもろもろ修正
    • ここでAppArmorにはまる(/etc/my.cnfに設定していたが反映されない)
    • 途中間違えて innodb_flush_log_at_trx_commit = 1 にしてスコア激減。0にするのを最後まで忘れるという失態
    • /etc/mysql/mysql.conf.d/mysqld.cnfに置いた。追記内容は以下
innodb_buffer_pool_size                 = 3G
innodb_buffer_pool_dump_at_shutdown     = on
innodb_buffer_pool_load_at_startup      = on
innodb_sort_buffer_size                 = 16M
skip-name-resolve
skip_show_database
innodb_file_per_table
innodb_checksums = 0
innodb_support_xa = 0
symbolic-links=0

binlog_stmt_cache_size                  = 65536
max_allowed_packet                      = 4M
max_heap_table_size                     = 3072M
tmp_table_size                          = 3072M

binlog_cache_size                       = 65536
join_buffer_size                        = 256K
read_buffer_size                        = 1M
read_rnd_buffer_size                    = 2M
sort_buffer_size                        = 2M

ソースコード(私はこの辺さわってないです)

  • 香ばしい感じのSQLを直す
    • 1回のアクセスで2000回とか叩かれるクエリがあったりで地道に直す
    • 恐らく全ては潰せてない
  • initializeでIndex追加

結果

  • 最終スコアは11000ほどでFinish
    • 正式な記録は残してなかったです…
    • 途中で3位になったが最終的には20位前後でした。
  • 予選突破ボーダーラインが13898だったのでまぁ戦うことはできてたのかなという印象

感想

  • 楽しかった。去年よりは戦えていたと自負している。
  • よく考えると凄く王道なことしかしていない
    • 初期実装の問題により焦ってしまい、途中一度立ち止まって話し合う時間を持たなかったことが大きな敗因かと思う
  • 実は PHPカンファレンス2015 - #phpcon2015 でISUCON5の話をLTでやるので頑張る
    • 予選突破して今回こそPHPの威厳を・・・と考えていたので悔しい
    • PHP5.6での結果スコアとか比較できるように今週は復習も兼ねて自習ISUCONが続く予定
  • 途中結果のGit Commitはあるが、スコアを記録してなかったのでそれはまずかった
  • ただ去年は今回やった内容レベルでも恐らく予選突破できていたなと感じる。レベルが上がっている凄い。
    • ISUCON4問題での練習時にアプリケーション構造変えずに、インフラ面onlyで予選突破ラインを軽く超えられていた。
  • 運営の皆さんは本当に大変だなと思う。社内勉強会とかもちょくちょく企画・運営しているがその比ではない。
    • 本当にありがとうございました!!!!!