秋招复习剪辑

数据库

索引

索引失效

• or条件查询可能失效，可以使用union代替
• 字符串类型用引号括起来，否则失效
• like非前缀匹配会引起失效
• 索引列使用mysql内置函数
• 索引列运算

• 索引字段使用!=、<>、not in、is null、is not null可能导致失效

• 左连接或右连接查询关联字段编码不一致

• mysql优化器预估全表扫描快于索引查询

不适合索引场景

• 数据量少（插入耗时增加？）
• 写多读少
• 区分度低的字段（如性别）

索引底层规则

• 覆盖索引（直接从索引一次性可查到数据）
• 回表（二级索引不能查到会回聚集索引中再查以得到最终数据）
• 索引条件下推优化（Using index condition）
  • 目的：减少IO次数
  • 特殊：在根据索引获取数据时，通过下推条件判断是读取表中数据，还是读下一个索引，减少MySQL Server返回数据量
  • 适用于：整表扫描场景，InnoDB只适用于二级索引
  • 不适用于：引用子查询条件不能下推、调用存储过程不能下推、触发条件不能下推
  • 配置：默认开启，属于存储引擎的优化手段，可通过SET optimizer_switch = 'index_condition_pushdown=off';配置开关

索引数据结构

为什么是B+树而不是

• 一般二叉树
  • 二叉树特殊化为链表，每次查询都是全表扫描
• 平衡二叉树
  • 平衡二叉树可存储数据较少，一个节点只存一个键值和数据，而B数可以存更多数据
• B树而是B+树
  • B树非叶子节点也有数据，读取一个磁盘块包含的节点更多，减少IO查询速度也更快
  • B+树同层节点按序，且用双向链表连接，叶子节点内部数据用单向链表连接，使得排序、范围查找、去重查找变得更简单

聚集索引和非聚集索引

• 一个表中只能有一个聚集索引，和多个非聚集索引
• 聚集索引索引键值的逻辑顺序对应了物理顺序，非聚集索引逻辑换顺序与物理顺序不同
• 如何选择

动作	使用聚集	使用非聚集
列经常分组排序	可	可
返回范围数据	可	不可
一个或极少数不同值	不可	不可
小数目不同值	可	不可
大数目不同值	不可	可
频繁更新列	不可	可
外键列	可	可
主键列	可	可
频繁修改索引列	不可	可

锁

分类

• 按粒度分：表锁、页锁、行锁
  • 表锁：粒度最大、开销小、加锁快
  • 页锁：BDB支持的锁机制，无人使用
  • 行锁：对索引加锁，粒度最小锁，开销大、加锁慢，会出现死锁，冲突概率低，并发性能高
    • 记录锁：锁住单行记录的索引
    • 间隙锁：锁住查询范围，防止幻读
    • 临键锁：扩充锁住前后范围，防止幻读
• 使用方式：共享锁、排它锁
• 思想分：乐观锁、悲观锁

乐观锁和悲观锁（思想）

• 悲观锁：直接加锁，阻塞其他线程修改
• 乐观锁：不上锁，更新的时候检查判定字段是否有被修改。CAS
• 强行加锁，如果指定索引列则加行锁，否则加表锁

Next Key Lock

Record Lock 和 Gap Lock 的结合，记住！是为了解决幻读

• 对非主键索引查询，记录的上下记录区间加锁，如对记录1,2,3,5,8查询3则会锁住(2,3]U[3,5)记录区间
• 对主键索引，不会产生幻读，因此只加普通行锁

死锁

• 程序出现高并发时，尽量对表串行化操作或锁升级，一次性获取全部资源
• 设置innodb_lock_wait_timeout变量，使得锁等待超时回滚
• 打开innodb_deadlock_detect变量，当发现死锁时，自动回滚其中一个事务

其他

• 锁竞争查询：show status like table_lock可以查看锁竞争状态，waited越大代表锁竞争越严重
• 并发插入：通过concurrent_insert变量调整并发插入配置，0不支持、1只要没有删除即插入表尾、2无论是否有删除都插入表尾

查询优化方法

• 加索引
• 仅返回需要的字段
• offset & limit
• sql结构优化
• 分库分表
  • 水平分表：一个库中的数据拆分为多个表（hash、range）
  • 垂直分表：按照业务拆分；按照字段活性，拆分主表和扩展表
  • 事务需要使用分布式事务
• 读写分离

SQL优化

• explain
• 慢查询日志（–log-slow-queries启动项和long_query_time ）

