Hermethus
2021/04/01
0
来自 头疼
约 8232 字
原创
最近更新： 2021/11/03 23:51

分布式系统笔记

系列目录

计算机通信网络学习笔记

操作系统学习笔记

数据库基础 - MySQL

分布式系统学习笔记

CAP理论

一个分布式系统最多只能同时满足

  • 一致性（Consistency）：总能保证读到的数据是最新的数据。需要保证所有节点随时更新到最新数据。

  • 可用性（Availability）：保证服务的可用，不出现失败或者超时等情况。

  • 分区容错性（Partition tolerance）：当分布式系统中节点的通信出现故障，依旧能提供具有一致性和可用性的服务。

这三项中的两项。

原因分析

核心原因是故障不可避免，此时如果要保障三者中的二者，则必然会损害到第三者。

CA：保障一致性和可用性，牺牲分区容错性

此时要保证所有读取都是最新数据，而且可用，在故障的前提下，说明不存在节点通信，也就没有分区容错性。

CA就是假设网络不存在问题，一般单机或者小规模集群会采用。

AP：保障可用性和分区容错性，牺牲一致性

假设拥有最新数据的节点出现通讯故障，则必然存在部分节点的数据无法更新，若要保证这部分无法更新的节点的可用性，则无法达成一致性。

适用于对数据时效性和一致性要求不高的系统。

CP：保障一致性和分区容错性，牺牲可用性

同上，若要保证一致性，则部分无法更新的节点的可用性无法保证，需要阻塞等待网络恢复。

对于涉及金钱交易的系统，或者每次操作代价很大的系统，是非常常见的选择。

BASE

  • Basically Available（基本可用）

    • 不能保证永远是最好状态响应，可能存在延迟、页面降级等情况。

  • Soft state（软状态）

    • 不只有成功和失败两种状态，而是有中间状态。破坏了操作的原子性。

  • Eventually consistent（最终一致性）

    • 不能随时保证一致性，但能保证一段时间后系统的数据会变得一致。

BASE是对CAP中一致性和可用性进行权衡的结果，稍微放低一些要求，达到更好的泛用性。

共识算法

让系统中的不同节点能够协调地进行作业。

选举算法

在若干节点（服务器）中，需要选出一个节点来进行工作的分配与协调，被称为协作者/领导者。选出协作者的方法就是选举算法。

欺负算法

选择编号最大的节点作为协作者。当任何一个节点发现协作者不再响应请求时，它就发起一次选举。

  1. 向所有编号比它大的节点发送一个ELECTION消息

  2. 如果无人响应，该节点获胜并成为协作者

  3. 如果有编号比它大的节点响应，则由响应者接管选举工作，继续发送ELECTION消息。

  4. 最终胜利者（活动节点中编号最大者）将选举获胜的消息发送给所有节点，通知这些节点自己是新的协作者。

  5. 当一个以前崩溃了的节点现在恢复过来时，它将主持一次选举。如果该节点恰好是当前正在运行的节点中编号最大的节点，它将赢得此次选举，接管协作者的工作。

这样，现存节点中编号最大的节点总是取胜，故称为“欺负算法”。

Raft 共识算法

Raft通过当选的领导者达成共识。使用Raft算法，系统有两个状态：选举状态、工作状态。

每个server可能会有3个身份：领导者（Leader）、候选者（Candidate）、跟随者（Follower）

选举过程

  • 系统初始化时，所有服务器都是Follower，没有Leader。

  • 每个服务器有一个计时器，如果超时没收到Leader发来的心跳信息，则认为Leader已经崩溃。

  • 当发现Leader不存在时，节点会变成Candidate，发起新一轮选举。

  • 节点会首先给自己投票，然后向集群中其他所有的节点发起请求，要求大家都给自己投票。

    • 为了防止所有节点同时发起新一轮选举，不同节点的计时器超时设定不同

  • 其他收到投票请求且还未投票的Follower节点会向发起者投票，发起者收到反馈通知后，票数增加。

  • 当得票数超过了集群节点数量的一半，该节点晋升为Leader节点。

  • Leader节点会立刻向其他节点发出通知，告诉大家自己是Leader。收到通知的节点全部变为Follower，并且各自的计时器清零。

