分布式理论思维导图模板_ProcessOn思维导图、流程图

CAP

consistence

一致性

avaliable

可用性

partition tolerance

分区容错

三者得其二

CP

如 zk etcd hbase 最终一致性顺序一致性 放弃可用性，保证强一致性， 在数据同步时，其余结点均不可用  因为为了防止数据不一致，集群将拒绝新数据的写入

AP

保证高可用，任意时刻结点都可用，但是可能会有 相应数据不一致的问题

AC

单体应用

思考

因为分布式系统一般取CP，或者AP，如果取CP， 那么假设可能系统中99.9%的时间都OK，此时三台机，整体可用性 约为99.7%，一个月可能有100+分钟不可用，所以一般选用ap

BASE

base理论是 对AP的延伸

Basically Available 基本可用

解释

系统出现不可预知的故障/错误时保障核心功能的可用， 损失部分功能可用性，抛弃部分边际功能

通知牺牲部分功能的可用性，保障核心功能的可用性

手段

流量削峰

请求排队

服务降级

服务熔断

soft-state 软状态

实现最终一致性的一种过渡状态 允许不同节点数据存在短暂的不一致，然后一致

eventually Consistente 最终一致性

解释

即时无法做到强一致性，也应该根据自身业务的特点， 在一定的时延之后最终到达数据一致性，

强一致性大致可以理解为无延时的最终一致性 几乎所有互联网系统都采用的一致性

手段

读时修复

读取时不一致，修复

写时修复

写入时，不一致修复

异步修复

定时修复

如果不是必须的话，不推荐实现强一致性或者事务，鼓励可用性和性能优先 根据业务特点，来实现基本可用，并完成最终一致性

PAXOS

三个角色

proposer 提议者

acceptor 接受者

learner 学习者

实际中一台机可能有三个角色

basic paxos

准备阶段

每个提议者发起一个prepare提案，带编号的值[m,v]给大多数acceptor

接受者没有收到过prepare请求，则接受此提案，并承诺不在接受小于编号m的提案

如果prepare当前编号小于曾接受的最大编号，则直接忽略

如果prepare请求M大于曾接受的最大编号，返回已接受的最大编号，并承诺不接受小于M的编号

批准阶段

如果提议者收到了大多数acceptor对[m,v]的回应，就向大多数acceptor发送accept请求

如果acceptor收到了[m,v]的accept提案,则批准该提案

multi paxos

引入leader，省略准备阶段，领导者作为唯一proposer

RAFT

三角色

follower

leader

candidate

动态图

http://thesecretlivesofdata.com/raft/

流程

leader election

系统中所有的节点都已follower开始(并自带一个随机的超时时间)， 如果超时时间内未收到leader的rpc通信，那么最先发现的那个会变为candidate, 增加自己的任期编号n，然后向其余的foller发送请求，期望获取选票

其它节点如果在任期n内未进行投票，则会将选票投给候选者，并设置自己的任期编号

候选者收到大部分的选票后，将自己设置为leader，然后向其余 的follower发送rpc消息，我是leader，你们不要自己开始选举

log replication

在raft中，数据是以日志形式存在的，写数据先写leader，然后写日志到follower，最后写数据

日志项，包括数据data,索引index，以及任期term

日志复制

leader通过日志复制RPC消息(appendentries)，将日志复制到follower

leader接受到客户端写请求后，创建新日志项，并附加到本地日志

follower接受到心跳，或者appednentry后，如果发现leader提交了日志，但是自己还未应用，就应用日志到本地记录

日志复制的过程，写入数据到节点时，leader会写日志，然后将日志以rpc形式发送至follower 如果接受到大部分follower的成功响应，就会返回成功至客户端，反之失败

一致性校验

日志记录如图：

流程

通过appendentries往follower发送最新日志，包括term,index,data term：任期，index此条数据所在下标，data下标

follower发现如果找不到，index,term对应的数据，说明数据不一致，返回数据给leader

leader接收失败消息，递减index，发送命令给follower,

follower找到了index，term一致的数据，就变更本地日志，发送成功给leader， 此时leader继续进行appendentries流程，直到所有日志完全同步

gossip

简介

Gossip 协议，顾名思义，就像流言蜚语一样，利用一种随机、带有传染性的方式， 将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。

方式

直接邮寄 Direct Mail

直接发送信息，当信息发送失败，缓存信息，重新发送

实现建档，同步及时，可能由于缓存队列满了，数据不一致，最终一致性无法保证

反熵 Anti-entropy

熵是体系混乱程度，反熵意味着消除混乱

推

nodeA的数据，全部给nodeB,修复B的熵

拉

