分布式理论
分布式概述
什么是分布式
分布式系统是计算机程序的集合，这些程序利用跨多个独立计算机点的计算资源来实现共同的目标。可以分为分布式计算、分布式存储、分布式数据库等
| 优势 | 挑战 |
| 去中心化 | 普遍的节点故障 |
| 低成本 | 不可靠的网络 |
| 弹性 | 异构的机器于硬件环境 |
| 资源共享 | 安全 |
| 可靠性高 |
常见的分布式系统
- 分布式存储
- GFS：Google分布式文件系统
- Ceph：统一的分布式存储系统
- Zookeeper：分布式数据管理与系统协调框架
- 分布式数据库
- MongoDB：文档数据库
- TiDB
- HBase
- 分布式计算
- Hadoop：基于MapReduce分布式计算框架
- Spark
系统模型
故障模型
- Byzantine failure：节点可以任意篡改发送给其他节点的数据（最难处理的情况）
- ADB：Byzantine failure的一个特例，节点可以篡改数据，但不能伪造其它节点的数据 [内存故障]
- Performance failure：节点未在特定时间段内收集到数据 [线缆故障]
- Omission failure：节点收不到数据 [线缆故障]
- Crash failure：在Omission failure基础上，增加节点停止响应的假设 [服务器主板故障]
- Fail-stop failure：在Crash failure基础上增加了错误可检测的假设 [磁盘故障]
共识和一致性
一致性是指分布式系统中的多个服务节点，给定一系列的操作，在约定协议的保障下，使它们对外界呈现的状态是一致的。换句话说，也就是保证集群中所有服务节点中的数据完全相同并且能够对某个提案（Proposal）达成一致。
共识性描述了分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程。 在实践中，要保障系统满足不同程度的一致性，核心过程往往需要通过共识算法来达成。
一致性往往指分布式系统中多个副本对外呈现的数据的状态。如顺序一致性、线性一致性，描述了多个节点对数据状态的维护能力。
共识性则描述了分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程。
因此，一致性描述的是结果状态，共识则是一种手段。达成某种共识并不意味着就保障了一致性（这里的一致性指强一致性）。只能说共识机制，能够实现某种程度上的一致性。
实践中，要保障系统满足不同程度的一致性，核心过程往往需要通过共识算法来达成。
扩展阅读：拜占庭将军问题 (The Byzantine Generals Problem) - 知乎 (zhihu.com)
时间和事件顺序
分布式系统的一些场景也需要记录和比较不同节点间事件发生的顺序，但不同于日常生活使用物理时钟记录时间，分布式系统使用逻辑时钟记录事件顺序关系
Lamport逻辑时钟
对于每一个节点Pi我们定义时钟Ci为一个函数，它为任意的事件a赋值编号为Ci(a)
- 如果a和b是相同节点Pi上的两个事件，a在b之前发生，则有Ci(a)<Ci(b)
- 如果事件a表示节点Pi发送某条消息，b表示节点Pj接收这条消息，则有Ci(a)<Cj(b)
于是就可以在时空图中加入类似图2-1虚线所示的tick line。
利用逻辑时钟，我们可以对整个系统中的事件进行全序排序
理论基础
CAP理论
| C（一致性） | 指数据在多个副本之间能够保持一致的特性 |
| A（可用性） | 指系统提供的服务必须一直处于可用的状态，每次请求能获得非错的响应 |
| P（分区容错性） | 分布式系统在遇到任何网络分区故障的时候，仍然能对外提供满足一致性和可用性的服务 |
- CA：放弃分区容错，传统单机数据库的选择
- AP：放弃一致性（强一致性），如注重用户体验的系统
- CP：放弃可用性，例如钱财安全相关的系统
但是永远无法同时满足CAP。
ACID理论
事务是数据库系统中的一个重要概念，是数据库管理系统执行过程中的一个逻辑单位，保证一个事务中的所有操作要么全部执行，要么不执行。事务拥有四个特性：
| 原子性 | 事务中包含的各操作要么都做，要么都不做 |
| 一致性 | 事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。 |
| 隔离性 | 一个事务的执行不能其它事务干扰。即一个事务内部的操作及使用的数据对其它并发事务是隔离的，并发执行的各个事务之间不能互相干扰。 |
| 持久性 | 指一个事务一旦提交，它对数据库中的数据的改变就应该是永久性的。接下来的其它操作或故障不应该对其执行结果有任何影响。 |
BASE理论
Base理论是对可用性和一致性的权衡的结果，基于CAP逐渐演化而来。（看视频后感觉分布式数据库中使用BASE理论是ACID中的I隔离性在复杂分布式环境下的一种妥协）
其核心思想是：
| Basically Available | 假设系统出现了不可预知的故障，但还是可以用。对于正常系统来说，增加了响应时间 |
| Soft state | 数据同步允许一定的延迟 |
| Eventually consistent | 系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态，不要求实时。 |
分布式事务
二阶段提交
二阶段提交：为了使基于分布式系统架构下的节点在进行事务提交时保持一致性而设计的一种演算法。
- 在分布式系统中，为了让每个节点都能够感知到其他节点的事务执行状况，需要引入一个中心节点来统一处理所有节点的执行逻辑，这个中心节点叫做协调者（coordinator），被中心节点调度的其他业务节点叫做参与者（participant）。
- 所有节点都采用预写式日志，且日志被写入后即被保持在可靠的储存设备上
- 所有节点不会永久性损坏。
可能出现的情况：
- C不宕机，P宕机，需要进行回滚
- C宕机，P不宕机。可以起新的协调者，待查询状态后，重复二阶段提交
- C宕机，P宕机。需要数据库管理员介入，防止数据库进入一个不一致的状态
需要注意的问题：
- 性能问题
- 协调者单点故障问题
- 网络分区带来的数据不一致
三阶段提交
三阶段提交相较于二阶段提交，将二阶段提交中的Prepare阶段拆分成了CanCommit和PreCommit机制。
解决了单点故障问题和阻塞问题，同时引入了超时机制，在等待超时之后，会继续进行事务的提交
MVCC
MVCC，即Multi-Version Concurrency Control （多版本并发控制）。它是一种并发控制的方法，维持一个数据的多个版本使读写操作没有冲突。所以既不会阻塞写，也不会阻塞读。提高并发性能，解决脏读问题。
数据库隔离级别读已提交、可重复读 都是基于MVCC实现的，相对于加锁（乐观锁和悲观锁）简单粗暴的方式，它用更好的方式去处理读写冲突，能有效提高数据库并发性能。
共识协议
Quorum NWR模型
N：在分布式存储系统中，有多少备份数据
W：代表一次成功的更新操作要求至少有W份数据写入成功
R：代表一次成功的读数据操作要求至少有R份数据成功读取
为了保证强一致性，需要保证W+R>N。当 W + R < N 的时候，对于客户端来讲，整个系统只能保证最终一致性，可能会返回旧数据。
RAFT协议
起源于 2013 年 斯坦福 Diego Ongaro和John Ousterhout的论文《In Search of an Understandable Consensus Algorithm》
RAFT协议是一种分布式一致性算法，即使出现部分节点故障，网络延时等情况，也不影响各节点，进而提高系统的整体可用性。
在Raft集群里，服务器可能会是这三种身份其中一个：
- Leader(领袖者)：所有请求的处理者，Leader 接受 client的更新请求，本地处理后再同步至多个其他节点；
- Follower(追随者) ：请求的被动更新者，从Leader接受更新请求，然后写入本地日志文件
- Candidate(候选人) ：节点处于候选状态，正在竞选 Leader。
Log：节点之间同步的信息，以止追加写的方式进行同步，解决了数据被覆盖的问题
Term：单调递增，每个Term内最多只有一个Leader
Committed：日志被复制到多数派节点，即可认为已经被提交了
Applied：日志被应用到本地状态机，执行了log中命令，修改了内存状态
Leader选举过程：
- 初始化全部为Follower
- Current Term +1
- 向其它参与者发起RequestVote请求，retry直到
- 收到多数派请求，成为Leader，并发送心跳
- 收到其它Leader的请求，转为Follower，更新自己的Term
- 收到部分，但未达到多数派，选举超时，随机timeout开始下一轮
说人话就是在一个任期内，每个参与者最多投一票。要成为Leader，必须拿到多数投票。
Log Replication过程：
新Leader产生，Leader和Follower不同步，leader会强制覆盖Follower的不同步的日志。
- Leader收到写请求W
- 将W写到本地log
- 向其它Follower发起AppendEntries RPC
- 等待多数派回复
- 更新本地状态机，返回给客户端
- 下一个心跳通知Follower上一个log已经被Committed了
- Follower也根据命令应用本地状态机
- Follower有问题，Leader会一直retry
当leader出现问题，就需要重新选举：
- Leader发现失去Follower的响应，失去了Leader身份
- 两个Follower之间一段时间未收到心跳，重新进行选举，产生新的Leader，发生切主
- Leader自杀重启，以Follower身份加入
在发生Leader切换，older leader收到了读请求，如果直接响应，可能会有Stale read，解决方案如下：
- 读操作在leader timeout内，默认自己是leader；不是则发起一次heartbeat。等待Commit index应用到状态机。
- Election timeout>lease timeout：在新的leader上任后，自从上次心跳之后一定超过了Election timeout，旧leader大概率能够发现自己的lease过期。
空空如也！