關係資料庫是如何工作的(8)

語言: CN / TW / HK

日誌管理器

我們已經認識到,為了提高效能,資料庫將資料儲存在記憶體緩衝區中。但是,如果在事務提交時,伺服器崩潰,你就會丟失所有記憶體中的資料,這將導致事務永續性問題。

你可以將所有資料寫入磁碟,但是,如果伺服器崩潰,你可能只寫入一半資料,這會導致事務的原子性問題。

事務所做的任何修改寫入必須要全部撤銷或全部寫入。

為解決這一問題,有兩種解決方案:

  • 影子拷貝/頁 :每一個事務建立自己的資料庫拷貝(或者是資料庫的一部分),在這個拷貝上面工作。如果發生了錯誤,移除該拷貝;如果成功,資料庫立刻將資料通過檔案系統技巧從拷貝切換,並移除“舊的”資料。
  • 事務日誌 :事務日誌是一段儲存空間。在每個寫入磁碟操作之前,資料庫將資訊寫入事務日誌,以便在事務崩潰/撤銷時,資料庫能夠知道如何移除(或完成)未完成的事務。

WAL

當大型資料庫需要很多事務時,影子拷貝/頁會佔用大量磁碟空間。這就是現代資料庫使用 事務日誌 的原因。事務日誌必須儲存在 穩定的儲存 中。我不會深入介紹儲存技術,只簡單提一句,使用(至少)RAID 磁碟陣列能夠有效防止磁碟失敗。

很多資料庫(包括 Oracle、 SQL ServerDB2PostgreSQL 、MySQL 和  SQLite )使用 預寫式日誌(Write-Ahead Logging protocol,WAL) 。WAL 包括三個規則:

  • 1) 資料庫每一條修改都要產生一條日誌記錄, 這個日誌記錄必須在資料寫入磁碟之前先寫入事務日誌
  • 2) 日誌記錄必須按照順序寫入:如果日誌記錄 A 發生在日誌記錄 B 之前,那麼 A 必須在 B 之前寫入
  • 3) 當事務提交時,直到事務成功結束,提交順序必須寫入事務日誌

這個工作是由日誌管理器完成的。簡單來說,日誌管理器就是,在快取管理器和資料訪問管理器(資料訪問管理器將資料寫入磁碟)之間,在資料寫入磁碟之前,將每一個更新/刪除/建立/提交/回滾寫入事務日誌。很簡單,是不是?

不對! 經過這麼多的學習,你應該知道,關於資料庫的一切都可能引起“資料庫效應”。嚴肅地說,日誌管理器的問題是,找到一種既能寫入日誌,又能保持好效能的方式。如果寫入事務日誌太慢,它就會拖慢所有事情。

ARIES

1992 年,IBM 的研究者“發明了”一種改進版本的 WAL,稱為 ARIES。ARIES 多多少少被大多數現代資料庫使用。具體邏輯可能不一樣,但是 ARIES 背後的概念已經被廣泛使用。我給發明這個詞加了引號,是因為根據 MIT 課程 ,IBM 研究者“什麼都沒幹,只是寫了篇事務恢復的最佳實踐”。因為 ARIES 論文發表的時候,我只有 5 歲,我不關心那些尖酸刻薄的研究者們的流言蜚語。事實上,我之所以在這裡寫出來這個,主要是為了在我們開始最後一個技術部分之前稍微休息一下。我閱讀了大量 關於 ARIES 的研究論文 ,發現它的確很有趣!在這部分我只介紹 ARIES 的大概,但是如果你想學習點真正的知識的話,我強烈推薦你去閱讀這些論文。

ARIES 是 A lgorithms for R ecovery and I solation E xploiting S emantics(利用語義的恢復和隔離演算法)的縮寫。

這項技術的目的有兩個:

  • 1) 獲得 寫日誌的良好效能
  • 2) 獲得快速 可靠的恢復

資料庫之所以要回滾事務,其原因是多方面的:

  • 因為使用者取消了事務
  • 因為伺服器或網路失敗
  • 因為事務打破了資料庫完整性(例如,你有一個帶有 UNIQUE 約束的列,而事務檢視插入重複值)
  • 因為死鎖

有時(比如網路失敗)資料庫能夠從事務恢復。

這是怎麼做到的?為回答這個問題,我們需要理解儲存在日誌記錄中的資訊。

