InnoDB存儲引擎底層拆解：從頁、事務到鎖，如何撐起MySQL數據庫高效運轉（上）

Page頁**

B+樹查詢

如何加快記錄的查詢？

索引**

聚簇索引(主鍵)

二級索引(非主鍵)

聯合索引——多列

bufferPool*

Free鏈表

flush鏈表

Flush鏈表刷新方式有如下兩種：

LRU鏈表

針對LRU鏈表方案缺點的優化

redoLog*

redo簡單日志類型

redo復雜日志類型（以MLOG_COMP_REC_INSERT為例：）

redo日志組

MTR（Mini-Transacti on）

redo日志緩沖區——log buffer

redo日志刷盤和日志文件組

undoLog*

事務**

MVCC

鎖*

????????你在電商平臺點擊“提交訂單”按鈕的瞬間，背后發生了什么？

????????數據庫需要在毫秒級內完成：查詢商品庫存、校驗用戶余額、生成訂單記錄、扣減庫存、最終提交事務……這些操作看似“絲滑”，實則由MySQL的核心存儲引擎——??InnoDB??默默支撐。

????????但你可能從未想過：

?
為什么InnoDB能在磁盤中快速找到一條記錄？是靠怎樣的“數據地圖”？
?
為什么它能同時處理上萬并發事務，還能保證數據不丟、不亂？
?
那些耳熟能詳的“B+樹索引”“Buffer Pool緩存”“redo log日志”……它們究竟如何協作？

????????這篇文章，我們從InnoDB最底層的??頁（Page）??開始，一步步拆解它的核心設計：B+樹如何優化查詢、Buffer Pool如何減少磁盤IO、redo/undo日志如何保障事務、事務與鎖如何協同工作……最終還原這個“數據庫隱形引擎”的底層邏輯。

Page頁**

????????為了避免一條一條讀取磁盤數據，InnoDB采取頁的方式，作為磁盤和內存之間交互的基本單位。一個頁的大小一般是16KB。

????????InnoDB為了不同的目的而設計了多種不同類型的頁。比如：存放表空間頭部信息的頁、存放undo日志信息的頁等等。我們把存放表中數據記錄的頁，稱為索引頁or數據頁。

往頁中存儲的數據也稱作：“記錄”

記錄的頭信息包括以下：

記錄是按照主鍵從小到大的順序形成了一個單向鏈表。記錄被刪除后next_record會有影響；查詢也只能以頭節點開始逐一向后查詢，但是如果數據量很大，那么性能就無法保證了。針對這個問題，InnoDB采取了圖書目錄的解決方案，即：Page Directory

分組規則如下所示：

① 對于Infimum記錄所在的分組只能有1條記錄。② 對于Supremum記錄所在的分組只能在1～8條記錄之間。③ 剩下的其他記錄所在的分組只能在4～8條記錄之間。

分組步驟如下：① 初始情況下，一個數據頁中只有Infimum記錄和Supremum記錄這兩條，所以分為兩個組。② 之后每當插入一條記錄時，都會從頁目錄中找到對應記錄的主鍵值比待插入記錄的主鍵值大，并且差值最小的槽，然后把該槽對應的n_owned加1。③ 當一個組中的記錄數等于8時，當再插入一條記錄的時候，會將組中的記錄拆分成兩個組（一個組中4條記錄，另一個組中5條記錄）。并在拆分過程中，會在PageDirectory中新增一個槽，并記錄這個新增分組中最大的那條記錄的偏移量。

B+樹查詢

【B樹&B+樹的插入和刪除圖文詳解】B樹和B+樹的插入、刪除圖文詳解 - nullzx - 博客園

【與B樹相同點】

一個節點可以存儲多個元素。

與B樹一樣，葉子節點是有序的。

每個節點中的元素，也都按照從小到大的順序排列，即：左小右大。

所有葉子節點都位于同一層，或者說根節點到每個葉子節點的高度都相同。

【與B樹不同點】

B+樹的葉子節點是有單向指針的，其中：MySQL中采用的是雙向指針。

B+樹的非葉子節點的元素是與葉子節點有冗余的。

如何加快記錄的查詢？

當記錄越來越多，創建的頁也會越來越多，如果僅通過鏈表方式遍歷查詢，性能會出現很大問題。如何解決呢？采用B+樹結構，即：

葉子節點里存儲完整的數據（數據頁），非葉子節點存儲主鍵索引（索引頁）

