張永翔，現任網易雲RDS開發，持續關注MySQL及數據庫運維領域，擅長MySQL運維，知乎ID：雁南歸。
MySQL 8.0中一個重要的新特性是對Redo Log子系統的重構，通過引入兩個新的數據結構recent_written和recent_closed，移除了之前的兩個熱點鎖：log_sys_t::mutex和log_sys_t::flush_order_mutex。
這種無鎖化的重構使得不同的線程在寫入redo_log_buffer時得以並行寫入，但因此帶來了log_buffer不再按LSN增長的順序寫入的問題，以及flush_list中的髒頁不再嚴格保證LSN的遞增順序問題。
本文將介紹MySQL 8.0中對log_buffer相關代碼的重構，並介紹併發寫log_buffer引入問題的解決辦法。
一、MySQL Redo Log系統概述
Redo Log又被稱為WAL ( Write Ahead Log)，是InnoDB存儲引擎實現事務持久性的關鍵。
在InnoDB存儲引擎中，事務執行過程被分割成一個個MTR (Mini TRansaction)，每個MTR在執行過程中對數據頁的更改會產生對應的日誌，這個日誌就是Redo Log。事務在提交時，只要保證Redo Log被持久化，就可以保證事務的持久化。
由於Redo Log在持久化過程中順序寫文件的特性，使得持久化Redo Log的代價要遠遠小於持久化數據頁，因此通常情況下，數據頁的持久化要遠落後於Redo Log。
每個Redo Log都有一個對應的序號LSN (Log Sequence Number)，同時數據頁上也會記錄修改了該數據頁的Redo Log的LSN，當數據頁持久化到磁盤上時，就不再需要這個數據頁記錄的LSN之前的Redo日誌，這個LSN被稱作Checkpoint。
當做故障恢復的時候，只需要將Checkpoint之後的Redo Log重新應用一遍，便可得到實例Crash之前未持久化的全部數據頁。
InnoDB存儲引擎在內存中維護了一個全局的Redo Log Buffer用以緩存對Redo Log的修改，mtr在提交的時候，會將mtr執行過程中產生的本地日誌copy到全局Redo Log Buffer中，並將mtr執行過程中修改的數據頁（被稱做髒頁dirty page）加入到一個全局的隊列中flush list。
InnoDB存儲引擎會根據不同的策略將Redo Log Buffer中的日誌落盤，或將flush list中的髒頁刷盤並推進Checkpoint。
在髒頁落盤以及Checkpoint推進的過程中，需要嚴格保證Redo日誌先落盤再刷髒頁的順序，在MySQL 8之前，InnoDB存儲引擎嚴格的保證MTR寫入Redo Log Buffer的順序是按照LSN遞增的順序，以及flush list中的髒頁按LSN遞增順序排序。
在多線程併發寫入Redo Log Buffer及flush list時，這一約束是通過兩個全局鎖log_sys_t::mutex和log_sys_t::flush_order_mutex實現的。
二、MySQL 5.7中MTR的提交過程
在MySQL 5.7中，Redo Log寫入全局的Redo Log Buffer以及將髒頁添加到flush list的操作均在mtr的提交階段中完成，簡化後的代碼為：
MySQL官方博客中有一張圖可以很好的展示了這個過程：
三、MySQL 8中的無鎖化設計
從上面的代碼中可以看到，在有多個MTR併發提交的時候，實際在這些MTR是串行的完成從本地日誌Copy redo到全局Redo Log Buffer以及添加Dirty Page到Flush list的。這裡的串行操作就是整個MTR 提交過程的瓶頸，如果這裡可以改成並行，想必可以提高MTR的提交效率。
但是串行化的提交可以嚴格保證Redo Log的連續性以及flush list中Page修改LSN的遞增，這兩個約束使得將Redo Log和髒頁刷入磁盤的行為很簡單。只要按順序將Redo Log Buffer中的內容寫入文件，以及按flush list的順序將髒頁刷入表空間，並推進Checkpoint即可。
當MTR不再以串行的方式提交的時候，會導致以下問題需要解決：
MTR串行的copy本地日誌到全局Redo Log Buffer可以保證每個MTR的日誌在Redo Log Buffer中都是連續的不會分割。當並行copy日誌的時候，需要有額外的手段保證mtr的日誌copy到Redo Log Buffer後仍然連續。MySQL 8.0中使用一個全局的原子變量log_t::sn在copy數據前為MTR在Redo Log Buffer中預留好需要的位置，這樣並行copy數據到Redo Log Buffer時就不會相互干擾。
由於多個MTR並行copy數據到Redo Log Buffer，那必然會有一些MTR copy的快一些，有些MTR copy的比較慢，這時候Redo Log Buffer中可能會有空洞，那麼就需要一種方法來確定Redo Log Buffer中的哪些內容可以寫入文件。MySQL 8.0中引入了新的數據結構Link_buf解決了這個問題。
並行的添加髒頁到flush list會打破flush list中每個數據頁對應LSN的單調性約束，如果仍然按flush list中的順序將髒頁落盤，那如何確定Checkpoint的位置？
下面本文將分別討論以上三個問題：
1、MTR複製日誌到Redo Log Buffer的無鎖化
在MySQL 8.0中， MTR的提交部分可以用如下偽代碼表示：
同5.7的代碼相比，最明顯的區別就是移除了log_sys->mutex鎖和log_sys->flush_order_mutex鎖，而實現Redo Log無鎖化的關鍵在於 log_buffer_reserve(*log_sys, len) 這個函數, 其中關鍵的代碼只有兩句：
可以看到，這裡是通過一個原子操作std::atomic<uint64>.fetch_add(log_len)實現在Copy Redo之前在全局Redo Log Buffer中預分配空間，實現並行寫入而不衝突。/<uint64>
2、Log Buffer空洞問題
預分配的方式可以使多個MTR不衝突的copy數據到Redo Log Buffer，但由於有些線程快一些，有些線程慢一些，必然會造成Redo Log Buffer的空洞問題，這個使得Redo Log Buffer刷入到磁盤的行為變得複雜。
如上圖所示，Redo Log Buffer中第一個和第三個線程已經完成了Redo Log的寫入，第二個線程正在寫入到Redo Log Buffer中，這個時候是不能將三個線程的Redo都落盤的。MySQL 8.0中引入了一個數據結構Link_buf解決這個問題。
Link_buf實際上是一個定長數組，並保證數組的每個元素的更新是原子性的，並以環形的方式複用已經釋放的空間。
Link_buf用於輔助表示其他數據結構的使用情況，在Link_buf中，如果一個索引位置i對應的值為非0值n，則表示Link_buf輔助標記的那個數據結構，從i開始後面n個元素已被佔用。同時Link_buf內部維護了一個變量M表示當前最大可達的LSN，Link_buf的結構示意圖如下所示：
在接口層面，Link_buf實際上定義了3個有效的行為：
Redo Log Buffer內部維護了兩個Link_buf類型的變量recent_written和recent_closed來維護Redo Log Buffer和flush list的修改信息。
對於redo log buffer，buffer的使用情況和recent_written的對應關係如下圖所示：
buf_ready_for_write_lsn這個變量維護的是可以保證無空洞的最大LSN值，也就是recent_written->tail的結果，在這之前的Redo Log都是可以安全的持久化到磁盤上的。
當第一個空洞位置的數據被寫入成功後，寫入數據的mtr通過調用log.recent_written.add_link(start_lsn, end_lsn)將recent_written內部狀態更新為如下圖所示的樣子：
這部分代碼在log0log.cc文件的log_buffer_write_completed方法中。
每次修改recent_written後，都會觸發一個獨立的線程log_writer向後掃描recent_written並更新buf_ready_for_write_lsn 值（調用recent_written->advance_tail()方法）。log_writer線程實際上就是執行日誌寫入到文件的線程。由log_writer線程掃描後的recent_written變量內部如下圖所示：
這樣就很好的解決了MTR併發寫入log_buffer造成的空洞問題。通過新引入的Link_buf類型的數據結構，可用很方便的知道哪一部分的Redo Log可以執行寫入磁盤的操作。
關於更多落盤的細節
在MySQL 8中，Redo log的落盤過程交由兩個獨立的線程完成，分別 log_writer和log_flusher，前者負責將Redo Log Buffer中的數據寫入到OS Cache中， 後者負責不停的執行fsync操作將OS Cache中的數據真正的寫入到磁盤裡。
兩個線程通過一個全局的原子變量log_t::write_lsn同步，write_lsn表示當前已經寫入到OS Cache的Redo log最大的LSN。
log buffer中的redo log的落盤不需要由用戶線程關心，用戶線程只需要在事務提交的時候，根據innodb_flush_log_at_trx_commit定義的不同行為，等待log_writer或log_flusher的通知即可。
log_writer線程會在監聽到recent_written被修改後，log_buffer中大於log_t::write_lsn小於buf_ready_for_write_lsn的redo log刷入到 OS Cache 中，並更新log_t::write_lsn。
log_flusher線程則在監聽到write_lsn更新後調用一次fsync並更新flushed_to_disk_lsn，該變量保存的是最新fsync到文件的值。
在這種設計模式下，用戶線程只負責寫日誌到log_buffer中，日誌的刷新和落盤是完全異步的，根據innodb_flush_log_at_trx_commit定義的不同行為，用戶線程在事務提交時需要等待日誌寫入操作系統緩存或磁盤。
在8.0之前，是由用戶線程觸發fsync或者等先提交的線程執行fsync( Group Commit行為)， 而在MySQL 8.0中，用戶線程只需要等待flushed_to_disk_lsn足夠大即可。
8.0中採用了一個分片的消息隊列來通知用戶線程，比如用戶線程需要等待flushed_to_disk_lsn >= X那麼就會加入到X所屬的消息隊列。分片可以有效降低消息同步損耗及一次需要通知的線程數。
在8.0中，由後臺線程log_flush_notifier通知等待的用戶線程，用戶線程、log_writer、log_flusher、log_flush_notifier四個線程之間的同步關係為。
8.0中為了避免用戶線程在陷入等待狀態後立即被喚醒，用戶線程會在等待前做自旋以檢查等待條件。8.0中新增加了兩個Dynamic Variable: innodb_log_spin_cpu_abs_lwm 和innodb_log_spin_cpu_pct_hwm控制執行自旋操作時CPU的水位，以免自旋操作佔用了太多的CPU。
3、flush list 併發控制以及check point 推進
回到上面的MTR提交的代碼，可以看到在將Redo Log寫入全局的log buffer中以後，mtr立即開始了將髒頁加入到flush list的步驟，其過程分為三個函數調用。
這裡同樣是通過一個Link_Buf類型的無鎖結構recent_closed來跟蹤處理flush list併發寫入狀態。
假設MTR在提交時產生的redo log的範圍是[start_lsn, end_lsn]，MTR在將這些redo對應的髒頁加入到某個flush list後，立即將start_lsn到end_lsn這段標記在recent_closed結構中。recent_closed同樣在內部維護了變量M，M對應著一個LSN，表示所有小於該LSN的髒頁都加入到了flush list中。
而與redo log寫入不同的是，MTR在寫入flush list之前，需要等待M值與start_lsn相差不是太多才可以寫入。這是為了將flush list上的空洞控制在一個範圍之內，這個過程的示意圖如下：
MTR在寫入到flush list之前，需要等待M值與start_lsn的相差範圍是一個常數L，這個常數度量了flush list中的無序度，它使得checkpoint的確定變得簡單（實際代碼中，L值就是recent_closed內部容量大小）。
從上面的代碼可以看到，在8.0中實際上加入到flush list的行為並不是完全併發的，但也不是5.7中完全串行的，而是被控制到一個範圍L之內的並行寫入。
由於MTR需要等待條件start_lsn - M < L成立才能加入到flush list , 反過來說，對於flush list中的每個Page ，如果其對應的修改的LSN為Ln，那麼可以斷定Ln - L對應的Page一定已經加入到了flush list中，而且一定在當前Page之前（因為Page添加時的檢查條件Ln-L < M，M之前是無空洞連續的LSN）。
也就是說，在延續原有的按flush list的順序刷新髒頁到磁盤的策略不變的情況下，只需要將Checkpoint的推進由原來的Page對應的LSN改成LSN-L即可。
MySQL 8.0中實際實現的時候，Checkpoint推進仍然是按照Page對應的LSN寫入的，只不過Recover的時候從Checkpoint - L開始執行，這兩張方式實際上是等效的。
不過在MySQL 8.0中，Recover階段從Checkpoint - L的地方開始，可能會遇到Checkpoint -L是某個Redo的中間位置而不是開始位置的情況，所以要對一些邊界情況做一些額外的工作才行。
四、總結
對於InnoDB存儲引擎，Redo Log的處理是實現事務持久性的關鍵，在MySQL 5.7及以前，通過兩個全局鎖，實際上使MTR的提交過程串行化保證了RedoLog以及髒頁處理的正確性，這使得MTR的提交過程因為鎖競爭的緣故無法充分的發揮多核的優勢。
8.0中通過引入的Link_buf 數據結構將整個模塊變成了Lock_free的模式，必然會帶來性能上的提升。
參考
MySQL8.0: 重新設計的日誌子系統
https://yq.aliyun.com/articles/592215?utm_content=m_49932
MySQL 8.0: New Lock free, scalable WAL design
https://mysqlserverteam.com/mysql-8-0-new-lock-free-scalable-wal-design/
MySQL Source Code Documentation/InnoDB Redo Log
https://dev.mysql.com/doc/dev/mysql-server/8.0.11/PAGE_INNODB_REDO_LOG.html
InnoDB的Redo Log分析
http://www.leviathan.vip/2018/12/15/InnoDB%E7%9A%84Redo-Log%E5%88%86%E6%9E%90/
MySQL · 引擎特性 · WAL那些事兒
http://mysql.taobao.org/monthly/2018/07/01/
近期熱文
帶人做項目吃力不討好？本文也許會給你些靈感
數據一致性“老大難”，美團數據治理平臺怎麼治好的？
從理論到案例，請盤下這篇Nginx監控運維乾貨
值得收藏：一份非常完整的MySQL規範
騰訊組織架構整改引思考：中小團隊要怎樣搭建架構？
閱讀更多 dbaplus社群 的文章
