Facebook Timeline は、データの非正規化という破壊力で誘う

Posted in Big Data, Facebook by Agile Cat on February 8, 2012

Facebook Timeline: Brought to You by the Power of Denormalization
http://wp.me/pwo1E-3TI
Monday, January 23, 2012 at 9:14AM
http://highscalability.com/blog/2012/1/23/facebook-timeline-brought-to-you-by-the-power-of-denormaliza.html

Facebook Timeline is audacious in scope. It wants to compile a complete scrollable version of your life story from photos, locations, videos, status updates, and everything you do. That could be many decades of data (hopefully) that must stored and made quickly available at any point in time. A huge technical challenge, even for Facebook, which we know are experts in handing big data. And they built it all in 6 months.

Facebook Timeline のスコープは大胆である。この Timeline は、Photo／Location／Video／Status Update といった全ての履歴から、あなたのライフ･ストーリーを作成し、その全体をスクロールできるバージョンへと編集してくれる。それらのデータは、何十年にもわたりストアされたはずのものであり、また、どのような想い出であっても、素早く参照できる。そして、たとえ Facebook であるにせよ、Big Data をハンドリングするエキスパートたちにとって、大きなチャレンジがあったことを、私たちは認識している。さらに言えば、彼らは 6カ月で、その全てを構築したのだ。

Facebook’s Ryan Mack shares quite a bit of Timeline’s own implementation story in his excellent article: Building Timeline: Scaling up to hold your life story. Five big takeaways from the article are:

Facebook の Ryan Mack は、自身の素晴らしい記事である「Building Timeline: Scaling up to hold your life story」において、Timeline の実装ストーリーにおける、かなりの部分をシェアしている。その中から、5つのポイントを以下に紹介する：

Leverage infrastructure rather than build something new.

You might expect that they would pioneer a new infrastructure for Timeline, but given the short schedule, they decided to go with proven technologies inside Facebook: MySQL, Multifeed (a custom distributed system which takes the tens of thousands of updates from friends and picks the most relevant), Thrift, Memcached, Operations. The last point about the operations infrastructure is a huge win for any team. All that just works. They can concentrate on solving the problem and skip the whole tooling dance, which is why new products can be generated amazingly fast inside a "big company", if the infrastructure is done right.

新しい何かを構築するより、既存のインフラを活用する.

Timeline のパイオニアとして、彼らは新しいインフラストラクチャを構築したと思うだろうが、短いスケジュールという条件のもと、Facebook で検証されているテクノロジーを用いることに決めた。つまり、MySQL および、Multifeed（フレンドからの無数のアップデートを受信し、最も適切なものを選択するカスタムな分散システム）、Thrift、Memcached、Operationsである。最後に指摘した Operation インフラストラクチャとは、あらゆるチームに蓄積された、莫大な成功体験のことである。ただし、それらすべては、単に機能するだけである。彼らは、対象となる問題の解決に全力を注ぎ、また、ツールへの取り組みというステージを省略できた。つまり、インフラストラクチャさえ正確に機能すれば、それらの新しいプロダクトが「大企業」の中でも、きわめて迅速に作成されることの証明が、そこにある。

Denormalize. Format data in the way you need to use

Denormalzation, creating special purpose objects instead of distributed rows that must be joined, minimizes random IO by reducing the number of trips to the database. Caching can often get around the need for denormalization, but given the amount of timeline data and how much of it is cold, that is it will rarely be viewed, caching everything isn’t a good design.
Timeline decides the order to display data by calculating a rank based on metadata. The denormalization process brought all that metadata together in a format that meant ranking could be done in a few IOs and streamed efficiently from the database using a primary key range query
Timeline is like a datamart in a data warehouse. Data must be slurped up from dozens of different systems, cleaned, merged, and reformatted into a new canonical format. Facebook of course did this in a Facebook-like way. They created a custom data conversion language, they deployed hundreds of MySQL servers to extract the data out of "legacy" systems as fast as possible, they deployed flash storage to speed up joins, they created a parallelizing query proxy, and they standardized on the Multifeed data format for future flexibility.

その使用法に合わせて、データのフォーマットを非正規化する.

