Twitterがスケールに苦しむ理由

Twitterのスケール関係で、面白い記事を発見したのでまとめ。

一時期「スケールしない」とか「動作が不安定」だとか言われ続けていたTwitter。5月ごろにslashdot.jpでも話題になっていた。論調は総じて「Twitterがスケールしないのは、Rubyを使っているから」というもの。

ところが同じ５月、「Why Can't Twitter Scale? Blaine Cook Tries To Explain（なんでTwitterってスケールしないの？）」という、blog紹介記事がSilicon Alley Insiderに掲載される。記事の元になったblogエントリは、Twitterの前チーフアーキテクトだったBlaine Cook氏によるもの。Cook氏によれば、TwitterのスケールとRubyは何の関係もないという。

Why Can't Twitter Scale? Blaine Cook Tries To Explain

In Twitter's case, there is zero chance that the problems there are in any way related to their language. It is likely that there are architectural challenges which come from the fact that it is very hard to cache a Twitter data request since no two people ever get the same data. And even for a given user, the data requests change quickly since users are always receiving tweets. This is a hard, though not unsolvable problem that requires a very specialized caching architecture. Eran Hammer-Lahav, has done some interesting work in this area and talks about it in an extensive blog post.

Twitterの場合、スケールの問題に、開発言語（Ruby）が少しでも関係している可能性はゼロといっていい。原因は、レスポンスをキャッシュすることが非常に困難であるというTwitterのアーキテクチャ上の問題だろう。ユーザはみんな（フォローリストの中身によって）それぞれ違うデータを取得するわけだから、ユーザ間でキャッシュの使いまわしができない。そして、ある特定のユーザのみをとって見ても、彼がフォローするユーザが発言するたびに取得すべきデータが頻繁に更新されてしまうわけだから、キャッシュしてもあまり意味が無い。この問題を解決するにはかなり特殊なキャッシュ・アーキテクチャを実装する必要がある。

と、Ruby責任説を完全否定し、Twitterのスケール問題はそのアーキテクチャに問題があるからだと言っている。じゃぁ、Twitterはなんであんなにスケールに苦しめられていたの？そのスケールを阻むアーキテクチャって何？

その答えは、上記記事でもポイントされているように、Hueniverse社のfounderであるEran Hammer-Lahav氏による解説記事「Scaling a Microblogging Service - Part I」で触れられている。

Scaling a Microblogging Service - Part I
People don’t seem to get what is so hard about scaling the Twitter service. Some think it has to do with Rails, while others look at the hosting company or other operating factors. Then there are those who incorrectly think a distributed or federated service is the solution (which will only make things worse). The idea that building a large scale web application is trivial or a solved problem is simply ridiculous. In a way it is surprising that there are so few companies out there dealing with commoditizing web developing scaling.

Twitterをスケールさせることの何がそんなに難しいのか、みんなわかっちゃいないみたいだ。Railと関係があるって人もいるし、データセンターとか運用の問題だろうという人もいる。分散システムを導入すれば問題が解決するとか考えてるやつもいる。そんなことしても状況が悪化するだけだ。大規模なWebアプリケーションを構築することが簡単だと考えるのは馬鹿げている。（それほど難しいことだというのに）そういったWebアプリケーションのスケール周りをコモディティ化してくれる会社が数えるほどしかないっていうのは、ある意味驚くべきことだ。

There are two main subsystems from an infrastructure standpoint (regardless of the actual implementation). The first is the distribution (or delivery) system which takes every incoming message and delivers it to the right list of followers via Instant Messaging, SMS, or email. The second is the retrieval (or query) system which allows users to query what the people they are following and the general population (the public timeline) have been up to (few messages at a time).
Building the delivery system isn’t trivial, but much easier to scale. Subscription lists are generally static (who is following who) and tend to be small (even thousands of followers is still a small list). Twitter only allows following all updates of a certain user or tracking all updates of a certain list of words, which means there isn’t any heavy calculation being done at the distribution point as to who should receive which message.

実装面を別にすれば、インフラ面からTwitterを考えた場合、大きく二つのサブシステムに分けることができる。一つ目は届いたメッセージを、フォロアーにIMやSMS、emailを使って届ける「ディストリビューションシステム」。二つ目は、自分がフォローしているユーザや、その他のユーザについての、ステータス一覧（最新メッセージ）を取得する「クエリシステム」だ。
一つ目のディストリビューションシステムを構築するのは簡単じゃないけど、スケールさせるのはずっとたやすい。誰が誰をフォローしているかを表す"サブスクリプションリスト"は静的だし、リストのサイズも大抵は小さい。Twitterでは、あるユーザの発言は、フォロアー全員に届ければいいわけだから、どのメッセージを誰に届けるのかについて色々と計算する必要ない。

In its current state, pushing updates out isn’t a challenge even at a large scale, and something that has generally scaled well and has showed very solid performance and stability in the past year. If Twitter was a push-only service, they would have no scaling issues at all – but in a way a much more difficult time competing with little-to-none technology barriers to slow competitors.