分布式主键方案

• 数据库自增序列或字段
• UUID
• Redis生成ID

引擎

InnoDB和MyISAM区别

• InnoDB独有
  • 事务
  • 外键
  • MVCC多版本并发控制
• MyISAM独有
  • 全文索引（InnoDB5.7后支持）
  • 变量保存表总行数，select count(*) from table更快
• 区别
  • InnoDB支持表、行锁，MyISAM只支持表锁，InnoDB使用索引默认为行锁，不使用则为表锁
  • InnoDB必须有主键，MyISAM可以没有主键
  • InnoDB表需要更多内存和存储，MyISAM可被压缩
  • InnoDB按主键大小有序插入，MyISAM按插入顺序保存

事务

MySQL事务特性

• 原子性
  • 定义：事务作为整体，要么全部执行要么全部不执行
  • 机制保障：undo log恢复事务执行之前的状态
• 一致性
  • 定义：事务开始之前和结束之后的数据不会被破坏，典型案例：转账
  • 机制保障：回滚、恢复、并发隔离
• 隔离性
  • 定义：多事务并发访问时，事务之间是相互隔离的
  • 机制保障：锁、MVCC
• 持久性
  • 定义：事务完成后，所有更改应该均保存到数据库中
  • 机制保障：redo log崩溃恢复

事务隔离级别

事务并发带来的问题

不同隔离级别导致的问题

• 脏读：事务A读取到了事务B未提交的数据
• 不可重复读：事务A受到事务B影响前后两次读取同一条数据不同
• 幻读：事务A受事务B影响，前后两次读取同一批数据不同

隔离级别

带来上述问题

• 读未提交：事务可以读取到其他事务未提交数据，导致脏读
  • 读不加锁，写阻塞其他事务写，不阻塞读
• 读已提交：事务只能读取到其他事务中已经提交的数据，可能导致不可重复读
  • 每次读取数据前，生成新的ReadView

• 可重复读：事务开始时会将select的数据打一份快照，保证同一个事务内select不受其他事务update/delete影响（系统默认隔离级别）

  • 仅在第一次读取时生成一个ReadView

• 串行化：防止事务并发

  • 读加共享锁，写加互斥锁

MVCC 多版本并发控制

• 依赖于隐式字段、undo日志、快照读&当前读、Read View
  • 每行记录存在隐藏列，记录事务ID、指向undo日志的指针、单调递增的RowID（无主键和非NULL唯一键）
  • undo日志：事务未提交时修改数据操作的反向操作存到undo日志。数据的undo日志指针会将不同事务产生的多个版本用指针串连
  • 快照读：不加锁读，读取记录数据当前可见版本
  • 当前读：显式加锁读读取记录最新版本
  • Read View：事务执行快照时产生的读视图，保存当时留存的事务ID列表，通过判断数据的记录事务ID决定数据是否可见
    • 当前ID小于当前最小事务ID，说明数据在当前留存事务前已经提交，可见
    • 当前ID大于事务最大事务ID，说明数据版本是在ReadView生成后才生成，数据不可见
    • 生成数据版本的事务ID在事务ID列表中，说明事务只生成了数据版本，但是未提交，不可见；如果不在事务ID列表中，生成数据版本已提交，可见。

其他

• 在使用exists和in时，遵循小表驱动大表原则

操作系统

调度算法

进程调度

CPU调度进程，因此也称CPU调度算法

进程五状态模型

• 就绪：已经获得所有所需资源，等待分配处理机资源
• 运行：占用处理机资源
• 阻塞：等待所需资源得到满足
• 新建：进程创建但未被提交，等待获取资源
• 终止：进程运行完毕

CPU调度时机

• 运行状态到阻塞状态 => 非抢占式
• 运行状态到就绪状态 => 抢占式
• 阻塞状态到就绪状态 => 抢占式
• 运行状态到终止状态 => 非抢占式

抢占式调度和非抢占式调度

• 抢占式调度：当前进程被动放弃处理机，如时间片用完、有更紧急的事情需要处理（IO中断）、有更高优先级进程进入队列
• 非抢占式调度：当前进程主动放弃处理机，如进程正常终止、进程运行中异常终止、近程主动请求阻塞（等待IO）

不会发生进程调度

• 处理中断时
• 进程在操作系统内核临界区时
• 进行原子操作时

调度算法

批处理系统调度算法

关注公平性、平均周转时间、平均等待时间等理性指标，不考虑任务的紧急程度

