参考文献

分布式概览

img

分布式起源

单兵模式: 单机模式

  • 单机模式是指,所有应用程序和数据均部署在一台电脑或服务器上,由一台计算机完成所有的处理.
  • 主要问题: 性能受限,存在单点失效问题.

游击队模式: 数据并行或数据分布式

  • 为了解决单机模式的问题,并行计算得到了发展,进而出现了数据并行(也叫做数据分布式)模式.
  • 并行计算采用消息共享模式使用多台计算机并行运行或执行多项任务,核心原理是每台计算机上执行相同的程序,将数据进行拆分放到不同的计算机上进行计算.
  • 好处: 可以利用多台计算机并行处理多个请求,使得我们可以在相同的时间内完成更多的请求处理,解决了单机模式的计算效率瓶颈问题.
  • 主要的问题: 对提升单个任务的执行性能及降低时延无效.
    • 相同的应用部署到不同的服务器上,当大量用户请求过来,如何能比较均衡地转发到不同的应用服务器上(负载均衡)?
    • 当请求量较大时,对数据库的频繁读写操作,使得数据库IO访问成为瓶颈.解决这个问题的方式是读写分离,读数据库只接收读请求,写数据库只接收写请求,读写数据库之间要进行数据同步,以保证数据一致性.
    • 当有些数据成为热点数据时,会导致数据库访问频繁,压力增大.解决这个问题的方法是引入缓存机制,将热点数据加载到缓存中.

集团军模式: 任务并行或任务分布式

  • 任务并行指的是,将单个复杂的任务拆分为多个子任务,从而使得多个子任务可以在不同的计算机上并行执行.
  • 主要问题: 集团军模式在提供更好的性能,扩展性,可维护性的同时,也带来了设计上的复杂性问题.

分布式是什么

  • 分布式就是将相同或相关的程序运行在多台计算机上,从而实现特定目标的一种计算方式.

分布式系统的指标

性能(Performance)

  • 吞吐量(Throughput)
    • 吞吐量指的是,系统在一定时间内可以处理的任务数.
    • 常见的吞吐量指标有QPS(Queries Per Second),TPS(Transaction Per Second),BPS(Bits Per Second)
      • QPS,即查询数每秒,用于衡量一个系统每秒处理的查询数.这个指标通常用于读操作,越高说明对读操作的支持越好.如果应用主要是读操作,那么需要重点考虑如何提高QPS,来支持高频的读操作.
      • TPS,即事务数每秒,用于衡量一个系统每秒处理的事务数.这个指标通常对应于写操作,越高说明对写操作的支持越好.如果应用主要是写操作,那么需要重点考虑如何提高TPS,来支持高频写操作.
      • BPS,即比特数每秒,用于衡量一个系统每秒处理的数据量.对于一些网络系统、数据管理系统,我们不能简单地按照请求数或事务数来衡量其性能.因为请求与请求、事务与事务之间也存在着很大的差异,比方说,有的事务大需要写入更多的数据.那么在这种情况下,BPS更能客观地反应系统的吞吐量
  • 响应时间(Response Time)
    • 系统响应一个请求或输入需要花费的时间.响应时间直接影响到用户体验,对于时延敏感的业务非常重要.
  • 完成时间(Turnaround Time)
    • 系统真正完成一个请求或处理需要花费的时间.任务并行(也叫作任务分布式)模式出现的其中一个目的,就是缩短整个任务的完成时间.特别是需要计算海量数据或处理大规模任务时,用户对完成时间的感受非常明显

资源(Resouce Usage)

  • 资源占用指的是,一个系统提供正常能力需要占用的硬件资源,比如 CPU、内存、硬盘等.
  • 一个系统在没有任何负载时的资源占用,叫做空载资源占用,体现了这个系统自身的资源占用情况.比如,你在手机上安装一个 App,安装的时候通常会提示你有多少 KB,这就是该App 的空载硬盘资源占用.对于同样的功能,空载资源占用越少,说明系统设计越优秀,越容易被用户接受.
  • 一个系统满额负载时的资源占用,叫做满载资源占用,体现了这个系统全力运行时占用资源的情况,也体现了系统的处理能力.同样的硬件配置上,运行的业务越多,资源占用越少,说明这个系统设计得越好.

可用性(Availability)

  • 系统的可用性可以用系统停止服务的时间与总的时间之比衡量
  • 系统的可用性还可以用某功能的失败次数与总的请求次数之比来衡量
  • 可靠性通常用来表示一个系统完全不出故障的概率,更多地用在硬件领域.而可用性则更多的是指在允许部分组件失效的情况下,一个系统对外仍能正常提供服务的概率.

可扩展性(Scalability)

  • 可扩展性,指的是分布式系统通过扩展集群机器规模提高系统性能 (吞吐、响应时间、 完成时间)、存储容量、计算能力的特性,是分布式系统的特有性质.

分布式互斥

霸道总裁: 集中式方法

  • 引入一个协调者,将所有的请求者进行排序,最早请求的参与者可以使用临界资源.
  • 优点:
    • 简单,易于实现
    • 通信高效
  • 缺点:
    • 可用性低
    • 性能易受协调者影响
  • 应用场景: 在协调者可靠性和性能有一定保障的情况下,可以适用于比较广泛的场景.

民主协商: 分布式方法

  • 征求其他参与者同意后,使用临界资源
  • 优点: 可用性高
  • 缺点:
    • 通信成本比较高
    • 复杂度比较高
  • 应用场景: 临界资源使用频度较低且系统规模较小的场景

轮值CEO: 令牌环方法

  • 所有参与者组成一个环,轮流使用资源
  • 优点:
    • 单个参与者通信效率较高
    • 可用性较高
  • 缺点: 当参与者对临界资源使用频率较低时,会带来较多无用通信
  • 应用场景: 系统规模较小,并且系统中每个程序使用共享资源频度较高且使用时间较短的场景

