Agile Cat — in the cloud

Google’s Colossus Makes Search Real-time by Dumping MapReduce
Saturday, September 11, 2010 at 5:50AM
http://highscalability.com/blog/2010/9/11/googles-colossus-makes-search-real-time-by-dumping-mapreduce.html

As the Kings of scaling, when Google changes its search infrastructure over to do something completely different, it’s news. In Google search index splits with MapReduce, an exclusive interview by Cade Metz with Eisar Lipkovitz, a senior director of engineering at Google, we learn a bit more of the secret scaling sauce behind Google Instant, Google’s new faster, real-time search system.

King of Scaling としての Google が、これまでとは全く異なることを行うために検索インフラストラクチャを変更すれば、それはニュースになる。 Google 検索インデックスは MapReduce により分散されるという、Google  エンジニアリング部門のシニア･ディレクタである Eisar Lipkovitz に対する、Cade Metz による独占インタビュー を読み解いていく。 そして、Google が提供する最速リアルタイム検索システムである、Google Instant の背景となる秘密のスケーリングについて、もう少し学んでいく。

The challenge for Google has been how to support a real-time world when the core of their search technology, the famous MapReduce, is batch oriented. Simple, they got rid of MapReduce. At least they got rid of MapReduce as the backbone for calculating search indexes. MapReduce still excels as a general query mechanism against masses of data, but real-time search requires a very specialized tool, and Google built one. Internally the successor to Google’s famed Google File System, was code named Colossus.

これまでの Google におけるチャレンジとは、コアとなる検索テクノロジーが、バッチ指向として有名な MapReduce であるのに、どのようにしてリアルタイムな世界をサポートすべきかという点にあった。 そしてシンプルに、Google は MapReduce を取り除いた。 少なくとも、検索インデックス計算というバックボーンとして  の MapReduce を取り除かれている。依然として、MapReduce は大量データに対する汎用クエリー･メカニズムとしては卓越した存在であるが、リアルタイム検索には完全に特化されたツールが必要であり、それを Google は構築した。その、有名な Google File System の後継者には、内部的に Colossus（巨像）というコードネームが付けられている。

注記：巨象ではなく巨像

Details are slowly coming out about their new goals and approach:

その新しいゴールとアプローチについては、ゆっくりとだが詳細が発表され始めている：

• Goal is to update the search index continuously, within seconds of content changing, without rebuilding the entire index from scratch using MapReduce.
  
• The new system is a “database-driven, Big Table–variety indexing system.”
  
• When a page is crawled, changes are made incrementally to the web map stored in BigTable, using something like database triggers.
  
• A compute framework executes code on top of BigTable.

• そのゴールは、コンテントが更新される数秒の間に、連続的に検索インデックスをアップデートすることだが、MapReduce でスクラッチからインデック化することではない。
  
• この新しいシステムは、”database-driven, Big Table–variety indexing system” である。
  
• 何らかのページがクロールされるとき、データベース･トリガーのようなものを用いて、BigTable にストされた Web マップに対して、そこでの変更がインクリメントされる。
• 計算のためのフレームワークは、BigTable のトップで’実行される。

The use of triggers is interesting because triggers are largely ignored in production systems. In a relational database triggers are integrity checks that are executed on a record every time a record is written. The idea is that if the data is checked for problems before it is written into the database, then your data will always be correct and the database can be a pure source of validated facts. For example, an account balance could be checked for a negative number. If the balance was negative then the write would fail, the transaction aborted, and the database would maintain a correct state.

トリガーを用いるという考え方が興味深いのは、大半のプロダクション･システムにおいて、それは無視される存在だからである。 リレーショナル･データベースにおけるトリガーとは、レコードが Write されるごとに、レコード上で実行される完全のチェックのことである。 この考え方とは、データベースへの書き込みの前に、データにおける問題がチェックされるなら、そのデータは常に正しくなり、また、そのデータベースは妥当性を検査された事実の、純粋なソースになり得るというものだ。 たとえば、アカウントのバランスにおいて、負数の存在をチェックできる。 もし、そのバランスが負であれば、書き込みは失敗し、トランザクションは中断され、データベースは正しい状態を維持するだろう。

In practice there are many problems with triggers:

