43

私は最近、簡単な質問にうまく答えずに就職の面接を失敗させました：LinkedInのようなサイトは、ページに表示されるすべての人（たとえば、人の検索結果、働く人のリスト）までの関係距離（1st / 2nd / 3rd）をどのように効率的に表示しますか会社などで）？

<編集>私は解決策の本質的な「トリック」を手に入れました。「私からの距離」を見つけることは一般的な操作です（たとえば、1ページで20倍以上、ログインセッションごとに100）。 X "、それをキャッシュし、他の操作をはるかに安くするために、キャッシュされた部分的な結果を何度も再利用します。また、「すべての第3レベルの接続をキャッシュする」と、RAMとCPUのコストが高すぎるため、部分的な結果は第2レベルの接続になる可能性が高いと推測しました。</編集>

しかし、この洞察をソリューションに変換しようとすると、サイト上のすべての人の第2レベルの接続の永続的なキャッシュを作成するという厄介な答えを思いつきました（これは、パフォーマンスが非常に高く、維持するのが複雑でした）。技術的にほとんど意味をなさない方法でブルームフィルターを使用することへの不可解な迂回。そのような答えの後で私は自分自身を雇うことはなかっただろう！

後で、面接のプレッシャーを頭にかけずに問題について考えたとき、私はより合理的な答えを思いついた。

  • ユーザーIDのバッチごとに第1レベルの接続を取得するための非常に高速な方法を構築します（バッチサイズは最大1000？）。これはおそらく、ネットワーク全体の第1レベルの接続をメモリにキャッシュできる多数のRAMサーバーの専用クラスターを意味します。幸いなことに、5,000万人のメンバーx平均。メンバーあたり100接続xメンバーIDあたり4バイト=RAMにキャッシュするための<25GB。これは手頃な価格のハードウェアで実行できます。また、1日あたりの変更数は1％未満になるため、キャッシュを最新の状態に保つことはそれほど難しくありません。（「大量のランダムI / O」アクセスパターンはリレーショナルDBのパフォーマンスを低下させるため、リレーショナルデータベースはこのキャッシュを実装するのにおそらく悪い選択であることに注意してください。）

  • ユーザーがログインしたら、すべての第1レベル接続の第1レベル接続をフェッチして、第2レベル接続をキャッシュし、ハッシュテーブルに固定します（キー=第2レベルID、値=接続する第1レベル接続の配列）君）。また、第1レベルの接続もキャッシュして、リモートキャッシュサーバーへの1回のコールバックで第1レベルと第2レベルの両方をプルバックできるようにします。ユーザーIDは簡単にパーティション化できるため、memcachedのような分散キャッシュがこれに適している場合があります。

  • 任意のユーザーIDについて、それが「ネットワーク」にあるかどうか、およびそれがユーザーとどのような関係にあるか（1番目、2番目、3番目）を確認するには、次のようにします。

    1. IDが第1レベルの接続にある場合は、停止します。
    2. キャッシュされた第2レベルの接続ハッシュテーブルでIDを検索してみてください。見つかった場合は、接続している接続の配列を返します。
    3. IDの第1レベルの接続をフェッチし、それぞれに対して手順2を繰り返します。すべての結果を1つの配列に集約し、それらを返します。
    4. <EDIT>をバッチ実装にリファクタリングして（「私からN人の異なるユーザーまでの距離を調べる」）、最大N個のリモート呼び出しを行うことなく、手順3のすべてのリモート結果を取得できます。</編集>

しかし、これにはもっと良い答えがあると確信しています。君は？さらに挑戦したい場合は、インタビューの状況をシミュレートしてみてください（Webでソリューションを検索することはできません）。

LinkedInが今日実際にどのようにそれを行っているかに関係なく、質問は最適な解決策に関するものであったことに注意してください。

4

6 に答える 6

6

このタイプのトラバーサルを最適化するために、小さな世界のネットワークに関する公理を活用できる場合があります。

スモールワールドネットワークは、他のノードの非常に密な相互接続を表す「ハブ」によって特徴付けられます。ネットワーク内のほとんどのノードは、通常、数ホップ以内でトポロジ的に近いノード（1〜4ホップ離れた場所）に接続するか、1つ以上のそのようなハブを経由してルーティングします。これが、小さな世界のネットワークがそのように動作する主な理由の1つです。

于 2009-10-12T20:09:41.817 に答える
4

興味深いことに、1970年代の技術は、これをモデル化するという公正な仕事をするでしょう。ネットワークデータベースモデルは、このタイプの関係を効率的に管理します。