A 仅将数据 key, version 推送给 B，B 将本地比 A 新的数据 （Key, value, version）推送给 A，A 更新本地

推拉结合

A把k version给B，b把大于version的数据给A，A更新后 在将本地比B新的数据给A

结点已知才可以操作，动态节点，或者节点太多，不适用

谣言传播 

Rumor mongering

散播过程

Gossip 是周期性的散播消息，把周期限定为 1 秒

被感染节点随机选择 k 个邻接节点（fan-out）散播消息， 这里把 fan-out 设置为 3，每次最多往 3 个节点散播。

每次散播消息都选择尚未发送过的节点进行散播

收到消息的节点不再往发送节点散播，比如 A -> B，那么 B 进行散播的时候，不再发给 A

Gossip 过程是异步的，发出去就不管了， 异步是它的优点，而消息冗余则是它的缺点。

https://zhuanlan.zhihu.com/p/41228196

quorum NWR

AP 型系统缺乏强一致性的痛点，给业务提供了按需选择一致性级别的灵活 Quorum NWR实现自定义一致性级别，比如Elasticsearch，就支持“any、one、quorum、all”4 种写一致性级别

N 副本个数，W 写一致性，R读一致性

要求

W+R>N

W>N/2 写入的时候，如果写入的副本个数>N/2 就可以不用写了，剩下的交给服务器自动同步

R>N-W 读取的时候如果 R>N-w 则肯定会读取到一个最新的值，将版本最高的返回就可以了

https://blog.csdn.net/bigtree_3721/article/details/76805103

共识问题

BFT

Byzantine Fault Tolerance

在存在恶意节点行为的场景中（比如区块链技术）

两忠一叛

假设存在恶意结点，举例，三位将军

C撤退 B叛徒 A 进攻  A-》c 进攻 B-》c 撤退 B-》a 进攻 C-》a进攻 C撤退 B撤退 A进攻 A被出卖

口信消息

最终实现共进退

如果叛将人数为 m，则将军总人数不能少于 3m + 1 ，此时需要进行m+1轮协商， 那么拜占庭将军问题就可以解决。

签名消息

Leader发送消息，所有follower接受广播

恶意结点发送消息，如果跟leader广播不同，则直接忽略

恶意结点先发送消息，则在等待一定时间后对锁收到指令选择一个执行

CFT

Crash Fault Tolerance

而在分布式系统中，最常用的是故障容错算法 解决不存在恶意结点伪造消息，解决网络丢消息问题

PBFT？？？？？

第一个接收消息的节点变成leader执行三阶段提交

pre-prepare 预准备，构造预准备消息发送广播给所有follower节点

准备阶段，所有follower收到预准备消息后，构造准备消息广播给其它节点

子主题

POW

proof of work工作量证明算法

比如对一个基准字符串，补位后使用sha256计算出前四位为0的时候就算通过

ZAB？？？

角色

Looking、Following、Leading

为每一个请求生成一个proposal, 并为每一个事务生成全局唯一ID：ZXID：64位数字

低32位 leaderid 递增计数器

高32位代表leader任期epoch

新产生leader，会在leader服务器找到ZXID,对leaderid从0开始。epoch+1

Zab 协议通过 epoch 编号来区分 Leader 变化周期，能够有效避免不同的 Leader 错误的使用了相同的 zxid 编号提出了不一样的 Proposal 的异常情况。

leader选举

选epoch最大的

epoch相等，选zxid最大的

epoch 和 zxid 相等，选择 server_id 最大的（zoo.cfg中的myid）

？？？

2PC

流程

投票阶段

协调者发起请求，等待参与者响应，都响应yes可以提交， 有no表明此次事务无法提交，网络超时自动为no

提交阶段

协调者收到所有参与者的yes响应，则表示可以开始提交事务 协调者向参与者发起提交请求，所有参与者必须保证事务提交成功

若有一个参与者响应no，则协调者发起回滚请求，所有参与者回滚操作

节点

coodinator 事务协调者

participant、cohort 事务参与者

优点

强一致性，因为一阶段预留了资源，所有只要节点或者网络最终恢复正常，协议就能保证二阶段执行成功

业界标准支持，二阶段协议在业界有标准规范——XA 规范 许多数据库和框架都有针对XA规范的分布式事务实现。

缺点

在第一阶段要预留资源，资源预留期间，其他人无法操作，降低了心痛吞吐量

容错较差，如果某节点超时/宕机，只能不断重试，导致事务冲突死锁概率增加 可能成为系统水平扩容的瓶颈

3PC

不好用。使用更多的消息进行协商，增加系统负载和响应延迟，很少被使用，

询问阶段

cancommit

