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

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

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

  • В реальном мире серверы терпят неудачу. Как это влияет на вас?

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

  • Вы выполняете поиск до конца графика (бесконечно)? Как вы решаете, когда отказаться?

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

Ответы

Ответ 1

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

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

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

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

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

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

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

Считайте также, что никто не будет выполнять реальный поиск для каждого node, все в facebook вполне "локально", вы можете посмотреть непосредственного друга одного человека, а не друга друга друга.... это было бы не полезно.

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