分布式

分布式系统的演进和定义

要理解分布式系统的定义，必须了解应用如何从单体到分布式的演进过程。

单体应用

• 一台机器上部署单一应用
• 受单机性能容量限制
• 单点故障
• 扩展性差

集群应用

无状态集群应用

• 任何一个请求都与之前的请求无关。
• 集群中的节点可以任意伸缩。

有状态的集群应用

• 单一服务的节点集群
  • 节点间完全隔离，只服务对应的用户。
  • 容错性较差。
• 共享信息池的节点集群
  • 多个节点共享信息池。
  • 受信息池容量、性能影响。
  • 存在信息池单点故障问题。
• 信息一致的节点集群
  • 每个节点有独立的信息池。
  • 信息池间同步，存在延迟和一致性问题。
  • 适用于读多写少的场景。

分布式应用

• 将应用拆分成多个子应用。
• 不同节点上可能部署不同的子应用。
• 子应用按需扩展集群。

集群与分布式

• 集群指多个节点做相同的任务。
• 分布式指多个节点协同做一种任务。

广义的分布式

• 判断依据：多个节点是否使用一致的信息池。
• 无论节点部署相同还是不同应用。
• 都面临信息池的同步及数据一致性问题。

分布式系统的基本问题

• 网络通信问题，网络存在抖动断网丢包，通信延迟超时等。
• 节点故障问题，机器宕机、重启等。
• 网络分区问题，集群因为网络问题分裂成多个完全独立的集群。
• 三态问题，每一次请求响应，除成功失败外还存在超时，无法确定请求是否被成功处理。

CAP 定律

• C是Consistency，一致性
  • 指写入成功后，必须保证后续读取到的是最新的数据。如果仍然读取到过期的数据，就是不一致的。
• A是Availability，可用性
  • 指提供正常可用的服务能力，不会发生超时或错误。
• P是Partition tolerance，分区容忍性
  • 指允许集群分裂成多组完全不连通的分区。
• CAP 定律指：分布式系统无法同时满足CAP三种特性，只能满足其二。
• 要保证一致性和可用性，则不能保证分区容忍性，即必须保证网络的可靠性不允许出现分区。
• 事实上，网络是不可靠的，分区容忍性是分布式系统的基本前提。
• 所以只能在一致性和可用性之间做选择。

一致性级别

• 强一致性：承诺始终能读取到最新写入的数据，代价是相对高的延迟。
• 弱一致性：不承诺可以立刻读取到最新写入的数据，但尽可能保证到某个时间级别后读到最新的数据。弱一致性又可分：
  • 会话一致性：保证在同一客户端会话的强一致性，其他会话不保证。
  • 用户一致性：保证在同一用户中的强一致性，其他用户不保证。
• 最终一致性：保证在经过一段时间后最终会达到一致性的特殊弱一致性。

分布式事务

事务具有 ACID 特性：

• A 原子性：要么成功，要么失败，没有中间状态。
• C 一致性：事务执行前后，数据库完整性约束不会被破坏。
• I 隔离性：不同事务之间不会相互影响。
• D 持久性：一旦事务提交，数据将持久保存。

分布式事务是指在分布式系统上实现事务，同样需要保证 ACID，尤其是一致性。
分布式事务保证强一致性，但牺牲可用性。

2PC 协议

• 2PC协议用于实现分布式事务，用于保证分布式系统的强一致性。
• 2PC是两阶段提交，分为准备阶段和提交阶段。
• 其关键点是，在准备阶段尽可能完成所有工作，而提交阶段将是耗时极短失败概率小的操作。
• 其实现，必须存在一个中心化的协调者，负责协调参与者的行为。
• 如果协调者单点故障将出现数据不一致现象。

3PC 协议

• 3PC协议是2PC的改进，目标与2PC相同。
• 3PC是三阶段提交，分为准备阶段、预提交阶段和提交阶段。
• 对比2PC，3PC对协调者和参与者都设置了超时时间，在参与者等待提交超时后会自动提交。
• 在提交阶段，如果协调者发出回滚，但参与者失联会提交，则出现数据不一致情况。

TCC 协议

• TCC是业务层面的2PC，而2PC和3PC都是分布式数据库事务的协议。
• TCC是Try-Confirm-Cancel。
• Try 阶段是准备阶段尽可能完成所有工作，都成功则 Confirm，否则 Cancel。
• Confirm 和 Cancel 必须保证幂等，而且 Cancel 允许空回滚。

BASE 理论

BASE 是对 CAP中一致性和可用性权衡的结果，核心思想是即使无法做到强一致性，但可以根据自己的业务特点，采用适当的方式达到最终一致性。
BASE 来源于对大规模分布式系统实践的总结。

• BA是 Basically Available，基本可用
  • 如损失响应时间
  • 如保证核心功能可用，损失部分功能的可用性
• S是 Soft State，软状态
  • 允许系统中的数据存在中间状态，并认为该中间状态不会影响系统整体可用性。
• E是 Eventually Consistent，最终一致性
  • 所有数据副本经过一段时间后，最终会达到一致

