MySQL 8.0 INSTANT DDL 算法原理簡析
引言
MySQL 8.0 中引入 INSTANT DDL，極大提高了 DDL 的執行效率，具體原理簡單說就是僅修改元數據，不修改現有行的物理結構，顯然這樣會導致數據與表結構不一致，這個問題是怎么解決的呢？本文將簡單分析這個問題，并先回顧 online DDL。
概念
表結構
MySQL 屬于關系型數據庫，關系型數據庫的基本單位是表（或稱為關系），每個表由行（記錄）和列（字段）組成，具體由表結構（schema）定義表的組織方式，包括表中可以存儲哪些數據以及這些數據的類型。
MySQL 屬于磁盤數據庫，數據最終保存磁盤上，包括表結構與數據。
MySQL 5.7 中每個表對應兩個文件。
[root@DB test_zk]# ll -h t2.*
-rw-r----- 1 mysql mysql 8.5K Dec 18 18:28 t2.frm
-rw-r----- 1 mysql mysql 112K Dec 18 18:28 t2.ibd其中：
- frm 文件，保存表的元數據，包括表的定義（如列名、數據類型、索引等），顯然對于一張表的每行數據，表結構都是相同的，因此如果每行數據單獨保存表結構，將導致空間浪費；
- ibd 文件，保存數據和索引，前提是開啟獨立表空間。
MySQL 8.0 中每個表對應一個文件。
[root@DB test_zk]# ll -h t2*
-rw-r----- 1 mysql mysql 128K Feb 4 2024 t2.ibd其中：
- 不包括 frm 文件，原因是將 frm 文件中的元數據從二進制文本格式轉移到了事務型數據字典中；
- 將表結構保存在 InnoDB 系統表的優點是確保元數據操作的原子性和崩潰恢復能力。
MySQL 內存 buffer pool 中保存數據頁，同樣表結構也會保存在內存中，從而支持快速查詢和操作。
內存中表結構的使用場景：
- 第一次訪問表時，將元數據從磁盤加載到內存中，MySQL 為每一張表創建一個
TABLE_SHARE對象，其中保存表結構的全局共享信息（如字段定義、索引結構）； - 對于查詢操作，SQL 解析時，從內存中的
TABLE_SHARE獲取表結構，驗證列名、類型、索引是否存在； - 對于更新操作，DDL 執行期間更同步更新磁盤與內存中的元數據，MySQL 8.0 中可以保證 DDL 的原子性。
行格式
MySQL 中數據與表結構分開存儲，每行數據通過行格式進行組織，如下圖所示是 COMPACT 行格式。
row_format
其中：
- info_bits 是記錄頭信息中的一部分，占 4 bits，用于存儲行級別的狀態信息，包括是否標記刪除、是否是最小記錄，另外兩個 bit 是預留位；
- 對于非 INSTANT 算法，需要重建表，需要修改現有行的物理結構，因此每行數據都需要處理，執行效率低；
- 對于 INSTANT 算法，并不需要重建表，也不需要修改現有行的物理結構，只修改存儲在系統表中的表結構，因此執行效率高。
如果不修改數據，僅修改表結構，將導致數據與表結構不一致，這也是 INSTANT 算法要解決的核心問題。
MySQL 在讀取數據時，通過指針可以獲取記錄的開始位置，但是并沒有保存記錄的長度，也沒有保存每個字段的長度，因此需要通過逐個讀取字段獲取完整的行記錄，具體是先獲取每個字段的長度然后獲取字段的值。
其中：
- 對于定長字段，從表結構中獲取字段長度；
- 對于變長字段，從行記錄中獲取變長字段長度列表。
如下所示，表中有四個字段，其中第三個字段是定長字段，其他都是變長字段，使用 ascii 字符集，表中插入兩行記錄。
mysql> CREATE TABLE record_format_demo (
-> c1 VARCHAR(10),
-> c2 VARCHAR(10) NOTNULL,
-> c3 CHAR(10),
-> c4 VARCHAR(10)
-> ) CHARSET=ascii ROW_FORMAT=COMPACT;
Query OK, 0 rows affected (0.03 sec)
mysql> INSERTINTO record_format_demo(c1, c2, c3, c4)
VALUES('aaaa', 'bbb', 'cc', 'd'),
('eeee', 'fff', NULL, NULL);
Query OK, 2 rows affected (0.02 sec)
Records: 2 Duplicates: 0 Warnings: 0
mysql> SELECT * FROM record_format_demo;
+------+-----+------+------+
| c1 | c2 | c3 | c4 |
+------+-----+------+------+
| aaaa | bbb | cc | d |
| eeee | fff | NULL | NULL |
+------+-----+------+------+
2 rows in set (0.00 sec)下圖是兩條記錄存儲的行記錄，接下來看怎么從中讀取數據。
img
其中：
- 由于 InnoDB 表中沒有指定主鍵，也沒有唯一約束，自動為記錄添加 row_id 隱藏字段；
- 第一條記錄，01 03 04 是變成字段長度列表，0x61616161 表示字符串 'aaaa'，0x626262 表示字符串 'bbb'，0x64 表示字符串 'd'；
- 第一條記錄，c3 列的類型是定長字段 char(10)，實際存儲字符串 'cc'，而 ascii 字符集中的字節表示是 '0x6363'，雖然表示這個字符串只占用了 2 個字節，但整個 c3 列仍然占用了 10 個字節的空間，除真實數據以外的 8 個字節的統統都用空格字符填充，空格字符在 ascii 字符集的表示就是 0x20；
- 第二條記錄，NULL 值列表 06，對應二進制 0000 0110，其中 1 表示列值為 NULL。c3 和 c4 列的值都為 NULL，它們被存儲在了前面的 NULL 值列表處，在記錄的真實數據處就不再冗余存儲，從而節省存儲空間。
DDL
對于 DDL，最關心的兩點通常是鎖定級別與執行時間，前者決定影響范圍，后者決定影響時間，正常情況下這些都是 MySQL 內部自動處理的，但是執行前還是需要有所了解才可以，否則不一定可以滿足業務需求，比如財務分庫分表 DDL 加一個字段用時一周。
MySQL ALTER TABLE 語法中有以下兩個子句，包括 ALGORITHM 與 LOCK。
ALGORITHM 用于指定 DDL 算法，支持以下選項：
- COPY，MySQL 5.5 及之前的方式，會重建表且表的記錄格式會發生變化；
- INPLACE，MySQL 5.6 引入，支持在原表上進行操作，包括 rebuild 與 no-rebuild 兩種方式，其中 rebuild 會重建表，no-rebuild 方式只會修改表的元數據信息；
- INSTANT，MySQL 8.0.12 引入，只修改表的元數據信息；
- DEFAULT，如果不指定 ALGORITHM，默認為 DEFAULT，將由 MySQL 自行選擇 DDL 使用的算法，優先級由高到低為 INSTANT、INPLACE、COPY。
LOCK 用于指定 DDL 的鎖定級別，支持以下選項：
- NONE，允許查詢和 DML 操作。注意所有 DDL 操作都不阻塞讀請求，因此這里所說的 DML 不包括 select；
- SHARED，允許查詢，但是阻塞 DML 操作；
- EXCLUSIVE，阻塞查詢和 DML 操作；
- DEFAULT，如果不指定 LOCK，默認為 DEFAULT，將由 MySQL 自行選擇 LOCK 使用的級別，優先級由高到低為 NONE、SHARED、EXCLUSIVE。
因此：
- 當 ALGORITHM = COPY 時，LOCK 只能設置為 SHARED / EXCLUSIVE，也就是說都會阻塞 DML。如果不指定 LOCK 級別，默認使用 SHARED；
- 當 ALGORITHM = COPY / INPLACE 時，都需要拷貝數據重建表，因此表越大 DDL 執行時間越長。
簡單對比以上三種算法，理論上性能依次提高。
ALGORITHM | Permits Concurrent DML | DESCRIPTION |
COPY | No | copy original table data to new table |
INPLACE | Yes | not copy data, but may rebuild the table in place |
INSTANT | Yes | only modify metadata, table data is unaffected |
其中：
- online DDL 表示 DDL 執行過程中不阻塞 DML；
- 只有當 ALGORITHM = INSTANT / INPLACE 且 LOCK = NONE 時，才可以稱之為 online DDL；
- LOCK 的鎖定級別分多個，元數據鎖也分多個級別，但是這里的 LOCK 和元數據鎖無關。
下一個問題是執行后怎么判斷使用了哪種 DDL 算法。
COPY 與 INPLACE 可以通過 DDL 執行完成后的返回值中受影響行數 rows affected 來判斷，如果大于 0，表明發生數據拷貝，因此 ALGORITHM = COPY，否則 ALGORITHM = INPLACE。
For DDL operations that modify table data, you can determine whether a DDL operation performs changes in place or performs a table copy by looking at the “rows affected” value displayed after the command finishes.
但是具體 INPLACE 如何判斷是 rebuild 還是 no-rebuild 方式？目前未找到相關方法，可以簡單地根據執行時間來判斷。
分析
online DDL
online DDL 的執行過程可以分為三個階段，包括 prepare、run、commit。其中：
- prepare，創建臨時表，更新數據字典；
- run，重建表空間，存量數據拷貝到臨時表，對于大表，該階段用時最長；
- commit，增量數據應用到臨時表，更新系統表。
主要流程見下圖。
online_add_column
其中：
- prepare 與 commit 階段分別需要持有 EXCLUSIVE 元數據鎖禁止讀寫，因此如果有其他事務持有元數據鎖，將導致元數據鎖等待；
- run 階段降級為 SHARED 元數據鎖允許讀寫，顯然這就是所謂的 online，因此該階段不會導致元數據鎖等待，表明元數據鎖等待只可能發生在 prepare 與 commit 階段；
- DDL 執行期間的增量數據保存在 row_log 對象中，在 commit 階段回放這部分數據。
INSTANT
Instant add column 在增加列時，實際上只是修改了 schema，并沒有修改原來存儲在文件中的行記錄，不需要執行最耗時的 rebuild 和 apply row log 過程，因此效率非常高。
主要流程：
instant_add_column
原理
行格式 INSTANT_FLAG
8.0.12 版本開始支持 INSTANT 算法，僅修改元數據，不修改表數據。
Operations that support ALGORITHM=INSTANT only modify metadata in the data dictionary. No exclusive metadata locks are taken on the table during preparation and execution phases of the operation, and table data is unaffected, making the operations instantaneous.
If not specified explicitly, ALGORITHM=INSTANT is used by default by operations that support it. If ALGORITHM=INSTANT is specified but not supported, the operation fails immediately with an error.
需要注意的是僅支持在最后一列后加字段，不支持指在定位置加字段，這條限制的原因也將在下文中分析。
首先用一個示例分析 INSTANT 算法要解決的問題與具體實現。
下面有兩個 DDL，三條數據，每條數據對應不同的表結構，對應的字段數量分別為 2、3、4。
CREATE TABLE t1 (a INTNOTNULL AUTO_INCREMENT PRIMARY KEY, b INT);
INSERTINTO t1 VALUES(0, 1); -- Row 1
ALTERTABLE t1 ADDCOLUMN c INTDEFAULT10;
INSERTINTO t1 VALUES(0, 2, 20); -- Row 2
ALTERTABLE t1 ADDCOLUMN d INT;
INSERTINTO t1 VALUES(0, 3, 20, 10); -- Row 3寫入的場景比較簡單，直接使用最新的表結構即可，主要問題是查詢的場景，由于存量數據沒有更新，因此會缺失部分字段，所以問題就是如何判斷具體一行數據缺失哪些字段。
可以通過數據行的版本號來判斷數據行對應的表結構，但是為了降低實現的難度，并沒有采用這種方案，而是通過打標判斷是否執行過 instant add column 操作。
To make an ADD COLUMN metadata change only, it is necessary to mark the record accordingly, so that later scan can know which record is fit to which table definition.
One solution is to give every record or page a version number, meaning that the record or records in a page are defined by table structure version X, so to parse a record, a proper table structure can be picked accordingly. But this is more complex and lots of work need to be done.
A simpler solution is how this worklog works. Instead of giving record/page a version, a bit in record would be set if there was any instant ADD COLUMN happened before. With this bit set, it's possible to distinguish a record is inserted before any instant ADD COLUMN or not.
At the meantime, it's necessary to remember the existing column number when first instant ADD COLUMN happens.
具體實現中引入了兩個字段：
- 標志位，用于標識是否執行過 instant add column 操作，如果執行過，針對存量數據的缺失字段返回默認值；
- 字段數量，用于保存當前的字段數量，由于僅支持在末尾加字段，字段順序不變，因此通過字段數量就可以確定字段列表，超出的字段同樣返回默認值。
由于只有一個 bit 記錄字段的變化，因此不支持改變字段順序，所以僅支持在末尾加字段，并且不支持刪除字段。
Since there is only one bit to indicate the column change, so the order of columns are assumed to be not changed after instant ADD COLUMN. For short, the newly instantly added columns can only appended at last of the table.
如下圖所示，紅色部分分別表示 INSTANT_FLAG 標志位與字段數量。
new_format
其中：
- info_bits 的一個 bit 位 INSTANT_FLAG 表示是否執行過 instant add column 操作；
- 如果執行過 instant add column 操作，記錄中新增一個字段保存字段數量。
MySQL · 引擎特性 · 8.0 Instant Add Column功能解析 中使用 hexdump 解析 ibd 文件顯示 instant add column 操作后存量數據保持不變，增量數據中新增了兩個字段，包括 INSTANT_FLAG 標志位與字段數量，且行記錄中多了一個新增的字段。
查詢時，對于具體的一行數據，首先判斷 INSTANT_FLAG，如果執行過 instant add column 操作，接下來查詢字段數量，超出的字段使用默認值。
元數據 VERSION
8.0.29 中增強 INSTANT 算法，支持在指定位置加字段，且支持在指定位置刪除字段。
Prior to MySQL 8.0.29, an instantly added column could only be added as the last column of the table. From MySQL 8.0.29, an instantly added column can be added to any position in the table.
Instantly added or dropped columns create a new row version. Up to 64 row versions are permitted. A new TOTAL_ROW_VERSIONS column was added to the INFORMATION_SCHEMA.INNODB_TABLES table to track the number of row versions.
同樣用一個示例分析 INSTANT 算法要解決的問題與具體實現，不同之處在于這個案例中包括刪除列。
CREATE TABLE t1 (C1 char(10), C2 char(10), C3 char(10), C4 char(10));
INSERTINTO t1 values ("r1c1", "r1c2", "r1c3", "r1c4"); -- 數據一
ALTERTABLE t1 ADDCOLUMN C5 CHAR(10) DEFAULT"c5_def", ALGORITHM=INSTANT;
INSERTINTO t1 values ("r2c1", "r2c2", "r2c3", "r2c4", "r2c5"); -- 數據二
ALTERTABLE t1 DROPCOLUMN C3, ALGORITHM=INSTANT;
INSERTINTO t1 values ("r3c1", "r3c2", "r3c4", "r3c5"); -- 數據三
SELECT * FROM t1;
+------+------+------+--------+
| C1 | C2 | C4 | C5 |
+------+------+------+--------+
| r1c1 | r1c2 | r1c4 | c5_def |
| r2c1 | r2c2 | r2c4 | r2c5 |
| r3c1 | r3c2 | r3c4 | r3c5 |
+------+------+------+--------+由于 INSTANT ADD / DROP 操作并不會修改存量數據，因此磁盤上的實際數據如下圖所示，其中數據一多了 C3 列，缺少 C5 列，數據二多了 C3 列。
img
因此問題就是如何正確解析并返回存量數據。
具體實現中引入元數據 VERSION，包括表元數據、列元數據、行格式。
簡單說就是每行記錄中保存數據寫入時的行版本（row version），INSTANT ADD / DROP 操作時更新行版本，元數據中維護每個行版本對于字段的可見性。
如下圖所示，行格式中新增 ROW VERSION 字段保存數據寫入時當前表的 VERSION 信息。
img
一文為你解讀MySQL8.0 Instant DDL源碼實現 文章中詳細介紹了表元數據、列元數據與行格式的變化，下面僅展示 INSTANT DROP COLUMN 操作后的列元數據。
ALTER TABLE t1 DROP COLUMN C3, ALGORITHM=INSTANT;
INSERT INTO t1 values ("r3c1", "r3c2", "r3c4", "r3c5"); -- 數據三
SELECT NAME, HIDDEN, SE_PRIVATE_DATA FROM mysql.columns WHERE table_id = (SELECT ID FROM mysql.tables WHERE NAME = 't1');列元數據查詢結果見下圖。
img
其中：
- HIDDEN 列表示可見性。三個系統列的可見性為 SE，代表 INNODB 可見，SERVER 層不可見；
- 新增 C5 列后元數據 SE_PRIVATE_DATA 字段中保存列的默認值，表的 VERSION 值從 0 到 1，因此 version_added 記錄為 1；
- 刪除 C3 列后表的 VERSION 值從 1 變成 2，因此 version_dropped 記錄為 2。但是刪除 C3 列后元數據中保留 C3 列的原因是磁盤數據中依然有該列的數據，因此解析行記錄時需要所有列的元數據，但是由于列邏輯刪除，因此 HIDDEN = SE 表示不可見；
- 數據三 C4 列的 physical_pos 值為 6，但是因為數據三中沒有 C3 列的數據，所以 C4 列數據實際在位置 5。表明 physical_pos 記錄的是相對物理位置，要結合其他元信息才能確定該 record 中列的具體物理分布情況。
磁盤上數據分布見下圖。
img
需要注意的是行版本使用的限制是最多允許 64 個版本，因此當 INSTANT ADD / DROP 操作次數超過 64 時，如果 DDL 中指定 ALGORITHM = INSTANT，執行報錯，如果不指定，將退化為 ALGORITHM = INPLACE。 注意重建表后表的 VERSION 值清空，存量數據使用最新表結構。
Instantly added or dropped columns create a new row version. Up to 64 row versions are permitted. A new TOTAL_ROW_VERSIONS column was added to the INFORMATION_SCHEMA.INNODB_TABLES table to track the number of row versions.
結論
MySQL 中表結構與數據分開存儲，表結構同時維護在磁盤的數據文件與內存的數據字典中。
通過指針可以獲取每行數據的開始位置，但是數據中并不保存字段列表，也不保存每個字段的長度，因此讀取數據時需要先獲取每個字段的長度然后獲取字段的值。對于定長字段從表結構中獲取字段長度，對于變長字段從變成字段列表中獲取字段長度。
顯然讀取數據時需要確認每行數據對應的字段信息，因此對于非 INSTANT DDL 算法，每次執行 DDL 時都會修改現有行的物理結構，優點是可以保證數據與表結構的一致性，缺點是 DDL 的執行時間與表大小成正比。
為解決 DDL 慢的問題，出現了 INSTANT DDL 算法，該算法不修改現有行的物理結構，僅修改表結構元數據，當然這樣會導致數據與表結構不一致，這也是該算法要解決的核心問題，MySQL 通過兩個版本的迭代解決了該問題。
- 8.0.12，僅支持在最后一列后加字段，不支持指在定位置加字段，其中：
具體實現是在行格式中新增 INSTANT_FLAG 標志位與字段數量，在字段順序不變的前提下通過字段數量就可以確定字段列表；
使用限制是僅支持在末尾加字段，原因是要求字段順序不變；
查詢時，對于具體的一行數據，首先判斷 INSTANT_FLAG，如果執行過 instant add column 操作，接下來查詢字段數量，超出的字段使用默認值。
- 8.0.29，支持在指定位置加字段，且支持在指定位置刪除字段，其中：
- 具體實現是引入元數據 VERSION，包括表元數據、列元數據、行格式；
- 每行記錄中保存數據寫入時的行版本（row version），INSTANT ADD / DROP 操作時更新行版本，元數據中維護每個行版本對于字段的可見性；
- 使用限制是行版本最多允許 64 個版本，因此當 INSTANT ADD / DROP 操作次數超過 64 時，將退化為 INPLACE；
- 重建表后表的 VERSION 值清空，存量數據使用最新表結構。
待辦
- DDL 原子性
- DDL 回滾
- PolarDB
- TiDB
參考教程
- 《MySQL 實戰》
- 《MySQL 是怎樣運行的：從根兒上理解 MySQL》
- MySQL · 源碼閱讀 · 白話Online DDL
http://mysql.taobao.org/monthly/2021/03/06/
- MySQL Online DDL的改進與應用
https://www.cnblogs.com/xinysu/p/6732646.html
- MySQL · 引擎特性 · 8.0 Instant Add Column功能解析
http://mysql.taobao.org/monthly/2020/03/01/
- 一文為你解讀MySQL8.0 Instant DDL源碼實現
https://www.cnblogs.com/huaweiyun/p/18464467
- WL#11250: Support Instant Add Column
https://dev.mysql.com/worklog/task/?id=11250
- MySQL 8.0: InnoDB now supports Instant ADD COLUMN
https://dev.mysql.com/blog-archive/mysql-8-0-innodb-now-supports-instant-add-column/
- MySQL 8.0 INSTANT ADD and DROP Column(s)
https://blogs.oracle.com/mysql/post/mysql-80-instant-add-drop-columns
- 3分鐘掌握Mysql是如何存儲一行記錄
- [ibd2sql] mysql frm 文件結構解析
https://cloud.tencent.com/developer/article/2409341
- InnoDB 表空間可視化工具innodb_ruby