分布式选举

为什么需要分布式选举

  • 主节点在一个分布式集群中负责对其他节点的协调和管理.
  • 主节点的存在,就可以保证其他节点的有序运行,以及数据库集群中的写入数据在每个节点上的一致性.这里的一致性是指,数据在每个集群节点中都是一样的,不存在不同的情况.
  • 选举的作用就是选出一个主节点,由它来协调和管理其他节点,以保证集群有序运行和节点间数据的一致性.

分布式选举算法

长者为大: Bully算法

  • Bully算法的选举原则是"长者"为大,即在所有存活的节点中,选取ID最大的节点作为主节点.

  • 在Bully算法中,节点的角色有两种: 普通节点和主节点.初始化时,所有节点都是平等的,都是普通节点,并且都有成为主节点的权利.但是,当选主成功后,有且仅有一个节点成为主节点,其他所有节点都是普通节点.当且仅当主节点故障或与其他节点失去联系后,才会重新选主.

  • Bully算法在选举过程中,需要用到以下三种消息:

    • Election消息,用于发起选举
    • Alive消息,用于对Election消息的应答
    • Victory消息,竞选成功的主节点向其他节点发送的宣誓主权的消息

  • Bully算法选举的原则是"长者为大",意味着它的假设条件是,集群中每个节点均知道其他节点的ID.在此前提下,其具体的选举过程是:

    1. 集群中每个节点判断自己的ID是否为当前活着的节点中ID最大的,如果是,则直接向其他节点发送Victory消息,宣誓自己的主权;

    2. 如果自己不是当前活着的节点中ID最大的,则向比自己ID大的所有节点发送Election消息,并等待其他节点的回复;

    3. 若在给定的时间范围内,本节点没有收到其他节点回复的Alive消息,则认为自己成为主节点,并向其他节点发送Victory消息,宣誓自己成为主节点;若接收到来自比自己ID大的节点的Alive消息,则等待其他节点发送Victory消息;

    4. 若本节点收到比自己ID小的节点发送的Election消息,则回复一个Alive消息,告知其他节点,我比你大,重新选举.

  • 优点: 选举速度快,算法复杂度低,简单易实现

  • 缺点:

    • 需要每个节点有全局的节点信息,因此额外信息存储较多;
    • 其次任意一个比当前主节点大的新节点或节点故障后恢复集群的时候,都可以会触发重新选举,成为新的主节点,如果该节点频繁退出或加入集群,就会导致频繁切主.

民主投票: Raft算法

  • Raft算法是典型的多数派投票选举算法,其核心思想是"少数服从多数".即在Raft算法中获得投票最多的节点成为主节点.
  • 采用Raft算法选举,集群节点的角色有3种:
    • Leader,即主节点,同一时刻只有一个Leader,负责协调和管理其他节点;
    • Candidate,即候选者,每个节点都可以成为Candidate,节点在该角色下才可以被选为新的Leader;
    • Follower,Leader的跟随者,不可以发起选举.
  • Raft 选举的流程,可以分为以下几步:
    1. 初始化时,所有节点均为Follower状态.
    2. 开始选主时,所有节点的状态由Follower转化为Candidate,并向其他节点发送选举请求.
    3. 其他节点根据接收到的选举请求的先后顺序,回复是否同意成为主.这里需要注意的是,在每一轮选举中,一个节点只能投出一张票.
    4. 若发起选举请求的节点获得超过一半的投票,则成为主节点,其状态转化为Leader,其他节点的状态则由Candidate降为Follower.Leader节点与Follower节点之间会定期发送心跳包,以检测主节点是否活着.
    5. 当Leader节点的任期到了,即发现其他服务器开始下一轮选主周期时,Leader节点的状态由Leader降级为Follower,进入新一轮选主.
  • 优点: 选举速度快,算法复杂度低,易于实现
  • 缺点:
    • 它要求系统内每个节点都可以相互通信,且需要获得过半的投票数才能选主成功,因此通信量大.
  • 该算法选举稳定性比Bully算法好,这是因为当有新节点加入或节点故障恢复后,会触发选主,但不一定会真正切主,除非新节点或故障恢复后的节点获得投票数过半,才会导致切主.

具有优先级的民主投票: ZAB算法

  • ZAB(ZooKeeper Atomic Broadcase)选举算法是为ZooKeeper实现分布式协调功能而设计的.相较于Raft算法的投票机制,ZAB算法增加了通过节点ID和数据ID作为参考进行选主,节点ID和数据ID越大,表示数据越新,优先成为主.
  • 相较于Raft算法,ZAB算法尽可能保证数据的最新性.所以ZAB算法可以说是对Raft算法的改进.
  • 使用ZAB算法选举时,集群中每个节点拥有3种角色:
    • Leader,主节点;
    • Follower,跟随者节点;
    • Observer,观察者,无投票权
  • 选举过程中,集群中的节点拥有4个状态:
    • Looking状态,即选举状态.当节点处于该状态时,它会认为当前集群中没有Leader,因此自己进入选举状态.
    • Leading状态,即领导者状态,表示已经选出主,且当前节点为Leader.
    • Following状态,即跟随者状态,集群中已经选出主后,其他非主节点状态更新为Following,表示对Leader的追随.
    • Observing状态,即观察者状态,表示当前节点为Observer,持观望态度,没有投票
      权和选举权.
  • 投票过程中,每个节点都有一个唯一的三元组(server_id,server_zxID,epoch),其中server_id表示本节点的唯一ID;server_zxID表示本节点存放的数据ID,数据ID越大表示数据越新,选举权重越大;epoch表示当前选取轮数,一般用逻辑时钟表示.
  • ZAB选举算法的核心是"少数服从多数,ID大的节点优先成为主",因此选举过程中通过(vote_id,vote_zxID)来表明投票给哪个节点,其中vote_id表示被投票节点的ID,vote_zxID表示被投票节点的服务器zxID.ZAB算法选主的原则是:server_zxID最大者成为Leader;若server_zxID相同,则server_id最大者成为Leader.
  • ZAB算法性能高,对系统无特殊要求,采用广播方式发送消息,若节点中有n个节点,每个节点同时广播,则集群中信息量为n*(n-1)个消息,容易出现广播风暴;且出了投票,还增加了对比节点ID和数据ID,这就意味着还需要所有节点的ID和数据ID,所以选举时间相对较长.但该算法选举稳定性比较好,当有新节点加入或节点故障恢复后,会触发选主,但不一定会真正切主,除非新节点或故障后恢复的节点数据ID和节点ID最大,且获得投票数过半,才会导致切主.

