あるソーシャルアプリ企業が、ユーザー間のフォロー関係・友人の友人推薦・不正アカウントのつながり検出を行う基盤を構築します。データは「誰が誰とつながっているか」という関係性そのものを多段階（5〜6ホップ）でたどるクエリが中

Question

あるソーシャルアプリ企業が、ユーザー間のフォロー関係・友人の友人推薦・不正アカウントのつながり検出を行う基盤を構築します。データは「誰が誰とつながっているか」という関係性そのものを多段階（5〜6ホップ）でたどるクエリが中心で、リレーションは数億エッジに及びます。低レイテンシで多ホップの関係探索を実行でき、運用負荷が最小になるデータストアはどれですか。

Accepted Answer

正解: Amazon Neptune を使い、Gremlin または openCypher で多ホップのグラフトラバーサルを実行する。多ホップの関係性探索はグラフデータベースの中核ユースケースです。Amazon Neptune は数十億エッジのグラフをネイティブに保持し、Gremlin・openCypher で5〜6ホップのトラバーサルを低レイテンシかつ少ない運用負荷で実行できます。フルマネージドでインデックス管理も自動化されます。

選択肢Aの Amazon DynamoDB は隣接リストで関係を表現できますが、各ホップごとにアプリ側でGSIクエリを繰り返す必要があり、多ホップではクエリ回数が指数的に増え運用・性能とも不利です。
選択肢Cの Amazon DocumentDB の $graphLookup は限定的なグラフ探索で、数億エッジ・多ホップでは性能が劣化しグラフ専用ではありません。
選択肢Dの Amazon RDS for PostgreSQL の再帰CTEは多段JOINとなり、数億エッジ規模では計算量が爆発し低レイテンシを満たせません。

Answer

Amazon DynamoDB で隣接リストパターンを用い、各ホップごとに GSI クエリを繰り返す構成にする — 隣接リストで関係を持てるものの、多ホップ探索ではホップごとにアプリがGSIクエリを繰り返す必要があり、5〜6ホップでクエリ回数が指数的に増大して低レイテンシと低運用負荷を両立できないため不適切です。

Answer

Amazon DocumentDB に関係をネストしたドキュメントで保持し、$graphLookup 集計で探索する — $graphLookupで簡易なグラフ探索は可能ですが、本来はドキュメントDBであり数億エッジ・5〜6ホップ探索では性能が劣化し、グラフ専用エンジンのような最適化がないため要件を満たせません。

Answer

Amazon RDS for PostgreSQL で再帰共通テーブル式（再帰CTE）を用いて関係を多段 JOIN する — 再帰CTEで関係をたどれますが、数億エッジの多段JOINは計算量が急増して低レイテンシを実現できず、グラフ探索に最適化されていないため大規模多ホップ要件には不適切です。

解説

解説