Hatena::ブログ(Diary)

Yoh Okunoの日記 このページをアンテナに追加 RSSフィード Twitter

2011-03-25

Facebookの新しいリアルタイム解析システムとは?

Facebookの新しいリアルタイム解析のシステムでは、HBaseで1日200億件のイベントを処理しているそうです。以下の記事の翻訳です。

Facebook’s New Realtime Analytics System: HBase to Process 20 Billion Events Per Day - High Scalability -

Facebookがまたやってくれた。彼らは巨大なリアルタイムデータのストリームを処理するもう1つのシステムを構築したのだ。以前にもFacebookはリアルタイムなメッセージシステムをHBaseで構築している(参考)。今度のシステムは1日200億件(=1秒あたり20万件)のイベントを30秒以内に処理するリアルタイム解析システムだ。

Facebookの技術マネージャAlex Himelは構築したシステムについて説明しているビデオもある)。それによると必要とされるスケールは以下のようなものだという。

ソーシャルプラグイン(Likeボタンなど)は過去数年間のうちにたくさんのウェブサイトにとってトラフィック源に成長した。先週、私たちはサイト管理者がよりよくアクセスを解析できるシステムをリリースした。このシステムにより、管理者は人々がいかに彼らのコンテンツに惹きつけられるかを知り、彼らのウェブサイトをリアルタイムに最適化するための助けとなることができる。これを実現するために、私たちは1日200億件(=1秒あたり20万件)のイベントを30秒以内に処理するシステムを構築する必要があった。

アレックスはそのプレゼンテーションにおいて素晴らしい仕事をしたので、一見をおすすめする。しかしここではより深く見てみることにしよう。

このような強力な解析システムの必要性は、Facebookがソーシャルプラグインを通してWeb支配を進めようとしていることに起因する。全ての外部サイトのアクセスはFacebookに取り込み、Facebookのもまた外部サイトにリンクしようとしている。基本的にできることはFacebookを通してアクセスをキャプチャおよびフィードバックすることと、Facebookで可能なことは全てあなたのウェブサイト上に表示することだ。これによって両者の関係をより近づけることができる。

あなたは外部のウェブサイトでソーシャルプラグインを見たことがあるはずだ。ソーシャルプラグインはあなたの友達がウェブ全体のどこでLikeボタンを押したり、コメントしたり、共有したりしたかを知ることができるようにする。ソーシャルプラグインを置くことで、コンテンツをより魅力的にできるということだ。あなたの友達はあなたが何を好むかを知ることができ、一方でウェブサイト側はユーザが好んでいるか知ることができる。魅力的なコンテンツはより多くのクリックと、より多くの「いいね!」とより多くのコメントを得ることができる。ビジネスやブランディング、あるいは個人にとっても、コンテンツがより人を惹きつけるほど、より多くの人々がそれを目にし、より多くフィードに現れ、より多くのトラフィックをサイトに誘導する。

例えばこのブログ(訳注:HighScalabilityのこと)のポストでは現在Likeボタンを設置している。TechCrunchはFacebookのコメントシステムを採用したことで有名だ。すぐにそのコメントシステムの質が議論になるが、問題はそれではなく、TechCrunchがFacebookの5億人以上のユーザのエコシステムに加わったということだ。Likeボタンとコメント以外には、推薦システムやフィード、ログイン、登録、Facepile、そしてライブストリームなどのプラグインがある。

すべてのデータは解析しなければ意味がないし、コンテンツ提供者にソーシャルプラグインが実際に彼らのサイトを魅力的にすることを証明しなければならない。そのためFacebookはInsightシステムをリリースしたのだ。この解析システムによって、あなたは収集された全ての有益なデータ(訳注:原文のjuicy dataという表現がツボに来ました)にアクセスできるようになる。Insightシステムは、Likeボタンの統計や、コメントボックスの解析、人気のページ、デモグラフィック(ユーザ層の分析)、組織的な共有などの機能を提供する。

数百万ものウェブサイトと何十億ものページと数百万ものユーザが、これらのソーシャルプラグインを通してデータを流し続けていると想像してみよう。どうすればこのようなデータすべてをリアルタイムに分析することができるだろうか? これは非常にチャレンジングな課題だ。

