分布式技术原理与算法解析思维导图模板

第二站: 分布式资源管理与负载调度

09 | 分布式体系结构之集中式结构（Master/slave结构）

Borg

简介

Brog是Google内部使用的集群管理系统，负责提交、调度、开始、重启和管理Google运行在其上的所有应用

使用权限

闭源，Google内部使用

设计目的

让用户能够不必操心资源管理的问题，专注于自己的核心业务，并做到跨多个数据中心的资源利用率最大化

任务调度框架

单层调度框架

基本调度单元

Job

基本操作单元

Task

使用公司

Google

Kubernetes

简介

Kubernetes是用于自动部署、扩展和管理容器化应用程序的开源系统。其核心是，在集群的节点上运行容器化应用，可以进行自动化容器操作，包括部署，调度和在节点间弹性伸缩

使用权限

开源，必须支持Google服务

设计目的

旨在消除编排物理/虚拟计算、网络和存储基础设施的负担，并使应用程序运营商和开发人员完全将重点放在以容器为中心的理念上进行自主运营

任务调度框架

单层调度框架

基本调度单元

Pod

基本操作单元

Service

使用公司

网易云、华为云

Mesos

简介

Mesos是Apache旗下的开源分布式资源管理框架，被称为分布式系统的内核

使用权限

开源

设计目的

为用户的数据中心提供动态的资源分配

调度框架

双层调度框架

基本调度单元

容器，Job

基本操作单元

Task

使用公司

Twitter、Apple、爱奇艺、去哪儿等

10 | 分布式体系结构之非集中式结构（Leader/Follwer结构）

Akka

简介

Akka集群是一个完全去中心化的分布式集群管理系统。集群由多个节点组成，每个节点都可以进行数据处理和任务执行，节点之间均可进行通信

特点

Akka集群为Actor模型提供了一个可容错、去中心化的节点集群管理系统，是一个用于构建可扩展的、弹性的、快速响应的应用程序的平台。

集群模型

基于Actor模型

系统结构

基于成员关系的P2P结构

数据存储方式

由负责数据存储的节点来存储数据

通信方式

Gossip协议通信

是否需要集群选主

需要

Redis

简介

Redis是一个开源的高性能分布式key-value数据库。Redis集群中的所有节点均可负责存储数据、记录集群的状态、自动发现其他节点，检测故障的节点，客户端可以访问或连接到任一节点上。

特点

支持数据的持久化、支持多种数据结构、支持数据的备份

集群模型

基于key-value数据库模型

系统结构

基于hash槽的网状拓扑

数据存储方式

分片存储，并基于Master-Slave模式实现了数据备份

通信方式

Gossip协议通信

是否需要集群选主

需要

Cassandra

简介

Cassandra集群的系统架构是基于一致性hash的完全P2P结构，没有Master的概念，每个节点代表一个hash值，通过hash映射的方式决定数据存储的位置

特点

Cassandra采用去中心化的架构，解决了集中式结构的单点故障问题，同时因为数据基于hash值分区存储，提高了读写数据的并发能力

集群模型

基于key-value 数据库模型

系统结构

一致性hash的P2P结构

数据存储方式

基于hash值分区存储

通信方式

Gossip协议通信

是否需要集群选主

不需要

11 | 分布式调度架构之单体调度

单体调度

定义

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

设计架构

有一个集中式调度器以中心化的方式取管理资源和调度任务；资源的使用状态和任务的执行状态都由调度器进行管理；调度器本身在系统中只存在单个实例，所有的资源请求和任务调度都通过着一个实例进行。

特点

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

应用实例

Brog

调度设计

以任务为单位进行调度

Scheduler模块负责任务地调度，当用户提交一个作业给BrogMaster后，BrogMaster会把该作业保存到Paxos仓库中，并将这个作业地所有任务加入等待队列中。

调度算法

筛选可行

评分取优

最差匹配

最佳匹配

Kubernetes

12 | 分布式调度架构之两层调度

定义

在两层调度器中，资源的使用状态同时由中央调度器和第二层调度器管理，但中央调度器一般只负责宏观的、大规模的资源分配，业务压力比较小；第二层调度器负责任务与资源的匹配，因此第二层调度可以有多个，以支持不同的任务类型。

特点

解决了单体调度架构中，中央服务器的单点瓶颈问题；相较于单体调度而言，提升了调度效率；支持多种类型的任务

应用实例

Apache Mesos

Mesos架构

Master节点：每个集群有且仅有一个Master节点，负责管理Slave节点，并对接上层框架

Slave节点：向Master节点汇报资源信息，并执行框架提交的任务

框架（Framework）：运行在Mesos上，是负责应用管理与调度的“组件”

Scheduler：从Master节点中获取到集群节点的信息

Executor: 在Slave节点上执行任务

调度形式

Mesos Master的Scheduler进程手机所有节点的空闲资源信息，并以Resource Offer的方式将空闲资源上报给注册的框架

框架的Scheduler接受到Mesos上报的资源后，进行任务调度与匹配，并将匹配结果下发给Mesos Master Scheduler,并由Mesos Master 转发给相应节点的执行器执行任务

调度算法

最大最小公平算法

在兼顾公平的前提下，尽可能让更多人满意的资源分配算法

主导资源公平算法（DRF）

在考虑用户公平性的前提下，还考虑了用户对不同资源类型的需求不一样，以尽可能地合理分配资源

Hadoop YARN

13 | 分布式调度架构之共享状态调度

定义

共享状态调度架构沿袭了单体调度器的模式，通过将单体调度器分解为多个调度器，每个调度器都有全局的资源状态信息，从而实现最优的任务调度

特点

分布式结构；
共享集群状态；
乐观并发调度；
调度形式类似于数据库中的事务操作；

优点

解决了单体调度架构中，中央服务器的单点瓶颈问题；解决了两层调度中任务匹配无法达到全局最优的问题；可扩展性强；

