検索オートコンプリートの設計

要件と規模の見積もり

まず機能要件を固定します。ユーザーが検索窓に1文字入力するたびに、その接頭辞（prefix）で始まる候補を人気度順に上位k件（典型的にはk=5〜10）返す。候補集合は過去の検索クエリから生成され、リアルタイム性は緩くてよい（新語が反映されるまで数分〜数時間の遅延は許容）。非機能要件としては、体感で「即座」に見せるためのレイテンシがすべてで、入力から候補描画までを数十ms（p99で50ms前後）に収めることを目標に置きます。可用性は高く求められますが、強い一貫性は不要です。

規模をフェルミ推定で桁だけ押さえます。日間アクティブユーザーを1億、1人あたり平均10回検索、1クエリで平均20文字入力し、その大半でリクエストが飛ぶとすると、検索は10億回/日ですが、キー入力起点のオートコンプリート要求はその20倍のオーダー、つまり200億回/日に達します。秒あたりに直すと約20万QPSが平均で、ピークはその2〜3倍の50万QPS超を見込みます。読み取りが圧倒的に多く、書き込み（人気度の更新）は集計後にまとめて反映するため桁違いに少ない、という非対称性がこの設計の出発点です。

ストレージは、ユニークな検索フレーズを5億件、1件あたり平均30バイトとすると生データで約15GB。ここに上位k件の候補やスコアを各ノードに持たせるトライ木の索引を加えても、数十GB〜100GB規模に収まり、分割すれば1台のメモリに載せられます。帯域は、1レスポンスが候補5件で約1KBとして、20万QPSなら約200MB/s。ピークで数百MB/sを見込み、これは後述の分割とレプリケーションで各サーバーへ分散します。

大枠の設計

APIは1本で足ります。GET /autocomplete?q=<prefix>&k=10 がスコア降順の候補配列を返す。レスポンスは強くキャッシュ可能で、CDNやクライアント側にも短いTTLで載せられます。ここはCDNのエッジキャッシュが素直に効く領域です。

データモデルの中核はトライ木（trie、接頭辞木）です。各エッジが1文字に対応し、根から辿った経路がその時点の接頭辞を表します。素朴な実装では、接頭辞ノードから配下の全葉を走査してスコア上位を選びますが、これは読み取り時に重い探索を強いるため目標レイテンシに反します。そこで各ノードに、その接頭辞から到達可能な候補の上位k件を事前計算して格納します。読み取りは「接頭辞の末尾ノードまで下りて、格納済みのリストを返す」だけの O(接頭辞長) 操作になります。

検索窓に "te" と入力
   root
    └ t
       └ e   ← このノードに上位k件を事前保持
              ["technology"(950), "test"(820), "tesla"(610), ...]
返却: そのまま配列を返す（追加の集計なし）

全体構成は、読み取り経路と更新経路を明確に分けます。読み取り側はメモリ常駐のトライ木サーバー群がロードバランサ配下に並び、更新側はログを集計してトライ木を再構築・差し替える非同期パイプラインです。両者を疎結合にすることで、集計の重さが読み取りレイテンシに漏れ出さないようにします。

主要コンポーネントの深掘り

なぜトライ木か。 ハッシュ表は完全一致には速いものの、接頭辞の列挙ができません。ソート済み配列＋二分探索でも接頭辞範囲は求まりますが、各ノードへの上位k件の事前計算とインクリメンタルな部分更新はトライ木の構造が扱いやすい。共通接頭辞を1経路に畳み込むためメモリ効率もよく、枝が1本しか続かない区間を1ノードに圧縮する基数木（radix tree / Patricia trie）にすると、ノード数と辿るホップ数をさらに削れます。

上位k件の事前計算とキャッシュ。 各ノードのリストは、子ノードのリストをマージして上位k件を選ぶボトムアップの集計で作れます。あるノードの上位k件は、必ず子ノードいずれかの上位k件の中に含まれるため、全葉を見る必要はなく、子のk件同士を優先度付きキューでマージすれば十分です。さらに、人気接頭辞の結果は外部キャッシュ（インメモリのキーバリュー）にも載せ、トライ木サーバーへの到達前に返します。キャッシュキーは接頭辞そのもの、値は候補配列で、TTLは分オーダー。ヒット率は接頭辞分布の偏りが大きいほど高く、短い接頭辞ほどよく効きます。

集計パイプライン（人気度の更新）。 実際に確定した検索クエリをログに集め、ストリーム集計で語ごとの出現回数を時間窓で数えます。生の頻度をそのまま使うと定番語が固定化するため、時間減衰（新しいログを重く見る指数移動平均など）を掛けてスコア化するのが定石です。集計結果は新しいトライ木の（部分）構築に流し込み、完成したものを読み取り側へアトミックに差し替えます。ログの取り込みには配送保証を持つメッセージキューを挟み、集計ジョブの再実行に耐えるようにします。

ボトルネックとトレードオフ

横にスクロール

分割（シャーディング）。 データは1台に載る規模でも、QPSと可用性のために分割します。素直なのは接頭辞の先頭1〜2文字によるレンジ分割で、a 始まりは第1シャード、というように振り分けます。ただし文字ごとに検索頻度が大きく偏るためホットスポットが生まれます。負荷を平準化するには、接頭辞をハッシュした値で割り当てる方法があり、その際はノード追加・削除時の再配置を最小化するコンシステントハッシュが有効です。分割の設計判断はシャーディング戦略の観点と共通し、レンジ分割は範囲局所性、ハッシュ分割は均等性を取る古典的な対立になります。

レプリケーションとスケール。 読み取りが支配的なので、各シャードを複数レプリカに複製し、ロードバランサで読み取りを分散します。トライ木は事実上の読み取り専用スナップショットなので、複製は容易でレプリカ間の一貫性の悩みも小さい（更新は差し替えで全レプリカに配る）。この読み取りスケールと非同期更新の割り切りは、CAP定理でいう可用性側に倒し、鮮度（結果的一貫性）を犠牲にする判断です。

タイポ許容の考慮。 ユーザーは綴りを誤るため、接頭辞の厳密一致だけでは候補ゼロが頻発します。実務では別インデックスで補います。編集距離（レーベンシュタイン距離）が小さい語を引くにはレーベンシュタインオートマトンを、部分文字列や誤字に強くするにはn-gram索引を併用する。これらは厳密トライ木より重いので、まずトライ木で厳密一致を引き、結果が乏しいときだけ曖昧一致にフォールバックする二段構えが現実的です。曖昧一致まで含めても数十msに収めるには、候補生成の探索幅を上限で絞り、スコア上位で早期打ち切りする工夫が要ります。

分割・複製の具体はデータベース、負荷分散とエッジ配信はネットワーク、集計パイプラインの運用はDevOpsの各トピックも参照してください。