twitterみたいなマイクロブログを作るとしたらどう実装する？

ある空想をしてみましょう。あなたはある企業の情報システム部門の技術者です。その会社のイントラネットシステムを担当しており、メールやワークフローの運用や保守を行なっています。大規模な開発を外部委託する窓口を担当する傍らで、社内へのお知らせ掲示板などの簡単なアプリケーションは自ら開発もしています。

ある日、社長が情シス部長に言いました。

「なんか『ツイッター』ってのがおもしろいらしいんだよね。しかも無料らしい。うちの会社でもやろう」

情シス部長は社長の発言をそのままあなたに伝えます。

「無料で、社内で、ツイッターを、やれ。」

twitter.comにアカウントを作ってしまうのも手かもしれませんが、社内の発言が外に見えてしまうのは気になります。自力で構築するしかないと踏んだあなたはいくつかのサイトを見て回りました。どうやらオープンソースのマイクロブログがあるようです。また、Yammerというサービスはイントラネット向けにパッケージが販売される動きもあるようです。よし、いける。そう思ったあなたは3秒後に首を左右に振りました。

「うちの基盤は、Lotus Notesだった。」

Lotus Notesのオーソドックスな手法、すなわちビューと文書を用いてtwitter相当のアプリが作れるだろうか、その疑問をきっかけにもう1つの疑問が生まれました。

「twitterってどう実装されているんだ？」

twitterの姿とは

さて、twitterとはどのようなサービスでしょうか。参照系、更新系、管理系にわけて主な機能を洗い出してみます。

参照系

1. タイムライン
   自分がフォローしている人と、自分の発言が時系列順に20件ずつ表示されます。
2. あなた宛のつぶやき
   自分に向けられた公開つぶやき（@username）を表示します。
3. ダイレクトメッセージ
   自分だけに公開されたつぶやきを表示します。
4. 全体の公開つぶやき
   twitter全体から公開つぶやきを取得します

更新系

1. つぶやく
   自分のつぶやき内容が時系列で表示されます。
2. お気に入り
   あるつぶやきをお気に入り登録します。
3. フォローする
   他のユーザをフォローします。

管理系

1. 「フォローする」の表示・削除
   自分がフォローしているユーザを表示します。
2. 「フォローされている」の表示・ブロック
   自分をフォローしているユーザを表示します。

他、会員登録やつぶやきの削除などの機能は省略しました。

さておそらくtwitterはこれらをRDBとキーバリュー型データストアあたりに保存していることと思われます。こちらの記事にもありますが、一般論からすればtwitterの仕様は性能を出しやすいとは決して言えません。

大規模サイトの舞台裏：大規模SNSのボトルネックとソリューション (1/4) - ITmedia エンタープライズ via kwout

こちらの記事はGREEというSNSのパフォーマンスについて書かれたものです。twitterについても同じような問題が出てきます。

• ひとりひとりのフォロー先は異なる。そのためタイムラインも異なり、共通データをキャッシュしても意味がない
• 発言を格納するテーブルが1つだった場合、データが肥大化して問い合わせのコストが上昇する
• テーブルが複数だった場合、ソートで困る

ですので例えば新人研修でRDBについてみっちり講義した後に「自由に情報共有システムを作ってみよう」というお題を出したとして、twitterと同じものを考えてきた人がいたら小一時間その意図を問い詰めたいところです。どうやってスケールするか考えて設計したか、と。

テーブル構造の妄想

今のtwitterがどのような構成になっているかうかがい知る資料を見つけることはできませんでした。推察するに、GREEの「友達の新着日記」と同様にユーザごとにタイムラインを保持しているのではないかと思います。以下はできるだけシンプルに考えた妄想のマイクロブログモデルです。実機に組んで検証したり第三者のレビューを受けたものではありませんが、RDBに組むならこんな感じかな、ということを考えてみました。

（イメージ）ユーザAのタイムラインテーブル

（イメージ）フォロー関係テーブル

（イメージ）ユーザBの発言テーブル

タイムライン

GREEやmixiで見られるような友達の最新日記では、見せるのは何件かに限られます。そのため無用なDBアクセスを増やさないために日時、友達の名前、発言内容が非正規化された状態で保存されているものと思われます。twitterの場合は過去に遡ってすべての発言が格納されていることから、文書IDをキーとしてテーブルを分割しているように思います。twitter.comのサイトからは20件おきにしかアクセスできませんので、副問い合わせも大きな負荷ではないでしょう。上のイメージでいうところのユーザBのテーブルはユーザごとに分かれているとテーブル数が凄まじくなりますので、実際のところはユーザ何人かでまとまっているでしょう。ただし下で述べるフォロー時の処理を考えると1人のユーザの発言がいたずらにバラバラのテーブルに書き込まれることは無さそうです。