日誌

每一個 事務中的操作(增加/刪除/修改)都會產生一條日誌 。這個日誌記錄包括:

  • LSNL og S equence N umber(日誌順序數)。LSN 按照順序以此給出*。這意味著如果一個操作 A 發生在操作 B 之前,那麼日誌 A 的 LSN 就會比 日誌 B 的 LSN 小。
  • TransID :產生操作的事務 ID。
  • PageID :被修改的資料在磁碟的位置。磁碟上資料的最小值是頁,因此資料的位置也就是包含了資料的頁的位置。
  • PrevLSN :同一事務產生的前一個日誌記錄的連結。
  • UNDO :移除該操作影響的方法。例如,如果操作是更新,UNDO 會儲存元素被更新之前的值/狀態(物理 UNDO)或者回到之前狀態的撤銷操作(邏輯 UNDO)**。
  • REDO :重現操作的方法。類似地,有兩種方法儲存 REDO:儲存操作之後元素的值/狀態或者可以重複執行的操作本身。
  • …:(順便說一句,ARIES 日誌還有另外兩個欄位:UndoNxtLSN 和 Type)。

另外,磁碟上每一個頁(儲存資料的頁,不是儲存日誌的頁)都儲存有最後修改資料的那個操作的日誌記錄 ID(LSN)。

*這種給出 LSN 的方式更復雜一些,因為它與儲存日誌的方式相關。但思路是一致的。

**ARIES 只使用邏輯 UNDO,因為物理 UNDO 會有很大的消耗。

注意:就我所知,只有 PostgreSQL 沒有使用 UNDO,而是使用了一個垃圾回收守護程序來移除舊的資料。這與 PostgreSQL 使用的資料版本實現相關。

為了更好理解,下面是日誌記錄的簡單的圖形化例子。這個日誌記錄來自於查詢 “UPDATE FROM PERSON SET AGE = 18;”。假設該查詢在事務 18 中執行。

每個日誌都有唯一的 LSN。同一事務的日誌被連結到一起。日誌是順序相連的(連結串列中的最後一個日誌對應著最後一個操作)。

日誌緩衝

為避免寫入日誌帶來的主要瓶頸,資料庫會使用 日誌緩衝

當查詢執行器請求修改時:

  • 1) 快取管理器在其緩衝區儲存修改
  • 2) 日誌管理器在其緩衝區儲存相關日誌
  • 3) 在這一步,查詢執行器認為操作已經完成(因此開始請求另外的修改)
  • 4) 然後(之後),日誌管理器在事務日誌寫入日誌。何時寫入日誌是由演算法決定的。
  • 5) 然後(之後),快取管理器將修改寫入磁碟。何時寫入資料是由演算法決定的。

事務提交,意味著事務中的每一個操作,上述 1,2,3,4,5 步已經完成。寫入事務日誌是很快的,因為這僅僅是“在事務日誌某個地方加入一條記錄”;但是,將資料寫入磁碟就複雜得多,因為“需要按照能夠快速讀取的方式寫入資料”。

STEAL 和 FORCE 策略

由於效能原因, 第 5 步可能會在事務提交之後完成 ,因為如果萬一崩潰,還有機會按照 REDO 日誌。這被稱為  NO-FORCE 策略

資料庫也可以選擇 FORCE 策略(也就是說,第 5 步必須在提交之前完成)降低恢復期間的工作負載。

另一個問題是, 資料是一步一步寫入磁碟的(STEAL 策略) 還是緩衝管理器需要等待提交命令,一次性寫入( NO-STEAL 策略) 。STEAL 和 NO-STEAL 的選擇取決於你想要什麼:使用 UNDO 日誌快速寫入很長的恢復,還是快速恢復?

下面是恢復策略的影響總結:

  • STEAL/NO-FORCE 需要 UNDO 和 REDO最高效能 ,但是更復雜的日誌和恢復過程(例如 ARIES)。 這是大多數資料庫的選擇 。注意,我通過很多研究論文和課程瞭解到這個事實,但是我沒有在官方文件找到(顯式的)證據。
  • STEAL/ FORCE 只需要 UNDO。
  • NO-STEAL/NO-FORCE 只需要 REDO。
  • NO-STEAL/FORCE 不需要任何東西: 最壞效能 ,需要大量冗餘。

恢復