索引**

聚簇索引(主鍵)

????????聚簇索引的 B + 樹葉子節點直接存儲了完整的行數據。這意味著，InnoDB 表的數據實際上是按照聚簇索引的順序進行物理存儲的。

二級索引(非主鍵)

????????二級索引的 B + 樹葉子節點存儲的是索引列的值以及對應的聚簇索引鍵值。

當通過二級索引進行查詢時，首先在二級索引的 B + 樹中找到對應的葉子節點，獲取到聚簇索引鍵值。然后，使用這個聚簇索引鍵值在聚簇索引的 B + 樹中再次查找，才能獲取到完整的行數據。這個過程稱為 “回表”。例如，執行SELECT * FROM table WHERE email = 'example@mail.com'，先在email的二級索引 B+樹中找到對應的葉子節點，得到聚簇索引鍵（如id值），再通過這個id值在聚簇索引B+樹中獲取完整的行數據。

聯合索引——多列

目錄項記錄的唯一性

????????為了讓新插入的記錄能找到自己在哪個頁中，就需要保證B+樹同一層內節點的目錄項記錄除頁號字段外是唯一的。所以二級索引的內節點的目錄項記錄的內容實際是有3部分構成的：索引列的值(c2)+主鍵值(c1)+頁號(pageNo)。這樣，如果c2列的值相同，那么可以接著比較主鍵值。所以，歸其根源，我們可以認為，為c2列建立的二級索引其實相當于為（c2，c1）列建立了一個聯合索引。

bufferPool*

為了緩存磁盤中的頁，MySQL服務器啟動時就向操作系統申請了一片連續的內存空間，他們給這片內存起名為Buffer Pool（緩沖池）。默認Buffer Pool只有128M，可以在啟動服務器的時候配置innodb_buffer_pool_size（單位為字節）啟動項來設置自定義緩沖池大小。Buffer Pool對應的一片連續的內存被劃分為若干個頁面，默認也是16KB，該頁面稱為緩沖頁。為了更好的管理Buffer Pool中的這些緩沖頁，InnoDB為每個緩沖頁都創建了控制塊，它與緩沖頁是一一對應的。

Free鏈表

Buffer Pool的初始化過程中，是先向操作系統申請連續的內存空間，然后把它劃分成若干個【控制塊&緩沖頁】對兒。當插入數據的時候，為了能夠知道哪些緩沖頁是空閑且可分配的，MySQL把所有空閑的緩沖頁對應的控制塊作為一個節點放到一個鏈表中，這個鏈表便稱之為free鏈表。

flush鏈表

如果我們修改了Buffer Pool中某個緩沖頁的數據，那么它就與磁盤上的頁不一致了，這樣的緩沖頁也被稱之為臟頁（dirty page）。為了性能問題，我們每次修改緩沖頁后，并不著急立刻把修改刷新到磁盤上，而是將被修改過的緩沖頁對應的控制塊作為節點加入到這個鏈表中，該鏈表也被稱為flush鏈表。

Flush鏈表刷新方式有如下兩種：

【1】從flush鏈表中刷新一部分頁面到磁盤

后臺線程也會定時從flush鏈表中刷新一部分頁面到磁盤，刷新的速率取決于當時系統是否繁忙。——即：BUF_FLUSH_LIST

有時后臺線程刷新臟頁的進度比較慢，導致用戶準備加載一個磁盤頁到Buffer Pool中時沒有可用的緩沖頁。此時，就會嘗試查看LRU鏈表尾部，看是否存在可以直接釋放掉的未修改緩沖頁。如果沒有，則不得不將LRU鏈表尾部的一個臟頁同步刷新到磁盤（與磁盤交互是很慢的，這會降低處理用戶請求的速度）。——即：BUF_FLUSH_SINGLE_PAGE

【2】從LRU鏈表的冷數據中刷新一部分頁面到磁盤

后臺線程會定時從LRU鏈表的尾部開始掃描一些頁面，掃描的頁面數量可以通過系統變量innodb_lru_scan_depth來指定，如果在LRU鏈表中發現臟頁，則把它們刷新到磁盤。——即：BUF_FLUSH_LRU

控制塊里會存儲該緩沖頁是否被修改的信息，所以在掃描LRU鏈表時，可以很輕松地獲取到某個緩沖頁是否是臟頁的信息。

