Twitterのアーキテクチャと遅延のしくみを考えてみる

今日もTwitterは遅延してたんで、その遅延が起こるようなTwitterのアーキテクチャを考えてみるよ。Twitterの不具合から考えてみただけで、完全に想像であって、実際になにかの資料に基づいたりはしてないので、念のため。

まず、サーバー構成はこんな感じ。

Webサーバーとデータベースサーバーは当然として、投稿したときの処理を管理するためのメッセージキューとユーザートップページを保存しておくキャッシュがあると思う。
ちなみにこのメッセージキューは今までRubyで書かれていたものがScalaに書き直されたらしく、Twitter Kestrel Projectとしてソースが公開されてる。
Twitter message queues move to Scala | The Scala Programming Language

で、データベース。

ユーザーテーブルとステータステーブルはもちろん必要。
あとは、ユーザーのタイムラインを管理するテーブルとリプライを管理するテーブルがある。
それと、フォローを管理するテーブル。
追記(2009/3/5 11:36):タイムラインテーブルは、タイムラインが40ページまでしか見れないことから、1ユーザーあたり40×20=800件程度を限度に切り捨ててると思われます。

そうすると、投稿のときの処理はこんな感じになる。

遅延が起きても、自分のタイムラインと「あなた宛のつぶやき」には表示されるので、この処理は投稿時に行われるはず。

擬似コードで処理を書いてみる。

/** 投稿処理 
 * @param id 投稿者のid
 * @param status 投稿内容
 */
function post(String $id, String $status){
  $statusId = getSequence();
  //ステータス追加
  insert into ステータス(ステータスID, 発言内容, ユーザーID, 発言時間)
    values ($statusId, $status, $id, now());
  //リプライ追加
  if($status.startWith("@")){
    $repliesId = getReply($status);
    insert into リプライ(ユーザーID, ステータスID)
      values($repliesId, $statusId);
  }
  //自分のタイムラインに追加
  insert into タイムライン(ユーザーID, ステータスID)
    values($id, $statusId);
  //メッセージキューに追加
  $queue.send($id, $statusId);
  //キャッシュをクリア
  $cache.clear($id);
}

そのあと、メッセージキューの処理として各フォロワーのタイムラインに追加する。この処理は投稿処理とは非同期に呼び出されて、一つずつ処理されていく。

投稿時の処理から、投稿者IDとステータスIDが渡ってくる。ステータスから投稿者を得れるとは思うけど、データベース呼び出しを減らしたいので投稿者IDも渡されると思う。
この処理が結構重くて、投稿頻度に対して、フォロワーのタイムラインへ追加する処理が滞ってくると、遅延が発生するというわけだ。

これを擬似コードで書いてみる。

/** メッセージ処理
 * @param id 投稿者ID
 * @param statusId 投稿
 */
function onMessage($id, $statusId){
  //フォロワーを抽出
  select * into $followers
    from フォロー
    where フォロー先ID=$id;
  //各フォロワーのタイムラインに追加
  foreach($follower in $followers){
    insert into タイムライン(ユーザーID, ステータスID)
      values($follower.ユーザーID, $statusId);
    $cache.clear($follower.ユーザーID);
  }
}

ついでに、トップページ表示はこんな感じの処理になる。

/** トップページ表示
 * @param id ユーザーID
 */
function topPage(String $id){
  //キャッシュにあればキャッシュから表示
  if($cache.exists($id)){
    print($cache.get($id));
    return;
  }
  //タイムライン抽出
  select ユーザー.ユーザー名, ステータス.発言内容 into $timeline
    from タイムライン
      inner join ステータス on タイムライン.ステータスID=ステータス.ステータスID
      inner join ユーザー on ステータス.ユーザーID=ユーザー.ユーザーID
    where タイムライン.ユーザーID=$id
    order by 発言時間 desc
  //表示
  $view.clear();
  foreach($statusin $timeline){
    $view.add($status);
  }
  print($view);
  //キャッシュに追加
  $cache.add($id, $view);
}

「あなた宛のつぶやき」の表示は、タイムラインのときのキャッシュ使わない版。投稿時にデータ追加されているので、遅延しない。

/** 「あなた宛のつぶやき」を表示
 * @param id ユーザーID
 */
function replies($id){
  //リプライ抽出
  select ユーザー.ユーザー名, ステータス.発言内容 into $replies
    from リプライ
      inner join ステータス on リプライ.ステータスID=ステータス.ステータスID
      inner join ユーザー on ステータス.ユーザーID=ユーザー.ユーザーID
    where リプライ.ユーザーID=$id
    order by ステータス.発言時間 desc
  //表示
  $view.clear();
  foreach($statusin $replies){
    $view.add($status);
  }
  print($view);
}

と、だいたいこんな感じの処理が行われているのではないかと想像するわけです。
こういう、挙動からアーキテクチャを推測する能力っていうのは、デバッグのときに重要ですね。

ちなみに、今回の擬似コードみたいにコード中にそのままSQLを書ければ便利よね、って思った人は、id:i-zukaが作ったalinous coreを見てみるといいと思います。
今回の擬似コードはalinous coreの仕様とは無関係ですけど。あ、「select * into $a」の書き方はalinous coreから取ってきた。

追記(2009/3/5 14:02)
twitter.com/kisなど、ユーザーのタイムラインを直接見にいったときにはステータステーブルから直接とってくると考えられます。だからここも遅延しない。
つまりこんな感じ。

/** ユーザーのタイムラインを表示
 * @param id ユーザーID
 */
function userTimeline($id){
  //リプライ抽出
  select ユーザー.ユーザー名, ステータス.発言内容 into $timeline
    from ステータス
      inner join ユーザー on ステータス.ユーザーID=ユーザー.ユーザーID
    where ステータス.ユーザーID=$id
    order by ステータス.発言時間 desc
  //表示
  $view.clear();
  foreach($statusin $timeline){
    $view.add($status);
  }
  print($view);
}