(cache) 【これはすごい】Twitter検索を3倍高速化した記事の翻訳

2011-04-20

【これはすごい】Twitter検索を3倍高速化した記事の翻訳

これはすごい！というわけでTwitter検索を3倍高速化したという記事を翻訳してみました。

Twitter Engineering: Twitter Search is Now 3x Faster

2010年春。Twitterの検索チームは、我々の増え続けるトラフィックに対応し、エンドユーザにとっての遅延を減らし、我々のサービスの可用性を向上させ、新しい検索の機能を素早く開発できるようにするため、検索エンジンを書きなおす作業を始めた。

その努力の一部として、我々は新しいリアルタイム検索をリリースし、検索のバックエンドをMySQLからLuceneのリアルタイム版に変更した。そして先週、我々はRuby-on-Railsに取って代わるフロントエンドをローンチした。我々がBlenderと呼ぶJavaサーバーである。我々はこの変更によって検索のレイテンシが3分の1になり、検索機能の開発を促進できるようになったことをアナウンスできて嬉しく思う。

パフォーマンス向上について

Twitter検索は世界で最もトラフィックの多い検索エンジンの一つであり、1日に10億クエリを処理している。我々がBlenderをデプロイする1週間前に日本の津波(#tsunami)の影響でクエリが急増し、それに伴い検索のレイテンシが増大した。Blenderのローンチのあと、95%のクエリはレイテンシが800msから250msに、つまり3分の1に削減され、フロントエンドサーバのCPU使用率は半分になった。今や1台のサーバは以前の10倍ものリクエストを受け持つ余裕がある。これは同じだけのクエリをより少数のサーバで処理できることを意味しており、フロントエンドサーバのコストを減らすことができる。

Twitterの改善後の検索アーキテクチャ

パフォーマンス向上の理由を理解するためには、まず以前のRuby-on-Railsのフロントエンドサーバがいかに非効率であったかを理解する必要がある。フロントエンドはシングルスレッドのrailsワーカープロセスを固定された数だけ立ち上げており、それぞれの役割が以下のように決まっている。

クエリの解析
インデックスサーバに同期的にクエリを投げる
結果を集約して表示する

かなり以前から同期的なリクエストの処理がCPU効率を悪くしていることは分かっていた。また時が経つにつれて、Rubyのコードベースに重大な欠陥が生じて、検索機能を追加したり信頼性を向上させたりすることが難しくなっていた。

Blenderではこれらの問題に以下のように対処している。

完全に非同期の集約サービスを作り上げた。ネットワークIO待ちになるスレッドは一つもない。
バックエンドサーバから色々な情報を集約する：例えばリアルタイム検索、TopTweet、地理情報インデックスなどである。
サービス間の依存関係をエレガントに扱う。ワークフローは自動的にバックエンドシステムの依存関係を解決する。

以下の図は、新しいTwitter検索エンジンのアーキテクチャを現している。WebやAPI、Twitter内部のクライアントから送られたクエリはハードウェアロードバランサを通してBlenderに発行される。Blenderはクエリを解析してバックエンドシステムに割り当てるが、そのときワークフローはサービス間の依存関係をうまく処理する。最後に、サービスからの結果はマージされて適切な言語でクライアントに表示される。

Blender概要

BlenderはNettyを使って構築されたThriftとHTTPのサービスである。NettyとはJavaで書かれた高スケーラブルなNIO（Network IO？）クライアントサーバーライブラリであり、Nettyによって様々なプロトコルのサーバーやクライアントを素早く簡単に開発できるようになる。我々は他の様々な競合、例えばMiraやJettyの中からNettyを選んだ。なぜならNettyはクリーンなAPIとよいドキュメントを持っていたし、より重要なことにTwitterの他のプロジェクトがこのフレームワークを使っていたからだ。NettyをThriftと組み合わせるために、我々は簡単なThriftのコーデックを書いた。ソケットから読み込むときにはNettyのチャンネルバッファから来るThriftのリクエストをデコードし、ソケットに書きこむときにはThriftのレスポンスにエンコードできるようにした。

Nettyはチャンネルと呼ばれる重要な抽象化を提供する。チャンネルはネットワークソケットへの接続をカプセル化して、I/O操作を実行するインターフェースを提供する。I/O操作とは例えばread, write, connect, bindなどである。全てのチャンネルI/O操作は本来的に非同期である。これはすなわち全てのI/O呼び出しはすぐにChannelFutureインスタンスを返すということである。ChannelFutureインスタンスはリクエストされたI/O操作が成功したか、失敗したか、キャンセルされたかを後から通知する。

Nettyサーバが新しい接続を受け取ったとき、それを処理するための新しいチャンネルパイプラインを生成する。チャンネルパイプラインとはただのチャンネルハンドラのシーケンスで、そのリクエストを処理するために必要なビジネスロジックを実装する。次のセクションでは、我々はBlenderがどのようにこれらのパイプラインをクエリ処理ワークフローにマッピングするかを示す。

ワークフローのフレームワーク

Blenderでは、ワークフローとは入ってくるリクエストを処理するために必要な、依存関係のあるバックエンドシステムの集合を指す。Blenderは自動的にサービス間の依存関係を解決する。例えば、もしサービスAがサービスBに依存していれば、まずAが先にクエリを処理して結果はBに渡される。ワークフローは有効非循環グラフ（DAG;directed acyclic graphs)によって表すと便利である。下記サンプルをご覧頂きたい。

