トップ  > メモ一覧  > カテゴリ「スケール」の絞り込み結果 : 2件

2件中 1 〜 2 表示  1 

No.2911 秒間120万つぶやきを処理、Twitterシステムの“今”

秒間120万つぶやきを処理、Twitterシステムの“今”

2010/04/19

photo01.jpg Twitterのシステム・アーキテクト、Nick Kallen氏

 ユーザー同士のつながりを元に時系列に140文字のメッセージを20個ほど表示する——。Twitterのサービスは、文字にしてしまうと実にシ ンプルだが、背後には非常に大きな技術的チャレンジが横たわっている。つぶやき数は月間10億件を突破、 Twitterを流れるメッセージ数は秒間120万にも達し、ユーザー同士のつながりを表すソーシャル・グラフですらメモリに載る量を超えている。途方も ないスケールのデータをつないでいるにも関わらず、0.1秒以下でWebページの表示を完了させなければならない。そのために各データストレージは1〜 5ms程度で応答しなければならない。

 Twitterのリスト機能の実装でプロジェクトリーダーを務めたこともあるNick Kallen氏が来日し、2010年4月19日から2日間の予定で開催中の「QCon Tokyo 2010」で基調講演を行った。「Data Architecture at Twitter Scale」と題した講演では、Twitterが最初に実装した素朴なシステムから、どのような課題に直面し、それをどうやって解決してきたかを概説し た。ローカリティ(局所性)を考慮したデータのパーティショニング戦略の重要性や、それがアクセスパターンに強く依存したものであること、あるいは重たい 計算処理が発生するクエリでは事前に処理を行っておくことなど、興味深い技術的洞察に満ちた講演だった。

twitter01.jpg Twitterが配信するメッセージは秒間120万にも達するという

単純なパーティショニングでは解決しない

 サービスの構造がシンプルなTwitterは、サービス開始当初には実装もシンプルだったようだ。各つぶやきのIDをプライマリキーとして、ユー ザーIDやテキスト、時刻などを1つのテーブルに保存。これをマスター・スレーブ構成とすることで、readの性能を上げるというストレートなスケーリン グを行っていたという。

twitter02.png もともとのTwitterのDBスキーマ

 memcachedによる高速化も行ったものの、最初に直面した課題は意外にもディスク容量の上限だったという。つぶやきの数が30億に近づき、 800GBというディスク容量の上限の9割にまで迫った時期があるという。「800GBを超えるサイズのディスク・アレイを導入することは避けたかっ た」(Kallen氏)というあたりは、Web系企業らしい発想で、これに対処するために、パーティショニングを行ったという。

 パーティショニングとは、例えばユーザーIDを偶数、奇数に分けて2つのDBに分けて保存するテクニック。特定のユーザーのつぶやきを表示する場 合、IDが偶数か奇数かで問い合わせすべきDBが一意に決まるため、分割すればするほどレスポンスが上がり、1つ1つのDBのサイズも抑えられる。

 ただ、ユーザーIDに基づくパーティショニングでは、特定のIDを持つつぶやきを見つけることができなくなる。そのIDのつぶやきを誰がしたかが 分からないからだ。このため、せっかくパーティショニングした複数のDBをすべて検索しなくてはいけなくなる。

twitter03.png パーティショニングの1つの方法。つぶやきのIDを元に分けることが考えられるが、この分割方法ではユーザーIDに 対応するつぶやきの検索には全パーティションに対するアクセスが発生してしまう

 つぶやきのIDでパーティショニングしても、逆の問題が起こる。特定のIDを持つつぶやきがどのパーティションにあるかは分かるが、あるユーザー IDに紐付いたつぶやきのIDは、結局すべてのパーティションを検索しないと分からないからだ。

時系列にパーティショニング

 つぶやきの量が多すぎるため、単一のテーブルに保存するのは非現実的。かといって、ユーザーIDやつぶやきIDに基づいて何らかの形で分割すると いうのも、あまりうまくいかない。

 そこで現在のTwitterでは、時系列のパーティショニングを行っているという。1月のつぶやき、2月のつぶやき、3月のつぶやき、今月(4 月)のつぶやき、というように時間軸に沿ってデータを分割しているのだという。

