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

第一部分  背景與動機
第1章  概述        1
1.1  目標和概述        1
1.2  應用舉例        2
1.2.1  聯(lián)機事務處理：借/貸的例子        2
1.2.2  電子商務的例子        5
1.2.3  工作流管理：旅行計劃的例子        6
1.3  系統(tǒng)范型        8
1.3.1  三層體系結(jié)構(gòu)和兩層體系結(jié)構(gòu)        8
1.3.2  服務器的聯(lián)合        11
1.4  事務概念的優(yōu)點        12
1.4.1  事務特性與事務編程接口        12
1.4.2  事務服務器的功能需求        14
1.5  數(shù)據(jù)庫服務器的概念與體系結(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
習題        21
文獻注釋        21
第2章  計算模型        23
2.1  目標和概述        23
2.2  計算模型的組成部分        23
2.3  頁模型        24
2.4  對象模型        27
2.5  本書的“路線圖”        30
2.6  小結(jié)        31
習題        31
文獻注釋        32
第二部分  并 發(fā) 控 制
第3章  并發(fā)控制：頁模型正確性的概念        33
3.1  目標和概述        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é)果正確性準則        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  小結(jié)        65
習題        66
文獻注釋        67
第4章  并發(fā)控制算法        69
4.1  目標和概述        69
4.2  通用調(diào)度器的設計        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  封鎖的幾何學意義        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
習題        99
文獻注釋        100
第5章  多版本并發(fā)控制        101
5.1  目標和概述        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  只讀事務的多版本協(xié)議        115
5.6  小結(jié)        116
習題        116
文獻注釋        117
第6章  對象上的并發(fā)控制：正確性概念        119
6.1  目標和概述        119
6.2  歷史和調(diào)度        119
6.3  平面對象事務的沖突可串行性        122
6.4  樹可歸約性        125
6.5  樹可歸約的充分條件        128
6.6  采用基于狀態(tài)的可交換性        132
6.7  小結(jié)        135
習題        136
文獻注釋        137
第7章  對象上的并發(fā)控制算法        139
7.1  目標和概述        139
7.2  平面對象事務封鎖        139
7.3  分層鎖        140
7.4  通用事務森林上的封鎖        144
7.5  混合算法        146
7.6  為返回值的可交換性加鎖和契約鎖        147
7.7  小結(jié)        150
習題        151
文獻注釋        151
第8章  關系數(shù)據(jù)庫的并發(fā)控制        153
8.1  目標和概述        153
8.2  面向謂詞的并發(fā)控制        154
8.3  關系的更新事務        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  應用事務程序知識        165
8.4.1  范例        166
8.4.2  事務分割        167
8.4.3  切割的適用性        169
8.5  小結(jié)        171
習題        171
文獻注釋        173
第9章  搜索結(jié)構(gòu)上的并發(fā)控制        174
9.1  目標和概述        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
習題        194
文獻注釋        195
第10章  實現(xiàn)和實用性問題        196
10.1  目標和概述        196
10.2  鎖管理器的數(shù)據(jù)結(jié)構(gòu)        196
10.3  多粒度封鎖和動態(tài)提升        197
10.4  暫態(tài)版本化        199
10.5  事務內(nèi)部并行的嵌套事務        201
10.6  調(diào)整選項        201
10.6.1  手動封鎖        202
10.6.2  SQL的隔離級別        202
10.6.3  短事務        204
10.6.4  多道程序級別的限制        206
10.7  過載控制        207
10.7.1  反饋驅(qū)動方法        208
10.7.2  等待深度限制        210
10.8  小結(jié)        210
習題        211
文獻注釋        211
第三部分  恢      復
第11章  事務恢復        213
11.1  目標和概述        213
11.2  帶有顯式Undo操作的擴展調(diào)度        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  避免級聯(lián)中止        220
11.4.3  嚴格性        221
11.4.4  嚴厲性        221
11.4.5  日志可恢復性        224
11.5  帶有事務中止的頁模型調(diào)度協(xié)議        227
11.5.1  為實現(xiàn)嚴格性和嚴厲性擴展兩階段封鎖協(xié)議        227
11.5.2  為日志可恢復性擴展串行圖檢測        227
11.5.3  為日志可恢復性擴展其他協(xié)議        229
11.6  對象模型的正確性準則        229
11.6.1  平面對象調(diào)度中的中止        229
11.6.2  通用對象模型中的完全中止和部分中止        234
11.7  帶有事務中止的對象模型調(diào)度協(xié)議        237
11.8  小結(jié)        237
習題        237
文獻注釋        239
第12章  崩潰恢復：正確性概念        241
12.1  目標和概述        241
12.2  系統(tǒng)體系結(jié)構(gòu)和接口        243
12.3  系統(tǒng)模型        244
12.4  正確性準則        246
12.5  算法路線圖        248
12.6  小結(jié)        250
習題        251
文獻注釋        251
第13章  頁模型崩潰恢復算法        252
13.1  目標和概述        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  完整的算法：處理事務中止和撤銷完成        281
13.4  重做歷史范型        288
13.4.1  正常操作期間的操作        288
13.4.2  簡單的三趟算法和兩趟算法        288
13.4.3  增強的算法：日志截斷、檢查點和重做優(yōu)化        294
13.4.4  完整的算法：處理事務回滾和撤銷完成        294
13.5  小結(jié)        299
習題        306
文獻注釋        308
第14章  對象模型的故障恢復        309
14.1  目標和概述        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
習題        325
文獻注釋        327
第15章  恢復的特別問題        328
15.1  目標和概述        328
15.2  索引和大對象的日志和恢復        328
15.2.1  重做索引頁分裂的邏輯日志條目        328
15.2.2  大對象操作的邏輯日志條目和刷出順序        331
15.3  事務內(nèi)部保存點和嵌套事務        334
15.4  在重啟過程中使用并行性        338
15.5  對主存數(shù)據(jù)服務器的特殊考慮        339
15.6  數(shù)據(jù)共享機群的擴展        341
15.7  小結(jié)        344
習題        344
文獻注釋        346
第16章  介質(zhì)恢復        347
16.1  目標和概述        347
16.2  基于日志的方法        348
16.2.1  正常操作期間的數(shù)據(jù)備份和歸檔日志        349
16.2.2  數(shù)據(jù)庫恢復算法        351
16.2.3  對平均數(shù)據(jù)丟失時間的分析        352
16.3  存儲冗余        355
16.3.1  基于鏡像的技術(shù)        355
16.3.2  基于糾錯碼的技術(shù)        357
16.4  災難恢復        363
16.5  小結(jié)        364
習題        364
文獻注釋        365
第17章  應用恢復        366
17.1  目標和概述        366
17.2  基于隊列的無狀態(tài)應用        367
17.3  基于隊列的有狀態(tài)應用        372
17.4  基于隊列的工作流        374
17.4.1  故障可恢復工作流的狀態(tài)和上下文        375
17.4.2  基于排隊事務的分散工作流        376
17.5  一般的有狀態(tài)應用        377
17.5.1  設計上考慮的事項        378
17.5.2  服務器應答日志算法綜述        380
17.5.3  數(shù)據(jù)結(jié)構(gòu)        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  對于多層體系結(jié)構(gòu)的適用性        393
17.6  小結(jié)        393
習題        394
文獻注釋        394
第四部分  分布式事務的協(xié)調(diào)
第18章  分布式并發(fā)控制        397
18.1  目標和概述        397
18.2  同構(gòu)聯(lián)邦中的并發(fā)控制        398
18.2.1  預備知識        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  準可串行性        410
18.5  通過本地的保證獲得全局可串行性        411
18.5.1  嚴厲性        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
習題        421
文獻注釋        422
第19章  分布式事務恢復        424
19.1  目標和概述        424
19.2  基本的兩階段提交算法        425
19.2.1  2PC協(xié)議        425
19.2.2  重啟和終止協(xié)議        430
19.2.3  獨立恢復        435
19.3  事務樹兩階段提交算法        436
19.4  分布式提交的優(yōu)化算法        439
19.4.1  假設中止協(xié)議和假設提交協(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
習題        449
文獻注釋        450
第五部分  應用與未來前景
第20章  下一步是什么        453
20.1  目標和概述        453
20.2  我們完成了什么        453
20.2.1  開發(fā)者可用的解決方案        453
20.2.2  高級的系統(tǒng)搭建者可用的最新技術(shù)        454
20.2.3  研究人員的方法學和新的挑戰(zhàn)        455
20.3  用于普遍訪問的數(shù)據(jù)復制        455
20.4  電子服務和工作流        457
20.5  性能和可用性保證        460
文獻注釋        462
參考文獻        464