Получение K новых новостей в социальном графе

Допустим у нас есть небольшой сервис основанный на социальном граф. Одной из функций таких проектов является формирование списка из k последних публикаций «друзей» пользователя. И так сложилось, что в основе проекта лежит документ-ориентированное NoSQL решение. Работа с графами в таких системах затруднительна, а формирование списка должно проходить максимально быстро. Тогда можно приметь следующий подход.

Рассмотрим на примере. Допустим у нас есть пользователь A, для которого мы бы хотели получить K свежих постов. Как видно из рисунка данный пользователь связан с тремя другими пользователями (но их может быть гораздо больше). Нам необходимо сформировать для него набор из K самых свежих постов от его «друзей».

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

• Id пользователя;
• LastPubDate — дата последней публикации пользователя;
• LastPubs — набор из K элементов вида { PubId, AddDate }, где PubId – идентификатор поста, AddDate – дата публикации поста. Набор должен содержать информацию о K последних публикаций пользователя.

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

Тогда, данные для пользователя A могут быть представлены следующим образом.

Для формирования k последних постов для пользователя A, мы возьмем K документов UserPostMetadata пользователей из списка друзей A, упорядоченные по LasPubDate. В данном наборе будут точно содержаться, K самых новых публикаций. Нам остается объединить наборы LastPubs выбранных документов UserPostMetadata, упорядочить их по времени AddDate и выдать первые K. Так как первые K будут содержать самые новые публикации его друзей.