缺点

存在潜在的资源冲突问题

实现复杂

应用实例

Google Omega

Omega 架构

资源维护模块：记录集群资源状态信息（Cell State）；接收Scheduler的任务匹配结果并选择合适的任务进行调度

节点：向资源维护模块汇报资源信息

Scheduler：每个Scheduler都拥有Cell State副本，执行任务匹配算法

调度形式

Scheduler从资源维护模块获取到集群资源信息，执行任务匹配算法，并将任务匹配结果发送给资源匹配模块；
资源匹配模块选择何时的任务进行调度；

使用场景

大规模集群

14 | 分布式事务与分布式锁相关问题

分布式事务

2PC 与 3PC的区别

2PC第一阶段就执行了事务只是不提交；
3PC第一阶段只检测资源执行事务，到了第二阶段才执行事务；

3PC在第一阶段根据什么来返回YES或NO？

比如自身空闲资源是否足以支撑事务、是否会存在故障等，预估自己是否可以执行事务，但不会执行事务

3PC 解决了参与者同步阻塞问题吗？

3PC引入了超时机制，参与者不会一直等待，所以说一定程度上减少了超时问题

3PC 解决了数据不一致问题吗？

2PC在第二阶段，无法处理网络超时等情况，所以有可能导致数据不一致；
3PC 中引入了预提交阶段，相对于 2PC 来讲是增加了一个预判断，如果在预判断阶段协调者出现故障，那就不会执行事务。这样，可以在一定程度上减少故障导致的数据不一致问题。

3PC会有单点故障吗？

3PC也会有单点故障，但是它多了一个超时机制，参与者在超时时会自动提交或回滚，相当于缓解了一部分故障的影响

分布式锁

分布式互斥和分布式锁的关系是什么？

分布式锁是实现分布式互斥的一种手段或方法

ZooKeeper 分布式锁，可能存在多个节点对应的客户端在同一时间完成事务的情况吗？

存在多个节点对应的客户端与 ZooKeeper 同时进行交互的可能

每个节点之间并未进行通信协商，且它们都是独立自主的，启动时间、与 ZooKeeper 交互的时间、事务完成时间都是独立的

因此存在多个节点对应的客户端在同一时间完成事务的这种情况

Redis 为什么需要通过队列来维持进程访问共享资源的先后顺序？

如果没有队列维护多进程请求，只通过多进程反复尝试以获取锁带来的问题

反复尝试会增加通信成本和性能开销

底过多久再重新尝试

如果每次都是众多进程进行竞争的话，有可能会导致有些进程永远获取不到锁

基于队列来维持进程访问共享资源先后顺序的方法中，当一个进程释放锁之后，队列里第一个进程可以访问共享资源。

第四站：分布式通信技术

19 | 分布式通信之远程调用

定义

远程调用是进程间函数的相互调用，是进程间通信IPC的一种方式

类型

本地过程调用

本地过程调用LPC是指运行在同一机器上的进程之间的互相通信，即在多进程操作系统中，运行的不同进程之间可以通过LPC进行函数调用

远程过程调用

定义

远程过程调用RPC是指不同机器中运行的进程之间的相互通信，某一机器上运行的进程在不知道底层通信细节的情况下，就像访问本地服务一样，去调用远程机器上的服务。

原理

将底层通信细节进行封装，使用户对底层通信无感知。底层通过Client Stub和Server Stub进行数据打包，并通过网络协议进行传输

适用范围

与操作系统和语言无关

调用方式

请求基于“类名+函数名”的方式实现，被调用方搜索与之想匹配的类和方法，然后执行

返回方式

XDR表示

RMI

定义

RMI是一个基于JAVA环境的应用编程接口，能够让本地Java虚拟机上运行的对象，像调用本地对象一样调用远程Java虚拟机上的对象

本质

基于对象的RPC的具体调用

原理

通过辅助对象Stub和Skeleton完成数据的打包并实现远程调用

适用范围

用于Java环境

调用方式

通过对象作为远程接口来进行远程方法的调用

返回方式

返回Java数据类型或基本数据类型

实现框架

EJB

实现框架

Dubbo

组成

分为服务提供方，服务注册中心，服务调用方，监控中心四个部分

流程

服务提供方向服务注册中心注册服务

服务调用方从注册中心获取服务对应的地址列表

调用方从地址列表中选出一个地址进行远程调用

监控中心统计相关调用信息

20 | 分布式通信之发布订阅

定义

生产者

负责产生数据放到消息中心

消费者

向消息中心订阅自己感兴趣的消息

消息中心

根据消费者订阅情况将相关数据推送给对应的订阅者

原理

点对点模式

支持多个消费者，但一条消息只能被一个消费者消费，不允许重复消费

发布订阅模式

一条消息可以被多个订阅的消费者进行消费，即允许重复消费

发布订阅消息系统kafka

生产者Producer

作用

发布消息到Broker

消费者Consumer

作用

向Broker订阅消息

消费组Consumer Group

共同消费消息，主题中每条消息只可以由消费组中的某一个消费者进行消费

作用

提供高消费效率

消息中心Broker

作用

存储消息，并推送给订阅的Consumer

主题Topic

逻辑概念，指的是消息类型

分区Partition

物理概念，一个Topic包含多个分区

作用

实现负载均衡，避免单个Broker上的负载过高

实现消息的备份，从而保证系统的可靠性？（起备份作用的是每个partition的replica副本）

Zookeeper集群

协调和管理Broker和Consumer

特征与应用

系统解耦，系统易于维护

异步执行，解决高负载问题

21 | 分布式通信之消息队列

定义

队列是一种具有先进先出特点的数据结构，消息队列是基于队列实现的，用于存储具有特定格式的消息数据

原理

组成

生产者

产生消息或数据，并将消息或数据插入到消息队列中

