InnoDB存儲引擎MVCC實現原理

02-01

簡單背景介紹

MySQL

MySQL是現在最流行的關係型資料庫(RDB)的選擇, 創建一個應用時，無論是用戶數據還是訂單數據，使用關係型資料庫存儲是最可靠穩定的選擇，藉助RDB提供的可靠性、事務等功能，為應用提供完善的支持。MySQL是開源軟體，可以免費使用，MySQL在發展多年後越來越成熟，成為大部分公司的資料庫首選。MySQL採用插件式的存儲引擎架構，5.5版本後默認使用InnoDB存儲引擎。

MySQL架構

MySQL從概念上可以分為四層，頂層是接入層，不同語言的客戶端通過mysql的協議與mysql伺服器進行連接通信，接入層進行許可權驗證、連接池管理、線程管理等。下面是mysql服務層，包括sql解析器、sql優化器、數據緩衝、緩存等。再下面是mysql中的存儲引擎層，mysql中存儲引擎是基於表的。最後是系統文件層，保存數據、索引、日誌等。

MVCC

MVCC是Multi Version Concurrency Control的簡稱，代表多版本並發控制。為什麼需要MVCC，還要從資料庫事務的ACID特性說起。

相信很多朋友都了解ACID，它們分別代表了Atomicity(原子性), Consistency(一致性), Isolation(隔離性), Durability(持久性)。

原子性表示一個事務的操作結果要麼全部執行要麼全部不執行。

一致性表示事務總是從一個一致的狀態轉換到另一個一致的狀態。

隔離性表示一個事務的修改結果在什麼時間能夠被其他事務看到，SQL1992規範中對隔離性定義了不同的隔離級別，

分為讀未提交(READ UNCOMMITED),事務能夠看到其他事務沒有提及的修改，當另一個事務又回滾了修改後的情況又被稱為臟讀dirty read。

讀已提交(READ COMMITTED),事務能夠看到其他事務提交後的修改，這時會出現一個事務內兩次讀取數據可能因為其他事務提交的修改導致不一致的情況，稱為不可重複讀。可重複讀(REPEATABLE READ)，在兩次讀取時讀取到的數據的狀態是一致的，和序列化(SERIALIZABLE)可重複讀中可能出現第二次讀讀到第一次沒有讀到的數據，也就是被其他事務插入的數據，這種情況稱為幻讀phantom read, 序列化級別中不能出現幻讀。

隔離級別依次增強，但是導致的問題是並發能力的減弱。

各種資料庫廠商會對各個隔離級別進行實現。

和Java中的多線程問題相同，資料庫通常使用鎖來實現隔離性。

最原生的鎖，鎖住一個資源後會禁止其他任何線程訪問同一個資源。但是很多應用的一個特點都是讀多寫少的場景，很多數據的讀取次數遠大於修改的次數，而讀取數據間互相排斥顯得不是很必要。所以就使用了一種讀寫鎖的方法，讀鎖和讀鎖之間不互斥，而寫鎖和寫鎖、讀鎖都互斥。這樣就很大提升了系統的並發能力。之後人們發現並發讀還是不夠，又提出了能不能讓讀寫之間也不衝突的方法，就是讀取數據時通過一種類似快照的方式將數據保存下來，這樣讀鎖就和寫鎖不衝突了，不同的事務session會看到自己特定版本的數據。當然快照是一種概念模型，不同的資料庫可能用不同的方式來實現這種功能。

之後的討論默認均以REPEATABLE READ作為隔離級別。

InnoDB與MVCC

MySQL中的InnoDB存儲引擎的特性有，默認隔離級別REPEATABLE READ, 行級鎖，實現了MVCC, Consistent nonlocking read(默認讀不加鎖，一致性非鎖定讀), Insert Buffer, Adaptive Hash Index, DoubleWrite, Cluster Index。

上面列舉了這麼多，表示InnoDB有很多特性、很快。

InnoDB中通過UndoLog實現了數據的多版本，而並發控制通過鎖來實現。

Undo Log除了實現MVCC外，還用於事務的回滾。

Redo log, bin log, Undo log

MySQL Innodb中存在多種日誌，除了錯誤日誌、查詢日誌外，還有很多和數據持久性、一致性有關的日誌。

binlog，是mysql服務層產生的日誌，常用來進行數據恢復、資料庫複製，常見的mysql主從架構，就是採用slave同步master的binlog實現的, 另外通過解析binlog能夠實現mysql到其他數據源（如ElasticSearch)的數據複製。

