Граф Структуры данных с миллионами узлов (Социальная сеть)

Question

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

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

1. В реальном мире серверы выходят из строя . Как это влияет на вас?

2. Как можно использовать преимущество кэширования ?

3. Вы ищете до конца графика (бесконечно)? Как вы решаете, когда сдаться?

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

Answer 1

Ваш вопрос кажется интересным и любопытным:)

1) Ну ​​... конечно, данные хранятся на дисках, а не в оперативной памяти.Диски имеют системы, которые избегают сбоев, в частности, RAID-5, например.Ключом является избыточность: если одна система выходит из строя, другая система готова занять его место.Существует также резервирование и совместное использование рабочей нагрузки ... есть два компьютера, которые работают параллельно и совместно используют свои рабочие места, но если один останавливает только одну работу и принимает полную рабочую нагрузку.

В таких местах, как Google или Facebook, избыточностьне 2, это 1200000000 :) И учтите также, что данные не находятся в одной ферме серверов, в Google есть несколько центров обработки данных, соединенных вместе, поэтому, если одно здание взрывается, другое займет его место, например.

2) Это не простой вопрос, но обычно эти системы также имеют большой кэш для дисковых массивов, поэтому чтение и запись данных на диск происходит быстрее, чем на наших ноутбуках :) Данные могут обрабатываться параллельно несколькими параллельными системами, и этоКлюч скорости услуг, таких как Facebook.

3) Конец графа не бесконечен.Так что это действительно возможно с реальной технологией.

Вычислительная сложность изучения всех соединений и всех узлов на графике составляет O (n + m), где n - количество вершин, а m - количество ребер.Это означает, что оно является линейным по отношению к количеству зарегистрированных пользователей и количеству соединений между пользователями.А оперативная память в наши дни очень дешевая.

При линейном росте легко добавлять ресурсы при необходимости.Добавляйте больше компьютеров, чем больше вы становитесь богатыми:)

Учтите также, что никто не будет выполнять реальный поиск для каждого узла, все в фейсбуке довольно «локально», вы можете просмотреть прямого друга одного человека,не друг друга друга ... это было бы бесполезно.

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