消息队列

一种具有先进先出特点的数据结构，用于存储消息

消费者

从消息队列中获取消息或数据，进行相关处理

具体流程

生产者将发送的消息插入消息队列，也就是入队，之后会有一个消费者从消息队列中逐次去除消息进行处理，完成出队

实例

RocketMQ

组成

Broker Cluster

作用

负责存储Producer Cluster发布的数据，以方便消费者进行消费

内部结构

主题Topic + 消息队列 Queue

Producer Cluster

作用

负责接收用户数据，然后将数据发布到消息队列中心Broker Cluster

NameServer Cluster

作用

管理Broker的信息，包括有哪些Broker、Broker的地址和状态等，以方便生产者获取Broker信息发布消息，以及订阅者根据Broker信息获取消息

Consumer Cluster

作用

负责从Broker中获取消息进行消费。Consumer 以集群方式进行部署的好处是，提升消费者的消费能力，以避免消息队列中心行存储溢出，消息被丢弃

流程

首先启动NameServer，然后启动Broker。Broker启动后，会主动找nameServer 建立连接，并将自己的信息注册到NameServer上。注册完毕后，Broker会周期型地给NameServer发送心跳包

创建主题，并确定这个主题的数据放入哪些Broker中

当Producer生产消息发送到主题时，需要先到NameServer查询该主题存放在哪些Broker中，获取到相关Broker信息后，将消息发送给这些Broker进行存储。

Consumer要从主题消费消息，也需要首先到NameServer查阅一下该主题的消息存储在哪些Broker上，然后去相应的Broker获取消息进行消费

使用场景

购物交易

钱包充值

消息推送

22 | 分布式体系架构与分布式计算答疑

1. 在集中式架构中，Master 如何判断 Slave 是否存活呢

Slave 进程退出

TCP 长连接断开

Slave 所在服务器宕机或重启

心跳检测

追问 1：非集中式架构中，如何判断节点是否存活

每个节点被 b（1≤b<n）个节点监控，以减少心跳信息量

断心跳超时机制，可采用集中式方法中的连续 k 次心跳超时的方法进行判断，也可以通过历史心跳信息进行预测

追加 2: 一个集群为什么会存在双主的场景呢？

主备节点之间的网络连接断开了，那么主节点与备节点之间心跳均不可达，因此主节点会认为备节点故障，此时主节点会继续提供服务，而备节点会认为主节点故障，备升主。所以，集群中就出现了双主的场景

线计算和批量计算，实时计算和流式计算到底是什么呢？离线计算和批量计算、实时计算和流式计算分别是等价的吗？

离线计算和批量计算对任务执行的时延不是特别敏感，而实时计算和流式计算对任务执行的时延敏感

离线计算和实时计算是从计算时延的维度进行分类的，而批量计算和流式计算是从计算方式的维度进行分类的

对比图

第六站：分布式高可靠

28 | 分布式高可靠之负载均衡

轮询策略

定义

服务器轮流处理用户请求，以尽可能使每个服务器处理的请求数相同

类型

顺序轮询策略

请求到来时，按照服务器顺序轮流进行处理

加权轮询策略

每个服务器设置了优先级，每次请求到来时会挑选优先级最高的服务器进行处理

优缺点

优点

实现简单，服务器负载均衡，可解决服务器节点异构的问题

缺点

处理每次请求的服务器不确定，不适合有状态请求的场景

没考虑请求开销不同造成的不均衡问题

适用场景

适用于用户请求所需资源比较接近的场景，以及无状态请求场景

典型框架

Nginx

随机策略

定义

当用户请求到来时，会随机发到某个服务节点进行处理

优缺点

优点

实现简单，服务器负载基本均衡

缺点

处理每次请求的服务器不确定，不合适有状态请求的场景

没考虑服务器节点异构性和请求开销不同造成的不均衡问题

适用场景

适用于集群中服务器节点处理能力相差不大，用户请求所需资源比较接近的无状态请求的场景

典型框架

Dubbo

哈希和一致性哈希策略

定义

当处理大量用户请求时，通过哈希函数极端来得到处理该请求的服务节点

优缺点

优点

哈希函数设置合理，服务器负载均衡，且相同key的请求可落在同一个服务器节点，适合有状态请求的场景

带虚拟节点的一致性哈希策略，可以解决服务器节点异构的问题

缺点

实现相对复杂

没考虑请求开销不用造成的不均衡问题

适用场景

适用于用户请求所需资源比较接近的场景，也适用于有状态请求的场景

典型框架

Reid、Memcahced、Cassandra

29 | 分布式高可靠之流量控制

定义

在分布式系统下，控制每个服务器接收的请求数，以保证服务器来得及处理这些请求

策略

漏桶策略

定义

无论用户请求有多少，无论请求速率有多大，“漏桶”都会去接受下来，但从漏桶里出来的请求是固定速率的

优缺点

优点

做到了流量整形，即无论流量多大，即便是突发的大流量，输出依旧是一个稳定的流量

缺点

对于突发流量的情况，因为服务器处理速度与正常速度一致，会丢弃比较多的请求

适用场景

适用于间隔性突发流量且流量不用即时处理的场景

典型框架

阿里开源的流量控制框架Sentinel中的匀速排队限流策略；分布式追踪系统Jaeger中一种速率限制类型的采集策略

令牌桶策略

定义

以固定速率向令牌桶里放入令牌，每当请求到来时，必须先到桶里取一个令牌才可被服务器处理

优点

当有突发大流量时，只要令牌桶里有足够多的令牌，请求就会被迅速执行

适用场景

适用于有突发特性的流量，且流量需要即时处理的场景

典型框架

Guava提供的限流工具类RateLimiter

流量控制框架Sentinel

并发线程数

定义

在分布式系统中，当请求过多时，执行请求的并发线程数自然会随之增加，当超过一定的阈值时，需要采取一定的策略来进行流量控制

