is_friend?

get_user

user_id

users

users

relations

友だちの日記エントリ/コメント

is_friend?

を大量に呼び出していたのは「友だちの日記エントリ」「友だちのコメント」でした。友だちの最新の日記エントリ10件取得したいというクエリは、

relations

テーブルをJOINするか、友だちのidリストを使えば以下のように書けます。

SELECT * FROM entries
WHERE user_id IN (:friend_ids)
ORDER BY id DESC LIMIT 10

友だちの最新コメント10件はpermitted?のN+1もあるのでもうひと手間必要ですが、落ち着いて考えれば以下の条件を考慮すればいいとわかります。

private=0(公開)のエントリへのコメントは表示してオッケー

private=1(友だち限定公開)のエントリへのコメントはpermitted?がtrueなら表示してオッケー

• permitted?

  がtrueになるエントリは自分のエントリか自分の友だちのエントリ

つまり、SQLにすると以下のように書けばよかったことになります。

SELECT * FROM comments c
JOIN entries e ON c.entry_id = e.id
WHERE c.user_id IN (:friend_ids)
AND (
  e.private = 0
  OR
  e.private = 1 AND (e.user_id = :my_user_id OR e.user_id IN (:friend_ids))
)
ORDER BY c.id DESC LIMIT 10

あとは

entries/comments

を取得する条件が変わったので必要なINDEX(

user_id

)を追加して、要らなくなったINDEX(

created_at

)は効率のために落としておくとよいでしょう。

ALTER TABLE comments ADD INDEX user_id (user_id), DROP INDEX created_at;
ALTER TABLE entries DROP INDEX created_at;

足あと

足あとは、同じ日に同じユーザーが付けた足あとは最新のものだけ残るように更新すれば表示するときのGROUP BYを無くすことができます。つまり、同じ日に同じユーザーが足あとを付けるときはINSERTの代わりにUPDATEする、いわゆるUPSERTをしたいわけですがMySQLの場合REPLACE文を使うと簡単に実現できます。

REPLACE INTO footprints (user_id,owner_id,date) VALUES (?,?,NOW())

REPLACE文で既存のレコードと衝突したときに更新させるには(

user_id,owner_id,date

)へのUNIQUE制約が必要なので、以下のようにして追加しておくとよいでしょう。

CREATE TABLE fp LIKE footprints;
ALTER TABLE fp ADD COLUMN date date NOT NULL, ADD UNIQUE INDEX unique_per_day (user_id,owner_id,date), ADD INDEX user_id (user_id);
REPLACE INTO fp SELECT id, user_id, owner_id, created_at, DATE(created_at) FROM footprints WHERE id <= 500000;
RENAME TABLE footprints TO footprints_old, fp TO footprints;

日記エントリの本文

「/」ページでは日記エントリのタイトルしか使わないのに、タイトルと本文が同じカラムに保存されているのでサイズの大きな本文を毎回取得しているのが無駄でした。これは以下のようにしてタイトルだけ取得するようにすると無駄に大きなデータをやり取りせずに済みます。

SELECT id, SUBSTRING_INDEX(body, '\n', 1) AS title FROM entries WHERE user_id = ? ORDER BY created_at LIMIT 5

もしくは、タイトルだけ別カラムや別テーブルに分けて保存するようにすると取得が楽になります。

[別解]友だちの日記エントリ/コメント

今回の予選問題ISUxiではここまでできれば十分に高速化することができました。しかし、もっと大きなデータセットを持つ現実のSNSでは「友だちの日記エントリ/コメント」の処理はこのままでは実用に耐えません。

SELECT * FROM entries WHERE user_id IN (:friend_ids) ORDER BY id DESC LIMIT 10

ユーザーひとりあたり100人前後の友だちがいてユーザーひとりあたり約100件のエントリをもつISUxiでは、友だちの最新エントリ10件を取得する上記クエリは以下のように動作します。

すべてのエントリの中から友だち(約100人)のエントリ(ひとりあたり約100件)をまず抽出する(合計約10000件)

並び順が不定なので投稿順に並び替える

最新エントリ10件を返す

これは、友だちがたくさんいるユーザーやエントリをたくさん投稿している友だちを持つユーザーは効率よくデータを抽出できなくなるということです。この手の友だちの最新のアクティビティ一覧、いわゆるフレンドタイムライン処理をどう実装するべきかという問題はSNS黎明期から考えられていて、より参照効率に特化したアプローチが知られています。それは、参照時に友だちの表示していいエントリを判別してかき集めてくるのではなく、エントリ投稿時にそのエントリを表示していい投稿者の友だちの最新エントリ一覧にエントリを配信するというアプローチです。このアプローチは前出のアプローチに対してpush型とかinbox方式とか言われています。

CREATE TABLE `entries_of_friends` (
  `user_id` int NOT NULL,
  `entry_id` int NOT NULL,
  PRIMARY KEY (`user_id`,`entry_id`)
) ENGINE=InnoDB CHARSET=utf8mb4;

後者のアプローチでinboxテーブルに配信されたエントリは、友だちの数や友だちが投稿したエントリの数にかかわらず以下のクエリで最新のエントリだけを取り出すことができます。

SELECT entry_id FROM entries_of_friends WHERE user_id = ? ORDER BY entry_id DESC LIMIT 10

参考リンク

フレンド・タイムライン処理の原理と実践

本当は難しいフレンド・タイムライン処理

Tumblr Architecture - 15 Billion Page Views A Month And Harder To Scale Than Twitter

参考回答(Perl)

参考回答[別解](Perl)

まとめ

本エントリでは予選の講評としてISUxiのボトルネックについて解説しました。かの首謀者であるモリスさん曰く「ISUCON参加前と参加後に最も多くのものを持ち帰った人こそが勝者」だと言っていました。本予選参加者が多くのものを持ち帰れたと思える出題であれば幸いです。