三种算法对比

Bully算法 Raft算法 ZAB算法
选举消息回复类型 alive消息 同意或不同意选举的消息 投票信息<epoch,vote_id,vote_zxID>
Leader选举机制 偏向于让ID更大的节点作为Leader 收到过半数的投票,则当选为Leader 倾向于让数据最新或者ID值最大的节点作为Leader
选举过程 只要节点发现Leader无响应是,或ID较大的节点恢复故障是,就会发起选举 每个角色为Candidate的节点可参于竞选Leader,且每一个Follower只有一次投票权即同意或不同意Candidate的选举 每个节点都可以处于Looking状态参与竞选,都可以多次重新投票,根据epoch,zxID,server_id来选择最佳的节点作为Leader
选举所需时间 短 较短 较长
性能 Bully < Raft < ZAB

分布式共识

  • 分布式选举的过程就是一个分布式共识的问题,因为每个节点在选出主节点之前都可以认为自己会成为主节点,就是说集群节点"存异",而通过选举的过程选出主节点,让所有的节点都认可该节点,这叫做"求同".由此可见,分布式共识的本质就是"存异求同"

  • 从本质上看,分布式选举的问题,其实就是传统的分布式共识方法,主要是基于多数投票策略实现的.

  • 基于多数投票策略的分布式选举方法,如果用于分布式在线记账一致性问题中,那么记账权通常会掌握到主节点中,这使得主节点非常容易造假,且存在性能瓶颈.因此,分布式选举不适用于分布式在线记账的一致性问题.

  • 这里所说的分布式在线记账,是指在没有集中的发行方,也就是没有银行参与的情况下,任意一台接入互联网的电脑都能参与买卖,所有看到该交易的服务器都可以记录这笔交易,并且记录信息最终都是一致的,以保证交易的准确性.而如何保证交易的一致性,就是该场景下的分布式共识问题.

什么是分布式共识

  • 分布式共识就是在多个节点均可独自操作或记录的情况下,使得所有节点针对某个状态达成一致的过程.

分布式共识方法

  • PoW(Proof-of-Work)工作量证明
  • PoS(Proof-of-Stake)权益证明
  • DPoS(Delegated Proof of Stake)委托权益证明

PoW

  • 从分布式选举问题可以看出,同一轮选举中有且仅有一个节点成为主节点.同理,在分布式在线记账问题中,针对同一笔交易,有且仅有一个节点或服务器可以获得记账权,然后其他节点或服务器同意该节点或服务器的记账结果,达成一致.
  • 也就是说,分布式共识包括两个关键点,获得记账权和所有节点或服务器达成一致.
  • PoW 算法,是以每个节点或服务器的计算能力(即“算力”)来竞争记账权的机制,因此是一种使用工作量证明机制的共识算法.也就是说,谁的计算力强、工作能力强,谁获得记账权的可能性就越大.
  • 那么,如何体现节点的“算力”呢？答案就是,每个节点都去解一道题,谁能先解决谁的能力就强.
  • 假设每个节点会划分多个区块用于记录用户交易,PoW 算法获取记账权的原理是：利用区块的 index、前一个区块的哈希值、交易的时间戳、区块数据和 nonce 值,通过 SHA256哈希算法计算出一个哈希值,并判断前 k 个值是否都为 0.如果不是,则递增 nonce 值,重新按照上述方法计算;如果是,则本次计算的哈希值为要解决的题目的正确答案.谁最先计算出正确答案,谁就获得这个区块的记账权.
  • 请注意：nonce 值是用来找到一个满足哈希值的数字;k 为哈希值前导零的个数,标记了计算的难度,0 越多计算难度越大.
  • 达成共识的过程,就是获得记账权的节点将该区块信息广播给其他节点,其他节点判断该节点找到的区块中的所有交易都是有效且之前未存在过的,则认为该区块有效,并接受该区块,达成一致.
  • PoW 机制每次达成共识需要全网共同参与运算,增加了每个节点的计算量,并且如果题目过难,会导致计算时间长、资源消耗多;而如果题目过于简单,会导致大量节点同时获得记账权,冲突多.这些问题,都会增加达成共识的时间.
  • 所以,PoW 机制的缺点也很明显,共识达成的周期长、效率低,资源消耗大.

PoS

  • 为了解决 PoW 算法的问题,引入了 PoS 算法.它的核心原理是,由系统权益代替算力来决定区块记账权,拥有的权益越大获得记账权的概率就越大.
  • 这里所谓的权益,就是每个节点占有货币的数量和时间,而货币就是节点所获得的奖励.PoW 算法充分利用了分布式在线记账中的奖励,鼓励“利滚利”.
  • 基于 PoS 算法获得区块记账权的方法与基于 PoW 的方法类似,不同之处在于：节点计算获取记账权的方法不一样,PoW 是利用区块的 index、前一个区块的哈希值、交易的时间戳、区块数据和 nonce 值,通过 SHA256 哈希算法计算出一个哈希值,并判断前 k 个值是否都为 0,而 PoS 是根据节点拥有的股权或权益进行计算的.