策略

直接拒绝

当并发线程数达到系统设定的阈值时，直接拒绝新来的请求

QPS指标

定义

当QPS过高达到阈值时，采取一定的策略来进行流量控制

策略

直接拒绝

定义

当QPS达到系统设定的阈值时，直接拒绝新来的请求

适用场景

适用于对系统处理能力确切已知的场景

预热

定义

当系统流量骤增时，让系统的QPS缓慢增加，在一定时间内逐渐增加到上限

适用场景

适用于具有突发特性的流量，且流量可以即时处理的场景

匀速排队

定义

严格控制系统每秒处理的请求数，请求数很多时，请求之间的间隔也会保持一致

适用场景

适用于间隔性突发流量且流量不用即时处理的场景

30 | 分布式高可用之资源隔离

线程级隔离

定义

指使用不同的线程池处理不同的请求任务，当某种请求任务出现故障时，负责其他请求任务的线程池不会受到影响

隔离标准

系统功能/服务

隔离级别

线程

适用场景

在生产环境中较为常用，尤其是对于单体应用（单进程多线程的应用）

隔离后协同方法

共享变量

进程级隔离

定义

将系统按照功能分为不同的进程，分布到相同或不同的机器中

隔离标准

系统功能/服务

隔离级别

进程

适用场景

适合于系统业务员复杂，需要对系统进行拆分的分布式应用场景

隔离后协同方法

进程间通信（IPC）

资源隔离

定义

将分布式系统的资源分成几个部分，每部分资源负责一个模块，这样系统各个模块就不会争抢资源，即资源之间互不干扰

隔离标准

系统资源

隔离级别

进程、虚拟机、主句、集群等均进行资源隔离

适用场景

适合于对资源有严格控制的分布式应用场景

隔离后协同方法

进程间通信：通常会通过网络通信

31 | 分布式高可用之故障恢复

故障类型

节点故障

定义

单个机器自身出现故障

类型

硬件故障

机器硬盘损坏、内存接触不良等

软件层故障

系统存在Bug或者负载过高，导致系统崩溃

网络故障

定义

分布式集群中，节点间无法完成通信

类型

路由器故障、DNS故障、网络线路断裂等

故障检测

定义

通过一定的方式识别或发现故障

策略

固定心跳检测

固定周期T秒发送心跳，若连续k次未收到心跳回复3（时间T内），则判断心跳超时

φ 值故障检测

定义

基于心跳间隔符合正态分布的假设计算φ 值，与设定的阈值Ф进行比较，若φ >= Ф, 则判断心跳超时，否则未超时

计算过程

采样窗口存储心跳到达的时间

通过样本计算出心跳到达时间间隔的分布

使用得到的正态分布计算当前的 φ 值

故障恢复

定义

修复分布式系统中出现的故障，使系统恢复正常

策略

主备

定义

当主节点故障后，从备节点中选出一个作为新的主节点，继续提供服务

典型框架

Redis集群、ZooKepper集群

CAP选择

本质

数据复制问题，即网络故障恢复后数据同步的问题

AP策略

保证系统可用性和分区容错性，牺牲数据一致性

适用于必须及时响应用户请求的场景

CP策略

保证系统数据一致性和分区容错性，牺牲数据可用性

适用于对数据一致性有严格要求的场景，比如银行、保险、金融系统等

32 | 答疑篇: 如何判断并解决网络分区问题

网络分区

定义

指的是在分布式集群中，节点之间由于网络不通，导致集群中节点形成不同的子集，子集中节点间的网络相通，而子集和子集间网络不通。也可以说，网络分区是子集与子集之间在网络上相互隔离了。

如何解决

集中式架构

现象

主节点与备节点之间网络不通，且一部分 Slave 节点只能与主 Master 节点连通，另一部分只能与备 Master 节点连通。

解决方案

Static Quorum

定义

固定票数的策略。在系统启动之前，先设置一个固定票数。当发生网络分区后，如果一个分区中的节点数大于等于这个固定票数，则该分区为活动分区

优点

简单、容易实现

缺点

当活动分区非常多的时候，由于各个分区的票数分散，不容易找到一个满足条件的分区，没有活动分区也就意味着整个集群不可用了

票数是固定不变的，所以不适用于集群中有动态节点加入的场景

Keep Majority

定义

保留具备大多数节点的子集群。由于不限定每个分区的节点数超过一个固定的票数，所以可以应用于动态节点加入的场景

优点

可以解决动态节点加入的问题

缺点

也不适用于产生多分区的场景。因为随着分区数增多、节点分散，也难以在众多分区中出现一个节点数 w≥n/2 的分区

通过设置仲裁机制处理

定义

引入一个第三方组件或节点作为仲裁者，该仲裁者可以与集群中的所有节点相连接，集群中所有节点将自己的心跳信息上报给这个中心节点

该中心节点可以根据全局心跳信息判断出有多少个分区。当出现网络分区后，由仲裁者确定保留哪个子集群，舍弃哪些子集群

优点

可解决多分区的问题

基于共享资源的方式处理

定义

类似于分布式锁的机制。也就是，哪个子集群获得共享资源的锁，就保留该子集群。获得锁的集群提供服务，只有当该集群释放锁之后，其他集群才可以获取锁

优点

可解决多分区的问题

缺点

，如果获取锁的节点发生故障，但未释放锁，会导致其他子集群不可用

非集中式架构

现象

非集中式架构中，节点是对称的，因此网络分区的形态是形成不同子集，子集内节点间可互相通信，而子集之间的节点不可通信

解决方案

每个节点都是对等的、提供的服务相同，所以当多个子集群之间不可达，或部分节点出现故障后，尽管提供的服务质量（SLA）可能会下降，但并不影响这些剩余节点或子集群对外提供服务，所以一般不用管。