The retrieval system is where things are not as simple. Unlike webmail services where refreshing a user’s inbox only queries a very simple data set (is there anything new in MY inbox?), refreshing a user’s home page on Twitter queries a much more complex data set (are there any new updates in ALL my friends’ pages?) and the nature of the service means that the ratio of reads to writes is significantly different from most other web services.

そういうわけだから、あがってきたメッセージを配送することに関しては、規模が大きくなってもそれほど難しくはないし、実際こういった類のアプリケーションはかなりスケールして、パフォーマンスも良好、且つ安定稼動させることができるってことが、過去に示されている。Twitterがこんな風に、PUSH要素しかないシステムであればスケールの問題なんておきなかっただろうし、競合に対しても技術優位性を確保できなかったから、競争はある意味もっと厳しかっただろう。
「クエリシステム」はそれほど簡単な話じゃない。DBへの問い合わせが簡単なwebメールサービスとか（自分のメールボックスに新しいメールが来ていないかどうかを調べるだけでいい）と違って、Twitter上で自分のホームページをリロードする（自分の友達全員のページそれぞれに、何らかの更新があるかどうかを調べなきゃいけない）ってのは、かなり複雑な問い合わせをする必要がある。しかもTwitterの使われ方では、ユーザの読みこみ/書きこみ比率が、他のWebサービスと比べてかなり違う。

It is these constant queries that bring Twitter down during popular events. The fact that a single request for a user’s home page or an API request for a user’s friends timeline must perform a complex iterative query is what causing some requests to take too long, at best timeout and at worst cause the entire system to lag behind. These custom views are expensive and mean that it is much more difficult to cache the final result of a request.

Going through a timeline request, the server first looks up the list of people the user is following. Then for each person, checks if their timeline is public or private, and if private, if the requesting user has the rights to view it. If the user has rights, the last few messages are retrieved, and the same is repeated for each person being followed. When done, all the messages are collected, sorted, and the latest messages are converted from their internal representation to the requested format (JASON, XML, RSS, or ATOM).

何か大きなイベントがあった時にTwitterがダウンしてしまうのはこういった処理のせいだ。アクセスのたびに複雑で反復的ななクエリを実行する必要があるから処理に時間がかかる。リクエストがタイムアウトしたり、運が悪けりゃシステム全体がラグってしまう。ユーザごとにカスタムされた情報を表示しないといけないから、生成負荷は重いし、キャッシュも難しい。
この処理では、まずユーザがフォローしている人のリストを取得する。そしてそれぞれの人に対して、ステータスが公開か非公開か、もし非公開だった場合アクセスしたユーザに閲覧権限があるかどうかを調べる。もし権限があれば最新の数件のメッセージを取得する。こういったことをフォローリスト全員に対してやらなきゃいけない。全部終わったら、取得したメッセージを集めて、時系列で並び替えて、最新の数件だけをJSONだとかXML、RSS、ATOM形式に変換する。

As long as all the messages in the system can fit into a single database table, this can be done with a pretty straight-forward query leaving the heavy lifting to the database. But once a single table or even a single server isn’t enough to hold the entire message base (or support the load), an application has to perform multiple database requests to gather the data. Partitioning the database which for many application is enough to offer scalability, solves the issue of a large and inefficient single table scenario, but is also the reason why the system slows down. Sharding takes away the ability to leverage the database indexing services to optimize users’ views. If the people you are following are not all on the same partition, multiple data queries are required.

全部のメッセージが単一のデータベースに入っているなら、こういった抽出処理は、データベースの負荷は重いけれども、シンプルでわかりやすいクエリですませることができる。でもデータがテーブルひとつに収まりきらなくなったり、サーバ一台では容量がたりなくなってしまったとき、アプリケーションは複数のデータベースにリクエストを投げなきゃいけない。データベースの分割は、スケールの手段として多くのWebアプリケーションで有効だけれど、（Twitterのようなソーシャルアプリケーションでは）データベースの分割は、システムの実行速度を遅くさせてしまう。データベースが分割されていた場合、クエリを処理する上で有効だったインデックスの威力が減退してしまうからだ。たとえばあるユーザがフォローしている友達が全員同じデータベースに載っていなかったとしたら、別のデータベースを探しにいかなきゃいけない。

Twitterが苦しんでいた原因は、ソーシャルアプリケーション特有のデータ処理が、RDBMSにとって、かなり取っ付きにくい類の処理だったからだ。では、TwitterのようなWebサービスは、どうすればスケールしてくれるのか。

One simple but painfully restrictive solution is to duplicate the data for each user. Basically what this means is turning the service into an email system. Each user is given a mailbox and whenever someone they are following publishes a status, it is copied into their inbox, as well as into all the other followers’ inboxes. This brings the solution in line with existing systems such as webmail services where data partitioning alone can accomplish great scaling. But this comes at a price. First the data storage grows significantly faster and requires much more disk space, together with increased backup cost. Second, it makes other actions much more complex such as erasing a message once sent.

