处理大量规则(条件和约束)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

我发现,随着输入数量的增加,以及规则数量的增加,评估"特定"规则并确定是否应该触发事件所需的总计算量正在失控 - 投掷该问题的速度越来越快,而且没有按预期进行扩展.

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

这个问题出现在复杂事件处理领域,遗憾的是,这个领域中的大多数架构使用了上面描述的相同的死角方法 - 可能还有一些与评估/重新评估事物的频率有关的改进.我们的想法是拥有一个能够近乎实时地做出反应的系统.在多个节点上分配规则和输入似乎也不能很好地工作,因为在某些情况下,超过95%的活动规则中存在少数输入.

我希望是否有任何其他SO'ers,知道更好的方法来解决这个问题,数据/结构或算法.

我想到的一个简单的想法是,可以构建一个依赖逻辑推理的列表.

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

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

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

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

还要注意,一些输入在时间上受到限制,这意味着规则可能要求变量的状态在特定位置/状态下持续一段时间(例如:MSFT的价格>最后30秒的20美元),目前,这是通过使用值为0或1/false或true的'代表变量'(facade)来实现的(变量的值由单独的机制决定,这通常是规则被触发的结果).

还应该注意的是,由于近实时约束和每秒产生的数据量,使用具有触发器和存储过程的DB的选项是不可能的.

Answer 1

几个想法.

如果您的规则的条件是连词,则为每个未满足的条件保持不满足的条件.将规则仅放在该术语的检查列表中.如果该术语满足,则扫描其他术语以确定是否触发了条件或是否存在另一个未满足的术语.(我想我在SAT求解器的背景下学到了这个技巧.)

如果您有10 <= x <= 50 之类的术语,请快速使用间隔树而不是哈希来找到即将变得不满足的满意术语,这些术语将由x的更新和即将满足的未满足的术语变得不满足.(O(log n)完全搜索,每个结果返回O(1).如果一次考虑一个变量会产生太多的虚假命中,则存在多维概括,但维护它们会更加昂贵.

如果您没有这样的术语(例如,a <= b),请使用派生输入(b-a)并使用哈希策略使其保持最新.

Answer 2

尝试分解常见表达式，对其进行分组和缓存：这可以加快速度，尤其是那些最常用的表达式，因此性能可能会提高。

这有多可行，取决于您在表达逻辑时必须使用的语言。我认为您的流程有可能被建模为电子表格，其中计算是数据驱动程序。WRT 单元引用的拓扑排序公式足以进行基本评估，但事情很快就会变得复杂......

在 C++ 中，您可以尝试使用模板表达式来解决逻辑。Boost.proto是对你的语言进行建模的助手

ETALIS在 Prolog 中执行 CEPS。

我还没有尝试过（唉），但我相信它非常好。并且肯定会实现您所追求的，甚至更多。

在SWI-Prolog中运行，应该是可访问的，易于设置和操作，并且SWI-Prolog C++接口对于实际数据交换非常方便。