CAP

• 原理：分布系统中Consistency(一致性)、Availability(可用性)、Partition Tolerance(分区容错性)，三者不可兼得
  • A(Consistency)：在分布式系统中，同一时刻，同一数据(包括备份数据)，在不同的模块中的是否相同。
    • 分级：强一致性(单机中一份)、会话一致性、弱一致性(最终一致性)。
  • C(Availability)：在集群中一部分节点故障后，集群整体是否还能响应客户端的读写请求。
    • 一般操作：同一服务、开的应用进程越多、越稳定。
  • P(Partition Tolerance)：在分区发生的情况下，当外部请求到来时，怎么处理错误(网络问题，通信的时限获取数据要求)，在提供什么程度服务和保证怎样的一致性下的一种权衡取舍策略
• 选择策略：
  • CA:单机服务。
    • 单机mysql :C + A
    • zookeeper:C + 不错的A
    • 两阶段提交协议：C + 糟糕的A
  • CP：担心提供给用户的不是最新的数据（最新的数据可能恰好在分区另一侧）而拒绝服务保证强一致性C,超过了规定的通信时间(舍A取C).
  • AP：在保证高可用性(服务不挂)的情况下，在通信时间类直接返回获取到的数据(无论次备份数据是否最新)，此时C被牺牲了(舍C取A)

Paxos算法

• 原理：基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。
• 角色：一个进程可能同时充当多种角色 。Proposer可以提出（propose）提案；Acceptor可以接受（accept）提案；如果某个提案被选定（chosen），那么该提案里的value就被选定了
  • Proposer：只要Proposer发的提案被Acceptor接受（刚开始先认为只需要一个Acceptor接受即可，在推导过程中会发现需要半数以上的Acceptor同意才行），Proposer就认为该提案里的value被选定了。
  • Acceptor：只要Acceptor接受了某个提案，Acceptor就任务该提案里的value被选定了。
  • Learners：Acceptor告诉Learner哪个value被选定，Learner就认为那个value被选定。
• 基本流程：二次确认，二次修改
  • 阶段一：接受提案(确认提案号)

    • P发送给A：版本号(提案号)：n
    • A返回：
      • a之前版本号n1>n：返回给P的提案号n1，拒绝接受提案号。
      • a之前版本号n1<n: 返回给P的提案号n，保证n为最新提案号。

  • 阶段二：确认提案值。(下面讨论该阶段A都已经接受提案号n)

    • P接受A回传：
      • 发送 {n,v} --({提案号:提案值})
    • A接受 {n,v} 后回传 {n,{n1,v1}} {提案号,{前一次提案号，前一次提案值}}
      • a之前版本号n1>n：拒绝接受提案值。
      • a之前版本号n1=n: 直接返回。
    • P接受 {n,{n1,v1}} 后，选出最大值 v1 作为最终提案值(这里由于中间A又接受了新的提案号，但是还是修改版本值)，发送 {n,v1}
    • A接受 {n,v} ，v1 作为最终提案值

  • 其它：

    • 阶段一: P 被A 拒绝接受提案号(n1>n)，则将提案号改为 n1，c。
    • 阶段二：P 被A 拒绝接受提案值(n1>n)，查看所有的返回值:
      • 如果A接受者超过一半，则默认为提案值被都已经接受，发送通知修改版值。
      • 如果A接受者没有超过一半，在重新开始。