etsy-activity-feeds-architecture.md

Etsy Activity Feeds Architecture

http://www.slideshare.net/danmckinley/etsy-activity-feeds-architecture

• データモデル
  • 基礎となるエンティティ
    • アクティビティ
      • サイト上で行われた行動またはその対象となるエンティティのログ
    • コネクション
      • エンティティ間の関係
  • コネクションのデータモデル
    • Circle、Favoriteなどサイト上のエンティティ間の関係のスーパーセット
    • コネクションは有向グラフとして実装されている
      • 今のところ人物またはショップをノードとすることができる（原理的にはどのようなオブジェクトでもよい）
    • グラフのエッジは2つのテーブルに格納される
      • どのノードも、outgoingエッジ用の connection_edges_forward リストと、incomingエッジ用の connection_edges_reverse リストにエントリがある
      • 各エッジを2度保存していることになる
    • 各エッジには親しさを表す重みを付けている
    • ユーザーHの場合
      • connection_edges_forward
        • | from | to | affinity |
        • | H | E | 0.3 |
        • | H | G | 0.7 |
      • connection_edges_reverse
        • | from | to | affinity |
        • | J | H | 0.75 |
      • Hのサークルにいる人物は forward connections で見つけられる
      • Hをフォローしている人は reverse connections で見つけられる
  • アクティビティのデータモデル
    • activity := (subject, verb, object)
      • subject（誰が行ったか）, verb（何を行ったか）, object（何に対して行ったか）
      • (Steve, connected, Kyle), (Kyle, favorited, brief jerky)
      • アクティビティに直接関係ないけど興味を持つ人すべてにどのように通知するのか、という問題
        • まずデータをすべての場所にコピーする
    • activity := [owner, (subject, verb, object)]
      • S, V, Oの組み合わせを、異なるオーナーたちに対して複製して持たせる
        • Steve も Kyle もそれぞれ自分のためのレコードを持つ
      • (Kyle, favorited, brief jerky)
        • [Kyle, (Kyle, favorited, brief jerky)] -> Kyle's shard
        • [MixedSpecies, (Kyle, favorited, brief jerky)] -> MixedSpecies shard
        • [brief jerky, (Kyle, favorited, brief jerky)] -> MixedSpecies shard
        • アクティビティに興味を持っている人たちのために、アクティビティはすべての場所に複製する
  • フィードの構築
    • 最終出力を得るには、集約と表示という2つの段階がある
    • 集約 (Aggregation)
      • データベース内のアクティビティをMemcache内のニュースフィードに変換する
      • 定型的にはGearmanによってオフラインで行われる
    • 集約のステップ
      • ステップ1 - コネクションの選択
        • ユーザーが接続している人のリストを、実際にアクティビティを検索する人のリストに変換する
        • コネクションの親和性でランク付けすることで行う
          • $choose_connection = mt_rand() < $affinity;
        • より近いコネクションを選択する
        • 実際には親和性はまだ扱っていない
        • 現時点では大部分の人は充分はコネクションを持っていない（平均値が大部分を占める）
      • ステップ2 - アクティビティセットの作成
        • コネクションに対して時系列のアクティビティを抽出し、アクティビティセットと呼ぶメモリ内の構造に変換する
        • アクティビティセットは、実際にはコネクションによってグループ化され、それぞれがスコアとフラグフィールドを持ったアクティビティである
      • ステップ3 - 分類
        • すべてのセットのすべてのアクティビティについて繰り返しを行い、分類をする
        • フラグはフィードオーナーからの視点でのビットフィールド (about_owner_shop | user_created_treasury)
        • 異なる人の同じアクティビティは、異なるフラグがアサインされる
      • ステップ4 - スコアリング
        • スコアフィールドに値を設定する
        • この時点ではスコアは、シンプルな時間減衰関数である（古いアクティビティは常に新しいアクティビティより小さいスコアになる）
      • ステップ5 - 刈り込み
        • 同じイベントに対する2つ以上のアクティビティは巻き上げることができる
        • アクティビティセットを繰り返して重複を取り除く
        • SVOペアの2つ目のインスタンスを抹消できる（コメントがある場合はよりややこしくなる）
          • オーナーに対して双方向のアクティビティは見せる必要がない
      • ステップ6 - ソートとマージ
        • すべてのスコアリングと分類ができたら、すべてのスコアでソートして1つのリストにまとめる
        • 最終的なアクティビティセットができたら、オーナーの既存のニュースフィードにマージする（ない場合は新規作成する）
      • クリーンアップ
        • ニュースフィードから平均的な大きさを超えている部分を取り除く
        • 最終結果をmemcachedに格納する
      • Etsyは秒間に25回の集約が今のところのピーク
      • 集約を行う理由
        • フィードオーナーが何かを行ったりログインした場合
        • cronによるスケジュールで
        • ユーザーが何かを行った場合も、そのユーザーのコネクションに対して行う（ただしこれはスケールしない）
  • 表示
    • memcachedからニュースフィードを表示する
    • 一律表示ではなく同じようなストーリーは結合してロールアップ表示する（View 3 more items that Rob added to his favorites）
    • ストーリーを埋める
      • ロールアップ用の処理が終わったあとは表示パイプラインを実行する
        • StoryHydrator -> Story (Global details) -> StoryTeller -> Story (Feed-owner-specific details) -> Smarty -> HTML
        • キャッシングは2つのStoryの箇所で行う
          • グローバルなもの（favoriteに加えられたショップなど）
          • フィードを見る人毎にユニークなもの（like the exact way the story is phrased）
    • 速度を上げる
  • Hack
    • TTLキャッシング
    • 懸命な関係