DPoS

  • 为了解决 PoS 算法的垄断问题,2014 年比特股(BitShares)的首席开发者丹尼尔 · 拉里默(Dan Larimer)提出了委托权益证明法,也就是 DPoS 算法.
  • DPoS 算法的原理,类似股份制公司的董事会制度,普通股民虽然拥有股权,但进不了董事会,他们可以投票选举代表(受托人)代他们做决策.DPoS 是由被社区选举的可信帐户(受托人,比如得票数排行前 101 位)来拥有记账权.
  • DPoS 是在 PoW 和 PoS 的基础上进行改进的,相比于 PoS 算法,DPoS 引入了受托人, 优点主要表现在：
    • 由投票选举出的若干信誉度更高的受托人记账,解决了所有节点均参与竞争导致消息量大、达成一致的周期长的问题.也就是说,DPoS 能耗更低,具有更快的交易速度.
    • 每隔一定周期会调整受托人,避免受托人造假和独权.
  • 但是,在 DPoS 中,由于大多数持币人通过受托人参与投票,投票的积极性并不高;且一旦出现故障节点,DPoS 无法及时做出应对,导致安全隐患.

三种分布式共识算法对比分析

PoW PoS DPoS
计算消耗 高 中 低
结构类型 去中心化 去中心化 去中心化(多中心)
交易量/秒 PoW < PoS < DPos
交易服务费 高 低 低
应用区块链平台 比特币 以太坊 比特股

一致性和共识的区别

  • 一致性是指,分布式系统中的多个节点之间,给定一系列的操作,在约定协议的保障下,对外界呈现的数据或状态是一致的.
  • 共识是指,分布式系统中多个节点之间,彼此对某个状态达成一致结果的过程.
  • 也就是说,一致性强调的是结果,共识强调的是达成一致的过程,共识算法是保障系统满足不同程度一致性的核心技术.

分布式事务

  • 分布式事务,就是在分布式系统中运行的事务,由多个本地事务组合而成

如何实现分布式事务

  • 基于 XA 协议的二阶段提交协议方法;
  • 三阶段提交协议方法;
  • 基于消息的最终一致性方法.
  • 其中,基于 XA 协议的二阶段提交协议方法和三阶段提交协议方法,采用了强一致性,遵从ACID,基于消息的最终一致性方法,采用了最终一致性,遵从 BASE 理论.

基于 XA 协议的二阶段提交方法(2PC Two-phase commit protocol)

  • XA 是一个分布式事务协议,规定了事务管理器和资源管理器接口.因此,XA 协议可以分为两部分,即事务管理器和本地资源管理器.
  • 事务管理器作为协调者,负责各个本地资源的提交和回滚;而资源管理器就是分布式事务的参与者,通常由数据库实现,比如 Oracle、DB2 等商业数据库都实现了 XA 接口.
  • 基于 XA 协议的二阶段提交方法中,二阶段提交协议(The two-phase commit protocol,2PC),用于保证分布式系统中事务提交时的数据一致性,是 XA 在全局事务中用于协调多个资源的机制.
  • 两阶段提交协议如何保证分布在不同节点上的分布式事务的一致性呢?
    • 为了保证它们的一致性,我们需要引入一个协调者来管理所有的节点,并确保这些节点正确提交操作结果,若提交失败则放弃事务.
  • 两阶段提交协议的执行过程,分为投票(voting)和提交(commit)两个阶段.
    • 投票为第一阶段,协调者(Coordinator,即事务管理器)会向事务的参与者(Cohort,即本地资源管理器)发起执行操作的 CanCommit 请求,并等待参与者的响应.参与者接收到请求后,会执行请求中的事务操作,记录日志信息但不提交,待参与者执行成功,则向协调者发送“Yes”消息,表示同意操作;若不成功,则发送“No”消息,表示终止操作.
    • 当所有的参与者都返回了操作结果(Yes 或 No 消息)后,系统进入了提交阶段.在提交阶段,协调者会根据所有参与者返回的信息向参与者发送 DoCommit 或 DoAbort 指令：
      • 若协调者收到的都是“Yes”消息,则向参与者发送“DoCommit”消息,参与者会完成剩余的操作并释放资源,然后向协调者返回“HaveCommitted”消息;
      • 如果协调者收到的消息中包含“No”消息,则向所有参与者发送“DoAbort”消息,此时发送“Yes”的参与者则会根据之前执行操作时的回滚日志对操作进行回滚,然后所有参与者会向协调者发送“HaveCommitted”消息;
      • 协调者接收到“HaveCommitted”消息,就意味着整个事务结束了.
  • 基于 XA 的二阶段提交算法的不足
    • 同步阻塞问题：二阶段提交算法在执行过程中,所有参与节点都是事务阻塞型的.也就是说,当本地资源管理器占有临界资源时,其他资源管理器如果要访问同一临界资源,会处于阻塞状态.
    • 单点故障问题：基于 XA 的二阶段提交算法类似于集中式算法,一旦事务管理器发生故障,整个系统都处于停滞状态.尤其是在提交阶段,一旦事务管理器发生故障,资源管理器会由于等待管理器的消息,而一直锁定事务资源,导致整个系统被阻塞.
    • 数据不一致问题：在提交阶段,当协调者向参与者发送 DoCommit 请求之后,如果发生了局部网络异常,或者在发送提交请求的过程中协调者发生了故障,就会导致只有一部分参与者接收到了提交请求并执行提交操作,但其他未接到提交请求的那部分参与者则无法执行事务提交.于是整个分布式系统便出现了数据不一致的问题.