总结

为什么提升直接竞争力要从尊重，诚实开始

如何提升职业竞争力，避免“中年危机”和“职业生命力的焦虑”呢？

要敬畏技术

说某种技术没有用，只是还没有深入了解，就从战术上轻视这些技术。殊不知，我们耳熟能详的很多新兴技术都是这些“陈芝麻烂谷子”技术的组合、延伸

不是技术没用，而是我们没有深入理解它们，没有找到它们的用武之地。

对自己要诚实

做一些重复工作之余，提升一下自我

只有对自己诚实，突破自己、完善自己

树立什么样的技术目标呢?

把自己塑造成一个“倒三角”人才（或 T 型人才）

努力把并行与分布式技术，作为技术发展的根据地，也就是字母 T 中的一竖

在不断做深、做厚分布式技术的同时，努力探索分布式技术跨界到新兴领域的可能性，或结合分布式技术去研究一些新兴技术，提升自己的技术广度，也就是字母 T 中的一横

第一站: 分布式协调与同步

03. 分布式互斥方法

霸道总裁法: 集中式算法

方法

引入一个协调者，将参与的请求者进行排序，最早的请求者可以使用临界资源

优点

简单，易于实现

通信高效

缺点

可用性低

性能易受协调者影响

应用场景

在协调者可靠性和性能有一定保障的情况下，可以适用于比较广泛的场景

民主协商法：分布式方法

方法

征求其它参与者同意后，使用临界资源

优点

可用性较高

缺点

通信成本较高

复杂度较高

应用场景

临界资源使用频度较低而且系统规模较小的场景

轮值CEO法：令牌环算法

方法

所有参与者组成一个环，轮流使用资源

优点

单个参与者通信效率较高

可用性较高

缺点

当参与者对临界资源使用频率较低时，会带来较多无用通信

应用场景

系统规模小，并且系统中每个程序使用共享资源频度较高且使用时间较短的场景

扩展点

如果要使用在大规模集群，考虑多层令牌环算法

04. 分布式选举算法

Bully 算法

选举原则

节点ID最大的成为leader

优点

容易理解

选举速度快

算法复杂度低

易于实现

缺点

信息存储量大

易频繁切主

不适用于大规模分布式系统

应用场景

适用于小规模的场景，如 MongoDB数据库

Raft

选举原则

“少数服从多数”，获得投票最多的节点成为主

优点

选举速度快

算法复杂度低

易于实现

缺点

要求系统全连接

消息通信量大

不适合大规模的集群

应用场景

适用于中小的场景，如Kubernates集群中3个节点的选主方式

ZAB

选举原则

倾向于让数据最新或者ID值最大的节点作为集群的主

优点

性能高

对系统无特殊要求

缺点

选举时间长

复杂度高

应用场景

适用于大规模分布式场景，如 Zookeeper

三种算法对比

图示

05. 分布式共识算法

Pow算法

原理

按劳分配，以每个节点的计算能力来竞争记账权，算力越高，越有可能获得记账权

优点

相对公平

有容错机制

完全去中心化

简单易懂

缺点

不适合私有链或者联盟链

共识效率很低，每秒完成交易量少

存在阻塞问题

资源浪费严重

交易服务费高

应用场景

比特币等

Pos 算法

原理

由系统权益代替算力决定区块记账权的共识机制，拥有的权益越大则成为下一个区块生产者的概率也越大

优点

资源消耗低

达成共识周期短

交易服务费低

缺点

每秒完成交易量较低

容易被垄断

无法处理分叉链的情况

应用场景

以太坊、点点币等

DPoS 算法

原理

持有币的人可以进行投票选举，选举出一些节点作为代表来记账

优点

能耗更低

每秒完成交易量高

无垄断情况

交易服务费低

更加安全

缺点

持币人投票的积极性不高

故障问题解决效率低，易出现安全隐患

应用场景

以太股、EOS等

三种算法对比

图示

06. 分布式事务方案

基于XA的二阶段提交

核心思想

系统中的事务管理器作为协调者，负责各个本地资源的提交和回滚，而资源管理器就是分布式事务的参与者；通过投票阶段和提交阶段，协调事务的操作，保持数据的一致性

特点

强一致性

同步执行

算法简单易实现

缺点

同步阻塞问题

单点故障问题

数据不一致问题

性能低

系统吞吐量低

三阶段提交

核心思想

有CanCommit、PreCommit、DoCommit三个阶段，引入超时机制和准备机制，解决2PC的同步阻塞和单点故障问题

特点

强一致性

同步执行

有同步阻塞问题（较轻）

有单点故障问题（较轻）

缺点

数据不一致问题

性能较低

系统吞吐量不高

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

核心思想

将事务通过消息或者日志的方式来异步执行，消息或者日志可以存到本地文件、数据库或消息队列中，再通过业务规则进行失效重试

特点

最终一致性

异步执行

无同步阻塞问题

无单点故障问题

性能高

系统吞吐量高

缺点

算法复杂度高

实现困难

三种实现方式对比

图示

07. 分布式锁实现方式

数据库表

实现方式

创建一张锁表，对临界资源做唯一性约束：通过增加一条记录对某一资源上锁，释放锁时删除记录

优点

容易理解

易于实现

缺点

容易出现单点故障，死锁问题

性能低

可靠性低

应用场景

适用于并发量低、性能要求低的场景

redis缓存

实现方式

通过函数setnx(key,value) 实现，key表示锁id，value表示当前时间 + 超时时间； setnx返回1则表示获得key所代表的锁，返回0则表示获取失败

优点

性能高

可以跨集群部署，无单点故障问题

易于实现

缺点

锁失效时间的控制不稳定

可靠性不如zk分布式锁高

不易理解

应用场景

适用于高并发，对性能要求高的场景

Zookeeper

实现方式

