Реалистичная модель социальной сети с десятками миллионов пользователей.Какие технологии я должен использовать?

Question

Я пытаюсь смоделировать реалистичную социальную сеть (Facebook).Я аспирант по компьютерным наукам, поэтому я разбираюсь в базовых структурах данных и алгоритмах.

Идея:
Я начал этот проект в Java.Моя идея заключается в создании нескольких областей пользователей.Каждый пользователь в данной области будет иметь случайное количество друзей с нормальным распределением вокруг заданного среднего значения.Каждый пользователь будет иметь большой процент или группу «Друзей» из Района, к которому он принадлежит.Остальные их «Друзья» будут небольшими кластерами из нескольких разных случайных областей.

Исходная структура
Я хотел создать ArrayList областей
ArrayList<Area> areas
С каждой областью, содержащей ArrayList пользователей
ArrayList<User> users
И с каждым пользователем, имеющим ArrayList «друзей»
ArrayList<User> friends

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

Проблема:
Когда я пытаюсь создать большие наборы данных, я получаю OutOfMemoryError из-за нехватки памяти вкучаТеперь я понимаю, что этот способ будет невозможен, если я захочу создать, скажем, 30 областей с 1 миллионом пользователей на область и 200 друзьями на пользователя.Я ем почти 2 ГБ с 1 областью ... Ну и что теперь.Мой алгоритм сработал бы, если бы я мог создать всех пользователей заранее, а затем просто «дать» друзей каждому пользователю.Но мне нужно сначала создать Области и пользователей.Чтобы стать «другом», в Районе должен быть пользователь.

Следующий шаг:
Мне нравится мой алгоритм, он прост и понятен.Что мне нужно, так это лучший способ хранения этих данных, поскольку они не могут быть сохранены и сохранены в памяти одновременно.Мне понадобится не только доступ к Области, к которой принадлежит пользователь, но и несколько случайных областей для каждого пользователя.

Мои вопросы:
1. Чтотехнология / структура данных, я должен помещать эти данные в.В конце концов, я в основном хочу отношения между пользователем и друзьями.Идея «Площадь» - это способ сделать эти отношения реалистичными.
2. Должен ли я использовать другой язык все вместе.Я знаю, что такие технологии, как Lucene, Hadoop и т. Д. Были созданы с использованием Java и используются для больших объемов данных ... Но я никогда не использовал их и хотел бы получить некоторые рекомендации, прежде чем погрузиться в что-то новое.
3. С чего мне начать?Очевидно, я не могу использовать только Java с данными в памяти.Но мне также нужно создать эти Области пользователей, прежде чем я смогу предоставить Пользователю список друзей.

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

Answer 1

Вам нужно решение для хранения с возможностью поиска, чтобы хранить ваши данные (а не хранить все это в памяти).Либо реляционная база данных (например, Oracle, MySQL или SQL Server) с O / RM (например, Hibernate), либо база данных nosql, такая как mongodb , будут работать нормально.

Answer 2

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

Здесь есть хорошая информация и множество ссылок на дополнительную полезную информацию о том, что FB, LinkedIn, Digg и другие делают здесь, на Stackoverflow, вопрос 1009025

Answer 3

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

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

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

Итак, как только вы построите свои отношения, вы можете начать писать запросы, связывающие информацию по-разному.

Возможно, вы захотите использовать списки вместо массивов, когда размеры разные, так что вы не тратите впустую память, когда читаете данные обратно.Я ожидаю, что это основная причина, по которой у вас заканчивается память, если вы предполагаете, что есть 100 пользователей, и наибольшее количество друзей для любого из них составляет 50, но у большинства будет 10, то для подавляющего большинства пользователей вытратить пространство, особенно когда вы имеете дело с миллионами, так как указатель на каждый объект станет нетривиальным.

Возможно, вы захотите пересмотреть свои структуры данных, я ожидаю, что у вас есть некоторые недостатки.

Вы также можете использовать некоторые инструменты мониторинга, и эта страница может помочь: http://www.scribd.com/doc/42817553/Java-Performance-Monitoring

Даже такая простая вещь, как jconsole, поможет вам увидеть, что происходит с вашим приложением.

Answer 4

1. Использование базы данных с каким-либо инструментом ORM [ JPA с Hibernate и т. Д.],
2. Загрузка данных Lazily , когда они действительно нужны
3. Выгрузить их, когда они из Кэш / Сессия, когда они на самом деле не нужны или неактивны.

Не стесняйтесь, дайте мне знать, если возникнут какие-либо трудности с пониманием.

http://puspendu.wordpress.com/