Freeman's Blog

一个菜鸡心血来潮搭建的个人博客

0%

分布式理论

发表于 更新于 分类于
  • [] CAP理论彻底理清
  • [] BASE
  • [] 常见中间件在CAP理论中的定位:
    • [] MySQL Cluster
    • [] Redis Cluster
    • [] Redis Sentinel
    • [] Zookeeper
    • [] Eureka
    • [] Nacos
    • [] HDFS(?)
  • [] 常见算法（优缺点及其原因
    • 2PC协议/3PC协议
    • Paxos简单情况
    • ZAB
    • Raft

多机器的时钟同步

  • 分布式环境下多台机器的时间流动可能是不一样的，需要一种机制来进行时钟同步，在多个机器间确定事件的发生顺序
  • 全序：任意两个元素都有二元关系，可比较
  • 偏序：只有部分元素可以比较，无法确定所有元素的准确顺序
  • 在单节点系统上维持全序关系是容易的，但是在分布式系统上维持全序关系需要付出代价。通信的代价是昂贵的，时间的同步是非常困难并且脆弱的。

全局时间

  • 理想世界，每个节点使用同一个有完美准确度的时钟

本地时间

逻辑时间戳

  • “逻辑时间（logical time）”而非真实时间来记录因果关系：使用计数器和通信机制来判断事件发生的顺序
  • 无法得知有关时间间隔的信息，也无法使用超时机制

向量时间戳

Simple Lamport Clock

进程工作 -> 计数器自增
发送消息 -> 携带计数器值
接收消息 -> 合并计数器

  • 偏序关系：若timestamp(a) < timestamp(b)，则a可能在b之前发生，也可能无法比较。因为一个Lamport clock只能携带1条时间线的信息，因此可能发生“明明是同时发生的事件，却被排序”的情况。

Vector Clock

FLP impossiblity result

  • 假设
    • 节点只会fail by crashing，不存在拜占庭式错误
    • 网络是可靠的
    • 其它异步系统模型所需的关于时间的假设
      • 各个进程行进的速率是独立的
      • 没有上界
      • 没有可用的时钟
  • 结论
    • 即使在消息不会丢失，最多一个进程fail且只会fail by crashing的条件下，异步系统模型中也不存在能够解决共识问题(consensus problem)的确定性算法。
    • 假设这样的算法存在，则总能设计出一种执行这种算法的方式，通过delaying message来让系统remain undecided(“bivalent”)
    • 这个结论的重要意义是它强调了在异步系统模型的假设下（no uppder bound），设计解决共识问题的算法必须考虑一种折衷：要么放弃safety，要么放弃liveness。

CAP theorem