在对应的持久节点shared_lock 的目录下为每个进程创建一个临时顺序节点，每个节点确定的编号是否最小，若最小则获得锁，否则等待更小编号节点释放锁

优点

无单点故障，不可重入，死锁问题

几乎解决了数据库锁和缓存式锁的不足

可靠性高

缺点

性能没有缓存分布式锁好

实现复杂

难以理解

应用场景

Zookeeper适用于大部分分布式场景，但是不适合用于对性能要求极高的场景

三种分布式锁的比较

图示

08. 分布式在人工智能领域应用

分布式集群

功能

将多个计算机的存储能力、计算能力等进行统一管理和调度、为分布式数据处理和模型训练奠定基础

主要分布式技术

分布式集群选主

分布式集群的架构和调度

分布式集群可靠性

涉及课程章节

第一站:分布式协调与同步

第二站: 分布式资源管理与负载调度

第六站: 分布式高可靠

数据预处理

功能

对数据确实、数据噪声、数据冗余、多数据源等问题进行处理以得到高质量数据，为模型训练提供高质量输入。

主要涉及分布式技术

分布式计算

节点之间通信

分布式数据的存储与管理

涉及课程章节

第三站: 分布式计算技术

第四站: 分布式通信技术

第五站: 分布式数据存储

数据分布式训练

功能

针对大规模训练数据的场景，对大规模数据进行拆分实现分布式模型训练

主要涉及分布式技术

节点之间通信

分布式数据的存储和管理

涉及课程章节

第四站: 分布式通信技术

第五站: 分布式数据存储

模型分布式训练

功能

针对大规模训练模型场景、对大模型进行拆分实现分布式模型训练

主要涉及分布式技术

分而治之策略、流水线计算模式等

节点间通信

涉及课程章节

第三站: 分布式计算技术

第四站: 分布式通信技术

混合模型训练

功能

针对大规模训练数据和大规模训练模型共存场景，对数据和模型均进行拆分，实现分布式模型训练。

主要涉及分布式技术

分布式数据的存储和管理

分而治之策略、流水线计算模式等

节点间通信

涉及课程章节

第三站: 分布式计算技术

第四站: 分布式通信技术

第五站: 分布式数据存储

第三站: 分布式计算技术

15 | 分布式计算模式之MR

定义

将一个复杂的，难以直接解决的大问题，分割成一些规模较小的，可以比较简单的或可以直接求解的子问题，这些子问题之间相互独立且与原问题形式相同，递归地求解这些子问题，然后将子问题的解合并得到原问题的解

特点

问题规模比较大或复杂

问题可以分解成几个规模较小的，简单的同类型问题进行求解

子问题之间相互独立

子问题的解可以和并得到原问题的解

核心步骤

1. 分解原问题

2. 求解子问题

3. 合并解

计算模型

MapReduce

抽象模型

MapReduce为Map 和 Reduce 两个阶段：
Map: 把复杂的任务分解为若干个“简单的任务”执行;
Reduce: 对Map接端的结果进行汇总

组件架构

Master，也就是MRAppMaster，负责分配任务，协调任务的运行，并为Mapper分配map()函数操作、为Reducer分配reduce() 函数操作

Mapper Worker，负责Map函数功能，即负责执行子任务

Reducer worker，负责reduce函数功能，即负责汇总各个子任务的结果

特点

可以大规模的扩展，适用于大型计算机集群

拆分后的任务，可以跨多个计算机去执行，且各个小人物之间不会相互通信

适用场景

大规模可跨集群执行的任务

Fork-Join

抽象模型

Fork-Join是Java提供的原生多线程并行处理框架，采用线程级的分而治之计算模式

Fork操作：以递归的形式把一个任务拆分成多个“小任务”，把多个小任务放到多个处理器上并行执行
Join操作：当多个小任务执行完成后，再将这些执行结果合并起来即可得到原始任务的结果

特点

不能大规模扩展，只适用于在单个java虚拟机上运行

多个小任务可以相互通信，甚至一个线程可以窃取其它线程上的子任务

使用场景

单机内，可多线程并行执行的任务

16 | 分布式计算模式之stream

定义

流数据

持续快速产生的、具有时效性的数据

流计算

实时获取来自不同数据源的海量数据，进行实时分析数据，获取有价值的信息

特点

数据特点

持续产生的、具有易逝性的实时数据

数据集成方式

实时加载数据，不存储数据

计算规则

任务处理过程中计算逻辑不可以修改

计算逻辑一旦修改，之前的数据不可重新计算

实时性分析

是一种持续性，低时延、事件驱动型的计算作业

试用场景

用于对时间敏感的实时计算的、数据密集型但可以拆分为小批量数据的任务

核心步骤

1. 提交流式计算作业

2. 加载流式数据进行流计算

3. 持续输出计算结果

计算模型

Apache Storm

简介

Twitter开源的分布式实时大数据处理框架

组件架构

Nimbus进程，在主节点上运行，负责为集群分发代码，为工作节点分配任务以及监控故障

Supervisor守护进程，运行在工作节点上，监听工作节点，接受Nimbus分配的任务，管理属于自己的worker进程

Spout，一种工作节点，接受源数据

Bolt, 一种工作节点，负责处理输入的数据流

IBM InfoSphere Streams

淘宝银河流数据处理平台

17 | 分布式计算模式之 Actor

定义

Actor

Actor类似于一个“黑盒”对象，封装了自己的状态和行为，是的其它Actor无法直接观察到它的状态，调用它的行为

Actor模型

Actor模型，代表了一种分布式并行计算模型，这种模型有自己的一套规则，规定了Actor的内部计算逻辑，以及多个Actor之间的通信规则

计算模式

模型三要素

状态

Actor组件本身的信息

行为

Actor的计算处理操作

消息

Actor的消息以邮件形式在多个Actor之间通信传递，每个Actor会有一个自己的邮箱，用于接受来自其他Actor的消息

