一瞥之见

0%

分布式系统（-）：一些相关基础理论/协议/算法/应用及其相互之间的关系

发表于

文章结构说明

最近系统的在学习分布式系统相关的理论和协议。经过长时间的“混乱”、终于现阶段的理清了相关概念及其之间的联系等。本文会使用渐进式的说明在分析/设计分布式系统的过程中依次需要使用到的理论/实现，争取让我/大家了解各个概念/协议/具体算法具体在分布式系统中的什么“位置”会用到，从而也就了解了其间的关系。

前言
本文仅讨论故障容错系统，不讨论存在恶意节点情况下的分布式系统
本文仅说明协议/算法之间的关系，暂不做详细说明（避免搞错了本文的重点）

1：分布式系统的指导理论（不那么有用的CAP -> 真正有用的PACELC）

CAP

定义
  • C - consistency 线性/强一致性：客户端的每次读操作，不管访问哪个节点，要么读到的是同一份“最新”写入的数据，要么读取失败。注意，这里的最新指的是读取事务开始时间之前的已提交事务的值，见下图（此图来自），图中的D读到的数还是1才对：
    cap-c
  • A - availability 可用性：任何来自客户的请求，不管访问哪个非故障节点，都能得到响应数据，但是不保证是同一份最新的数据
  • P - partition tolerence 分区容错性：当集群存在节点间通信问题时，若系统仍能继续工作，就是满足分区容错性的。由于分区通信故障不可避免的存在，故P是必须要保证满足的
常见误区之只能选择CP或者AP吗？

上面说了，P是必须保证的。有理论证明，CAP是不能够同时保证的，故剩下的就是只能选择CP系统或AP系统了。
但是，实际情况是绝大部分时间是不存在节点间通信问题的，在不存在分区问题时，CA时可以共存的。
到这里，问题就转化为了，在你设计/分析分布式系统时，应该分以下两步：

  1. 若分区通信问题存在（P不能满足），你是要你的系统保证C（线性一致性）还是保证A（可用性）
  2. 若分区通信问题不存在（P满足），如何衡量CA的问题（见下面的PACELC理论）

PACELC

PACELC理论是CAP理论的扩展

定义

如果有分区partition（P），系统就必须在 可用性-availiability（A）和 线性一致性-consistency(C) 之间取得平衡；
否则（E）当系统运行在无分区情况下，系统需要在 延迟-Latency（L）和 一致性-consistency（C）之间取得平衡。

总结

到目前为止，我们知道了设计/分析分布式理论的第一步就是依据PACELC理论指导，分别考虑在P存在时候的可用性与线性一致性之间的取舍以及P不存在时候的延迟和一致性之间的取舍。
下面就会分别来介绍可用性与一致性及其取舍、延迟和一致性及其取舍

2.1: A - 可用性

设计一个可用性高的系统的指导理论是BASE理论。BASE 理论是 CAP 理论中的 AP 的延伸，是对互联网大规模分布式系统的实践总结，强调可用性。

BASE理论定义

核心就是基本可用（Basically Available）和最终一致性（Eventually consistent）。

基本可用

当分布式系统在出现不可预知的故障时，允许损失部分功能的可用性，保障核心功能的可用性。这里面自然也包含了不是查到最新数据的情况。
常见的一些实现招式：

  1. 流量错峰（不同地区售票时间错峰出售）
  2. 异步处理（买票排队，基于队列先收到用户买票请求，排队异步处理，延迟响应）
  3. 服务降级（看到非实时数据，采用缓存数据提供服务）
  4. 过载保护（熔断/限流，直接拒绝掉一部分请求，或者当请求队列满了，移除一部分请求，保证整体系统可用）
  5. 故障隔离（出现故障，做到故障隔离，避免影响其他服务）
  6. 弹性扩容（基于Metric和Monitor实现系统态势感知，做到弹性伸缩）
最终一致性

系统中所有的数据副本在经过一段时间的同步后，最终能够达到一个一致的状态。也就是说，在数据一致性上，存在一个短暂的延迟。
常见的一些实现招式：

  1. 读时修复：在读取数据时，检测数据的不一致，进行修复。比如 Cassandra 的 Read Repair 实现，具体来说，在向 Cassandra 系统查询数据的时候，如果检测到不同节点的副本数据不一致，系统就自动修复数据。
  2. 定时异步修复：这个是最常用的方式，通过定时对账检测副本数据的一致性，并修复

2.2：C - 线性一致性

