Как сайты типа LinkedIn эффективно отображают отношения 1-го / 2-го / 3-го уровня рядом с именем каждого человека?

Question

Я недавно провалил собеседование при приеме на работу, плохо ответив на простой вопрос: как такие сайты, как LinkedIn, эффективно показывают расстояние отношения (1/2/3) от вас до каждого человека, отображаемого на странице (например, в результатах поиска людей, списке людей, работающих в компании и т. д.)?

Я получил существенную «хитрость» решения: поиск «расстояния от меня» - обычная операция (например, 20x + на одной странице, 100 на сеанс входа в систему), так что вы можете выполнить часть «расстояния от меня до X», кэшировать его, а затем повторно использовать этот частичный результат в кэше много раз, чтобы сделать другие операции намного более дешевыми. Я также предположил, что частичным результатом, вероятно, будут мои соединения второго уровня, потому что «кэшировать все соединения 3-го уровня» будет слишком дорого в оперативной памяти и ЦП.

Но, пытаясь преобразовать это понимание в решение, я придумал неуклюжий ответ, заключающийся в создании постоянных кэшей соединений 2-го уровня для всех на сайте (что было бы чрезвычайно дорого в обслуживании и сложным в обслуживании), и я сделал необъяснимый обходной путь в использовании Bloom Filters способом, который не имел большого технического смысла. Я бы не взял себя на работу после такого ответа!

Позже, когда я подумал о проблеме без давления интервью, нависшего над моей головой, я нашел более разумный ответ.

• Создайте очень быстрый способ получения соединений первого уровня для каждого из пакетов идентификаторов пользователей (размер пакета до ~ 1000?). Это, вероятно, означает выделенный кластер серверов с большим количеством оперативной памяти, который может кэшировать соединения 1-го уровня всей сети в памяти. К счастью, 50 миллионов членов х ср. 100 подключений на элемент x 4 байта на идентификатор элемента = <25 ГБ для кэширования в ОЗУ, что выполнимо с помощью недорогого оборудования. И количество изменений в день будет ниже 1%, поэтому поддерживать кеш в актуальном состоянии не так уж сложно. (Обратите внимание, что реляционная база данных, вероятно, будет плохим выбором для реализации этого кэша, поскольку шаблон доступа «много случайных операций ввода-вывода» снижает производительность реляционной БД.) </p>

• когда пользователь входит в систему, кэширует его соединения 2-го уровня, выбирая соединения 1-го уровня для каждого соединения 1-го уровня, и вставляет хеш-таблицу (ключ = идентификатор 2-го уровня, значение = массив 1-го уровня. уровень соединений, которые соединяют вас). Также кешируйте ваши соединения первого уровня, чтобы вы могли откатить и 1-й, и 2-й уровни с помощью одного обратного вызова на ваш удаленный сервер кеша. Идентификаторы пользователей легко разбиваются, поэтому распределенный кеш, такой как memcached, может хорошо работать для этого.

• для любого идентификатора пользователя, чтобы определить, находится ли он в вашей «сети» и какое отношение он имеет к вам (1-й, 2-й, 3-й), выполните следующие действия:

  1. если идентификатор находится в соединениях первого уровня, остановитесь.
  2. попробуйте найти идентификатор в вашей кэшированной таблице соединений 2-го уровня. Если найдено, верните массив соединений, которые вас соединяют.
  3. Извлеките соединения первого уровня идентификатора и повторите шаг # 2 для каждого из них. Объедините все результаты в один массив и верните их.
  4. рефакторинг в пакетную реализацию («посмотрите на расстояние от меня до N разных пользователей»), так что вы можете получить все удаленные результаты с шага № 3 без необходимости делать N удаленным вызовы.

Но я уверен, что есть лучшие ответы на это. Что твое? Если вам нужны дополнительные проблемы, попробуйте смоделировать ситуацию в интерактивном режиме (не можете искать решения в Интернете).

Обратите внимание, что вопрос был об оптимальном решении, независимо от , как LinkedIn на самом деле делает это сегодня , который я посмотрел после того, как написал свой собственный ответ выше.

Answer 1

Вы можете использовать аксиомы о небольших мировых сетях для оптимизации этого типа обхода.

Небольшие мировые сети характеризуются "концентраторами", которые представляют собой очень плотные соединения других узлов. Большинство узлов в сети, как правило, либо подключаются через несколько прыжков к топологически близкому узлу (1-4 перехода), либо маршрутизируют через один или несколько таких концентраторов. Это одна из главных причин того, что сети малого мира ведут себя так, как они.

Answer 2

Интересно, что технологии 1970-х годов вполне справились бы с моделированием этого. Модель сетевой базы данных эффективно управляет этим типом отношений.

Он неэффективен с точки зрения специальных запросов или обслуживания моделей данных, поэтому потерял популярность с ростом реляционных моделей данных.

Answer 3

Для реализации

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

Используйте тот факт, что соединения являются двунаправленными.

Хранить соединения 1-го уровня как отсортированный список в некоторых болях KV:

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 - номер подключения обоих пользователей.

Answer 4

Я не уверен в структуре таблицы или сложности системы, но вот простой пример SQL Server с использованием рекурсивного CTE:

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)

Answer 5

Если подумать, выполнение этого в SQL может быть очень ресурсоемким.

Учитывая это и тот факт, что в конечном итоге он будет использоваться повсеместно, и это пространство будет относительно дешевым ... Я бы предложил создать индекс с использованием Lucene (или Lucene.NET) в зависимости от ваших языковых предпочтений. Вы могли бы сделать пару вещей таким образом.

Вы можете либо создать структуру данных древовидного типа и рекурсивно сканировать свой индекс, ища все родительские узлы или дочерние узлы, а также их родительские или дочерние узлы в зависимости от ваших потребностей в данный момент.

Или вы могли бы выписать все отношения по мере их создания (пространство - дешевая концепция). Это будет процесс однократной записи (который вы не будете обновлять часто). Когда связь создается или отзывается, вы помещаете в очередь обновление своего индекса (очередь, потому что вы не хотите открывать для записи для отдельных запросов ... пакетные обновления индекса). Тогда вы можете прочитать эту действительно плоскую структуру, чтобы получить идентификаторы под вопросом.

Имея идентификаторы в руках (из какого типа поиска вы выполняете), вы можете перейти в БД, чтобы получить необходимую информацию об окружении. Затем кешируйте свой вывод, чтобы еще больше минимизировать то, что будет очень быстрым поиском, запросом базы данных, построением данных ... но все же быстрее, если он просто приходит из кеша.

Используйте что-то вроде Velocity, MemCached или MemCached Win32 для централизованного кэширования в веб-ферме.

Answer 6

Разве данные о мышцах не представлены в виде большого гигантского графика? и когда человек входит в систему, система будет обрабатывать свой узел, а затем, выполняя сначала обход в 3 уровня, система будет сохранять эти узлы в виде набора (вместе с информацией об уровне), и когда человек появляется на веб-странице система выполняет поиск по этому набору узлов и выдает расстояние взаимосвязи.

Это мое предположение. Пожалуйста, не стесняйтесь указывать, что делает это непрактичным.