关键特征

实现了更高级的抽象

非阻塞性

无需使用锁

并发度高

易扩展

不足之处

代码重用性小

系统开销大

实现复杂

不适用于对消息处理顺序有严格要求的系统

模型应用

Erlang/OTP

Akka

Quasar(Java)

18 | 分布式计算模式之流水线

定义

流水线技术

计算机中的流水线技术是一种将每条指令拆分为多个步骤，多条指令的不同操作步骤重叠操作，从而实现几条指令并行处理的技术）

流水线计算模式

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

计算模型

TensorFlow
计算流水线

输入流水线

步骤

提取

通过多种途径读取数据，比如内存、本地的HDD或SSD、远程的HDFS、GCS等

转换

使用CPU处理器对输入的数据进行解析以及预处理操作，包括混合重排（shuffling）、批处理（batching）、以及一些特定的转换

加载

将转换后的数据加载到执行机器学习模型的加速器设备上，比如GPU或TPU

原理

当CPU对第N个样本的数据完成预处理后，会将预处理后的数据发送给GPU/TPU，然后CPU继续对第N+1个样本的数据进行预处理，同时GPU/TPU对第N个样本数据进行模型训练

优势

提高 CPU、GPU/TPU 的利用率

加速训练过程

计算学习流水线

步骤

数据输入

数据转换

特征提取

模型训练

模型验证

HTTP流水线传输

计算机图形学中的图流水线

指令流水线

第五站: 分布式数据存储

23 | CAP理论

定义

组成

C(Consistency，一致性)

所有节点在同一时刻的数据是相同的

A(Availability, 可用性)

系统提供的服务一直处于可用状态，对于用户的请求可即使响应

P(Partition Tolerance, 分区容错性)

在分布式系统遇到网络分区的情况下，仍然可以响应用户的请求

内容

在分布式系统中C、A、P这三个特征不能同时满足，只能满足其中两个

选择策略

保CA弃P

特点

在分布式系统中，网络基础设施无法做到始终保证稳定，因此网络分区（网络不连通）难以避免，牺牲分区容错性P，就相当于放弃使用分布式系统

应用场景

单店系统

典型系统

关系型数据库DBMS（比如MySQL，Oracle）

保CP弃A

特点

一个保证CP而舍弃A的分布式系统，一旦发生网络分区会导致数据无法同步，即会牺牲系统的可用性，降低用户体验，知道节点数据达到一致后再响应用户

应用场景

需要很强的数据一致性，或者可以容忍系统长时间无响应的场景

典型系统

ZooKeeper

架构

Zookeeper集群包含多个节点（Server），这些节点会通过ZAB算法选出一个Leader节点

特性

强一致性

当用户向节点发送写请求时，请求会转给Leader

Leader会先向所有的Follower发出一个Proposal

等超过一半的节点同意后，Leader提交这次写操作

弱可用性

当出现网络分区时，再选出下一轮Leader之前，不能正常为用户提供服务

当出现网络分区时，若形成的分区中没有一个分区的节点数大于集群总节点数的一半，那么系统不能正常为用户提供服务，必须待网络恢复后，才能正常提供服务

Redis， HBase......

保AP弃C

特点

一个保证AP而舍弃C的分布式系统，一旦发生网络分区，各个节点之间数据无法马上同步，为了保证高可用，分布式系统需要即刻响应用户的请求

应用场景

需要很高的可用性，或者在网络状况不太好的情况下运行数据暂时不一致的场景

典型系统

CoachDB, Eureka, Cassandra, DynamoDB

24 | 分布式数据存储系统之三要素：顾客、导购与货物

顾客

定义

顾客可以生产和消费数据，相当于分布式存储系统中的应用程序

顾客分类

生产者

给存储系统添加数据

消费者

使用系统中存储的数据

数据分类

结构化数据

数据关联较大、格式固定

半结构化数据

数据之间关系比较简单，有基本固定的结构

非结构化数据

数据之间关联不大，没有固定模式

导购

数据分片

定义

相当于一种导购技术，分布式存储系统按照一定的规则将数据存储到相对应的存储节点中，或者到相对应的存储节点中获取想要的数据

作用

降低单个存储节点的存储和访问压力

快速找到数据所在的存储节点，大大降低搜索延迟，提高用户体验

方法

数据特征分片

数据范围分片

哈希分片

一致性哈希分片

......

数据复制

定义

将数据进行备份，多个节点存储相同的数据

作用

主备方式存储，保证数据的可靠性

货架

定义

货架是用来存储数据的

分类

分布式数据库

作用

通过表格来存储结构化数据

实例

MySQL Sharding、 Microsoft SQL Azure、 Google Spanner、 Alibaba OceanBase......

分布式键值系统

作用

通过键值对来存储半结构化数据，可用作缓存系统

实例

Redis、Memecache......

分布式文件系统

作用

通过文件来存储非结构化数据

实例

Ceph、GFS、HDFS、Swift......

25 | 数据分布方式之哈希与一致性哈希

设计原则

分布均匀性

不同存储节点中存储的数据要尽量均衡，用户的数据访问也要尽量均衡

数据稳定性

当存储节点出现故障需要移除或者扩增时，数据应尽量保持稳定，不要出现大范围的数据迁移

节点异构性

不同存储节点的硬件配置可能差别很大，节点存储的数据要和自己的硬件配置相匹配

隔离故障域

数据尽量存放到不同的故障域，比如不同机房、不同机架

......

哈希

核心思想

根据书籍key值，通过哈希函数计算得到数据对应的存储节点

优缺点

只要哈希函数设置得当，可以很好地保证数据均匀性；有一个较为严重的缺点，就是稳定性较差。

适用场景

适合同类型节点且节点数量比较固定的场景

相关框架

Redis

一致性哈希

核心思想

