Kazuho@Cybozu Labs

　プッシュ型のフレンド・タイムラインにおいては、各ユーザが、自分が読むべきメッセージの一覧を保持します。SQL のスキーマは以下のようになります。

-- フォロワー関係を保持するテーブル
CREATE TABLE `follower` (
  `user_id` int(10) unsigned NOT NULL,            -- follow する user id
  `follower_id` int(10) unsigned NOT NULL,        -- follow される user id
  PRIMARY KEY (`user_id`,`follower_id`),
  KEY `follower_id` (`follower_id`)
);

-- メッセージを保持するテーブル
CREATE TABLE `message` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,  -- メッセージID
  `user_id` int(10) unsigned NOT NULL,            -- メッセージの送信者
  `body` varchar(255) NOT NULL,                   -- メッセージ本体
  PRIMARY KEY (`id`),
  KEY `user_id_id` (`user_id`,`id`)
);

-- ユーザ毎の読むべきメッセージ一覧を保持するテーブル
CREATE TABLE `mailbox` (
  `user_id` int(10) unsigned NOT NULL,            -- 受信者の user id
  `message_id` int(10) unsigned NOT NULL,         -- メッセージの id
  PRIMARY KEY (`user_id`,`message_id`)
);

　メッセージの登録処理は以下のようになります。

INSERT INTO message (user_id,body) VALUES ($user_id,$body);
INSERT INTO mailbox (user_id,message_id)
    SELECT user_id,last_insert_id() FROM follower WHERE follower_id=$user_id;

　フレンド・タイムラインの取得処理は以下のようになります。

SELECT message.id,message.user_id,message.body FROM message
    INNER JOIN mailbox ON message.id=mailbox.message_id
    WHERE mailbox.user_id=$user_id
    ORDER BY mailbox.message_id DESC LIMIT 20;

　フレンド・タイムラインの２ページ目以降の取得処理については、LIMIT 20,20 のように書く方法と、前ページにおける最小のメッセージ ID を覚えておいて、WHERE mailbox.message_id<??? のように指定する方法の２種類があります。前者の方が単純ですが、後者の方が軽く (前者が O(n) なのに対して後者は O(log n))、また、ページ遷移の間に新しいメッセージが書き込まれた場合でも、表示内容に重複や欠落が発生しないという点で優れています。

　プッシュ型を採用するメリットは、フレンド・タイムラインの取得処理が軽い点です。一方で、メッセージの登録処理は重たくなります。また、データベースがプル型と比較して非常に大きくなります。一人のユーザーが平均 100 人をフォローしていると仮定すると、１メッセージの登録処理毎に 100 回以上の書込処理が発生することになります。具体的なチューニングとベンチマークについては、追って提示します。

2. プル型

　プル型のフレンド・タイムラインにおいては、ユーザー毎の受信メッセージリスト (mailbox テーブル) は用意しません。リクエストがあった段階で動的に一覧を生成する形になります。

　Mailbox テーブルがないため、メッセージの登録処理は単純になります。

INSERT INTO message (user_id,body) VALUES ($user_id,$body);

　一方、フレンド・タイムラインの取得処理においては、工夫が必要です。具体的には、以下のようなアルゴリズムを使うのが良いのではないかと思います。

1. フォローしている各ユーザーについて、そのメッセージ ID の最大値を取得
2. 1 のリストをメッセージ ID の降順でソートし、その先頭 20 件 (１ページ分) 以外を破棄
3. 2 のリストの各ユーザーについて、それぞれ最新 20 件のメッセージを取得し、マージ
4. 3 のリストの先頭 20 件が、クライアントに返すべきフレンド・タイムライン

　まず、このアルゴリズムにおける手順 1 の負荷ですが、インデックスをフォローしているユーザーの数だけ引くことになります。この処理を軽いと考えるか重いと考えるかは微妙 (ベンチマークは後述) ですが、システム全体としての負荷は、１ユーザーあたりの平均フォロー数に比例することになります。また、手順 3, 4 については、最大 n^2 の行にアクセスすれば良いということになります (さらに最適化を行うのであれば、最後まで繰り返さなくても、手順 2 で得られたメッセージ ID の最大値が、取得できたタイムラインの 20 件目のメッセージ ID の値を下回った時点でループを打ち切ることもできるでしょう) 。つまり、n 件 (ここでは 20) のメッセージを取得するためにアクセスする行数は、データの偏りや規模に関係なく (フォロワー数 + n²) 以下ということになります。

