タイプアヘッドのシステム設計：大規模な検索オートコンプリートの仕組み

検索ボックスに「how to」と入力すると、次の単語を打ち終える前に候補が表示されます。この機能は、ほぼすべてのキー入力で、すべてのユーザーに対してリクエストに応答し、しかも瞬時に感じられなければなりません。数十年前にさかのぼる応答時間の研究は、「システムが即座に反応している」と感じられる限界を約 0.1 秒としています。オートコンプリートの個々の要素は難しくありません。難しいのは、単純な処理を非常に高いリクエストレートのもとで厳しいレイテンシ予算に収め、しかも候補を新鮮に保ち、決して表示したくないものを排除し続けることです。

この記事では、タイプアヘッドサービスを設計します。要件と容量、上位 k 件のプレフィックスインデックス、配信とシャーディング、オフラインの構築パイプライン、トレンドのクエリ、キャッシュ、パーソナライズ、フィルタリングを、両方の半分を描いた図とともに扱います。

要件

機能要件：

• プレフィックスに対して、主に人気順で並べた上位 5〜10 件の補完候補を返すこと。
• 新しいトレンドを、数日ではなく数分で反映すること。
• ポリシーに違反する候補を決して表示しないこと。

非機能要件：

• エンドツーエンドで約 100 ms。ネットワーク時間を差し引くと、バックエンドに残る予算は数十ミリ秒です。
• 高可用性：候補が失敗しても検索は動くので、穏やかに機能を縮退させること。
• 安価であること：キー入力のたびに実行されます。

容量

1 日のユーザーが 5,000 万人で、それぞれが 1 日に 10 回検索し、クライアントが 1 文字ごとの送信をやめた後で、検索 1 回あたり約 6 回の候補リクエストが発生すると仮定します。

設計を左右する観察が 2 つあります。短いプレフィックスは極めて反復的です。「w」と入力する人は全員、同じ質問をしています。そして、プレフィックスに対する答えはゆっくりとしか変わらないので、前もって計算できます。

仕事の半分はクライアントが担う

• デバウンス。 最後のキー入力から 100〜200 ms 待ってからリクエストを送り、速く打つ人が 1 文字ごとにリクエストを発生させないようにします。
• 古いリクエストをキャンセルする。 新しいプレフィックスを送ったら前のリクエストを中止し、古いプレフィックスへの遅れた応答は無視します。
• ローカルにキャッシュする。 「how t」の結果 10 件がすべて「how to」で始まっていれば、クライアントはリクエストなしで「how to」用に絞り込めます。
• 黙ってフォールバックする。 候補の呼び出しが失敗したり遅かったりしたら、何も表示しません。検索は引き続き機能しなければなりません。

上位 k 件のプレフィックスインデックス

古典的な構造はトライです。各ノードがプレフィックスで、子ノードはそれを 1 文字伸ばします。リクエスト時にトライをたどり、サブツリー全体から最も人気のあるクエリを探すのは、人気のあるプレフィックスでは遅すぎます。代わりに答えを事前に計算し、各プレフィックスノードに、並べ替え済みの上位 k 件の補完候補を保存します。ルックアップは 1 回の読み取りになります。

多くの実装は、ポインターベースのトライを完全に省き、プレフィックスから上位 k 件のリストへのフラットなマップを保存します。非常に長いプレフィックスはまれで、遅い経路に回せるため、マップは最大プレフィックス長で打ち切ります。集計済みのカウントから作るコードは短く済みます。

import heapq
from collections import defaultdict

def build_prefix_index(query_counts, k=10, max_prefix=12):
    index = defaultdict(list)  # prefix -> min-heap of (count, query)
    for query, count in query_counts.items():
        for n in range(1, min(len(query), max_prefix) + 1):
            heap = index[query[:n]]
            if len(heap) < k:
                heapq.heappush(heap, (count, query))
            elif count > heap[0][0]:
                heapq.heapreplace(heap, (count, query))
    return {p: [q for _, q in sorted(h, reverse=True)] for p, h in index.items()}

出力は読み取り専用で、各配信ノードのメモリに読み込みます。すでに Elasticsearch を運用しているなら、その completion suggester が同じ考え方を機能として提供しています。ドキュメントには、高速なルックアップを可能にする一方で構築コストが高く、メモリに保存されるデータ構造だと書かれており、まさにこの設計と同じトレードオフです。

配信とシャーディング

候補サービスはプレフィックスを正規化し（小文字化、前後の空白除去、Unicode 正規化）、インデックスから上位 k 件のリストを読み、トレンドと個人の結果を混ぜ、フィルタリングして返します。読み取るものはすべてメモリ上にあります。

インデックスが 1 台に収まらなくなったら、シャーディングします。先頭の文字で分けるのは自然に見えますが、ひどく偏ります。「x」より「s」で始まるクエリのほうがはるかに多いからです。代わりにプレフィックスをハッシュするか、計測したトラフィックの範囲で分割し、各シャードを複製して、ノード障害が容量の低下だけで済むようにします。インデックスはオフラインで再構築されるので、レプリカ同士が書き込みについて合意する必要はありません。どれも同じスナップショットを読み込みます。

オフラインの構築パイプライン

1. 収集。 検索のフロントエンドは、完了したクエリをすべて Kafka のようなストリームに記録します。
2. 集計。 バッチジョブが、たとえば直近 30 日のような期間でクエリを数えます。最近の日ほど重みを大きくし、しきい値未満のまれなクエリは、プライバシー保護とノイズ除去のために捨てます。
3. フィルタリング。 何かが候補になる前に、ブロックリストとポリシー分類器を適用します。
4. 構築。 上のようにプレフィックスインデックスを計算し、バージョン付きのスナップショットとしてオブジェクトストレージに書き込みます。
5. デプロイ。 配信ノードは新しいスナップショットを旧版と並べて読み込み、アトミックに切り替え、すばやくロールバックできるよう前のバージョンを残します。

