高并发与一致性算法

所有的计算任务都由一台计算机完成，数据的存储也由一台计算机完成

概念

单点故障

IO的瓶颈

内存

性能瓶颈

单节点计算

数据存储历史背景

Redundant Arrays of Independent Disks（ 独立磁盘冗余阵列 ）

将数据存放在多块磁盘解决IO问题

磁盘阵列是由很多块独立的磁盘，组合成一个容量巨大的磁盘组，利用个别磁盘提供数据所产生加成效果提升整个系统效能。利用这项技术，将数据切割成许多区段，分别存放在各个硬盘上。

磁盘阵列还能利用同位检查（Parity Check）的观念，在数组中任意一个硬盘故障时，仍可读出数据， 在数据重构时，将数据经计算后重新置入新硬盘中。

磁盘阵列

分支主题

图解

Raid简介

大多数磁盘系统都对访问次数（每秒的I/O操作，IOPS）和数据传输率（每秒传输的数据量，TPS）有限制。

问题

条带化技术就是将一块连续的数据分成很多小部分并把他们分别存储到不同的磁盘上去。

这就能使多个进程同时访问数据的多个不同部分而不会造成磁盘冲突

在对这种数据进行顺序访问的时候可以获得最大程度上的 I/O 并行能力，从而获得非常好的性能

解决方案

图文

条带化

RAID0具有低成本、高读写性能、100%的高存储空间利用率等优点，但是它不提供数据冗余保护，一旦数据损坏，将无法恢复

RAID0一般适用于对性能要求严格但对数据安全性和可靠性不高的应用，如视频、音频存储、临时数据缓存空间等。

注意

Raid0

RAID1 称为镜像，它将数据完全一致地分别写到工作磁盘和镜像磁盘，它的磁盘空间利用率为50%

RAID1 提供数据写入时，响应时间会有所影响，但是读数据的时候没有影响

RAID1 提供了最佳的数据保护，一旦工作磁盘发生故障，系统自动从镜像磁盘读取数据，不会影响用户工作

Raid1

RAID2 称为纠错海明码磁盘阵列，其设计思想是利用海明码实现数据校验冗余。

如果是 4 位数据宽度需要 4 块数据磁盘和 3 块校验磁盘

如果是 64 位数据宽度需要 64 块 数据磁盘和 7 块校验磁盘。

海明码宽度和校验码计算

海明码的数据冗余开销太大，而且 RAID2 的数据输出性能受阵列中最慢磁盘驱动器的限制。再者，海明码是按位运算， RAID2 数据重建非常耗时。

说明

Raid2

RAID3 是使用专用校验盘的并行访问阵列，它采用一个专用的磁盘作为校验盘，其余磁盘作为数据盘，数据按位可字节的方式交叉存储到各个数据盘中

RAID3 至少需要三块磁盘，不同磁盘上同一带区的数据作 XOR 校验，校验值写入校验盘中

RAID3 完好时读性能与 RAID0 完全一致，并行从多个磁盘条带读取数据，性能非常高，同时还提供了数据容错能力。

RAID3 写入数据时，必须计算与所有同条带的校验值，并将新校验值写入校验盘中

一次写操作包含了写数据块、读取同条带的数据块、计算校验值、写入校验值等多个操作，系统开销非常大，性能较低。

如果 RAID3 中某一磁盘出现故障，不会影响数据读取，可以借助校验数据和其他完好数据来重建数据。

Raid3

RAID4 与 RAID3 的原理大致相同，区别在于条带化的方式不同。

RAID4 按照块的方式来组织数据，写操作只涉及当前数据盘和校验盘两个盘，多个 I/O 请求可以同时得到处理，提高了系统性能。

RAID4 按块存储可以保证单块的完整性，可以避免受到其他磁盘上同条带产生的不利影响。

RAID4 提供了非常好的读性能，但单一的校验盘往往成为系统性能的瓶颈。

数据块也称为存储块，它包含为文件系统分配的其余空间。这些数据块的大小是在创建文件系统时确定的。

缺省情况下，为数据块分配以下两种大小：8 KB 的逻辑块大小和 1 KB 的段大小 (fragmentsize)。

数据块

Raid4

RAID5 应该是目前最常见的RAID等级，它的校验数据分布在阵列中的所有磁盘上，而没有采用专门的校验磁盘

对于数据和校验数据，它们的写操作可以同时发生在完全不同的磁盘上。

RAID5还具备很好的扩展性。当阵列磁盘数量增加时，并行操作量的能力也随之增长

