5

我正在开发一个接受 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'的当前值不等于它之前的值(值已经改变了)。执行事件Z

我发现随着输入数量的增加以及规则数量的增加,评估“特定”规则并确定是否应触发事件所需的总计算量正在失控 - 投掷问题上更快和更多的硬件没有按预期扩展。

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

这个问题属于复杂事件处理领域,不幸的是,该领域中的大多数架构都使用上述相同的死机方法 - 可能对评估/重新评估事物的频率进行了一些改进。我们的想法是拥有一个可以近乎实时地做出反应的系统。将规则和输入分布在多个节点上似乎也效果不佳,因为在某些情况下,超过 95% 的活动规则中存在少数输入。

我希望如果那里有任何 SO'ers,知道更好的方法来解决这个问题,数据/结构或算法。

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

如果有两个这样的规则:

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

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

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

进一步说明,一些输入是暂时受限的,这意味着该规则可能要求变量的状态在一段时间内处于特定位置/状态(例如:MSFT 的价格在过去 30 秒内 > 20 美元),目前,这是通过使用值为 0 或 1 /false 或 true 的“表示变量”(外观)来完成的(变量的值由单独的机制确定,这通常是触发规则的结果)。

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

4

3 回答 3

8

几个想法。

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

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

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

于 2012-04-16T15:47:00.727 回答
0

Distributing the rules and inputs over multiple nodes doesn't seem to work well either, as in some situations a minority of inputs exists in over 95% of the active rules.

Distribute the rules, and feed the inputs to all the machines. Then you can linearly scale on the number of rules... if you are on a LAN you could send the events/input as multicast, so the network traffic won't increase.

于 2012-04-16T15:55:17.957 回答
0

尝试分解常见的表达式,对它们进行分组和缓存:这可以加快速度,尤其是那些最常用的,所以性能可能会增长。

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

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

ETALIS在 Prolog 中执行 CEPS。

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

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

于 2012-04-16T02:18:09.483 回答