线性一致性与分布式事务的关系

线性一致性需要分布式事务来支撑

分布式事务与ACID的关系

分布式事务的实现由ACID四个属性来支撑，即若实现了操作的ACID也就实现了事务。

ACID的定义

  • A - atomicity 原子性：一个事务中的多个操作、要么都完成，要么都不完成
  • C - consistency 一致性：首先说明，这里的C绝不是CAP中的C！这里的一致性表述有很多模凌两可的地方。甚至可以认为是非必要强存在于ACID中的属性（《Designing Data-Intensive Applications》一书的作者在书中写道：“The letter C doesn’t really belong in ACID”）。常见来说，这个一致性表述的是将此次操作面对的系统作为一个状态机，每次操作就是一次状态的变化，只要此次状态变化是符合预期的，就是保证一致性的。这里的预期又可以分为两种：一种是业务预期、一种是底层依赖预期，这里假设底层依赖是mysql数据库来看一个转账例子：从A向B转账100、且A账户只有90元。若数据库设置了此字段要求大于0，那么此操作不能完成，即没有完成数据库的有效状态转移，如果此字段没有设置要求大于0，那么数据库层面的状态转移一致性是成功的，但是业务层面的状态一致性转移是失败的（因为不应出现存款小于0的情况）。故实现一致性是需要结合底层依赖提供的能力 + 业务层面的设计正确共同来保证。特别说明，实际上来说，C是需要AID来协助的，上面说的结合底层依赖提供的能力，其实就是利用其提供的原子性或隔离性等（e.g1：还是从账户A向账户B转账100元，事务本身的实现逻辑没有问题，它先执行了从账号A中减去了100元，但在执行往账户B中增加100元之前，却发生了意想不到的错误，比如进程突然crash了，或是磁盘满了，或是网络突然不通了，或是其它任何可能的硬件错误。这时候，事务只执行了前一半，势必会破坏数据库整体状态的一致性。那怎么办呢？这其实就需要A（原子性）来保障了；e.g2：假设有两个事务：事务1从账户A向账户B转账100元，事务2从账户A向账户C转账50元。如果两个事务先后顺序执行，自然没有问题。但如果两个事务同时执行了，那么可能会出现下面的执行序列（假设账号A的初始余额为x元）：
    ​ <事务1>：读取账户A的余额，读到了x元；
    ​ <事务2>：读取账户A的余额，也读到了x元；
    ​ <事务1>：向账户A中写入(x-100)元；
    ​ <事务2>：向账户A中写入(x-50)元；
    ​ ……
    ​ 上面的执行过程，账户A中最后被写入的值是(x-50)元，显然是不对的（事务的一致性会被破坏）。如果两个转账的事务能正确执行完，那么账户A的余额应该是(x-150)元才对。
    ​ 这个并发的问题怎么处理呢？这就需要I（隔离性）来保障了。它对于并发执行的多个事务进行合理的排序，保障了不同事务的执行互不干扰。换言之，隔离性这种特性，能够让并发执行的多个事务就好像是按照「先后顺序」执行的一样。备注：此两个例子之间来源于文章）
  • I - isolation 隔离性：在执行一个事务时，其他操作不能存取正在执行事务访问到的数据。能够让并发执行的多个事务就好像是按照「先后顺序」执行的一样
  • D - durability 持久性：事务提交后需要保证更新的数据不会丢失。这个虽然看起来很简单，但是实际分析还是很重要的，以Redis为例，就要结合具体日志的设置来看是否满足此点了。

分布式事务实现的协议/算法

2PC - 两阶段提交协议

实现：

  1. 加入一个协调节点
  2. 第一阶段 - 提交请求/投票阶段：需要预留资源，在资源预留期间，其他人不能操作（比如，XA 在第一阶段会将相关资源锁定）
  3. 第二阶段 - 提交执行阶段
TCC - try-commit-cancel

实现：
2. 可以将 TCC 理解为编程模型，TCC 的 3 个操作是需要在业务代码中编码实现的，为了实现一致性，确认操作和补偿操作必须是等幂的，因为这 2 个操作可能会失败重试。
3. 一般来说都需要引入TCC框架来推动感知各个阶段的执行情况以及推进执行下一个阶段等等事情
4. 缺点：性能较低（所有服务都commit后、对应数据的下一个up/write事务才能进行）；协调节点单点故障；数据不一致（若confirm阶段出现部分服务发生网络故障不能得到commit信息）
具体实现原理可参考

Percolator