RAID5当一个数据盘损坏时，系统可以根据同一带的其他数据块，和对应的校验数据来重建损坏的数据

重建数据时，RAID5的性能会收到较大的影响

Raid5

RAID6 引入双重校验的概念，它可以保护阵列中同时出现两个磁盘失效时，阵列仍能够继续工作，不会发生数据丢失。

RAID6 不仅要支持数据的恢复，还要支持校验数据的恢复，因此实现代价很高，控制器的设计也比其他等级更复杂、更昂贵。

RAID6 思想最常见的实现方式是采用两个独立的校验算法，假设称为 P 和 Q ，校验数据可以分别存储在两个不同的校验盘上，或者分散存储在所有成员磁盘中。

RAID6 具有快速的读取性能、更高的容错能力。但是，它的成本要高于 RAID5 许多，写性能也较差，并有设计和实施非常复杂。

Raid6

分类

CAP定理是2000年，由 Eric Brewer 提出来的。Brewer认为在分布式的环境下设计和部署系统时，有3个核心的需求，以一种特殊的关系存在

这3个核心的需求是：Consistency，Availability和Partition Tolerance

CAP定理认为：一个提供数据服务的存储系统无法同时满足数据一致性（C）、数据可用性(A)、分区容忍性(P)

定义

一致性，这个和数据库ACID的一致性类似，但这里关注的所有数据节点上的数据一致性和正确性，而数据库的ACID关注的时在一个事务内，对数据的一些约束。

系统在执行过某项操作后仍然处于一致的状态。在分布式系统中，更新操作执行成功后的所有用户都该读取到最新值。

Consistency 一致性

可用性，每一个操作总是能够在一定时间内返回结果。需要注意的是“一定时间”和“返回结果”。

“一定时间”是指系统结果必须在给定时间内返回

“返回结果”系统返回操作成功或失败的结果

Availability 可用性

分区容忍性，是否可以对数据进行分区。这是考虑到性能和可伸缩性。

Partition Tolerance 分区性

不能保证可用性

如果要求对数据进行分区了，就说明节点之间必须进行通信，涉及到通信，就无法保证有限的时间内完成指定的任务

分区性+一致性

不能保证一致性

如果要求两个操作之间要完整的进行，因为设计到通信，肯定存在某一时刻只完成一部分业务的操作，在通信完成的这一段时间内，数据就是不一致性的。

分区性+可用性

失去分区性

使用一个节点很容易就该值达成一致或共识

如果要求保证一致性，那么就必须在通信完成这一段时间内保护数据，是的任何访问这些数据的操作不可用

一致性+可用性

推导图

推导

在大型网站应用中，数据规模总是快速扩张的，因此可伸缩性即分区容忍性必不可少，规模变大以后，机器数量也会变得庞大，这是网络和服务器故障会频繁出现，要想保证应用可用，就必须保证分布式处理系统的高可用性。

在大型网站中，通常会选择强化分布式存储系统的可用性和伸缩性，在某种程度上放弃一致性

结论

CAP原则

一些分布式系统通过赋值数据来提高系统的可靠性和容错性，并且将数据的不同副本存放在不同的机器

在数据有多少份副本的情况下，如果网络、服务器或软件出现故障，会导致部分副本写入成功，部分副本写入失败。这就造成各副本之间的数据不一致，数据内容冲突。

要求无论更新操作在哪一个副本执行，之后所有的读操作都要能获得最新的数据。

强一致性

用户读到某一操作对系统特定数据的更新需要一段时间，我们称这段时间为“不一致性窗口”。

弱一致性

是若一致性的一种特例，保证用户最终能后获取到某操作对系统特定数据的更新

有可能暂时获取的不是最新的数据，但是最终还是能访问到最新的

从客户端来看

数据存储并复制到分布到整个系统超过半数的节点，以保证数据最终一致。

从服务端来看

最终一致性

模型

如果进程A通知进程B它已更新了一个数据项，那么进程B的后续访问将返回更新后的值，且一次写入将保证取代前一次写入。

与进程A无因果关系的进程C的访问，遵守一般的最终一致性规则。

图解：查询微博和评论

因果一致性（Casual Consistency）

当进程A自己更新一个数据项之后，它总是访问到更新过的值，绝不会看到旧值。这既是因果一致性模型的一个特例。

读自己的数据都是从主服务器去读取，读其他人的数据再从从服务器去读取

案例思考：发表微博和修改微博

读己之所写一致性（read-your-writes）

