此笔记是对 database system concepts 学习的记录

10 存储和文件结构

文件在逻辑上被划分为固定大小的单元，称为blocks，它是存储和数据传输的基本单元； 一个block可能包含多个records

我们假设单个record大小不超过一个block，这个假设对大多数数据处理应用是合理的；另外还要求，record不会跨block存储，这简化对data item的访问(这个要求合理吗？)

records如何表示

固定长度的record
当record被删除时，就会留下空白空间，新插入的record应优先使用这些空间； 可以从File header出发，将各个blank space串联起来，形成free list，如下图所示：
image.png

变长record
有着可变长度属性的record，往往有两部分，一个固定长度的属性，跟着是变长属性，在最前头的initial part那可以放置变长属性的(offset, length) pair，
image.png
上图，offset=21的位置就是id field， 65000是salary字段，固定大小所以放在前面； bitmap可以用来表示哪些field是null

关于变长record如何在block中存储，常用技巧是 slotted-page structure。header有entry个数 ，有指向free space的指针，有array分别指向各个record; 作者说当有record删除时，将前面的record进行move以腾出连续的free space，这种move代价不大，因为block 大小有限 ?
image.png

records如何文件中组织

前面讲的是records如何表示，那给定一系列records，该如何表示它们？常见的有：

  • heap file organization

只要还有空间就可以放，不管放在哪里,records间无序 (这种方式为何叫heap ?)

  • sequential file organization

根据search key的值，按序排放

  • hashing file organization

根据某种属性的hash值来决定放在哪个block里

sequential file
是为以某种sorted order来高效处理而设计的， search key不一定得是primary key;

当插入和删除时，就得维护其sorted order. 比如当insert时，首先定位到比new record前面那个record A，看看A后面有没有free space，如果有则插入，如果没有，则需将new record放在 overflow block 里。
这样就会造成，时间久了，按照search key的访问顺序 和record物理顺序相差很大造成访问变慢，这就需要 reorganization。代价昂贵，得在低峰期做！

multitable clustering file organization
一般来讲，一个表/关系用一个单独文件进行存储，但在 multi-table clustering file organization中，多个表的记录可以放在相同文件中，相关记录还可放在相同的block里，这样有利于I/O

比如对join操作这种组织是有利的，但同时对其它查询就不利。是否采用取决于db designer认为哪种类型的查询是最为频繁的

16 Recovery System

fail-stop assumption: 硬件故障不会导致corrupt nonvolatile 存储，是一个合理的假设

我们假定data item 不会跨多个blocks，大多数应用是满足的

buffer blocks: 物理块映射在内存中的blocks
disk buffer: 装buffer blocks的memory area

We say a txn modifies db if it performs an update on a disk buffer or on disk itself.

如果事务直到提交才修改db，这叫deferred-modification；
如果在活跃状态中就不断修改,这叫 immediate-modification

为避免cascading rollback，要求 no other txn can modify data item until the first txn commits or aborts

  • 对于SI,或validation这样的concurrency scheme, deferred-modification is a natural fit. 即在最后的阶段才将修改提交；
  • 对于two-phase locking，既然都上锁了，那赶紧地修改db才是比较稳妥的做法

当然SI也可以是immediate-modification，或two-phase也可以是deferred-modification

什么叫事务提交了

We say that a txn has committed when its commit log record, which is the last log record of the txn has been output to stable storage; at that point all earlier log records have already been output to stable storage.

use redo/undo

redo(Ti)：扫一遍log，对每条碰到的log都考虑执行redo，而不是为每个txn单独地执行redo （因为item 的apply 顺序要和当初apply顺序一致）

When the undo op for txn Ti completes, it writes a log record,indicating that the undo has completed.

事务undo做完后，要写一条abort log

系统crash后，系统consults the log to determine which txns needs to be redone, and which need to be undone.

  • 有，但无 or ，则undone
  • 有，但有 or ，则redone

simple checkpoint

一种简单策略如下：

  • 把当前内存中的所有Log刷盘
  • 将所有修改的buffer blocks刷盘
  • 写一个刷盘，L 是checkpoint进行中时的txn list

simple CP过程中不可有事务再有更新操作

系统重启后，examine the log to find the last record(this can be done by searching the log backward),然后redo/undo只需对L中的事务以及 写入后开启的事务，后者表示为T

  • 对T中所有的txn Tk，如果没有 or , then undo(Tk)
  • 若有 or , then redo(Tk)

对于Ti in L, 它们的Log records不能删，因为可能没有commit而要undo； 但对于 min{Ti start} 之前 的log可以被prune了

之后会讲fuzzy checkpoint，允许在chekcpoint期间接收写

wiredtiger CP 与概念如何对应

恢复算法详解

rollback during normal op

在正常操作下的回滚，不是指crash后的重启

  • 向后搜索，每遇到时，将V1写入到Xj； 同时写一条redo-only log, (为什么不直接从最新的checkpoint开始，只需对Ti undo一次就行呢？)
  • 找到后停止，写入一条

recovery after system crash

系统重启有两步走：

  1. redo phase. 系统从最新的checkpoint向前扫log，要replay的log包括两部分：
    1. crash前已经rollback的txn log
    2. crash时还未完成的txn log

具体步骤如下：

  1. 将undo-list 初始化 L 中的txn
  2. 当遇到或 时，一律做redone，即把V2 写到 Xj（因为此时不知道该redo 还是 undo，但redo可以简化恢复策略），不管Ti最终是什么结果
  3. 当遇到时，就把Ti 加入到 undo-list
  4. 当遇到 or 时，将Ti 从undo-list 中移除
    1. undo phase，系统rollback undo-list中的事务，从前往后扫log
  5. 只要碰到一条属于undo-list 中的log, undone，同时写redo-only log
  6. 碰到 ，写一条，且从undo-list中移除
  7. undo-list为空时，undo phase结束

第1步中，会对所有事务的更新对redone，不管它是不是failed tx。 这会简化recovery scheme

image.png

上图中，在undo phase阶段，只剩下T2.往后回溯，先恢复A 的值500，遇到T2 start后，回滚即将结束，写一条T2 abort，即结束

buffer management

WAL logging rule:

  • 只有Ti 的commit log record 刷盘了，Ti 才提交了
  • 在 刷盘前，所有与Ti 相关的修改log 都要刷盘
  • 在内存数据 block 刷盘前，与其相关的log record 必须先刷

Strictly speaking, the WAL rule requires only that the undo information in the log has been output to stable storage, and it permits the redo information to be written later. The difference is relevant in systems where undo information and redo information are stored in separate log records.

no-force: 在提交时，有些blocks 并未写disk. 这个好处是允许block 积累，减少disk write 开销，属于标准做法 （force 则是提交时，所有的修改block 得刷盘）
steal: 事务还没提交，修改的blocks 就可以写disk （可理解成tx一边做事，一边偷磁盘的空间） ，此为标准做法 （与force 强调的不同，force/no-force 是强调提交时应该做什么, steal/no-steal 是强调进行中应该做什么）； no-steal 意味着做大量更新的 tx 会retain 所有修改在内存直到提交时

wiredtiger 支持的是 no-steal，所有unresolved tx 的修改都在内存中

对block 加锁

当block 被写disk 时，不允许有写作用于此block;
需要加short-duration lock，往往称为latch

wiredtiger 有吗？