высокопроизводительный неблокирующий упорядоченный обработчик сообщений

Question

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

Пример: если поступило 1,2,3,5 сообщения - оно должно уведомить о пропущенном сообщении 5го числа, а если 1,2,3,4,2,5 - он должен уведомлять только об устаревшем сообщении при получении 2 после 4.

Поскольку он высокопроизводительный, он не должен использовать блокировки.

Вот моя текущая реализация - https://codereview.stackexchange.com/q/10329/5334

- Я решил проблему ABA, но не могу решить проблему 1, возможно ложное предупреждение после игнорирования устаревших сообщений: на 1,2,3,4,2,5 - он будет уведомлять о устаревших 2 (после 4), но также может ошибочно уведомлять о пропущенных сообщениях 5го числа.

Есть ли способы исправить это или другие неблокирующие алгоритмы для этой задачи?

Answer 1

Почему бы вам не запомнить наивысший идентификатор, уже обработанный в AtomicLong / AtomicInt, а затем, если следующее сообщение имеет более низкий идентификатор, то оно «устаревшее», и вы просто отбрасываете его, и если идентификатор следующего сообщения отличается от более чем 1 от последнего запомненного Вы предупреждаете о пропаже.

Это должно ответить на ваш конкретный вопрос, но мне было бы интересно, сколько таких предупреждений вы получите в действительно «высококонкурентной» среде - вероятно, много. Интеграционные решения, такие как Apache Camel, обычно имеют встроенные механизмы для обработки и обнаружения неупорядоченных сообщений, которые довольно сложны с очередями и т. Д. Возможно, вы захотите либо использовать одно из них, либо хотя бы изучить его построение. чтобы получить больше идей.

Answer 2

Поскольку оба состояния недопустимы, у вас есть возможность дважды сообщить о сообщении.

Если вы получите 1,2,3,5,4, то сообщите о сообщении «Сообщение 4 не получено» и сообщении «Сообщение 4 получено не в порядке».

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

Таким образом, вы получите «Сообщение 4 получено не по порядку» сразу же после его появления, но вы не можете отправлять сообщение «Сообщение 4 не получено» до, возможно, намного позже (N секунд спустя, X сообщений позже , что уместно).

Так что вам просто нужно согласовать эти два сценария и то, как вы хотите с ними справиться.