分布式技术原理与算法

单机模式

所有应用程序和数据均部署在一台电脑或服务器上,由一台计算机完成所有的处理。存在性能受限、存在单点失效问题

分布式模式

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

数据并行/数据分布式

并行计算采用消息共享模式使用多台计算机并行运行或执行多项任务,核心原理是每台计算机上执行相同的程序,将数据拆分放到不同的计算机上进行计算。对提升单个任务的执行性能及降低时延无效

任务并行/任务分布式

将单个复杂的任务拆分为多个子任务,从而使得多个子任务可以在不同的计算机上并行执行。提供了更好的性能、扩展性、可维护性的同时,也带来了设计复杂性问题

分布式系统指标

性能、资源占用、可用性、可扩展性

分布式互斥(Distributed Mutual Exclusion)

在分布式系统里,排他性的资源访问方式,而这种被互斥访问的共享资源就叫作临界资源

分布式算法

集中式算法

每个程序在需要访问临界资源时,先给协调者发送一个请求。如果当前没有程序使用这个资源,协调者直接授权请求程序访问;否则,按照先来后到的顺序,访问临界资源

流程

  1. 向协调者发送请求授权信息,1次消息交互;
  2. 协调者向程序发放授权信息,1次消息交互;
  3. 程序使用完临界资源后,向协调者发送释放授权,1次消息交互。

优点 直观、简单、信息交互量少、易于实现,并且所有程序只需和协调者通信,程序之间无需通信。

缺点 协调者会成为系统的性能瓶颈,容易引发单点故障问题

分布式算法

程序要访问临界资源时,先向系统中的其他程序发送一条请求消息,在接收到所有程序返回的同意消息后,才可以访问临界资源。其中,请求消息需要包含所请求的资源、请求者的ID,以及发起请求的时间。也常使用组播和逻辑时钟的算法。

缺点 在大型系统中使用分布式算法,消息数量会随着需要访问临界资源的程序数量呈指数级增加,容易导致高昂的沟通成本

令牌环算法

所有程序构成一个环结构令牌按照顺时针(或逆时针)方向在程序之间传递,收到令牌的程序有权访问临界资源,访问完成后将令牌传送到下一个程序;若该程序不需要访问临界资源,则直接把令牌传送给下一个程序

优点 公平性高,在改进单点故障后,稳定性也很高,适用于系统规模较小,并且系统中每个程序使用临界资源的频率高且使用时间比较短的场景。

两层结构的分布式令牌环算法

广域网由多个局域网组成,因此在该算法中,局域网是较低的层次,广域网是较高的层次。每个局域网中包含若干个局部进程和一个协调进程。局部进程在逻辑上组成一个环形结构,在每个环形结构上有一个局部令牌T在局部进程间传递。局域网与局域网之间通过各自的协调进程进行通信,这些协调进程同样组成一个环结构,这个环就是广域网中的全局环。在这个全局环上,有一个全局令牌在多个协调进程间传递。

主节点

在一个分布式集群中负责对其他节点的协调和管理

Bully算法

活着的节点中,选取ID最大的节点作为主节点。

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

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

流程

Raft算法

典型的多数派投票选举算法

Leader,即主节点,同一时刻只有一个Leader,负责协调和管理其他节点; Candidate,即候选者,每一个节点都可以成为Candidate,节点在该角色下才可以被选为新的Leader; Follower,Leader的跟随者,不可以发起选举。

优点 选举速度快、算法复杂度低、易于实现

缺点 要求系统内每个节点都可以相互通信,且需要获得过半的投票数才能选主成功,因此通信量大

该算法选举稳定性比Bully算法好,这是因为当有新节点加入或节点故障恢复后,会触发选主,但不一定会真正切主,除非新节点或故障后恢复的节点获得投票数过半,才会导致切主

ZAB算法

具有优先级的民主投票,尽可能保证数据最新性,ID大的节点优先成为主

选主原则

server_zxID最大者成为Leader,若server_zxID相同,则server_id最大者成为Leader。

优点 性能稳定。

缺点 选举时间较长,容易出现广播风暴,需要知道所有节点的zxId和serverId

分布式共识

在多个节点均可独自操作或记录的情况下,使得所有节点针对某个状态达成一致的过程。分布式共识包括两个关键点,获得记账权所有节点或服务器达成一致

PoW算法

以每个节点或服务器的计算能力,即算力,来竞争记账权

