Каковы наиболее известные алгоритмы / методы для обновления ребер в огромных графовых структурах, таких как социальные сети?

Question

В социальных сетях, таких как твиттер, где миллионы подписываются на одну учетную запись, очень сложно мгновенно обновлять всех подписчиков при публикации нового твита.Точно так же на фейсбуке есть фан-страницы с миллионами подписчиков, и мы сразу же узнаем о них, когда они будут размещены на странице.Мне интересно, каковы наиболее известные методы и алгоритмы для достижения этой цели.Я понимаю, что с миллиардами учетных записей у них есть огромные центры обработки данных по всему миру, и даже если мы уменьшим эту проблему только для одного компьютера следующим образом - 100 000 узлов со средним 200 ребрами на узел, тогда каждое обновление одного узла потребует 200 обновлений ребер.Итак, каковы лучшие методы / алгоритмы для оптимизации таких больших обновлений.Спасибо!

Answer 1

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

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

Варианты выбора:

1. Обновите 1 миллион подписчиков пару раз в день в течение нескольких секунд;или

2. Отвечать на чеки от 1 миллиона подписчиков, пары сто раз в день, в течение 1/10 секунды или около того.

Существуют промежуточные стратегии, включающие кластеризацию пользователей и прочего, но шаблоны использования, подобные тем, которые вы видите в Facebook и Twitter, вероятно, настолько сильно смещены в сторону варианта (1), что такие стратегии не окупаются.