LRU鏈表

線性預讀：如果順序訪問某個區（extent，一個區默認64個頁）的頁面超過了innodb_read_ahead_threshold（默認56）的值，就會觸發一次異步讀取下一個區中全部的頁到Buffer Pool中的請求。

隨機預讀：如果開啟了隨機預讀功能（默認：innodb_random_read_ahead=OFF），如果某個區（extent）有13個連續的頁面都已經被加載到了Buffer Pool中，無論這些頁面是不是順序讀取的，都會觸發一次異步讀取本區全部的頁到Buffer Pool中的請求。

針對LRU鏈表方案缺點的優化

針對預讀的優化①InnoDB規定，當磁盤上的某個頁在初次加載（只是加載，沒有涉及讀取）到BufferPool中的某個緩沖頁時，該緩沖頁對應的控制塊會被放到old區域的頭部。這樣預讀頁就只會在old區域，不會影響young區域中使用比較頻繁的緩沖頁。
針對全表掃描的優化①雖然首次加載放到的是old區域的頭部，但是由于是全表掃描，會對加載的數據進行訪問，那么第一次訪問的時候，就會將該頁放到young區域的頭部。這樣仍然會把那些使用頻率比較高的頁面給“排擠”下去。②那怎么辦呢？由于全表掃描有一個特點，就是它對某個頁的頻繁訪問且總耗時很短。所以，針對這種情況，InnoDB規定，在對某個處于old區域的緩沖頁進行第一次訪問時，就在它對應的控制塊中記錄下這個訪問時間，如果后續的訪問時間與第一次訪問的時間在某個時間間隔內（即：innodb_old_blocks_time，默認為1000，單位為ms），那么該頁面就不會從old區域移動到young區域的頭部，否則將它移動到young區域的頭部。

chunk和BufferPool實例

redoLog*

什么是redo日志？

如果我們只在內存的BufferPool中修改了頁面，假設在事務提交后突然發生了某個故障，導致內存中的數據都失效了，那么這個已經提交的事務在數據庫中所做的更改也就丟失了。針對這種問題，怎么處理呢？

【方案1】在事務提交時，把該事務修改的所有頁面都刷新到磁盤，刷新成功了才提示事務提交成功①刷新一個完整的數據頁太浪費了。雖然我們只修改了一條記錄，但是會將這條記錄所在的頁（16KB）都刷新到磁盤上，會造成大量磁盤I/O的浪費。②隨機I/O刷新起來比較慢。一個事務可能包含很多語句，即使是一條語句也可能修改許多頁面，并且該事務修改的這些頁面可能并不相鄰。這就意味著將某個事務修改的BufferPool中的頁面刷新到磁盤時，需要進行很多的隨機I/O。而隨機I/O要比順序I/O慢，尤其是機械硬盤。

【方案2】在事務提交時，只需要把修改的內容記錄一下就好了。例如：“將第0號表空間第100號頁面中偏移量為1000處的值更新為2。”

redo簡單日志類型

在對頁面的修改是極其簡單的情況下，redo日志中只需要記錄一下在某個頁面的某個偏移量處修改了幾個字節的值、具體修改后的內容是什么就好了，比如操作MaxRowId

MLOG_1BYTE：表示在頁面的某個偏移量處寫入1字節的redo日志類型。

MLOG_2BYTE：表示在頁面的某個偏移量處寫入2字節的redo日志類型。

MLOG_8BYTE：表示在頁面的某個偏移量處寫入8字節的redo日志類型。

MLOG_WRITE_STRING：表示在頁面的某個偏移量處寫入一個字節序列。

redo復雜日志類型（以MLOG_COMP_REC_INSERT為例：）

redo日志組

在執行語句的過程中產生的redo日志，被InnoDB劃分成了若干個不可分割的組。比如：更新MaxRowID屬性時產生的redo日志為一組，是不可分割的；向聚簇索引/二級索引對應B+樹的頁面中插入一條記錄時產生的redo日志為一組，是不可分割的等等。?InnoDB認為，比如向某個索引對應的B+樹中插入一條記錄的過程必須是原子的，不能說插入了一半之后就停止了。否則就會形成一棵不正確的B+樹。所以他們規定在執行這些需要保證原子性的操作時，必須以組的形式來記錄redo日志。在進行恢復時，針對某個組中的redo日志，要么把全部的日志都恢復，要么一條也不恢復。

