【DB】【Twitter】Twitterにおける大規模リアルタイムデータの取り扱い方法いについて

SlideShareで見つけておもしろかったので内容をざっとまとめてみました.
3 months agoとなっているので結構最近の資料ですね

内容はtwitterでのリアルタイムデータの取り扱い方法について、初期の実装手法 + 問題 + 解決方法 + 将来の実装 + 原則といった感じの順番でそれぞれの項目についてまとめている


始めに: Real Time Dataとは?

メイン: Twitterにおける4つのリアルタイムデータの取り扱い手法について

  • 1. Tweets
  • 2. TimeLines
  • 3. Social Graphs
  • 4. Search Indices

1. Tweets

    • 140 charのメッセージ + メタデータで構成されてる
    • クエリとしてはid, authorなどが使われる(@replyもあるがここではあつかわず)
    • primary keyで単一tweets, user_idでユーザーtweetsの検索など行う
  • 初期実装手法
    • column: id, user_id, text, created_at(4 column)
    • Relational, Single table, Master-slave Replication + Memchached利用
  • 問題
    • Disk Spaceの問題
    • 800GB以上のDisk Arrayは利用してない?(2954291678 tweetsでdiskの90%を利用)
  • 解決方法 + 現在の実装方法
    • Partitionを区切る必要性が出てくる
    • どのカラムでpartitionを区切るか? primary key? user_id? time?
    • 解決策としてはtimeでのpartitioinを利用.
      • Real Timeデータの検索が多いのでtimeでパーティション区切るのが一番よい
      • 検索などする時は十分なデータを取得するまで各パーティションデータを探索する
  • 将来的な実装予定
    • Cassandra利用(non relational)
    • primary keyのpartiion
    • user idにsecondary indexをつける
    • readの90%をmemchachedする

2. Timelines

  • 初期実装
    • 以下のようなクエリでタイムライン取得してた
    • 普通にやればそうなるなという感じのSQL
SELECT * FROM tweets
WHERE userr_id IN
      (SELECT source_id
      FROM followers
      WHERE destination_id = ?)
      ORDER BY created_at DESC
      LIMIT 20
  • 問題
    • 当然ながら友人が多い場合はサブクエリ部分が異常な遅さになる。indicesもRAMに乗らない。
  • 現状の実装
    • sequenceをmemchachedで保存

3. Social Graph

  • 誰をfollowingしてるか、followerは誰かといった情報の管理
  • 初期実装
    • 2 column: source_id, destination_id
    • 誰が誰をfollowしてるかを管理するテーブル
    • Single Table, Master slave replication
    • source_id, destination_idの両者にindexを付加
  • 解決方法 + 現状の実装
    • user idでpartitionを区切っている
    • forward, backwardといった分け方をしている.
      • つまりaがbをfollowしたというテーブルとbがaにfollowされたテーブルの二種類がある
    • time, elementにインデックスをつけている
  • テーブル設計ではシンプルな分散手法がうまくいく場合が多い
  • partition, replication, indexを巧みに使う必要あり

4. Search Indices

  • いわゆる検索インデックス
  • 初期実装
    • term_idとdoc_idにマルチカラムインデックス?を付けていた
    • Single Table, Master Slave replication
  • 問題 1
    • インデックスがメモリに乗らない
  • 現状実装
    • timeでpartitionを区切っている
    • MySQL利用(mjd)
    • delayed key-write利用
  • 問題 2
    • レアな検索語句を利用されるとたくさんのパーティションを検索する事になる
    • Spaceの効率性など. MySQLがメモリを大量に必要とするのが問題となる
  • 将来的な実装
    • Document Partition利用
    • Time Partitionは変わらず利用
    • layerのマージ
    • MySQLからLuceneへの以降
  • 原則
    • Partitionを平行検索できるような感じで区切る必要あり
  • 全体的なまとめ
    • どのような手法も一時的な打開策に過ぎない
      • 最高の手法というものは存在せず、一時的に良い手法をとらざるを得ない
    • スケーラブルは魔術的な手法を必要としない
      • 重要なのはpartition, index, replicationをいかに上手く使うかにかかっている
    • real-timeデータはメモリ上に必ずのせる必要がある
      • Diskは書き込みのみ利用
    • 事前計算できないような問題は必ず出てくる

まあこんなところかと。結構省略してりますがね.

  • 参考資料
  • その他
    • Slide ShareでのNoSQL関連記事は面白いのが多いので大規模負荷分散とか必要な仕事してる人は見ておくと役に立つやも.