《数据库系统概念》学习笔记——恢复系统
數據庫系統概念——恢復系統
- 恢復系統
- 故障分類
- 存儲器
- 穩定存儲器的實現
- 數據訪問
- 恢復與原子性
- 日志記錄
- 數據庫修改
- 并發控制和恢復
- 事務提交
- 使用日志來重做和撤銷事務
- 檢查點
- 恢復算法
- 事務回滾
- 系統崩潰后的恢復
- 緩沖區管理
- 日志記錄緩沖
- 數據庫緩沖
- 操作系統在緩沖區管理中的作用
- 模糊檢查點
- 非易失性存儲器數據丟失的故障
- 鎖的前提釋放和邏輯 undo 操作
- 邏輯操作
- 邏輯 undo 日志記錄
- 有邏輯 undo 的事務回滾
- 遠程備份系統
恢復系統
故障的原因包括:磁盤故障、電源故障、軟件錯誤、人為破壞等。
數據庫系統必須預先采取措施,以保證即使發生故障,也能保證事務的原子性,持久性。
恢復機制用于將數據庫在遭遇故障時,將其恢復到故障發生前的一致性狀態。
恢復機制還提供高可用性,即:它必須將數據庫崩潰后不能使用的詩句縮減到最短。
故障分類
-
事務故障
有兩種錯誤可能造成事務執行失敗:
邏輯錯誤。 事務由于某些內部條件而無法繼續正常執行,這樣的內部條件如非法輸入、找不到數據、溢出或超出資源限制。
系統錯誤。 系統進入一種不良狀態(如死鎖),結果事務無法繼續正常執行。但該事務可以在以后的某個時間重新執行。 -
系統崩潰
硬件錯誤,或者是數據庫軟件或操縱系統的漏洞,導致易失性存儲器內容的丟失,并使得事務處理停止。而非易失性存儲器仍完好無損。
硬件錯誤和軟件漏洞致使系統終止,而不破壞非易失性存儲器內容的假設稱為故障-停止假設。 -
磁盤故障
在數據傳送操作過程中由于磁頭損壞或故障造成磁盤塊上的內容丟失。
其他磁盤上的數據拷貝,或三級介質(如DVD或磁帶)上的歸檔備份可用于從這種故障中恢復。
故障發生后仍保證數據庫一致性以及事務原子性的算法,稱為恢復算法。由兩部分組成:
- 1.在正常事務處理時采取措施,保證有足夠信息用于故障恢復。
- 2.故障發生后采取措施,將數據庫內容恢復到某個保證數據庫一致性、事務原子性及持久性的狀態。
存儲器
存儲器分為以下三類:
- 易失性存儲器
- 非易失性存儲器
- 穩定存儲器
穩定存儲器,或更準確地說是接近穩定的存儲器,在恢復算法中起到至關重要的作用。
穩定存儲器的實現
在多個非易失性存儲介質(通常是磁盤)上以獨立的故障模式復制信息,并且以受控的方式更新信息,以保證數據傳送過程中發生的故障不破壞所需信息。
最簡單并且最快的RAID形式是磁盤鏡像,即在不同的磁盤上為每個磁盤塊保存兩個拷貝。
更安全的系統遠程為文檔存儲器的每一個塊保存一份拷貝,除在本地磁盤系統進行塊存儲外,還通過計算機網絡寫到遠程去。
由于在往本地存儲器輸出塊的同時也要輸出到遠程系統,一旦輸出操作完成,即使發生火災或洪水這樣的災難,輸出結果也不會丟失。即遠程備份系統。
在內存和磁盤存儲器間進行塊傳送有以下幾種可能結果:
- 成功完成
傳送的信息安全地到達目的地。 - 部分失敗
傳送過程中發生故障,目標塊有不正確信息。 - 完全失敗
傳送過程中故障發生得足夠早,目標塊仍完好無缺。
要求,如果數據傳送故障發生,系統能檢測到且調用恢復過程將塊恢復為一致的狀態。
系統需為每個邏輯數據庫塊維護兩個物理塊。
若是鏡像磁盤,則兩個塊在同一個地點;若是遠程備份,則一個塊在本地,另一個在遠程節點。
輸出操作的執行如下:
恢復過程:
對于每一個塊,系統需要檢查它的兩個拷貝。如果他們相同并且沒有檢測到錯誤存在,則不需要采取進一步動作。
如果系統檢測到一個塊中有錯誤,則可以用兩一個塊的內容替換這一塊的內容。如果兩個塊都沒有檢測出錯誤,但它們的內容不一致,則我們用第二塊的值替換第一塊的內容,或者用第一塊的值替換第二塊的內容。
上述方法可保證寫操作,要么完全成功,要么完全失敗。
數據訪問
假設沒有數據項跨越多個塊。
事務由磁盤向主存輸入信息,然后再將信息輸出回磁盤。
輸入和輸出操作以塊為單位完成。
位于磁盤上的塊稱為物理塊,臨時位于主存的塊稱為緩沖塊。
內存中用于臨時存放塊的區域稱為磁盤緩沖區。
磁盤和主存間的塊移動是由下面兩個操作引發的:
- input(B)
將物理塊B送至內存。 - output(B)
將緩沖塊B送至磁盤,并替換磁盤上相應的物理塊。
每個事務有一個私有工作區,用于保持事務訪問和更新的數據項的拷貝。
事務提交或中止時,由系統刪除。
read(X)
a. 若X所在的塊BxB_xBx?不在主存中,執行input(Bx)input(B_{x})input(Bx?),將包含x的塊讀入主存。
b. 將緩沖塊中X的值賦予xix_ixi?。
write(X)
a. 若X所在的塊BxB_xBx?不在主存中,執行input(Bx)input(B_{x})input(Bx?),將包含x的塊讀入主存。
b. 將xix_ixi?的值賦予緩沖塊BxB_xBx?中的X。
如果數據庫系統發指令執行output(Bx)output(B_{x})output(Bx?),稱對緩沖塊B執行強制輸出。
數據庫系統執行額外的動作來保證,即使發生了系統崩潰,由提交的事務所做的更新也不會丟失。
恢復與原子性
修改數據庫本身前,先向穩定存儲器輸出信息,描述要做的修改。
輸出的信息能幫助我們確保已提交事務做的所有修改都反映到數據庫中(或者在故障后的恢復過程中反映到數據庫中)。
這種信息還能幫助我們確保中止事務所做的任何修改都不會持久存在于數據庫中。
日志記錄
日志是日志記錄的序列,它記錄數據庫中的所有更新活動。
日志記錄有幾種。
更新日志記錄描述一次數據庫寫操作,它具有如下幾個字段:
- 事務標識
執行write操作的事務的唯一標識。 - 數據項標識
是所寫數據項的唯一標識。
通常是數據項在磁盤上的位置,包括數據項所駐留的塊的塊標識和塊內偏移量。 - 舊值
是數據項的寫前值。 - 新值
是數據項的寫后值。
日志記錄類型:
- < TiT_iTi? start >
表示事務的開始 - < TiT_iTi? commit >
表示事務的提交 - < TiT_iTi? abort >
表示事務的中止
每次事務執行寫操作時,必須在數據庫修改前建立該次寫操作的日志記錄并把它加到日志中。再實際執行寫數據庫。
日志記錄讓我們有能力進行操作的撤銷、重做。
日志需放在穩定存儲器中。
數據庫修改
事務在對數據庫進行修改前創建了一個日志記錄。
日志記錄使得系統在事務必須中止的情況下能夠對事務所做的修改進行撤銷;并且在事務已經提交但在修改已存放到磁盤上的數據庫中之前系統崩潰的情況下能夠對事務所做的修改進行重做。
事務執行數據項修改的步驟:
如果事務對磁盤緩沖區內的塊或磁盤自身進行了更新,則稱其修改了數據庫。
如果僅在主存中對事務私有部分進行修改,則不算對數據庫的修改。
事務提交時,若仍然沒修改數據庫,稱其采用了延遲修改技術。
這種情況下,事務對修改的數據項,先拷貝一份到事務私有部分,之后指向和修改其私有部分。
事務執行中,即修改了數據塊,稱其采用了立即修改技術。
恢復算法必須考慮多種因素,包括:
- 有可能事務已經提交,但其修改仍然在磁盤緩沖區,而非磁盤上數據庫中。
- 有可能一個事務已經修改了數據庫,但執行了某一步需要中止。
由于所有的數據庫修改之前必須建立日志記錄,因此系統有數據項修改前的舊值和要寫給數據項的新值可以用。
- undo
使用一個日志記錄,將指明的數據項設為舊值 - redo
使用一個日志記錄,將指明的數據項設為新值
并發控制和恢復
一般,數據項X被事務A修改了,則在A提交或中止前,不允許其他事務修改X。
對更新數據項X申請排他鎖,事務提交時才釋放鎖。
事務提交
當一個事務的 commit 日志記錄為該事務的最后一個日志記錄,輸出到文檔存儲器后,就稱事務提交了。
此后,即使系統崩潰,事務所做的更新也可重做。
如果在事務的commit日志記錄輸出到穩定存儲器前,崩潰,則事務回滾。
包含 commit 日志記錄的塊的輸出是當原子動作,它導致了事務的提交。
事務提交時事務修改的緩沖區塊,可以立即寫入文檔存儲器,也可后續寫入。
使用日志來重做和撤銷事務
- redo(T)
將事務T更新過的所有數據項的值都設為新值。
掃描日志,對掃描范圍的每個日志記錄逐個處理。 - undo(T)
將事務T更新過的所有數據項的值都設為舊值。- 撤銷過程也產生日志記錄(redo-only日志記錄)。
- 對事務T的undo操作完成后,寫一個日志記錄,表示撤銷完成。
每個事務在日志中,最終要么有一個commit,要么有一個abort。
發生系統崩潰之后,系統查閱日志以確定為保證原子性需要對哪些事務進行重做,對哪些事務進行撤銷。
- 如果日志中含 <T start>記錄,但既不含<T commit>又不含記錄,則需對T執行撤銷。
- 如果日志中含<T start>記錄,以及<T commit>或<T abort>記錄,需對T進行重做.
如果在日志中有<T abort>,意味著日志中有undo操作所產生的redo-only日志記錄;對其重做意味著對T的撤銷。
若崩潰重啟后,日志如a所示,則對T0T_{0}T0?執行撤銷,撤銷后A為1000, B為2000。
若崩潰重啟后,日志如b所示,則對T1T_{1}T1?執行撤銷,對T0T_{0}T0?執行重做.處理后A為950,B為2050,C為700。
若崩潰重啟后,日志如c所示,則對T0T_{0}T0?,T1T_{1}T1?執行重做,處理后A為950,B為2050,C為600。
檢查點
當系統故障發生時,我們必須檢查日志,決定哪些事務需要重做,哪些需要撤銷。
原則上,需要搜索整個日志來確定該信息。這樣做有兩個主要的困難:
為降低這種開銷,引入檢查點。
一個簡單的檢查點:它在執行檢查點操作的過程中不允許執行任何更新,在執行檢查點的過程中將所有更新過的緩沖塊都輸出到磁盤。
檢查點具體執行過程如下:
- 將當前位于主存的所有日志記錄輸出到穩定存儲器。
- 將所有修改的緩沖塊輸出到磁盤。
- 將一個日志記錄<checkpoint L>輸出到文檔存儲器,其中L是執行檢查點時正活躍的事務的列表。
檢查點執行過程,不允許事務執行任何更新動作,如往緩沖塊寫入,寫日志記錄等。
若某事務A的<A commit>記錄在日志中位于記錄前,則恢復時,不必再對A的相關日志記錄進行 redo。
系統崩潰后,系統檢查日志,以找到最后一條<checkpoint L>記錄。
只需對L中的事務,及<checkpoint L>記錄寫到日志中后才開始的事務執行undo或redo。把此事務集合記為T。
對T中任一事務設為A,
1.若日志中無<A commit>和<A abort>記錄,則執行undo(A)。
2.若日志中有<A commit>或<A abort>記錄,則執行 redo(A)。
一旦檢查點完成了,就不再需要L對應事務集合關聯的。
<X start>集合中在日志中最先出現的那個<P start>之前的所有日志記錄,對后續恢復不再有意義,可以從日志文件刪除掉這部分日志記錄。
模糊檢查點,它即使在緩沖塊正在寫出時也允許事務執行更新。
恢復算法
使用日志記錄從事務故障中恢復的完整恢復算法,以及將最近的檢查點和日志記錄集合起來從系統崩潰中進行恢復的算法。
事務回滾
正常操作時的事務T的回滾。
對發現的每個形如<Ti,Xj,V1,V2><T_i, X_j, V_{1}, V_{2}><Ti?,Xj?,V1?,V2?>的日志記錄:
a.值V1V_{1}V1?被寫到數據項X
b.往日志中寫一個特殊的日志記錄<Ti,Xj,V1><T_i, X_j ,V_{1}><Ti?,Xj?,V1?>,其中V1V_1V1?是在本次回滾中數據項XjX_jXj?恢復成的值。
有時這種日志記錄稱為補償日志記錄。
這樣的日志記錄只會在崩潰恢復時被執行redo,不會被執行undo
這樣對事務T
該事務所做的,和對其撤銷所做的每個動作都記錄到了日志.
系統崩潰后的恢復
崩潰發生后當數據庫系統重啟時,恢復動作分兩階段進行:
-
1.在重做階段
系統從最后一個檢查點日志記錄處開始正向掃描日志來重做所有每個掃描到日志記錄所做操作。
這些被重做的事務包含崩潰前已經回滾的事務,崩潰時尚未提交的事務。
掃描過程采取的步驟如下:
a.將要回滾的事務列表undo-list初始設定為<checkpoint L>日志記錄中的 L列表。
b.一旦遇到形如<Ti,Xj,V1,V2><T_i, X_j, V_{1}, V_{2}><Ti?,Xj?,V1?,V2?>的正常日志記錄或形如<Ti,Xj,V2><T_i, X_j, V_{2}><Ti?,Xj?,V2?>的 redo-only 日志記錄,就對其執行重做;即將值V2V_{2}V2?寫給數據項 XjX_jXj?。
c.一旦遇到形如<TiT_iTi? start>的日志記錄,就把T加到undo-list。
d.一旦遇到形如<TiT_iTi? abort>或<TiT_iTi? commit>的日志記錄,就把 TiT_iTi? 從 undo-list 中去掉。redo階段在掃描并處理完崩潰發生時日志中的最后一個日志記錄后結束。
此時undo-list包括在崩潰前尚未完成的所有事務。 -
2.在撤銷階段
系統回滾undo-list中的所有事務。
從日志尾端開始反向掃描日志來執行回滾。
a.一旦發現屬于undo-list中的所有事務,就執行undo操作。就像在一個失敗事務的回滾過程中發現了該日志記錄一樣。
b.系統發現undo-list中事務TiT_iTi?的<TiT_iTi? start>日志記錄時,
就從undo-list中刪除TiT_iTi?,且產生一條<TiT_iTi? abort>形式的日志記錄,寫入日志末尾。
c.一旦 undo-list 變為空表,即系統已經找到了開始時位于 undo-list 中的所有事務的<TiT_iTi? start>日志記錄, 則撤銷階段結束。撤銷階段結束后,即可開始正常的事務處理。
緩沖區管理
日志記錄緩沖
將一個塊輸出到穩定存儲器的開銷非常高,最好是一次輸出多個日志記錄。
將日志記錄寫到主存的日志緩沖區。
穩定存儲器中的日志記錄順序需與寫入日志緩沖區的順序一樣。
由于使用了日志緩沖區,日志記錄在輸出到穩定存儲器前可能有一段時間只存在于主存(易失性存儲器)中。
由于系統發生崩潰時這種日志記錄會丟失,必須對恢復技術增加一些要求以保證事務的原子性:
- 在日志記錄<T commit>輸出到穩定存儲器后,事務T進入提交狀態。
- 在日志記錄、輸出到穩定存儲器前,與T有關的所有日志記錄需已經輸出到穩定存儲器。
- 在主存中的數據塊輸出到數據庫[非易失性存儲器]前,所有與該數據塊中數據有關的日志記錄需已經輸出到穩定存儲器。
將緩沖的日志寫到磁盤有時稱強制日志。
數據庫緩沖
-
強制策略
事務提交時,強制地將修改過的所有塊都輸出到磁盤。 -
非強制策略
提交狀態后,一段時間事務修改的某些塊仍然未寫回磁盤。
非強制策略下不影響正確性(因為日志已經寫入),但有助于減少和磁盤塊輸出次數,也利于事務較快提交。 -
非竊取策略
一個活躍的事務修改過的塊不應寫出到磁盤。 -
竊取策略
允許將活躍事務修改過的塊寫出到磁盤。
竊取下不影響正確性(因為日志已經寫入),但有助于避免較多已更新塊占據緩沖區,影響空間使用效率。
要將塊B輸出到磁盤時,所有與塊B中的數據相關的日志記錄需在塊B輸出前先輸出到穩定存儲器。
塊B輸出中,不能往塊B進行寫。
- 事務對一個數據項執行寫前,獲得數據項所在塊的排他鎖
更新執行完釋放該鎖 - 一個塊要輸出時,采取以下動作序列:
1.獲取該塊上的排他鎖,保證無事務對該塊寫
2.將該塊相關的所有日志記錄保證輸出到穩定存儲器
3.將塊輸出到磁盤
4.塊輸出完成,釋放鎖
緩沖塊上的鎖還可用來保證在檢查點進行過程中緩沖塊不更新,且沒新的日志記錄產生。
1.檢查點操作開始前獲得在所有緩沖塊上的排他鎖及對日志的排他鎖。
2.檢查點操作完成可釋放鎖。
操作系統在緩沖區管理中的作用
管理數據庫緩沖區的方法,可選擇其中之一:
- 1.數據庫系統保留部分主存作緩沖區,對其管理,不讓操作系統管理。
缺點是限定了一塊內存區域為數據庫專用(類似通道靜態劃分),限制了主存使用的靈活性。 - 2.數據庫系統在操作系統提供的虛擬內存中實現其緩沖區。
操作系統決定哪個緩沖塊何時強制輸出到磁盤。
但對對數據庫緩沖頁,應由數據庫系統強制輸出緩沖塊。
遺憾的是,一般操作系統完全控制虛擬內存-內存間交互。
操作系統保留的以存儲當前不在主存的那些虛擬頁的磁盤空間稱為交換區。
如果操作系統輸出一個塊,該塊會輸出到磁盤交換區,數據庫系統無法控制此過程。
數據庫文件和虛擬內存緩沖區間的數據傳送需由數據庫系統管理。
操作系統控制的塊從內存輸出只會將塊輸出到磁盤交換區,不會輸出到磁盤數據文件存儲部分。
數據庫系統需輸出塊B時,此緩沖區塊(虛擬內存塊)當前在交換區中。
故操作系統先從交換區讀入該塊,可能還會從緩沖區換出一塊到交換區以提供容納空間。
然后在由數據庫系統控制該塊內容輸出到數據庫(磁盤上非交換區部分,存儲實際數據部分對應位置)。
模糊檢查點
允許在checkpoint記錄寫入日志后,但在修改過的緩沖塊寫到磁盤前開始做更新。這樣產生的檢查點稱為模糊檢查點。
如寫入checkpoint記錄后,寫完所有修改過緩沖塊之前崩潰,造成磁盤上不完全檢查點。
一種處理不完全檢查點的方法:
將最后一個完全檢查點記錄在日志中的位置存在磁盤上固定位置 last_checkpoint 上。
所有修改過的緩沖塊寫完后,才更新它。
非易失性存儲器數據丟失的故障
基本方法是周期性將整個數據庫的內容轉儲到穩定存儲器中,比如一天一次。
如果發生了一個導致物理數據庫塊丟失的故障,系統就可以用最近的一次轉儲將數據庫復原到前面的一致狀態。
一旦復原完成,系統再利用日志將數據庫系統恢復到最近的一致狀態。
數據庫轉儲的一種方法要求在轉儲過程中不能有事務處于活躍狀態,并且必須指向一個類似于檢查點的過程:
1.將當前位于主存的所有日志記錄輸出到穩定存儲器中。
2.將所有緩沖塊輸出到磁盤。
3.將數據庫內容拷貝到穩定存儲器。
4.將日志記錄<dump>輸出到穩定存儲器。
數據庫內容的轉儲也稱為歸檔轉儲。
將大多數的數據庫系統還支持SQL轉儲,它將SQL DLL等語句寫到文件轉儲用于后續重執行這些語句的方式叫SQL轉儲。
鎖的前提釋放和邏輯 undo 操作
邏輯操作
插入和刪除操作是一類操作的例子,它們需要邏輯 undo 操作,因為它們提前釋放鎖;把這樣的操作稱為邏輯操作。
索引訪問時,訪問時獲取索引頁面鎖,訪問完畢即釋放。即使關聯事務還在執行。
操作執行前獲得鎖,執行完立即釋放鎖。
此后無法通過更新數據項舊值方式執行操作撤銷。
數據項的鎖被操作釋放后,會被其他事務中某操作獲取,并修改數據項中與本事務不發生沖突部分。
此時需執行一個補償操作來撤銷——邏輯undo操作。
邏輯 undo 日志記錄
執行修改索引操作前,事務創建一 <T, Q, operation-begin> 日志記錄。
執行操作時,按正常方式創建更新日志記錄(物理日志)。
操作結束,寫一個形如<T, O, operation-end, U>(邏輯日志)日志記錄。
U表示undo信息。
如果操作為往B+樹插入一項,則undo的U指出要執行刪除,指明刪除基于的B+樹,刪除的項。
記關于操作的這類信息的日志稱作邏輯日志。與此相反,記關于舊值和新值信息的日志稱為物理日志,對于的日志記錄稱為物理日志記錄。
邏輯操作要后續被執行時,執行前應保證數據庫處于操作一致狀態(對B+樹,索引數據應處于某個操作已經結束狀態,而非操作修改索引到一般又執行邏輯操作情況。)
冪等:一個操作執行多次與執行一次結果相同。
有邏輯 undo 的事務回滾
當回滾事務T時,從后往前掃描日志,對事務T的日志記錄做如下處理:
使用由操作產生的物理日志記錄對不完全的邏輯操作進行撤銷。
由 operation-end 標記的已完成的邏輯操作的回滾與此不同。一旦系統發現了一個 <T, O, operation-end, U >日志記錄,就做以下特殊動作:
a. 它通過使用日志記錄中的 undo 信息 U 來回滾該操作。在對操作的回滾中,它將所指向的更新記入日志,就像操作首次執行時進行的更新一樣。
在操作回滾的最后,數據庫系統不產生 <T, O, operation-end, U >日志記錄,而是產生 <T, O, operation-abort>日志記錄。
b. 隨著對日志的反向掃描的繼續進行,系統跳過事務T的所有日志記錄,直至遇到<T, O, operation-begin>日志記錄。
如果系統遇到一個 <T, O, operation-abort>日志記錄,它就跳過前面索引的記錄(包括 O 的 operation-end 記錄),直至它找到 <T, O, operation-begin>日志記錄。
與前面一樣,當遇到<T, start>日志記錄時,事務回滾就完成了,系統往日志中添加一個 <T, abort>日志記錄。
遠程備份系統
傳統的事務處理系統是集中式或客戶/服務器模式的系統。
這種系統必須提供高可用性;即系統不能使用的時間必須非常低短。
在一個站點執行事務處理,稱為主站點,使用一個遠程備份站點,這里有主站點所有數據的備份。
在設計一個遠程備份系統時有幾個問題必須考慮:
- 故障檢測。
- 控制權的移交。
- 恢復時間。
- 提交時間。
持久性的程度可以按如下分類:
一方保險。 事務的提交日志記錄一寫入主站點的穩定存儲器,事務就提交。
問題:當備份站點接管處理時,已提交事務的更新可能還沒有在備份站點執行,這樣,給更新好像丟失了。當站點恢復后,丟失的更新不能直接并入。
兩方強保險。 事務的提交日志記錄一寫入主站點和備份站點的穩定存儲器,事務就提交。
問題:如果主站點或備份站點其中的一個停工,事務處理就無法進行。因此,雖然丟失數據的可能性很小,但其可用性實際上比單站點的情況還低。
兩方保險。 如果主站點和備份站點都是活躍的,該機制與兩方強保險機制相同。
問題:導致比一方保險機制較慢的提交。
另一種達到高可用性的可選方法是使用分布式數據庫,將數據庫復制到不止一個站點。此時事務更新任何一個數據項,都要求更新其所有副本。
學習參考資料:
《數據庫系統概念》第6版總結
以上是生活随笔為你收集整理的《数据库系统概念》学习笔记——恢复系统的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: NFC天线工作原理、设计
- 下一篇: GAN(生成对抗网络) 解释