2010-07-03

OpenSocial Pages のタイムラインは AppEngine for Java の Data Store でどのように実現しているか

こんにちは。Nobuhiro Nakajima です。

OpenSocial Pages for Google Apps は OpenSocial Activities API という Twitter でいうところのタイムライン API を備えています。また Activities は Twitter でいうところの Friends (Following)、Lists、Mentions という人と人の関係(ソーシャルグラフ)で絞り込めるようになっています。


OpenSocial Pages は Google AppEngine for Java でホストしています。そして Activity の格納と検索は Data Store (JDO) で実現していて、エンティティの主な構造は、次のようにしています。

エンティティの構造

Twitter でいうところの User を表すエンティティです。この User が、誰に Follow されているか、どのグループに属するかを保持させています。
public class User {
  private String id;
  private Set<String> followerIds; // 誰に Follow されているか
  private Set<String> groupIds; // どのグループに属するか
}
Twitter でいうところの Lists を表すエンティティです。
public class Group {
  private String id;
}
Twitter でいうところの Status を表すエンティティです。この Activity が誰のもので、誰が関係するのか保持させています。followerIds と groupIds は Person のコピーを保持させています。mentionIds は Twitter でいうところの、テキスト中の @username で引用された User たちを保持させています。
public class Activity {
  private Long id;
  private String userId; // Person#id
  private String title; // テキスト
  private Set<String> followerIds; // Person#followerIds のコピー
  private Set<String> groupIds; // Person#groupIds のコピー
  private Set<String> mentionIds; // テキスト中の @username たち
}
Follow と Unfollow

User A が User B を Follow するとき、User B の followerIds に User A の userId を追加します。また Unfollow するときは、User B の followerIds から User A を除外します。

Group の参加と退会

User が Group に参加するときは、User の groupIds に自身の userId を追加します。また、退会するときは、User の groupIds から 自身の userId を除外します。

Activity の送信

送信する User の followerIds と groupIds を Activity の followerIds と groupIds にコピーして格納します。さらに、テキスト中の @username に該当する User の userId を mentionIds に格納します。

検索クエリ

User の Activity を検索するときは、Activity エンティティに対して、次のフィルタを使っています。
Query#setFilter("userId == :userId");
User が Follow している Friends の Activity を検索するときは、次のフィルタを使っています。このときの userId は、自分自身の ID を指定します。
Query#setFilter("followerIds == :userId");
Group に所属している User たちの Activity を検索するときは、次のフィルタを使っています。
Query#setFilter("groupIds == :groupId");
User が関係する Activity を検索するときは、次のフィルタを使っています。
Query#setFilter("mentionIds == :mentionId");

Activity の再構築

User A が User B を Follow したとき、User B の 全 Activity (*1) の followerIds に User A の userId を追加します。また Unfollow したときは、followerIds から除外します。

User が Group に参加するときは、User A の 全 Activity (*1) の groupIds に Group の groupId を追加します。また、退会したときは、groupIds から除外します。

前者と後者とも Task Queue を使って Activity を更新しています。

利点と欠点、そして課題

まず、基本方針は、シンプルなデータ構造とすること、そして、参照のコストを均一化するの(と削除)を最優先にしました。

この方法は、どんなに User が増えて、どんなに Follow したり、Group に参加したりしても、検索クエリのコストは一定なのが利点です。ただし、Follow/UnFollow、Groupの参加/不参加が発生したとき、過去にさかのぼって Activity を再構築する必要があるのが、大きな欠点です。

Activity がいくら蓄積されようとも、Activity 自体のコピーは保持していないため、Activity の削除は用意というのも利点です。ただ、User 自体を削除したとき、その User の 全 Activity を削除する必要がありますが、現状は削除せず、残したままとしています。

*1 Activity はどんどん蓄積されるものなので、時間が経過するにしたがって、全 Activity を更新するのは、現実的に難しくなってきます。そこで OpenSocial Pages では、新しいものの内 n 件分、もしくは n 日分の Activity のみ再構築の対象にするように妥協しています。古い Activity は重要度が低いよねという考え方です。

できれば、古い Activity もすべて再構築したいというのが課題です。古い Activity は即時で再構築することは絶対条件ではないため、バッチ的なものや、無駄な再構築が起こらないようにスケジューリングするとかいった方法でもよさそうです。

何かよいアイディアはないものでしょうか? エンティティグループとか、エンティティのエンティティとかうまく使えば、別の方法があるのかもしれないです。

1 件のコメント:

Nobuhiro Nakajima さんのコメント...

大量のエンティティを処理するデザインパターン
http://d.hatena.ne.jp/int128/20100703/1278161548