分布式系统概念

[BruceChen7]

参考资料

• Distributed Systems 1.1: Introduction - YouTube

• 分布式共识

  (concept:: 广播协议)

• 
• 

(concept:: 广播模型)

• 

(concept:: FIFO 模型)

• 
• 追求的是同一个节点，先发出的消息，必然要比后发出去的消息先收到，但是不同节点发出去的消息不受这个限制，
• 算法违反了因果一致性，
• 尽管 B 节点是收到了节点 A 的消息 m1，再发出消息 m2 上，但是在 C 中，却先收到了 m2，再收到 m1，违反了因果一致性。

因果一致性模型

• 如果一个消息 happen before 另一个消息，那么所有节点必须保持这个顺序。
• 比如上图中，节点 C 先收到这个 m2，然后收到 m1，算法必须先保存 m2，等收到 m1 后，再维护这个顺序。
• 
• 图中，m3 和 m2 没有因果一致性关系，所以在节点 C 中，收到的是 m1，m3 和 m2，而在节点 B 中是 m1, m2, m3，这不违反因果一致性。
• 因果一致性，也就是部分一致性，满足一个时间序列中的部分消息（有因果关系的节点收到消息的顺序是一致的）

Total Order broadcast

• 
• 前面的几种模型都将自己发送给自己的消息，假设成马上能收到，
• 在 total order broadcast 模型中，则不是这样的假设，这样的模型，要求所有的节点，都是看到顺序一致的消息。
• 这个顺序不要求是按照消息开始发送的顺序来看到，而是以收到消息的顺序为一致。
• 这个是线性一致性 Linearizability Consistency

FIFO-total order broadcast

• 总体像 total order broadcast，但是需要额外的 FIFO 模型的要求，
• 同一个消息必须按照发送的顺序在其他节点收到，这个就是严格一致性
• 

广播算法

• 要解决的问题，消息能够被收到，消息的顺序要按照上述模型保持。

可靠的收到消息

• 

• 问题是浪费网络的带宽，后面有优化的算法比如 Gossip 算法。

• 这个算法并不是严格的保证所有的节点都会收到消息，但是如果参数选的好，这种概率是很小的。

• 

复制一致性

• 数据库中的 ACID 中的 C 是由 application 定义的不变性，而复制的一致性是指每个复本，都是一样的。
• 这里有多个 Consistency 的意义：
• 

(concept:: 分布式事务)

• 分布式事务和共识是不一样的 (consensus)：
• 

(concept:: 二阶段提交)

• 

二阶段提交的问题

• 

linearizability

• 线性一致性系统关心的是每个 operation 对应的开始和结束，以及以后最后的结果，不关心每个操作的节点是哪个。

(concept:: 线性 vs happens-before 关系)

• 
• happen-before 定义的是消息的接收和发送的关系，而线性一致性则不是，
• 在上面的图中，client 2 的 get 操作和 client 1 的 get 操作没有 happen-before 的关系，而线性一致性则要求 client 2 的 get 操作需要读取 client 1 set 的值。

非线性系统

• 

解决上述非线性一致性

• 

共识

• 共识，就是多个节点就一个值达成共识。

• 一个或多个节点提出一个值，共识算法用来决定值。

• 已经形式化证明total order broadcast 算法和共识算法是等价的。

• 将 total order broadcast 转成共识，

• 将共识转换成 total order broadcast，用一组运行共识算法的实例来决定第一条，第二条，第三条消息。

• 这组实例保证这些被决定的消息被收到。哪个节点想要广播消息，直接提议一个值，交个共识算法实例来决策。

• 

• 常见的共识算法是 Paxos 和 Raft，Paxo 只是就一个值达成共识，而 Multi-Paxos 实际上是 Paxos 的一般化实现，提供了 FIFO-total order 的广播的实现。

• Raft 也是实现的 FIFO-total order 的一种方式。

共识系统模型

• 
• 对节点和网络的节点假设能弱化成拜占庭的模型，不过这种模型下的共识会非常复杂。
• Raft 和 Paxos 的假设是一个 fair-loss，crash-recovery 的环境。比如私有的数据中心。
• 另外对部分同步的模型不能弱化成完全异步的模式，共识需要一个故障检测器，这反过来又需要一个本地时钟来触发超时。
• 如果没有任何时钟，那么一个确定性的共识算法可能永远不会终止。
• 但是这也不意味着在这种半同步的模型中，需要假设网络的延迟，或者节点的执行速度，意思是可能存在延迟很大，而不是在一个指定范围内。
• 共识算法需要保证系统中的时钟不管是咋样的，即使消息延迟接收了，所有节点的收到消息的顺序是一样的。
• 只有 liveness，也就是消息最终会被收到依赖 clocking 和 timing

领导选举

• 

type/system #ddia #public