google提出、TiDB的分布式事务是基于此实现的。
针对TCC的优化说明：

  1. 简化了协调节点和切片的通信流程，让协调节点只跟其中一个primary切片通信，一方面，减少了通信开销，另一方面，避免了因为故障，commit阶段部分节点通信失败导致的数据不一致问题（针对TCC的缺点3的情况、commit通知的时候没有通知到某些切片）。
  2. prepare阶段记录了日志，这样即使协调节点故障了，恢复后也可以根据日志来做事务恢复。（通过主切片发现已提交、可自己再提交）
  3. 使用异步线程来做资源的释放工作，这样即使协调节点故障了，也不用担心资源得不到释放。
  4. 支持了读取历史版本数据

具体实现原理可参考

2.3：延迟与一致性之间的取舍

前面已经说过了C - 线性一致性 和 A - 可用性实现的要点。但是忽略了一个非常重要的指标 - 延迟。然而延迟/性能是非常重要的指标，直接决定了用户的体验。这里就涉及到具体算法的选择了，这是指导用户在不存在分区时，需要根据自己系统对于一致性和性能的要求，选择正确的算法：
| 算法名称 | 一致性 | 延迟 |
| ———- | ———- | —- |
| 2PC | 强一致性 | 高 |
| TCC | 强一致性 | 高 |
| Paxos | 强一致性 | 中 |
| ZAB | 最终一致性 | 中 |
| Raft | 强一致性 | 中 |
| Gossip | 最终一致性 | 高 |
| Quorum NWR | 强一致性 | 中 |

关于共识算法

定义

解决的是如何在分布式系统中的多个节点之间就某个提议达成共识。

与分布式事务的关系

  1. 理解1: 共识算法可以应用于分布式事务的ACID中的A（原子提交）部分，解决的是参与分布式事务的所有“节点”该执行confirm还是cancel的共识问题。也就是说原子提交可以使用共识算法（即分布式事务的实现在A部分需要使用共识算法、但是不是使用了共识算法就完整支撑分布式事务了！）。
  2. 理解2: 分布式事务说的是跨了多个“服务”的多个操作同步成功/失败，而对于每个服务内部对应的那个操作达成一致后影响的认知问题是共识问题

具体协议/算法

Paxos算法

基本上是分布式共识的代名词，因为当前最常用的一批共识算法都是基于它改进的。比如，Fast Paxos 算法、Cheap Paxos 算法、Raft 算法等等。
兰伯特提出的 Paxos 算法包含 2 个部分：

  1. 一个是 Basic Paxos 算法，描述的是多节点之间如何就某个值（提案 Value）达成共识；
  2. 另一个是 Multi-Paxos 思想，描述的是执行多个 Basic Paxos 实例，就一系列值达成共识。（兰伯特并没有把 Multi-Paxos 讲清楚，只是介绍了大概的思想，缺少算法过程的细节和编程所必须的细节（比如缺少选举领导者的细节））
Raft算法
  • Raft 算法属于 Multi-Paxos 算法，它是在兰伯特 Multi-Paxos 思想的基础上，做了一些简化和限制，比如增加了日志必须是连续的，只支持领导者、跟随者和候选人三种状态，在理解和算法实现上都相对容易许多。
  • Raft 算法是现在分布式系统开发首选的共识算法。绝大多数选用 Paxos 算法的系统（比如 Cubby、Spanner）都是在 Raft 算法发布前开发的，当时没得选；而全新的系统大多选择了 基于Raft 算法（比如 Etcd、Consul、CockroachDB、TiDB）再做优化。
  • Raft 算法是强领导者模型，通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。
Gossip算法

当性能要求最高、一致性要求低的就使用此算法

Quorum NWR算法

非常实用的一个算法，能有效弥补 AP 型系统缺乏强一致性的痛点，给业务提供了按需选择一致性级别的灵活度。

总结

分布式存储系统，有太多的知识点，且有些概念/协议本身就存在模糊性，常常导致不知道各个概念之间的关系以及应该应用于分布式系统的什么位置。本文目的就是理清各个概念之间的关系及其应用点。
总结起来就是：

  1. 根据延迟与一致性之间的取舍选择合适的算法
  2. 根据系统特点选择在分区发生时是否需要实现线性一致性（若需要的话、还要选择合适的共识算法来实现分布式事务中的原子性）
  3. 根据系统特点选择在分区发生时是否需要实现可用性（若需要的话按照其包含的一些要点针对的进行设计）