実際のところ、トリガーに関わる数多くの問題がある：

• Destroys performance. Since triggers happen on every write they slow down the write path to the extent that database performance is often killed. Triggers also take record locks which makes contention even worse.
  
• Checking is distributed. Not all integrity checks can be made from data inside the database so checks that are database oriented are put in the triggers and checks, that say access a 3rd party system, are kept in application code. So now we have checks in multiple places, which leads to the update anomalies in code that ironically, relational databases are meant to prevent in data.
  
• Checking logic is duplicated. Checking in the database is often too late. A user needs to know immediately when they are doing something wrong, they can’t wait until a transaction is committed to the database. So what ends up happening is checking code is duplicated, which again leads to update anomalies.
  
• Not scalable. The database CPU becomes dedicated to running triggers instead of “real” database operations, which slows down the entire database.
  
• Application logic moves into triggers. Application code tends to move into triggers over time since triggers happen on writes (changes), in a single common place, they are a very natural place to do all the things that need to be done to data. For example, it’s common to emit events about data changes and perform other change sensitive operations. It’s easy to imagine building secondary indexes from triggers and synchronizing to backup systems and other 3rd party systems. This makes the performance problems even worse. Instead of application code being executed in parallel on horizontally scalable nodes, it’s all centralized on the database server and the database becomes the bottleneck.

• Destroys performance.トリガーはすべての書き込みおいて発生するため、データベース性能が頻繁に損なわれるという範囲において、その書き込み経路の速度を遅くする。 さらに、トリガーはレコードをロックするため、この論点を更に悪化させる。
  
• Checking is distributed. すべての完全性に関するチェックが、データベース内のデータに基づいて、実現されるわけではない。したがって、データベース指向のチェックはトリガー内に取り込まれてチャックされるが、アプリケーション･コード内に保持されるサード･パーティ･システムにアクセスすることになる。そのため、多数の場所にチェックを持ることになるが、それは皮肉にも、リレーショナル･データベースが意図的に許可していない、コードにおけるアップデートの不整合へと導くことになる。
  
• Checking logic is duplicated. 大半のケースにおいて、データベース内でのチェックは遅すぎる。それらが、問題を引き起こす何かを行っているとき、ユーザーは直ちに把握する必要がある。こうした問題は、トランザクションがデータベースにコミットされるのを、待つことができない。 したがって、複写されたコードを調べることになるが、前述のとおり、アップデートの不整合へと導いてしまう。
  
• Not scalable. データベース CPU は、「本来」データベース操作ではなく、トリガーに占有されるため、データベース全体の速度が劣化する。
  
• Application logic moves into triggers. 紆余曲折の後にアプリケーション･コードが、トリガー内部の共通の位置に取り込まれる傾向にあるのは、そこがデータに対して施すべき処理を、トリガーから実行もしくは記述（変更）するのに都合の良い場所だからだ。 たとえば、データの変更に関するイベントを発行し、それらの変更に対応するオペレーションを実行することなどが、一般的な用法である。トリガーに基づいて 2番目のインデックスを構築し、バックアップ･システムとサードパーティ･システムを同期指せる方式などが、容易に思いつくはずだ。それにより、パーフォーマンス的な問題が、さらに悪化していく。 ホリゾンタルにスケーリングされたノード上で、アプリケーションコードを並列に実行させる代わりに、データベース･サーバー上にセンタライズされる方式であるため、そのデータベースがボトルネックになる。

So, triggers tend not to be used in OLTP scenarios. Applications contain the same logic and it’s up to release policies and testing to make sure nothing falls through the cracks.

したがって、OLTP のシナリオでは、トリガーは使用されない傾向にある。 複数のアプリケーションが同じロジックを含むが、それらはリリース･ポリシーに依存するものになる。また、想定外の問題を起こさないようにするための、厄介なテストも必要になる。

This isn’t to say you don’t want to put logic in triggers, you do. Triggers are ideal in an event oriented world because the database is the one central place where changes are recorded. The key is to make triggers efficient.

これでは、トリガーにロジックを取り込まないと思うはずだし、現実に誰もが、それを行わない。 つまり、トリガーがイベント指向の世界で理想的になるのは、データベースが変更が記録される、センタライズされた場所にデータベースが置かれる場合となる。 そこでは、キーによりトリガーが効率化される。

