[編集者より: 本記事は Indeed で行われた初の Indeed テックトークの姉妹編第一弾です。 スライドと動画はこちらよりご覧いただけます。]
Indeed.com は、米国で 2004 年にローンチしました。現在 Indeed は 50 か国以上で展開しており、 1 億人のユニークビジター (UV) （追記:2015年10月現在では毎月1.8億人のUV）が毎月 30 億件の求人検索を行っています。
世界中の他のどの求人検索エンジンよりも多いトラフィック量を Indeed は誇ります。
もし最初からこの規模に対応しようとしていたなら、ローンチは叶わなかったでしょう。
なぜなら、現在のトラフィックレベルに対応できる求人検索システムを構築するには、時間もかかりますし、それに必要な知識も当時の私たちは持ち合わせていませんでした。
同様に、成長にあわせてシステムを進化させてこなければ、こうして今、ここまでの発展を遂げていなかったでしょう。1億 UV を達成するまでの道のりには、 8 年の歳月を要しました。
私たちは、速くシンプルで、網羅性と関連性の高いプロダクトの構築を信条としています。ソリューションを構築する際にも、速くてシンプルであることを心に留めています。新しい機能をユーザーへ提供し、素早く改善を繰り返すことで、プロダクトを向上し続けているのです。
この記事では毎月何十億もの検索に耐えうるだけのシステム拡張を続けてきた中で、私たちがおこなってきた改善の歴史をお伝えしたいと思います。
2004年:最もシンプルなソリューション
2004 年に実装された求人検索の最初のバージョンを生み出した際、私たちは Lucene に着目しました。
Lucene は、インデックス化を行い、検索を可能にする Java をベースにしたオープンソースプロジェクトです。ドキュメント (Indeed の場合は求人情報) のインデックスを作成すると、 Lucene は求人クエリをマッチするドキュメント ID のセットに効率よく、素早く変換してくれます。 Indeed の検索 Web アプリは、 Lucene のインデックスを使用して、ユーザーの検索にマッチするドキュメント ID を取得していました。
しかし、表示用に対応する求人情報データも必要でした。これらの ID を、表示可能な求人データに変換することを、私たちは「ドキュメント・サービング」と呼んでいます。
ドキュメント・サービングで重要なことは、網羅性と速さです。
私たちは常に世界中からの求人情報をアグリゲーションしており、いつでもその全てのデータを提供可能にしておく必要があります。
新着の求人と更新情報を出来るだけすぐにサイトで閲覧できるようにしなければならないので、求人情報のドキュメント・サービングも非常に高速である必要があります。
検索結果には 10 件の求人情報が表示されています。各結果には、役職、会社名、求人情報が掲載されてからの経過日数、職務内容にもとづいたスニペットなどの属性を表示します。
図 1: ドキュメントの属性を示した検索結果の例
最初のバージョンでは、 strored fields を使用して、 Lucene インデックス内にジョブ・ドキュメントデータを保存していました。 Lucene で広く使われている機能である stored fields はインデックスを構築中に、インデックスにドキュメントデータを保持することを可能にします。
図 2 は、この最初のバージョンにおけるデータフローを表しています。
このインデックスビルダーは、数分ごとに実行され、データベースから求人情報を読み込み、 Lucene インデックスを構築するものでした。
このインデックスは、それから rsync を使用して Web サーバーへコピーされ、検索 Web アプリがドキュメントを検索し提供する際に使用されました。
図２： stored fields からドキュメントを提供
最初の一か月、私たちは 200 万件の求人をアグリゲーションしました。
一番忙しい日でも、 16 万件のジョブ・ドキュメント、最大で 1 秒間に 7 件のドキュメントを提供していました。
システムはこれで上手く行っており、検索も素早く、求人検索結果も最新でした。
2005 年: サイズは大事
それから一年後の 2005 年の11 月、私たちは、毎月ほぼ 400 万件の新着求人をアグリゲートしていました。一日あたりに提供するドキュメントは 500 万件にのぼり、ピーク時には 1 秒間に 100 件になりました。
検索可能な求人情報の数は、ほぼ倍近くになり、これにより、インデックスは 6 GB 〜 7 GB へと増加しました。 stored fields がこのファイルサイズの大部分を占めていました。
Lucene は、ディスクキャッシュに全てのインデックスがおさまれば、非常に高速です。しかし私たちの本番環境のサーバーは、 4 GBの RAM しか持ち合わせていませんでした。検索を実行するために、サーバーはディスクからデータをページインする必要があったので、求人検索のパフォーマンス低下を引き起こしてしまいました。
インデックスはどの求人情報を検索結果ページに表示するか決定するので、古くなった求人情報や、元の投稿先から削除された求人情報は残しておきたくありません。
検索結果ページには、既に掲載されていない求人情報でも、ブックマークや email から、ユーザーがその求人の詳細ページに戻ってくるかもしれません。
なので、インデックスに求人情報がない場合でも、そのまま提供可能にしておかなければならないのです。
Lucene のインデックスには永続的にすべての求人情報を保存できないため、新たなアプローチを考える必要がありました。
進化の始まり
まず、求職者のユーザーエクスペリエンスにおいて重要な、検索のパフォーマンスを最適化するために、アーキテクチャを改良する必要がありました。
既に求人データのプライマリストレージとなっていた MySQL データベースから、直接求人情報データを提供することを決めました。 MySQL はアグレッシブ・キャッシングなどのオプションを提供してくれ、主要なジョブ・データテーブルは、job ID にプライマリキーのインデックスを既にもっていたため、高速な参照を可能にしていました。
また、データベースは、別の、さらにパワフルなマシンでホストされていました。検索Webアプリをホストするマシン上に全データを利用可能な状態で保存するのではなく、データベースに直接クエリをかけることで、それらの Web サーバー上でリソースの使用を減らすことが可能になりました。
データベースから直接求人情報を取得することで、stored field を使うのをやめることが可能になり、 Lucene インデックスのサイズが大幅に削減しました。
私たちはこれまでと同じ求人情報をインデックス化していましたし、検索 Web アプリも検索にインデックスを使用し続けていました。異なる点は、 Lucene は検索に一致する job ID のみを返すようになり、検索 Web アプリは、データベースから、それらの求人情報のデータを取得していた点です。(図 3 を参照)。この変更は成功しました。インデックスはより小さくなり、ドキュメントの参照も速くなり、求人検索のパフォーマンスも向上しました。
図 3: MySQL データベースからドキュメントを提供
2006: 競合の過多
私たちは一年以上、直接データベースへアクセスするアプローチを採用していました。 2006 年の 11 月には、毎月 520 万件の新着求人情報をアグリゲートしていました。毎日最大で 2100 万のドキュメントを提供しており、ピーク時には 1 秒間で 500 件のドキュメントに上りました。前年と比べて５倍の増加です。求人検索にかかる平均時間はそれでもまだ速いものでしたが、一日のある時間には、パフォーマンスが悪くなることに気づきました。
このスピード低下の原因は、 MyISAM ストレージエンジンを使用した主要なジョブ・テーブルで書き込みの競合が起きたためでした。 MyISAM はテーブル単位でロックするので、アグリゲーション・プロセスからの書き込みが検索からの読み込みをブロックしていました。反対に、検索サイドでの読み込みが、それらの書き込みをブロックしていました。ユーザーの検索実行と、データベースへの新規の求人データ取得が、互いに邪魔し合ってしまっていたのです。
一つの選択肢としては、 MySQL の InnoDB ストレージエンジンに切り替えることでした。これは行単位でのロックを行うものでしたが、ハードウェアのコスト増加や広範囲に渡るコード変更という意味で煩雑な変更がマイグレーションに必要とされました。結果的にマイグレーションは行いましたが、私たちはより早くデプロイできるソリューションを必要としていました。
もう一つ私たちが検討したソリューションは、プライマリのデータベースを複製し、この複製からジョブのドキュメントを提供することでした。このアプローチは、読み込みの負荷が大きいシステムに対してはうまくいくものでした。けれど、これを利用するには、発生する書き込みが多すぎました。
MySQL の複製は単一のスレッドで実行されます。そのため、その単一の書き込みスレッドからの複製のストリームの書き込みを、検索 Web アプリからの大量の読み込みがロックアウトしてしまう際に、複製はマスターより遅れてしまうのです。
もし私たちの検索 Web アプリが複製から読み込んでおり、複製が遅れた場合、インデックスは、まだ複製の中にないジョブに対応した Job IDを Web アプリへ返してしまうかもしれないのです。
データべ―スが無理なら、キャッシュだ！
これらの問題を改善するため、私たちは古典的なアプローチをとりました。アプリケーション層でのキャッシュです。オープンソースであり高性能な、メモリ内でオブジェクトをキャッシュしてくれる Memcached を使用しました。
同時に、検索 Web アプリの他の要素も進化させていました。全て担っていた単一の Web アプリからサービス指向アーキテクチャへの移行を始めたのです。
検索 Web アプリから独立させた最初のサービスの一つに、 docservice がありました。これはドキュメント・サービングを扱うものでした。検索 Web アプリはジョブのドキュメントデータ用に docserviceへリクエストを送信します。
図4に示されているように、複数の検索 Web アプリのインスタンスは単一の docservice で対応可能でした。最初のバージョンでは、検索 Web アプリは HTTP で docservice と通信していました。その後、その通信方法の実装を変更し、 boxcar と呼ばれる効率の良い、自社製のサービスインフラを使用しました。
図4: memcache からドキュメントを提供
ドキュメントのリクエストを提供するために、 docservice はまず memcached 内部を確認し、求人情報がキャッシュされていない場合のみ、データベースにクエリをかけます。
memcached の探索時間はおよそ1～5 ms で、データベースの読み込みには、ロックの過多の場合によっては10ms かそれ以上を必要としました。
キャッシュのヒット率を最大化し、データベースアクセスを避けるために、各 docservice は新規の求人データを監視し、それらのジョブをキャッシュ内に読み込むバックグラウンドのスレッドを持っていました。
空の memcache を持つ新しい docservice がデータベースに過剰なリクエストを送るのを防ぐため、 memcache を“事前準備”しました。新しい memcache のインスタンスを本番環境へ配置する前に、キャッシュ内にできる限り多くの最新の求人情報用のデータを読み込みました。このテクニックを使用することで、新しい docservice のインスタンスですら、殆どの求人情報のドキュメントが、キャッシュから提供されるようになりました。
memcached の導入により、一日中求人情報のドキュメントの提供を確実に早く提供できるようになりました。データベース負荷と集約の処理の過多が大幅に削減されたことが、急成長をし続ける手助けとなりました。
2009: 世界規模では
このドキュメント提供のアプローチは、 Indeed が国際的にロールアウト始めた当初、２年以上もの間、うまく機能していました。
2008年の 11月までには Indeed は6か国に展開し、710万件の求人を毎月アグリゲートしていました。 1億 5000 万件のドキュメントを一日に提供しており、ピーク時には、一秒間 3000 件のドキュメントを提供していました。
この拡張に対応するため、さらに多くの本番環境のサーバーを追加し、新しい docservice のインスタンスを立ち上げました。データベースを使用して、率先して memcache の事前準備をすることはできませんでした。というのは、一回で数分にのぼり MySQL のマスター上への書き込みをロックしてしまうからです。代わりに、事前準備する処理がデータベースにクエリをかける割合を制限しました。私たちの予測では、やがて、ライブトラフィックを提供する前に、割合を制限した事前準備を行い、新規の memcached デーモンを準備する作業に 36 時間必要になることがわかっていました。
同時に、データのパイプラインへの制限に直面するようになりました。最初の集約の後、より多くのデータを求人情報から抽出しており、これらの属性は他のテーブルや、他のデータベースにさえも保存されていました。
属性の例をあげると、求人の記載された言語、求人の種類（フルタイム、パートタイム、等）、給与などがあります。現行のアーキテクチャ内でこの情報を求人の表示する唯一の選択肢は、テーブルの結合か、一つの検索につき複数のデータベースへのクエリだけでした。しかし、どちらも求人情報のドキュメント提供を遅くさせ、データベース負荷を増やすため、受け入れがたいものでした。
Stored fields を再び使用することもできましたが、着々と増え続けるインデックスのサイズもあり、役に立ちそうもありませんでした。
また、米国外のユーザーにも最良のユーザー体験を提供するため、私たちは世界中のデータセンターに弊社サイトをホストする必要がありました。 memcached をもってしても、データベースが時には必要でした。
世界中のデータセンターを単一のデータベースに依存させるということは、許容範囲を超えた量のレイテンシをもたらしますし、データベースの複製は、私たちのユースケースには役に立たないことは既に分かっていました。
すべての求人属性を含み、遠隔のデータセンターにも簡単に複製できて、素早いアクセスを提供できる単一のデータストアを実装する時期がきていました。
新しいデータストア
docstore と呼ばれる私たちの新しいソリューションは、非正規化された、読み込み専用（read-only）、ファイルに基づいた求人データ用のストアでした。
docstore のビルダーのビルダープロセスは求人のデータを書き込み、 Thrift を使用してシリアライズし、最大 100 件の求人 ( ID 順に)が圧縮されたセグメントファイルに保存していました。
下図のように、シンプルな命名規則が、その ID をもつ求人を参照するのを簡単にしました。
あるドキュメントに対しリクエストが来ると、まずシンプルなディレクトリ検索を使用し、セグメントファイルを特定します。 そして、セグメントファイルを読み込み、オフセットを利用しファイル内の求人データを取得します。
docservice はデータの優先ソースとして memcache を使用していましたが、その求人情報がキャッシュにない場合、 docstore にフォールバックし、求人情報がそのどちらにも存在しない場合のみデータベースにリクエストを送りました。
docstore はデータを削除することは絶対にないので、 docstore の構築や複製が最新の本番インデックスより遅れた場合のみ、求人情報は不在となります。
その後、私たちは検索サービスのインターフェースを更新し、まだ docstore に存在しない結果を除外しました。それにより完全にデータベースへの依存性を無くすことができました。これは、遠方のデータセンターに (たとえ稀でも) クエリを出すには、コストが高くつきすぎるような遠隔のデータセンターのローンチを可能にしました。うまくいったのです。ジョブの提供と新しいdocserviceをオンラインに配置するためのキャッシュの事前準備を素早くおこなうことが世界中で可能でした。
この新しいアプローチをもって、 docstore ビルダーは求人情報データベースの唯一の直接のコンシューマーなりました。これは劇的にデータベースの競合を削減しました。結果として派生する docstore を遠隔のデータセンターに複製するため、私たちは再び rsync を使用しました (図5 参照) 。
そして、docstoreは検索結果を提供する際の全求人データのソースとなったのです。
docstore のローンチは、2009年には23か国におけるグローバルな事業展開を可能にしました。 2009年 11月には、世界中で、毎月 2250万の求人情報をアグリゲートしていました。毎日 3億 1200万件のドキュメント、ピーク時には 1秒間に 6000件を提供していたのです。
図 5: docstore から提供
2011: それまで世界規模で機能したパフォーマンスも…
Docstore のソリューションは 2011年ごろまで、うまく機能していました。
ドキュメント提供における、実行時のデータベース依存性を廃止したことで、パフォーマンスと可用性の水準を高く保ちながら、世界中のデータセンターへのロールアウトが可能になりました。
2011 年末には、 4100 万件の新規の求人情報を毎月アグリゲートしていました。毎日 8 億 5000万件の求人情報のドキュメントを提供しており、ピーク時には毎秒 1万 4000件のドキュメントを処理していました。
Job IDをもとに docstoreのディレクトリ構造を決めたことで、求人情報を探すのは簡単になりました。
しかし、それは同時に、アグリゲーションシステムが求人情報に更新があることを発見すると、 docstore ビルダーは、最新の情報を維持するために、既存のセグメントファイルのコンテンツを変更する必要があるということを意味しました。
データから、1件の求人に対する平均的な更新の回数は 1.5 だとわかっていました。インデックス内の半数近い求人情報が、少なくとも一度は更新されていましたし、多くは一度以上更新されていました。
各更新につき、 docstore はまず求人情報を含むセグメントファイルを見つけ、セグメント内の全100件の求人情報のデータを解凍し読み込み、求人情報を更新し、それからセグメントファイル全体をもう一度圧縮し、ディスクに書き込んでいました。
docstore によって処理された求人情報の更新ストリームは Job ID ではなく、時間に基づいています。したがって、docstoreへの書き込みはファイルシステムのディレクトリを用いる際に利用していたJob IDの局所性からは恩恵を受けることができませんでした。これは、 docstore で最初に直面したボトルネックでした。書き込みのボリュームです。
ディスク中で根本的にはランダムに発生する更新がとても多かったので、単一のドライブでは間に合わせるのが大変でした。また、同じ理由で複製作業が遅くなりました。遠隔の docstore を更新するには、プライマリの docstore ビルダーを遅くしているのと全く同じパターンの書き込みが必要でした。
決まった場所に更新が書き込まれることのもう一つの副作用は、 docstore ビルダーを一回実行すると、 docstore 間での異なるセグメントファイルに影響しかねなかったのです。
これは予期せぬ問題によるセグメントファイルの破損の検知を難しくしました。破損が起きるのは稀でも、破損時にどの求人情報が更新されていたか調査し、影響を受けたセグメントファイルを特定し、修復するのに、多くの手作業を要しました。
根本的には、 docstore は全ての求人情報のコピーを一つもっており、更新が行われるたびに最新の状態に保たれています。そしてはディスク上の保存される場所については、厳しい要件がありました。
このパラダイムの結果として起こる書き込みパターンは、ドライブの物理的な限界にきていましたし、それを既存の docstore で改善できるはっきりした方法もありませんでした。
2011年後半には、新しい技術が必要な時期が来ていました。そして、まったく新しいスケーラブルな docstore を作りました。
本番環境に移行してから一年以上経ちますが、現時点で拡張の限度はありません。
次の投稿では、 docstore v2 の実装の詳細を説明していきます。
関連リンク
@IndeedEng: A New Technical Speaker Series in Austin
“From 1 to 1 Billion: Evolution of a Document Serving System” slides & video