基于 XA 协议的三阶段提交方法(3PC Three-phase commit protocol)

  • 三阶段提交协议(Three-phase commit protocol,3PC),是对二阶段提交(2PC)的改进.为了解决两阶段提交的同步阻塞和数据不一致问题,三阶段提交引入了超时机制和准备阶段.

    • 同时在协调者和参与者中引入超时机制.如果协调者或参与者在规定的时间内没有接收到来自其他节点的响应,就会根据当前的状态选择提交或者终止整个事务.
    • 在第一阶段和第二阶段中间引入了一个准备阶段,也就是在提交阶段之前,加入了一个预提交阶段.在预提交阶段排除一些不一致的情况,保证在最后提交之前各参与节点的状态是一致的.

  • 也就是说,除了引入超时机制之外,3PC 把 2PC 的提交阶段一分为二,这样三阶段提交协议就有 CanCommit、PreCommit、DoCommit 三个阶段.

  • 第一,CanCommit 阶段.

    • CanCommit 阶段与 2PC 的投票阶段类似：协调者向参与者发送请求操作(CanCommit请求),询问参与者是否可以执行事务提交操作,然后等待参与者的响应;参与者收到CanCommit 请求之后,回复 Yes,表示可以顺利执行事务;否则回复 No.

  • 第二,PreCommit 阶段.

    • 协调者根据参与者的回复情况,来决定是否可以进行 PreCommit 操作.

    • 如果所有参与者回复的都是“Yes”,那么协调者就会执行事务的预执行：

      • 发送预提交请求.协调者向参与者发送 PreCommit 请求,进入预提交阶段.
      • 事务预提交.参与者接收到 PreCommit 请求后执行事务操作,并将 Undo 和 Redo信息记录到事务日志中.
      • 响应反馈.如果参与者成功执行了事务操作,则返回 ACK 响应,同时开始等待最终指令.

    • 假如任何一个参与者向协调者发送了“No”消息,或者等待超时之后,协调者都没有收到参与者的响应,就执行中断事务的操作：

      • 发送中断请求.协调者向所有参与者发送“Abort”消息.

      • 终断事务.参与者收到“Abort”消息之后,或超时后仍未收到协调者的消息,执行事务的终断操作

  • 第三,DoCommit 阶段

    • DoCmmit 阶段进行真正的事务提交,根据 PreCommit 阶段协调者发送的消息,进入执行提交阶段或事务中断阶段.
    • 执行提交阶段：
      • 发送提交请求.协调者接收到所有参与者发送的 Ack 响应,从预提交状态进入到提交状态,并向所有参与者发送 DoCommit 消息.
      • 事务提交.参与者接收到 DoCommit 消息之后,正式提交事务.完成事务提交之后,释放所有锁住的资源.
      • 响应反馈.参与者提交完事务之后,向协调者发送 Ack 响应. 完成事务.协调者接收到所有参与者的 Ack 响应之后,完成事务.
    • 事务中断阶段：
      • 发送中断请求.协调者向所有参与者发送 Abort 请求.
      • 事务回滚.参与者接收到 Abort 消息之后,利用其在 PreCommit 阶段记录的 Undo信息执行事务的回滚操作,并释放所有锁住的资源.
      • 反馈结果.参与者完成事务回滚之后,向协调者发送 Ack 消息.
      • 终断事务.协调者接收到参与者反馈的 Ack 消息之后,执行事务的终断,并结束事
        务.

补偿事务(TCC)

  • TCC（Try-Confirm-Cancel）又称补偿事务.其核心思想是：“针对每个操作都要注册一个与其对应的确认和补偿（撤销操作）”.它分为三个操作：

    • Try阶段：主要是对业务系统做检测及资源预留.
    • Confirm阶段：确认执行业务操作.
    • Cancel阶段：取消执行业务操作.

  • CC事务的处理流程与2PC两阶段提交类似,不过2PC通常都是在跨库的DB层面,而TCC本质上就是一个应用层面的2PC,需要通过业务逻辑来实现.这种分布式事务的实现方式的优势在于,可以让应用自己定义数据库操作的粒度,使得降低锁冲突、提高吞吐量成为可能.

  • 而不足之处则在于对应用的侵入性非常强,业务逻辑的每个分支都需要实现try、confirm、cancel三个操作.此外,其实现难度也比较大,需要按照网络状态、系统故障等不同的失败原因实现不同的回滚策略.为了满足一致性的要求,confirm和cancel接口还必须实现幂等.

基于分布式消息的最终一致性方案

  • 2PC 和 3PC 这两种方法,有两个共同的缺点,一是都需要锁定资源,降低系统性能;二是,没有解决数据不一致的问题.因此,便有了通过分布式消息来确保事务最终一致性的方案.
  • 实现方式: 将需要分布式处理的事务通过消息或者日志的方式异步执行,消息或日志可以存到本地文件、数据库或消息队列中,再通过业务规则进行失败重试.
  • 基于分布式消息的最终一致性方案的事务处理,引入了一个消息中间件(Message Queue,MQ),用于在多个应用之间进行消息传递.
    • 以网上购物为例.假设用户 A 在某电商平台下了一个订单,需要支付 50 元,发现自己的账户余额共 150 元,就使用余额支付,支付成功之后,订单状态修改为支付成功,然后通知仓库发货.
    • 在该事件中,涉及到了订单系统、支付系统、仓库系统,这三个系统是相互独立的应用,通过远程服务进行调用.大致流程如下
      • 订单系统把订单消息发给消息中间件,消息状态标记为“待确认”.
      • 消息中间件收到消息后,进行消息持久化操作,即在消息存储系统中新增一条状态为“待发送”的消息.
      • 消息中间件返回消息持久化结果(成功 / 失败),订单系统根据返回结果判断如何进行业务操作.失败,放弃订单,结束(必要时向上层返回失败结果);成功,则创建订单.
      • 订单操作完成后,把操作结果(成功 / 失败)发送给消息中间件.
      • 消息中间件收到业务操作结果后,根据结果进行处理：失败,删除消息存储中的消息,结束;成功,则更新消息存储中的消息状态为“待发送(可发送)”,并执行消息投递.
      • 如果消息状态为“可发送”,则 MQ 会将消息发送给支付系统,表示已经创建好订单,需要对订单进行支付.支付系统也按照上述方式进行订单支付操作.
      • 订单系统支付完成后,会将支付消息返回给消息中间件,中间件将消息传送给订单系统.订单系统再调用库存系统,进行出货操作.