Denormalzation（非正規化）は、Join されるべき分散された Row に代えて、特殊な目的を持つオブジェクトを作成し、データベースとのラウンド･トリップの回数を減らすことで、ランダム IO を最小にする。非正規化が必要とされるところに、高い頻度でキャッシュが配置されるが、めったに参照されることのない、Cold 状態に置かれた全体的な Timeline データの、すべてをキャッシュするのは良いデザインではない。
Timeline は、メタ･データに基づくランクの計算により、データ表示の順序を決定する。この非正規化プロセスは、IO の回数を減らしたタンキングのためのフォーマットの中に、すべてのメタデータを集める。そして、主キーのレンジでクエリーを使用し、データベースからのストリーミングを効率よく処理する。
Timeline は、データ･ウエアハウスにおける datamart のようなものである。データは、多種多様なシステムから掻き集められ、クリーニングとマージを施され、新しい規準的なフォーマットの中で再フォーマットされなくてはならない。Facebook は、もちろん Facebook らしい方式で、それを処理している。彼らは、カスタムなデータ･コンバージョン言語を作成した。続いて、可能な限り高速に、レガシー･ステムからデータを抽出する、何百という MySQL サーバーを実装した。そして、結合を高速化するために Flash ストレージを配置した。さらに、パラレル･クエリー･プロキシーを作成した。最終的に、彼らは、将来のフレキシビリティのために、Multifeed データ･フォーマットを標準化した。

Keep different types of caches.

hort term cache. A timeline of recent activity is frequently invalidated because it is changing all the time as you perform actions through your life. This cache is an in RAM row cache inside InnoDB that uses the Flashcache kernel driver to expand the OS cache onto a flash device.
Long term cache. A query cache is kept in memcached. The results of large queries, like the ranking of all your activities in 2010, can be efficiently cached since they will rarely be invalidated.

複数タイプのキャッシュを用意する.

Short term cache. 最近のアクティビティにおける Timeline が、ほとんど無意味なのは、ユーザーのアクションにより、常に変化し続けているからである。 InnoDB 内の RAM Row へのキャッシュは、Flash デバイス上の OS キャッシュを拡張するために、Flashcache カーネル･ドライバを使用する。
Long term cache. クエリー･キャッシュは、memcached 内に保持される。たとえば、2010年における全アクティビティをランキングするような、大規模なクエリーの結果は、それらが無効になることは稀なため、効率よくキャッシュできる。

Run operations locally.

The Timeline Aggregator (geographically clustering nearby check-ins, ranking status updates, etc) runs on each database so it can max out the disks. Only data that needs to be displayed is sent over the network.

オペレーションはローカルで実行する.

Timeline Aggregator（チェックインした場所に、地理的に近いクラスタリングや、ステータス･アップデートのランキングなど）は、それぞれのデータベース上で実行され、そのディスクを極限まで使用できるようにしている。そして、表示する必要のあるデータだけが、ネットワーク上で送信される。

Parallelize development.

The short 6 month development time was partly a product of the quality infrastructure, but of also running significant development activities in parallel. The development team was split into design, front-end engineering, infrastructure engineering, and data migrations. In parallel they built: UI prototypes on a test backend, production UI on a simulated backend, the scalable backend, the denormalization framework, the data warehouse, and simulated load testing.

並列化された開発.

この、6ヶ月という短い開発期間は、インフラストラクチャ･プロダクトにおける品質によるものであるが、大量の開発アクティビティも、平行して実施されていた。そして、開発チームは、デザイン／フロントエンド･エンジニアリング／インフラストラクチャ･エンジニアリング／データ･マイグレーションに分割されていた。さらに、並列で構築されたものには、テスト･バックエンドの UI プロトタイプ／シミュレートされたバックエンド上のプロダクション UI／非正規化フレームワーク／データ･ウエアハウス／負荷テスト･シミュレーションなどがある。

ーーーーー

この Ryan Mack さんが書いた Timeline の記事については、先月にも「Facebook が Timeline をデザインしていく発想は、いったい何処から湧き上がってくるのか？ – Gigaom」を訳していますが、どちらも絶賛ですね。そして感心するのは、Facebook の柔軟な発想とテクノロジーなのですが、ユーザーと向き合うサービスから基盤であるデータセンターまでの全スタックを、すべて自ら設計して構築していく企業だからこそ、得られるものなのだろうと捉えています。訳していて、とても楽しかったですーーー