LinkedIn上のユーザー間のパスの検索方法。

最近、私の同僚とソーシャルネットワークLinkedInについて議論し、興味深い質問を投げかけました。 このサイトには、アカウントから他のアカウントへのパスを表示する機能があります。 ステップの最大数は3です。 パスは次のようになります。あなた->あなたの友人->あなたの友人の友人->あなたが探している人。 問題は、このパスをどのように検索するかです。 他の人のアカウントにログインするたびに検索されますか？ または、すべてのユーザーのすべてのパスがすでに事前に計算されていますか？ 最初のオプションは多大な時間を費やし、2番目のオプションは大きなストレージコストをもたらします。







同僚と私は幸運なことに、今年5月にサンフランシスコで開催されたJavaOne 2008カンファレンスで、LinkedInの代表者がソーシャルネットワークのアーキテクチャについて2つのプレゼンテーションを行いました。 このブログは、レポートの優れた概要を提供し、 ここにその翻訳があります。 ところで、両方の投稿には、LinkedInの代表者の元のプレゼンテーションへのリンクが含まれています（誰かが興味を持っている場合）。



したがって、ユーザーグラフ全体が12 GBを占有し、常にRAMに保持されていることがわかりました。 ただし、各セッションの開始時に、特定のユーザーの個人用に共通のグラフからサンプルが作成されます。 彼の観点からソーシャルネットワークを見るようなものです。 このパーソナルグラフは、セッション全体でキャッシュに保存され、各ユーザーに約2 MBかかります。 ユーザーが友人に追加または削除などの変更を加えた場合にのみ更新されます。 他のユーザーから変更があった場合、グラフは変更されません。 明らかに、アカウントへのパスの検索はこの列で行われます。



したがって、LinkedInはハイブリッドオプションを実装しています。 パスの検索はオンザフライで行われますが、同時に情報の一部（パーソナルグラフ）が事前に構築され、メモリに保存されます。 好奇心itive盛な読者は、「完全なグラフの場合、個人のグラフの場合のように、ユーザーから探している人までのすべての可能な経路を整理する必要があります。 それでは、パーソナルグラフの利点は何ですか？」問題は、グラフが配列または線形リストで表されることです。 どちらの場合でも、要素を見つけるために、最悪の場合のシナリオでは、利用可能なすべての要素を反復処理します。 完全なグラフには、このようなアイテムが2,200万あります（LinkedInの登録ユーザー数です）。 個人用グラフのサイズは明らかにはるかに小さいです。 たとえば、ユーザー、友人、および友人の友人のそれぞれが30の連絡先を持っている場合、そのようなグラフのサイズは27931のみになります。さらに、パスが存在することを確認するために、考えられるすべてのパスを並べ替える必要はありません。必要なアカウントが列に存在するかどうかを確認してください。 実際、このグラフが最大ステップ数が3に等しい「ネットワークの個人ビュー」として作成された場合、その中にアカウントが存在するということは、3ステップ内のユーザーへのパスが存在することを自動的に意味し、一般的にそれを探すのが理にかなっています。



そして最後に、小さなオフトピック。 ソーシャルネットワーク全体のグラフには、2200万の頂点と1億2000万のエッジが含まれていることに驚きました。 これは、各アカウントに平均5.45人の友人がいることを意味します。 どうやらこれは、多くの人々が登録するが、そのアカウントを使用しないという事実によるものです。