問題とスコープ
グローバルな周辺スポット検索サービスを設計します。カタログには5,000万件のレストラン、ショップ、公共施設が含まれます。ユーザーは現在地、500mから50kmの検索半径、カテゴリ、営業時間のフィルターを指定し、最も近い20件の結果を受け取ります。検索トラフィックはピーク時で秒間200,000リクエストに達します。施設の新規作成、移転、閉店はピーク時で秒間100件の更新です。読み取りレイテンシはp99で150ミリ秒未満を維持する必要があります。
この問題では、施設は変化の遅い静的エンティティとして扱います。ドライバー、配達員、友人の秒単位の位置情報、マッチング、排他割り当ては、別の動的位置情報システムの対象です。距離とは地球表面上の地理的距離を意味します。ルート所要時間、パーソナライズ、広告オークションはコアスコープ外です。すべての数値とSLOは面接上の前提条件です。
中心的な課題は2次元の半径クエリです。緯度と経度に対する通常のB-treeでは、クエリの円内に含まれるすべての行へ直接ジャンプすることはできません。推奨されるパターンは、まず空間インデックスまたは離散グリッドを使用して候補のスーパーセットを作成し、次に正確な距離を計算し、フィルタリング、ソート、切り捨てを行うことです。セルの一致は粗いフィルターにすぎず、同一セルや隣接セルを共有していることは、施設が半径内にあることを証明しません。
面接官が評価するポイント
第一の評価基準は、コンポーネントの前に正当性を定義することです。すべての結果は半径内に収まり、フィルターを通過し、決定論的な近着順（近い順）で表示される必要があります。候補セットはセルの境界をまたぐ施設を網羅しなければならず、正確な距離によって粗い結果を検証する必要があります。ユーザーのgeohashのみをクエリすると、任意のセルの境界を越えた数十メートル先の施設を見落とすことになります。
第二の評価基準は、更新パターンに応じたインデックスの選択です。静的な施設であれば、PostGIS GiST、R-tree、またはデータベース固有の距離インデックスから始めることができます。読み取りトラフィックとグローバルルーティングによって妥当性が認められる場合は、施設をH3、S2、またはgeohashセルにマッピングできます。単に「Redis GEOを使用する」と言うだけでは、円のカバー範囲、解像度、ホットスポット、正確な距離の説明にはなりません。
第三の評価基準は、空間的な偏り（スキュー）の認識です。海洋や過疎地域のセルはほぼ空ですが、都心部の1つのセルは極端にホットになる可能性があります。均一な緯度・経度の範囲は、均一なシャードを生み出しません。実用的な設計では、粗い空間プレフィックスでルーティングし、密なセルを分割し、読み取りの多いセルにレプリカを追加します。大きな半径のクエリはシャードをまたぐため、1回の検索が常に1つのノードにヒットするとは想定できません。
最後に、ページネーション、整合性、障害処理が調和している必要があります。距離ページネーションの場合、ユーザー座標、フィルター、カタログバージョン、最後の距離、施設IDがカーソル契約の一部となります。更新やシャードのタイムアウトによって結果セットが変化する可能性があります。優れた回答では、スナップショットセマンティクスまたはベストエフォートセマンティクスを宣言し、部分的な結果であることを識別できるようにします。
回答前に明確にすべき質問
- 位置情報は静的ですか、それとも継続的に移動しますか？ 秒間100件の更新ピークであれば、キャッシュと非同期インデックス作成が可能です。移動するエンティティには、より厳密な鮮度、書き込みに最適化されたインデックス、マッチングの整合性が必要です。
- 「最も近い」とは地理的距離ですか、それとも移動時間ですか？ この設計では地理的距離を使用します。移動時間には道路グラフと個別のETAサービスが必要であり、通常は絞り込まれた粗い候補セットに対して適用されます。
- 結果は完全である必要がありますか、それともおおよその候補20件で許容されますか？ この問題では、正確な半径フィルタリングと、インデックスされた施設の中から決定論的に最も近い20件を返すことが求められます。セルは候補の生成にのみ使用します。
- 営業状態の鮮度はどの程度必要ですか？ 位置情報とカテゴリは分単位の伝播を許容できます。一時的な閉店に秒単位の鮮度が必要な場合は、静的カタログに混合した単一の保証を与えるのではなく、個別の短いTTLオーバーレイで保持します。
- 深いページネーション（deep pagination）は必要ですか？ 周辺検索では通常、数ページしか必要としません。この設計では、1つの検索セッションの上限を100件とします。50km以内のすべての結果をエクスポートするには、非同期APIまたは地域ブラウズAPIが必要です。
- クロスシャード障害時に部分的なデータを返してもよいですか？ 探索APIは、欠落したリージョンとともに
partial=trueを返すことができます。厳格な呼び出し元は失敗として再試行できます。部分的なデータを完全な最近傍セットとして提示してはなりません。
30秒の回答まとめ
「カタログの書き込みパスと検索パスを分離します。バージョン管理された施設レコードが信頼できる情報源（Single Source of Truth）となるカタログに入り、空間インデックスを非同期に更新します。各施設は正確な座標、ルーティング用の粗いセル、検索解像度のセルを保持します。クエリは半径とフィルターを検証し、H3、S2、geohashのカバリングまたはPostGISの距離インデックスを使用して候補のスーパーセットを取得します。正確な球面距離を計算し、フィルターを適用し、(distance, place_id)でソートした上で上位20件を取得します。
粗いプレフィックスによってシャードへルーティングします。密なセルは分割可能とし、セルをまたぐクエリは並列で制限された数のシャードにアクセスした後にグローバルなtop-kマージを行います。キャッシュキーにはセル、半径バケット、フィルター、カタログバージョンを含め、バージョン付きの移動では古いセルと新しいセルの両方を無効化します。カーソルには元のクエリとカタログスナップショットをバインドします。正当性とp99を測定しながら、境界、日付変更線、極点、ホットな都市、移転、シャードのタイムアウト、古いキャッシュを検証します。」
ステップごとの詳細解説
ステップ1：API、モデル、不変条件の確定
APIは、境界付けられた半径、有効な座標、承認されたフィルター、小さなページサイズを受け入れます。レスポンスには、計算された距離、カタログバージョン、完全性、および継続カーソルが含まれます。
GET /v1/places/nearby?lat=&lng=&radius_m=&category=&open_at=&limit=&cursor=
Place {
place_id, lat, lng, search_cell, routing_cell,
category, status, hours_version, location_version, updated_at
}
Cursor {
query_hash, catalog_version, last_distance_m, last_place_id
}4つの不変条件を維持します。すべての結果が半径とフィルターを満たすこと、候補生成で円内のポイントを取りこぼさないこと、最終的な順序が(distance_m, place_id)であること、そして古い位置バージョンが新しいバージョンを上書きできないことです。座標は1つの宣言された参照系を使用し、無効な範囲を拒否し、内部的にはメートル単位を使用します。
ステップ2：ターゲットを満たす最もシンプルな空間インデックスの選択
初期バージョンでは、空間インデックスを持つリレーショナルデータベースを使用できます。半径クエリは、インデックス可能な境界形状を使用してセットを縮小し、次に正確な距離関数を使用してフィルタリングします。公式のearthdistanceドキュメントには、インデックス可能なボックスには要求された大圏距離の外側にあるポイントも含まれると明記されているため、2回目の距離チェックが必要です。この候補スーパーセットのルールは特定のベンダーに依存しません。
1つのデータベーストポロジーでグローバルな読み取りトラフィックを処理できない場合や、明示的な空間ルーティングが必要な場合は、各施設を固定解像度のH3、S2、またはgeohashセルにエンコードします。クエリの円をセルのカバーセットに変換し、各セルの転置リストを読み取り、重複を排除して絞り込みます。H3の階層構造は解像度を効率的に変更できますが、親セルと子セルの間の地理的包含関係には近似に関する懸念があります。最終的な包含判定は、依然として正確なポイント間検証によって行われます。
単一の固定解像度には相反する問題があります。大きなセルは候補数を肥大化させ、微小なセルは50kmのクエリで過剰な数のセルを列挙することになります。半径に基づいて事前定義された少数の解像度セットから選択し、施設ごとにそれらのレベルを事前計算するか、大きな半径をより粗いインデックス経由でルーティングします。候補の増幅率、ファンアウト、p99負荷テストによって適切なレベルを選択します。
ステップ3：候補検索とグローバルtop-kの実行
クエリサービスは、中心だけでなく交差するすべてのセルをカバーするように、円を候補セルに変換します。全体的なデッドラインとシャードごとのバジェットのもとで、各セルから粗くフィルタリングされた施設IDと座標を並列に読み取ります。place_idで重複を排除し、正確な地理的距離を計算し、円外のポイントを除去し、権限、状態、カテゴリのフィルターを適用します。
各シャードはローカルのtop kを返すことができますが、切り捨てには証明が必要です。すべてのシャードが同一の最終距離でソートし、少なくともグローバルのkを返す場合、シャード内のk+1番目のアイテムがグローバルのtop kに入ることはありません。アグリゲーターはサイズkのmax heapを使用してマージします。処理量は返された候補数に対して線形であり、マージメモリはO(k)です。
大きな半径や過密な都心部では、候補が多すぎる状態になる可能性があります。サービスは候補バジェットを設定しますが、黙って切り捨てて正確性を主張することはできません。より細かいグリッドを選択する、カテゴリフィルタリングをプッシュダウンする、20件の結果が得られ、かつ未探索のすべての領域からの最小可能距離が現在の20番目の結果を超えるまでリング状に拡張する、あるいは明示的なリソース制限エラーを返すなどの対応をとります。
ステップ4：シャーディング、ホットスポット、キャパシティの設計
空間クエリのたびにブロードキャストが発生してしまうplace_idによるランダムシャーディングではなく、粗いrouting_cellを使用してセルディレクトリをシャードにマッピングします。ディレクトリサービスがルーティングテーブルとエポックを管理します。クエリは1つのエポックを使用し、ルーティング変更時には再試行するため、セル分割によってギャップが生じることはありません。
ID、座標、フィルターフィールド、オーバーヘッドを含む1つの検索インデックスレコードを128〜256バイトと見積もると、5,000万件のレコードには、レプリケーション、複数解像度、データベースオーバーヘッドを除いて約6〜12 GiBが必要です。この規模であればパーティショニングして読み取り最適化ノードから配信できますが、特定のデータベースが目標を満たすことを保証するものではありません。
200,000 QPSで、平均ファンアウトが6回のセル読み取りと仮定すると、バックエンドは毎秒約120万回のセル読み取りを処理することになります。キャッシュとバッチ読み取りによって操作を削減する必要があります。読み取りのホット度に基づいてレプリカを追加し、密なセルを子セルに分割します。疎なセルのマージはストレージとルーティングのみを変更し、正当性は依然として幾何学的なカバリングによって担保されます。
ステップ5：書き込み、キャッシュ、整合性の収束
所有権の検証後、プレイスサービスはソースレコードを更新し、location_versionをインクリメントします。変更イベントには古いセル、新しいセル、バージョンが含まれます。インデックスコンシューマーは、古いセルを削除する前に新しいバージョンを新しいセルに書き込みます。読み取り側はバージョンによって重複排除を行うため、リプレイが安全になり、削除の遅延によって古いデータが優先されるのを防ぎます。シャードをまたぐ移動ではインデックスの遅延が一定範囲に抑えられ、即時分散トランザクションを必要とせずにバージョンによって収束します。
セルから候補IDへのキャッシュと、完全な施設オブジェクトのキャッシュという2つのキャッシュレイヤーを使用します。候補キーには、インデックスバージョン、セル、カテゴリ、状態バケットが含まれます。最終レスポンスのキャッシュには、座標バケット、半径バケット、フィルター、カタログバージョンも含める必要があるため、通常はヒット率が低くなります。更新によって古いセルと新しいセルの両方が無効化され、短いTTLによって無効化イベントのロストの影響を抑えます。
open_atが毎分変化する場合でも、毎分すべての空間キャッシュを破棄してはなりません。静的な候補と営業ルールをキャッシュし、クエリ時にルールを評価します。一時的な閉店は、最新の小さなオーバーレイに保持します。これにより、営業状態の頻繁な変動によって地理インデックスが再構築されるのを防ぎます。
ステップ6：ページネーションと障害セマンティクスの定義
カーソルは座標、半径、フィルター、catalog_versionをハッシュ化し、最後の(distance_m, place_id)を保存します。次ページ呼び出しで異なるクエリパラメータが渡された場合は拒否します。短期間のスナップショットがサポートされている場合は、同じカタログバージョンを読み取ります。ベストエフォートAPIの場合は、同時更新によって重複や欠落が発生する可能性があることをドキュメントに明記し、クライアント側でIDを重複排除できるようにします。
各シャードには、エンドツーエンドの目標である150ミリ秒よりも短いデッドラインが設定されます。1つのシャードがタイムアウトした場合、欠落したシャードにより近い施設が含まれている可能性があるため、そのレスポンスをグローバルで最も近い20件と呼ぶことはできません。探索APIはpartial=true、欠落したセル、再試行カーソルを返すことができます。厳格なクライアントには、明確な利用不可（unavailable）の結果を返します。サーキットブレーカーはグローバルインデックス全体ではなく、障害が発生したシャードのみを分離します。
リージョン展開では、完全なローカル読み取りレプリカまたは地理的パーティションを優先する必要があります。越境ポリシーは施設のメタデータと監査を管理し、公開されている企業の座標であっても認可された調達が必要です。フェイルオーバーは十分最新のインデックスを持つリージョンのみを使用でき、as_ofを返す必要があります。障害発生時にカタログテーブルのフルスキャンにフォールバックすることはできません。
ステップ7：幾何学的反例と障害による検証
小規模なテストデータでは、ブルートフォース（総当たり）による正確な距離計算をオラクル（正解判定器）として使用します。ランダムなポイントと円を生成し、結果セットを比較します。セルのエッジやコーナー、東経/西経180度、極域、半径の境界線上に正確に位置するポイント、重複座標、結果ゼロ件、20位と21位が同距離の場合、セルをまたぐ移転などを対象にします。偽陰性（見落とし）がないこと、円外のポイントが含まれないこと、安定したタイブレークが行われることを検証します。
負荷テストでは、空の領域、通常の都市、極端に密集したホットスポットを個別にカバーします。セルのファンアウト、候補増幅率、正確な距離の計算回数、キャッシュヒット率、シャードのp95/p99、マージ時間、エンドツーエンドのp99を測定します。障害テストには、低速なセルレプリカ、ルーティングエポックの変更、無効化のロスト、コンシューマーのリプレイ、中断されたシャード間移動、リージョンフェイルオーバーが含まれます。
シャドウクエリを使用してロールアウトします。トラフィックの少量のサンプルを新しいインデックスと信頼できる古い実装の両方に送信し、上位20件のセット、順序、距離、欠落率を比較します。レイテンシの改善を理由に偽陰性を許容することはできません。正しい周辺スポットを取りこぼすことは、インデックスの正当性の欠陥です。
模範解答の例
「まず、このスコープを移動するドライバーのマッチングではなく、静的な施設の検索に限定します。施設カタログは正確な座標と単調増加する位置バージョンを保存し、空間インデックスにイベントを発行します。読み取り処理では、テーブル全体を緯度経度の式でソートすることはありません。円を完全にカバーするセルに変換します。PostGISの空間インデックスから開始し、グローバルトラフィックで明示的な空間ルーティングが必要になった段階でH3、S2、またはgeohashを導入できます。セルは粗いフィルタリングのみを行い、正確な地理的距離によって包含を決定し、距離と施設IDによる安定したソートを行います。
粗いセルによってシャードへルーティングします。密なセルは分割され、読み取りの多いセルにはレプリカが追加されます。クエリは制限されたシャードを並列に読み取り、それぞれがローカルのtop-kを返し、アグリゲーターがグローバルのtop-kを生成します。候補が多すぎる場合は、より選択的なフィルタリングやリング状の拡張をトリガーし、黙って切り捨てることはしません。セル候補と施設オブジェクトはインデックスバージョンとともにキャッシュされます。移動時は両方のセルが無効化され、位置バージョンによってリプレイが収束します。
カーソルは座標、半径、フィルター、カタログバージョン、最後の距離/施設IDをバインドします。シャードのタイムアウトはグローバルな最近傍結果を証明できないことを意味するため、探索APIはレスポンスに部分データであることを示し、欠落セルを明記します。一方、厳格なAPIはエラーを返します。検証にはブルートフォース距離計算をオラクルとします。ホットな都市での負荷テストや障害テストで150ミリ秒のp99を証明する前に、ランダム比較や、セルのエッジ、日付変更線、極域、タイブレーク、移動、ルーティング変更をターゲットにしたケースによって正当性を証明します。」
よくある間違い
- 中心のgeohashのみをクエリする → セル境界をまたぐ円で近隣スポットを取りこぼす → 交差するすべてのセルを読み取り、正確な距離を検証する。
- 隣接セルをすべて半径内として扱う → 離れたセルの角は半径を超える可能性がある → グリッドは候補用に使用し、包含判定には球面距離を使用する。
- 施設IDでランダムにシャーディングする → すべての周辺検索がグローバルにブロードキャストされる → 粗い空間プレフィックスでルーティングし、ホットセルを分割またはレプリケーションする。
- 単一の最も細かい解像度を使用する → 小半径の精度を優先すると、大半径でのファンアウトが爆発する → 測定値に基づいて選択された少数の制御されたレベルを使用する。
- 座標のみでキャッシュする → 半径、カテゴリ、カタログバージョンが互いに汚染される → 完全なクエリ契約とバージョンをキーに含める。
- 移動時に追加する前に削除する → コンシューマーの障害によって施設が一時的に消失する → 先に新しいバージョンを書き込み、後から古いセルを削除し、バージョンで重複排除する。
- シャードタイムアウト後にレスポンスを「最も近い20件」と呼ぶ → 欠落したシャードにより近い結果が含まれている可能性がある → 部分データであることを明記するか、厳格なリクエストは失敗させる。
- 密集した都心部のデータのみをテストする → 境界、極域、疎な領域のバグが見過ごされる → ブルートフォースオラクル、プロパティテスト、的を絞った幾何学的反例を使用する。
追加の質問と回答
追加質問1：システム全体にPostGISを使用しないのはなぜですか？
最初の選択肢としては優れています。空間データベースはすでに正しいインデックス候補と距離関数を提供しているため、チームはより少ないコンポーネントで信頼性の高いシステムをリリースできます。トラフィック、グローバルルーティング、ホットスポットの分離、またはコスト測定によってデータベーストポロジーが目標を達成できないことが示された場合にのみ、離散グリッドと個別の検索層を導入します。シャドウマイグレーションでは、レイテンシだけでなく完全な結果セットを比較する必要があります。
追加質問2：セルのカバリングが円内の施設を取りこぼさないことをどのように証明しますか？
隣接セル数を推測するのではなく、ライブラリの円またはポリゴンのカバリング操作を使用します。カバリングには余分なセルが含まれる場合がありますが、円と交差するすべてのセルが含まれている必要があります。正確な距離計算によって、後から偽陽性が除去されます。ランダムな円、セルの角、日付変更線、極域に対してフルスキャンオラクルと比較します。偽陰性が1件でもあればリリースをブロックします。
追加質問3：50kmのクエリが数千もの細かいセルをカバーする場合はどうしますか？
セル数が制限内に収まるように事前計算された粗いレベルに切り替え、プッシュダウンされたフィルターと正確な絞り込みに依存します。20件の結果が得られ、未訪問のすべての領域の最小可能距離が現在の20番目の結果を超えた時点で、リング拡張を停止できます。大きな半径のリクエストが依然としてリソースバジェットを超える場合は、黙って探索範囲を狭めるのではなく、リクエストを拒否するか非同期処理にします。
追加質問4：これを周辺ドライバーのマッチングに応用するにはどう変更しますか？
問題の性質が大きく変わります。ドライバーの位置情報には秒単位の書き込みと有効期限、都市やセルごとにパーティショニングされたインデックス、順不同の更新やゴーストドライバーへの対策が必要です。候補を取得した後のランキングには、ETA、ステータス、公平性が必要です。最終的な割り当てには、二重配車を防ぐためにバージョン付きの条件付き更新または単一のオーナーが必要であり、結果整合性の空間インデックスでドライバーを予約することはできません。
追加質問5：分単位で変化する営業状態によって無効化ストーム（invalidation storm）が発生しませんか？
静的な空間候補と動的な状態を分離します。セルキャッシュにはID、位置、カテゴリを保持します。クエリノードがopen_atに対する営業ルールを評価し、一時的な閉店は最新の小さなオーバーレイから取得します。位置またはカテゴリの変更のみが空間候補キャッシュを無効化します。オーバーレイの鮮度を監視し、利用できない場合は不明な状態またはビジネスで承認された縮退動作を返します。