　残念なことに、SQL ではこの種のクエリを１ステートメントで実装することは不可能です (できるのなら誰か教えてください)。 かといって、多数のクエリを発行すればプロセス間通信のコストが増大してしまいます。MySQL においては、今のところ、ストアドプロシージャとして実装するのが、最も効率が高そうです。

CREATE PROCEDURE fetch_timeline_ids (IN uid int unsigned)
BEGIN
  DECLARE fid,maxid int unsigned;
  DECLARE done int DEFAULT 0;
  DECLARE fid_maxid_cur CURSOR FOR
    SELECT follower_id,(
      SELECT id FROM message WHERE user_id=follower.follower_id
      ORDER BY user_id DESC,id DESC LIMIT 1) AS max_id
    FROM follower WHERE user_id=uid ORDER BY max_id DESC LIMIT 20;注1
  DECLARE CONTINUE HANDLER FOR NOT FOUND SET done=1;
  CREATE TEMPORARY TABLE IF NOT EXISTS fetch_timeline_tt (
    id int unsigned NOT NULL PRIMARY KEY
  ) ENGINE=heap DEFAULT CHARSET=utf8;
  DELETE FROM fetch_timeline_tt;
  OPEN fid_maxid_cur;
  REPEAT
    FETCH fid_maxid_cur INTO fid,maxid;
    IF NOT done THEN
      INSERT INTO fetch_timeline_tt
        SELECT id FROM message WHERE user_id=fid
        ORDER BY id DESC LIMIT 20;
    END IF;
  UNTIL done END REPEAT;
  CLOSE fid_maxid_cur;
END;

　このストアドプロシージャを使って、フレンド・タイムラインの取得コードは以下のように書くことができます。

CALL fetch_timeline_ids($uid);
SELECT message.id,user_id,body FROM message
  INNER JOIN fetch_timeline_tt USING(id)
  ORDER BY message.id DESC LIMIT 20;

　このコードが実際どの程度の速度で動作するのかは、後述します。ただ、プル型における最新のフレンド・タイムライン取得処理は memcached を使って最適化すればよいことなので、あまり問題にならないかもしれません。むしろ、２ページ目以降の取得処理の負荷をどう考えるか、というのが実際的な課題になるでしょう。

2.1. プル型におけるページ処理

　プッシュ型と異なり、プル型においては LIMIT 句を利用したページ処理はできません。ページ処理は、必ず、前ページの最小メッセージ ID を基準に、より小さいメッセージ ID を探していく、という形式になります。本来であれば、前述のプロシージャ fetch_timeline_ids の SELECT 文に条件を追加すれば済む話なのですが、MySQL のオプティマイザは上手に最適化してくれません。そこで、さらにクエリをストアドプロシージャに展開する必要が出てきます。

CREATE PROCEDURE build_max_ids_of_followers (IN uid int unsigned,IN max_id int unsigned)
BEGIN
  DECLARE fid int unsigned;
  DECLARE done int DEFAULT 0;
  DECLARE fcur CURSOR FOR
    SELECT follower_id FROM follower WHERE user_id=uid;
  DECLARE CONTINUE HANDLER FOR NOT FOUND SET done=1;
  CREATE TEMPORARY TABLE IF NOT EXISTS max_ids_of_followers (
    user_id int unsigned NOT NULL,
    max_id int unsigned NOT NULL
  ) ENGINE=heap DEFAULT CHARSET=utf8;
  DELETE FROM max_ids_of_followers;
  OPEN fcur;
  REPEAT
    FETCH fcur INTO fid;
    IF NOT done THEN
      INSERT INTO max_ids_of_followers SELECT fid,max(id) AS m FROM message
        WHERE user_id=fid AND id<=max_id HAVING NOT ISNULL(m);
    END IF;
  UNTIL done END REPEAT;
  CLOSE fcur;
END;