フォロー(した|された)場合

ここでユーザAが新たにユーザXをフォローした場合はどうでなるでしょうか。フォロー関係テーブルを更新するとともに、ユーザXの発言をすべて抜いてきてユーザAのタイムラインに追加する処理が発生します。このとき、ユーザXの発言をすべて、の抜きやすさはテーブル数が少なく、また総当りしなくてもテーブルを特定できる（ユーザIDからのハッシュ値計算など）ことが望ましいでしょう。

新たに発言した場合

その後、ユーザXが発言した場合はどうなるでしょうか。ユーザXの発言は発言IDが付与された後にユーザXの発言テーブルに格納されます。そしてフォロー関係テーブルで被フォロー者がuserXのレコードを取得し、ユーザXをフォローしている人のタイムラインに発言IDを配信します。ダイレクトに処理したら大変ですので、キューイングされるでしょう。高負荷時はタイムラインの取得リクエストがあったことをイベントとして処理を行い、リクエストがないデータについては遅延させてしまうというのも割り切っていてよいかもしれません。

タイムラインのソート

ここのところでタイムラインの「ソート」について考えなくてはなりません。データ量が大きくなればなるほどソートは大変になります。しかし既にソートされているデータにソートされているデータを差し込むのはそう難しいことではありません。人間がUIを操作しながらフォローを増やしていったり、被フォローが増えていく過程は非常に緩やかですので、無理のある処理にはならないでしょう。レコード数が大きくなりすぎないように設計できたならばそのへんのRDBMSのB+木か何かに任せれば問題ないと思われます。レコードにポインタ的列を持たせて並び順が次に位置する文書IDを格納してもおもしろいかもしれません。挿入データが既にソートされているので、先頭から1回だけ全行をスキャンすれば挿入とソートの処理が終わります。

もしフォローした1000人分の発言をすべて抜いてきて、一度にソートしようとしたらえらいことになるでしょう。

あなた宛のつぶやきとDM

@UserIDのつぶやきについては、相手が自分のフォローリストに入っていない場合と入っている場合とで処理が異なります。入っている場合は普段と同じつぶやき処理になりますが、入っていない場合は普段の処理に加えてつぶやきを送った相手のタイムラインテーブルに自分の発言レコードを突っ込む処理になります。自分に向けられたつぶやきを見る場合は、自分のタイムラインから@UserIDで始まるものを抜き出すか、そもそもタイムラインへの登録時に@UserIDで始まるものにフラグを立てる、あたりになるでしょう。DMは普段のつぶやき処理を行なわず、相手のタイムラインにだけつぶやきを配信します。

自分のつぶやき

自分のタイムラインに自分の発言が入っていますので、自分のユーザIDでレコードを検索します。

お気に入り

ある発言をお気に入りに追加する場合、お気に入りテーブルが必要になります。自分のユーザID、文書IDの構造になるでしょう。

キャッシュについて

twitterで特に頻繁にアクセスされるレコードは最近1日分くらいのデータでしょうから、それらはRDBでなくオンメモリのキーバリュー型データストアに書き込んでおいたらRDBを検索するコストが更に下げられるでしょう。処理としては24時間以内のレコードならば文書IDのみをキーにキーバリュー型データストアを検索し、24時間以前ならばユーザIDをキーにしてテーブルを見つけ、その中から該当する文書データを持ってきたらいいかと思います。ただし各人のタイムラインのトップ20件については、フォローしている人が誰か1人でも発言したら更新されてしまいますのでキャッシュ効果があるかどうか疑問です。反対に全体の公開つぶやきは、確かに更新の可能性も高いですが、読み込まれる回数もそれだけ多いと思われます。そのバランス次第ではキャッシュに入れたほうが望ましいかもしれません。

でも一人当たりの平均とか総発言数、1時間当たりの発言数、ピーク時のリクエスト／秒などを聞かずに好きなように妄想するというのも健康的でよいですね。

いい加減、長くなり過ぎたのでこれをLotus Notesで実装したらどうなるか？についてはまた気が向いたときに書きます。（環境が無いのでソースなどは出せませんが。）乞うご期待。