Bloom中的一致性分析：一种CALM而集中的方法 - 《Apaas平台》

论文地址： Bloom中的一致性分析：一种CALM而集中的方法 – Alvaro et al. 2011

本文有几个大的想法：

第一，引入关于分布式系统行为推理的CALM原则；
第二，一种叫做Bloom的声明性语言，它鼓励CALM编程，并且非常适合分布式的固有特性；
第三，以这种方式开发软件的实用指南和工具。

我们证明，通过“无序”编程模式，辅以自动分析技术，以原则性的方式识别和管理程序的顺序点，我们可以将该理论应用到软件开发实践中。

如果你对深入挖掘布鲁姆的理论基础感兴趣，你可能想看看乔·海勒斯坦的“陈述性命令：分布式逻辑中的经验和猜想”论文。另外，别忘了读彼得·阿尔瓦罗关于Edelweiss: 分布式编程的自动存储回收的后续工作。

面对不确定性保持CALM
分布并发性和异步性、性能可变性和部分故障的挑战通常转化为任务协调和数据一致性方面的棘手的数据管理挑战…。指导程序员解决这些问题的工作主要有两个方面。

首先是分布式事务的“ACID”基础，以可串行化读/写调度和Paxos和两阶段提交等一致性协议的理论为基础。
第二个参考点是研究和系统开发的长期传统，它使用特定于应用程序的推理来容忍由于读、写和消息的灵活排序而产生的“松散”一致性。

后一种方法可以提供更好的可用性和/或更低的延迟，但“通常不清楚以这种方式构建的系统提供了什么保证。“暂时的不确定性（即不知道什么时候会发生）是许多困难的根源。然而，如果我们具有顺序独立性（时间不确定性的容忍度），我们最终可以是一致的。基于集合的声明式语言往往具有这种特性，关系数据库和逻辑编程的理论有助于我们对它们进行推理。

单调程序——例如，可以通过选择、投影和连接（甚至是递归）来表示的程序——可以通过流算法来实现，该算法在接收输入元素时递增地生成输出元素。输入的最终顺序或内容一旦生成，就永远不会导致任何先前的输出被“撤销”。非单调程序——例如，那些包含聚合或求反操作的程序只能通过阻塞算法正确实现，这些阻塞算法在接收到输入集逻辑分区中的所有元组之前不会产生任何输出。

因此，单调程序易于分发，并且可以容忍消息重新排序和延迟。相比之下，即使是简单的非单调任务，如计数，在分布式系统中也很困难

作为一种助记符，我们说计数需要在分布式系统中等待：一般来说，在产生正确的输出之前，一个完整的分布式数据计数必须等待其所有输入，包括散乱的输入。“等待”是通过协调逻辑（Paxos，2PC，…）在程序中指定的。

正如我们在过去两周所看到的，分布式共识还包括计数（以确保达到法定人数）。因此，我们也可以说“等待需要计算”

这里有一个重要的想法：

我们对等待和计数的观察说明了我们称之为平静原则的关键：一致性和逻辑单调性之间的紧密关系。单调程序保证了在任何交付和计算交错的情况下最终的一致性。与此相反，非单调性（将元素添加到输入集中的属性可能会撤销输出集中以前有效的元素）要求协调方案“等待”直到可以保证输入是完整的。

我们希望尽量减少协调的数量（出于延迟和可用性的原因）。通过在逻辑语言上构建程序，我们可以开发分布式一致性检查，因为在该领域中，对单调性的保守测试是很好理解的。

如果分析不能保证整个程序的单调性，它可以提供程序中可能需要协调以确保一致性的点的保守评估。

如果这听起来有点吓人，别担心。这些想法可以体现在一个2400行的Ruby DSL中，具有惊人的能力。

保持CALM，暗号
冯·诺依曼体系结构带来了一系列隐含的排序假设…

传统的命令式编程源于这些关于顺序的普遍假设。因此，流行的命令式语言与并行和分布式平台不匹配也就不足为奇了，因为并行和分布式平台很少保证执行和通信的顺序。相比之下，面向集的方法（如SQL）和批处理数据流方法（如MapReduce）可以更好地转换为对顺序有松散控制的体系结构。布鲁姆是按照编程风格的传统设计的，这种编程风格在本质上是“无序的”。状态以无序集捕获。计算是用逻辑来表示的：一组无序的声明性规则，每个规则由一个无序的谓词连接组成。

Bloom程序由一组本地集合（state）和一组关于这些集合的声明语句组成。

Bloom语句是根据原子“时间步”定义的，原子“时间步”可以通过连续的轮求值来实现。在每个时间步中，由于持久性或来自外部代理（例如，网络或系统时钟）的消息到达，集合中存在某些“基本事实”。Bloom程序中的语句指定其他事实的派生，这些事实可以声明存在于当前时间步、下一个时间步或将来某个不确定的远程节点上。

