Derflow:Erlang的分布式确定性数据流编程

论文地址：Derflow:Erlang的分布式确定性数据流编程–Bravo等人。2014年

今天的选择是SyncFree欧洲研究项目（SyncFree European research project）在不同步的情况下进行大规模计算的工作的一部分。

不确定性使得对分布式应用程序的推理变得非常困难。所以布拉沃等人指出我想如果我们能让它们具有确定性，生活可能会更容易。那就看Derflow是如何做到的…

非确定性语言中的并发程序很难被证明是正确的，并导致了众所周知的灾难…。我们认为，限制编写非确定性代码的能力是彻底检查应用程序正确性的合理选择。

Derflow基于分布式单任务数据存储的思想，建立在riak核心之上。

给定相同的输入值，以确定性数据流样式编写的程序将始终返回相同的输出值，或者永远不会返回。这些输入值也可以是数据流，这是函数编程对并发设置的自然概括。我们提出的解决方案提供了一个分布式确定性数据流解决方案，它在分布式Erlang上透明地运行，提供了具有高可用性、容错性和确定性计算的能力。

基本的Derflow模型很容易理解。想象一下一个赋值存储，其中键是变量标识符，而值要么是未赋值的，要么是对另一个变量的引用，要么是Erlang术语。一旦给变量赋值，就永远无法更改它。

还有一大堆隐藏的元数据与系统跟踪的每个变量关联：

• 哪些变量与此变量绑定
• 哪些进程正在等待变量绑定到值
• 如果变量是流的一部分，那么流中的“next”值是多少（见下文）
• 在设置值之前等待读取器的任何进程（以支持值的延迟生成）
• 任何跟踪变量可用性/可访问性的监视器（用于处理分区等）
• 基本编程模型包括declare（）（创建一个新变量并返回其id）、bind（x，v）（将变量x绑定到值v）和read（x）。读取未绑定变量的进程将阻塞，直到绑定值为止。Derflow还利用Erlang的spawn来支持并发性。

通过将流视为数据流变量列表来支持流数据：

流是一种有用的技术，它允许线程或进程在并发编程中进行通信和同步。流在这里表示为数据流变量列表，未绑定的数据流变量作为列表的最后一个元素。

produce操作通过将新值绑定到最后一个元素并创建新的未绑定的最后一个变量（“next”）来扩展流的尾部。consume从流中读取元素，并返回流中下一个变量的id。

如果失败不引入非决定论，就需要小心处理。

确定性和数据流变量为故障处理提供了一个非常有用的特性：冗余计算不会影响确定性数据流程序的正确性。我们提出了一个故障处理模型，其中故障进程或暂时无法访问的进程可以重新启动，同时仍然提供确定性编程模型的保证。

如果一个计算过程失败了，它就会被重新执行。在Derflow模型中，重复处理无法更改结果。（当然，这也依赖于没有副作用的程序）。如果进程被阻塞是因为它等待读取的变量永远不可用，则重新启动必须更深入地级联：

重新执行被阻止的进程将导致该进程立即再次被阻止。因此，我们必须提供一种方法来识别进程和数据流变量之间的依赖关系，以便提供一种保证进度的确定性重启策略。确保在这种情况下取得进展的常见策略是重新启动声明失败数据流变量的进程。此外，还应重新启动依赖于重新启动的进程的所有进程。

Derflow的实现建立在riak核心之上。mnesia被考虑但被拒绝，部分原因是它在网络分区下的行为：

在存在网络分区的情况下会出现问题，在这些分区中，网络分区两边的mnesia节点能够独立地取得进展。目前，不存在协调节点重新连接时对数据库所做更改的机制，也不存在对并发或因果影响操作进行推理的机制。

给出了几个Derflow程序的例子，说明程序的结果与计算过程中使用的并发度无关。

在Derflow中，任何使用数据流变量的函数都可以在不同的进程中运行，同时保持最终结果不变。因此，程序员可以以一种安全的方式透明地将并发性添加到他们的程序中（并行性或分布），而不必考虑数据竞争和可能的错误。

然而，这种并发性并不是通过运行时自动管理的——程序员必须明确地指定它（与此相反，例如，一个用于数据日志的执行计划器）。

本文对Derflow程序的语义做了很清楚的解释，并发执行的确定性模型也很有意思。然而，我发现仅仅从这篇论文中很难评估Derflow是否是编写实际系统的一种有趣的方式，或者限制是否会感到受限。也许这个问题的答案可以在Derflow所基于的Kahn过程网络的文献中找到。

确定性数据流最早由Gilles-Kahn于1974年在一个编程模型中提出，现在称为Kahn网络。1977年，Kahn和David MacQueen提出了这个模型的一个懒惰版本。然而，直到最近，这个模型还没有成为主流并发编程的一部分。这可能是由于模型无法表示非确定性，或者同时发明了两个处理并发编程的其他模型：actor模型（消息传递）和monitors（共享状态）。

（注意，Derflow还引入了一种机制，在您真正需要的地方支持显式地引入少量非确定性）。