ユーザごとにデータを重複して持たせることが、この問題に対する解法のひとつだ。emailと同じように、それぞれのユーザに「メールボックス」みたいなものを持たせて、誰かがステータスを更新したら、そのユーザをフォローしている人全員のメールボックスにそれぞれステータスのコピーを入れる。こうすればWebメールと同様、データベースを分割した状態で、いくらでもスケールさせることができる。欠点のひとつは全体のデータサイズがかなり大きくなってしまい、ディスクスペースを浪費すること。欠点のもうひとつは、一度送られてしまったメッセージが削除されたようなときにかなりややこしい処理をするはめになること。

つまり、ユーザからアクセスがあって初めて情報（フォローしている人のステータス）を探しにいくのではなく、誰かのステータスが更新された時点で、その人をフォローしているユーザ全員のページ情報を更新し、どこかに保管しておくというもの。こうすれば、情報の更新自体は、「デリバリーシステム」とほぼ同じ処理なので簡単にスケールするし、ユーザが友達の最新ステータスを取得しにきたときには、既に準備された情報を送るだけなので、Webメールと同様、やはり簡単にスケールすることができる。

Twitterが直面したアーキテクチャ上の問題は、Twitterに限った話ではない。FacebookやPownce、LinkedIn、mixi等、ソーシャルネットワークをベースに組み立てられたコミュニケーションサイトであれば、程度の差こそあれ、同様の課題をアーキテクチャに抱えているといえるだろう。この問題への対処は、SNS系サービスを大きくする上で避けては通れないはず。
たとえば日本のGREEがこの問題に対してどのように対処しているか、ITmediaの記事「大規模SNSのボトルネックとソリューション」で詳しく解説されている。

大規模SNSのボトルネックとソリューション
一定以上のユーザー数、データ量、そして機能を持つSNSでは、普通に構築していくと非常に悩ましいボトルネックが2つ顕在化してきます。1つは、「友達の新着」系の情報取得です。もう1つはアクセスコントロール、つまり「この情報は全体に公開、こちらは友達の友達まで」といった制限です。

（中略）

blogテーブルが肥大化してくると問題が顕在化します。例えば1日平均で10万件程度の日記が書かれるとすると、1年でおよそ3500万〜4000万レコードのテーブルとなります。すると、WHERE句とORDER BY句が並存した場合にインデックスが効果的に使われない*ため、パフォーマンスが劣化していきます。例えばuser_idとpublication_datetimeにマルチカラムインデックスが張られていても、

SELECT title FROM blog WHERE user_id IN （...）

で取得される件数（つまり自分の友達が書いた日記の総数）が増えれば増えるほど、ソートにコストが掛かります。

（中略）

また、GREEではログイン後の初期画面（いわゆる『ホーム』。図1）で、友達の新着情報を各種（日記、フォト、レビューなど……）表示させていますが、ホームはサイト内でもかなりアクセスの多いページで、毎回前記のような動的ページ生成を行うと、非常にコストが高くなります。
この問題に対処するため、単純にページキャッシュなども利用できますが、

• 表示されるデータがユーザーごとに異なるため、キャッシュのヒット率が非常に低い
• データの性質上即時性が求められるため、あまりキャッシュしたくない

という問題があり、キャッシュの利用も避けたいところです。

ではＧＲＥＥはこの問題にどう取り組んだのか。

これら2つの問題について、目下のところGREEでは、「フックを利用したイベント通知機構」を利用して解決しています（図2）。つまり、

• リクエストがあったタイミングでデータを取得する

のではなく、

• データ更新のタイミングであらかじめ必要なデータを非同期に構築しておく

わけです。

考え方としては、個人ごとに「メールボックス」のようなものを準備するHammer-Lahav氏の説明と大体同じで、且つデータのDBへの挿入は非同期で処理し、フロント側（webサーバ）を待たせるようなことはしないと。フロント側の処理を迅速に終わらせることは、Webサーバリソース（プロセスやスレッド）の回転効率を上げることにつながり、サーバのメモリ使用効率が高まる。

このあたりの話は、httpでいかにC10K問題を解決するか、という文脈で語られることが多い。データの格納をWebサーバと非同期でやるべきという考え方は、Life is beautiful(中島聡さん)の記事「マルチスレッド・プログラミングの落とし穴、その２」でも紹介されている。

前述のHammer-Lahav氏は、現在Real-Time Content DeliveryエンジンであるNouncer開発プロジェクトに従事されているということで、これを使えば開発者は簡単にスケールするMicro-blog（Twitterみたいなサービスの総称）サービスを作れちゃうらしい（サイトを見たところプロジェクトが停滞しているようだけれど..）。　こうやってまたひとつ技術がコモディティ化していくんだなー。。