如果由于网络问题，其中一个leader崩溃之后又进入了集群，此时集群中存在两个leader。此时节点会关注leader的“任期”值，新leader的任期值较大，旧leader会退化为follower。

工作过程

  1. client向leader发送数据。

  2. leader向所有follower复制数据，如果失败则不断重试。

  3. 复制成功，follower向leader返回ACK。

  4. 当leader收到过半数follower发送的ACK，则向client返回成功。

  5. leader继续未完成的同步作业。

Paxos 共识算法

核心思路：发生冲突时，只接受最新的提案。

角色

  • client：系统外部角色，负责发起请求。

  • proposer：接收client请求，向集群提出propose，并在冲突发生时起到调节作用。

  • acceptor：集群中提议的接受者，只有大多数acceptor接受的提议才会形成决定。

  • learner：提议接受者，但是不影响决策，只负责备份已经接受的提案。

过程

1a. prepare

proposer提出一个提案，提案只包含一个编号N。N对于每个proposer都是单调递增的。

1b. promise

acceptor收到提案，如果提案的编号大于他收到的所有提案的编号，则接受并返回ACK，否则拒绝。

2a. accept

如果某个提案的接受者达到了大多数，proposer会发出accept请求，请求中包含提案编号N和内容。

2b. accepted

如果acceptor在收到accept请求期间没有再收到更大的N的提案，则接受并向proposer和learner发送，否则忽略。

Multi Paxos

上述算法存在一些问题，譬如：

难以实现、效率低（需要两轮请求）、存在活锁现象（如果不断有新提案出现，则难以达成共识）。

解决方法：只设置唯一的proposer，称为leader。只有leader能提出提案。

此时就不需要两轮同步，只需要一轮提案就可以达成共识。

数据一致性

数据一致性问题是复制造成的，数据在不同节点之间复制，会由于各种问题导致不同节点间的数据存在差异，如复制差错、网络崩溃等。

一般而言，我们以leader/master节点为数据的原本，讨论follower/slave节点的数据一致性问题。

强一致性

保证任何一次读取都是最新数据。

且任何进程锁能看到的操作顺序，都和全局时钟下的顺序一致。

leader 在保证了所有 follower 的数据和自己完全一致后才向用户确认，达成强一致性。

强一致性以外的都是弱一致性。弱一致性能够容忍过时的数据读取。

顺序一致性

任何一次读取都是最新数据。

所有进程看到的操作顺序是一致的，就算错了也是一起错。

最终一致性

系统可能因为各种原因无法及时达成一致，存在某些 follower 的数据滞后，这时候就出现了不一致的情况。

最终一致性保证这种不一致的状态是暂时的，整个系统会在一段时间后达成一致性。

不同的最终一致性可以在不同的局部范围之内，保证一定程度的一致性。

读写一致性

保证用户的每次成功的写操作后，读到的数据中都是写成功后的版本。

单调读

用户如果先后从不一致的不同库中读取信息，可能会出现后读取的信息版本更旧的情况。

单调读保证后读取的数据版本不会更旧。

因果一致性

让以逻辑顺序发生的事件被以正确的逻辑顺序读。

譬如，提问的出现应当在回答之前，那么读取时应当保证不会先看到回答再看到提问。

数据定位

用有限的服务器存储大量数据，如何将数据均匀地存放在不同的服务器中？

普通哈希算法

假设有0、1、2三台服务器，那么可以对数据进行哈希运算之后对3取余，根据运算结果决定数据存放在哪个服务器上。

这样的算法可以保证数据分布的均匀性，但是可扩展性差。当要增加或减少服务器节点的时候，会有大量数据需要进行迁移。

一致性哈希

服务器仍是有限的，但是数据的取不再对服务器数量取余，而是对2^32-1取余。

服务器也对2^32-1取余，使得到的结果分布在 0 ~ 2^32-1 构成的圆环上。所有的数据存放在按圆环顺时针寻找到的第一台服务器。