实现方式对比

基于XA的二阶段提交协议 基于XA的三阶段提交协议 基于分布式消息的最终一致性方案
算法一致性类别 强一致性 强一致性 最终一致性
执行方式 同步执行 同步执行 异步执行
同步阻塞问题 有 无 无
单点故障问题 有 无 无
系统并发度 基于XA的二阶段提交协议 < 三阶段提交协议 < 基于分布式消息的最终一致性方案
分布式事务系统性能 基于XA的二阶段提交协议 < 三阶段提交协议 < 基于分布式消息的最终一致性方案

分布式锁

分布式锁的三种实现方法及对比

  • 基于数据库实现分布式锁(关系型数据库)
  • 基于缓存实现分布式锁
  • 基于Zookeeper实现分布式锁

基于数据库实现分布式锁

  • 要实现分布式锁,最简单的方式就是创建一张锁表,然后通过操作该表中的数据来实现.
  • 当我们要锁住某个资源时,就在该表中增加一条记录,想要释放锁的时候就删除这条记录. 数据库对共享资源做了唯一性约束,如果有多个请求被同时提交到数据库的话,数据库会保证只有一个操作可以成功,操作成功的那个线程就获得了访问共享资源的锁,可以进行操作.
  • 基于数据库实现分布式锁比较简单,绝招在于创建一张锁表,为申请者在锁表里建立一条记录,记录建立成功则获得锁,消除记录则释放锁.该方法依赖于数据库,主要有 两个缺点：
    • 单点故障问题.一旦数据库不可用,会导致整个系统崩溃.
    • 死锁问题.数据库锁没有失效时间,未获得锁的进程只能一直等待已获得锁的进程主动释放锁.一旦已获得锁的进程挂掉或者解锁操作失败,会导致锁记录一直存在数据库中,其他进程无法获得锁.

基于缓存实现分布式锁

  • 所谓基于缓存,也就是说把数据存放在计算机内存中,不需要写入磁盘,减少了 IO 读写.
  • 使用Redis来实现
    • Redis 通常可以使用 setnx(key, value) 函数来实现分布式锁.key 和 value 就是基于缓存的分布式锁的两个属性,其中 key 表示锁 id,value = currentTime + timeOut,表示当前时间 + 超时时间.也就是说,某个进程获得 key 这把锁后,如果在 value 的时间内未释放锁,系统就会主动释放锁.
    • Redis 通过队列来维持进程访问共享资源的先后顺序.Redis 锁主要基于 setnx函数实现分布式锁,当进程通过 setnx<key,value> 函数返回 1 时,表示已经获得锁.排在后面的进程只能等待前面的进程主动释放锁,或者等到时间超时才能获得锁.

基于Zookeeper实现分布式锁

  • ZooKeeper 基于树形数据存储结构实现分布式锁,来解决多个进程同时访问同一临界资源时,数据的一致性问题.ZooKeeper 的树形数据存储结构主要由 4 种节点构成：

    • 持久节点.这是默认的节点类型,一直存在于 ZooKeeper 中.
    • 持久顺序节点.也就是说,在创建节点时,ZooKeeper 根据节点创建的时间顺序对节点进行编号.
    • 临时节点.与持久节点不同,当客户端与 ZooKeeper 断开连接后,该进程创建的临时节点就会被删除.
    • 临时顺序节点,就是按时间顺序编号的临时节点

  • 根据它们的特征,ZooKeeper 基于临时顺序节点实现了分布锁.

三种实现方式对比

理解的容易程度 数据库>缓存>Zookeeper
实现的复杂度 Zookeeper>=缓存>数据库
性能 缓存>Zookeeper>=数据库
可靠性 Zookeeper>=缓存>数据库
  • 为了确保分布式锁的可用性,我们在设计时应考虑到以下几点：
    • 互斥性,即在分布式系统环境下,分布式锁应该能保证一个资源或一个方法在同一时间只能被一个机器的一个线程或进程操作.
    • 具备锁失效机制,防止死锁.即使有一个进程在持有锁的期间因为崩溃而没有主动解锁,也能保证后续其他进程可以获得锁.
    • 可重入性,即进程未释放锁时,可以多次访问临界资源.有高可用的获取锁和释放锁的功能,且性能要好

如何解决分布式锁的羊群效应问题？

  • 在分布式锁问题中,会经常遇到羊群效应.所谓羊群效应,就是在整个分布式锁的竞争过程中,大量的“Watcher 通知”和“子节点列表的获取”操作重复运行,并且大多数节点的运行结果都是判断出自己当前并不是编号最小的节点,继续等待下一次通知,而不是执行业
    务逻辑.
  • 具体方法可以分为以下三步:
    • 在与该方法对应的持久节点的目录下,为每个进程创建一个临时顺序节点.
    • 每个进程获取所有临时节点列表,对比自己的编号是否最小,若最小,则获得锁.
    • 若本进程对应的临时节点编号不是最小的,则继续判断：
      • 若本进程为读请求,则向比自己序号小的最后一个写请求节点注册 watch 监听,当监听到该节点释放锁后,则获取锁;
      • 若本进程为写请求,则向比自己序号小的最后一个读请求节点注册 watch 监听,当监听到该节点释放锁后,获取锁.

