05-事务

1. 事务处理

事务的本质是多个操作一个步骤（操作包括读取和写入数据记录）

• ACID特性：
  1. A 原子性：事务本质要求
  2. C 一致性：数据完整要求，开发者控制而不是数据库控制
     1. 数据库只能保证实体完整性和参照完整性，数据的一致性只能由开发者保证
  3. I 隔离性：并发的要求
  4. D 持久性：数据库系统要求

事务调度管理器 ：协调、调度和跟踪事务的各个步骤
锁管理器：保证隔离性，锁的粒度决定隔离级别
页缓存：充当持久化存储和存储引擎其余部分之间的中介
日志管理器 ：记录已应用在缓存页上的操作（日志条目），以便撤销已中止的事务所作出的更改
分布式事务协调

2. 缓冲区管理 Buffer Management

1. 双层存储是大部分数据库的基础
2. 页缓存
   1. Page in 换入
   2. Flush 刷写
   3. Evict 换出

缓存页什么时候换出？
提早换出，还是刷写时才换出？

2.1. 在缓存中锁定页

1. B+树越靠近顶部越窄，层次较高的节点在大多数读取中都会被命中
2. 分裂和合并操作最终会传播到高层节点
3. 频繁的子树结构变化，可以一起处理

2.2. 页置换策略选择

缓存更大不能减少换出次数，Beadly异常

1. FIFO
2. LRU：最长时间未使用策略
   1. 范围查询时，连续查询叶节点，叶节点虽然只被读一次但会把根节点换出去
3. LRU-K：最近K次访问频繁用到的页，并使用此信息估计访问时间
4. 2Q的LRU（双队列，k=2）：后续访问移入第二个队列，从而区分最近访问和经常访问
5. LFU
6. CLOCK

3. 恢复

• 日志：恢复最重要的技术

  1. Undo
  2. Redo：事务提交后，数据库发生崩溃，还未写回到磁盘
     • 格式e.g.把#1表的#293页面的偏移量2323的值更新为2

• 为什么不在事务提交之前，把事务所有的页面刷写到磁盘？

  1. 刷写一个完整的数据页太浪费，如果只修改一个字节，却要刷写一个16k的数据页
  2. 随机I/O环境效率低

3.1. redo日志

• Redo
  1. 占用空间小，
  2. 顺序I/O

3.1.1. redo日志设计

• 静态结构
  1. redo目录的结构
  2. redo需不需要设置页大小？要不要比正常的page大？
     • 页要足够大，方便一次性全部读出来
  3. 顺序文件还是随机文件？
     • 顺序I/O，追加写
• 动态结构
  1. 事务的原子性如何保障？冲突如何解决？
  2. redo日志也是双存储结构，如何写？
• 维护
  1. 如何循环使用redo

3.1.2. 格式

• 本质是记录事务对数据库物理表上的修改
  

• 简单日志：

  1. Type
  2. SpaceID：表ID
  3. Page number：页ID
  4. Data：日志的内容
  5. offset
  6. len：可能是变长

• 复杂日志：一条SQL可能修改多个地方（数据页面，聚簇索引，二级索引等）

  1. 在每个修改的地方都记录一条日志
     • 导致有很多条日志
  2. 将整个页面第一个修改的字节到最后一个修改的字节之间的数据，当成一条物理redo
     • 只有一条日志，但是很大

• 其他可能：只记录操作，不记录物理变化

  1. 物理层面的记录：指明哪个表空间，哪个页被改动
  2. 逻辑层面的记录：记录操作，系统崩溃后，重新执行这个操作
     • 基于逻辑的日志：本质是提供了调用恢复函数的参数，并不能直接执行日志恢复

3.1.3. Mini-Transaction

• 以组的形式写入redo log

  1. 一组操作，一组日志，不可分割

• 特殊类型的redo日志：保证一组日志的原子性
  

• 事务管理器：把整个事务组织成一个树状结构
  

3.1.4. redo log block

redo log的日志page大小比正常的page大（MySQL中,512K）

结构：头，尾，内容

3.1.5. redo日志缓存(redo log buffer pool)

• redo依然是双存储结构，有独立的Buffer，由若干连续redo log block组成
  • 事务结束标准：内存里的操作执行完成，脏页已经产生，日志已经写回磁盘
• 顺序写入，速度是最快的

