陈述性命令：分布式逻辑中的经验和猜想 - 《Apaas平台》

本文是JoeHellerstein在2010年ACM播客会议上的一个邀请演讲的扩展版本。因此，主要的读者是数据库研究人员，但这里也有一些值得我们思考的好东西。本文介绍了CALM猜想。

……以数据为中心的编程语言比计算历史上任何时候都更受关注，部分原因是这些语言自然并行。

我们都很熟悉这几天的“没有免费午餐”争论：

摩尔定律不再预测芯片的时钟速度，而是它所提供的并行度。因此，随着时间的推移，传统的顺序程序不会变得更快。[…]同时，除非开发人员能够编写利用并行性的程序，同时管理分布式计算机集群特有的异构性和组件故障，否则云计算的潜力将无法发挥。

尊贵的数据日志有什么可以提供给我们的吗？

我们已经演示了分布式系统的全功能数据日志式实现，这些实现比流行的强制实现系统要紧凑几个数量级，具有竞争性的性能和显著加快的软件演进。越来越多的证据表明，数据日志可以作为一个简单得多的语言家族的基础，用于编程严肃的并行和分布式软件。

这项工作是由伯克利秩序的Magnitute（BOOM）项目开发的Bloom语言的根源。数据日志是一种逻辑编程语言，在精神上类似于Prolog。支持Bloom的Dedalus扩展了数据日志：

……在过去的12个月里，我们已经解决了一个数据日志变体，它清晰地捕获了我们所认为的并行和分布式计算的显著语义问题。我们称之为Dedalus语言，它的主要贡献是将时间作为分布式系统的组织原则，而不是物理空间中的距离。

管理大型图形的关键web基础设施仍然是用命令式语言编写的。

我们的声明式编程工作开始于对Web的响应，其重点是大型图和网络…正如所料，Datalog是一种优秀的语言，用于表示传递闭包和图遍历，以及这些任务[Web爬虫、p2p网络爬虫、网络路由协议，分布式贝叶斯信念传播算法]对代码来说几乎是微不足道的。

数据日志的流水线半朴素评估策略（见本文参考文献）使单调逻辑令人尴尬地并行。

这句话很重要：一大类递归程序（所有的基本数据日志）可以并行化，而无需任何协调。顺便说一句，这种见解似乎已经被MapReduce社区所回避，在那里join必然是一个阻塞操作符…。

这一见解引出了一个冷静的猜想：

一致性和逻辑单调性（平静）。当且仅当程序在（单调的）数据日志中可表示时，程序具有最终一致的、无协调的执行策略。

“无协调”特性是关键，而且Vardi证明了（单调的）数据日志可以在数据库大小的时间多项式中实现。

我们还有一个鲜为人知的CRON猜想：

只有非单调性（CRON）才需要因果关系。当且仅当消息参与非单调派生时，程序语义要求因果消息排序。

单调性意味着我们只增加信息，从不否定或带走。

整篇论文在某些方面（至少对我来说）很难被批判性地理解，但它暗示了尚未达到主流的进展，正如论文的结论所说：

“数据族”似乎有一个最好的光源：我们多年来成功地并行SQL，我们有MapReduce作为连接同事的桥梁的共同文化，我们有易于移植到实践中的声明性逻辑语言的花园。

现在，如果我们能把函数式编程和逻辑编程结合起来，我们就会有FLOG，混合一些反应式编程，我们就会得到FlogR。