こちらは Algolia Co-founder CTOのJulien LemoineがHigh Scalabilityに寄稿した Evolution Of Search Engines Architecture – Algolia New Search Architecture Part 1 の翻訳です。
完全に新しくなった検索エンジンのアーキテクチャとはどのようなものでしょうか？AlgoliaのCo-founder & CTOのJulien Lomoine(ジュリアン ルモアンヌ)が、検索の未来がどのようなものになるか解説します。この記事はシリーズの第一弾です。
検索エンジン、そしてより一般的な情報検索システムは、今日の技術スタックにおいて、中心的な役割を果たしていると言えるでしょう。情報検索は、コンピューターサイエンスの分野では創世記にはじまったものです。1990年代の初頭にTREC(Text REtrieval Conference)で紹介され研究が加速されていきました。TRECから30年以上が経った今でも、検索エンジンは成長を進化を続けており、新しいチャレンジを生んでいます。
こちらの記事では、検索エンジンのアーキテクチャの進化における、重要なマイルストーンのいくつかをご紹介します。また、これらのアーキテクチャが現在直面しているような課題についても解説します。ご覧頂きますように、私たちはエンジンを4つのアーキテクチャカテゴリに分類しました。これは敢えてシンプルにしたものであって、実際は様々なアーキテクチャが混在するようなエンジンが世の中には数多く存在しています。このようにまとめた理由としては、これらのアーキテクチャの最も重要な部分にフォーカスするためです。
1. 転置インデックス – 検索の黎明期
検索エンジンの黎明期における、最初の大きな革命は転置インデックスの利用といっても過言ではないでしょう。”index”という言葉は、書籍の最後にある索引に由来していますが、ある単語と、その単語に関する情報を含む様々なページが関連付けられているものです。
検索エンジンは、そこに出現する全ての単語の辞書を構築し、それぞれの単語ごとに、その単語が含まれるドキュメントのリストを保存し、並べます。それによって、エンドユーザーが複数の単語でクエリを実行した際、検索エンジンは全ての単語をスキャンして、インターセクション(全ての単語が含まれるドキュメント)を計算して、それらをランク付けすることができるのです。
全ての検索エンジンは、このようなIndexingという一般的なコンセプトをフォローしています。Indexingは転置インデックスたち(複数の転置リストで構成されている)をいかに効率的に表現するかという新しい研究分野を切り拓きました。この研究によってより多くの情報が含まれる転置リストを効率良く圧縮してスキャンするための複数の圧縮用のアルゴリズムが開発されました。
もし、転置リストがどのように表現されているか、そして、そこで使われている様々なアルゴリズムに興味がある方は、Christopher D. ManningのIntroduction to Information Retrievalを一読されることをお勧めします。
ソフトウェアアーキテクチャにおける黎明期の検索エンジンは次のようにサマライズすることができます。
- “Indexingプロセス”は、レコードのリストを計算し、転置インデックスを表現するバイナリファイルを作成します。
- “Queryプロセッシング”は、バイナリファイルを読み取り特定のクエリにおける転置リストのインターセクションを計算します。
ここにはスケーリングに関するコンセプトはありません。このアーキテクチャはデータが少ない場合においては非常に上手く機能しました。1990年代初頭のWebの出現および拡大によってデータのボリュームが急激に増えたため、アーキテクチャのスケーリングが必要になりました。
2. シャーディングの導入 – パラレル化
インターネットの黎明期には、ウェブサイトは手動でディレクトリに登録されていました。しかし、その数年後には増え続けていくウェブサイトに手動で対応することは不可能であることが明らかになりました(internet live statsによると、ウェブサイトの数は1993年の130サイトから1995年には23,500にまで増えています)。このようにして、検索エンジンの最もポピュラーなユースケースとしてのWeb検索エンジンははじまっていきました。
1993年、最初のWeb検索エンジンたちが登場しました。それらは全て1990年代初頭のデータ量の急増に対応しなければなりませんでした。1995年、DEC(Digital Equipment Corporation)がAlta Vistaという検索エンジンを発表したのは、マルチプロセッサ搭載の64ビットAlphaサーバーの能力を示すためでした。Alta Vistaは当時掲載されていた1,000万件のWebサイトのインデックスを作成可能な完全に並列で稼働する最初の検索エンジンの1つでした。
パラレル化を検索エンジンに適用するのはとてもシンプルです:
- 全てのドキュメントを含む1つの転置インデックスを保持するのではなく、ドキュメントをN個の小さなドキュメントセットに分割します。それぞれのセットはシャードと呼ばれ、それは最初のドキュメントセットのサブセットを含みます
- これによって全てのシャードのIndexingを並列で行い、1つの大きな転置インデックスではなく、N個の小さな転置インデックスを作成することが可能になります
- 最終的に、各シャードを並行して検索し、N個のクエリを作成して結果を集約することで統一された結果セットを作成することができます
シャーディングの導入によって、検索エンジンは大量のデータを扱うことが出来るようになりました。シャーディングが登場した当初は、シャード数、もしくはサーバーの数はあらかじめ決め打ちでした。そこでの多くの実装は、数学的なハッシュ化を施して、1つのドキュメントをN個のシャードの中の1つに割り当てていました。ドキュメントは常に同じシャードに割り当てられるため、シャード間で同じドキュメントのレコードが重複することはありませんでした。
このシャードベースの検索エンジンのアーキテクチャは次のようにサマライズできます:
- 異なるサーバーに分散された固定数のシャード
- 転置インデックスの分散された計算(Indexing – 1つのシャードにつき1スレッド)
- 異なるシャード間での検索結果の分散計算(Searching – 1つのシャードにつき1スレッド)
いくつかの追加コメント:
- 1つのシャードにおけるIndexingとSearchingは、同じマシン上で行われる必要性(転置インデックスはローカルストレージに存在する)
- 分散コミットのように、Indexingオペレーションを全てのシャードで同じタイミングで行うような仕組みはありません。例えば、インデックスを作成する属性のリストを変更したい場合や、レコードの構造を変更したいような場合には別のインデックスを作成する必要がありますが、これらの走査をアトミックに行うことは出来ないということです
- マージ機能が代数的でないアグリゲーション(non-algebraic aggregation)を行わなければならない場合、新しいタイプの問題が発生することになります。例えば、フィールドの値に基づいて結果を縮約するような場合。(ジョブボードで会社名ごとにジョブを縮約して、カテゴリごとに上位10件のジョブを表示する 等)
このようなアーキテクチャは1990年代、さらには2000年代初頭にも使われていました。もちろん、このようなアーキテクチャにも負荷に耐えられるよう、多くの改良や改善が加えられました。例えば、Batch Indexingは、すぐさま、パスごとの転置リスト再構築を避けるため(データベースに似ていますね)、インクリメンタルビルドに置き換えられました。シャーディングは、検索エンジンを拡張するための重要なコンポーネントです。今日は次のセクションで後述する、高可用性に到達するための他の原則に加えて、全ての検索エンジンのアーキテクチャの一部となっています。
3. 高可用性と検索のスケーリング – 成熟の時代
検索エンジンは、大量のデータや膨大なクエリを管理するために拡張性が求められます。Internet World Statsによると、1995年には1600万人しなかったインターネットユーザーが、急速な成長に伴い、2020年には50億人以上に達すると言われています。
前のセクションでは、シャーディングによる大量データの管理方法について説明しましたが、次の問題は、大量のクエリをどう管理するかということ、それに伴う検索の可用性(つまりハードウェアの故障をサポートすること)です。
この問題を解決するには、転置シャードのレプリカを導入して、複数のマシンセットからのクエリに答えられるようにする必要があります。一般的な原則としてはシンプルです: 今までと同じアーキテクチャを使用するものの、1つのマシングループだけではなく、任意のクエリに答えることができるN個のマシングループを用意します。それぞれのグループのマシンには、クエリに答えるための全てのシャードが含まれていて、クエリの量に応じてレプリカの数を増減させます。
このようなアーキテクチャの複雑は重荷レプリケーションのロジックにあり、以前のアーキテクチャと同じような特性と欠点を持っています。転置インデックスのレプリケーションの複雑さは、ディスク上のデータ構造のフォーマットに依存します。生成されたデータ構造は多くの場合、転送されるデータ量を最小限に抑えるように最適化されます。ディスク上の様々なタイプのデータ構造について詳細を知りたい方は、LevelDBのKeyValueストアの内部に関する詳細を読んでいただくことを推奨します。同じコンセプトが検索エンジンについてもしばしば適用されています。
こういったアーキテクチャがパブリッククラウド環境でホストされている場合、サービスレベル目標(SLO)を向上させるために、異なるマシングループを異なるアベイラビリティーゾーンでホストする必要性が生じます。クエリを異なるマシンセットに分散したり、エラー時にリトライを行うためにロードバランサーが必要です。
このレプリカベースの検索エンジンアーキテクチャは従来のものと全く同じ特徴を持ちますが、それに加えて:
- データのレプリケーションを通じて無制限のクエリを処理可能なキャパシティ(キャパシティを増やすには既存のマシンから転置インデックスをコピーする必要があり、通常は長時間かかる。これはトラフィックの増加が予想される場合にのみ良いソリューションと言える)
- multi-providerなデプロイメントにおいては、on-disk data-structureはよくIndexingオペレーションがトランスファーされるprimary/replicasのセットアップに置き換えられます。プライマリのシャードはIndexingオペレーションを受け取り、ストアしてログに書き込みます。このログはIndexingプロセスによってローカルのディスクに置かれ、そして、1つまたは複数の場所にレプリケートされます。この設定を行う理由としては、大きなバイナリファイルを転送する際に、プロバイダ間の帯域がボトルネックになる可能性があるため、バイナルファイルではなく、Indexingオペレーションをレプリケートした方が通常は早いためです。
4. Indexingの高可用性と弾力性 – ビジネスでクリティカルな領域
あらゆるオンラインビジネスにおいて、検索の高可用性が重要であることを考慮すると、ビジネスに影響を与えずにハードウェア障害を許容できるすることは非常に重要であると言えます。アーキテクチャにおいては、エンドユーザーに透明性があるように、ハードウェアの障害を管理する必要があります。
上記で紹介したアーキテクチャで、検索機能に影響を与えることなく、ハードウェア障害を受け入れる方法が導入されました。しかし、Snapchatのような新しいユースケースにおいては、Indexingがシステムの重要な構成要素となります: スナップショットの情報は一時的なものであるため、直ぐに検索できる必要があります。Indexingの高可用性は、様々なアーキテクチャを通じて検索エンジンに導入されましたが、共通していることは、少なくとも2台のマシンで1つのシャードを構築できるということです。これにおいて最も優れたアーキテクチャとしてはElasticsearchが挙げられ、2010年にこれが導入されて、検索とIndexingの両方の高可用性を実現しました; Elasticsearchがもたらした最も重要なイノベーションは、Indexingの高可用性ではなく、弾力性(Elasticity)です。Elasticityとは、既存のインスタンスにマシンを追加したり、マシンの間でシャードを移動させたりできるということです。これは検索エンジンのアーキテクチャを大きく進化させたと言えます。
Indexingの高可用性の導入においては、前のセクションで説明したようにprimary/replicasなアーキテクチャを進化させたものとなります。各シャードには1つのプライマリがあり、IndexingジョブとN個のレプリカのユニークなオーダーが実現されています。それぞれのレプリカがジョブを同じ順序で処理することで、全く同じ状態に収束するという点が重要です。
プライマリシャードをホストしているマシンがダウンしたとしましょう。その場合、グローバルに一貫した状態を保つため、リーダーを選ぶアルゴリズムによって、1つのレプリカが新しいプライマリに選出されます。
これを表現するために、次のような例を挙げてみます:
- 1つのインデックスに4つのシャードがある
- Factor-threeレプリケーション(各シャードの3つのコピー: 1つのプライマリシャードと2つのレプリカシャードの構成)
- 4台のマシンに分散配置。各マシンには1つのプライマリシャードと2つのレプリカシャード
システムにIndexingオペレーションがやってくると、ルーティングフェーズでオペレーションを正しいプライマリシャードにルーティングします。このルーティングプロセスは、3台のマシンのうち、どのマシンでも実行することができます(これはどのマシンをターゲットにしたとしても、Indexingオペレーションを実行することができるということです)。プライマリシャードのIndexingプロセスは、その後、全てのシャードにIndexingオペレーションをレプリケートして、その結果、3台のマシンでIndexingオペレーションが並行して行われることになります(図3を参照)
ロードバランサは各シャードの3つのコピーのうち1つを選択してトラフィックを割り振ってクエリを実行します。3つのコピーはシャードの1つのコピーと比較すると、3倍のクエリを行うことを可能にします。こちらの設定では、マシンは2つのアベイラビリティーゾーン(AZ)に分散しています。それぞれのAZはクラウドプロバイダのリージョン内の可能な限り異なる物理インフラ上で動作します。3つのコピーは、1つ目のコピーが100%1つ目のAZでホストされ、2つ目のコピーが100%2つ目のAZでホストされ、3つ目のコピーは、2つのAZで分割される形で保持します。図4は、1つのAZに100%ホストされているコピーに送られる1つのクエリを表しています。
それぞれのマシンにおいては、Indexingと検索のプロセスがローカルに保存されている全てのシャードにアクセスすることができます。弾力性に関しては、既存のセットアップにマシンを追加および削除することによって担保されます。例えば、先程の例に新しいマシンを追加すると、シャードは自動的に新しいマシンに移行されて、各マシンに均等に負荷がかかるようになります。検索エンジンの割り当てに関するアルゴリズムによっては、図5のような結果になるかもしれません。
このアーキテクチャにおいてはシャードの数は固定されています。シャードの数を定義するということは、拡張性と基本的なパフォーマンスを定義することを意味し、これはコンフィグレーションにおいて重要な要素と言えるでしょう。こちらの例では、シャードの数は全てのマシンの全てのCPUリソースを消費するほど大きくはありません。しかし、レプリカの数を増やせば、より多くのクエリをサポートし、全てのリソースを使うことができます。これがスタンダードなスケールの方法です。
シャードの数を増やしすぎないこともまた重要です。ゴールは全てのシャードを並行して処理することですが、全てのシャードに大して同様にCPUスレッドを用意することが出来ないと、レスポンス時間に悪影響を与えます。
このアーキテクチャでは、全てのシャードを利用可能な状態に保ちつつ、2種類の障害をやりくりすることができます:
- 1台のマシンがダウン。この場合、Indexingおよび検索には何も影響がありません。十分な数のレプリカがあるので、検索クエリは継続して動作することが可能です。リーダーの選挙は、2つのレプリカのうちのどちらか1つがマスターとして選出されることになります。唯一の影響としては、検索に使うことができるスレッド数が少なくなるので、検索能力が低下する恐れがあります。
- 1つのアベイラビリティーゾーンがダウン。この場合、スケールするキャパシティが少なくてよければ検索は可能です。Indexingは3つのコピーのうち1つしか残らず、2つのシャードが利用できないため、リーダーの選挙をすることができません。
このようなタイプのアーキテクチャは今日では最先端であると言え、次のような特徴があります。
- 設定したシャードの数に応じて、データを拡張可能なこと
- 新しいレプリカを追加することで、クエリのボリューム応じた拡張が可能であること
- ハードウェアの故障やアベイラビリティーゾーンの故障をある程度許容可能であること
5. Next Steps – 検索エンジンの現在のチャレンジ
なんと、最新の世代のアーキテクチャは10年以上前に登場したものなのです！それ以来、急成長するマーケットプレイスやSaaSアプリケーションは、こういったアーキテクチャから多くの制約を受けています。今こそ次の10年に向けて、以下のような課題を解決する次世代のアーキテクチャを設計する時期に差し掛かっているのではないでしょうか:
- 1分未満でのマシンの追加や削除が可能。既存の構成でもマシンを追加したり削除する方法は既にわかっていますが、更に一歩進んで、ダイナミックなスケーラビリティをサポートする必要があります。これは1分以内にマシンを追加・削除し、更に新しいマシンが利用できるようになるまでの間、一時的にトラフィックの増加を処理するというものです。今日の検索エンジンは今まで以上に急激な成長に対応し、トラフィックの急増に合わせてインフラを拡張することが求められていると言えます。ダイナミックなスケーラビリティを実現することで、検索エンジンの新しいクリエイティブな使い方を可能にし、コスト効率を高めることができます。例えば、ある大手のマーケットプレイスでは、検索エンジンを活用したフラッシュセールのアイデアを発表しました。お客様は、膨大なカタログの中から安い商品を見つけるわけですが、数百万人のユーザーにメールを送信した直後に検索エンジンに問い合わせが殺到することは想像に難くなく、前回のイベントでは、1日の平均トラフィックの160倍のトラフィックが発生したとのことです。しかし、このような検索イベントはビジネス上ではいつでも起こり得るのと、こういったことを事前に計画しておくのは不可能です。
- ダイナミックにシャード数を変更する。シャードの数はパフォーマンスと拡張性の重要な要素になりますが、これを最適な状態にするには、その数が頻繁に変更できる必要があります。次世代の検索エンジンのアーキテクチャでは、この数をダイナミックに変更できるようになります。そして更にエンジンがこの数を自動的に調整して、常に最適なパフォーマンスと拡張性を確保できるようにしなければなりません。
- 検索とIndexingの分離。クエリの量とデータの量の両方でスケーリングすることは、検索エンジンにとっては容易ではありませんが、マーケットプレイスのような多くのユースケースでは問題となりえます。このような状況でレプリカごとにIndexingを行うとインフラのコストがすぐさま非常に高価になってしまいます。検索やIndexingのキャパシティを増やすと、既存のマシンリソースの消費量に影響をおよぼしてしまいます。例えば、既にシステムに負荷がかかってしまっている時に、サブシステムの1つをスケールアップすると、システム全体が崩壊しかねないことがあります。次世代においては、検索とIndexingの可用性を高めつつ、各シャードに大して1度だけIndexingを行います。また、Indexingと検索を別々にスケーリングさせることで、Indexingが検索に与える悪影響を回避します。
- 進化を遂げるネットワーク帯域を活用する。10年前はマシン間のリンクが1Gpbsであることが当たり前でしたが、現在、パブリッククラウドのプロバイダは最大100Gbpsのネットワークリングを利用できるようになっており、今後益々それが当たり前になっていくでしょう。この10年間でCPUやストレージの向上は帯域の100倍という観点からははるかに限定的でした。このようなネットワークアーキテクチャを活用するには、より多くの並列化を伴う、全く異なるデータ転送の使い方が必要になるでしょう。これは、効率的にスケールをさせる検索エンジンのアーキテクチャの中核となるような不可欠な要素です。
- ネイティブなマルチテナント型の最適化。SaaSアプリケーションにおいては、1つのインデックス内で複数のユーザーをホストすることが広く行われています。顧客ごとに専用のインデックスを用意するのはコストがかかりすぎるからです。これは素晴らしい戦略ですが、大規模なユーザーに対して保証されたパフォーマンスを提供することは、今日ではかなり難しくなってきています。新しい検索アーキテクチャは、ロジカルな観点から1つのインデックスであるように見えるような進化が必要です。それでも最重要顧客には専用のシャードとリソースを用意し、パフォーマンスを保証することで他のお客様からの影響を回避します。
私たちは2019年に次世代アーキテクチャの構築に着手しはじめた際、上記の5つのユニークな課題を特定しました。私たちはこれを解決することを目的とした独自のアーキテクチャをデザインし、最初のお客様にテストしていただいています。次の記事ではこのアーキテクチャがどのように機能するのか、また、私たちがどのようにして検索の5つのユニークな課題を解決しているのかについて詳しく説明していきます。
コメント