3.1.6. lsn(log sequence number)

LSN是一个单调递增的数字，用于唯一标识事务日志记录（Log Record）在日志文件中的位置。每次事务修改了数据库中的数据并将其变更写入日志时，都会分配一个LSN。

1. 记录哪些log已经刷写，哪些日志尚未被刷写
   1. buf_free,buf_next_to_write
2. 对大多数数据库，需要有一个全局log变量定位位置
   • 记录block头尾和log大小，包括跨页，这样可以完整计算所有的偏移量，而不需要记录页id+偏移量，因为顺序插入

3.1.7. redo 日志文件(redo log file)

• redo log刷盘时机
  1. log buffer空间不足时
  2. 事务提交时
  3. 脏页刷新
  4. 定时进程，固定刷新
  5. 正常关闭服务器
• 磁盘中日志文件
  1. 数量和大小(2-100，48M)
  2. 循环写入
     

3.1.8. check point

定期地将内存中的数据（如缓存中的脏页）刷写到磁盘上。
在数据库恢复时，可以从最新的Checkpoint开始，然后根据日志中的LSN顺序redo或undo操作，直到达到最新的状态。

• redo日志组容量时有限的，不得不循环使用
• 需要解决的问题：
  1. buffer中，哪个日志组已经刷写到硬盘？
  2. 日志文件中，哪个日志组所涉及的操作已经刷写到数据文件中？

• 计算步骤

  1. 计算当前系统可以被覆盖的redo日志对应的lsn值最大是多少
  2. 将信息写入日志文件的管理信息中，记录check point的操作
     

• 理想状况，check point记录一次就行，但如果更新过快，可能需要多次记录

• check point每执行一次，均要修改redo日志文件的管理信息

• 后台刷脏操作和check point操作是两个并行的操作

  1. 修改页面非常频繁，导致lsn快速增长，无法及时做checkpoint，则线程做刷脏操作
  2. 定时完成check point操作

redo日志文件格式

1. log buffer本质上是一片连续的内存空间，被划分为若干个512k大小的block
2. redo日志刷新到磁盘是把block的镜像写入日志文件，文件也是若干个512k的block

3.1.9. 恢复

1. 确定恢复的起点：
   • 选取最近的checkpoint的信息，checkpoint_no比较一下大小
   • 然后找checkpoint_lsn和checkpoint_offset
2. 确定恢复的终点：log中记录的每个block的字节空间，找没满的那个
3. 按照日志的内容扫描，checkpoint_lsn之后的redo日志进行页面恢复

1. 同一个页面的redo log在同一个槽里
2. 同一个页面的redo log按生成时间顺序排序，保证恢复时操作有序
   

3.2. Undo日志

是Redo操作的子集

1. 事务原子性都是用日志保证
2. 对每一条记录进行改动的时候，都需要留一手
   1. INSERT，记录主键，rollback就删除主键
   2. DELET，记录内容，rollback就恢复记录
   3. UPDATE，记录内容，rollback就恢复记录

3.3. 更一般的恢复

1. 预写日志(Write-Ahead-Log, WAL) ，也叫提交日志(commit log)
   1. 允许页缓存将页进行缓存的时候，保留数据库可持久性语义
   2. 事务的提交，以日志写在磁盘上为结束，而不是事务修改的脏页写到磁盘上
   3. 当发生崩溃时，数据库可以从日志重建内容
2. 日志是追加还是原地
   1. WAL是仅追加，已写入内容不变，顺序写入
   2. 安全访问写入边界之前的内容，并在结尾增加新的日志
3. 日志的语义要求：
   1. 日志序列号LSN，唯一，递增，内部计数器或时间戳
   2. 强制刷盘操作，事务管理器，页缓存触发
   3. WAL作为事务结束标准

• 每次换出页都刷写磁盘，性能可能会更差，解决⽅案是？
  • 独立后台进程循环刷写（PostgreSQL的后台刷写器）以及定期checkpoint刷写

3.4. 操作日志和复制日志

• 影子页（shadow paging）——写时复制（copy-on-write）
  • 新更改的内容被存放在一个新的、未发布的影子页
  • 并通过指针翻转使其可见，从旧页切换到包含更新内容的新页
• 数据日志（保存对完整页状态或字节级的更改，物理日志）
• 操作日志（保存在当前状态上执行的操作）