【正文】 tiversion TwoPhase Locking ? Readonly transactions that start after Ti increments tscounter will see the values updated by Ti 后面的其它只讀事務只看見更新后的數(shù)據(jù) ? Readonly transactions that start before Ti increments the tscounter will see the value before the updates by Ti. 之前的其它只讀事務可以看到更新提交前的數(shù)據(jù) ? Only serializable schedules are produced 因此只產(chǎn)生可串行的調度 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 死鎖處理 ? 考慮下列兩個事務 : T1: write (X) T2: write(Y) write(Y) write(X) ? 有死鎖的調度 T1 T2 lockX on X write (X) lockX on Y write (Y) wait for lockX on X wait for lockX on Y 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 死鎖處理 ? 如果有一個事務集合使得集合中的每個事務都在等待集合中的另一個事務 , 則系統(tǒng)死鎖 ? 死鎖預防 協(xié)議確保系統(tǒng)永遠不會進入死鎖狀態(tài) . 一些預防策略如下 : ?要求每個事務在開始執(zhí)行為其所有數(shù)據(jù)項加鎖 (預聲明 ),即每個事務鎖定所需資源才開始 ?施加所有數(shù)據(jù)項上的偏序 , 并要求一個事務只能按偏序指定的次序鎖數(shù)據(jù)項 (基于圖的協(xié)議 ) ?直觀解釋 :修房子不要邊施工， 邊申請地皮、水、電、氣 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 更多死鎖預防策略 ? 下列方案僅為死鎖預防目的使用事務時間戳 ? 等待 死亡 方案 — 非搶占式 ?老事務可能等待年輕事務釋放數(shù)據(jù)項 . 年輕事務永遠不會等待老事務 , 而是回滾 . ?一個事務可能在獲得所需數(shù)據(jù)項之前死亡若干次 ? 擊傷 等待 方案 — 搶占式 ?老事務擊傷 (強制回滾 )年輕事務而不是等待它 ?年輕事務可能等待老事務 ?可能比等待 死亡方案有較少的回滾 ? 在 waitdie 和 woundwait 方案中 , 回滾的事務重啟動時帶有原來的時間戳 . 老事務因此具有對新事務的優(yōu)先級 , 故避免了餓死 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 死鎖預防 ?基于超時的方案 （不耐煩法） ?事務對一個鎖只等待一個指定的時間量 . 此后 , 等待超時 , 事務回滾 . ?因此死鎖是不可能的 ?實現(xiàn)簡單，但可能有餓死 . 另外難以確定合適的超時間隔 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 死鎖檢測 ?死鎖可用 等待圖 描述 , 即一個二元組 G = (V,E), ?V 是頂點集合 (即系統(tǒng)中的所有事務 ) ?E 是邊的集合 。 其中每個元素是一有序對 Ti ?Tj. ?若 Ti ? Tj 屬于 E, 則存在從 Ti 到 Tj 的有向邊 , 意味著 Ti 等待 Tj 釋放數(shù)據(jù)項 ?當 Ti 請求一個正被 Tj 持有的數(shù)據(jù)項時 , 邊 Ti Tj 被插入到等待圖中 . 僅當 Tj 不再持有 Ti 所需的數(shù)據(jù)項時 , 這條邊才被刪除 ?系統(tǒng)處于死鎖狀態(tài)當且僅當?shù)却龍D有圈 . 必須周期性地調用死鎖檢測算法來查找圈 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 死鎖檢測 沒有圈的等待圖 有圈的等待圖 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 死鎖恢復 ?當檢測到死鎖時 ?某些事務必須回滾 (作為犧牲品 ) 來打破死鎖 . 選擇導致最小代價的事務作為犧牲品 ?回滾 – 決定事務回滾多遠 ?完全回滾 : 夭折事務并重啟動 ?更有效的是只做為打破死鎖所必須的回滾 ?若同一事務總是被選為犧牲品則發(fā)生了餓死 . 在代價因子中包括回滾次數(shù)以避免餓死 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 插入與刪除操作 ?如果使用兩階段鎖 ?僅當刪除元組的事務對刪除元組具有排他鎖時 , delete 操作才可以被執(zhí)行 ?向數(shù)據(jù)庫插入一條新元組的事務對該元組獲得 X鎖 ?插入和刪除可能導致 幻影現(xiàn)象 ?掃描關系的事務 (例如查找所有 Perryridge的賬戶 ) 和向關系中插入元組的事務 (例如在 Perryridge插入一條新元組 )盡管不存取任何共同的元組也可能沖突 ?類似于還沒釣到魚，就談論是紅燒，還是清蒸 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 插入與刪除操作 ? 掃描關系的事務正在讀指明“關系中包含什么元組”的信息 , 而插入元組的事務則更新這同一信息 ,因此該信息應該封鎖 . ? 一種解決方法 : ?將關系與一個數(shù)據(jù)項相關聯(lián) , 該數(shù)據(jù)項表示“關系中包含什么元組”的信息 ?掃描關系的事務獲得該數(shù)據(jù)項上的共享鎖 ?插入或刪除元組的事務獲得該數(shù)據(jù)項上的排他鎖 . (注 : 該數(shù)據(jù)項上的鎖與各個元組上的鎖不沖突 .) ? 上述協(xié)議對插入 /刪除操作提供了較低的并發(fā)性 ? 索引封鎖協(xié)議 提供了較高的并發(fā)性同時防止了幻影現(xiàn)象 , 此協(xié)議要求對某些對索引桶加鎖 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 索引封鎖協(xié)議 ? 前提 : 每個關系必須具有至少一個索引 , 對關系的存取只能通過關系上的一個索引進行 ? 執(zhí)行查找的事務 Ti 必須以共享方式鎖住它存取的所有索引桶 ? 執(zhí)行插入的事務 Ti 在更新所有 r 上索引之前不能向關系r 中插入元組 ti ? 執(zhí)行更新的事務 Ti 必須對每個索引執(zhí)行查找以找到所有可能包含指向元組 ti 的指針的索引桶 , 如果已經(jīng)存在的話 , Ti 還必須獲得它所更新的所有索引桶上的 X鎖 . ? 必須遵守兩階段封鎖協(xié)議 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 弱一致性級別 ? 二級一致性 : 不同于兩階段封鎖 , S鎖可以隨時釋放 , 并且鎖可以在任何時候獲得 ?X鎖必須保持到事務結束 ?不能保證可串行化 , 程序員必須確保不會發(fā)生錯誤的數(shù)據(jù)庫狀態(tài) ? 游標穩(wěn)定性 : ?對于讀操作 , 對每條元組加 S鎖 , 讀 , 立即釋放鎖 ?X鎖持有到事務結束 ?二級一致性的特例 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition SQL中的弱一致性級別（略） ? SQL92允許非可串行化的執(zhí)行 ?可串行化 : 默認級別 ?可重復讀 : 只允許讀已提交記錄 , 并且事務中的重復讀應返回相同的值 (因此讀鎖應該保持 ) ?然而 , 不需要防止幻影現(xiàn)象 – T1 可以看到 T2插入的某些記錄 , 但可能看不到T2插入的另一些記錄 ?讀已提交 : 與二級一致性相同 , 但是多數(shù)系統(tǒng)將它實現(xiàn)為游標穩(wěn)定性 ?讀未提交 : 允許讀到未提交數(shù)據(jù) 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition Concurrency in Index Structures ? 索引結構的并發(fā)， 無方法性或思想性的要點 (略或自學 ) ? Indices are unlike other database items in that their only job is to help in accessing data. ? Indexstructures are typically accessed very often, much more than other database items. ? Treating indexstructures like other database items leads to low concurrency. Twophase locking on an index may result in transactions executing practically oneatatime. ? It is acceptable to have nonserializable concurrent access to an index as long as the accuracy of the index is maintained. ? In particular, the exact values read in an internal node of a B+tree are irrelevant so long as we land up in the correct leaf node. ? There are index concurrency protocols where locks on internal nodes are released early, and not in a twophase fashion. 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition Concurrency in Index Structures (Cont.) ? Example of index concurrency protocol: ? Use crabbing instead of twophase locking on the nodes of the B+tree, as follows. During search/insertion/deletion: ? First lock the root node in shared mode. ? After locking all required children of a node in shared mode, release the lock on the node. ? During insertion/deletion, upgrade leaf node locks to exclusive mode. ? When splitting or coalescing requires changes to a parent, lock the parent in exclusive mode. ? Above protocol can cause excessive deadlocks. Better protocols are available。 see Section for one such protocol, the Blink tree protocol End of Chapter 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 任務 : Derby 并發(fā)控制實現(xiàn)分析 ?參考 : ?Derby v10 source cod