システムの目的

  • 信頼できる方法で、たくさんの異なる基準と、データの偏りを考慮しつつ、リアルタイムなカウンタを人々に提供する。
  • 匿名のデータを提供する。あなたは人々が誰であるかを特定することはできない。
  • プラグインが有用であることを証明する。あなたのビジネスは、そこからどのような価値を引き出すことができるか?
  • データをすぐに利用可能にする。ユーザがコンテンツをより価値あるものにするための手助けをする。
    • 新しいUIのメタファ。漏斗のアイデアを利用している。
    • どれだけ多くの人がプラグインを目にして、どれだけの人がそれにアクションを起こし、どれだけの人があなたのサイトにトラフィックをもたらしたか。
  • データを最新のものにする。
    • リアルタイムにする。48時間かかっていたものを30秒でできるようにする。
    • この目的のためにいくつかの障害を取り除く必要がある。

なにが難しいか

  • イベントタイプの多さ
    • 100以上の基準を扱う
    • プラグインのインプレッション(表示回数)
    • いいね!ボタンが押された回数
    • 新しいフィードのインプレッション
    • 新しいフィードのクリック回数
    • デモグラフィック(ユーザ属性)
  • データの規模
    • 1日あたり200億件(1秒あたり20万件)のイベント
  • データの分布の偏り
    • Likeボタンはある種のべき分布に従う。大部分を占めるロングテールは少数のLikeしか受け取らないが、一部のサイトは巨大な数のLikeを受け取る。
    • この性質はアクセス過多の領域とキー、そしてロック競合の問題を引き起こす。

さまざまなプロトタイプ

  • MySQLによるDBカウンタ
    • キーとカウンタの行を持つテーブルを作る
    • データベースへの大量アクセスが起こる
    • 書き込み頻度の高さはロック競合を引き起こし、データベースがオーバーロードしやすく、常に監視が必要で、分散の戦略を考え直す必要があった
    • この方法はこのような課題には向いていなかった
  • インメモリのカウンタ
    • IOのボトルネックが気になるなら、全てをメモリに突っ込むのだ
    • スケールに問題はない。カウンタはメモリに保存されるので書き込みは高速で、分散も容易だ。
    • インメモリのカウンタは、理由はわからないが他のアプローチより不正確だった。解析ではお金が動くためカウンタは非常に正確でなければならない。
    • 彼らは実際にはこの方法を実装していない。これは思考実験であり正確性の問題から候補から外した。
  • MapReduce
    • 以前のソリューションとしてはHadoopとHiveが使われていた。
    • 柔軟で実行しやすい。大規模な読み込みと書き込みのIOに対処できる。事前にクエリの種類を知る必要がない。データはインデクシングすることなしに保存し、クエリを実行することができる。
    • リアルタイムではない。多くの依存関係がある。実行に失敗しやすい。複雑なシステム。リアルタイムという目的にそぐわない。
  • Cassandra
    • Hbaseのほうがより可用性と書き込み効率の点で適していると思われた。
    • 書き込み効率が大きなボトルネックとなる点については改善された。

実際の実装:HBase + Scribe + Ptail + Puma