这是上一个模型的实用版本，它把访问存储系统的进程放到会话的上下文中。只要会话还存在，系统就保证“读已之所写”一致性。如果由于某些失败情形令会话终止，就要建立新的会话，而且系统的保证不会延续到新的会话

确保会话内访问都是最新的

会话（Session）一致性

如果进程已经看到过数据对象的某个最新值，那么任何后续访问都不会返回再那个值之前的值。

不会读取最旧的数据

单调（Monotonic）读一致性

系统保证来自同一个进程的写操作顺序执行。要是系统不能保证这种程度的一致性，旧非常难以编程了。

单调写一致性

按照顺序完成数据的书写

数据的一致性

Paxos算法是Leslie Lamport宗师提出的一种基于消息传递的分布式一致性算法，使其获得2013年图灵奖。

Paxos在1990年提出，被广泛应用于分布式计算中，Google的Chubby，Apache的Zookeeper都是基于它的理论来实现的

发展

即一个分布式系统中的各个进程如何就某个值（决议）达成一致

让参与分布式处理的每个参与者逐步达成一致意见

Paxos算法解决的问题是分布式一致性问题

目的

少数服从多数的方式，最终达成一致意见

目标

共享内存（Shared memory)

消息传递（Messagespassing）

传统节点通信存在着两种通信模型：

Paxos是一个基于消息传递的一致性算法

简介

Paxos描述了这样一个场景，有一个叫做Paxos的小岛(Island)上面住了一批居民，岛上面所有的事情 由一些特殊的人决定，他们叫做议员(Senator)。议员的总数(Senator Count)是确定的，不能更 改。岛上每次环境事务的变更都需要通过一个提议(Proposal)，每个提议都有一个编号(PID)，这个编 号是一直增长的，不能倒退。每个提议都需要超过半数((Senator Count)/2 +1)的议员同意才能生 效。每个议员只会同意大于当前编号的提议，包括已生效的和未生效的。如果议员收到小于等于当前编号 的提议，他会拒绝，并告知对方：你的提议已经有人提过了。这里的当前编号是每个议员在自己记事本上 面记录的编号，他不断更新这个编号。整个议会不能保证所有议员记事本上的编号总是相同的。现在议会 有一个目标：保证所有的议员对于提议都能达成一致的看法。

议员及规则描述

现在议会开始运作，所有议员一开始记事本上面记录的编号都是0。有一个议员发了一个提议：将电费设 定为1元/度。他首先看了一下记事本，嗯，当前提议编号是0，那么我的这个提议的编号就是1，于是他 给所有议员发消息：1号提议，设定电费1元/度。其他议员收到消息以后查了一下记事本，哦，当前提议 编号是0，这个提议可接受，于是他记录下这个提议并回复：我接受你的1号提议，同时他在记事本上记 录：当前提议编号为1。发起提议的议员收到了超过半数的回复，立即给所有人发通知：1号提议生效！收 到的议员会修改他的记事本，将1好提议由记录改成正式的法令，当有人问他电费为多少时，他会查看法 令并告诉对方：1元/度。

提出并通过提议

提议冲突解决流程

算法描述

1、小岛（Island）服务器集群

2、议员（Senator）单台服务器

3、议员的总数（Senator Count）是确定的

4、提议（Proposal）每一次对集群中的数据进行修改

5、每个提议都有一个编号（PID），这个编号是一直增长的

6、每个提议都需要超过半数（（Senator Count）/ 2+1 ）的议员统一才能生效

7、每个议员只会同意大于当前编号的提议

8、每个议员在自己记事本上记录的编号，他不断更新这个编号

9、整个议会不能保证所有议员记事本上的编号总是相同的

10、议会有一个目标：保证所有的议员对于提议都能达成一致的看法。

11、前提投票（>1/2），后期广播（all）

数据的全量备份

弱一致性 ——》 最终一致性

12、Paxos算法

Paxos推断

如果Paxos岛上的议员人人平等，在某种情况下会由于提议的冲突而产生一个“活锁”

描述

对于活锁情况，我的理解是大家都没有死，都在动，但一直解决不了冲突问题

无主集群模型

理解

提出新的角色：总统

Paxos的作者在所有的议员中设立一个总统，只有总统有权发出提议，如果议员有自己的提议，必须发给总统并由总统来提出。

解决了提议编号和同步问题

成果