协调者向参与者发送cancommit请求，参与者如果可以提交就响应yes ，反之no，这样尽早发现无法执行的参与者，提高效率

准备阶段

PreCommit

若所有协调者收到了所有参与者的yes响应，就发送预执行指令 precommit, 参与者接收到preCommit请求后，会执行事务操作，并将Undo和Redo信息记录到事务日志中

参与者成功执行了事务咋发送ACK给协调者 并等待最终指令 commit / abort(终止)

协调者收到任意一个no响应，或者等待超时都会发出abort请求 参与者收到abort或者等到协调者超时都会中断事务

提交阶段

执行提交

协调者收到所有参与者的ack发起docommit请求 参与者收到dommit请求，会正式执行事务，并释放资源 参与者执行完毕，发送ack给协调者，协调者收到ack，事务执行完毕 若二阶段参与者响应ack，但等待docommit超时同样会执行事务

中断

协调者收到任意no响应或者等到超时都会发起abort请求 参与者收到abort会利用二阶段中的undo做事务回滚，回滚完成释放资源

参与者完成回滚，发送ack给协调者， 协调者收到ack，终止事务

询问以及超时，降低了资源阻塞 三阶段提交协议最大的优点就是降低了参与者的阻塞范围

参与者接收到preCommit消息后，如果网络发生分区，无法收到协调者响应 但此时协调者收到了abort请求，则此参与者同样执行事务，会导致数据不一致

TCC

try 

此阶段对资源进行锁定/预留

commit

执行业务操作，不做检查，使用try阶段的预留资源，confirm需要有幂等性,失败要重试

cancel

任何服务/业务方法出错，此处需要补偿(回滚)，释放try阶段资源，cancle需要幂等，失败要重试

针对每一个操作，都注册一个与之对应的确认和补偿(撤销)操作

利用中间状态实现

可靠消息最终一致性方案

实现方式

基于本地消息表

基于支持分布式事务的消息中间件

利用状态字段实现

本地消息表

可靠消息服务

单独服务有自己的数据库，主要用来存储消息

状态

待确认

已发送

已取消

已完成

防止网络失败，上游服务发送了取消或者确认，但是未传递到消息服务 增加定时任务，调用上游接口获取消息最终状态

上游服务(生产者)

发送half-msg给消息服务，消息服务落盘

<ol><li>生产者执行本地事务，成功发确认给消息服务，失败给小服务发送取消消息</li></ol>

消息服务受到消息，更改状态已发送，已取消

下游服务(消费者)

保证幂等性，防止多次消费

消费成功后，发送消息给消息服务，变更状态为已完成

防止因为网络问题，消费成功凡是状态未变更，增加定时任务。 检查已发送但未完成的消息，然后再次投递给消息队列，下游重新消费

流程：上游(生产)->消息服务(中间服务落盘)->消息队列(存储消息加速消费)->下游(消费)

rocketmq

prepare

生产者发送halfmsg到消息中间件，中间件生成唯一id

生产者执行本地事务

确认

生产者执行成功，发送commit给消息中间件， 中间件修改半消息状态为已完成，通知消费者执行事务

消费者无法立即消费halfmsg,只有commit了 halfmsg，消费者才可以消费

如果生产者执行本地事务失败，就向消息中间件发送一个Rollback消息 （包含之前HalfMsg的唯一标识），中间件修改HalfMsg的状态为【已取消】。

ACK机制

消费者消费消息，可能因为自身机制业务问题，消费失败， 消费者有ack机制，只有消费业务成功返回ack， 消息中间件才会更新消息的状态为已消费

数据分片

一致性hash

https://www.zsythink.net/archives/1182

过程

一个包含了0~2^32-1的环

这个和计算机的存储有关系，一个字节有8位，就有2的八次方种排序。四个字节的话就是2的32次方

ipv4总共有4位，保证能均匀分布

对服务器ip做hash,hash之后对环大小取模，服务器映射在环上的某一个位置

存储时，对文件名hash.对环大小取模，然后顺时针方向找最近的服务器，存入

Hash(“202.168.14.241”);

优缺点

此种模式，可能会出现资源倾斜，所有的资源都集中在一个服务器上

服务器的上下线，宕机，不会影响资源的存储

虚拟节点

解决资源倾斜的问题

根据真实服务器，复制出虚拟节点，这样，节点分布平均，资源能相对均衡的分布

虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式 物理节点与虚拟节点的映射，可以采用服务器ip或主机名的后面增加编号的方式

