事件流上的分布式谓词计算

Question

我的问题实际上是对我在工作中试图解决的问题的论文、文章、文本或书籍的请求。

我正在开发一个程序，该程序计算分布式系统中给定对象的谓词值（真或假），其中存在可以更改对象属性的事件流，从而更改谓词值。每当谓词值更改时，程序必须发送有关此更改的通知。

例如，考虑有一个对象 A 它有一个名为 name 并认为有一个谓词 P 当对象的 name 等于 Jhon。流中的每个事件都有一个时间戳和一个属性名称值。因此，请考虑以下事件顺序：

e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 2 }
e3 = { name: Peter, timestamp: 3 }
e4 = { name: Doug, timestamp: 4 }
e5 = { name: Jhon, timestamp: 5 }

在这个问题中，事件具有全序关系：如果您有两个事件，您总是可以说出哪一个是其中最古老的。

现在，事件不一定根据其时间戳以正确的顺序显示在流中。每个事件的时间戳都是唯一的，因此同一对象不会有两个或多个事件具有相同的时间戳。此外，时间戳不一定形成总是加一的序列：如果我们看到 e1 带时间戳 1 和 e3 带时间戳 3, ，并不意味着存在 e2 带时间戳 2。不保证所有事件都会收到或何时收到。问题的一部分是我们只知道我们在流中看到的事件的存在。

真实的情况更糟糕：有多台计算机并行处理该事件流。然而，为了简单起见，我将在这个示例中进一步考虑仅考虑一台计算机。

如果事件到达并按上述顺序处理，则发送的通知应为：

P(A) = true when e1 arrives
P(A) = false when e3 arrives
P(A) = true when e5 arrives.

这是正确的通知顺序，因为它遵循时间戳顺序。现在，假设计算机按以下顺序接收事件：

e1, e5, e2, e4, e3

不考虑事件时间戳的简单算法会发送不正确的通知序列：

P(A) = true when e1 arrives
P(A) = false when e4 arrives

我正在研究的算法考虑时间戳并推断何时应该发送通知但没有发送。所以当 e3 到达时它会注意到通知 P(A) = true 为了 e5 没有发送。这感觉有点像重新发明轮子，尽管我不知道有任何关于这个问题的读物。我想要一些关于这个问题或类似问题的参考资料，比如一些处理此类问题的论文。

真正的问题要复杂得多，因为它涉及存储谓词 $\次$ 数据库中的对象状态，作为处理流的计算机之间的共享状态，我所说的是每秒到达的数千个事件，因此不可能将所有事件都存储在某个数据库中。

有没有关于我所描述的问题的文献？如果是的话，你能给我链接吗？

我希望看到一篇论文或一篇文本来解释解决这个问题的算法，如果这样的论文提供有关该算法的证明，那就更好了（例如正确性）。

如果这样的论文不存在（我实际上认为是这样），我会接受描述算法并提供关于其正确性的论点或证明的答案。

为了使该算法正确，无论事件到达的顺序如何，它都应该始终发送正确的通知序列。并且该算法不应该将所有接收到的事件保留在内存中，因为真正的问题是处理太多事件而无法保存在内存中或存储在数据库中。将一些事件保留在内存中是合理的，最好是固定数量。

Answer 1

不可能的结果#1：丢弃的事件

问题一般无法解决；如果某些事件被丢弃（即未收到），则无法保证满足您的要求。首先考虑这个流：

e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 4 }

算法看到这两个事件。接下来，考虑这个流：

e1' = { name: Jhon, timestamp: 1 }
e2' = { name: Pete, timestamp: 2 }
e3' = { name: Jhon, timestamp: 3 }
e4' = { name: Jhon, timestamp: 4 }

算法只看到事件 e1',e4' （其他事件丢失并且从未收到）。您可能会注意到，算法在两种情况下看到的内容是相同的，因此其输出在两种情况下都是相同的。然而，这两种情况的正确答案是不同的，因此算法不可能总是产生正确的输出。（第一种情况的正确响应是不发出任何通知；第二种情况的正确响应是产生两个通知，一个通知在收到后指示谓词为假 e2', ，以及 1 表示接收后谓词为真 e3'.)

目前尚不清楚如何调整要求来应对这种情况。我能看到的唯一合理的解决方案是，生成的通知应该仅取决于接收到的事件，而不取决于发送的事件。这相当于指定事件不能被删除。

不可能的结果#2：重新排序的事件

您声明您必须能够处理重新排序的事件，而无需将所有事件存储在内存中，并且可以任意重新排序。然而，这些要求是不兼容的：这是不可能实现的。考虑时间戳为 2,4,6,8,10,12,... 的一长串事件在长事件序列的末尾，如果具有奇数时间戳的事件到达，确保正确处理它的唯一方法是存储过去事件（或对象过去状态）的整个历史记录。

因此，您还必须放宽重新订购的要求。也许您愿意将所有事件永远存储在内存中。（如果是这样，您就有了解决方案。）也许您愿意对重新排序施加限制，例如，任何事件都不会延迟超过 10 分钟。（如果是这样，您只需存储过去 10 分钟的历史记录，所有较旧的内容都可以删除。）也许其他东西在您的特定情况下更有意义。

但不能选择的一件事是强加您问题中所述的所有严格要求，并且需要一种始终正确的算法。

---

我不知道有任何这方面的文献，而且我也没有特别认为有任何理由期望有任何文献。这是一组非常具体的要求，在我看来，最终的任务要么微不足道，要么无法解决。这些通常不是文献中经常研究的问题。也许您可能感兴趣 持久数据结构, ，但这只是存储整个事件历史的一种奇特方式，正如您所说的那样；在您的特定情况下，您不需要花哨的数据结构来做到这一点。