詳解關係型資料庫運作機制

一說到關係型資料庫，我總感覺缺了點什麼。如果你嘗試透過「關係型資料庫是如何運作的」的關鍵詞句來進行搜索，其搜索結果是少量的而且內容是簡短的。難道說是由於它已經太老舊而已經不再流行嗎？

作為一名開發者，我討厭使用我不明白的技術。此外，關係型資料庫已經使用超40年，肯定有它過人的原因。因此，我花了大量時間來想真正弄懂它裡面如同黑盒子那樣的奧秘。關係型資料庫實際上是非常有趣的，因為它是基於實用和復用的概念。但是限於篇幅，以下我將把重點放在資料庫如何處理SQL查詢的問題上。本文內容大致劃分為以下三部分：

1.低階資料庫和高級資料庫組成概述

2.查詢優化流程的處理概述

3.事務和緩衝池管理概述

基本概念回顧

在編程年代早期，開發者是必須要理解清楚自己所進行操作的原理的。他們對於所使用的演算法和數據結果是瞭然於胸的，因為他們很注重在計算機配置較低時於CPU和內存上的開銷。在這一節，我首先要介紹的是資料庫索引。

O(1) vs O(n2)

時間複雜度用於計算演算法處理數據的用時。科學家使用大O表示法來進行時間複雜度描述，其定義是對於輸入的數據演算法需要進行多少步運算。這裡要強調的是，它的核心是數據量增加對運算增加的影響而不是數據量的多少。時間複雜度不會直接給出精確的運算步數，而是以趨勢的方式展示。

在上圖中，你可以看到不同複雜度的發展趨勢，我使用的方法是對數法。換言之，數據量將會從1快速地增加到10億。我們可以得出以下結論：

O(1)或常數複雜度是維持不變的

O(log(n))在處理10億數據量時也維持與一個較低複雜度水平

O(n2)複雜度增長最快

其餘兩種複雜度位於中游

舉例說明

如果是處理少量數據，O(1)和O(n2)的差別是不明顯的。例如是2000個運算元素：

O(1) 的運算量是1

O(log(n)) 的運算量是7

O(n) 的運算量是2000

O(n*log(n)) 的運算量是14000

O(n2) 的運算量是4 000 000

儘管O(1) 和 O(n2)的運算量的差距是4百萬，但是這僅需2ms，也就是眨眼的功夫。此外，如果使用的是多核處理器，其運算速度會更快。所以性能和優化問題在現在的重視程度無法跟以往相比。如果處理的數據量是1 000 000，其結果又會如何呢？

O(1) 的運算量是1

O(log(n)) 的運算量是14

O(n) 的運算量是1 000 000

O(n*log(n)) 的運算量是14 000 000

O(n2) 的運算量是1 000 000 000 000

這樣一來，你可以先喝杯咖啡休息下再回來看結果了！如果再加個0，你可以先進行午休了！

進一步說明

這裡有幾點提示： 具體演算法和數據結果會在本文稍後列示

在一個完整hash表中進行一次搜索會提交一個元素給O(1)

在一個全平衡樹種進行一次搜索會提交一個結果給O(log(n))

在一個數組中進行一次搜索會提交一個結果給O(n)

最優排序演算法的時間複雜度與O(n*log(n))相當

低效排序演算法的時間複雜度與 O(n2)相當

時間複雜度的類型有：

平均事件場合

最佳時間場合

最差時間場合

時間複雜度通常是最差時間場合。除了時間複雜度，複雜度還可以用來表示內存使用和磁碟I/O佔用情況等。誠然，比n2更複雜的計算有n4，3n，nn 。

合併排序

如果你要對一個集合進行排序該如何做呢？什麼？使用sort()？聽起來是個好的答案。

但如果排序對象是一個資料庫，你就務必知道sort()的工作原理。這裡我介紹排序演算法中最重要的一種：合併排序。對合併排序理解透徹，一方面可以掌握如何進行查詢優化，二來可以更好地理解本文稍後說到的合併join運算。

合併(Merge)

合併排序的運算過程是：合併兩個已排序的N/2數組到一個已排序N個元素數組，例如下圖所示：

以上是本系列文的上篇，更多內容請關注後續文章，後續內容簡述：全局概念，客戶管理器，查詢管理器，數據管理器。

本文以下內容是下篇，內容涉及資料庫總體架構，客戶端管理器，查詢管理器，數據管理器介紹等。

總體架構

前述文章從比較細的角度來討論了資料庫，現在我們嘗試從宏觀角度來分析。