比特币系统设置的总量2100万个比特币,系统中的每个节点都有记账权,成功获得记账权的节点将获得记账奖励,这个奖励就来自于这个总量,这个就是比特币的来源。因为和黄金采矿原则类似,谁付出谁得到,因此记账的过程也被称形象的称为挖矿。

工作量证明过程 利用区块的index、前一个区块的哈希值、交易的时间戳、区块数据、nonce值,通过SHA256计算出一个哈希值,这里的nonce值是无法直接猜出的,所以只能大量的穷举尝试并且每次尝试都需要一定的计算量,因此需要大量的计算量才能得到一个正确的nonce值。每次为了争取一个区块的记账权,而获得正确nonce值的过程就是一个PoW(工作量证明)

PoS算法

系统权益代替算力来决定区块记账权,拥有的权益越大,获得记账权的概率就越大

DPoS算法

是一种委托权益证明算法。持有币的人可以通过投票选举出一些节点,来作为代表去记账

实现分布式事务

XA协议的二阶段提交

XA协议可以分两部分,即事务管理器本地资源管理器

执行过程 分为投票(voting)和提交(commit)两个阶段。协调者下发请求事务操作,参与者将操作结果通知协调者,协调者根据所有参与者的反馈结果决定各参与者是要提交操作还是撤销操作

缺点 同步阻塞问题,单点故障问题,提交阶段由于网络问题等导致的数据不一致问题

三阶段提交

为了解决两阶段提交的同步阻塞和数据不一致问题,三阶段提交引入了超时机制和准备阶段

同时在协调者和参与者中引入超时机制。如果协调者或参与者在规定的时间内没有接收到来自其他节点的响应,就会根据当前的状态选择提交或者终止整个事务

在第一阶段和第二阶段中间引入了一个准备阶段,也就是在提交阶段之前,加入了一个预提交阶段。在预提交阶段排除一些不一致的情况,保证在最后提交之前各参与节点的状态是一致的。

CanCommit、PreCommit、DoCommit三个阶段

PreCommit阶段 协调者根据参与者的回复情况,来决定是否可以进行PreCommit操作。如果所有参与者回复的都是“Yes”,那么协调者就会执行事务的预执行:

2PC和3PC这两种方法,有两个共同的缺点,一是都需要锁定资源,降低系统性能;二是,没有解决数据不一致的问题。基于分布式消息的重试机制,得到最终一致性方案

刚性事务

遵循ACID原则,具有强一致性。比如,数据库事务。

柔性事务

其实就是根据不同的业务场景使用不同的方法实现最终一致性,也就是说我们可以根据业务的特性做部分取舍,容忍一定时间内的数据不一致

BASE理论

基本可用:分布式系统出现故障的时候,允许损失一部分功能的可用性。比如,某些电商618大促的时候,会对一些非核心链路的功能进行降级处理。

柔性状态:在柔性事务中,允许系统存在中间状态,且这个中间状态不会影响系统整体可用性。比如,数据库读写分离,写库同步到读库(主库同步到从库)会有一个延时,其实就是一种柔性状态。

最终一致性:事务在操作过程中可能会由于同步延迟等问题导致不一致,但最终状态下,数据都是一致的。

分布式锁

与普通锁不同的是,是指分布式环境下,系统部署在多个机器中,实现多进程分布式互斥的一种锁

实现方式

a. 本进程为读请求,如果比自己序号小的节点中有写请求,则等待; b. 本进程为写请求,如果比自己序号小的节点中有读请求,则等待

在整个分布式锁的竞争过程中,大量的“Watcher通知”和“子节点列表的获取”操作重复运行,并且大多数节点的运行结果都是判断出自己当前并不是编号最小的节点,继续等待下一次通知,而不是执行业务逻辑,若本进程对应的临时节点编号不是最小的,则继续判断: 若本进程为读请求,则向比自己序号小的最后一个写请求节点注册watch监听,当监听到该节点释放锁后,则获取锁; 若本进程为写请求,则向比自己序号小的最后一个请求节点注册watch监听,当监听到该节点释放锁后,获取锁

分布式资源管理

分布式体系结构

集中式结构

一台或多台服务器组成中央服务器,系统内的所有数据都存储在中央服务器中,系统内所有的业务也均先由中央服务器处理。多个节点服务器与中央服务器连接,并将自己的信息汇报给中央服务器,由中央服务器统一进行资源和任务调度:中央服务器根据这些信息,将任务下达给节点服务器;节点服务器执行任务,并将结果反馈给中央服务器。

