.. _theory: 分布式理论知识 ========================================= 本章介绍后端常用到的分布式理论知识，包括 cap，base理论，一致性协议算法等。 一致性模型 ---------------------------------------- 弱一致性(最终一致性): - DNS(Domain Name System) - Gossip 强一致性: - 主从同步(一致性高，可用性低) - master 接受写清球 - master 复制日志到 slave - master 等待直到所有从库返回。 - Paxos - Raft (multi-paxos) - ZAB (multi-paxos) 最终一致性根据业务场景可以分为五种： - 因果一致性（causal consistency）。因果一致性指的是：如果节点A在更新完某个数据后通知了节点B，那么节点B之后对该数据的访问和修改都基于节点A更新后的值， 而和节点A无因果关系的节点C的数据访问则没有这样的限制。例如，电商业务里的下单和支付就属于这一种。 - 读己之所写（read your writes）。读己之所写指的是：当节点A更新一个数据后，它总是能访问到自身更新过的最新值，而不会看到旧值。 这也是因果一致性的一种，只不过是单个事件的内部逻辑，而因果一致性可能是多个事件的因果关系。例如，支付系统扣款完成之后再刷新余额就属于这一种。 - 会话一致性（session consistency）。会话一致性指的是：将对系统数据的访问过程限定在一个会话当中，系统能保证在同一个有效的会话中实现“读己之所写”的一致性。 也就是说，执行更新操作之后，客户端能够在同一个会话中始终读取到该数据项的最新值。会话一致性是读己之所写的延伸和扩展。例如，找回密码的操作分为很多步骤，每个步骤都依赖前一个步骤是否成功，所有前置步骤全部按照次序完成才允许修改密码。 - 单调读一致性（monotonic read consistency）。单调读一致性指的是：如果一个节点从系统中读取出一个数据项的某个值，那么系统对于该节点后续的任何数据访问都不应该返回更旧的值。 例如，多机房间用户授权token的同步，只要一个新的token已通过数据同步存储下来了，后面允许存储的token就不应该比这个token更早。这样读取到的token一定是用户更新的授权信息。 - 单调写一致性（monotonic write consistency）。单调写一致性指的是：一个系统要能够保证来自同一个节点的写操作被顺序地执行。 例如，用户多次修改订单信息，那么通过消息队列进行分发最终落地数据库修改时，需要保障用户的操作是按照时间先后顺序被执行的。 基于Kafka的单分区可以保障数据有序，但是这种方式性能有限，也可考虑将每个信息都带上时间戳，再依据时间戳的先后顺序覆盖写入。 Paxos ----------------------------------------- Bacic Paxos ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 角色： - Client: 系统外部角色，请求发起者。(民众) - Proposer: 接收 client 请求，向集群踢出提议(propose)。(议员) - Accpetor(Voter): 提议投票和接收者，只有在形成法定人数(Quorum，一般为majority多数派)时，提议才会被接受。(过会) - Learner: 提议接受者, backup，备份。对一群一致性无影响。(记录员) 阶段： - 1a: Prepare: Proposer提出一个提案编号N，此 N 大于这个 proposer 之前踢出的编号。请求 Accpetor的quorum接 - 1b: Promise: 请求 N 大于此 Acceptor 之前接受的任何提案编号则接受，否则拒绝 - 2a: Accept: 如果达到了多数派,Proposer 会发出 accept 请求(包含N)和提案内容 - 2b: Accepted: 如果Acceptor在此期间没有接收到任何编号大于N的提案，则接受此提案内容，否则忽略 潜在问题：活锁(liveness)或dueling。解决方案，随机超时 难实现，效率低（2轮RPC)，活锁 Multi Paxos ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 新概念，Leader： 唯一的Proposer，所有请求都需要经过此 Leader Fast Paxos ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Raft ----------------------------------------- - http://www.kailing.pub/raft/index.html raft动画演示 - https://github.com/hashicorp/raft 代码实现 参考： ----------------------------------------- - 《设计数据密集型应用》 - https://martinfowler.com/articles/patterns-of-distributed-systems/