Как дедуплицировать параллельные потоки событий

Question

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

Мой клиентский компонент будет взаимодействовать с двумя серверами. Каждый из них обеспечивает поток событий почти в реальном времени (~ 1 секунда). События могут иногда быть не в порядке. Предположим, я могу однозначно идентифицировать события. Мне нужно отправить один поток событий в код потребления с той же производительностью почти в реальном времени.

Answer 1

Я думаю, что оптимизация может зависеть от ОС. Из задачи, которую вы описали, я думаю о двух потоках, потребляющих входящие данные и добавляющих их в общий поток, имеющих доступ на основе мьютексов. И Linux, и Win32 имеют мьютекс-подобные процедуры, но они могут иметь низкую производительность, если у вас действительно высокая скорость передачи данных. В этом случае я бы оперировал блоками данных, что позволит использовать мьютексы не так часто. Конечно, есть основной поток, который потребляет данные, и он также обращается к ним с помощью мьютекса.

Answer 2

Много написано об этой проблеме. Вот основополагающая статья Лесли Лампорта:

http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#time-clocks

Статья в Википедии по теории операционного преобразования - отличная отправная точка для дальнейших исследований:

http://en.wikipedia.org/wiki/Operational_transformation

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