c++ - 处理大量规则(条件和约束)CEP 系统

Question

我正在开发一个接受 100k+ 唯一输入的应用程序——为简单起见，我们假设每个输入都是一个浮点值(a、b、c 等)——尽管它们也可以是字符串等。该应用程序有许多与这些输入相关的规则/事件/触发器。

示例 1:

Rule[(a > b) and (c <= d)] --> [execute EventX]

定义1:上面的规则说:当输入'a'的值大于'b'并且输入'c'的值小于或等于'时d' 执行 EventX

例子2:

Rule[x != x.prev] --> [execute EventZ]

定义2:上面的规则说:如果在值更新后，如果输入'x'的当前值不等于它以前的值(值已经改变)。执行EventZ

我发现随着输入数量的增加和规则数量的增加，评估“特定”规则并确定是否应触发事件所需的总计算量正在减少control - 在问题上 throw 更快和更多 h/w 并没有按预期扩展。

目前，在每次新的输入更新时，都会在哈希表中查找关联的输入/变量，该哈希表将变量映射到包含它的规则。随后对这些规则中的每一个进行评估，如果结果为真或可操作，则异步触发相关事件。

这个问题属于复杂事件处理领域，不幸的是，这个领域中的大多数架构都使用与上述相同的无用方法——可能有一些与评估/重新评估的频率相关的改进。我们的想法是拥有一个可以近乎实时地使用react的系统。在多个节点上分布规则和输入似乎也不太奏效，因为在某些情况下，少数输入存在于超过 95% 的事件规则中。

我希望那里是否有任何 SO'ers，他们知道解决这个问题、数据/结构或算法的更好方法。

我想到的一个简单想法是，可以构造一个依赖逻辑推理列表。

如果有两条规则是这样的:

Rule[a < b] --> [exec E1]
Rule[b >= a] --> [exec E2]

然后对“a”或“b”的更新不应该需要对两者进行评估等。但我发现构建这样的逻辑推理结构非常复杂且容易出错，并且难以完全和严格地测试。

输入可以代表股票价格、温度传感器等。

另外请注意，一些输入在时间上受到限制，这意味着规则可能要求变量的状态在一段时间内处于特定位置/状态(例如:最后一次 MSFT 的价格 > 20 美元30 秒)，目前这是通过使用值为 0 或 1/false 或 true 的“表示变量”(外观)来实现的(变量的值由单独的机制确定，通常是规则被触发)。

还应注意，由于接近实时的限制和每秒生成的数据量，使用带有触发器和存储过程的数据库的选项是不可能的。

Answer 1

一些想法。

如果您的规则的条件是连词，则为每个不满足的条件维护一个不满足的条件。仅将规则放在该术语的检查列表中。如果该术语得到满足，则扫描其他术语以确定条件是否已触发或是否存在另一个不满足的术语。 (我想我是在 SAT 求解器的上下文中了解到这个技巧的。)

如果您有 10 <= x <= 50 这样的术语，请使用 interval tree而不是散列来快速定位将要通过对 x 的更新变得不满意的满意条款和即将变得满意的不满意条款。 (完全搜索 O(log n)，加上每个返回结果的 O(1)。)如果一次只考虑一个变量会产生太多虚假命中，则存在多维概括，但它们的维护成本会更高。

如果您没有这样的术语(例如，a <= b)，请进行派生输入 (b - a) 并使用您的哈希策略使它们保持最新。