Redis集群是一个非集中式集群管理系统,没有中心节点,不会因为某个节点造成性能瓶颈,每个节点均支持数据存储,且采用分片存储方式,提高了写的并发能力。同时,每个节点的设计采用主备设计,提高了数据的可靠性

Akka集群是一个完全去中心化的集群管理系统,节点之间都是P2P的连接模式,通过Gossip协议来进行通信,节点之间有角色划分,负责数据存储的节点会进行存储数据。

Redis集群也是P2P的网状连接模式,但是基于key-value的数据库模型每个节点都可以执行数据的计算和存储。此外,Redis集群引入了哈希槽的概念,来解决数据的分片存储问题。

Cassandra集群的结构是一致性哈希的P2P,节点会构成一个环结构,通过哈希映射来选择对应的节点

在主备场景下,正常情况下,主节点提供服务,备节点是对主节点的数据、状态进行备份,以确保主故障后备升主后业务可以正常运行。主备节点之间通常会通过心跳的方式进行检测,目的是监控主节点是否故障,若故障则备升主,保证业务运行,如果主备节点网络端口,两者之间心跳均不可达,就会出现双主现象

集中式架构,Master判断Slave存活方式 上图中,TCP连接针对Slave进程退出的情况,而Slave所在器服务器故障,宕机的情况下,则使用心跳的方式进行检测。

单体调度

一个集群中只有一个节点运行调度进程,该节点对集群中的其他节点具有访问权限,可以搜集其他节点的资源信息、节点状态等进行统一管理,同时根据用户下发的任务对资源的需求,在调度器中进行任务与资源匹配,然后根据匹配结果将任务指派给其他节点

单体调度器拥有全局资源视图和全局任务,可以很容易地实现对任务的约束并实施全局性的调度策略

单体调度的特征

两层调度

资源的使用状态同时由中央调度器第二层调度器管理,中央调度器从整体上进行资源的管理与分配,将资源分配到第二层调度器;再由第二层调度器负责将资源与具体的任务配对,因此第二层调度可以有多个调度器,以支持不同的任务类型。

中央调度器算法 通常有最大最小公平算法和主导资源公平算法等

共享状态调度器

通过将单体调度器分解为多个调度器,每个调度器都有全局的资源状态信息,从而实现最优的任务调度,提供了更好的可扩展性

乐观并发调度

强调事后检测,在事务提交时检查是否避免了冲突:若避免,则提交;否则回滚并自动重新执行。也就是说,它是在执行任务匹配调度算法后,待计算出结果后再进行冲突检测。

悲观并发调度

强调事前预防,在事务执行时检查是否会存在冲突。不存在,则继续执行;否则等待或回滚。也就是说,在执行任务匹配调度算法前,通过给不同的Framework发送不同的资源,以避免冲突

分布式计算

MapReduce

Fork-Join计算模式是Java版本的MapReduce思想实现

流数据Stream

需要实时处理的数据,我们称之为流数据,适用流数据大量、快速、时变的流形式持续在应用中产生的处理数据密集型应用

Actor计算模式

流水线计算模式

将一个大任务拆分为多个步骤执行,不同的步骤可以采用不同的进程执行

分布式通信

本地调用:进程内函数之间的相互调用; 远程调用:进程间函数的相互调用

RPC

调用方采用参数传递的方式,通过调用本机一个函数或方法,去执行远程机器上的函数或方法(可以统称为服务),并返回结果

核心 远程过程调用和调用一次本地服务没什么不同

RPC与本地调用区别

调用ID和函数的映射:本地调用中,进程内可共享内存地址空间,因此程序可直接通过函数名来调用函数,函数名如指针,得到执行方法,执行指针对应的指令,而远程调用由于不同进程地址空间的关系,需要在通信的两台机器间,维护一个函数与调用ID的映射表,进程在做远程过程调用时,必须附上这个调用ID

序列化和反序列化:网络协议传输的内容是二进制流,无法直接传输参数的类型,需要调用方把参数先转成一个二进制流,传到被调用方后,被调用方再把二进制流转换成自己能读取的格式

网络传输协议:大部分RPC框架采用的是TCP协议

RMI

RMI是基于对象的,充分利用了面向对象的思想去实现整个过程,其本质就是一种基于对象的RPC实现

不管是RPC还是RMI,大多服务调用都是同步阻塞式的,虽然也可以使用异步,但是进程较多时,进程维护通信的复杂度非常高,这是分布式计算规模增大和复杂化需求下,出现了专门的异步通信模式