好了,現在我們有了漂亮的日誌,用用它們吧!

假設我們新來的臨時工把資料庫搞垮了(規則 No 1:總是臨時工的錯)。你重啟資料庫,開始恢復程序。

ARIES 從崩潰中恢復需要三個階段:

  • 1) 分析階段 :恢復程序讀取完整的事務日誌*,重建時間線,找出崩潰期間發生了什麼,決定回滾哪個事務(所有沒有提交命令的事務都要被回滾),哪些資料需要在崩潰時寫入磁碟。
  • 2) 重做階段 :這一階段開始於分析決定的一條日誌記錄,使用 REDO 更新資料庫,使其回到崩潰開始之前的狀態。在重做期間,REDO 日誌按照順序處理(使用 LSN)。對於每一條日誌,恢復程序讀取包含有需要修改的資料的磁碟上的頁的 LSN。如果 LSN(page_on_disk) >= LSN(log_record),意味著崩潰之前資料已經寫入磁碟(但是值被日誌之後、崩潰之前的操作覆蓋掉了),什麼都不做。如果 LSN(page_on_disk) < LSN(log_record),那麼更新磁碟上的頁。對於那些準備回滾的事務也需要進行重做,因為這會簡化恢復程序(但是我肯定現代資料庫不會這麼幹)。
  • 3) 撤銷階段 :這一階段回滾所有在崩潰時未完成的事務。回滾開始於每一個事務的最後一個日誌,按照倒序執行 UNDO 日誌(使用日誌記錄的 PrevLSN)。

在恢復期間,事務日誌必須警惕恢復管理器執行的動作,以便保證寫入磁碟的資料與事務日誌中的是完全同步的。一個解決方案是,刪除已經撤銷完成事務日誌記錄,但這很困難。ARIES 則是在事務日誌中寫入補償日誌,刪除那些邏輯刪除的日誌記錄。

當事務“手動”取消或者由鎖管理器取消(終止死鎖)或僅僅是由於網路失敗,分析階段是不需要的。REDO 和 UNDO 所需資訊儲存在兩個記憶體中的表:

  • 事務表 (儲存所有當前事務的狀態)
  • 髒頁表 (儲存哪些資料需要被寫入磁碟)

這些表由快取管理器和事務管理器為每一個新的事務事件進行更新。由於它們是在記憶體中的,資料庫崩潰時就會被銷燬。

分析階段的工作是在崩潰之後使用事務日誌重建這兩個表*。為加速分析階段,ARIES 提供了 檢查點 標記,其思路是,將事務表和髒頁表的內容不定時寫入磁碟,並且寫入此時最後一個 LSN,這樣在分析階段,只有在該 LSN 之後的日誌才會被分析。

總結

在寫本文之前,我就知道這個話題是有多大,需要花費多少時間寫一篇有深度的文章。事實證明我還是過於樂觀,我花費了比預想多兩倍的時間,但是我學到了很多。

如果你想很好學習資料庫,我推薦閱讀這篇研究論文《 Architecture of a Database System 》。這是一篇很好的介紹資料庫的文章(110 頁),適合非計算機專業人事閱讀。這篇文章對編寫本文計劃給我很大幫助。它並沒有像我的文章一樣關注資料結構和演算法,而是給出很多架構概念。

如果你仔細閱讀本文,你應該知道資料庫的強大之處。由於這是一篇很長的文章,我來提醒一下你閱讀過什麼:

    • B+ 樹索引的概覽
    • 資料庫全域性概覽
    • 基於成本的優化的概覽,尤其關注於連線運算
    • 緩衝池管理概覽
    • 事務管理概覽

但是資料庫要聰明得多。例如,我沒有碰觸下面的問題:

    • 如何管理叢集式資料庫和全域性事務
    • 如何在資料庫執行時對其建立快照
    • 如何有效儲存(包括壓縮)資料
    • 如何管理記憶體

所以,當你需要在充滿 bug 的 NoSQL 資料庫和像石頭一樣堅固的關係資料庫之間選擇時,我奉勸你要多多思考。不要將我的意思理解錯了,某些 NoSQL 資料庫非常棒,但是它們還年輕,只能處理某些應用的特定問題。

總結一下,如果以後有人問你,資料庫是怎麼工作的,我希望你不是像下面一樣回答這個問題:

否則的話,你可以把這篇文章甩到他臉上。