プロンプトと適用可能なコンテキスト
入力されたプレフィックスに対して上位10件の検索クエリ候補を返すバックエンドサービスを設計してください。日間アクティブユーザー数（DAU）5000万人、ユーザー1人あたり1日10回の検索、検索1回あたり5回のサジェストリクエスト、ピーク時150,000リクエスト/秒、p99レイテンシ目標50ミリ秒、人気度更新目標15分、ポリシー削除目標1分を前提とします。
これらは面接用の前提条件であり、計測された本番環境の実測値ではありません。基本設計では、匿名でロケール固有の人気サジェストを提供します。ブラウザコンポーネント、スペル訂正、セマンティック補完、およびユーザーごとのパーソナライズは初期スコープ外とします。本サービスは、単にログに出現したという理由だけで、低頻度なクエリや禁止されたクエリを露出してはなりません。
これは、コアの処理がイベント取り込み、ランキング、イミュータブルなインデックス構築、オンライン配信、キャッシュおよびシャードの挙動、安全な公開にまたがるため、システムデザインの問題となります。フロントエンドのオートコンプリートコンポーネントがこのAPIを利用でき、Trieはローカルインデックスの表現方法の1つに過ぎません。
面接官が評価するポイント
優れた回答は、まず書き込み負荷の高い学習パスと、読み取り負荷の高い配信パスを分離します。キーストロークごとに生のログをスキャンしたり候補をソートしたりしていては、厳しいテールレイテンシの目標を達成できません。集約、適格性チェック、モデレーション、およびランキングの大部分はリクエストが到着する前に行う必要があります。オンラインパスは制限されたプレフィックス検索を実行し、少数のリストを返します。
第2の評価ポイントは定量的推論です。日次の前提条件から25億リクエスト（5000万人 × 10回 × 5回）が導き出されます。これは平均で毎秒約28,900リクエストに相当するため、提示された150,000のピークは約5倍のピークファクターとなります。レスポンスを1 KBと見積もると、プロトコルのオーバーヘッドとレプリケーションを除いたピーク時のレスポンスペイロードは約150 MB/sです。これらの計算はレプリケーション、キャッシュ、負荷テストの目標を導くものであり、エンコードされたインデックスを測定することなくメモリサイズを決定したかのように見せかけるものではありません。
第3の評価ポイントは公開の正確性です。不完全に構築されたインデックスやルーティングが一貫していないインデックスは、結果の欠落や順位の不一致を引き起こす可能性があります。優秀な候補者は、バージョン管理されたイミュータブルなアーティファクトを構築し、検証し、古いバージョンと並行してロードし、アトミックにルーティングを切り替え、ロールバック用に以前の正常なバージョンを保持します。
最後に、人気度と適格性は同義ではありません。検索ログには個人情報、不正操作、有害なテキストが含まれる可能性があります。最小頻度の閾値、保持期間の制御、不正防止シグナル、公開前のモデレーション、およびより迅速な緊急拒否パスは、システムの正確性の一部です。
回答前に明確にすべき質問
- サジェストは何を表すか？ クエリ補完、商品エンティティ、ナビゲーション先では、必要な候補ソースやランキング特徴量が異なります。基本設計では完全なクエリ文字列を返します。
- どのようなマッチングが必要か？ プレフィックスのみの検索であれば、コンパクトで順序付けられたプレフィックスインデックスが利用可能です。中間一致、あいまい（ファジー）マッチ、またはセマンティックマッチを追加すると、候補生成器が増え、オンラインのレイテンシ予算内に抑えることが難しくなります。
- 変更の鮮度はどの程度必要か？ 人気度は前提の15分を許容できますが、ポリシーによる削除は1分以内に行う必要があります。これにより、バージョン管理されたベースインデックスと、独立して更新される拒否レイヤーを組み合わせる設計になります。
- 結果はグローバルか、それともパーソナライズされるか？ グローバルな結果は高度にキャッシュ可能です。パーソナライズはキャッシュの共有性を低下させ、同意確認、削除処理、特徴量取得のレイテンシを増加させます。初期段階では除外します。
- ロケールと正規化はどのように定義されるか？ 大文字小文字の統一、文字体系、アクセント、単語の境界はロケールごとに異なります。インデックスとクエリは同一のバージョン管理された正規化ポリシーを使用する必要があります。
- 空のプレフィックスや1文字のプレフィックスはどう処理するか？ これらはアクセスが極めて集中し、幅広いトレンドを露出する可能性があります。基本システムでは、空の入力には精選されたロケール別リストを返し、1文字の場合は事前計算されたリストを返します。
- 安全性とプライバシーの要件は何か？ これらによって、ログの保持期間、集約の閾値、レビュアーのワークフロー、リージョンごとのストレージ、および候補をインデックスに含めてよいかどうかが決まります。
30秒の回答フレームワーク
「システムをオフラインの構築パスと、制約されたオンライン検索パスに分割します。検索イベントはストリームに入り、ロケールとタイムウィンドウごとに正規化・集約され、頻度、不正、プライバシー、モデレーションのゲートを通過します。ランキングジョブが上位の候補をバージョン管理されたプレフィックスインデックスに書き込みます。検証後、配信レプリカがイミュータブルなバージョンをロードし、ルーティングをアトミックに切り替えます。オンラインリクエストはプレフィックスを正規化し、ホットプレフィックスキャッシュを確認し、ロケールとプレフィックスのシャードへルーティングし、高速拒否レイヤーを適用して10件の結果を返します。150,000のピークに基づいてサイジングを行い、必要に応じてホットプレフィックスを分割し、ロールバック用に以前のインデックスを保持し、p99レイテンシ、カバレッジ、セーフティ再現率、古いバージョンの発生率、ランキング品質を測定します。」
ステップごとの詳細解説
ステップ1: レイテンシ予算とコントラクトの導出
小規模な冪等リードAPIを使用します。
GET /v1/suggestions?prefix=iph&locale=en-US&limit=10
200 {
"suggestions": [
{ "text": "iphone charger", "id": "q_7f2" }
],
"indexVersion": "2026-07-19T17:30Z"
}limit を制限し、正規化されたプレフィックスの長さに上限を設け、未サポートのロケールを拒否し、クライアントからのランキング重みを決して受け付けないようにします。不透明な安定ID（opaque ID）により、表示テキストを識別子として扱うことなくアナリティクスをサポートできます。indexVersion により、古いバージョンやバージョンが混在したレスポンスを可視化できます。
1日25億回の計算から、平均約28,900 QPSが導き出されます。提示された150,000のピークがキャパシティ目標となります。1つのレスポンスが約1 KBの場合、150 MB/sを配信するにはリージョンごとのレプリカと圧縮転送が必要です。キャッシュ容量とインデックスのRAMサイズについては、依然として本番サンプルが必要です。代表的なアーティファクトをシリアライズし、プレフィックスおよびTop-Kエントリあたりのバイト数を測定した上で、レプリケーションとヘッドルーム（余力）を加算します。推測したTrieノードサイズに候補数を掛け合わせるだけでは、誤った精度を生むことになります。
ステップ2: 生ログを直接公開せずに候補を構築する
クライアントは、クエリID、正規化されたロケール、大まかなコンテキスト、タイムスタンプ、結果シグナル、および制限された集約にのみ使用されるプライバシー保護のための短寿命アクターキーを含む検索完了イベントを発行します。取り込みサービスはスキーマを検証し、明らかなボットを破棄した上で追記専用ストリームに送ります。ウィンドウ集約によってユニークアクター数と品質シグナルを計算します。生のユーザー識別子がサジェストキーの一部になることは決してありません。
候補パイプラインは、最小ユニークユーザー閾値、レート・不正制御、プライバシー・保持ルール、ポリシー分類を適用します。その後、人気度、時間の経過に伴う減衰、結果品質、エディトリアルルールの文書化された組み合わせを使用して適格な候補をランク付けします。正確な重みは学習とテストによって決定され、普遍的な定数ではありません。不採用となった候補とその理由は、配信インデックスではなく、アクセスが制限された監査用ストアに保持します。
観測されたクリック数に基づくランキングは、すでに表示されていたものを強化してしまう可能性があります。エンゲージメントとともにオフラインの関連性評価やガードされた実験を使用し、サジェストカバレッジ、ゼロヒット率、苦情、露出の偏りを監視します。自動生成されたログ由来のサジェストは有害または偏ったテキストを再現する可能性があるため、モデレーションはインデックス構築の前に行う必要があります。
ステップ3: 制約されたプレフィックスインデックスの実体化
適格なサジェストごとに、オンラインで使用されるものと同じロケール対応の正規化のもとでプレフィックスを生成します。検索とフィルタリングの計算量を抑えるため、プレフィックスごとに制限された上位リスト（たとえば、APIが10件返す場合は上位20件の候補）のみを保存します。余分な候補を持たせることで、サブツリーを探索することなく重複排除や緊急削除が可能になります。
Trieや有限状態トランスデューサー（FST）は共有プレフィックスを表現できます。ロケール＋プレフィックスをキーとする順序付きKey-Valueテーブルは運用がよりシンプルで、良好に圧縮される場合があります。アーティファクトサイズ、構築時間、検索p99、更新ワークフローをベンチマークした上で選択します。ElasticsearchのCompletion Suggesterも同様のトレードオフを示しています。高速なプレフィックス検索にはメモリ内構造を使用しますが、構築コストが高く、重みとコンテキストがランキングとフィルタリングに影響します。
基本スコープは完全プレフィックス補完です。あいまい（ファジー）補完は、編集距離の展開によって再現率、CPUコスト、安全性分析が変化するため、別の生成器とします。同じレイテンシ保証を暗黙的に共有すべきではありません。
ステップ4: イミュータブルなバージョンを安全に公開する
各ビルドには、入力ウォーターマーク、正規化バージョン、ランカーバージョン、ポリシーバージョン、チェックサム、作成時刻が含まれます。検証では、スキーマ、候補数、禁止テストフレーズ、ロケール分離、決定論的タイブレーク、検索サンプル、アーティファクトサイズ、および負荷のかかったレプリカでのレイテンシをチェックします。
レプリカは、アクティブなインデックスの横に新しいイミュータブルインデックスをロードします。ヘルスレポートがそのチェックサムと代表的なクエリを確認します。その後、コントロールプレーンはシャードグループのアクティブバージョンをアトミックに変更します。ロールアウト中、リクエストは1つのバージョンに固定され、結果の混在が測定されます。新しいバージョンがカナリア期間を通過するまで以前の正常なバージョンを保持し、レイテンシ、安全性、またはカバレッジが低下した場合はルーティングをロールバックします。
ビルドが失敗したり遅延したりしても、正常なインデックスが置き換えられることはありません。鮮度はSLO（サービスレベル目標）であり、無効なアーティファクトの公開を許可するものではありません。
ステップ5: オンラインパスを短く保つ
リクエストは、レート制限、正規化、ロケール解決、および完全一致ホットプレフィックスキャッシュを通過します。ルーターがプレフィックスシャードとレプリカを選択します。レプリカはインデックス検索を1回実行し、高速拒否セットに含まれるエントリを削除し、安定IDで重複を排除して上位10件を返します。このパスに生のログクエリ、分散集約、または完全ソートを含めてはなりません。
キャッシュキーには、ロケール、正規化されたプレフィックス、件数制限、ポリシーバージョン、アクティブなインデックスバージョンが含まれます。これにより、古いランキングやポリシーのレスポンスが有効化後も残存するのを防ぎます。空のプレフィックスおよび1文字のプレフィックスは、トラフィックと候補セットが非常に幅広いため、別途事前計算されます。ネガティブキャッシュによって存在しないプレフィックスを保護できますが、そのTTLによって新たに適格となったサジェストが鮮度目標を超えて隠蔽されてはなりません。
ステップ6: ローカリティとホットプレフィックスに応じたシャーディング
まずロケールでパーティショニングし、次にプレフィックス範囲または最初の数文字の正規化文字のハッシュによってパーティショニングします。範囲パーティションはローカリティを維持しますが、ホットシャードを作成します。完全なハッシュ化は負荷を分散しますが、追加のルーティングメタデータが必要になる場合があります。実用的なルーターは、プレフィックス範囲からシャードへのバージョン管理されたマップを保持し、関係のない範囲を再構築することなく、特定の人気のある先頭1文字のようなホットレンジを分割できます。
各シャードを障害ドメイン間でレプリケーションし、正常なローカルレプリカにルーティングします。プレフィックスごとのQPS、キャッシュヒット率、シャードCPU、検索p99、およびインデックスバイト数を記録します。レプリカを追加することで読み取り負荷を解決し、ホットレンジを分割または分離することで負荷の偏りを解決します。シャードが利用できない場合は、明示的な鮮度メトリクスを含むキャッシュバージョンまたは空のリストを返します。他ロケールのサジェストを決して返してはなりません。
ステップ7: 2つの鮮度クロックを満たす
ベースインデックスは15分ごとに再構築されます。小規模な最近のトレンドオーバーレイは、より短いウィンドウを集約し、ベースの候補と制限されたセットをマージできますが、同じプライバシーおよびセーフティゲートを通過する必要があります。そのオーバーレイに障害が発生した場合は、エンドポイント全体を利用不可にするのではなく、最後に確認された正常なベースインデックスを提供します。
ポリシーによる削除は、1分目標で個別に配布される拒否セットを使用します。配信レプリカは検索後に拒否されたIDをフィルタリングし、キャッシュキーにはそのバージョンが含まれます。次のベースビルドでそれらは完全に削除されます。この2つのクロックを持つ設計により、決定論的なベース公開を維持しながら、緊急削除のために大きなアーティファクト全体を再構築することを回避できます。
ステップ8: ランキング、安全性、運用の検証
負荷テストでは、ホットな1文字プレフィックス、コールドキャッシュの起動、レプリカの喪失、バージョンの有効化を含め、150,000のピークQPSで観測されたプレフィックス長とロケールの分布を再現します。サービス境界でのp99が50ミリ秒未満であること、エラー率が制限されていること、レスポンスごとにチェックサムが混在していないこと、およびサンダリングハード（thundering herd）なしで回復することを確認します。
オフライン評価では、Top-Kの関連性、カバレッジ、重複率、ロケールの正確性、禁止コンテンツの再現率、およびバージョン間の安定性をカバーします。オンライン実験では、ゼロヒット率、レイテンシ、苦情、露出の偏りに対するガードレールを設けつつ、検索完了率と下流の結果品質を測定します。表示順位がクリックに影響するため、クリック率の向上だけでは不十分です。
運用訓練には、有害なイベントバッチの混入、ビルドの失敗、サイズ超過のアーティファクト、ホットシャード、古い拒否セット、不完全なレプリカロールアウト、ランカーの性能劣化が含まれます。すべてのアラートは安全なアクションに対応している必要があります（有効化の保留、最後に確認された正常バージョンへのフォールバック、オーバーレイの分離、レンジの分割、または緊急拒否ルールの有効化）。
質の高い回答例
「匿名でロケール固有のプレフィックス補完と10件の結果から始めます。5000万人のユーザー、10回の検索、検索あたり5回のリクエストから、1日あたり25億回のリクエスト、平均約28,900 QPSとなります。提示された150,000のピークに合わせてキャパシティを計画し、Trieのメモリを推測するのではなく、シリアライズされたインデックスサイズを測定します。
データパスと配信パスは分離されています。検索完了イベントはストリームに入ります。集約によってユニークユーザー数、鮮度、結果品質のシグナルが生成されます。候補は最小頻度、不正、プライバシー、モデレーションのゲートを通過し、ランカーが正規化されたプレフィックスごとに制限された上位リストを書き込みます。すべてのアーティファクトは、データのウォーターマーク、正規化、ランカー、ポリシーのバージョンを記録します。
配信レプリカはイミュータブルなインデックスバージョンを保持します。古いバージョンの横で新しいバージョンをロードして検証した後、ルーティングがアトミックに切り替わり、ロールバックも可能です。リクエストはプレフィックスとロケールを正規化し、バージョン管理されたキャッシュを確認し、プレフィックスシャードにルーティングし、1回の検索を実行し、高速拒否セットを適用して10件を返します。ホットな1文字の範囲には専用のキャッシュが割り当てられ、個別に分割できます。
ベースの再構築は15分の目標を満たします。ゲート管理された小規模なトレンドオーバーレイによって鮮度を向上させることができ、緊急削除には1分の拒否レイヤーを使用します。どちらに障害が発生しても、最後に確認された正常なベースインデックスを壊すことはありません。150,000 QPSで実際のプレフィックス分布をテストし、p99、鮮度、キャッシュヒット率、シャードの偏り、関連性、ロケール漏洩、セーフティ再現率、ロールバック時間を追跡します。」
よくある間違い
- キーストロークごとに生ログをクエリしてソートする → 履歴の増加に伴って処理が増大し、テールレイテンシが予測不能になる → 制限されたTop-Kリストを事前計算し、オンライン検索を定数時間・一定範囲に保つ。
- データ構造を『Trie』とだけ答えて終了する → ランキング、公開、シャーディング、安全性、復旧が抜け落ちる → 構築と配信の両方のライフサイクルを説明し、表現方法をベンチマークする。
- 勝手に想定したノードサイズからRAMを見積もる → 実際のバイト数はエンコードとプレフィックス共有によって決まる → 代表的なデータをシリアライズし、アーティファクトサイズと検索レイテンシを測定する。
- プレフィックスのみでキャッシュする → ロケール、ポリシー、インデックスバージョンが混ざり、誤った結果を返したり保持したりする → 結果に影響を与えるすべてのバージョンをキャッシュキーに含める。
- インプレース（その場）で公開する → 読み取り側が不完全または混在したデータを参照する → イミュータブルなアーティファクトを構築し、検証し、並行してロードし、アトミックに有効化する。
- 人気度のみを適格性ルールとして使用する → 稀な個人情報、不正操作、または有害なテキストが表面化する可能性がある → ユニークユーザー閾値、不正防止、プライバシー、モデレーションのゲートを適用する。
- 緊急削除のためにすべてを再構築する → 安全性のデッドラインが大規模なバッチジョブに依存してしまう → 高速拒否レイヤーを配布し、次回のベースビルドで完全に削除する。
- クリック率（CTR）をバイアスのない関連性として扱う → 表示順位がクリックに影響する → ガードされた実験とオフライン評価および安全性メトリクスを組み合わせる。
フォローアップの質問と回答
フォローアップ1: あいまい（ファジー）マッチをどのように追加するか？
完全プレフィックス検索を最初の低コストな生成器として維持します。最小の長さに達した後や、完全一致のカバレッジが低い場合にのみファジー生成をトリガーし、編集距離と候補数を制限し、1つのランカーとモデレーションポリシーで統合します。ファジー展開はCPU使用率を増加させ、ポリシーに抵触する異体字を取得する可能性があるため、Unicode対応の距離計算と敵対的入力をベンチマークします。
フォローアップ2: パーソナライズをどのように追加するか？
グローバルな候補を取得した後、認可された少数の個人用候補セットをブレンドします。キャッシュはその境界まではグローバルのままであり、最終的なレスポンスはユーザー固有のものとなるため共有キャッシュには含めません。ランキング特徴量を追加する前に、同意、保持、削除、機密クエリの除外、特徴量取得のタイムアウト、およびグローバルのみへのフォールバックを定義します。
フォローアップ3: 1つのロケールがメモリに収まらなくなった場合はどうするか？
測定されたバイト数とQPSを使用してプレフィックス範囲を分割し、バージョン管理されたルーティングマップを更新します。トップレベルのホットプレフィックスは専用レプリカに保持し、コールドレンジについてはp99が許容範囲内であればメモリマップトファイルまたはリモートインデックスの使用を許可します。読み取り側がインプレースのキー移行に依存しないよう、アーティファクトのバージョンごとにリバランスします。
フォローアップ4: 数秒以内のニュース速報をどのようにサポートするか？
ベースビルド全体の周期を盲目的に短縮してはなりません。信頼できる候補ソース、高い適格性閾値、即時モデレーション、TTL、キルスイッチを備えた、厳密に制約されたストリーミングオーバーレイを追加します。固定の候補予算内でベース結果とマージします。その鮮度やポリシーのウォーターマークが古い場合は、オーバーレイを破棄して最後に確認された正常なベースを提供します。
フォローアップ5: プライバシー要求を受けた後、クエリをどのように削除するか？
データモデルに従って適格な生イベントと集約データを削除または廃棄標識（tombstone）を設定し、サジェストIDを高速拒否レイヤーに追加し、ポリシーバージョンを通じて影響を受けるキャッシュエントリを無効化し、修正された入力からベースアーティファクトを再構築します。機密テキストを再度ログに記録することなく、リージョン間での伝播時間を監査します。