CREATE PROCEDURE fetch_timeline_ids2 (IN uid int unsigned,IN maxid int unsigned)
BEGIN
  DECLARE fid,fmaxid int unsigned;
  DECLARE done int DEFAULT 0;
  DECLARE fid_maxid_cur CURSOR FOR
    SELECT user_id,max_id FROM max_ids_of_followers
    ORDER BY max_id DESC LIMIT 20;
  DECLARE CONTINUE HANDLER FOR NOT FOUND SET done=1;
  CREATE TEMPORARY TABLE IF NOT EXISTS fetch_timeline_tt (
    id int unsigned NOT NULL PRIMARY KEY
  ) ENGINE=heap DEFAULT CHARSET=utf8;
  DELETE FROM fetch_timeline_tt;
  CALL build_max_ids_of_followers(uid,maxid);
  OPEN fid_maxid_cur;
  REPEAT
    FETCH fid_maxid_cur INTO fid,fmaxid;
    IF NOT done THEN
      INSERT INTO fetch_timeline_tt
        SELECT id FROM message
        WHERE user_id=fid AND id<=fmaxid
        ORDER BY id DESC LIMIT 20;
    END IF;
  UNTIL done END REPEAT;
  CLOSE fid_maxid_cur;
END;

　これらのストアドプロシージャを使って、ページ処理のコードは以下のように書くことになります。

CALL fetch_timeline_ids2($uid, $max_id);
SELECT message.id,user_id,body FROM message
  INNER JOIN fetch_timeline_tt USING(id)
  ORDER BY message.id DESC LIMIT 20;

3. ベンチマークとチューニング

　では、実際のパフォーマンスはどの程度のものでしょうか。プッシュとプル、両モデルについてベンチマークを取ったところ、以下のような値が得られました。なお、測定条件は以下のとおりです。メッセージの投稿頻度やフォローの関係については、一定の傾きを設けました。

表1. 測定条件

想定ユーザ数	10,000
総メッセージ数	1,000,000
平均フォロー数	42.9
実行環境	CentOS 5.1 (i386; linux-2.6.18-8.1.15.el5xen) MySQL 5.1.24-rc (InnoDB を使用) Pentium 4 3.0GHz 2GB RAM

表2. ベンチマーク

	プッシュ	プル
データサイズ	2.0GB	130MB
登録速度 (メッセージ/秒)	560	6,700
取得速度 (タイムライン/秒)	1,300	120

　まず、データサイズの差が目を引きます。プッシュ型のデータサイズがプル型よりも 10 倍以上大きいのは、mailbox テーブルが肥大化するためです。プッシュ型を採用する場合は、HDD の容量に気をつける必要がありそうです。対策としては、InnoDB Plugin のデータベース圧縮機能を使う、あるいは、mailbox テーブルの複数行を単一の blob にまとめる、といった手が挙げられるでしょう。

　次に、登録速度ですが、プッシュ型が意外と検討しています。これは、ベンチマークにおいて、ジャーナリング機能をもつ InnoDB を使ったためだと考えられます。ジャーナル (innodb_log_file_size) が十分大きくとることで、異なる領域への書き込みがマージされるので、プッシュ型を HDD ベースでの運用することも可能と思われます。

　最後に、取得速度ですが、やはりプル型は苦戦しています。ストアドプロシージャとはいえ、多数の SQL を発行するのはパフォーマンス低下を招くためだと考えられます。プル型を使用して大規模なサービスを運用したい場合は、

1. memcached 等を使い、最新のタイムライン取得処理をオフロードする (２ページ目以降のみ MySQL にアクセスするのであれば、120 リクエスト/秒・CPU は十分な数値でしょう)
2. MySQL より優れたオプティマイザをもつ RDBMS を検討する
3. あるいは専用のデータベースを開発する

といった対策が必要になるでしょう。

　

4. 最後に

　プッシュ型、プル型ともにスケーラビリティに差はありません。どちらも、ユーザ ID を鍵とした水平分割^注2によって、スケールアウトすることができます。

　となると、結論としては、プッシュ型／プル型ともに、一長一短がある、というあたりに落ち着きそうです。少なくとも、プッシュ型が HDD／メモリインテンシヴであるのに対し、プル型が CPU インテンシヴというのは確かなようですが、両者の間に決定的な差があるわけではなさそうです^注3。むしろ、実際に運用してみないと分からないことかもしれません。もしどなたか、実際にお試しになることがありましたら、結果を教えていただければ幸いです。

