« フレンド・タイムライン処理の原理と実践 | メイン | MySQL の ORDER BY を高速化 »

2008年06月12日

MySQL (InnoDB) に直接アクセスしてタイムライン処理を高速化する話

 フレンド・タイムライン処理の原理と実践 の続きです。

 先のエントリでは、プルモデルの速度が当初予測していたよりも遅かった (というより SQL レイヤでのオーバーヘッドが大きそうだった) ので、MySQL Internals メーリングリストで質問したりしながら、C++ で直接 InnoDB にアクセスするようなコードを書いてみました。

タイムライン構築速度
タイムライン/秒
SQL56.7
ストアドプロシージャ136
C++ での直接アクセス1,7102,000 (追記参照)

 そしたら、10倍以上高速に! ベンチマークを perl ベースのものから mysqlslap に変えたのですが、プッシュモデルの 2/3 の速度が出ています。これなら、データサイズが約 1/10 になることを考えると、メモリの代わりに CPU に投資するほうが良い、という判断も非常に現実味を帯びてきます。また、最近のクアッドコアな CPU を使えば 10,000 タイムライン/秒クラスも夢じゃないでしょうから、memcached による支援の必要もないのかもしれません。

 ちなみに、コードは /lang/sql/mysql_timeline - CodeRepos::Share - Trac に置いてあります。C++ で約120行 (+同程度のラッパライブラリ) なので、簡単に理解できると思います。実際のアクセスパターンをコードに直接書けばいいので、むしろ SQL をチューニングするより簡単かもしれません。コアのコードはこんな感じ。

int4store(follower_keybuff, user_id);
if (follower_tbl->file->index_read_map(follower_tbl->record[0],
                                       follower_keybuff, 1, HA_READ_PREFIX)
    == 0) {
  do {
    unsigned follower_id = follower_follower_id_fld->val_int();
    int4store(message_keybuff, follower_id);
    if (message_tbl->file->index_read_map(message_tbl->record[0],
                                          message_keybuff, 1,
					  HA_READ_PREFIX_LAST)
	== 0) {
      do {
        if (! test_add_id(message_id_fld->val_int())) {
	  break;
	}
      } while (message_tbl->file->index_prev(message_tbl->record[0]) == 0
	       && message_user_id_fld->val_int() == follower_id);
    }
  } while (follower_tbl->file->index_next(follower_tbl->record[0]) == 0
	   && follower_user_id_fld->val_int() == user_id);
}

 使い方はこんな感じ。ユーザID 123 のタイムラインが表示されます。

% g++ -I ~/dev/mysql/51/32-src/include -I ~/dev/mysql/51/32-src/sql -I ~/dev/mysql/51/32-src/regex -g -Wall -O1 -fno-rtti -fno-exceptions  -shared -o timeline.so timeline.cc
(snip)
% cp timeline.so ~/dev/mysql/51/32-bin/lib/plugin
% mysql -u root -p test
mysql> CREATE FUNCTION timeline returns int soname 'timeline.so';
Query OK, 0 rows affected (0.00 sec)

mysql> CREATE TEMPORARY TABLE fetch_timeline_tt (id int unsigned NOT NULL) ENGINE=heap;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT timeline(123);

mysql> SELECT message.* FROM message INNER JOIN fetch_timeline_tt USING (id);

 実装はしていませんが、過去の任意の時間のタイムラインを抽出する機能をつけることも簡単でしょう (message->index_read_map の呼出条件を変えるだけ)。

 なんだかんだ言って、MySQL の API の奇麗さと InnoDB のチューニングのすばらしさを見せつけられた感じです。中途半端に自前のストレージを書くより、大樹によりかかるほうが楽だなと痛感しました。複雑な条件での検索を実行したいけど SQL では上手に書けない、というケースでは、この手法は結構現実的な選択肢になるのかもしれません。

6月13日追記: rev. 13812 でページング処理に対応しました。SELECT timeline(user_id,max_message_id); のように書くことで、メッセージ ID が max_message_id 未満のタイムラインを取り出すことができます。処理速度は最新タイムライン取得と同等かなと思っていたのですが、1,300 タイムライン/秒程度と、やや劣化しました。インデックスサーチの条件が先頭4バイトから8バイトになったためかな、と思います。

 また、ユーザー毎の最新のメッセージIDをキャッシュできるようにしました (内部でユーザIDを鍵とする配列を準備し、そこにメッセージIDの最大値を格納)。コンパイル時に -DCACHE_MAX_MESSAGE_IDS=1 とすることで有効になります。ただ、この場合は、InnoDB 内の状態と timeline UDF 内のキャッシュ情報を同期させる必要があるので、必要に応じて timeline_set_maxid() 関数 (これも UDF として実装してあります) を呼び出すようにしてください。

-- MySQL 起動時に最新メッセージIDをキャッシュ
SELECT timeline_set_maxid(user_id,max(id)) FROM message GROUP BY user_id;

-- INSERT, UPDATE, DELETE にトリガーを設定 (手動で SQL 発行してもいいですが)
CREATE TRIGGER timeline_update_maxid_after_insert AFTER INSERT ON MESSAGE
FOR EACH ROW BEGIN
  SELECT timeline_set_maxid(
    NEW.user_id,
    (SELECT max(id) FROM message WHERE user_id=NEW.user_id)
  ) INTO @unused;
END;
(以下略)

 ただ、ここまでしても最新タイムラインの取得速度は 1,710 タイムライン/秒から 2,000 タイムライン/秒程度までしか向上しませんでした。結局、いったんテンポラリテーブルに結果のメッセージIDを格納してから、それを別の SQL クエリで結合して取り出しているのがオーバーヘッドになっていると考えられます。この点を最適化しようと思うと、MySQL 本体に手を加える必要があるので、ちょっと今すぐには、やる気にはなりません。需要はなくはないと思うので、誰かやってみませんか?

投稿者 kazuho : 2008年06月12日 17:12 このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク

トラックバック

このエントリーのトラックバックURL:
http://labs.cybozu.co.jp/cgi-bin/mt-admin/mt-tbp.cgi/1933

コメント

すばらしい!
C++で書くのは考えた事がなかったです。

投稿者 masuidrive : 2008年06月13日 05:51