Эффективно коррелировать события

Question

Я работаю над приложением Windows C++ и должен добавить возможность корреляции. На данный момент у меня есть два продюсера событий, каждый производитель генерирует подобные события. Средний комбинированный коэффициент генерации событий составляет 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) 

Я думал о

• в HashMap (ProcessId, как ключ) с очередями (для корреляции времени и действия)
• Boost трубопроводы (пример на github)

Но я не уверен, как справляться с выселением быстрых событий, поскольку мне необходимо снизить загрузку процессора и памяти.

Может ли кто-нибудь предложить решение, позволяющее эффективно коррелировать события (минимальное влияние на процессор и низкий объем памяти)?

Answer 1

Поскольку у вас есть довольно небольшое окно корреляции, вы можете начать с разбивки своих данных там для удобства выселения.

Храните все объекты из потока 1 (более медленный/меньший поток) в циклическом буфере из трех хэш-карт. Когда временная метка события, которое вы только что получили, больше, чем на две секунды старше, чем первая временная метка, которую вы ввели в новейшую хэш-карту, вы очистили старую хэш-карту и поставили ее спереди, переместив все остальные на один шаг. Вы также записываете «время начала» первого элемента, который вы сейчас помещаете в это ведро.

Это позволяет хранить циклический буфер примерно 4-6 секунд данных из потока 1, что дает небольшой буфер для сообщений, которые не доставляются в правильном порядке.

Для потока 2 (более крупный/более быстрый поток) вы просто выполняете поиск во всех хэш-картах. Когда вы получаете совпадение, вы проверяете, что это действительно реальное совпадение, используя вашу корреляционную функцию. Это выполняется в O(m+b*n log k/b) для b hashmaps (buckets) и k сообщений в секунду в потоке n, по потокам n и m сообщений. Для b=3 у вас есть O(m + n log k) для k сообщений в секунду в потоке n. Требования к пространству должны быть около 6k.

Если использование только трех хэш-карт делает работу слишком шикарной (как с точки зрения использования памяти, так и с использованием процессора (удаление хэш-карт занимает некоторое время)), вы можете использовать больше хэш-карт (увеличение b). Просто держитесь достаточно на время, которое нужно сохранить в памяти, плюс один или два, и помните небольшой буфер для позднего прибытия.