f:id:nokuno:20110325071636p:image

  • 上位レイヤー
    • HBaseが分散したコンピュータにデータを保存する
    • 追従(原文:tailing)アーキテクチャを採用し、新しいイベントはログファイルに保存され、読み出される
    • システムはイベントを巻きとり、ストレージに書きこむ
    • UIはデータを引っ張ってきてユーザに提示する
  • データフロー
    • ユーザがウェブページでLikeボタンをクリック
    • AJAXリクエストがFacebookに送られる
    • Scribeを使ってリクエストをログファイルに書き込む
    • Ptail
      • 自社開発のツールで、Scribeのストアからログファイルの末尾を読み出す。
      • プラグインインプレッション、フィードインプレッション、アクションの3種類に分けて後続に処理に流される
    • Puma
      • バッチ処理は高負荷のキーを教えてくれる。Hbaseは1秒間に大量のデータ書き込みを処理できるが、それでもバッチ処理は必要である。人気の記事は大量のインプレッションとフィードインプレッションを生むため、巨大なデータの偏りがI/Oに問題を引き起こす。この場合、バッチ処理がより適している。
      • バッチといっても平均1〜5秒程度で処理される。もっと長くするとURLが多くなってハッシュテーブルの生成にメモリ不足が生じる。
      • ロック競合の問題を避けるために、新しいバッチが始まるときは最後のフラッシュが終わるのを待つ
    • UIはデータを表示する
      • フロントエンドは全てPHPで書かれている
      • バックエンドはJavaで書かれていてThriftでPHPから使えるようにしている
    • キャッシュを使ってより高速にウェブページを表示する
      • パフォーマンスは統計的に変動する。
      • より多く長く使われるデータほどキャッシュされやすい。
      • memcacheで異なるキャッシュTTLを設定している。
    • MapReduce
      • データはHiveで解析できるようにMapReduceに送られる。
      • これはデータをHiveから復活するためのバックアップとしても機能する。
      • 生ログは一定期間の後に削除される。
  • HBaseは分散された列指向のデータストアである
    • Hadoopへのデータベースインターフェース。FacebookにはhBaseの内部を開発しているエンジニアがいる。
    • リレーショナルデータベースと違って、テーブル間のマップを作ったりはしない。
    • 行キーからたくさんの疎なカラムを得ることができ、非常に柔軟である。スキーマを決める必要がない。カラムファミリを定義することで、キーをそこに追加できる。
    • スケーラビリティと信頼性はWAL(write ahead log)、つまり実行される操作のログによるものである。
      • キーに基づいてどの領域のサーバに分散するかを決定する。
      • まずWALを書きこむ。
      • データはまずメモリに入れられる。ある時点で、あるいは十分なデータが蓄積されたらディスクに書きだす。
      • もしサーバーが停止したら、WALからデータを復旧できる。そのため永久にデータを失うということがない。
      • 高いIO信頼性のためにログとインメモリのストレージの組合せを使う。
    • HBaseは失敗の検出を行い、自動的に
    • 現在はHBaseの再分散は手動で行われる。
      • 自動的なホットスポットの検出と再分散はHBaseのロードマップにあるが、まだ実装されていない。
      • 毎火曜日に誰かがキーを見てシャーディングのプランに変更を加えるかどうか決定する。
  • スキーマ
  • サーバ1台あたり1秒間に10,000書き込みを処理する
  • チェックポイントによってログファイルからデータ読み込み中にデータが失われるのを防ぐ
  • クリック詐欺を検出するのにも使えるが、まだビルトインでは詐欺の検出は組み込まれていない
  • さらなるホットトピック
  • 今後の方向性
    • トップリスト
      • もっともLikeされたURLのリストを提示することは、例えばYouTubeのように数百万のURLが素早く共有されるような領域では非常に難しい
      • インメモリでソートしてデータの変更に対して最新に保つためには新しい解決策が必要だ
    • ユーザ数の集計
      • タイムウィンドウ内であるURLをLikeしたユーザの数。MapReduceでは容易に計算出来るが、単純なカウンタという方法で行なうことは困難である。
    • ソーシャルプラグイン以外のアプリケーションへの一般化
    • 複数のデータセンターのサポート
      • 現在は単一のデータセンターしかサポートしていない。しかし複数のデータセンターに拡張したい。
      • 現在のやり直しプランはMapReduceシステムを使うこととなっている。
      • バックアップシステムは毎晩テストされている。Hiveとこの新しいシステムの結果の一致を見ている。
  • プロジェクト
    • 約5ヶ月かかった。
    • 最初は2人のエンジニアから始まった。次に50%のエンジニアが加わった。
    • 2人のUIエンジニアがフロントエンドを担当している。
    • 14人がエンジニアリング、デザイン、PM、そして運用に携わっている。

おわりに

私たちが以前のメッセージングシステムとこの解析システムを見たとき、2つのシステムには共通部分があることに気づいた:大規模、HBase、リアルタイム。信頼性と即時性を維持して巨大な書き込みを行なうというチャレンジは、これらの課題に共通の基盤となっている。FacebookはHBase, Hadoop, HDFSのエコシステムにフォーカスしており、運用上の問題が改善されることを期待している。別の部分ではCassandraが好まれていて、スケーラビリティや複数データセンター対応、運用の手軽さなどで優れているが、このような解析の課題には適していなかった。

このことはあなたにとってどのような意味を持つだろうか? もしあなたがFacebook社員ではなかったとしても、このアーキテクチャは十分にシンプルで、十分に切り離されたツールから構成されており、もっと小さなプロジェクトでもうまく動くだろう。