事务信息系统（并发控制与恢复的理论算法与实践）

第一部分  背景与动机
第1章  概述        1
1.1  目标和概述        1
1.2  应用举例        2
1.2.1  联机事务处理：借/贷的例子        2
1.2.2  电子商务的例子        5
1.2.3  工作流管理：旅行计划的例子        6
1.3  系统范型        8
1.3.1  三层体系结构和两层体系结构        8
1.3.2  服务器的联合        11
1.4  事务概念的优点        12
1.4.1  事务特性与事务编程接口        12
1.4.2  事务服务器的功能需求        14
1.5  数据库服务器的概念与体系结构        14
1.5.1  数据库系统的分层体系结构        14
1.5.2  数据是如何存储的        16
1.5.3  数据是如何被访问的        17
1.5.4  查询与更新是如何进行的        19
1.6  小结        21
习题        21
文献注释        21
第2章  计算模型        23
2.1  目标和概述        23
2.2  计算模型的组成部分        23
2.3  页模型        24
2.4  对象模型        27
2.5  本书的“路线图”        30
2.6  小结        31
习题        31
文献注释        32
第二部分  并 发 控 制
第3章  并发控制：页模型正确性的概念        33
3.1  目标和概述        33
3.2  经典的并发问题        33
3.3  历史和调度的语法        35
3.4  历史和调度的正确性        39
3.5  调度的Herbrand语义        40
3.6  终态可串行性        42
3.7  视图可串行性        45
3.7.1  视图等价和结果正确性准则        46
3.7.2  检测视图可串行性的复杂性        47
3.8  冲突可串行性        51
3.8.1  冲突关系        51
3.8.2  CSR类        52
3.8.3  冲突和交换性        54
3.8.4  冲突可串行性的约束        56
3.9  提交可串行性        57
3.10  一个可选的正确性准则：交叉存取说明        60
3.11  小结        65
习题        66
文献注释        67
第4章  并发控制算法        69
4.1  目标和概述        69
4.2  通用调度器的设计        69
4.3  锁调度器        72
4.3.1  简介        72
4.3.2  两阶段封锁协议        74
4.3.3  死锁处理        77
4.3.4  2PL的变体        79
4.3.5  有序的共享锁        80
4.3.6  利它锁        83
4.3.7  非两阶段封锁协议        86
4.3.8  封锁的几何学意义        89
4.4  非封锁调度器        91
4.4.1  时间戳排序        91
4.4.2  串行化图的检测        92
4.4.3  乐观协议        94
4.5  混合协议        96
4.6  小结        98
习题        99
文献注释        100
第5章  多版本并发控制        101
5.1  目标和概述        101
5.2  多版本调度        101
5.3  多版本可串行性        103
5.3.1  多版本视图可串行性        103
5.3.2  MVSR成员资格检测        105
5.3.3  多版本冲突可串行性        107
5.4  限制版本的数目        109
5.5  多版本并发控制协议        110
5.5.1  MVTO协议        110
5.5.2  MV2PL协议        111
5.5.3  MVSGT协议        114
5.5.4  只读事务的多版本协议        115
5.6  小结        116
习题        116
文献注释        117
第6章  对象上的并发控制：正确性概念        119
6.1  目标和概述        119
6.2  历史和调度        119
6.3  平面对象事务的冲突可串行性        122
6.4  树可归约性        125
6.5  树可归约的充分条件        128
6.6  采用基于状态的可交换性        132
6.7  小结        135
习题        136
文献注释        137
第7章  对象上的并发控制算法        139
7.1  目标和概述        139
7.2  平面对象事务封锁        139
7.3  分层锁        140
7.4  通用事务森林上的封锁        144
7.5  混合算法        146
7.6  为返回值的可交换性加锁和契约锁        147
7.7  小结        150
习题        151
文献注释        151
第8章  关系数据库的并发控制        153
8.1  目标和概述        153
8.2  面向谓词的并发控制        154
8.3  关系的更新事务        157
8.3.1  语法和语义        158
8.3.2  可交换性和简化规则        159
8.3.3  历史和最终状态的可串行性        160
8.3.4  冲突可串行性        161
8.3.5  扩展的冲突可串行性        162
8.3.6  在函数依赖面前的可串行性        163
8.3.7  小结        165
8.4  应用事务程序知识        165
8.4.1  范例        166
8.4.2  事务分割        167
8.4.3  切割的适用性        169
8.5  小结        171
习题        171
文献注释        173
第9章  搜索结构上的并发控制        174
9.1  目标和概述        174
9.2  B+树搜索结构的实现        175
9.3  访问层的键范围封锁        178
9.4  页层的技术        183
9.4.1  锁耦合        184
9.4.2  链接技术        189
9.4.3  放弃技术        190
9.5  进一步的优化        191
9.5.1  无死锁的页闩锁        191
9.5.2  增强的键范围并发        191
9.5.3  降低封锁开销        192
9.5.4  利用暂态版本化        193
9.6  小结        193
习题        194
文献注释        195
第10章  实现和实用性问题        196
10.1  目标和概述        196
10.2  锁管理器的数据结构        196
10.3  多粒度封锁和动态提升        197
10.4  暂态版本化        199
10.5  事务内部并行的嵌套事务        201
10.6  调整选项        201
10.6.1  手动封锁        202
10.6.2  SQL的隔离级别        202
10.6.3  短事务        204
10.6.4  多道程序级别的限制        206
10.7  过载控制        207
10.7.1  反馈驱动方法        208
10.7.2  等待深度限制        210
10.8  小结        210
习题        211
文献注释        211
第三部分  恢      复
第11章  事务恢复        213
11.1  目标和概述        213
11.2  带有显式Undo操作的扩展调度        214
11.2.1  概念的直觉和概述        214
11.2.2  形式化模型        214
11.3  页模型的正确性准则        216
11.3.1  扩展冲突可串行性        216
11.3.2  可归约性与前缀可归约性        217
11.4  充分的句法条件        219
11.4.1  可恢复性        220
11.4.2  避免级联中止        220
11.4.3  严格性        221
11.4.4  严厉性        221
11.4.5  日志可恢复性        224
11.5  带有事务中止的页模型调度协议        227
11.5.1  为实现严格性和严厉性扩展两阶段封锁协议        227
11.5.2  为日志可恢复性扩展串行图检测        227
11.5.3  为日志可恢复性扩展其他协议        229
11.6  对象模型的正确性准则        229
11.6.1  平面对象调度中的中止        229
11.6.2  通用对象模型中的完全中止和部分中止        234
11.7  带有事务中止的对象模型调度协议        237
11.8  小结        237
习题        237
文献注释        239
第12章  崩溃恢复：正确性概念        241
12.1  目标和概述        241
12.2  系统体系结构和接口        243
12.3  系统模型        244
12.4  正确性准则        246
12.5  算法路线图        248
12.6  小结        250
习题        251
文献注释        251
第13章  页模型崩溃恢复算法        252
13.1  目标和概述        252
13.2  基本数据结构        253
13.3  重做胜者范型        256
13.3.1  正常操作期间的操作        256
13.3.2  简单的三遍扫描（三趟）算法        259
13.3.3  增强算法：日志截断、检查点、重做优化        269
13.3.4  完整的算法：处理事务中止和撤销完成        281
13.4  重做历史范型        288
13.4.1  正常操作期间的操作        288
13.4.2  简单的三趟算法和两趟算法        288
13.4.3  增强的算法：日志截断、检查点和重做优化        294
13.4.4  完整的算法：处理事务回滚和撤销完成        294
13.5  小结        299
习题        306
文献注释        308
第14章  对象模型的故障恢复        309
14.1  目标和概述        309
14.2  重做历史算法的概念综述        309
14.3  一个简单的两层系统的重做历史算法        311
14.3.1  正常操作期间的操作        312
14.3.2  重启期间的操作        313
14.4  一个增强的两层系统的重做历史算法        316
14.5  一个完整的通用对象模型执行的重做历史算法        322
14.6  小结        324
习题        325
文献注释        327
第15章  恢复的特别问题        328
15.1  目标和概述        328
15.2  索引和大对象的日志和恢复        328
15.2.1  重做索引页分裂的逻辑日志条目        328
15.2.2  大对象操作的逻辑日志条目和刷出顺序        331
15.3  事务内部保存点和嵌套事务        334
15.4  在重启过程中使用并行性        338
15.5  对主存数据服务器的特殊考虑        339
15.6  数据共享机群的扩展        341
15.7  小结        344
习题        344
文献注释        346
第16章  介质恢复        347
16.1  目标和概述        347
16.2  基于日志的方法        348
16.2.1  正常操作期间的数据备份和归档日志        349
16.2.2  数据库恢复算法        351
16.2.3  对平均数据丢失时间的分析        352
16.3  存储冗余        355
16.3.1  基于镜像的技术        355
16.3.2  基于纠错码的技术        357
16.4  灾难恢复        363
16.5  小结        364
习题        364
文献注释        365
第17章  应用恢复        366
17.1  目标和概述        366
17.2  基于队列的无状态应用        367
17.3  基于队列的有状态应用        372
17.4  基于队列的工作流        374
17.4.1  故障可恢复工作流的状态和上下文        375
17.4.2  基于排队事务的分散工作流        376
17.5  一般的有状态应用        377
17.5.1  设计上考虑的事项        378
17.5.2  服务器应答日志算法综述        380
17.5.3  数据结构        381
17.5.4  正常操作期间的服务器日志活动        382
17.5.5  正常操作期间的客户端日志活动        384
17.5.6  日志截断        385
17.5.7  服务器重启        387
17.5.8  客户端重启        388
17.5.9  正确性推理        390
17.5.10  对于多层体系结构的适用性        393
17.6  小结        393
习题        394
文献注释        394
第四部分  分布式事务的协调
第18章  分布式并发控制        397
18.1  目标和概述        397
18.2  同构联邦中的并发控制        398
18.2.1  预备知识        399
18.2.2  分布式2PL        400
18.2.3  分布式TO        401
18.2.4  分布式SGT        402
18.2.5  乐观协议        403
18.3  分布式死锁检测        404
18.4  异构联邦中的可串行性        406
18.4.1  全局历史        407
18.4.2  全局可串行性        408
18.4.3  准可串行性        410
18.5  通过本地的保证获得全局可串行性        411
18.5.1  严厉性        411
18.5.2  提交排序        412
18.6  基于ticket的并发控制        413
18.6.1  强迫冲突的显式ticket        413
18.6.2  隐式ticket        415
18.6.3  显示和隐式ticket的结合        415
18.7  异构联邦中对象模式的并发控制        416
18.8  数据共享系统的一致性和并发控制        417
18.9  小结        420
习题        421
文献注释        422
第19章  分布式事务恢复        424
19.1  目标和概述        424
19.2  基本的两阶段提交算法        425
19.2.1  2PC协议        425
19.2.2  重启和终止协议        430
19.2.3  独立恢复        435
19.3  事务树两阶段提交算法        436
19.4  分布式提交的优化算法        439
19.4.1  假设中止协议和假设提交协议        439
19.4.2  只读子树的优化        443
19.4.3  协调者转移        445
19.4.4  减少阻塞        447
19.5  小结        448
习题        449
文献注释        450
第五部分  应用与未来前景
第20章  下一步是什么        453
20.1  目标和概述        453
20.2  我们完成了什么        453
20.2.1  开发者可用的解决方案        453
20.2.2  高级的系统搭建者可用的最新技术        454
20.2.3  研究人员的方法学和新的挑战        455
20.3  用于普遍访问的数据复制        455
20.4  电子服务和工作流        457
20.5  性能和可用性保证        460
文献注释        462
参考文献        464