共识算法

• 共识算法是对 BASE 理论的实践。
• 目标是使分布式系统在出现各种异常（网络故障、节点故障、网络分区等）时，仍然能够达成最终一致。
• 共识算法和分布式事务区别：分布式事务保证绝对一致性牺牲可用性，而共识算法通过保证共识达成最终一致性。
• 常见共识算法有 Paxos、Raft。
• Paxos 和 Raft 都是解决非拜占庭容错问题，即不存在恶意节点伪造信息。
• Paxos 是最早提出的共识算法，比较复杂。
• Raft 比较新，相对简单。Raft 是当前分布式系统的首选算法。

Paxos 算法

• Paxos 算法是分布式系统中实现一致性的算法。
• 基本思想
  • 将节点分为提议者、接受者、学习者。
  • 提议者提出提案，接受者接受提案并投票，学习者学习已经达成一致的提案。
  • 需经过多轮的消息交换和投票产生一个大家认可的值，然后所有节点执行操作最终达成一致。
• 优点
  • 较高容错性，能容忍节点故障和网络延迟
  • 较高扩展性，适应不同规模的分布式系统，从几个节点到几千个节点
• 缺点
  • 复杂型，理解和实现有一定难度
  • 性能，多轮消息交换有性能开销
• Zookeeper 的zab 算法基于 Paxos 算法改进而来。

Raft 算法

• 比 Paxos 更具可理解性。
• 通过 Leader 选举、心跳机制、日志复制等方式来维护数据一致性。
• Etcd 采用 Raft。

日志复制：

• 基于复制状态机模型实现
• 相同的初始状态+相同的输入=相同的结束状态
• 相同的输入通过操作日志实现

Leader 选举：

• 节点角色
  • 领导，负责提交日志，并广播日志
  • 跟随者，负责日志复制
  • 候选人，竞选 Leader
• 任期
  • 作为逻辑时钟，通过任期 ID 识别过期信息
  • 节点之间通信会对比任期，更新到最大
• 心跳机制
  • 领导节点通过广播心跳给其他节点
  • 其他节点收到心跳后重置定时器，定时器过期后认为领导不存在开始选举
• 选举过程
  • 跟随者将自己的任期 ID 加 1，标记自己为候选人，向其他节点拉票。
  • 其他节点根据先到先得原则投票，票数超过节点数的一半则当选。
  • 收到宣称领导的信息时，对比任期 ID 来接受或拒绝。
  • 如果一轮出现多个候选人且票数一样则无法得出领导人，会再次选举。

写入过程：

• 只有 Leader 节点可以处理写入请求。
• Leader 收到请求后，将请求添加到日志中，然后向其他节点复制日志。
• 只有超过一半节点复制成功 Leader 才认为写入成功。

读取过程：

• Raft 共识算法本身并不保证读取的强一致性，需使用额外的手段。
• 如确保 Leader 的最新日志已复制到当前节点再读取，才能保证强一致性。

一致性哈希

哈希算法在分布式集群中的应用场景：

• 请求的负载均衡，对于请求IP进行哈希，然后对集群节点数取模，可以映射到具体节点上。
• 分布式存储，对 key 值取哈希，然后对集群节点数取模，可以锁定到具体节点上。

普通哈希算法，如果节点数发生变更（故障或扩容），则映射关系会大量失效：

• 请求的负载均衡，会路由到其他节点，导致原会话丢失。
• 分布式存储，需要迁移大量数据。

使用一致性哈希，可以避免映射关系大规模失效。

算法要点：

• 将节点标识和请求 key 的都进行哈希，然后对 2 ^32 取模，映射到 [0, 2^32-1] 上一个值上。
• [0, 2^32-1]形成了一个哈希环，从 key 的位置在环中顺时针找到第一个节点则是映射的目标节点。
• 为防止分布不均，将节点映射成多个虚拟节点，再将虚拟节点映射到环上。

幂等

• 幂等是指对同一操作发起多次请求时，对系统状态的影响是一致的。
• 分布式系统中，接口有三态问题（成功、失败、超时），为提高系统可靠性，重试是不可避免的。
• 通常查询和删除操作具有幂等性，而新增和修改操作不具有幂等性。
• 将非幂等操作转换为幂等的方法：
  • 唯一约束，生成全局唯一ID（UUID 或雪花算法），利用数据库唯一约束进行防重。
  • 乐观锁，对数据加版本号，写入时把之前读取的版本号作为条件同时对版本号加 1。
  • 防重token，操作前先获取 token，操作时服务端通过token 判断是否重复提交。

分布式锁

• 锁用于控制多线程对同一个资源的并发访问，将访问串行化，避免相互干扰。
• 分布式锁是在分布式系统中实现的锁，控制不同节点上对同一资源的并发访问。
• 分布式锁的实现，本质是通过将锁保存在节点外的共享存储中来实现，如：
  • 数据库悲观锁
  • 数据库乐观锁
  • 基于Redis的分布式锁
  • 基于Zookeeper或 Etcd 的分布式锁