Блог

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

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

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

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

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

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

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

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

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

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

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

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