一致性哈希

这样，当我们需要对服务器进行增减，就只会影响到某一部分的数据。

存在的问题：

  • 数据偏斜：如果服务器在圆环上分布不均匀，可能会导致服务器存放数据不均匀。

  • 雪崩现象：当一个服务器失效，它的所有数据要迁移到下一个服务器，可能会导致下一个服务器过载严重也失效，造成链式反应。

解决方法：虚拟节点

圆环上不一定只能放物理服务器，可以将每个物理服务器映射成多个虚拟服务器放在圆环上，可以有效解决上述两个问题。

一般而言，节点数量越多，发生问题的概率越小。

哈希槽

哈希槽是Redis采用的方法，可以看做是一致性哈希的简化和优化。

  • 不使用普通的哈希算法和32位的哈希空间，而使用 crc16(key) mod 2^14(=16384) 简化的哈希算法，实现更加简单。

  • 每个节点都管理数量不定一组哈希值，称为哈希槽。增删节点时，会进行哈希槽的分配，也可以手动分配哈希槽。

  • 每个节点不是单个服务器，而是一组master-slave的集群，master负责数据的接收和处理，slave负责数据的备份。

    • 当master失效的时候，会选出一个slave成为新的master。

Zookeeper

是一个基于观察者模式设计的分布式服务管理框架，负责存储和管理数据，接受观察者的注册。当数据发生变化，则通知zookeeper上注册的观察者。

zookeeper = 文件系统 + 通知机制

其基本构成是一个leader，多个follower的集群，可以高效管理集群，提供强一致性和可用性（zookeeper，小动物管理员）

zookeeper可以单机部署，此时就是多进程模型，主要用于测试。

zookeeper所要处理的数据量很小，所以分布式部署时可以近乎看成是单机。

特性

  • 可用性：集群只要有半数以上节点存活，就能正常服务。建议奇数台服务器，至少三台。

  • 强一致性：每个节点都保存一份相同的数据副本

  • 实时性：在一定时间范围内，client总能读到最新数据。

  • 顺序执行：来自同一个client的更新请求都按照其发送顺序执行。

  • 原子性：数据更新要么成功，要么失败

文件系统：类似于unix文件系统，由树形结构组织成的ZNode，每个节点存放1MB数据，通过路径唯一标识。

提供的服务

  • 统一命名服务 提供分布式环境下的全局命名，便于识别。

  • 统一配置管理 提供分布式环境下的配置文件同步，保证所有节点的配置信息一致。 可以通过将配置信息写入一个ZNode，然后其他客户端监听这个ZNode，一旦有修改则通知同步。

  • 统一集群管理 提供实时监控节点变化。 可以将节点信息写入一个ZNode，并监听这个ZNode。

  • 服务器端动态上下线 可以将服务器信息写入一个ZNode，并监听这个ZNode。

总之就是监听ZNode

内部原理

选举机制

类似欺负算法，在所有节点中，可能有若干节点同时发起投票。此时节点会将票投给发起投票的节点中编号最大的那个。当节点收到的票数过半则直接当选。

  • 不一定是全局编号最大的。

节点分类：持久节点和短暂节点，取决于断开连接后是否删除。

监听机制

是观察者模式的核心。

  1. 创建一个main线程，在main中创建zookeeper客户端。
  2. 客户端中会创建两个线程，一个负责通信connect，一个负责监听listener
  3. 通过connect将注册的监听事件发送给ZK服务器
  4. ZK服务器在注册的监听器中将事件添加到监听列表
  5. ZK监听到目标ZNode有数据或路径变化，将消息发送给listener线程
  6. listener调用用户自己定义的process()方法进行操作

写数据（同步）流程

和raft的写数据流程基本一样。

  1. client向zookeeper的一个server上写数据
  2. 如果这个server不是leader，则将请求转发给leader
  3. leader将请求广播给follower
  4. follower写成功后通知leader
  5. 当大多数follower数据写成功，leader向收到请求的server返回成功
  6. server再向client返回成功

Kafka

kafka是一个分布式的基于发布/订阅模式的消息队列，主要应用于大数据实时处理