twitter04.png 現在のTwitterのデータのパーティショニング方法。時系列に分割しているという

 この分割戦略は「当初はとてもまずい実装のように思えた」(Kallen氏)という。n個のパーティションに分割したら、そのアクセス時間の平均 はO(n)となるからだ。ところがTwitterというサービスには、Kallen氏が「時間的局所性」(temporal locality)と呼ぶ独特のアクセスパターンがある。「実際にはほとんどのクエリは、より新しい情報へのバイアスがかかっている」(同)からだ。ほと んどの人のリクエストは最新のパーティションに対するクエリで完結する。すべてのユーザーがアクティブなわけではないため、「あるユーザーの直近のつぶや き20件」は、複数のパーティションにさかのぼっていくことになるが、それでもこの戦略によりアクセス時間の平均は事実上O(1)となっているのだとい う。

 今後はFacebookで開発されたオープンソースのCassandraを使い、つぶやきのIDとユーザーIDのそれぞれをプライマリキーとした テーブルを使う計画だという。

メール配送に似た非同期の仕組み「fan out」

 Twitterで次に大きな問題となるのはタイムラインだ。

 タイムラインにはフォローしている人のつぶやきが流れてくるが、これはつまり以下のようなSQL文に相当する。

twitter05.png サービス開始当初の素朴なクエリ。矢印で示した部分がメモリ上に載らなくなり、非常に遅くなったという

 上のようなストレートな実装では、フォロワー数が増えていくると途端にスケールしなくなる。メモリに載り切らずにディスクアクセスが発生し、レス ポンスが落ちるためだ。ディスクアクセスのペナルティは大きく、1秒以下で終わるはずのページの描画が数秒かかるということになる。

 さらにTwitterの技術上の課題を大きくしているのは、リストやブロック関係、あるいは「@someone」というリプライによってメッセー ジの配信先が変わるということだ。これは非常に大きな計算処理である一方、「Hadoopを使って50分かけて処理するタイプの問題ではな い」(Kallen氏)。あくまでも数msという低遅延で行わなくてはいけない。

 こうした問題への対処方法として、Kallen氏は2つのアプローチを紹介した。

 1つは「fan out」と呼ぶメール配送に似たアーキテクチャを使うこと(fan outは漢字で書くと“扇出”か。風で一気にまき散らすようなイメージ)。各ユーザーのタイムラインをメールの受信箱のように見立てて、そこにメッセージ を配信する。つぶやきはいったんmemcachedに保存され、それが各受信箱(タイムライン)に送られるが、その配送処理は非同期のオフライン処理だと いう。ただ、オフラインといっても夜間バッチのような半日単位というものではなく、秒単位の遅延を上限としたものであるという。

twitter06.png 現在Twitterではメール配送に似た仕組みでフォロワーにつぶやきを配送しているという

 もう1つの工夫は、フォローと被フォローの関係をそれぞれ別にデータに持つこと。論理的には片方向のグラフだけ持っておけば十分だが、あえて「誰 をフォローしているか」「誰にフォローされているか」に分けてデータ化しておく。データの整合性に気を付ける必要はあるものの、こうしておけばクエリは特 定パーティションへのアクセスで完結するため、メモリに乗り切らないという問題も解消するのだという。

 こうした仕組みにより、書き込み側のデッドロック(すべてのつぶやきは巨大な単一のデータセットに放り込まれる)を解消しつつソーシャル・グラフ がメモリに乗り切らないという課題を乗り越えて、リアルタイム性の高いサービスを実現できている。

 2008年時点でTwitter上で生まれるつぶやきの数は秒間30だったが、2010年4月現在は約700にまで膨れ上がっている。スポーツイ ベントやオスカーの発表時など、ピーク時には秒間2000に達するという。そして1つのつぶやきは平均600個もfan outされるため、秒間120万のメッセージ配送を処理する能力が求められるという計算だ。