redo log記錄了數據操作在物理層面的修改，mysql中使用了大量緩存，緩存存在於內存中，修改操作時會直接修改內存，而不是立刻修改磁碟，當內存和磁碟的數據不一致時，稱內存中的數據為臟頁(dirty page)。為了保證數據的安全性，事務進行中時會不斷的產生redo log，在事務提交時進行一次flush操作，保存到磁碟中, redo log是按照順序寫入的，磁碟的順序讀寫的速度遠大於隨機讀寫。當資料庫或主機失效重啟時，會根據redo log進行數據的恢復，如果redo log中有事務提交，則進行事務提交修改數據。這樣實現了事務的原子性、一致性和持久性。

Undo Log: 除了記錄redo log外，當進行數據修改時還會記錄undo log，undo log用於數據的撤回操作，它記錄了修改的反向操作，比如，插入對應刪除，修改對應修改為原來的數據，通過undo log可以實現事務回滾，並且可以根據undo log回溯到某個特定的版本的數據，實現MVCC。

redo log 和binlog的一致性，為了防止寫完binlog但是redo log的事務還沒提交導致的不一致，innodb 使用了兩階段提交

大致執行序列為

InnoDB prepare （持有prepare_commit_mutex）；n write/sync Binlog；n InnoDB commit (寫入COMMIT標記後釋放prepare_commit_mutex)。n

MVCC實現

innodb中通過B+樹作為索引的數據結構，並且主鍵所在的索引為ClusterIndex(聚簇索引), ClusterIndex中的葉子節點中保存了對應的數據內容。一個表只能有一個主鍵，所以只能有一個聚簇索引，如果表沒有定義主鍵，則選擇第一個非NULL唯一索引作為聚簇索引，如果還沒有則生成一個隱藏id列作為聚簇索引。

除了Cluster Index外的索引是Secondary Index(輔助索引)。輔助索引中的葉子節點保存的是聚簇索引的葉子節點的值。

InnoDB行記錄中除了剛才提到的rowid外，還有trx_id和db_roll_ptr, trx_id表示最近修改的事務的id,db_roll_ptr指向undo segment中的undo log。

新增一個事務時事務id會增加，trx_id能夠表示事務開始的先後順序。

Undo log分為Insert和Update兩種，delete可以看做是一種特殊的update，即在記錄上修改刪除標記。

update undo log記錄了數據之前的數據信息，通過這些信息可以還原到之前版本的狀態。

當進行插入操作時，生成的Insert undo log在事務提交後即可刪除，因為其他事務不需要這個undo log。

進行刪除修改操作時，會生成對應的undo log，並將當前數據記錄中的db_roll_ptr指向新的undo log

數據可見性判斷

CREATE TABLE `testunique` (n `id` int(11) unsigned NOT NULL AUTO_INCREMENT,n `uid` int(11) DEFAULT NULL,n `ukey` int(11) DEFAULT NULL,n PRIMARY KEY (`id`),n KEY `id_uid` (`uid`),n KEY `index_key` (`ukey`)n) ENGINE=InnoDB AUTO_INCREMENT=70 DEFAULT CHARSET=utf8;n隔離級別REPEATABLE READn

session1session2begin;select * from testunique;insert into testunique values(NULL, NULL, 1);select * from testunique;commitselect * from testunique;commitselect * from testunique;

只有當session2 commit之後的查詢才能查到session1插入的數據

事務可見性的處理過程:

RR級別下一個事務開始後第一個snapshot read的時候，會將當期活動的事務id記錄下來，記錄到read view中。RC級別則是每次snapshot read都會創建一個新的read view。

假設當前,read view中最大的事務id為tmax, 最小為tmin。則判斷一個數據是否可見以及對應的版本的方法為。

如果該行中的trx_id, 賦值給tid, 如果tid和當前事務id相等或小於tmin，說明是事務內發生的或開啟前的修改，則直接返回該版本數據; 如果

trx_id大於tmax, 則查看該版本的db_roll_ptr中的trx_id，賦值給tid並從頭開始判斷。如果tid小於tmax並且不在read view中，則返回，否則中回滾段中找出undo log的trx_id，賦值給tid從頭判斷。

所以可見性是，只有當第一次讀之前提交的修改和自己的修改可見，其他的均不可見。

代碼實現部分

在storage/innobase/include/read0types.h中