三类属性

  • 一致性Consistency：所有节点在同一时间都可以访问到同样的数据（see the same data）
  • 可用性Availability：节点的failure不影响没有fail的节点继续工作
  • 分区容错性Partition tolerance：即使出现了因为网络问题（Partition - communication break）导致的消息丢失，系统还是能继续工作
  • 最多只有两种属性能够同时满足。（事实上，这并不是严格的“3选2”问题，某些时候属性之间存在tradeoff）

    三系统类型

  • CA：保证一致性可用性， full strict quorum protocols，例如two-phace commit（2PC）
    • 一种强一致性模型，无法区分节点不可用和网络问题，只能通过停止接收写操作来避免数据分歧
    • quorum protocol：基于鸽巢原理的算法，保证数据冗余和最终一致性
      • 分布式系统中的每一份数据拷贝对象都被赋予一票。每一个读操作获得的票数必须大于最小读票数（read quorum）（Vr），每个写操作获得的票数必须大于最小写票数（write quorum）(Vw）才能读或者写。如果系统有V票（意味着一个数据对象有V份冗余拷贝），那么最小读写票数(quorum)应满足如下限制：
        • Vr + Vw > V
        • Vw > V/2
      • 第一条规则保证了一个数据不会被同时读写。当一个写操作请求过来的时候，它必须要获得Vw个冗余拷贝的许可。而剩下的数量是V-Vw 不够Vr，因此不能再有读请求过来了。同理，当读请求已经获得了Vr个冗余拷贝的许可时，写请求就无法获得许可了。
      • 第二条规则保证了数据的串行化修改。一份数据的冗余拷贝不可能同时被两个写请求修改。
  • CP：保证一致性和分区容错性，majority quorum protocols，例如Paxos，Raft
    • 也是一种强一致性模型，通过对网络中断的两段实行不对称的行为来避免数据分歧。节点多的一侧可用，节点少的一侧不可用（属于哪种情况需要使用算法进行区分）。
  • AP：使用冲突化解(conflit resolution)的协议

导出结论

  • 应该积极考虑Partition Tolerance：“分布式系统必须保证分区容错性，基本上只能选择AP原则和CP原则”，“You can’t sacrifice partition tolerance”
  • 因此分布式系统中并不存在”CA”类别，当network partition发生时，分布式系统要么保证一致性，要么保证可用性。（单机系统可以存在CA类别，比如RDBMS）
  • 存在network partitions时，强一致性和高可用性存在冲突
  • 在一般情况下，强一致性和性能存在冲突。要保证强一致性，各个节点要在每个操作上进行通信和协商，这会导致很高的latency

强一致性与弱一致性模型

强一致性模型

  • 可线性化一致性：在可线性一致性的情况下，所有的操作似乎都按照与全局实时操作顺序一致的顺序原子地执行
  • 顺序一致性：在顺序一致性的情况下，所有操作似乎都是按照某种顺序原子地执行的，这种顺序与在单个节点上看到的顺序一致，并且在所有节点上都是相等的。

弱一致性模型

  • client-centric一致性模型：入了客户端或会话机制的一致性模型，保证客户不会访问到一个数据项的旧版本，通常可以在客户端增加额外的cache来实现
  • 最终一致性模型：如果停止对数据的值进行修改，经过”一段待定义的时间”后所有数据的副本都会达成一致得到某个相同的值。在此之前，多个数据的副本可能在”某些为定义的行为中”存在不一致的现象。
    • 因果一致性：如果A更新完数据通知了B，则B之后对数据的访问和修改必须基于A更新后的值。对于C则没有这样的限制。
    • Read your writes：节点A更新后总是能访问到自己更新过的最新值。

BASE理论

  • Basically Available: 基本可用。出现故障时，可能出现响应时间变慢或者部分功能降级，但是仍能提供服务。
  • Soft State: 软状态，允许系统中的数据存在中间状态，而不是要求多个节点的数据副本总是一致的。
  • Eventually Consistent: 最终一致性，软状态存在时间期限。时间期限过后应该保证所有的副本保持数据一致性。

分布式事务

  • 一种分布式共识的特殊情况
  • DBMS相较于文件系统的意义在于
    • 基于关系代数，实现对数据的一种结构化存储和结构化查询
    • 事务的支持 -> ACID

      2PC：尽量保证强(?)一致性

      流程：

  • 一阶段：
  1. 客户端向协调者发起事务。事务的协调者节点首先向所有的参与者节点发送Prepare请求。
  2. 接收到Prepare请求后，每一个参与者节点都会写入日志并各自执行与事务有关的数据更新（此时会对数据上锁），但是暂时不提交事务，而是想协调者节点返回“完成”消息。
  3. 协调者接收到所有参与者返回的消息后，分布式事务进入第二阶段。
  • 二阶段正常流程：
    • 成功流程：
      1. 如果协调者节点接收到的都是“可以准备提交事务”的消息，那么协调者节点会向所有参与者发送事务提交命令。
      2. 参与者接收到事务提交命令，进行事务的提交并释放锁资源。本地事务完成提交后，会向当前协调者返回“完成”消息。
      3. 协调者接收到所有事务参与者的反馈，分布式事务完成。
    • 失败流程：
      1. 在第一阶段协调者接收到某个参与者反馈的失败消息，说明该节点的事务执行不成功，必须回滚。
      2. 协调者节点向所有的参与者发送abort请求。接收到abort请求的参与者需要在本地进行事务的回滚操作。
    • 无论是成功还是失败，此时才会告知客户端事务执行的结果。

存在的问题

  • 一阶段中如果协调者发出Prepare请求，有可能收不到所有参与者的响应。此时可以引入重试-超时机制。如果超时，则直接回滚。
  • 二阶段第一步如果协调者发出提交请求或回滚请求，但是没有收到所有参与者的响应。则需要不断重发提交请求，直到收到全部协调者的响应。否则可能导致参与者节点的数据不一致。
  • 各个节点在事务执行过程中会持续占用数据库资源（在事务相关的数据上加锁），性能较差。
  • 协调者的单点故障问题
    • 发送Prepare请求之后协调者单点故障、发送提交事务/回滚事务之前单点故障、发送…之后单点故障…

3PC

流程

  • 一阶段同样发出Prepare请求，但是不让参与者立即执行事务，而是只需要返回是否能够准备。
  • 二阶段进行预提交，多出这一状态可以让参与者确认其它参与者都回应了协调者，表示可以进行后续事务。该阶段参与者会进行写日志和修改数据，不提交事务。
  • 三阶段进行事务提交，协调者发出提交事务请求，参与者响应。
  • 同样，不管哪一个阶段有参与者返回失败都会宣布事务失败。
  • 参与者超时：等待提交事务请求超时，参与者会直接提交事务（？）。而等待与提交命令超时的情况，则没有任何影响。

复制（Replication）

复制的时机来分类

同步复制

  • 请求 -> 阻塞，将操作复制到所有节点 -> 所有节点返回 -> 向客户端返回
  • 返回客户端之前状态变化会被系统中所有节点所知。
  • 性能差，耐用性保证强。

    异步复制

  • 请求 -> 立即响应，将更新数据保存在本机 -> 发送异步复制消息，联系其他节点 其他节点更新它们的副本
  • 性能高，对网络延迟的容忍度高，耐用性保证差，如果某个修改在给客户端发送响应后，在成功复制到从节点之前丢失了，那这个修改就永远丢失了。
  • 高可用性，但是单纯的lazy approach无法保证错误发生时能够读出之前写入的内容

按照副本一致性的强弱分类

维护单一副本（prevent divergence，single copy）

  • 尽可能地表现得像单一系统
  • 保证只有一个活动副本
  • 保证所有副本的一致性
  • 例子：异步主从复制、同步主从复制、2PC、Multi-Paxos，3PC，Paxos with leader election

    multi-master systems（risk divergence）

常见的复制算法：主从复制

  • 所有操作都在一个master server上进行，master server将所有操作序列化并形成local log，local log将被发送到所有backup server上形成replica
  • 丢失修改的两种情况
    • 异步复制导致：没来得及同步完成时master宕机，新slave成为master，旧master即使恢复了也会变成slave，无法将修改复制到其他节点
    • 脑裂：master和slave无法互相联系，联系不上master的slave选出了backup master，新旧master同时接收修改，导致丢失修改
      • 怎么解决？要求master必须与一定量的slave保持联系才可以接受写，否则拒绝写

主从复制下的一致性协议：2PC(2 Phase Commit)

  • 中心化的协议，需要单一的master/leader/coordinator角色
  • 过程 vote -> decision -> commit
  • 是一个CA算法，不保证Partition Tolerance

共识算法

Quorum机制

最极端的情况：Write All Read One

  • 当Client请求向某副本写数据时(更新数据)，只有当所有的副本都更新成功之后，这次写操作才算成功，否则视为失败。
  • 写操作很脆弱，因为只要有一个副本更新失败，此次写操作就视为失败了。
  • 读操作很简单，因为，所有的副本更新成功，才视为更新成功，从而保证所有的副本一致。这样，只需要读任何一个副本上的数据即可。假设有N个副本，N-1个都宕机了，剩下的那个副本仍能提供读服务；但是只要有一个副本宕机了，写服务就不会成功。

W R N

  • 更新操作在W个副本中更新成功后才认为此次更新操作成功。更新后的数据为“成功提交”。
  • 对于读操作，至少要读R个副本才能读到此次更新的数据
  • W + R > N
  • 在保证强一致性的情况下，W越大，写操作的可用性越差，读操作的可用性越好，反之亦然。

如何判断是否是最新的？

一致性哈希

传统哈希方法的局限性

  • 通过哈希的方式确定某个数据或某个请求应该落到哪个节点。
  • 传统哈希方法在节点增加或减少的时候需要进行重哈希，这会导致大量key和节点的映射关系发生变化。 -> 如果是缓存的情况，此时会发生大量的缓存失效，造成缓存雪崩。

一致性哈希算法

特点

  • 保证了增加或减少服务器时让尽可能少的映射发生改变

    原理

  • 一致性哈希环：分布范围是[0, 2^32 - 1]
  • 对象和服务器放置在同一个哈希环上。
  • 对于每个对象，在哈希环上顺时针查找举例这个对象的哈希值最近的服务器。将这一服务器确定为该对象所属的服务器。
  • 对于服务器增加的情况，只有在哈希环上位于新增的服务器和该服务器的上一台服务器之间的对象需要进行重新分配。
  • 对于服务器减少的情况，只有原本分配到该台服务器上的对象需要进行重新分配，其它节点不会受影响。
  • 虚拟节点：将每台物理服务器虚拟为一组虚拟服务器，将虚拟服务器配置到哈希环上，然后维护虚拟服务器到物理服务器的映射。

雪崩问题

  • 如果哈希环上的一个服务器故障，原本属于该服务器的请求或数据访问就会全部转移到哈希环上的下一个服务器，这会造成下一个服务器的负载瞬间上升，有可能导致下一个服务器故障。
  • 解决：在下一个服务器之前增加虚拟节点，分担下一个服务器的压力。