消息发布订阅模式

观察者模式和发布订阅区别

观察者模式采用了直接通信,观察者和被观察者通信时延低一些,但它们的依赖关系比较强,不管是被观察者还是观察者逻辑或接口有更改,另外一个均会受影响。而发布者和订阅者模式采用间接通信,引入了消息中心,相对比较厚重,且通信时延相对会高一点,但实现了订阅者与发布者的解耦

消息队列模式

发布订阅与消息队列区别

分布式数据存储和管理

CAP

CAP三个指标不能同时满足

保CA弃P 多见于单体架构情况,不存在网络分区问题的系统,分布式系统难免出现网络问题,不适用改策略

保CP弃A 多见于分布式场景需要很强的数据一致性,或者该场景可以容忍系统长时间无响应的情况

保AP弃C 多见于分布式场景需要很高的可用性,或者说在网络状况不太好的情况下,该场景允许数据暂时不一致

zookeeper是基于CP的,euraka是基于AP的,zokeeper有master,slave之分,如果正在选主或集群半数以上机器不可用,那么zookeeper无法保证服务的可用;而Euraka没有,采用peer to peer通信,节点彼此互相注册提高可用性。即使所有节点都挂了,也能通过本地得到缓存数据。根据两者区别来选择合适的注册中心

ACID中的C强调的是事务一致性,而CAP中的C强调的数据一致性

ACID中的A强调的是原子性,而CAP中的A强调的可用性

BASE理论同时牺牲一些C,和一些A得到服务基本可用数据最终一致性

分布式数据存储系统

将数据根据某种规则存储到不同的机器上,当获取指定数据时,再按照规则到存储数据的机器里获取

数据分片技术 数据分片技术,是指分布式存储系统按照一定的规则将数据存储到相对应的存储节点中,或者到相对应的存储节点中获取想要的数据。减少单节点的性能瓶颈问题;

数据复制技术 将数据进行备份,以使得多个节点存储该数据。对每个节点上存储的分片数据,采用主备方式存储,以保证数据的可靠性

数据的格式 数据可以被划分为三类:结构化数据、半结构化数据和非结构化数据

数据存储系统 分布式数据库、分布式键值系统和分布式文件系统。

数据分布设计原则

数据均匀

数据稳定 存储节点出现故障需要移除或者扩增时,数据按照分布规则得到的结果应该尽量保持稳定,不要出现大范围的数据迁移

节点异构性 不同存储节点的硬件配置可能差别很大,要考虑分到的数据量、用户访问量的问题

隔离故障域 为了保证数据的可用和可靠性,通过备份数据到不同的故障域,比如不同机房、不同机架

性能稳定性 数据存储和查询的效率要有保证,不能因为节点的添加或者移除,造成存储或访问性能的严重下降

数据分布方法

哈希 通过哈希函数,通过特定数据特征计算得到存储节点。哈希函数设置得当,可以很好地保证数据均匀性,缺点:就是稳定性较差。适用于同类型节点且节点数量比较固定的场景

一致性哈希 将存储节点和数据都映射到一个首尾相连的哈希环上,存储节点可以根据IP地址进行哈希,数据通常通过顺时针方向寻找的方式,来确定自己所属的存储节点,即从数据映射在环上的位置开始,顺时针方向找到的第一个存储节点。在数据存储前,对存储节点预先进行了哈希,数据存储时采用哈希方式确定存储位置.缺点:均匀性问题;适用于同类型节点、节点规模会发生变化的场景

带有限负载的一致性哈希 每个存储节点设置了一个存储上限值来控制存储节点添加或移除造成的数据不均匀,适用于同类型节点、节点规模会发生变化的场景

带虚拟节点的一致性哈希 根据每个节点的性能,为每个节点划分不同数量的虚拟节点,并将这些虚拟节点映射到哈希环中,然后再按照一致性哈希算法进行数据映射和存储。缺点:节点的维护和管理的复杂度。适用于异构节点、节点规模会发生变化的场景

容错(fault tolerance)指的是, 发生故障时,系统还能继续运行。

灾备(又称灾难恢复,disaster recovery)指的是, 发生灾难时恢复业务的能力。灾备不是为了挽救基础设置,而是为了挽救业务。

高可用不是指系统不中断(那是容错能力),而是指一旦中断能够快速恢复,即中断必须是短暂的