Table of Contents

  1. Algorithm
  2. Review
    1. 形式化定义
    2. 两阶段提交
    3. 故障
    4. 总结
  3. Tips
  4. Share

Algorithm

Leetcode 649: https://leetcode.com/problems/dota2-senate/

https://medium.com/@dreamume/leetcode-649-dota2-senate-9f8adff6526

Review

Consensus Protocols: Two-Phase Commit

https://www.the-paper-trail.org/post/2008-11-27-consensus-protocols-two-phase-commit/

共识问题指一系列分布式节点在某些事情上达成共识，可能指某个值、行为或决定，使分布式系统看起来像一个实体，网络中的每个节点都知晓或参与该共识。

例如，一些可能的共识：

  1. 决定是否提交交易到数据库
  2. 同步时钟，对当前时间达成共识
  3. 同意进入分布式算法的下一阶段
  4. 选举领导者来协调一些高层协议

共识问题成为二十多年分布式理论研究的中心，原因如下：

  1. 共识问题是一个有挑战的难题，能够表征出不同系统模型的差异，如之前博客里提到的FLP所述，共识问题在同步系统中是可解的，但在有故障可能性的异步系统中不行。问题在于两种模型的阶段边界，并且严重依赖时序。
  2. 制作正确的共识协议很困难。简单的解决方案并不能很好的工作，会表现出的奇怪行为和偶尔行为异常。Mike Burrows，谷歌Chubby服务的发明者，说“只存在一种共识协议：Paxos“ – 所有其他的都是不完美的Paxos。Paxos协议非常精妙，理解起来也有点困难。
  3. 共识是非常重要的问题。分布式系统依赖于它。事实上，大部分分布式系统搭建需要基于共识。组成员系统、故障容忍复制状态机、数据存储 – 所有典型的分布式系统在某些程度上都取决于能够解决共识。共识跟原子广播问题同构，原子广播指网络中转发消息是可靠的且对所有节点总体有序。

形式化定义

我们说一个节点最终做出决定是当它认为其他节点都同意该值。更形式化的定义是每个节点有一个输出寄存器，一旦协议终止，该寄存器中存有该决定好的值。对该寄存器写入值的动作即是做决定。

节点提议某值，即建议某值作为决定值。协议不能授权节点提议任何值。

基于以上的定义，假设一个分布式系统有N个节点，我们认为共识协议正确当且仅当：

  1. 同意 – 所有节点决定相同的值
  2. 有效 – 决定的值必须是N个总节点中部分节点提议的
  3. 终止 – 所有节点最终做出决定

我们可以弱化同意指大多数节点同意即可。

一些协议会指定节点一个决定缺省值，不管当前网络实际状态如何。例如数据库提交协议默认是不提交，不管交易是否满足同意的条件。有效性确保协议不会这么做。

同意限定了节点如何决定，终止确保最终会决定某值。

两阶段提交

两阶段提交是一种解决共识问题的简单方案，分两步：

  1. 联系每个参与者，提议一个值并收集其回复
  2. 如果每个参与者都同意，则联系每个参与者该消息，否则联系每个参与者取消该共识

提议的节点叫做协调者，协调者不需要选举，任意节点可以作为协调者，初始化2阶段提交的过程。

两阶段提交同样满足共识问题的条件，每个节点同意协调者提议的决定值当且仅当在每个节点被告知在第二阶段协调者所做的事情。协调者给每个节点发送相同的决定值，所以一个节点被告知决定则所有节点也被告知同一个值。

有效性同样满足，除非所有节点同意提交否则都会取消，决定值至少需要被一个节点提议。

当协调者收到所有节点的回复，并最终以决定值联系每个节点则保证了协议被终止。异步模型保证每个消息都被处理并且所有回复被发送。两阶段提交不会发送循环，所以一定会在某时刻正常终止。

两阶段提交作为共识的解决方案优点是非常高效，对n个节点只需要3n次消息，对它进行改进优化比较困难。

如果节点允许故障，即是一个节点可能故障，事情将会变得非常复杂。

故障

节点会因几种方式崩溃。最简单的，会崩溃并无法恢复，或崩溃然后在某时间点恢复并继续执行。更一般地，节点会在共识协议中的任意时刻出现问题，这被称为拜占庭故障，设计协议处理这种故障目前是研究的一个活跃领域，相当困难。我们目前考虑最常见的前两种故障。

我们看一下故障在两阶段协议中的情形，考虑协调者或参与者在协议中的每个阶段状况。

在第一阶段，在任何消息被发送前，协调者可能崩溃。这种情况两阶段提交不会启动。如果参与者在协议初始化之前故障，则提议消息发送给该参与者会失败，我们之后会处理这种情况。

考虑提交消息已发生部分节点，但还没有到全部节点，这时协调者故障则部分节点已收到提议并开始两阶段提交过程，另外的节点则完全不知晓。如果协调者长时间不恢复，接收到提议的节点将阻塞等待。则协议的其他实例不能正常执行，因为参与者在占有资源锁投票提交过程中。这些节点发送它们的投票给协调者，但并不知道协调者已故障，因此不能简单超时处理或者取消，因为协调者可能重新恢复，并看到它们的投票然后继续。

协议则被阻塞在协调者这边。我们可以添加一些机制来处理这种情况。一但我们意识到协调者故障，我们可以让另一个参与者作为协调者的角色工作。当一些节点发送超时时，我们可以强制节点结束协调者发起的协议。该节点联系其他所有节点，找到它们的投票。这需要所有节点存储所有两阶段协议执行的结果，直到它们知道所有其他节点已提交或取消。否则如果所有节点忘记它们的执行，则代替协调者工作的恢复节点无法恢复交易的状态。