一些概念

消息队列

实现消息的异步传递。提供一个消息的缓冲区，发送的消息可以先存放在缓冲区中，然后慢慢处理。

  • 解耦：允许对两边的处理过程进行独立的修改
  • 可恢复性：系统一部分组件失效时，不会导致整个系统不可用。即使处理消息的进程挂了，队列中的消息也可以在系统恢复后处理。
  • 缓冲：平衡两端的处理速度不一致情况，主要是生产大于消费。
  • 灵活性和峰值处理：可能存在短时间访问量剧增的情况，消息队列可以削峰。

发布/订阅模式

是一种一对多的消息传递模式。相对于点对点的模式。

消息的生产者将消息发布到topic中，同时可以有多个消息的消费者订阅该消息。

消费模式有两种：topic推送数据，或者消费者从topic中拉取数据，kafka选择后者。

  • 好处：考虑到了消费者的处理能力，不容易造成资源浪费

  • 缺陷：消费者要维持一个常轮询来拉取数据，消耗CPU

kafka架构

  • 生产者（Producer）：生产消息的进程

  • 消费者（Consumer）：消费消息的进程

  • kafka集群（Broker）：由kafka服务器构成的消息管理模块，每个Broker是一个服务器节点

  • 主题（Topic）：消息按主题分类，消费者根据需求拉取对应主题的消息

  • 分区（Partition）：将同一个Topic的消息分成不同Partition，存放在不同的服务器上，实现不同机器的负载均衡。

    • kafka会自动将不同分区均匀地分配在不同机器上。
    • kafka会将消息轮询地发往不同分区，也可以手动指定消息发往的分区。

  • 副本（Replication）：保证可用性，同一个Partition需要有备份，分为leader和follower。

    • 消息的生产、消费都在Leader上进行，Follower只进行备份。当Leader崩溃时，Follower会选举出一个Leader。

    • 备份会放在不同机器上，所以副本数应当不大于机器数。

  • 消费者组（Consumer Group）：消费者可以进行分组。同一个组内的消费者不能重复消费一个分区，用于提高并发性。

    • 组内消费者数应小于等于目标主题的分区数。

  • 偏移（offset）：用于记录消费者消费到了Partition中的哪一条信息，要存放在Zookeeper(0.9版本之前)/kafka磁盘中，方便崩溃恢复之后继续工作。

可靠性保障

kafka 通过 ack 保障数据可靠性。

当 kafka 收到生产者发来的消息后，会先进行同步，同步完成后返回对应的 ack。

ack参数

  • ack=0 生产者不管ack，只负责生产，基本没有可靠性。

  • ack=1 leader 落盘后就会返回ack，如果leader同步完成后出现故障，就会数据丢失。

  • ack=-1 见下方。

ack 方案

kafka 既不是全部同步后才 ack，也不是半数同步 ack，而是维护了一个ISR列表，其中存放了活跃 follower 的编号。

如果一个 follower 长时间未向 leader 同步数据，则踢出 ISR。等到 follower 恢复并且同步完成时再加回来。

leader 在同步了 ISR 中的 follower 之后，就返回 ack。

一致性保障

如何保证 follower 之间的数据一致性？

LEO：指每个 follower 的最大的 offset

HW（高水位）：指消费者能见到的最大的offset，LSR队列中最小的LEO。

核心：follower 向 offset 最少的那个看齐，来保证不特定多数服务器挂掉之后出现的数据无法同步。

  • 譬如一个 offset 很大的 leader 和 follower 挂掉后，其他落后的 follower 可能没有较新的消息。

Follower故障

会被 leader 临时踢出ISR。等到恢复后，follower 会读取 HW，并将 log 文件中大于 HW 的截掉，然后开始和 leader 的同步。

Leader故障

Leader 发生故障后，会从 ISR 中选出一个新的 leader。之后，为了保证多个副本之间的数据一致性，其余的 follower 会先将各自的log文件高于 HW 的部分截掉（新 leader 自己不会截掉），然后从新的 leader 同步数据。

八股文

评论区