概览

基本数据结构和算法

同步机制

1. rw-lock/latch
   1. s-/x-：x-可递归，s-不可？；以spin获得，一段时间后进入wait array（信号量？）
2. p38 若sync_primary_wait_array中1000个cell都已分配，则ut_error触发crash
   1. 当持有latch的线程释放latch后，调用sync_array_signal_object唤醒等待线程

重做日志

1. p42 redo log原来保证事务的持久性（D），undo log用于回滚和MVCC
2. innodb_flush_log_at_trx_commit=0/1/2
3. redo log VS. bin log
   1. 前者记录的是页的物理逻辑操作日志
   2. 设计思想：物理日志记录页内的修改（old-new value），逻辑日志记录对表的操作（insert/delete）
4. LSN（表示事务写入redo log的字节量？）
   1. 对‘检查点’，表示刷新到磁盘的位置？——不管怎么说，LSN有一种‘随时间单调变化’的性质
5. 检查点：将缓冲池中的页刷新到磁盘
   1. sharp
   2. fuzzy*
6. redo日志的大小是固定的（3GB）->归档日志
7. ib_logfile<N>
8. redo日志块（512B-12-8）
   1. 和磁盘扇区大小一样，保证原子性，不需要double write？
9. 重做日志组*
10. 组提交：fsync -> log_flush_up_to 会对最后一个日志块进行复制
11. 恢复：recovery_from_checkpoint_start
    1. 表空间第一个页头部的FIL_PAGE_FILE_FLUSH_LSN记录了数据库关闭时最后刷新页的LSN
    2. recv_parse_or_apply_log_rec_body
    3. recv_add_to_hash_table
    4. recv_recover_page
    5. recv_read_in_area 判断页所在相邻的32个页？

mini-transaction（mtr）

1. FIX rules：修改页之前需要持有该页的latch
2. WAL
   1. 每个页需要有一个LSN？LSN溢出怎么办？
3. Force-Log-at-Commit
4. mtr_t mtr; mtr_start(&mtr); ... mtr_commit(&mtr);
   1. 提交时若mtr->modified==TRUE，先修改缓冲池中的页*1，然后释放log_sys->mutex（这是一个热点）
      1. *1 log_reserve_and_write_fast/log_write_slow 快速/慢速2个路径
   2. 更新多行记录时，MLOG_MULTI_REC_END

存储管理

1. 页：(space_id, offset) 16KB
2. 1 extent = 64 连续的page
   1. space header
3. 段（segment）
   1. 每张用户表至少2个段：聚集索引（B+树）的叶子节点和非叶子节点段
   2. 一个段最多可以管理32个独立的页，和若干区
4. 表空间
5. 数据结构：fil_system/space/node_struct
6. 4个异步I/O线程：异步读、异步写、插入缓存、重做日志

记录

1. 物理记录
   1. p102 用户记录的heap no总是从2开始
      1. 伪记录：Infimum/Supremum（感觉将像是双链表的first/last）
   2. p103 VARCHAR类型的NULL不占用磁盘空间，而CHAR NULL用0x00填充
   3. 大记录：BLOB/TEXT（溢出页，extern属性）
2. 逻辑记录
   1. dtuple_struct，对大记录是big_rec_struct
   2. B+树索引只定位页，页内记录需要二分扫描
      1. mtype/prtype
3. 行记录版本（MVCC只是列？）：通过隐藏的事务ID列
   1. read_view_struct：
      1. low/up_limit_id
      2. trx_ids, n_trx_ids
      3. creator
   2. p114 函数read_view_sees_trx_id用来判断当前事务是否可以读记录的当前版本，不是，则row_sel_build_prev_vers_for_mysql

索引页

1. Page Header
   1. 页内记录根据主键是逻辑顺序，不是物理顺序
2. Page Directory（定位记录在页内的位置）
   1. slot？offset的主键逆序记录
3. Page Cursor*

锁

1. p136 理论上，隔离级别越低，事务请求的锁越少或保持锁的时间越短
2. 幻读：谓词锁 --> key-range locking --> next/previous-key locking
3. p138 意向锁：意味着事务希望在更细粒度上加锁
   1. InnoDB是行级锁，不会阻止全表扫描以外的请求
4. lock_rec_struct = { space, page_no, n_bits }
   1. 所有锁对象通过kernel_mutex进行保护（又一个热点！）
      1. 优化：细粒度拆分？
5. p144 LOCK_GAP（代表范围锁不包含端点）
6. 显式锁和隐式锁**（略）
7. 行锁的维护*（重点，略）
   1. 插入
   2. 更新
   3. PURGE
   4. 一致性的锁定读
   5. 页的分裂
   6. 页的合并
8. 自增锁（atomic？）
9. 死锁*

B+树索引

1. 聚集 / 辅助
2. 分裂操作：btr_page_split_and_insert
3. 合并：btr_compress
4. 查找：btr_cur_search_to_nth_level
   1. p203 对唯一约束的键值，需要使用模式PAGE_CUR_GE，而不是LE
   2. latch_mode
   3. cursor
5. DML操作
   1. 乐观插入：btr_cur_optimistic_insert
   2. 非主键更新（主要是列的大小会不会发生变化）
      1. btr_cur_optimistic_update --> btr_cur_pessimistic_update（例略）
   3. 主键更新
      1. 删除
6. 持久游标 btr_pcur_struct
7. 自适应哈希索引*

Insert Buffer

1. 将多次插入合并为一次操作（提高了非唯一约束辅助索引的插入性能）
2. p237 实现最为困难的在于对死锁的处理
   1. 页逻辑层次划分：非IB页、IB非bitmap页、bitmap页
   2. p241 异步I/O线程可能引起死锁问题 --> rw_lock_x_lock_move_ownership

缓冲池

1. LRU、Free和Flush链表
2. 预读
   1. p258 随机预读
      1. 要满足32个页中9个已经访问过且都是活跃的才可能触发
   2. 线性预读*
   3. 逻辑预读
3. 页的刷新
   1. 部分写问题（？） --> double write（存在于内存的表空间，大小为2MB，这意味着最多128页/次刷新）

事务处理

1. 分类：扁平、带保存点的扁平、链、嵌套、分布式
2. 事务系统段*
3. doublewrite段*
4. undo日志存储
   1. 一致性的非锁定读
      1. p282 读取快照不需要加锁
   2. undo日志实现：回滚段 + undo段
      1. trx_undo_struct
5. undo记录
6. purge*
7. rollback
   1. 7B roll_ptr隐藏列 {rseg_id(1), page_no(4), offset(2)}
   2. 3个回滚类型：TRX_SIG_{TOTAL_ROLLBACK, ROLLBACK_TO_SAVEPT, ERROR_OCCURRED}
8. commit

数据字典

服务管理