資料庫的核心組件：

過程管理器(The process manager)：資料庫都會有一個過程池/線程池需要進行管理。此外，為了使運行時間更短，現代資料庫會使用自己的線程來替代操作系統線程。

網路管理器(The network manager)：網路的輸入輸出是個大問題，特別是對於分散式資料庫來說。所以部分資料庫針對網路管理打造了自己的管理器。

文件系統管理器(File system manager)：磁碟I/O是資料庫的第一瓶頸。使用管理器進行磁碟文件進行管理是很重要的。

內存管理器(Memory manager)：當你需要處理大量內存數據或大量查詢，一個高效的內存管理器是必須的。

安全管理器(Security manager)：進行認證和用戶認證管理。

客戶端管理器(Client manager)：進行客戶端連接管理

資料庫的工具：

備份管理器：進行資料庫的備份與恢復

復原管理器：在資料庫崩潰後進行資料庫重啟

監視管理器：進行資料庫活動日誌記錄，同時進行資料庫監視

管理員管理器：進行metadata存儲，管理資料庫，表空間，數據泵等

查詢管理器：對查詢進行有效性檢驗，優化，編譯和執行

數據管理器：包括事務管理器，緩存管理器，數據訪問管理器

下面將詳細介紹客戶端管理器，查詢管理器以及數據管理器。

客戶端管理器

客戶端管理器用於處理和管理客戶端的通信。客戶端可以是一台伺服器或是終端應用。客戶端管理器透過不同的API來提供訪問權，例如：JDBC，ODBC，OLE-DB等。

當你連接到一個資料庫時：

管理器會對你的身份和授權進行確認。

如果驗證通過，會對你的查詢請求進行處理。

管理器同時會檢查資料庫是否處於滿負荷狀態。

管理器會等待請求資源的返回。如果發生超時，它會關閉連接並返回可讀的錯誤信息。

然後會把你的查詢發送給查詢管理器，而你的查詢是被處理狀態。

管理器會存儲部分結果到緩衝區然後開始進行結果返回。

如果出現異常，管理器會中斷連接，返回相關原因解釋並釋放資源。

查詢管理器

查詢管理器是資料庫的重要組成部分。其工作過程是：

查詢會被解釋以確認有效性

然後會被重寫以消除不必要的操作並進行預優化處理

然後會被優化處理以提高性能並發送到執行和數據訪問計劃

然後改計劃會被編譯處理

最後進行執行查詢

查詢重寫器的運作

重寫器的目的是：

進行查詢預優化處理

避免不必要的操作

幫助優化器找出最佳方案

常見的重寫規則：

視圖合併：如果你在查詢中使用了視圖，那麼該視圖會被轉換層SQL視圖代碼

子查詢扁平化：子查詢使查詢優化變得困難，因此重寫器會修改含有子查詢的查詢以消除子查詢。

消除不必要的操作符：例如當你使用了UNIQUE唯一約束而同時使用了DISTINCT操作符，那麼DISTINCT將會被消除。

多於JOIN連接清除：當你 有兩次相同條件的JOIN連接但是其中一個條件被隱藏了或者是一個多於的JOIN，那麼它會被清除。

分區處理：如果你使用了一個分區表，那麼重寫器會找出那個分區會被使用。

自定義規則：如果你有自定義的查詢規則，重寫器會執行這些規則。

數據管理器

查詢管理器的作用是執行查詢並對資源發出請求，數據管理器會處理這些請求並返回結果。但這裡有兩個問題：

關係資料庫使用的是事務模型。所以你有可能得不到數據，因為其他人可能會正同時使用/修改這些數據。

數據獲取是資料庫中最慢的操作，因此數據管理必須要能高效地獲取並數據存放在內存緩衝區。

那麼關係資料庫是如何解決這兩個問題的呢？

緩存管理器

如前所述，資料庫的主要瓶頸是磁碟I/O。所以現代資料庫使用了緩存管理器來提高效率。查詢執行器的數據請求對象是緩存管理器而不是直接的文件系統。緩存管理器有一個內存里緩存叫做緩衝池。從內存獲取數據會大大提高資料庫速度。

緩衝–替換策略

很多主流資料庫(如：SQL Server，MySQL，Oracle等)使用的是LRU演算法。 LRU是Least Recently Used的簡寫，意思最近使用。其理念是緩存最近使用的數據以便再次使用時快速讀取。