　なお、本記事は、昨夜からデータ生成＆コーディング＆実装を行いつつ作成したものですので、まだ誤り等が含まれていたり、あるいは最適解ではないものが含まれていたりするかもしれません。何かありましたら、ご指摘いただければと思います。

　それでは、have fun!

注1: MySQL の Loose index scan 最適化は結合を扱えないので、副クエリを使用して書く必要がある
注2: ここでは、RDBMS の用法で「水平分割」(キーの値によってテーブルを水平方向に分割する) を使用しています
注3: 個人的には MySQL の限界により、プル型の可能性を引き出せなかったのが残念です

6月10日追記:

　上記ベンチマークで使用した InnoDB の設定は以下のとおりです。

innodb_buffer_pool_size=768M
innodb_log_file_size=64M
innodb_flush_log_at_trx_commit=0
innodb_file_per_table
innodb_flush_method=O_DIRECT

また、テストに使ったスクリプトをアップロードしましたので、ご覧ください。

• setup_followers.pl - follower テーブルの充填スクリプト
• add_messages.pl - メッセージの登録ベンチマーク
• pull_timeline.pl - タイムラインの取得ベンチマーク

ども、久しぶりです。

興味深く読ませていただきました。
お恥ずかしいのですが、一点、プッシュ型に対して、プル型の実装が1-4になることを詳しく解説願えますでしょうか。

なんで疑問に思ったかというと、プル型をざっくり実装するなら

SELECT *
FROM message
INNER JOIN follower USING (message.user_id = follower.follower_id)
WHERE follower.user_id = xxx
ORDER BY message.id DESC LIMIT 10;

のような感じになるかなと自分は思っていた次第でありまして。
これだと、followする前のメッセージも見えちゃう/見えちゃわないとかの違いがありますが、まぁ大筋は変わらないような気もする（サービスデザインとのトレードオフ？）

どっちにせよ、追記のみのショートメッセージの配信に特化したストレージエンジンは受けそうというか需要ありますよね。RSSリーダー、SNS、Twitter、みんなこの形ですし。

ご無沙汰しております。

えっと、shn さんのクエリは結果は正しいのですが、速くないというか、メッセージ量やユーザ数が増えた場合にスケールしないのです (どちらかに対して O(n) になる)。オプティマイザで LIMIT の行数を見て記事内のような最適化をかけてくれればいいのですが、RDBMS レベルではちょっと難しいかも、と思います。

なるほど、理解しました。
インデックス周りは「同時に1インデックス」とか気をつけてれば、MySQLがよろしく最適化してくれんのかなーとうすらぼんやり考えていました。
参考になりました！

各ユーザのfollowers Listがupdateされる頻度が高く、フレンド・タイムライン処理がそれに動的対応しなければいけないとするとプッシュ型は不利なような気がします。如何でしょうか？問題ない程度なのしょうか？

Tocotonist さん、プッシュ型で動的対応するといっても、例えば InnoDB の場合だと、変更をいったんログファイルに書いておいて、定期的にまとめてデータベース本体に適用するようになっている (いわゆるジャーナリング) ので、I/O の書き込み負荷は、それほど大きくないようです (上のベンチマークのとおりです) 。

むしろ、データサイズ肥大化により、HDD からの読み込み負荷が上がってくる方が問題になりそうな気がします。

実際のアプリケーションの場合には mailbox と message を JOIN しないで、mailbox からは id のみを取得して message は id をキーにして memcached で get_multi すると、クエリの実行速度は上がると思うのですが、その場合のパフォーマンスはどうなるのでしょうか。というところが気になりました。

あともう一つ。twitter の場合には protected という概念が存在しますので、これもパフォーマンスを左右する要因になるのではないかとおもいます。

> mailbox と message を JOIN しないで、mailbox からは id のみを取得して message は id をキーにして memcached で get_multi すると、クエリの実行速度は上がると思う

memcached の cache hit 率がどの程度確保できるかによると思います。ただ、id を取得するために必ず MySQL にクエリを投げるという前提であれば、memcached を使ったところで、あまりパフォーマンスは上がらないかもしれないと思いました。

> twitter の場合には protected という概念が存在しますので、これもパフォーマンスを左右する要因になるのではないかとおもいます。

protect しているかの有無を follower テーブルに反映するようにしておけば問題ないと思います。