twitter07.png 2008年時点と現在とでのTwitterの統計情報。秒平均30だったつぶやき生成速度は700にまで上がり、そ の結果最大で秒間120万程度のメッセージを配送しているという

 Twitterは現在もまださまざまな技術的課題を抱えている。例えば検索インデックスについても時系列のパーティショニングを行っているため、 検索される頻度が低い単語などでは最新パーティションにインデックスがないため何もヒットしないということが起こる。このため、現在MySQLベースで 行っている検索インデックスを時系列のパーティショニングだけでなく、ドキュメント単位にパーティショニングする案や、MySQLの代わりに全文検索エン ジンの「Lucene」を使うという案を検討しているという。

原理は自明でも定石のない世界

 余談だが、Nick Kallen氏は2008 年9月にTwitterに加わる以前から、Ruby on Railsコミュニティでは広く知られたハッカーだった。RailsのORM層であるActiveRecordで、より抽象度の高いクエリを構成できる 「Named_scope」を実装したのがKallen氏だ。Named_scopeを使えば、例えば「公開フラグが立っているブログエントリ」という条 件に名前を付けておくことで、積集合の演算を端的に表現できるようになる(参考)。 このNamed_scopeの発想をさらに押 し進めて関係代数に基づいてKallen氏が実装したのがRuby向け汎用データクエリライブラリ「Arel」で、これは、まもなく正式版がリリースされる次期Ruby on Railsのメジャーバージョンアップ、Ruby on Rails 3にも含まれる。ArelはC#などにあるLINQに似て、条件をメソッドチェーンとしてつなげていくことができる。

 Arelというクエリの抽象化を行う実装を行ったKallen氏だが、Twitterのような実サービスで重要なのは、むしろ、パーティショニン グやローカリティの利用の方法論にはこれという単一のアプローチが存在しないという認識を持つことだと指摘する。「すべてのエンジニアリング上の解決策と いうのは、一時的なものだ」(Kallen氏)。

 Twitter規模のスケーラビリティの問題を抱えるエンジニアは多くはないかもしれないが、今後、巨大なデータセットに対してリアルタイム性の 高いシステムを設計・実装することがあれば参考になるのかもしれない

引用元

更新:2010/08/08 18:44 カテゴリ: web開発  > スケール ▲トップ

No.1292【引用】はてな流大規模データ処理

はてな流大規模データ処理
」を以下にアップロードしました。

http://bloghackers.net/~naoya/ppt/081108huge_data.ppt

一部参考文献からの引用 (Introduction to Information Retrieval から Vector space model の図、たつをの ChangeLog から転置インデックスの図) があります。この場を借りて感謝。
環境によってはおそらくフォントの表示がいまいちだと思いますが、ご了承ください。
追記
SlideShare にアップロードしました。
081108huge_data.ppt

View SlideShare presentati...

引用元

更新:2009/08/09 00:16 カテゴリ: web開発  > スケール ▲トップ
2件中 1 〜 2 表示  1 

FuelPHP

Mac

フロントエンド開発

web開発

プロマネ

マネタイズ

プレゼン

webサービス運用

webサービス

Linux

サーバ管理

MySQL

ソース・開発

svn・git

PHP

HTML・CSS

JavaScript

ツール, ライブラリ

ビジネス

テンプレート

負荷・チューニング

Windows

メール

メール・手紙文例

CodeIgniter

オブジェクト指向

UI・フロントエンド

cloud

マークアップ・テキスト

Flash

デザイン

DBその他

Ruby

PostgreSQL

ユーティリティ・ソフト

Firefox

ハードウェア

Google

symfony

OpenPNE全般

OpenPNE2

Hack(賢コツ)

OpenPNE3

リンク

個人開発

その他

未確認

KVS

ubuntu

Android

負荷試験

オープンソース

社会

便利ツール

マネー

Twig

食品宅配

WEB設計

オーディオ

一般常識

アプリ開発

Python

サイトマップ

うずら技術ブログ

たませんSNS

rss2.0