• FCFS 先来先服务

  • 特点：非抢占式，先到先服务
  • 优点：对各个作业公平，算法简单，不会产生进程饿死
  • 缺点：对CPU密集作业有利，对IO密集作业不利。CPU密集型需要占用更多CPU时间，导致IO密集型需要更多的等待时间

• SJF 短作业优先

  • 特点：短作业优先，非抢占式（抢占式场景为SRTN 最短剩余时间优先算法）
  • 优点：短作业可以更快被调度，拥有最短平均等待时间和平均周转时间
  • 缺点：长作业可能被饿死，工程实现上较难

• HRRN 高响应比优先

  响应比 = （ 等待时间+实际运行时间 ）/ 实际运行时间 = 等待时间 / 实际运行时间 + 1

  • 特点：综合FCFS和SJF算法，当运行时间相同，响应比越高等待时间越长越应该被调度类似FCFS；当等待时间相同，响应比越高运行时间越短越应该被调度类似SJF

交互系统调度算法

更注重响应时间、公平性、平衡性

• RR 时间片轮转法
  • 特点：所有任务轮转使用固定时间片运行，抢占式调度
  • 优点：公平、响应快
  • 缺点：时间片把握，太长退化成FCFS，太短导致上下文切换时间过高
• HPF 最高优先级调度
  • 特点：根据任务优先级抢占式/非抢占式调度
  • 优点：考虑任务优先级情况
  • 缺点：任务可能会饿死
• 多级反馈队列
  • 特点：
    • 多级执行队列，不同队列执行时间片递增
    • 队列内部FCFS，一个时间片没有执行完则进入下一级队列
    • 已经是最后一级队列则放入队尾
    • 时间片越短队列级别越高，总是先抢占式调度高级别队列任务
  • 优点：融合了FCFS的公平性、SFJ对短作业的照顾、RR对进程的响应速度
  • 缺点：存在进程饿死的场景

内存页面置换

缺页中断

• CPU执行Load M指令会访问M对应的页表
• 当页表标记有效时，直接访问内存；标记无效时，发送缺页中断
• 缺页中断后，查找磁盘对应数据，写入物理内存
• 写入物理内存时，若找到空闲页，则直接写入，若未找到，则需要替换已存在的物理内存页，若是脏页则需要将对应的页写回盘，页表项标记无效

置换算法

• OPT 最佳页面置换
  • 算法：置换下次访问时间最长的页
  • 优点：最低程度较少缺页
  • 缺点：工程无法实现，程序访问页面是无法准确预知下一次访问时间的
• FIFO 先进先出
  • 算法：替换驻留时间最长的页
  • 优点：实现简单
  • 缺点：性能较低
• LRU 最久未使用
  • 算法：替换最长时间没有被访问的页（双向链表，访问置队尾，替换队头）
  • 优点：性能相对FIFO有所提高，且工程上可以实现
  • 缺点：实现相对复杂，开销较大
• 时钟页面置换算法
  • 算法：
    • 构造环形队列，页面访问位初始化为0，初始指向0号页面
    • 若被访问，将访问位置1
    • 需要替换时，从当前指向节点开始，替换第一个访问位为0的页面，并将沿途为访问位为1的页面改为0
  • 优点：结合了LRU和FIFO的特点，每次替换近期未使用的较早进入队列的页面，减少替换页面时的开销
• LFU 最不常使用算法
  • 算法：替换最不经常使用的页面，对页表项添加计数器，替换最小的页面
  • 缺点：对于短期内高频访问而之后不再访问的页面无法正确置换，同时计数器硬件成本较高

磁盘调度算法

先来先服务

• 算法：按照请求顺序先来先服务
• 特点：实现简单，但是效率无法保证

最短寻道时间优先

• 算法：总是找离磁头最近的磁道优先访问
• 特点：效率有所提高，但是可能存在请求饿死

扫描算法

• 算法：也叫电梯算法，先朝某个方向移动至顶端再返回
• 特点：效率有一定提升，但是每个磁道的响应频率存在差异
• 循环扫描算法：每次朝同一个方向到达另一端顶点后，返回头部，中间不接收任何请求

LOOK & C-LOOK算法

• 算法：类似扫描算法，但是不到达端点，而是到达最远端请求磁道后即返回

进程互斥与同步

临界资源

• 并发进程的共享资源
• 同一时间内只支持一个进程访问

资源访问分区

• 进入区：检查是否可以进入临界区
• 临界区：访问共享资源
• 退出区：重置临界区占用标识
• 剩余区：其他逻辑