Bloom没有副作用，没有易变状态。集合可以是五种基本类型之一，语句遵循简单的“lhs-rhs”格式。集合类型为：

表–跨时间步持续存在的集合
scratch–其内容仅持续一个时间步的集合
通道–具有特殊位置说明符属性的暂存集合。元组“出现”在此位置说明符指定的网络地址
周期性——一个临时集合，其中元组“出现”的时间大约为每一个周期秒，具有唯一的id和当前的wallclock时间
接口——特别指定为模块间接口点的暂存集合

操作符包括：

scratch=rhs（scratch的内容由这个时间段的rhs决定）
table或scratch<=rhs（lhs包括当前时间步中rhs的内容）
table或scratch<+rhs（lhs将在下一个时间步中包含rhs的内容）
表<-rhs（在下一个时间步中，lhs不包括rhs中的元组）
通道<~rhs（rhs中的元组将在未来某个时间出现在远程lhs中）
这些信息应该足够让您对下面可靠的单播消息传递程序的工作方式有一个良好的印象。请参阅完整的论文，以获取一个工作过的键值存储示例，其中包括存储的抽象规范以及单节点和分布式实现。

module DeliveryProtocol
def state
interface input, :pipe_in,
[‘dst’,’src’,’ident’],[‘payload’]
interface output, :pipe_sent,
[‘dst’,’src’,’ident’],[‘payload’]
end
end

module ReliableDelivery include DeliveryProtocol

def state
channel :data_chan, [‘@dst’,’src’,’ident’],[‘payload’]
channel :ack_chan, [‘@src’,’dst’,’ident’]
table :send_buf, [‘dst’,’src’,’ident’],[‘payload’]
periodic :timer, 10
end

declare
def send_packet
send_buf <= pipe_in
data_chan <~ pipe_in
end

declare
def timer_retry
data_chan <~ join([send_buf,timer]).map{|p,t| p}
end

declare
def send_ack
ack_chan <~ data_chan.map{|p| [p.src, p.dst, p.ident] }
end

declare
def recv_ack
got_ack = join [ack_chan, send_buf],
[ack_chan.ident, send_buf.ident]
pipe_sent <= got_ack.map{|a, sb| sb}
send_buf <- got_ack.map{|a, sb| sb}
end

end

针对CALM模型的深度思考
Bloom程序可以看作是一个数据流图，外部输入接口作为源，外部输出接口作为汇，集合作为内部节点，规则作为边。此图表示程序中集合之间的依赖关系，由Bud解释器自动生成。

生成这样一个图使程序的可视化变得容易，特别是看到由于非单调性而需要协调的点。（当然，这是基于逻辑的语言的基本特性，使这种分析成为可能）。这有助于你对自己的设计进行理性思考，或许可以选择减少所需协调量的替代方案。一个工作购物车的例子显示了这些想法在行动。第一种方法是响应一个删除请求从购物车中删除商品（表面看来这是个好主意！）。但第二种方法只是将更新请求（添加和删除项）累加在单调递增的集合中。此集合仅在签出时“汇总”。现在我们只在结账时需要它，而不需要在每一个购物车动作上进行协调。

严格单调的程序在实践中是很少见的，因此经常需要添加一些协调来确保一致性。在这个运行示例中，我们在程序分析的帮助下研究了简单分布式应用程序的两个候选实现。两个程序都有顺序点，但是分析工具帮助我们对它们的相对协调成本进行了推理。判断无序方法“更好”需要我们应用领域知识：与cart操作及其复制相比，checkout是一个粗粒度的协调点。

如果添加额外的协调是不可取的，Bloom的“顺序点”分析可以帮助程序员找出他们需要在哪里采取适当的措施来容忍不一致。Helland和Campbell的“流沙上的建筑”论文被引用为一个模型，我们可以从中获得灵感（我很快会在早报上报道）。这引入了记忆、猜测和道歉的概念。

这些模式中的大多数都可以实现为自动程序重写。我们设想构建一个系统，该系统有助于在前台运行低延迟、“猜测”驱动的决策，以及作为后台进程的昂贵但一致的逻辑。当后台进程检测到前台系统产生的结果不一致时（例如，由于“猜测”结果被证明是错误的），它可以通过生成“道歉”来采取纠正措施。重要的是，这两个子系统都是同一个高级设计的实现，除了具有不同的一致性和协调性需求之外；因此，应该可以从同一个源代码合成程序的两个变体。在这个过程中，我们可以计算“猜测”，存储适当的“记忆”，并生成必要的“执行回退”——我们看到了构建脚手架和工具支持以减轻程序员负担的重要机会。