事務(wù)信息系統(tǒng)（并發(fā)控制與恢復(fù)的理論算法與實踐）

第一部分  背景與動機
第1章  概述        1
1.1  目標(biāo)和概述        1
1.2  應(yīng)用舉例        2
1.2.1  聯(lián)機事務(wù)處理：借/貸的例子        2
1.2.2  電子商務(wù)的例子        5
1.2.3  工作流管理：旅行計劃的例子        6
1.3  系統(tǒng)范型        8
1.3.1  三層體系結(jié)構(gòu)和兩層體系結(jié)構(gòu)        8
1.3.2  服務(wù)器的聯(lián)合        11
1.4  事務(wù)概念的優(yōu)點        12
1.4.1  事務(wù)特性與事務(wù)編程接口        12
1.4.2  事務(wù)服務(wù)器的功能需求        14
1.5  數(shù)據(jù)庫服務(wù)器的概念與體系結(jié)構(gòu)        14
1.5.1  數(shù)據(jù)庫系統(tǒng)的分層體系結(jié)構(gòu)        14
1.5.2  數(shù)據(jù)是如何存儲的        16
1.5.3  數(shù)據(jù)是如何被訪問的        17
1.5.4  查詢與更新是如何進行的        19
1.6  小結(jié)        21
習(xí)題        21
文獻注釋        21
第2章  計算模型        23
2.1  目標(biāo)和概述        23
2.2  計算模型的組成部分        23
2.3  頁模型        24
2.4  對象模型        27
2.5  本書的“路線圖”        30
2.6  小結(jié)        31
習(xí)題        31
文獻注釋        32
第二部分  并 發(fā) 控 制
第3章  并發(fā)控制：頁模型正確性的概念        33
3.1  目標(biāo)和概述        33
3.2  經(jīng)典的并發(fā)問題        33
3.3  歷史和調(diào)度的語法        35
3.4  歷史和調(diào)度的正確性        39
3.5  調(diào)度的Herbrand語義        40
3.6  終態(tài)可串行性        42
3.7  視圖可串行性        45
3.7.1  視圖等價和結(jié)果正確性準(zhǔn)則        46
3.7.2  檢測視圖可串行性的復(fù)雜性        47
3.8  沖突可串行性        51
3.8.1  沖突關(guān)系        51
3.8.2  CSR類        52
3.8.3  沖突和交換性        54
3.8.4  沖突可串行性的約束        56
3.9  提交可串行性        57
3.10  一個可選的正確性準(zhǔn)則：交叉存取說明        60
3.11  小結(jié)        65
習(xí)題        66
文獻注釋        67
第4章  并發(fā)控制算法        69
4.1  目標(biāo)和概述        69
4.2  通用調(diào)度器的設(shè)計        69
4.3  鎖調(diào)度器        72
4.3.1  簡介        72
4.3.2  兩階段封鎖協(xié)議        74
4.3.3  死鎖處理        77
4.3.4  2PL的變體        79
4.3.5  有序的共享鎖        80
4.3.6  利它鎖        83
4.3.7  非兩階段封鎖協(xié)議        86
4.3.8  封鎖的幾何學(xué)意義        89
4.4  非封鎖調(diào)度器        91
4.4.1  時間戳排序        91
4.4.2  串行化圖的檢測        92
4.4.3  樂觀協(xié)議        94
4.5  混合協(xié)議        96
4.6  小結(jié)        98
習(xí)題        99
文獻注釋        100
第5章  多版本并發(fā)控制        101
5.1  目標(biāo)和概述        101
5.2  多版本調(diào)度        101
5.3  多版本可串行性        103
5.3.1  多版本視圖可串行性        103
5.3.2  MVSR成員資格檢測        105
5.3.3  多版本沖突可串行性        107
5.4  限制版本的數(shù)目        109
5.5  多版本并發(fā)控制協(xié)議        110
5.5.1  MVTO協(xié)議        110
5.5.2  MV2PL協(xié)議        111
5.5.3  MVSGT協(xié)議        114
5.5.4  只讀事務(wù)的多版本協(xié)議        115
5.6  小結(jié)        116
習(xí)題        116
文獻注釋        117
第6章  對象上的并發(fā)控制：正確性概念        119
6.1  目標(biāo)和概述        119
6.2  歷史和調(diào)度        119
6.3  平面對象事務(wù)的沖突可串行性        122
6.4  樹可歸約性        125
6.5  樹可歸約的充分條件        128
6.6  采用基于狀態(tài)的可交換性        132
6.7  小結(jié)        135
習(xí)題        136
文獻注釋        137
第7章  對象上的并發(fā)控制算法        139
7.1  目標(biāo)和概述        139
7.2  平面對象事務(wù)封鎖        139
7.3  分層鎖        140
7.4  通用事務(wù)森林上的封鎖        144
7.5  混合算法        146
7.6  為返回值的可交換性加鎖和契約鎖        147
7.7  小結(jié)        150
習(xí)題        151
文獻注釋        151
第8章  關(guān)系數(shù)據(jù)庫的并發(fā)控制        153
8.1  目標(biāo)和概述        153
8.2  面向謂詞的并發(fā)控制        154
8.3  關(guān)系的更新事務(wù)        157
8.3.1  語法和語義        158
8.3.2  可交換性和簡化規(guī)則        159
8.3.3  歷史和最終狀態(tài)的可串行性        160
8.3.4  沖突可串行性        161
8.3.5  擴展的沖突可串行性        162
8.3.6  在函數(shù)依賴面前的可串行性        163
8.3.7  小結(jié)        165
8.4  應(yīng)用事務(wù)程序知識        165
8.4.1  范例        166
8.4.2  事務(wù)分割        167
8.4.3  切割的適用性        169
8.5  小結(jié)        171
習(xí)題        171
文獻注釋        173
第9章  搜索結(jié)構(gòu)上的并發(fā)控制        174
9.1  目標(biāo)和概述        174
9.2  B+樹搜索結(jié)構(gòu)的實現(xiàn)        175
9.3  訪問層的鍵范圍封鎖        178
9.4  頁層的技術(shù)        183
9.4.1  鎖耦合        184
9.4.2  鏈接技術(shù)        189
9.4.3  放棄技術(shù)        190
9.5  進一步的優(yōu)化        191
9.5.1  無死鎖的頁閂鎖        191
9.5.2  增強的鍵范圍并發(fā)        191
9.5.3  降低封鎖開銷        192
9.5.4  利用暫態(tài)版本化        193
9.6  小結(jié)        193
習(xí)題        194
文獻注釋        195
第10章  實現(xiàn)和實用性問題        196
10.1  目標(biāo)和概述        196
10.2  鎖管理器的數(shù)據(jù)結(jié)構(gòu)        196
10.3  多粒度封鎖和動態(tài)提升        197
10.4  暫態(tài)版本化        199
10.5  事務(wù)內(nèi)部并行的嵌套事務(wù)        201
10.6  調(diào)整選項        201
10.6.1  手動封鎖        202
10.6.2  SQL的隔離級別        202
10.6.3  短事務(wù)        204
10.6.4  多道程序級別的限制        206
10.7  過載控制        207
10.7.1  反饋驅(qū)動方法        208
10.7.2  等待深度限制        210
10.8  小結(jié)        210
習(xí)題        211
文獻注釋        211
第三部分  恢      復(fù)
第11章  事務(wù)恢復(fù)        213
11.1  目標(biāo)和概述        213
11.2  帶有顯式Undo操作的擴展調(diào)度        214
11.2.1  概念的直覺和概述        214
11.2.2  形式化模型        214
11.3  頁模型的正確性準(zhǔn)則        216
11.3.1  擴展沖突可串行性        216
11.3.2  可歸約性與前綴可歸約性        217
11.4  充分的句法條件        219
11.4.1  可恢復(fù)性        220
11.4.2  避免級聯(lián)中止        220
11.4.3  嚴(yán)格性        221
11.4.4  嚴(yán)厲性        221
11.4.5  日志可恢復(fù)性        224
11.5  帶有事務(wù)中止的頁模型調(diào)度協(xié)議        227
11.5.1  為實現(xiàn)嚴(yán)格性和嚴(yán)厲性擴展兩階段封鎖協(xié)議        227
11.5.2  為日志可恢復(fù)性擴展串行圖檢測        227
11.5.3  為日志可恢復(fù)性擴展其他協(xié)議        229
11.6  對象模型的正確性準(zhǔn)則        229
11.6.1  平面對象調(diào)度中的中止        229
11.6.2  通用對象模型中的完全中止和部分中止        234
11.7  帶有事務(wù)中止的對象模型調(diào)度協(xié)議        237
11.8  小結(jié)        237
習(xí)題        237
文獻注釋        239
第12章  崩潰恢復(fù)：正確性概念        241
12.1  目標(biāo)和概述        241
12.2  系統(tǒng)體系結(jié)構(gòu)和接口        243
12.3  系統(tǒng)模型        244
12.4  正確性準(zhǔn)則        246
12.5  算法路線圖        248
12.6  小結(jié)        250
習(xí)題        251
文獻注釋        251
第13章  頁模型崩潰恢復(fù)算法        252
13.1  目標(biāo)和概述        252
13.2  基本數(shù)據(jù)結(jié)構(gòu)        253
13.3  重做勝者范型        256
13.3.1  正常操作期間的操作        256
13.3.2  簡單的三遍掃描（三趟）算法        259
13.3.3  增強算法：日志截斷、檢查點、重做優(yōu)化        269
13.3.4  完整的算法：處理事務(wù)中止和撤銷完成        281
13.4  重做歷史范型        288
13.4.1  正常操作期間的操作        288
13.4.2  簡單的三趟算法和兩趟算法        288
13.4.3  增強的算法：日志截斷、檢查點和重做優(yōu)化        294
13.4.4  完整的算法：處理事務(wù)回滾和撤銷完成        294
13.5  小結(jié)        299
習(xí)題        306
文獻注釋        308
第14章  對象模型的故障恢復(fù)        309
14.1  目標(biāo)和概述        309
14.2  重做歷史算法的概念綜述        309
14.3  一個簡單的兩層系統(tǒng)的重做歷史算法        311
14.3.1  正常操作期間的操作        312
14.3.2  重啟期間的操作        313
14.4  一個增強的兩層系統(tǒng)的重做歷史算法        316
14.5  一個完整的通用對象模型執(zhí)行的重做歷史算法        322
14.6  小結(jié)        324
習(xí)題        325
文獻注釋        327
第15章  恢復(fù)的特別問題        328
15.1  目標(biāo)和概述        328
15.2  索引和大對象的日志和恢復(fù)        328
15.2.1  重做索引頁分裂的邏輯日志條目        328
15.2.2  大對象操作的邏輯日志條目和刷出順序        331
15.3  事務(wù)內(nèi)部保存點和嵌套事務(wù)        334
15.4  在重啟過程中使用并行性        338
15.5  對主存數(shù)據(jù)服務(wù)器的特殊考慮        339
15.6  數(shù)據(jù)共享機群的擴展        341
15.7  小結(jié)        344
習(xí)題        344
文獻注釋        346
第16章  介質(zhì)恢復(fù)        347
16.1  目標(biāo)和概述        347
16.2  基于日志的方法        348
16.2.1  正常操作期間的數(shù)據(jù)備份和歸檔日志        349
16.2.2  數(shù)據(jù)庫恢復(fù)算法        351
16.2.3  對平均數(shù)據(jù)丟失時間的分析        352
16.3  存儲冗余        355
16.3.1  基于鏡像的技術(shù)        355
16.3.2  基于糾錯碼的技術(shù)        357
16.4  災(zāi)難恢復(fù)        363
16.5  小結(jié)        364
習(xí)題        364
文獻注釋        365
第17章  應(yīng)用恢復(fù)        366
17.1  目標(biāo)和概述        366
17.2  基于隊列的無狀態(tài)應(yīng)用        367
17.3  基于隊列的有狀態(tài)應(yīng)用        372
17.4  基于隊列的工作流        374
17.4.1  故障可恢復(fù)工作流的狀態(tài)和上下文        375
17.4.2  基于排隊事務(wù)的分散工作流        376
17.5  一般的有狀態(tài)應(yīng)用        377
17.5.1  設(shè)計上考慮的事項        378
17.5.2  服務(wù)器應(yīng)答日志算法綜述        380
17.5.3  數(shù)據(jù)結(jié)構(gòu)        381
17.5.4  正常操作期間的服務(wù)器日志活動        382
17.5.5  正常操作期間的客戶端日志活動        384
17.5.6  日志截斷        385
17.5.7  服務(wù)器重啟        387
17.5.8  客戶端重啟        388
17.5.9  正確性推理        390
17.5.10  對于多層體系結(jié)構(gòu)的適用性        393
17.6  小結(jié)        393
習(xí)題        394
文獻注釋        394
第四部分  分布式事務(wù)的協(xié)調(diào)
第18章  分布式并發(fā)控制        397
18.1  目標(biāo)和概述        397
18.2  同構(gòu)聯(lián)邦中的并發(fā)控制        398
18.2.1  預(yù)備知識        399
18.2.2  分布式2PL        400
18.2.3  分布式TO        401
18.2.4  分布式SGT        402
18.2.5  樂觀協(xié)議        403
18.3  分布式死鎖檢測        404
18.4  異構(gòu)聯(lián)邦中的可串行性        406
18.4.1  全局歷史        407
18.4.2  全局可串行性        408
18.4.3  準(zhǔn)可串行性        410
18.5  通過本地的保證獲得全局可串行性        411
18.5.1  嚴(yán)厲性        411
18.5.2  提交排序        412
18.6  基于ticket的并發(fā)控制        413
18.6.1  強迫沖突的顯式ticket        413
18.6.2  隱式ticket        415
18.6.3  顯示和隱式ticket的結(jié)合        415
18.7  異構(gòu)聯(lián)邦中對象模式的并發(fā)控制        416
18.8  數(shù)據(jù)共享系統(tǒng)的一致性和并發(fā)控制        417
18.9  小結(jié)        420
習(xí)題        421
文獻注釋        422
第19章  分布式事務(wù)恢復(fù)        424
19.1  目標(biāo)和概述        424
19.2  基本的兩階段提交算法        425
19.2.1  2PC協(xié)議        425
19.2.2  重啟和終止協(xié)議        430
19.2.3  獨立恢復(fù)        435
19.3  事務(wù)樹兩階段提交算法        436
19.4  分布式提交的優(yōu)化算法        439
19.4.1  假設(shè)中止協(xié)議和假設(shè)提交協(xié)議        439
19.4.2  只讀子樹的優(yōu)化        443
19.4.3  協(xié)調(diào)者轉(zhuǎn)移        445
19.4.4  減少阻塞        447
19.5  小結(jié)        448
習(xí)題        449
文獻注釋        450
第五部分  應(yīng)用與未來前景
第20章  下一步是什么        453
20.1  目標(biāo)和概述        453
20.2  我們完成了什么        453
20.2.1  開發(fā)者可用的解決方案        453
20.2.2  高級的系統(tǒng)搭建者可用的最新技術(shù)        454
20.2.3  研究人員的方法學(xué)和新的挑戰(zhàn)        455
20.3  用于普遍訪問的數(shù)據(jù)復(fù)制        455
20.4  電子服務(wù)和工作流        457
20.5  性能和可用性保證        460
文獻注釋        462
參考文獻        464