子非鱼的技术博客

RAFT分布式共识机制

系统机制

Raft 是一个管理 replicated log 的算法

Raft 实现共识的机制

• 领导者选举（Leader Election）：共同选举出一个 Leader
• 日志复制（Log Replication）：给予这个 Leader 管理 replicated log 的完全职责
• 安全（Safety）：Leader 接受来自客户端的 log entries，然后复制给其他节点， 并在安全（不会导致冲突）时，告诉这些节点将这些 entries 应用到它们各自的状态机

只有一个 Leader 的设计简化了 replicated log 的管理。例如，

1. Leader 能决定将新的 entry 放到 log 中的什么位置，而不用询问Follower
2. 仅存在Leader->Follower的单向数据流

Leader 可能会挂掉（fail）或从集群中失联（disconnected），这种情况下会选举一个新 Leader

领导者选举（Leader Election）

选举触发

状态机切换流程

初始化

初始化流程主要包括从磁盘中加在持久化配置，将自己的状态设为 Follower

init：从磁盘中加在持久化配置，将自己的状态设为 Follower

becomeFollower：状态机切换为 Follower，执行 Follower 的处理流程

1
2
3
4
5
6
7
8
9
10
11
12
13

int init()
{
  // 1. 读取初始化配置（from 本地磁盘）
  currentTerm = read_file(currentTerm);
  votedFor = read_file(voteFor);
  prevLogIndex = get_prev_log_index(read_file(log[]));
  prevLogTerm = get_prev_log_term(read_file(log[]));
  
  // 2. 将自己的状态设置为Follower
  becomeFollower();
  
  return 0;
}

主要功能模块

请求响应模块

所有结点都可以响应客户端的读请求

线程池原理与实现

B站讲解视频：线程池原理与实现

线程池

线程池是什么

线程池（Thread Pool）是一种基于池化思想管理线程的工具，经常出现在多线程服务器中，如MySQL。

线程过多会带来额外的开销，其中包括创建销毁线程的开销、调度线程的开销等等，同时也降低了计算机的整体性能。线程池维护多个线程，等待监督管理者分配可并发执行的任务。这种做法，一方面避免了处理任务时创建销毁线程开销的代价，另一方面避免了线程数量膨胀导致的过分调度问题，保证了对内核的充分利用。

什么问题适用滑动窗口

对于连续子序列问题，可以使用滑动窗口。例如按要求得到最长/短的序列

滑动窗口算法框架

1
2
3
4
5
6
7
8
9
10
11
12
13

int low = 0, high = 0;

while (high < nums.size()) {
    // 增大窗口
    window.addLast(nums[high]);
    high++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.removeFirst(nums[low]);
        low++;
    }
}

滑动窗口方法需要考虑两个问题

1. 何时满足题目条件

   可能需要用到哈希表来统计元素出现情况

2. 何时缩小范围

   当high移动到第一次（不）满足题目要求后，移动low来缩小范围

3. 何时记录结果

   如果要记录最长序列则在缩小范围前记录

   如果要记录最短序列则在缩小范围后记录

最小覆盖子串

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

示例 1：

什么问题适合用前缀和

适用于快速、频繁地计算一个索引区间内的元素之和

前缀和算法框架

一维

每次累加前缀，当前元素指的是0-i的前缀和

注：从1开始是为了避免边界另外讨论，sum_list大小为原数组大小+1。填充的边界为0

1
2
3

for (int i = 1; i < sum_list.size(); i++) {
  sum_list[i] = sum_list[i - 1] + sum_list[i - 1];
}

二维

当前元素表示的是0-i，0-j范围内的前缀和

注：从1开始是为了避免边界另外讨论，sum_list长宽为原矩阵大小+1。填充的边界为0

CPU调度策略

任务调度策略的三个基本准则

• 任务周转时间：从新建到完成的时间
• 任务响应时间：从提交请求到首次响应的时间（前台任务关心）
• 系统吞吐量：一段时间内系统能完成的任务数

调度算法

1. 先来先服务

2. 最短作业优先调度：不可抢占，平均周转时间短（作业运行时间只能近似给出）

3. 最短剩余时间有限：最短作业优先的可抢占版本

4. 时间片轮转调度：保证响应时间

   时间片设得太短会导致过多的进程切换，降低了CPU效率；设得太长会引起对短作业的交互请求的响应时间变长

5. 多级反馈队列调度：动态调整任务类型（近期多IO可能为前台任务，无IO时间片结束未完成可能为后台大任务）

   运行流程

   1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
   2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。 若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回最下级队列队尾
   3. 只有第k级队列为空时，才会为k+1级队头的进程分配时间片

调度算法比较

视图（view）

概念

在MySQL中，视图是一种虚拟表，它是由一个或多个基本表的行或列组成的。视图并不实际存储数据，而是根据定义的 select 语句动态生成结果集。视图可以简化复杂的查询操作，提高查询效率，同时也可以保护数据的安全性，隐藏敏感数据。

执行过程

执行过程类似于 select 语句，流程如下

1. 视图展开（预处理器）：将视图名转化为 select 语句
2. 查询优化（优化器）：选择使用索引或者连接算法优化查询效率
3. 执行查询（执行器，存储引擎）：生成优化后的执行计划后，数据库的 存储引擎会根据这个计划执行查询。执行过程中，MySQL 会从底层表中读取数据，并按需执行连接、过滤、排序等操作，最终返回查询结果

连接（join）

简单嵌套循环连接

执行流程

对于左表的每一条记录，扫描右表的所有记录，找到匹配的记录

为什么要有缓存机制

MySQL 的数据是存储在磁盘里的，但每次访问磁盘开销过大。为此，Innodb 存储引擎设计了一个缓冲池（Buffer Pool），当数据从磁盘中取出后，缓存到Buffer Pool中，下次查询同样的数据的时候，直接从内存中读取，来提高数据库的读写性能。

除了数据的读取保存在缓存中，对数据的修改也不是立即写入磁盘，而是先写到缓存后择机刷盘。所以 Buffer Pool 中包含脏数据（数据页中）和 undo 页

如何提高缓存命中率

基本实现

使用LRU（Least recently used）算法

该算法的思路是，链表头部的节点是最近使用的，而链表末尾的节点是最久没被使用的。那么，当空间不够了，就淘汰最久没被使用的节点，从而腾出空间。

简单的 LRU 算法的实现思路是这样的：

数据库运行期间会发生哪些故障（问题）

事务故障

事务故障指事务未运行到既定的终点（没有commit或显式的rollback），例如对于支付系统若付款失败则需要回滚支付的操作，确保事务的一致性

系统故障

系统故障指需要即时重启系统而造成的数据库故障，现象是修改内存中的修改未写到磁盘，写入磁盘的数据未必是完成的事务

介质故障

介质故障指磁盘损坏造成的故障，需要全量迁移数据库数据

MySQL日志（解决方案）

undo log

概念

执行select的过程

连接器

客户端通过TCP三次握手与数据库建立连接

查询缓存

如果 SQL 是查询语句（select 语句），MySQL 就会先去查询缓存（ Query Cache ）里查找缓存数据，看看之前有没有执行过这一条命令，这个查询缓存是以 key-value 形式保存在内存中的，key 为 SQL 查询语句，value 为 SQL 语句查询的结果。

解析SQL

解析器完成词法分析（根据输入的字符串识别出关键字）和语法分析（判断语句语法）

执行SQL

预处理器