然而，在恢复节点完成共识协议之前另一个参与者发生故障，协议状态将不能恢复。恢复节点不能区分所有节点已经投票提交及故障的节点已提交（这种情况下缺省为取消是无效的），所有节点除了故障节点已经投票提交，故障节点投票取消（这种情况缺省为提交是无效的）。

如果提交信息发送给所有节点之前协调者故障，我们需要一个恢复节点作为协调者，指导协议完成。

最坏的情况是当协调者本身也是一个参与者，当这个协调者故障时，协议将阻塞。

协调者将记录所有成功的协议结果，这样当它恢复时它能知道交易是否已提交。这将允许参与者定期的日志垃圾收集，协调者可以告知参与者不能恢复一个手动的提交交易并且可以从日志中删除的行为。

总结

两阶段提交是一个流行的共识协议，它的消息复杂度低（虽然在故障情况下，如果所有节点决定作为恢复节点会导致复杂度为O(n2)）。参与者跟协调者通话的回复只有3个消息的延迟时间。低延迟对一些应用程序非常有吸引力。

然而，两阶段提交会被协调者故障所阻塞，影响可用性，如果交易可以在任意时间回滚，则协议可以在节点超时时恢复，如果协议永久地谨慎对待任何提交决定，错误的故障将导致严重的瘫痪现象。

目前仍有最前沿的研究信奉两阶段提交。最有影响的论文是Sinfonia，其获得了SOSP 2007最佳论文奖。它在两阶段提交基础上构建了一套分布式内存，使协调者故障可恢复（通过超时和恢复节点干涉）。内存节点崩溃认为是不可恢复的（但内存节点本身是高可复制的）。

Tips

  • 如看书看不懂的地方，找同类的书多翻翻，可能这本书上看不懂的地方其他书上讲得很详细

Share

Swift Concurrency Manifesto

https://gist.github.com/lattner/31ed37682ef1576b16bca1432ea9f782

Swift发明者Chris Lattner写的关于Swift语言并行问题的文章，讲述了Swift在并行上如何发展，参考了其他语言并行的优点。

强调Swift聚焦于基于任务的并行，而不是数据的并行。认为多核是目前的主流但未来不是。设计新并行模型必须考虑与现有并行结构和api兼容。

认为共享可修改的状态是不好的设计。

简单介绍了目前4种主流的计算抽象：

  1. 传统的控制流
  2. 异步控制流
  3. 消息发送和数据隔离
  4. 分布式数据和计算

Async/await是漂亮的异步API，被用于其他多个语言，Swift考虑把async，await作为关键字来支持。

采用actor model，因为其有很强的学术研究历史及已被elang和AKka使用大型可扩展可靠性的系统中。

actor model理论基础研究从1970年就开始了。学术界设想了一个纯actor model（一切即actor），model的通讯限制很强，这是Swift不能接受的。

Wikipedia里介绍：

对接收到的消息，actor可以做本地决定，创建更多的actors，发送更多的消息，决定如何处理下一个消息。actors可以修改私有状态，但只能通过消息来影响其他actors。

actors很方便创建，你可以跟actor高效地建立单向异步消息发送。因为消息单向，不需要等待，因此不会产生死锁。在学术界中的actor模型，所有的数据都是深度拷贝，actors之间不共享数据。actors之间不借助互相的状态（也不会访问全局状态），因此不需要同步，没有共享可修改状态的问题。

actor模型没有返回值，Swift可以通过结合await，以便能接收actor返回值。

let x = await self.getNumberOfEntries()   // trivial deadlock.

由于界面刷新等操作必须在主线程，可以实现一个actor单例，确保该actor的操作都是在主线程。

public actor MainActor {  // Bikeshed: could be named "actor UI {}"
   private init() {}      // You can't make another one of these.
   // Helpful public stuff could be put here to make app developers happy. :-)
}
public let mainActor = MainActor()

另一种设计上的考虑是把actor设计为类。

接下来讨论了可靠性问题，隔离故障。

基于以上提到的Swift化的actor模型有两个问题：

  1. 如果await在一个actor方法上，如果actor崩溃则可能一直等待
  2. 丢失消息可能导致死锁

使用reliable关键字构造更复杂一些的可靠的actor，actor方法崩溃可通过throw捕获。

间接丢失消息可通过如下两个方法解决：

  1. 提供标准库API注册actor的失败处理函数
  2. 强制所有actor方法抛异常

进程间通信、客户端服务器通信、服务器之间的通信也是通过异步消息，且不能共享可修改状态。这些是不是听着很熟悉。我们可以改进系统架构：

  1. 客户端服务器之间代码写在不同实体上，API需要独立发展
  2. 网络引入新的可失败模型，原来的API可能不适应，可通过发展可靠actor解决
  3. 消息中的数据需要支持Codable协议
  4. API设计需要考虑延迟问题

最后提到了其他语言的并行设计：

Pony，基于actor，提供类型安全、内存安全、deadlock-free、datarace-free的编程模型。Pony为提供引用能力有大量的复杂度设计，导致学习曲线很高。

Akka Actors in Scala，基于actor，已被大量不同的组织和人使用，不同的是这里的它是一个库特征，不是语言特征。不能提供附加的类型系统和安全特性。

Go，基于goroutines和可双向的channels，支持方便优异地写并行程序。

Rust能够基于库的并行pattern，支持message passing，支持共享可修改状态的锁和其他类型抽象，Rust适合系统程序员。