1 時間ごとか 1 日ごとの再構築で、ほとんどのクエリにとって十分に新鮮なメインインデックスを保てます。

トレンドのクエリ

速報ニュースは、次のバッチ構築よりずっと前の数分のうちに、新しい人気クエリを生みます。小さなリアルタイム層を加えましょう。ストリームプロセッサーがスライディングウィンドウでクエリを数え、ベースラインよりはるかに速く伸びているものを検出し、Redis のような高速ストアにプレフィックスをキーとして書き込みます。候補サービスはそれをバッチの結果と混ぜます。この層は小さく保ち、厳しくフィルタリングしてください。組織的な攻撃が候補を仕込もうとするのはここだからです。

すべての層でキャッシュする

短いプレフィックスは誰にとっても同じなので、最もホットで、最もキャッシュしやすいものです。パーソナライズした結果は CDN でキャッシュできません。パーソナライズを軽く保つ理由の 1 つです。

パーソナライズ、タイプミス、フィルタリング

• 個人の履歴。 ユーザー自身の最近のクエリを全体の候補と混ぜると大いに役立ち、最近のクエリがデバイス上かユーザーごとの小さなストアにあれば低コストです。
• タイプミス。 プレフィックスから編集距離 1 以内のあいまい一致で「pyhton」を救えます。コストが高いので、多くのシステムはまず完全一致のプレフィックスを試し、結果が少ないときだけあいまい一致にフォールバックします。
• フィルタリングは 2 回適用します。オフラインでは、クエリがインデックスに入る前に。オンラインでは、再構築なしで数分以内に更新できる高速なブロックリストに対してです。

タイプアヘッドの図

図の読み方は次のとおりです。

• オンラインのフレームは、キー入力ごとの経路です。ブラウザー、CDN キャッシュ、API ゲートウェイ、候補サービスと続きます。
• 候補サービスは、メモリ上の 2 つのプレフィックスシャードと Redis のトレンドストアを読み、結果をマージしてフィルタリングします。
• オフラインのフレームは構築の経路です。Kafka からのクエリログ、集計ジョブ、オブジェクトストレージ内のバージョン付きインデックススナップショットです。
• オブジェクトストレージからシャードへの破線のエッジはスナップショットの読み込みで、2 つの半分をつなぐ唯一のリンクです。
• Markdown ブロックは、レイテンシ予算と容量の数値を示しています。

読み取り中心のシステムをわかりやすく描く

• オンラインとオフラインを分けます。 2 つの半分は、レイテンシ予算も、障害の現れ方も、担当者も異なります。図はそれをひと目で伝えるべきです。
• すべてのキャッシュ層を有効期限とともに描きます。読み取り中心のシステムでは、アーキテクチャの大部分がキャッシュです。
• 2 つの半分をつなぐ唯一のリンクを描きます。 ここではバージョン付きのスナップショットです。更新がどうユーザーに届き、ロールバックがどう機能するかを説明します。
• オンラインの経路にレイテンシ予算を書き込みます。

一般的な進め方はシステム設計図の例を参照してください。キャッシュ戦略図はキャッシュ層をさらに詳しく扱っており、ログの集計はデータパイプラインのアーキテクチャ図のパターンに従います。

Archboard で作る

1. Google または GitHub でサインインし、図を作成します。
2. 基本パックの フレーム ノードを 2 つ追加します。Online, per keystroke と Offline, hourly build です。
3. オンラインのフレームに、ブラウザー用としてネットワークパックの デバイス ノード、クラウドパックの CDN と APIゲートウェイ、候補サービス用に コンピューティング ノード、プレフィックスシャード用にデータパックの Redis ノードを 2 つ、トレンドのクエリ用にもう 1 つ Redis ノードを追加します。
4. オフラインのフレームに、クエリログ用としてデータパックの Kafka ノード、集計ジョブ用にクラウドパックの コンピューティング ノード、インデックスのスナップショット用にデータパックの オブジェクトストア を追加します。
5. リクエストの経路を左から右へ、構築の経路をその下に描き、スナップショットからシャードへ破線のエッジを引きます。
6. レイテンシ予算と容量を書いた基本パックの Markdown ブロックを追加します。

この例で使うダイアグラムノードは 13 個で、Free プランの範囲に収まります。

よくある質問

オートコンプリートにはどんなデータ構造を使いますか？ トライ、またはプレフィックスから結果へのフラットなマップを使い、各プレフィックスに上位 k 件の補完候補を事前計算しておきます。事前計算によって、すべてのルックアップがメモリ上の 1 回の読み取りになります。

オートコンプリートはどのくらい速くなければなりませんか？ キー入力から候補表示まで約 100 ms なら瞬時に感じられます。ネットワーク時間を差し引くとバックエンドに残るのは数十ミリ秒で、インデックスをメモリに置くのはそのためです。

候補はどうやって最新の状態に保たれますか？ バッチパイプラインが 1 時間ごとか 1 日ごとにクエリログからインデックスを再構築し、リアルタイム層が急上昇するクエリを数分以内に追加します。

オートコンプリートのリクエストはキー入力のたびに送るべきですか？ いいえ。クライアントで 100〜200 ms のデバウンスをかけ、古いリクエストをキャンセルし、長いプレフィックスにはキャッシュ済みの結果を再利用します。これでリクエスト量が大幅に減ります。

不快な候補はどう排除しますか？ クエリがインデックスに入る前にオフラインでフィルタリングし、人気度の最低しきい値を設け、すばやく更新できるブロックリストに照らして結果をオンラインで確認します。

無料で始める — 1 シート、クレジットカード不要。