进程互斥原则

• 空闲让进：临界区空闲时应该让想要进去临界区的进程立刻进来
• 忙则等待：如果已经有资源进入临界区，则其他进程只能等待
• 有限等待：保证等待进入临界区的进程等待时间是有限的，不能一直等下去
• 让权等待：当进程不能进入自己的临界区时，应该释放CPU资源，防止进程“忙等”

信号量

• 机制：通过P/V原语操作标记资源数量的变量，原语有不可中断的性质，实现多进程互斥访问
• 数值型信号量：数值标记资源 + while循环等待
• 记录型信号量：数值标记资源 + 进程等待队列，资源不足时阻塞进程，防止忙等

进程同步

使用信号量控制进程同步

• 信号量初始化为0
• 在后操作之前使用P原语阻塞进程
• 当“前操作”执行完毕后，调用V原语，增加资源，唤醒“后操作”进程。前VP后

典型例题

生产者消费者

• 互斥规则：缓存区要么放要么取
• 同步规则：只有缓存区有东西才可以取 ；只有缓存区有空位才可以放；
• 伪代码

producer() {					consumer() {
	生产商品					    P(full)
	P(empty)					   P(mutex)
	P(mutex)					  取商品
	商品放入缓存					  V(mutex)
	V(mutex)					  V(empty)
	V(full)						  使用产品
}								}

橘子苹果问题

• 互斥规则：盘子要么放水果要么取水果

• 同步规则：盘中有橘子儿子才取；盘中有苹果女儿才取；盘中无水果父母才放

• 伪代码

Dad() {				Mom() {
	P(empty)			P(empty)
	放苹果				  放橘子
	V(apple)			V(orage)
}					}

Daughter() {		Son() {
	P(apple)			P(orange)
	取苹果			  	  取橘子
	V(empty)			V(empty)
}					}

文件读写

• 互斥规则：读写互斥，读读不互斥
• 同步规则：无
• 伪代码

Writer() {		Reader() {
	P(w)			P(w)	// 确保读写公平，防止写进程饿死
	P(rw)			P(mutex)	// 锁住count，防止阻塞其他读进程
	写文件			  if (count == 0) {
	V(rw)				P(rw)	// 首个读进程阻塞写操作
	V(w)			}
					conunt += 1
}					V(mutex)
					V(w)
					读文件
					P(mutex)
					count --
					if (count == 0) {
						V(rw)
					}
					V(mutex)

哲学家吃饭问题

• 互斥规则：筷子只能被一位哲学家使用
• 同步规则：只有等身边的哲学家吃完自己才能开始吃
• 伪代码（略）
  • 方法1：一次申请全部资源，使得拿筷子是原子操作
  • 方法2：奇数号哲学家先拿左手筷子，偶数号哲学家先拿右手筷子
  • 方法3：只有n-1人能够参与筷子争夺

计算机网络

OSI七层模型和TCP/IP四层模型

ref: https://zhuanlan.zhihu.com/p/32059190

四层	七层	应用层	功能	TCP/IP协议族
4	7	应用层	为应用程序提供网络服务	Http、Telnet、Ftp、Email、DNS
4	6	表示层	数据格式转化	无
4	5	会话层	解除或建立与其他端点连接	无
3	4	传输层	提供端对端接口	TCP、UDP（RTP）
2	3	网络层	数据包路由选择	IP、ICMP、ARP、RARP、BOOTP
1	2	链路层	传输有地址帧、错误检测	SLIP、CSLIP、PPP、
1	1	物理层	二进制形式传输	IEEE 802.1A

拥塞控制

1. 慢启动

   • 连接建好后初始化窗口大小 cwnd = 10

   • 当收到一个ACK，cwnd += 1，经过一个RTT，cwnd翻倍，指数增加

   • 当cwnd >= ssthresh时，进入拥塞避免算法

2. 拥塞避免

   • 经过一个RTT，发送方拥塞窗口cwnd += 1

3. 快速重传

   • 主要用于丢包检测

4. 快速恢复

   • 当检测到丢包时，触发快速重传，进入降窗状态，将cwnd降到一个合理值

系统设计

缓存系统

主要问题

• 一致性：存储和缓存中的数据的一致性问题
• 缓存击穿：查询在缓存中未命中，透传DB查询，大量击穿导致DB拒绝服务
• 缓存雪崩：数据过期时间近似，大量数据同时过期或冷数据瞬间涌入大量请求导致DB压力过大拒绝服务