分布式体系结构

  • 分布式系统架构的目的是,将多个服务器资源管理起来,寻找合适的服务器去执行用户任务

集中式结构

  • 集中式结构就是,由一台或多台服务器组成中央服务器,系统内的所有数据都存储在中央服务器中,系统内所有的业务也均先由中央服务器处理.多个节点服务器与中央服务器连接,并将自己的信息汇报给中央服务器,由中央服务器统一进行资源和任务调度：中央服务器根据这些信息,将任务下达给节点服务器;节点服务器执行任务,并将结果反馈给中央服务器.
  • 集中式结构最大的特点,就是部署结构简单.这是因为,集中式系统的中央服务器往往是多个具有较强计算能力和存储能力的计算机,为此中央服务器进行统一管理和调度任务时,无需考虑对任务的多节点部署,而节点服务器之间无需通信和协作,只要与中央服务器通信协作即可.
经典集中式结构
  • Google Borg、 Kubernetes 和 Apache Mesos

非集中式结构

  • 在非集中式结构中,服务的执行和数据的存储被分散到不同的服务器集群,服务器集群间通过消息传递进行通信和协调.

  • Akka 集群、Redis 集群和Cassandra 集群

分布式调度架构

单体调度

  • 为用户任务寻找合适的服务器这个过程,在分布式领域中叫作调度.在分布式系统架构中,调度器就是一个非常重要的组件.它通常会提供多种调度策略,负责完成具体的调度工作.
  • 分布式系统中的单体调度是指,一个集群中只有一个节点运行调度进程,该节点对集群中的其他节点具有访问权限,可以搜集其他节点的资源信息、节点状态等进行统一管理,同时根据用户下发的任务对资源的需求,在调度器中进行任务与资源匹配,然后根据匹配结果将任务指派给其他节点.
  • 单体调度器拥有全局资源视图和全局任务,可以很容易地实现对任务的约束并实施全局性的调度策略
多个集群/数据中心如何实现单体调度呢？
  • 集群联邦,就是将多个集群联合起来工作,核心思想是增加一个控制中心,由它提供统一对外接口,多个集群的 Master 向这个控制中心进行注册,控制中心会管理所有注册集群的状态和资源信息,控制中心接收到任务后会根据任务和集群信息进行调度匹配,选择到合适的集群后,将任务发送给相应的集群去执行.
单体调度的特征
  • 单体调度器可以很容易实现对作业的约束并实施全局性的调度策略,因此适合批处理任务和吞吐量较大、运行时间较长的任务.
  • 单体调度系统的状态同步比较容易且稳定,这是因为资源使用和任务执行的状态被统一管理,降低了状态同步和并发控制的难度.
  • 调度算法只能全部内置在核心调度器当中,因此调度框架的灵活性和策略的可扩展性不高.
  • 单体调度存在单点故障的可能性

两层调度

  • 两层调度结构对应的就是两层调度器,资源的使用状态同时由中央调度器和第二层调度器管理,中央调度器从整体上进行资源的管理与分配,将资源分配到第二层调度器;再由第二层调度器负责将资源与具体的任务配对,因此第二层调度可以有多个调度器,以支持不同的任务类型.
  • 典型代表是 Apache Mesos 和 Hadoop YARN.

共享状态调度

  • 集群中需要管理的对象主要包括两种：

    • 一是,资源的分配和使用状态;
    • 二是,任务的调度和执行状态;

  • 在单体调度中,这两种对象都是由单体调度器管理的,因此可以比较容易地保证全局状态的一致性,但问题是可扩展性较差（支持业务类型受限）,且存在单点瓶颈问题.

  • 而在两层调度中,这两种对象分别由第一层中央调度器和第二层 Framework 调度器管理,由于 Framwork 调度器只能看到部分资源,因此不能保证全局状态的一致性,也不容易实现全局最优的调度.

  • 这种调度架构在支持多种任务类型的同时,还能拥有全局的资源状态信息.要做到这一点,这种调度架构的多个调度器需要共享集群状态,包括资源状态和任务状态等.因此,这种调度架构,称之为共享状态调度器

  • 代表: Google Omega

单体调度、两层调度和共享调度的区别是什么？

  • 单体调度,是由一个中央调度器去管理整个集群的资源信息和任务调度,也就是说所有任务只能通过中央调度器进行调度.
    • 这种调度架构的优点是,中央调度器拥有整个集群的节点资源信息,可以实现全局最优调度.但它的缺点是,无调度并发性,且中央服务器存在单点瓶颈问题,导致支持的调度规模和服务类型受限,同时会限制集群的调度效率.因此,单体调度适用于小规模集群.
  • 两层调度,是将资源管理和任务调度分为两层来调度.其中,第一层调度器负责集群资源管理,并将可用资源发送给第二层调度;第二层调度接收到第一层调度发送的资源,进行任务调度.
    • 这种调度架构的优点是,避免了单体调度的单点瓶颈问题,可以支持更大的服务规模和更多的服务类型.但其缺点是,第二层调度器往往只对全局资源信息有部分可观察性,因此任务匹配算法无法实现全局最优.双层调度适用于中等规模集群.
  • 共享状态调度,多个调度器,每个调度器都可以看到集群的全局资源信息,并根据这些信息进行任务调度.相较于其他两个调度架构来说,共享状态调度架构适用的集群规模最大.
    • 这种调度架构的优点是,每个调度器都可以获取集群中的全局资源信息,因此任务匹配算法可以实现全局最优性.但,也因为每个调度器都可以在全局范围内进行任务匹配,所以多个调度器同时调度时,很可能会匹配到同一个节点,从而造成资源竞争和冲突.

分布式计算

