首页  思维导图  详情

高并发与一致性算法

2021-11-11 23:24:22   0  举报





AI智能生成

数据存储历史背景、磁盘阵列、CAP原则、数据的一致性、Paxos算法、Raft算法

redis

最终一致性

高并发与高可用

易于理解的paxos分布式一致性选举算法

作者其他创作

大纲/内容

数据存储历史背景

概念

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

单节点计算

单点故障

性能瓶颈

IO的瓶颈

内存

磁盘阵列

Raid简介

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

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

磁盘阵列

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

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

图解

分支主题

条带化

问题

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

解决方案

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

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

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

图文

分支主题

分类

Raid0

注意

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

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

图解

分支主题

Raid1

注意

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

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

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

图解

分支主题

Raid2

说明

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

海明码是一种在原始数据中加入若干校验码来进行错误检测和纠正的编码技术，其中第 2n 位（ 1,2, 4, 8, … ）是校验码，其他位置是数据码

海明码宽度和校验码计算

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

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

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

图解

分支主题

Raid3

说明

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

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

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

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

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

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

图解

分支主题

Raid4

说明

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

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

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

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

数据块

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

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

图解

分支主题

Raid5

注意

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

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

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

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

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

图解

分支主题

Raid6

注意

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

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

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

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

图解

分支主题

图解

分支主题

CAP原则

定义

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

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

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

图文

分支主题

概念

Consistency 一致性

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

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

Availability 可用性

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

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

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

Partition Tolerance 分区性

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

推导

分区性+一致性

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

不能保证可用性

分区性+可用性

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

不能保证一致性

一致性+可用性

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

失去分区性

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

推导图

分支主题

结论

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

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

图解

分支主题

数据的一致性

定义

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

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

模型

强一致性

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

弱一致性

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

最终一致性

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

从客户端来看

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

从服务端来看

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

最终一致性

分类

因果一致性（Casual Consistency）

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

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

图解：查询微博和评论

分支主题

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

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

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

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

会话（Session）一致性

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

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

单调（Monotonic）读一致性

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

不会读取最旧的数据

单调写一致性

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

图解

按照顺序完成数据的书写

分支主题

图解

分支主题

Paxos算法

简介

发展

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元/度。

提议冲突解决流程

现在看冲突的解决：假设总共有三个议员S1-S3，S1和S2同时发起了一个提议:1号提议，设定电费。S1 想设为1元/度, S2想设为2元/度。结果S3先收到了S1的提议，于是他做了和前面同样的操作。紧接着他又收到了S2的提议，结果他一查记事本，咦，这个提议的编号小于等于我的当前编号1，于是他拒绝了这个提议：对不起，这个提议先前提过了。于是S2的提议被拒绝，S1正式发布了提议: 1号提议生效。S2 向S1或者S3打听并更新了1号法令的内容，然后他可以选择继续发起2号提议。

Paxos推断

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的作者在所有的议员中设立一个总统，只有总统有权发出提议，如果议员有自己的提议，必须发给总统并由总统来提出。

成果

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

图解

分支主题

情景

情况一

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

情况二

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

情况三

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

模型延伸

无主集群模型

说明

人人都会发送指令，投票

问题

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

6个节点，33对立

类似于以前党争

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

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