It sounds like Google may have made a specialized database where triggers are efficient by design. We know hundreds of thousands of pages are being crawled simultaneously. When the pages are written to the database that’s the perfect opportunity perform calculations and updates. The compute framework would make it efficient to perform operations in parallel on pages as they come in so that processing isn’t completely centralized on each node.

そのためか、効果的なトリガーのためにデザインされた特別なデータベースを、Google が開発したのかとも思える。 私たちが知っているのは、何 10万ページものデータが、同時にクローリングされていることである。 ページがデータベースに書き込まれるときが、計算と更新を実行する完ぺきなタイミングとなる。 このコンピューティング･フレームワークでは、それらのページが取る込まれるときにページ上での並列処理を効率よく実現し、それぞれのノード上に処理がセンタライズされないようにするのだろう。

One can imagine that the in-memory data structures that existed on the MapReduce nodes have been extracted in some form and reified within BigTable. What we have is a sort of Internet DOM, analogous to the browser DOMs that have made it possible to have such incredibly powerful browser UIs, but for the web. I imagine programming the web for Google has become something like programming a browser DOM. I could be completely wrong of course, but I explored this idea a while ago in All the world is a DOM.

MapReduce ノード上に存在するインメモリ･データ構造が、いくつかの形式で抽出され、また、BigTable 内で具体化されると、想像する人もいるだろう。 私たち、ブラウザの DOM に類似した、ある種の Internet DOM を持っている。つまり、ブラウザ DOM は、信じられないほどにパワフルな ブラウザ UI を持っているが、それは Web ではない。 私は、 Google における Web プログラムが、ブラウザ DOM をプログラムに似たものになっていると想像する。もちろん、それはまったくの見当違いかも知れないが、この考え方については All the world is a DOM において、以前に探求している。

There’s an interesting quote at the end of the article: “We’re in business of making searches useful, we’re not in the business of selling infrastructure.”

この記事の最後には、『 私たちのビジネスは検索を有益なものにすることであり、そのインフラストラクチャを販売することではない 』という、興味深い引用が記されている。

These could actually be the same goal. It’s a bit silly to have everyone in the world crawl the same pages and build up yet another representation of the Web. Imagine if the Web was represented by an Internet DOM that you could program, that you could write to, and that you could add code to just like Javascript is added to the browser DOM. Insert a node into the Internet DOM, like a div in an HTML page, and it would just show up on the Web.

しかし、現実においては、それらのゴールが同じものにもなり得る。 世界中の誰もが、同じページをクローリングして、Web に別の表現を展開することは、少し愚かなことである。あなたがプログラムできる Internet DOM により、Web が表現されると想像して欲しい。 もちろん、そこでは書き込みも可能であり、Browser DOM と同様に、Javascript などのコードも加えられる。 HTML ページの div のように、Internet DOM にノードをインサートすれば、それが Web 上に、ただちに表示されるだろう。

This Internet DOM could be shared and all that backbone bandwidth and web site CPU reclaimed for something more useful. Google is pretty open, but they may not be that open.

この Internet DOM を共有することは可能であり、バックボーンの帯域幅と Web サイトの CPU は、より有益なものとして再構成される。 Google は、かなりオープンであるが、オープンではないのかもしれない。

ーーーーー

ひさびさに、Google の底力を見せつけられました。 これだけのものを、ポンと実装から提供してしまうのって、やはりスゴイことですよね。 特許でも何でも取ってしまって構いませんので、Apache だけには、優しくしてほしいです。 ーーー A.C.

ーーーーー

＜関連＞
Google は 1000万台のサーバーを目指す？ (Spaneer 関連)
年間で 30億円以上になる Google サーチの電気料金は、Instant の登場で跳ね上がるのか？
新検索エンジン「Google Instant」、入力中に検索結果を逐次表示
Google Instant, YouTube Instant, そして今度はGoogle Maps Instantだっ！
Google Instant：「真の可能性」と他への影響
グーグル、「Google Instant」検索をローンチ
Google、入力予測で検索結果を表示する「Google Instant」を発表