アドホッククエリやデータモデルの保守という点では効率的ではないため、リレーショナルデータモデルの台頭により支持されなくなりました。

于 2009-10-12T20:01:50.100 に答える
1

あなたがそれについて考えるならば、SQLでこれを行うことは非常にプロセッサを集中的に使うかもしれません。

それと、最終的にはあらゆる場所で使用され、そのスペースが比較的安価であるという事実を考えると、言語の好みに応じて、Lucene（またはLucene.NET）を使用してインデックスを作成することをお勧めします。この方法でいくつかのことができます。

ツリータイプのデータ構造を作成し、インデックスを再帰的にクロールして、その時点でのニーズに応じて、すべての親ノードまたは子ノードとその親ノードまたは子ノードを探すことができます。

または、作成されたすべての関係を書き出すこともできます（スペースは安価な概念です）。これは、ライトワンスプロセスになります（これは、それほど頻繁に更新することはありません）。リレーションシップが作成または取り消されると、インデックスの更新をキューに入れます（単一のリクエストの書き込み用に開きたくないため、キューに入れます...インデックスの更新をバッチ処理します）。次に、この非常にフラットな構造を読み取って、問題のIDを取得できます。

IDを手元に置いて（どの検索タイプから実行しても）、DBに移動して周囲の必要な情報を取得できます。次に、出力をキャッシュして、非常に高速な検索、データベースクエリ、データ構築をさらに最小限に抑えます。ただし、キャッシュから取得した場合はさらに高速になります。

Webファーム全体の集中キャッシュには、Velocity、MemCached、MemCachedWin32などを使用します。

于 2009-10-12T19:54:07.697 に答える
1

テーブルの構造やシステムの複雑さはわかりませんが、再帰CTEを使用した単純なSQLServerの例を次に示します。

DECLARE @People table (PersonID int, Name varchar(10))
DECLARE @Network table (PersonID int, NetworkedPersonID int)
INSERT INTO @People VALUES (1,'AAA')
INSERT INTO @People VALUES (2,'BBB')
INSERT INTO @People VALUES (3,'CCC')
INSERT INTO @People VALUES (4,'DDD')
INSERT INTO @People VALUES (5,'EEE')
INSERT INTO @People VALUES (6,'FFF')
INSERT INTO @People VALUES (7,'GGG')
INSERT INTO @People VALUES (8,'HHH')
INSERT INTO @Network VALUES (1,2)
INSERT INTO @Network VALUES (1,3)
INSERT INTO @Network VALUES (2,5)
INSERT INTO @Network VALUES (2,7)
INSERT INTO @Network VALUES (4,8)
INSERT INTO @Network VALUES (7,8)
INSERT INTO @Network VALUES (7,3)
INSERT INTO @Network VALUES (8,9)
DECLARE @TargetPersonID  int
SET @TargetPersonID=1

;WITH NetworkLevels AS
(   SELECT
        NetworkedPersonID,1 AS NetworkLevel
        FROM @Network
        WHERE PersonID=@TargetPersonID
    UNION ALL
    SELECT
        n.NetworkedPersonID, l.NetworkLevel+1
        FROM @Network                n
            INNER JOIN NetworkLevels l ON n.PersonID=l.NetworkedPersonID
    WHERE l.NetworkLevel<=2
)
SELECT * FROM NetworkLevels

出力：

NetworkedPersonID NetworkLevel
----------------- ------------
2                 1
3                 1
5                 2
7                 2
8                 3
3                 3

(6 row(s) affected)
于 2009-10-12T20:20:58.767 に答える
1

実装する

DistanceCategory(A,B): { 1, 2, 3+}

接続が双方向であるという事実を使用してください。

いくつかのKVの痛みに、ソートされたリストとして第1レベルの接続を保存します。

Key: [UserFromId,UserToId].
Value: UserToId

擬似コード：

DistanceCategory(A,B)
{
    if ( exists([A,B]) )
        return 1;
    if ( firstCommonElement(getAll([A,B]), getAll([A,B])) != null )
        return 2;
    return 3;
}

複雑さ：O（C1 + C2）。C1、C2-両方のユーザーの接続数。

于 2015-10-23T08:58:51.117 に答える
0

LinkedInのデータは大きな巨大なグラフとして表されていませんか？そして、人がログインすると、システムはそのノードを処理し、次に3レベルの幅優先探索を実行することにより、システムはこれらのノードをセットとして（どのレベル情報とともに）保持し、人がWebページに表示されたときに、システムはこのノードセットを検索し、関係距離を示します。

これは私の推測です。何が実用的でないのか、お気軽にご指摘ください。

于 2011-06-08T12:12:31.953 に答える