MTR（Mini-Transacti on）

對底層頁面進行一次原子訪問的過程被稱為一個Mini-Transaction（MTR）。

事務、語句、MTR、redo日志之間的關系，如下所示：① 1個事務可以包含N條SQL語句② 1條SQL語句可以包含N個MTR③ 1條MTR可以包含N條redo日志

redolog block

為了更好地管理redo日志，InnoDB把通過MTR生成的redo日志都放在了大小為512字節的頁中，把用來存儲redo日志的頁稱為block。

與Buffer Pool類似，寫入redo日志時也不能直接寫到磁盤中，實際上在服務器啟動時就向操作系統申請了一大片稱為redo log buffer（redo日志緩沖區）的連續內存空間，也可以將其簡稱為log buffer。這片內存空間被劃分成若干個連續的redo log block。

其中，用innodb_log_buffer_size指定log buffer的大小。該啟動選項的默認值為16MB。

redo日志緩沖區——log buffer

向log buffer中寫入redo日志的過程是順序寫入的。其中，buf_free是一個全局變量，該變量指明后續寫入的redo日志應該寫到log buffer中的哪個位置。

一個MTR執行過程中可能產生若干條redo日志，這些redo日志是一個不可分割的組，所以并不是每生成一條redo日志就將其插入到log buffer中，而是將每個MTR運行過程中產生的日志先暫時存到一個地方，當該MTR結束的時候，再將過程中產生的一組redo日志全部復制到log buffer中

不同的事務是可能并發執行的，所以T1、T2的MTR可能是交替執行的。

redo日志刷盤和日志文件組

MTR運行過程中產生的一組redo日志在MTR結束時會被復制到log buffer中。可是這些日志總在內存里也不是辦法，在一些情況下它們會被刷新到磁盤中:

**重點面試題：redolog 在哪些情況刷盤？

①log buffer空間不足50%的時候②事務提交的時候③ 后臺有線程，大約以每秒1次的頻率將log buffer中的redo日志刷新到磁盤。④ 正常關閉服務器時⑤ 做checkpoint時

在MySQL的數據目錄中，默認有名稱為：ib_logfile0和ib_logfile1的兩個文件，logbuffer中的日志在默認情況下就是刷新到這兩個磁盤文件中，也可以通過下一頁中的配置參數對其進行調節和修改：

查看redo日志相關配置信息

datedir：查看數據目錄所在位置。

innodb_log_group_home_dir指定了redo日志文件所在目錄，默認值為當前的數據目錄。

redo日志文件格式

lsn（logsequence number）

lsn是一個全局變量，用來記錄當前總共已經寫入的redo日志量。

lsn初始值為8704，也就是說，一條redo日志什么也沒寫入的時候，lsn的值就是8704。

redo日志刷新到磁盤

flush鏈表

刷入磁盤

mtr1和mtr2生成的redo日志雖然已經寫到磁盤上的log file中了，但是它們修改的臟頁仍然留在Buffer Pool中，所以它們的redo日志不可以被覆蓋。隨著系統運行，如果頁a從Buffer Pool中刷到了磁盤上，那么頁a對應的控制塊就會從flush鏈表中移除掉。而且，它的redo日志占用的空間就可以被覆蓋掉了。

chec kpoint

InnoDB通過全局變量checkpoint_lsn，來表示當前系統中可以被覆蓋的redo日志總量是多少。這個變量的初始值也是8704（因為lsn的初始值就是8704）。比如，現在頁a被刷新到了磁盤上，mtr1生成的redo日志就可以被覆蓋了，所以進行一個增加checkpoint_lsn的操作。我們把這個過程稱為執行一次checkpoint。

redo日志文件組中各個lsn值的關系，如下圖所示：

innodb_flush_log_at_trx_commit

為了保證事務的持久性，用戶線程在事務提交時，需要將該事務執行過程中產生的所有redo日志都刷新到磁盤中。

這個規則我們可以通過系統變量innodb_flush_log_at_trx_commit來進行配置修改，該變量有如下3個可選值:0：在事務提交時，不立即向磁盤同步redo日志，這個任務交給后臺線程來處理；1：在事務提交時，需要將redo日志同步到磁盤。（默認值）2：在事務提交時，需要將redo日志寫到操作系統的緩沖區中，但并不需要保證將日志真正刷新到磁盤。如果操作系統掛掉了，則數據丟失。