У меня есть приложение-издатель, которое отправляет сообщения нескольким подписчикам. Каждому сообщению присваивается возрастающий порядковый номер. Допустим, A, B и C — три подписчика, и издатель отправил сообщение номер 1 пользователю A, номер 2,3,4,7 — номеру B и номер 5,6 — номеру C.
Будет ли сообщение с номером x отправлено подписчику A, B или C, является функцией некоторого неизменного атрибута сообщения (не числа), т. е. сообщение номер 7 направляется на B, поскольку оно может относиться к акции, символ которой начинается с «b». .
У издателя есть карта с максимальным порядковым номером, отправляемая каждому подписчику. Карта на данный момент будет выглядеть так:
{"A" -> 1, "B" ->7, "C" ->6}
На данный момент мы не знаем, успешно ли доставлены эти сообщения соответствующим подписчикам. Однако гарантируется, что сообщения будут доставлены последовательно.
В случае аварии, которая потребовала перезагрузки издателя, нам нужно воспроизвести сообщения, которые могли быть потеряны для подписчика.
Важно: чтобы воспроизвести сообщения подписчикам, издателю необходимо отправить запрос на воспроизведение другому вышестоящему серверу, и у него нет постоянного хранилища всех сообщений, которые он ранее видел. Таким образом, издатель здесь действует больше как маршрутизатор. За воспроизведение сообщений с вышестоящего сервера взимается плата, поэтому я хочу свести к минимуму количество сообщений, которые мне нужно запрашивать для воспроизведения.
Текущий алгоритм, который я использую, заключается в том, чтобы найти максимальную последовательность сообщений, которую получил каждый подписчик. Скажем, мы получаем что-то вроде:
{"A"->1, "B" ->7, "C" ->6}
Текущий алгоритм просто предполагает, что нам нужно воспроизвести минимальное количество сообщений, восстановленных от подписчиков (в данном случае 1). Тогда как на самом деле нам нужно беспокоиться о сообщениях с номером больше 7 только в этом случае.
Я могу периодически сохранять карту отправленных сообщений с наибольшим количеством сообщений для каждого подписчика на стороне издателя.
Так что я мог сохранять состояние этой карты каждые 5 минут. Если после перезагрузки я увижу, что все подписчики получили номер сообщения выше последнего сохраненного значения, я могу воспроизвести максимальное количество восстановленных порядковых номеров (7 в данном случае). Это уменьшает количество сообщений для воспроизведения.
Я думаю, что может быть стандартный алгоритм для этой проблемы, но поиск в Интернете ничего полезного не дал. Если кто-то может указать мне соответствующий алгоритм, это было бы очень полезно.
Пожалуйста, предположим, что:
- Сохранение каждого номера сообщения, отправленного каждому подписчику, невозможно.
- Подписчик может хорошо обрабатывать дубликаты сообщений, поэтому мы хотим ошибиться в воспроизведении большего количества сообщений, чем требуется.
