高效地关联事件

我正在使用C++ Windows应用程序，并且需要添加关联功能。目前我有两个活动制作人，每个制作人都会产生类似的活动。两个生产者的平均综合事件发生率均为2k /秒。然而，它在负载下跳到300-500 k/sec。这是一个事件的简化版本，看起来怎么样高效地关联事件

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为键）与队列（时间和动作相关）
增强管道（例如github）

但我不知道如何处理快速事件驱逐，因为我需要保持低CPU和内存利用率。

任何人都可以请建议一个解决方案，让我有效地关联事件（最小的CPU影响和低内存占用）？

来源

2016-11-28 oleksii

您是否正在寻找产生的事件量或某些事件特征之间的相关性？是否允许采样和估计，或者您是否需要精确的相关度量？ – Dave

这是事件的特点：在一系列有争议的事件中，我需要找到与我的过滤器相匹配的事件。也许“相关性”这个词在这里并不完全正确。抽样/估计可能会在可能错过重要数据的情况下引入错误，但我认为我可以应用一些过滤来消除重复事件，因为会有很多“近似”重复项。 – oleksii

由于您有一个相当小的关联窗口，您可以先将数据拆分为易于驱逐。

将流1中的所有对象（较慢/较小的流）存储在三个hashmaps的循环缓冲区中。当刚刚获得的事件的时间戳比第一次放入最新的哈希映射的时间戳早2秒以上时，您将清空最旧的哈希映射并将其放在最前面，将所有其他时间戳移动一步。您还记录了您现在放入此存储桶的第一个项目的“开始时间”。

这允许您保留来自数据流1的大约4-6秒数据的循环缓冲区，这会为未按正确顺序传递的消息提供一点缓冲区。

对于流2（更大/更快的流），只需在所有hashmaps中执行查找。当你得到一场比赛时，你使用你的相关函数检查它实际上是一场比赛。它在流n上以每秒O(m+b*n log k/b)为b hashmaps（桶）和k消息，在n和m消息的流上运行。对于b=3，对于流n中的每秒k条消息，您有O(m + n log k)。空间要求应该在6k左右。

如果只使用三个hashmaps使性能太spikey（无论是在内存使用情况和CPU使用情况（清空hashmaps确实需要一些时间）），你可以使用更多的hashmaps（增加b）。只需保持足够的时间你需要记住，加上一两个，并记住晚到的小缓冲区。

来源

2016-11-28 18:26:24

高效地关联事件

回答

相关问题