将存储节点和数据都映射到一个首尾相连的哈希环上，存储节点可以根据IP地址进行哈希，数据通常通过顺时针方向寻找的方式，来确定自己所属的存储节点

优缺点

保证了数据稳定性，但随之而来的均匀性问题也比较明显，即对后继节点的负载会变大

使用场景

适合同类型节点，节点规模会发生变化的场景

相关框架

Cassandra

带有限负载的一致性哈希

核心思想

给每个存储节点设置了一个存储上限值来控制存储节点添加或移除造成的数据不均匀

优缺点

均匀性和稳定性都得到提升，但没有考虑节点异构性问题，还是没有完全做到数据的均匀分布

适用场景

适合同类型节点、节点规模会发生变化的场景

相关框架

Google、Vimeo等公司的负载均衡项目

带虚拟节点的一致性哈希

核心思想

根据每个节点的性能，为每个节点划分不同数量的虚拟节点，并将这些虚拟节点映射到hash环中，再按照一致性哈希算法进行数据映射和存储

优缺点

解决了节点异构性问题，数据的均匀性和稳定性也得到了提升；但引入了虚拟节点，增加了节点规模

适用场景

适合异构节点、节点规模会发生变化的场景

相关框架

Memcached

26 | 分布式数据复制技术

同步复制技术

定义

当用户请求更新数据时，主数据库必须要同步到备数据库之后才可给用户返回，即如果主数据库没有同步到备数据库，用户的更新操作会一直阻塞

特点

保证了数据的强一致性，但牺牲了系统的可用性

适用场景

适用于分布式数据库主备场景或对数据一致性有严格要求的场合，比如金融，交易之类的场景

典型框架

MySQL

异步复制技术

定义

当用户请求更新数据时，主数据库处理完请求后可直接给用户响应，而不必等待备数据库完成同步，即备数据库会异步进行数据的同步，用户的更新操作不会因为备数据库未完成数据同步而导致阻塞

特点

保证了系统的可用性，但牺牲了数据的一致性

适用场景

适用于对用户请求响应时延要求很高的场景

典型框架

MySQL、Redis、Oracle

半同步复制技术

定义

用户发出写请求后，主数据库会执行写操作，并给备数据库发送同步请求，主数据库可以等待一部分备数据库同步完成后响应用户写操作执行成功

常用方案

当主数据库收到多个备数据库中的某一个回复数据同步成功后，便可给用户响应写操作完成

主数据库等超过一半（包括主数据库）回复数据更新成功后，再给用户响应写操作成功

适用场景

多数分布式系统采用半同步复制技术、既能对数据进行保护，又能有效提高系统性能

典型框架

MySQL,Zookeeper, Cloud SQL Server, Etcd, Oracle 等

27 | 分布式数据之缓存数据

定义

缓存技术

指用一个更快的存储设备存储一些经常用到的数据，供用户快速访问

分布式缓存

指在分布式环境或系统下，把一些热门数据存储到离用户近、离应用近的位置，并尽量存储到更快的设备，以减少远程数据传输的延迟，让用户和应用可以很快访问到想要的数据

Redis

集群结构

去中心化结构，每个节点都负责一部分数据的存储，同时，每个节点还可以通过贮备设计来提高可靠性

特性

数据结构

不仅支持简单的 k/v类型，还支持List、Set、Hash等复杂类型的存储

持久化

定义

指将数据从内存这种易失性存储设备中写入磁盘，从而让数据永久保存

实现方式

RDB

定义

Redis会定时将内存中的数据备份到磁盘中，形成一个快照

优缺点

当节点出现故障时，可以根据快照恢复到不同版本的数据，但可能造成数据丢失

AOF

定义

记录下Redis中所有的更新操作

策略

AOF_FSYNC_NO (不同步)

AOF_FSYNC_EVERYSEC (每秒同步)

AOF_FSYNC_ALWAYS (每次写都同步)

优缺点

弥补了RDB数据不一致的问题

主备同步

数据复制技术

异步复制技术

完整重同步

场景

初次同步，即备数据库刚启动时的数据同步

流程

当备服务器启动时，会向主服务器发送SYNC命令

主服务器收到命令后会生成RDB(快照)文件，并记录从现在起新执行的写操作

RDB生成后会发送给备服务器，备服务器通过RDB文件进行数据更新

更新完成后，主服务器再将新纪录的写操作发送给备服务器，备服务器执行完这些新纪录的写操作，便与主服务器的数据保持一致了

部分重同步

场景

因网络故障导致贮备数据库断开连接，待网络恢复后的备数据库的数据同步

实现方式

主备数据库会共同维护一个复制偏移量，这样主数据库就知道应该将哪些写操作发给备数据库，备数据库同步时也知道应该从哪里继续执行操作

Memcached

集群结构

采用一致性哈希的思路，使用的是Ketama算法，主要思想是，带虚拟节点的一致性哈希算法

特性

数据结构

仅支持简单的 k/v 数据类型

持久化

不支持持久化，断电时，Memcached中存储的数据将会全部丢失

主备同步

自身不支持主备，可以通过第三方实现

第七站：分布式核心知识串讲

33 | 以购买火车票的流程串联分布式核心技术

铁路局发布火车票

过程描述

将火车票信息发布到服务器集群进行存储

涉及的知识

存储系统三要素: 顾客、导购与货架

数据分布

数据复制

用户查询火车票

过程描述

用户向服务器发起查询请求，服务器根据用户请求，通过数据索引定位到火车票信息存储的位置，然后获取数据返回给用户

涉及的知识

导购技术

负载均衡和流量控制

故障隔离和故障恢复

用户购买火车票

过程描述

用户购买火车票，服务器进行数据库更新，给用户返回结果

涉及的知识

CAP理论

数据库复制技术

分布式事务与分布式锁

远程调用、消息队列

34 | 搭建一个分布式实验环境