屁民甲(Client)到某个议员(ZK Server)那里询问(Get)某条法令的情况(ZNode的数据)，议员毫 不犹豫的拿出他的记事本(local storage)，查阅法令并告诉他结果，同时声明：我的数据不一定是最新 的。你想要最新的数据？没问题，等着，等我找总统Sync一下再告诉你。

情况一

情况二：屁民乙(Client)到某个议员(ZK Server)那里要求政府归还欠他的一万元钱，议员让他在办公室等 着，自己将问题反映给了总统，总统询问所有议员的意见，多数议员表示欠屁民的钱一定要还，于是总统发表 声明，从国库中拿出一万元还债，国库总资产由100万变成99万。屁民乙拿到钱回去了(Client函数返回)。

情况二

情况三：总统突然挂了，议员接二连三的发现联系不上总统，于是各自发表声明，推选新的总统，总统大选期 间政府停业，拒绝屁民的请求。

情况三

情景

情景延伸

人人都会发送指令，投票

6个节点 ，33对立

类似于以前党争

投票人数可能导致分区（分不同阵营）

提议的编号不能重复和小于

事务编号混乱，每个节点都有可能有自己的提议

只能有一个主发送指令，发送提议

重新选举

切换到备用节点

单主会单点故障，肯定有备用的方案

如果存在多个主就会脑裂

有主集群模型

主要集群中节点数目高于 1/2+1 ，集群就可以正常运行

模型延伸

算法模型延伸

Paxos算法

Raft 适用于一个管理日志一致性的协议，相比 Paxos 协议 Raft 更容易理解和实现它。

Raft 将一致性算法分成了几个部分，包括领导选举（leader selection）、日志复制（log replication）、安全（safety）

http://thesecretlivesofdata.com/raft/

官网

维护多个副本的一致性

分布式存储系统通过维护多个副本来提高系统的availability可用性，难点在于分布式存储系统的核心问题

一组server从相同的初始状态起，按相同的顺序执行相同的命令，最终会达到 一致的状态

一组server记录相同的操作日志，并以相同的顺序应用到状态机

Raft协议基于复制状态机（replicated state machine）

每台机器保存一份日志，日志来自于客户端的请求，包含一系列的命令，状态机会按照顺序执行这些命令

Raft有一个明确的场景，就是管理复制日志的一致性

负责 Client 交互和 log 复制，同一时刻，系统中最多存在1个。

Leader 领导者

被动响应请求 RPC ，从不主动发起请求 RPC

Follower 跟随者

一种临时的角色，只存在于 leader 的选举阶段，某个节点想要编程 leader ，那么就发起投票请求，同时自己变成 candidate

Candidate 候选者

Raft 算法将Server划分为3中状态，或者也可以称为角色

角色分配

Term 的概念类比中国历史上的朝代更替， Raft 算法将时间划分成为任意不同长度的任期（term）。

任期用连续的数字进行标识。

每一个任期的开始都是一次选举（election），一个或多个候选人会试图成为领导人。

如果一个候选人赢得了选举，它就会在该任期的剩余时间担任领导人。

在某种情况下，选票会被瓜分，有可能没有选举出领导人，那么，就会开启另一个任期，并且立刻开启下一次选举。

Raft 算法保证在给定的一个任期最多只有一个领导人

Term

Raft 算法中服务器节点之间通信使用远程过程调用（RPCs）

子主题 2

基本的一致性算法只需要两种类型的 RPCs，为了在服务器之间传输快照增加了第三种 RPC。

候选人在选举期间发起

RequestVote RPC

领导人发起的一种心跳机制，复制日志也在该命令中完成

AppendEntries RPC

领导者使用该RPC来发送快照给太落后的追随者

InstallSnapshot RPC

三种RPC

RPC

主要用于保证节点的一致性，这阶段所做的操作也是为了保证一致性与高可用性。

日志复制（Log Replication）就是为了保证执行相同的操作序列所做的工作。

作用

1、当Leader选举出来后便开始负责客户端的请求，所有事务（更新操作）请求都必须先经过Leader处理

2、在Raft中当接收到客户端的日志（事务请求）后先把该日志追加到本地的Log中

3、然后通过heartbeat心跳机制把该Entry同步给其他Follower，Follower接收到日志后记录日志然后向Leader发送ACK

4、当Leader收到大多数（n/2+1）Follower的ACK信息后将该日志设置为已提交并追加到本地磁盘中

5、通知客户端并在下个heartbeat中Leader将通知所有的Follower将该日志存储在自己的本地磁盘中。

流程

日志复制（Log Replication）

算法流程

Raft算法

高并发与一致性算法