DDIA-一致性与共识

- 可序列化：事务的隔离属性，确保事务的行为与串行执行相同
- 线性一致性：读取和写入寄存器的新鲜度保证

- 真的使用单副本。 这是必然线性一致的，但又必然没有容错能力。
- 使用多副本的话会引入复制问题。
    - 单主复制。 如果主从都提供在线读，那么由于主从延迟很可能不线性一致。就算只有主提供服务，从负责热备，那么也可能有脑裂导致不线性一致。
    - 多主复制。多个主节点都处理写入，很可能产生冲突从而不线性一致。
    - 无主复制。使用松散的法定人数，必然不线性一致。如果使用严格的法定人数，也会因网络延迟而不线性一致。
    - 共识算法。 和单主复制类似，但能防止脑裂。

- 线性一致性 VS 可用性。  多主复制是非线性一致的。那么选择了线性一致就意味着放弃了多主复制，这是在多DC部署时放弃了“可用性”
- 线性一致性 VS 性能。 现代多核CPU上的内存是非线性一致的，这是性能考虑。  

- 顺序，有助于保持因果关系。
- 线性一致性 和 因果一致性。  
    - 线性一致性是全序的。系统表现得像只有一个副本，所有操作都是源自的，所以对任何两个操作，总能判断哪个先发生。
        - 在线性一致的数据存储中，不存在并发操作。
    - 因果一致是偏序的。 因果一致的前提是 两件事情是因果相关的，也就是说，如果两件事是并发的，他们的顺序就无法比较。
    - 线性一致性  包含 因果一致性

兰伯特时间戳。 （计数器， 节点ID） 进程自己执行操作数量的计数器。 计数器值越大越新，节点ID越大越新
    https://www.youtube.com/watch?v=CMBjvCzDVkY
    每个节点和每个客户端 跟踪迄今为止见到的最大 计数器值，并在每个请求中包含这个计数器值。当一个节点收到的最大计数器值大于自身计数器值的请求或          响应时，将自己的计数器设置为这个最大值。
    通过兰伯特时间戳，将有因果关系的事件连接成一条路径，这条路径上的事件都是可比较顺序的。
    有因果顺序的一定遵循lamport timestamp，但通过lamport timestamp可比较大小的，不一定有因果顺序!
全序广播。在节点间交换信息的协议。就像append log，一个最简单的全序广播的例子，就是mysql的主从复制
    全序广播 <-> 线性一致

原子提交问题： 2PC -> 更好的共识算法
2PC，引入“协调者”角色。  2PC的提交点归结为协调者上的“常规单节点原子提交”
    2PC的问题是，协调者挂了的话，就只能等待其恢复    —> 3PC，假定网络延迟有界，节点响应时间有限
    2PC的性能问题，引入了太多的网络开销

先有鸡还是先有蛋问题： 单主复制和共识，单主复制就是一个全序广播，前提是“主” 是如何决定的，否则有脑裂问题。而主是如何决定的，需要节点间达成共识
不保证只有一个领导者，而是作出弱保证：协议定义了“时代编号”，在每个时代中，领导者是唯一的
    每当现任leader挂掉时，选举出带有时代编号的领导者
    在任何leader做决定前，需要从法定人数的节点中获取选票，确定自己是最高时代编号的leader后，才能发出决定
    选举领导者的节点 和 对提议进行表决的节点 必须有重叠

SO，共识算法可以看做2PC的进化版。2PC的问题是，协调者挂掉，怎么办，有3种：
1. 等待领导者恢复。这就是2PC
2. 人工故障切换。
3. 使用共识算法（具有时代编号的领导者，决策前需要投票获得法定人数的赞同）选出新领导者