Hash(“202.168.14.241#1”); Hash(“202.168.14.241#2”);

range based

将整个hash值控件分成不相交的片段，每个物理节点负责其中某写片段

如redis，分为0-16583个槽，每个节点负责一定数量的槽，完成集群 使用哈希槽的好处就在于可以方便的添加或移除节点。 当需要移除节点时，只需要把移除节点上的哈希槽挪到其他节点就行了

全局流水号

要求

分布式系统全局唯一

递增

实现

数据库

，自增主键id,业务类型type

分布式系统中，可以设置不同的库，不同的起点，和增长步长 A： 1 incr 2   2 incr

snowflake

SnowFlake的结构如下(每部分用-分开) 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0

41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)

10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId

12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号

加起来刚好64位，为一个Long型，每S大概400W ID

高可用

master-salve

方式

主备

主机读写，备机做故障转移

备机硬件浪费，需要人工切换

主从

主写从读

主从通信，客户端感知主从。主从延迟

主主

双主机数据复制

分布式id问题

双机切换 故障切换

互连式

主备建立状态连接

互连式模式下，为了切换后不影响客户端的访问，主机和备机之间通常共享一个对客户端来说唯一的地址，例如虚拟IP，主机需要绑定这个虚拟的IP；或者客户端同时记录主/备机的地址，哪个能访问就访问哪个，只不过备机虽然能收到客户端的操作请求，但是会直接拒绝

中介式

主备机之间不直接连接，而是都去连接中介，并且通过中介来传递状态信息

比如Keepalived、ZooKeeper，都可以作为中介，并且可以通过选举算法来保证自身的高可用。

模拟式

模拟式指主/备机之间并不传递任何状态数据，而是备机模拟成一个客户端， 向主机发起模拟的读写操作，根据读写操作的响应情况来判断主机的状态

集群

数据分散集群

客户端可以向任意节点读/写数据

由于其良好的可伸缩性，适合业务数据量巨大、集群机器数量庞大的业务场景。例如，Hadoop集群、HBase集群，大规模的集群可以达到上百台甚至上千台服务器

数据集中集群

客户端只能将数据写到主机

数据集中集群适合数据量不大，集群机器数量不多的场景。例如，ZooKeeper集群，一般推荐5台机器左右，数据量是单台服务器就能够完全支撑的；

降级/熔断/限流

降级

通过开关启停功能，让核心服务可用，非核心功能停止

熔断

限流

请求限流

令牌桶

按固定速率往桶里放令牌，桶满了，就不放了 有请求，就取走令牌。请求拿不到令牌就直接返回

可以应对一定的突发流量

漏桶

限制总量/限制时间量

资源限流

排队限流

读写分离

分库分表

分表

范围路由，0-1000000  1000000-2000000

hash路由 id%10

配置路由

就是用一张独立的路由表来记录原表到子表的路由信息

以用户 ID 为例，我们新增一张 userrouter 表，这个表包含 userid 和 tableid 两列，根据 userid 就可以查询对应的 table_id

使用灵活，但是增加了一次查询

join

业务join

count

count+

增加记录数表

分库

跨库join,中间件

分布式事务

迁移

停机迁移

双写迁移

新数据双写，增删改，同时写新库和旧库

由于新库数据差太远，可以用一个自己写的导数工具，读取老库数据并写到新库中。写到新库时，首先判断新库中是否已有该条记录，没有则写入，有的话判断这条记录最后修改时间（标准规范的表结构设计中，都会包含一个最后修改时间字段），如果老库中的记录更加新，则覆盖新库中的记录

动态伸缩

高性能

分布式缓存

负载均衡

DNS轮询

子主题

lvs nginx

负载均衡算法

服务

轮询

权重

负载最低优先

LVS这种4层网络负载均衡设备，可以以“连接数”来判断服务器的状态，服务器连接数越大，表明服务器压力越大；

Nginx这种7层网络负载系统，可以以“HTTP请求数”来判断服务器状态（Nginx内置的负载均衡算法不支持这种方式，需要进行扩展

hash

iphash

业务id hash,比如sessionId hash

客户端

性能优先算法，客户端看哪个的响应最快

需要做服务响应采样

消息中间件

可用性

幂等性

消息丢失

生产者投递

rabbit,confirm机制

kafka,设置 ack = all leader接收消息，follower全部同步成功才算成功

消息队列存储

mq自身故障，自身HA机制，重选leader

消费者消费

消费者手动提交offset

有序消费

rabbit指定queue

kafka

显式指定partition

不指定partition，指定key：根据key的hash值与分区数进行运算，确定发送到哪个partition分区

无序 不指定partition，不指定key：轮询各分区发送

内存队列

消息积压

消息太多，就新建大批量消费者消费

磁盘问题，就消费之后写入别的队列，先把磁盘让出来

搜索引擎

子主题