上記サンプルのワークフローでは、6つのサービス{s1,s2,s3,s4,s5,s6}が依存関係を持っている。s3からs1への有向エッジは、s1がs3の結果を必要としているためs3はs1の前に呼ばれなければならないことを意味している。このようなワークフローのもとで、BlenderフレームワークはDAG上でのトポロジカルソートを実行してサービスの実行順序を決める。上記のワークフローにおける実行順序は{(s3, s4), (s1, s5, s6), (s2)}となる。これは最初の実行でs3とs4が並列に呼べることを意味しており、そのレスポンスが返ってきたら次の実行でs1,s5,s6が並列に呼ばれ、最後にs2が呼ばれる。

一度Blenderがワークフローの実行順序を決定したら、Nettyのパイプラインにマッピングされる。このパイプラインはリクエストが処理のために渡される必要のあるハンドラのシーケンスである。

リクエストを多重化する

ワークフローはBlenderのNettyパイプラインにマッピングされるため、我々は入ってくるクライアントリクエストを適切なパイプラインに割り当てる必要がある。このために、我々はクライアントリクエストを多重化し、パイプラインに割り当てるプロキシレイヤを開発した。これは次のように動作する：

リモートのThriftクライアントがBlenderに恒久的な接続を開始したとき、プロキシレイヤはローカルのクライアントをローカルのワークフローサーバーに割り当てるマップを作成する。全てのローカルのワークフローサーバーはBlenderのJVMプロセスに含まれており、Blenderのプロセスが開始するときに実体化される。
リクエストがソケットに到着したときは、プロキシレイヤがそれを読み込み、どのワークフローが必要とされているかを見つけ、それを適切なワークフローサーバーに割り振る。
同様に、ローカルワークフローサーバーからレスポンスが到着したときはプロキシがそれを読み込みリモートクライアントにレスポンスを書き戻す。

我々はNettyのイベントドリブンモデルを使って上記のタスクを全て非同期に実現しているため、I/Oにおいてスレッド待ちが発生することはないようになっている。

バックエンドのリクエストを配布する

ワークフローのパイプラインにクエリが到着したら、サービスハンドラのシーケンスにワークフローで定義されたように渡す。サービスハンドラはそのクエリに対する適切なバックエンドリクエストを構築し、リモートサーバーに投げる。例えばリアルタイム検索サービスはリアルタイム検索のリクエストを構築し、それを1つまたは複数のリアルタイム検索インデックスに非同期に発行する。我々は最近オープンソースになったtwitter commonsライブラリを使ってコネクションプーリング・ロードバランシング・停止ホスト検出を提供する。

クエリを処理するI/Oスレッドは全てのバックエンドリクエストが送信されたときに開放される。タイマースレッドが数ミリ秒おきにどのリモートサーバーからバックエンドのレスポンスが返されたかを監視しており、そのリクエストが成功したか、失敗したか、タイムアウトしたかの状態を表すフラグをセットする。我々はこのタイプのデータを管理するために、検索クエリのライフタイム全体にわたり1つのオブジェクトを保持している。

成功したレスポンスは集約されてワークフローのパイプライン中の次のサービスハンドラ集合に渡される。最初のサービスハンドラ集合から全てのレスポンスが到着したとき、次のサービスへの非同期なリクエストが生成される。この処理はワークフローが完了するか停止するまで繰り返される。

見てわかるように、ワークフローの実行を通してI/Oによるスレッドがビジーウェイトになることはない。これにより我々のBlenderサーバは効率的にCPUを使うことができるようになり、たくさんのリクエストを並列に処理することができる。我々はまたほとんどのバックエンドサービスへのリクエストを並列に実行できるため、レイテンシを減らすことができる。

Blenderのデプロイと今後の課題

我々のシステムにBlenderを導入して高いクオリティのサービスを行えるよう保証するため、我々は以前のRuby-on-Railsによるフロントエンドサーバを使ってThriftリクエストを我々のBlenderサーバに中継するプロキシサーバを立てている。以前のフロントエンドサーバをプロキシとして使うことにより、内部の技術を大きく変更している間も一貫したユーザ体験を提供できている。我々の計画の次の段階は、検索スタックからRuby-on-Railsを完全に廃止してユーザが直接Blenderにアクセスできるようにすることで、さらなるレイテンシの削減を実現することである。

by @twittersearch

謝辞

Blenderに関して次のTwitterエンジニアが働いている: Abhi Khune, Aneesh Sharma, Brian Larson, Frost Li, Gilad Mishne, Krishna Gade, Michael Busch, Mike Hayes, Patrick Lok, Raghavendra Prabhu, Sam Luckenbill, Tian Wang, Yi Zhuang, Zhenghua Li.

訳者あとがき

Facebookの記事に続き、Twitterの記事を翻訳してみました。

検索フロントエンドを非同期にすることでレイテンシを削減するという試みは色々な示唆を与えてくれていると思います。「ワークフローをDAGで表してトポロジカルソートで実行順を決めつつ並列化で実行効率を上げる」というやり方は実はHadoopなどのバッチシステムでも全く同じ考え方ができて、Asakusaの発表でも聞いたことがあります。

翻訳については自分の理解不足もありカタカナ語が多くなってしまって申し訳ないと思います。素晴らしい内容なので、これを気に英語の原文を読む人が増えてくれれば本望です。翻訳をすることで一字一句を読む必要があるので、自分自身も英語と技術の勉強になっています。良い記事を見つけたら翻訳することは、これからも続けていきたいと思います。