やる気のないランキング・履歴実装 - プログラミング美徳の不幸

ユーザがいて、記事があって、ユーザが記事にアクセスするとカウントされる。で、履歴が残ってその履歴データをもとにランキングを集計するみたいなやつ。

最終的にはリアルタイムにユーザの記事アクセス履歴が表示できるようにするのと、多少遅い~１時間おきに集計するみたいな感じで人気の記事を表示するみたいなことがやりたいとき。

こういうのっていろんな実装方針があると思うのですが、だいたいウェブ上にあがってるノウハウってfluentdでログを集計とかアクセスをNoSQL的なのに突っ込んで処理とか、

ma3tk.hateblo.jp

Google for Work Japan 公式ブログ: Cloud Datastore を用い、大規模ゲームでのランキング処理を 1 時間から 5 秒に短縮　

ソシャゲだったり大規模サイトだったりが多くて、正直デイリーで10万PVくらいまでだったらこういう頑張った実装じゃなくてMySQLでなんとかなるんじゃないかなーと思ってやってみた。

テストデータを作る

一応本番っぽいデータで耐えられるか気になったので、テストデータを作ってみた。

スキーマはこんな感じ。

mysql> describe articles;
+-------+------------------+------+-----+---------+----------------+
| Field | Type             | Null | Key | Default | Extra          |
+-------+------------------+------+-----+---------+----------------+
| id    | int(11) unsigned | NO   | PRI | NULL    | auto_increment |
| title | varchar(255)     | NO   |     |         |                |
+-------+------------------+------+-----+---------+----------------+
2 rows in set (0.01 sec)

mysql> describe users;
+-------+------------------+------+-----+---------+----------------+
| Field | Type             | Null | Key | Default | Extra          |
+-------+------------------+------+-----+---------+----------------+
| id    | int(11) unsigned | NO   | PRI | NULL    | auto_increment |
| name  | varchar(255)     | NO   |     |         |                |
+-------+------------------+------+-----+---------+----------------+
2 rows in set (0.01 sec)

mysql> describe access_logs;
+------------+------------------+------+-----+---------+----------------+
| Field      | Type             | Null | Key | Default | Extra          |
+------------+------------------+------+-----+---------+----------------+
| id         | int(11) unsigned | NO   | PRI | NULL    | auto_increment |
| article_id | int(11)          | NO   |     | NULL    |                |
| user_id    | int(11)          | YES  |     | NULL    |                |
+------------+------------------+------+-----+---------+----------------+
3 rows in set (0.01 sec)

mysql> show index from access_logs;
+-------------+------------+------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table       | Non_unique | Key_name         | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------------+------------+------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| access_logs |          0 | PRIMARY          |            1 | id          | A         |           0 |     NULL | NULL   |      | BTREE      |         |               |
| access_logs |          1 | article_id_index |            1 | article_id  | A         |           0 |     NULL | NULL   |      | BTREE      |         |               |
| access_logs |          1 | user_id_index    |            1 | user_id     | A         |           0 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------------+------------+------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
3 rows in set (0.00 sec)

で、今回はaccess_logs.user_idが一般的には非ログインユーザだとNULLを許容するんじゃないかなと思ってNULL可にしてます。が、それだと同一ユーザのアクセスをユニークカウントしたいときにuser_idがないアクセスをどうカウントするのかという別の問題が生じることに注意します。

で次にテストデータの投入

CREATE TABLE digit(num integer);
INSERT INTO digit VALUES
(0),
(1),
(2),
(3),
(4),
(5),
(6),
(7),
(8),
(9);

INSERT INTO articles(title)
    SELECT CONCAT("title", d1.num + d2.num * 10 + d3.num * 100 + d4.num * 1000 + d5.num * 10000)
    FROM digit d1, digit d2, digit d3, digit d4, digit d5;

INSERT INTO users(name)
    SELECT CONCAT("name", d1.num + d2.num * 10 + d3.num * 100 + d4.num * 1000 + d5.num * 10000)
    FROM digit d1, digit d2, digit d3, digit d4, digit d5;

INSERT INTO access_logs(user_id, article_id)
    SELECT CEIL(RAND() * 10000), CEIL(RAND() * 10000)
    FROM digit d1, digit d2, digit d3, digit d4, digit d5, digit d6;

参考

qiita.com

でユーザ10万行, 記事10万行, アクセスログ100万行できあがり。

クエリについて

このテーブルから履歴とランキングを作成する。たぶんソシャゲとか大規模サイトだとそもそも単一のテーブルで２つの算出を行う時点でどちらかが犠牲になるとかがあると思うけど。