MapReduce

  • 批处理

  • 核心思想是,将大任务拆分成多个小任务,针对这些小任务分别计算后,再合并各小任务的结果以得到大任务的计算结果.

  • 这种模式下任务运行完成之后,整个任务进程就结束了,属于短任务模式

Stream

  • 实时性任务主要是针对流数据的处理,对处理时延要求很高,通常需要有常驻服务进程,等待数据的随时到来随时处理,以保证低时延.处理流数据任务的计算模式,在分布式领域中叫作Stream.

Actor

流水线

  • 将一个任务拆分为多个步骤（子任务）,然后多个这样的任务通过对步骤（子任务）的重叠执行,以实现数据并行处理的场景.

分布式通信

远程调用

  • 本地调用通常指的是,进程内函数之间的相互调用;而远程调用,是进程间函数的相互调用,是进程间通信 IPC（Inter-Process Communication）的一种方式.
  • 根据进程是否部署在同一台机器上,远程调用可以分为如下两类：
    • 本地过程调用（Local Procedure Call,LPC）,是指运行在同一台机器上的进程之间的互相通信,即在多进程操作系统中,运行的不同进程之间可以通过 LPC 进行函数调用.
    • 远程过程调用（Remote Procedure Call,RPC）,是指不同机器中运行的进程之间的相互通信,某一机器上运行的进程在不知道底层通信细节的情况下,就像访问本地服务一样,去调用远程机器上的服务.
远程过程调用 RPC(Remote Procedure Call)
  • RPC 就是调用方采用参数传递的方式,通过调用本机器上的一个函数或方法, 去执行远程机器上的函数或方法（可以统称为服务）,并返回结果.在整个过程中,RPC会隐藏具体的通信细节.
  • RPC 与本地调用主要有三点不同
    • 第一个区别是,调用 ID 和函数的映射.
      • 在本地调用中,进程内可共享内存地址空间,因此程序可直接通过函数名来调用函数.而函数名的本质就是一个函数指针,可以看成函数在内存中的地址.比如,调用函数 f(),编译器会帮我们找到函数 f() 相应的内存地址.但在 RPC 中,只通过函数名是不行的,因为不同进程的地址空间是不一样的.
      • 所以在 RPC 中,所有的函数必须要有一个调用 ID 来唯一标识.一个机器上运行的进程在做远程过程调用时,必须附上这个调用 ID.另外,我们还需要在通信的两台机器间,分别维护一个函数与调用 ID 的映射表.两台机器维护的表中,相同的函数对应的调用 ID 必须保持一致.
      • 当一台机器 A 上运行的进程 P 需要远程调用时,它就先查一下机器 A 维护的映射表,找出 对应的调用 ID,然后把它传到另一台机器 B 上,机器 B 通过查看它维护的映射表,从而确 定进程 P 需要调用的函数,然后执行对应的代码,最后将执行结果返回到进程 P.
    • 第二个区别是,序列化和反序列化.
      • 我们知道了调用方调用远程服务时,需要向被调用方传输调用 ID 和对应的函数参数,那调用方究竟是怎么把这些数据传给被调用方的呢？
      • 在本地调用中,进程之间共享内存等,因此我们只需要把参数压到栈里,然后进程自己去栈里读取就行.但是在 RPC 中,两个进程分布在不同的机器上,使用的是不同机器的内存,因此不可能通过内存来传递参数.
      • 而网络协议传输的内容是二进制流,无法直接传输参数的类型,因此这就需要调用方把参数先转成一个二进制流,传到被调用方后,被调用方再把二进制流转换成自己能读取的格式. 这个过程,就叫作序列化和反序列化.
      • 同理,被调用方返回的结果也需要有序列化和反序列化的过程,不然调用方无法获取到结
        果.也就是说,RPC 与本地调用相比,参数的传递需要进行序列化和反序列化操作.
    • 第三个区别是,网络传输协议
      • 序列化和反序列化解决了调用方和被调用方之间的数据传输格式问题,但要想序列化后的数据能在网络中顺利传输,还需要有相应的网络协议,比如TCP、UDP 等,因此就需要有一个底层通信层.
      • 调用方通过该通信层把调用 ID 和序列化后的参数传给被调用方,被调用方同样需要该通信层将序列化后的调用结果返回到调用方.
      • 也就是说,只要调用方和被调用方可以互传数据,就可以作为这个底层通信层.因此,它所使用的网络协议可以有很多,只要能完成网络传输即可.目前来看,大部分 RPC 框架采用的是 TCP 协议.
远程方法调用 RMI(Remote Method Invocation)
  • RMI 是一个基于 Java 环境的应用编程接口,能够让本地 Java 虚拟机上运行的对象,像调用本地对象一样调用远程 Java 虚拟机上的对象.
  • RMI 可以说是 RPC 的一种具体形式,其原理与 RPC 基本一致,唯一不同的是 RMI 是基于对象的,充分利用了面向对象的思想去实现整个过程,其本质就是一种基于对象的 RPC 实现.
  • RMI 与 PRC 最大的不同在于调用方式和返回结果的形式,RMI 通过对象作为远程接口来进行远程方法的调用,返回的结果也是对象形式,可以是 Java 对象类型,也可以是基本数据类型. RMI 的典型实现框架有 EJB（Enterprise JavaBean,企业级 JavaBean）

消息队列

发布订阅

  • 发布订阅的三要素是生产者、消费者和消息中心.
    • 生产者负责产生数据放到消息中心,消费者向消息中心订阅自己感兴趣的消息,当发布者推送数据到消息中心后,消息中心根据消费者订阅情况将相关数据推送给对应的订阅者
发布订阅的基本工作原理
  • 在分布式通信领域中,消息系统一般有两种典型的模式.一种是点对点模式（P2P,Point to Point）,另一种是发布订阅模式（Pub/Sub,Publish/Subscribe）