// Friend declarationnclass MVCC;n/** Read view lists the trx ids of those transactions for which a consistentnread should not see the modifications to the database. */n...nclass ReadView {n ...n private:n // Prevent copyingn ids_t(const ids_t&);n ids_t& operator=(const ids_t&);n private:n /** Memory for the array */n value_type* m_ptr;n /** Number of active elements in the array */n ulint m_size;n /** Size of m_ptr in elements */n ulint m_reserved;n friend class ReadView;n };npublic:n ReadView();n ~ReadView();n /** Check whether transaction id is valid.n @param[in] id transaction id to checkn @param[in] name table name */n static void check_trx_id_sanity(n trx_id_t id,n const table_name_t& name);n// 判斷一個修改是否可見n /** Check whether the changes by id are visible.n @param[in] id transaction id to check against the viewn @param[in] name table namen @return whether the view sees the modifications of id. */n bool changes_visible(n trx_id_t id,n const table_name_t& name) constn MY_ATTRIBUTE((warn_unused_result))n {n ut_ad(id > 0);n if (id < m_up_limit_id || id == m_creator_trx_id) {n return(true);n }n check_trx_id_sanity(id, name);n if (id >= m_low_limit_id) {n return(false);n } else if (m_ids.empty()) {n return(true);n }n const ids_t::value_type* p = m_ids.data();n return(!std::binary_search(p, p + m_ids.size(), id));n }n nprivate:n // Disable copyingn ReadView(const ReadView&);n ReadView& operator=(const ReadView&);nprivate:n // 活動事務中的id的最大n /** The read should not see any transaction with trx id >= thisn value. In other words, this is the "high water mark". */n trx_id_t m_low_limit_id;n // 活動事務id的最小值n /** The read should see all trx ids which are strictlyn smaller (<) than this value. In other words, this is then low water mark". */n // n trx_id_t m_up_limit_id;n /** trx id of creating transaction, set to TRX_ID_MAX for freen views. */n trx_id_t m_creator_trx_id;n /** Set of RW transactions that was active when this snapshotn was taken */n ids_t m_ids;n /** The view does not need to see the undo logs for transactionsn whose transaction number is strictly smaller (<) than this value:n they can be removed in purge if not needed by other views */n trx_id_t m_low_limit_no;n /** AC-NL-RO transaction view that has been "closed". */n bool m_closed;n typedef UT_LIST_NODE_T(ReadView) node_t;n /** List of read views in trx_sys */n byte pad1[64 - sizeof(node_t)];n node_t m_view_list;n};n

Undo log刪除

undo log在沒有活動事務依賴（用於consistent read或回滾)便可以清楚，innodb 中存在後台purge 線程進行後台輪詢刪除undo log。

Current Read snapshot read

REPEATABLE READ隔離級別下普通的讀操作即select都不加鎖，使用MVCC進行一致性讀取，這種讀取又叫做snapshot read。

而update, insert, delete, select … for update, select … lock in share mode都會進行加鎖，並且讀取的是當前版本，也就是READ COMMITTED讀的效果。innodb-locks-set.html中對各種操作會進行的鎖操作有詳細的說明，這裡我簡單總結下。

InnoDB中加鎖的方法是鎖住對應的索引，一個操作進行前會選擇一個索引進行掃描，掃描到一行後加上對應的鎖然後返回給上層然後繼續掃描。InnoDB支持行級鎖(record lock)，上述需要加鎖的操作中，除了select … lock in share mode 是加shared lock（共享鎖或讀鎖）外其他操作都加的是exclusive lock(即排他鎖或寫鎖)。在加行級鎖前，會對錶加一個intention lock，即意向鎖，意向所是表級鎖，不會和行級鎖衝突，主要用途是表明一個要加行級鎖或正在加鎖的操作。

另外InnoDB種除了record lock外還有一種gap lock，即鎖住兩個記錄間的間隙，防止其他事務插入數據，用於防止幻讀。當索引是主鍵索引或唯一索引時，不需要加gap lock。當索引不是唯一索引時，需要對索引數據和索引前的gap加鎖，這種方式叫做next-key locking。

另外在插入數據時，還需要提前最插入行的前面部分加上insert intention lock, 即插入意向鎖，插入意向鎖之間不會衝突，會和gap鎖衝突導致等待。當插入時遇到duplicated key錯誤時，會在要插入的行上加上share lock。

Mac下Debug mysql

git clone https://github.com/mysql/mysql-serverncd mysql-servernmkdir bldncmake .. -DWITH_DEBUG=1 -DDOWNLOAD_BOOST=1 -DWITH_BOOST=~/boostn

Clion中debug

下載最新版本的Clion,

import project 打開mysql-server文件夾

配置cmake 參數

之後Clion自動進行cmake

結束後可以看到有很多可以debug的程序

選擇mysqld，即為mysql伺服器程序

入口在sql/http://main.cc

加上斷點, 點擊debug後，經過一段時間build，即可進行debug了