まず何も考えないで両方SQLにすると

履歴(user id=1の人)

-- idが大きい方が作成日が新しいことが保証されているとする

SELECT * FROM articles
    INNER JOIN access_logs as logs ON articles.id = logs.article_id
    WHERE logs.user_id = 1
    GROUP BY articles.id
        HAVING MAX(logs.id) 
        ORDER BY MAX(logs.id) DESC
    LIMIT 10;

となる。上が7sくらい、下が0.6msくらいだったので履歴のほうはそのまま使えるし、上のほうもまぁそのまま使うのはまずいけどキャッシュするとかすればいける。ちなみにさっきユーザごとに重複が~と言ったけど、重複を許可しないのはわりときつい。なぜならこのやり方だとさすがに日付でグルーピングするところまでをさくっとはいけないし、バッチで日ごとに集計データとか作らないと無理だと思う。

次に仮に日付なしでかつてアクセスされたかどうかだけでやろうとすると

SELECT *, COUNT(logs.user_id) as unique_access FROM articles
    INNER JOIN access_logs as logs ON articles.id = logs.article_id
    GROUP BY articles.id
    ORDER BY unique_access DESC
    LIMIT 10;

みたいになると思うんですが、ユーザが多いとこのクエリはかなり重くなる。まぁ手元で45秒くらいかかった。

改善する

人気のほうのクエリはいろいろ実験して改善点があることに気づきました。まず単純にaccess_logsをarticle_idでグルーピングして、グループに所属するレコードの数の順番に並び替えるクエリを試してみました。

SELECT *, COUNT(logs.id) as log_count from access_logs as logs
    GROUP BY article_id
    ORDER BY log_count DESC;

これは1.2sくらいで終わりました。ということは、少なくとも人気順のarticle_idを取得するだけならわりとなんとかなるので、1クエリで6秒かかっていたのを分割して早くできる。

article_ids = AccessLog.find_by_sql(<<-SQL
SELECT *, COUNT(logs.id) as log_count from access_logs as logs
  GROUP BY article_id
  ORDER BY log_count DESC
        LIMIT 100;
SQL
).map(&:article_id)
sanitized_id_string = article_ids.map { |id| connection.quote(id) }.join(',')
Article.where(id: article_ids).order("FIELD(id, #{sanitized_id_string})")

妥協に妥協を重ねる

データベースの本をちゃんと読むとO(log(n))の計算量がどうとか書いてあるんですが、まぁそういうことを言わずにやればわかるんですがこの人気ランキングクエリはaccess_logsの行数に比例して重くなってる。

で、今100万行あって1.2sなので、10倍早くしたければ10万行くらいに絞ればいい。このあたりは何行あればある程度信頼性のおけるものになるのか、サービスによって違うのでサービス開発エンジニアのセンスのいい妥協ポイントが問われてくると思います。

今回は記事が10万件あるけど、たいていのメディアって5000件もないくらいなんでそれなら(勘だけど)3万件くらいでそれっぽくなると思う。

これはidから動的にクエリを組み立てて実装するか、自分のサイトがだいたいどのくらいで３万アクセスくるのか考えればいいと思う(一日3万アクセスくるならデイリーランキングですね。)

Railsだと

これはおまけですがActiveRecordの場合のメソッドです。

class Article
  def self.popular
    article_ids = AccessLog.find_by_sql(<<-SQL
SELECT article_id, COUNT(logs.id) AS log_count FROM access_logs AS logs
  GROUP BY article_id
  ORDER BY log_count DESC
  LIMIT 100;
SQL
).map(&:article_id)
    sanitized_id_string = article_ids.map { |id| connection.quote(id) }.join(',')
    where(id: article_ids).order("FIELD(id, #{sanitized_id_string})")
  end

  def self.recent_viewed_by(user)
      joins("INNER JOIN access_logs AS logs ON logs.article_id = articles.id").
        where("logs.user_id = ?", user.id).
        group("articles.id").
        having("MAX(logs.id)").
        order("MAX(logs.id) DESC")
  end
end

ちなみに文字列でクエリ書いてるのはこのテーブルに強く依存したくない(いずれ耐え切れなくなったところで捨てる実装なので)なので、belongs_toとかを貼りたくないだけです。関連貼ったらjoins(:logs).merge(AccessLog.where('created_at > ?', 1.days.ago))とかでいけますね。

その他のやる気のない実装

PVランキングはウェブだけのサービスならGoogleAnalyticsからAPIでデータを取得するってのがオススメです。一回疎通させればデイリー、ウィークリー、通年とか作り放題だし。