雖然它有很多優點但也存在不足，比方說表/索引的大小超過了緩衝區大小。因此出現了進階版本的LRU，這就是LRU-K，例如在SQL Server 使用的是LRU-K，K=2。在LRU-K中：

首先考慮數據的K次最近使用記錄；根據數據的使用次數分配權值；如果有新的數組載入緩存，舊的但經常使用的數據不會被移除，但是當舊數據不再使用，將會被移除，所以權值的設立有助於減少多餘數據。

事務管理器

事務管理器是為了確保每個查詢會執行自己的事務。在講述事務管理期前，我們需要理解ACID事務的概念。ACID是一個工作單元，它的意思是：

Atomicity(原子性)：事務是」全或全不」的，即使是10個小時的事務。如果事務崩潰了，會發生狀態回滾。

Isolation(隔離性)：如果事務A和B同時運行，那麼事務A和B的結果必須是一致的，不論A對於B是完成前/完成後/過程中的狀態。

Durability(耐久性)：一旦事務完成，數據會存放在資料庫中而不論發生什麼情況(異常或錯誤)。

Consistency(一致性)：只有有效數據被寫入資料庫。一致性與原子行和隔離性關聯。

並發控制

確保隔離性，附著性和原子性的關鍵是能對同一數據進行正確寫操作(添加，更新和刪除)

如果僅僅是數據讀取事務，那麼它們可以不與其它修改事務發生衝突；

如果一個修改事務處理的數據被其它事務讀取，資料庫需要找到方法來隱藏這些修改操作。同時，它需要保證這些修改操作不會被清除。

以上問題就是並發控制。最簡單的處理方法是逐個執行事務。但是這不利於進行規模擴張，也無法發揮伺服器/CPU的多核性能。理想的處理方式是每當事務新建或取消時

監視所有事務的全部操作，檢查同時讀取/修改相同數據的兩個(或多個)事務是否發生衝突，在發生衝突的事務中進行操作記錄以減少衝突部分的大小，把衝突部分以其它次序進行處理，判別某事務是否可以取消。

更正規的做法是進行衝突日程表管理。但是在企業級資料庫中，是很難為每個新事務事件分配足夠多的處理時間。所以會使用其它方法來進行處理。

鎖管理器

為了處理以上問題，多數資料庫會採用鎖或數據版本來進行處理。但這是個內容豐富的話題，以下會把討論重點放在鎖部分。

什麼是鎖呢？

事務是否需要數據

是否鎖定了數據

另一事務是否需要相同數據

是否不得不等待直至第一個事務釋放這些數據

這叫做排斥鎖。但是排斥鎖針對的對象相同數據的讀取和等待，這是不利於資源調配的。還有一種鎖，叫共享鎖。

在共享鎖中：

一個事務是否只需讀取數據A

共享鎖對數據鎖定並讀取數據

如果第二個事務也只需要讀取數據A

共享鎖對數據鎖定並讀取數據

如果第三個事務只需要修改數據A

那麼會對數據進行排斥鎖鎖定，但它必須等待直至事務一，二釋放共享鎖才對數據A進行排斥鎖鎖定

鎖管理器的作用是提供和釋放鎖。從內部角度看，它把鎖存儲在一個有關聯的hash數據表中。

哪些事務鎖定了數據

哪些事務在等待數據

死鎖

鎖的存在會導致一個問題：兩個事務在無限期地等待數據。下圖所展示，這就是死鎖。

事務A對數據1使用了排斥鎖，同時在等待獲取數據2

事務B對數據2使用了排斥是，同時在等待獲取數據1

遇到死鎖後，鎖管理器會選擇對哪個事務進行撤銷(回滾)以消除死鎖。但要進行選擇，並不是件容易的事。DB2和SQL Sever使用了兩段鎖協議(Two-Phase Locking Protocol)來進行處理。

在增長段，事務會得到鎖，但是不能釋放鎖。

在下降段，事務可釋放鎖，但是不能得到鎖。

其核心理念是：

釋放不再使用的鎖以減少其他事務對這些鎖的等待時間

避免事務開始後對數據進行修改，所以這是非連貫事務

寫在最後

我一直所堅持的習慣是：明白你所使用的技術，如果你想不斷提升自己的開發水平，嘗試深入掌握你所使用的工具的原理是個大有裨益的方法。雖然NoSQL在現今很流行，但是它們還是屬於發展初期，一些特定的問題或重要思想還是得藉助關係資料庫才能徹底弄懂。文章來自極客頭條，關係資料庫是如何運作的(上 /下)。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！