Эффективно соотносить события
Я работаю над приложением C ++ для Windows, и мне нужно добавить возможность корреляции. На данный момент у меня есть два производителя событий, каждый из которых генерирует похожие события. Средняя суммарная скорость генерации событий составляет 2 к / с для обоих производителей. Тем не менее, он прыгает до 300-500 к / с под нагрузкой. Вот так выглядит упрощенная версия события
Event
ProcessId // e.g. 1234
Action // e.g. 0, 1, 2
Timestamp // e.g. LARGE_INTEGER Windows timestamp
Правило корреляции, которое мне нужно построить, выглядит следующим образом
Filter
// events are from the same process
ev1.ProcessId == ev2.ProcessId
&&
// events have specific types
( ev1.Action == 0 && ev2.Action == 1)
&&
// they are less than 2 secs apart
( abs(ev1.Timestamp - ev2.Timestamp) < 2 seconds)
Я думал о
- хэш-карта (ProcessId в качестве ключа) с очередями (для соотношения времени и действия)
- Повысить конвейеры (пример на GitHub)
Но я не уверен, что делать с быстрым удалением событий, так как мне нужно поддерживать низкую загрузку процессора и памяти.
Кто-нибудь может предложить решение, которое позволит мне эффективно коррелировать события (минимальное воздействие на процессор и низкий объем памяти)?
Решение
Поскольку у вас довольно небольшое окно корреляции, вы можете начать с разделения данных там для легкого выселения.
Сохраните все объекты из потока 1 (медленный / меньший поток) в циклическом буфере из трех хэш-карт. Когда отметка времени только что полученного вами события на две секунды старше первой отметки времени, вставленной в новейшую хеш-карту, вы удаляете старую хеш-карту и помещаете ее впереди, перемещая все остальные на один шаг вниз. Вы также записываете «время начала» первого предмета, который вы сейчас помещаете в это ведро.
Это позволяет хранить в циклическом буфере примерно 4-6 секунд данных из потока 1, что дает небольшой буфер против сообщений, доставляемых не в правильном порядке.
Для потока 2 (больший / более быстрый поток) вы просто выполняете поиск во всех хэш-картах. Когда вы получаете совпадение, вы проверяете, что это действительно настоящее совпадение, используя вашу функцию корреляции. Это работает в O(m+b*n log k/b) за b хешмапы (ведра) и k сообщений в секунду в потоке nчерез потоки n а также m Сообщения. За b=3, у тебя есть O(m + n log k) для k сообщений в секунду в потоке n, Требования к пространству должны быть около 6k,
Если использование только трех хеш-карт делает производительность слишком высокой (как с точки зрения использования памяти, так и использования процессора (очистка хеш-карт занимает некоторое время)), вы можете использовать больше хеш-карт (увеличение b). Просто оставьте достаточно времени, которое нужно хранить в памяти, плюс один или два, и запомните небольшой буфер для позднего прибытия.
Другие решения
Других решений пока нет …