分布式一致性简史

来自 https://betathoughts.blogspot.com/2007/06/brief-history-of-consensus-2pc-and.html

第一个一致性问题是从 Lamport 大神的 1978年Time论文指出，虽然他没有明确提出consensus or agreement的概念， 但他提出了分布式状态机的概念（复制状态机， RSM）， 一组确定状态机，从相同初始状态开始，确保他们以相同顺序处理相同消息，可以确保每个状态机都是其他的状态机的副本。 关键是，哪个消息是下一个需要处理的消息，达成一致， 这就是一致性问题。

1979年 Jim Gray描述了2PC，但是2PC会Block，随后，Dale Skeen在1981年提出3PC, 但是找到好的3PC算法花了近25年。

1985年 著名的FLP Impossiblility被提出。 即一个异步系统即使只有一个进程出错，分布式一致性也不可能达到。跟海森堡的测不准原理有些神识。此时 Consensus变成，让一系列处理器在一个value上达成共识的问题。 核心是没法区分，是低速执行，还是终止。

这时，人们意识到分布式算法有两个非常重要的属性， safety liveness 前者：坏的事情不会发生，后者：好的事情最终会发生。

虽然，2pc保证safety，但是liveness非常不好。

同时：分布式系统被分为同步，异步两种， 同步看做异步的特例， 它的消息传输时间有上界。

1982年 Byzantine Generals Problem： 进程会说谎。

1986年，一致性和事务聚在一起。 最好的一致性算法是Byzantine Generals，但是代价太高，根部无法用于事务处理。

1987年 Jim Gray， 指出分布式事务是一个新的一致性问题，不是bg的退化版本，分布式事务是uniform consensus（2010年） 所有进程必须在一个value上达成一致，即使是那些出错进程。

进入90年代，曙光来临：

• 1990年 Lamport提出 Paxos

• 1996年 Lampson引用Paxos

• 2001年 Lamport 发表 Paxos Made Simple

Paxos及Paxos-like的出现，大有一统分布式一致性的趋势。

而针对分布式系统的同步异步问题，人们发现：系统简单划分同步异步有些宽泛

1988年 Dwork Lynch Stockmeyer定义了部分同步系统：

进程已给点bound的速率运行，消息传输时间有界，但边界的实际取值无法得知
处理速度和传输的边界一直，只是在未来某个未知时间开始。

2005年 Lamport Jim Gray将Paxos应用的分布式事务提交中， 用于容错，解决block问题。进行了整体融合。