摘要：?前言 日志先行的技術廣泛應用于現代數據庫中，其保證了數據庫在數據不丟的情況下，進一步提高了數據庫的性能。本文主要分析了WAL模塊在MySQL各個版本中的演進以及在阿里云新一代數據庫POLARDB中的改進。

前言

日志先行的技術廣泛應用于現代數據庫中，其保證了數據庫在數據不丟的情況下，進一步提高了數據庫的性能。本文主要分析了WAL模塊在MySQL各個版本中的演進以及在阿里云新一代數據庫POLARDB中的改進。

基礎知識

用戶如果對數據庫中的數據就行了修改，必須保證日志先于數據落盤。當日志落盤后，就可以給用戶返回操作成功，并不需要保證當時對數據的修改也落盤。如果數據庫在日志落盤前crash，那么相應的數據修改會回滾。在日志落盤后crash，會保證相應的修改不丟失。有一點要注意，雖然日志落盤后，就可以給用戶返回操作成功，但是由于落盤和返回成功包之間有一個微小的時間差，所以即使用戶沒有收到成功消息，修改也可能已經成功了，這個時候就需要用戶在數據庫恢復后，通過再次查詢來確定當前的狀態。 在日志先行技術之前，數據庫只需要把修改的數據刷回磁盤即可，用了這項技術，除了修改的數據，還需要多寫一份日志，也就是磁盤寫入量反而增大，但是由于日志是順序的且往往先存在內存里然后批量往磁盤刷新，相比數據的離散寫入，日志的寫入開銷比較小。 日志先行技術有兩個問題需要工程上解決：

1. 日志刷盤問題。由于所有對數據的修改都需要寫日志，當并發量很大的時候，必然會導致日志的寫入量也很大，為了性能考慮，往往需要先寫到一個日志緩沖區，然后在按照一定規則刷入磁盤，此外日志緩沖區大小有限，用戶會源源不斷的生產日志，數據庫還需要不斷的把緩存區中的日志刷入磁盤，緩存區才可以復用，因此，這里就構成了一個典型的生產者和消費者模型。現代數據庫必須直面這個問題，在高并發的情況下，這一定是個性能瓶頸，也一定是個鎖沖突的熱點。

2. 數據刷盤問題。在用戶收到操作成功的時候，用戶的數據不一定已經被持久化了，很有可能修改還沒有落盤，這就需要數據庫有一套刷數據的機制，專業術語叫做刷臟頁算法。臟頁(內存中被修改的但是還沒落盤的數據頁)在源源不斷的產生，然后要持續的刷入磁盤，這里又湊成一個生產者消費者模型，影響數據庫的性能。如果在臟頁沒被刷入磁盤，但是數據庫異常crash了，這個就需要做奔潰恢復，具體的流程是，在接受用戶請求之前，從checkpoint點(這個點之前的日志對應的數據頁一定已經持久化到磁盤了)開始掃描日志，然后應用日志，從而把在內存中丟失的更新找回來，最后重新刷入磁盤。這里有一個很重要的點：在數據庫正常啟動的期間，checkpoint怎么確定，如果checkpoint做的慢了，就會導致奔潰恢復時間過長，從而影響數據庫可用性，如果做的快了，會導致刷臟壓力過大，甚至數據丟失。

MySQL中為了解決上述兩個問題，采用了以下機制:

1. 當用戶線程產生日志的時候，首先緩存在一個線程私有的變量(mtr)里面，只有完成某些原子操作(例如完成索引分裂或者合并等)的時候，才把日志提交到全局的日志緩存區中。全局緩存區的大小(innodb_log_file_size)可以動態配置。當線程的事務執行完后，會按照當前的配置(innodb_flush_log_at_trx_commit)決定是否需要把日志從緩沖區刷到磁盤。

2. 當把日志成功拷貝到全局日志緩沖區后，會繼續把當前已經被修改過的臟頁加入到一個全局的臟頁鏈表中。這個鏈表有一個特性：按照最早被修改的時間排序。例如，有數據頁A,B,C，數據頁A早上9點被第一次修改，數據頁B早上9點01分被第一次修改，數據頁C早上9點02分被第一次修改，那么在這個鏈表上數據頁A在最前，B在中間，C在最后。即使數據頁A在早上9點之后又一次被修改了，他依然排在B和C之前。在數據頁上，有一個字段來記錄這個最早被修改的時間：oldest_modification，只不過單位不是時間，而是lsn，即從數據庫初始化開始，一共寫了多少個字節的日志，由于其是一個遞增的值，因此可以理解為廣義的時間，先寫的數據，其產生的日志對應的lsn一定比后寫的小。在臟頁列表上的數據頁，就是按照oldest_modification從小到大排序，刷臟頁的時候，就從oldest_modification小的地方開始。checkpoint就是臟頁列表中最小的那個oldest_modification，因為這種機制保證小于最小oldest_modification的修改都已經刷入磁盤了。這里最重要的是，臟頁鏈表的有序性，假設這個有序性被打破了，如果數據庫異常crash，就會導致數據丟失。例如，數據頁ABC的oldest_modification分別為120，100，150，同時在臟頁鏈表上的順序依然為A，B，C，A在最前面，C在最后面。數據頁A被刷入磁盤，然后checkpoint被更新為120，但是數據頁B和C都還沒被刷入磁盤，這個時候，數據庫crash，重啟后，從checkpoint為120開始掃描日志，然后恢復數據，我們會發現，數據頁C的修改被恢復了，但是數據頁B的修改丟失了。

在第一點中的，我們提到了私有變量mtr，這個結構除了存儲了修改產生的日志和臟頁外，還存儲了修改臟頁時加的鎖。在適當的時候(例如日志提交完且臟頁加入到臟頁鏈表)可以把鎖給釋放。

接下來，我們結合各個版本的實現，來剖析一下具體實現細節。注意，以下內容需要一點MySQL源碼基礎，適合MySQL內核開發者以及資深的DBA。

MySQL 5.1版本的處理方式

5.1的版本是MySQL比較早的版本，那個時候InnoDB還是一個插件。因此設計也相對粗糙，簡化后的偽代碼如下：

日志進入全局緩存:

mutex_enter(log_sys->mutex);
copy?local?redo?log?to?global?log?buffer
mtr.start_lsn?=?log_sys->lsn
mtr.end_lsn?=?log_sys->lsn?+?log_len?+?log_block_head_or_tail_len
increase?global?lsn:?log_sys->lsn,?log_sys->buf_freefor?every?lock?in?mtr????if?(lock?==?share?lock)
????????release?share?lock?directly????else?if?(lock?==?exclusive?lock)????????if?(lock?page?is?dirty)????????????
????????if?(page.oldest_modification?==?0)??//This?means?this?page?is?not?in?flush?list
????????page.oldest_modification?=?mtr.start_lsn
???????????????add?to?flush?list???????????//?have?one?flush?list?only
????????release?exclusive?lock
mutex_exit(log_sys->mutex);

日志寫入磁盤：

mutex_enter(log_sys->mutex);log_sys->write_lsn?=?log_sys->lsn;
write?log?to?log?file
mutex_exit(log_sys->mutex);

更新checkpoint:

page?=?get_first_page(flush_list)
checkpoint_lsn?=?page.oldest_modification
write?checkpoint_lsn?to?log?file

奔潰恢復：

read?checkpoint_lsn?from?log?filestart?parse?and?apply?redo?log?from?checkpoint_lsn?point

從上述偽代碼中可以看出，由于日志進入全局的緩存都在臨界區內，不但保證了拷貝日志的有序性，也保證了臟頁進入臟頁鏈表的有序性。需要獲取checkpoint_lsn時，只需從臟頁鏈表中獲取第一個數據頁的oldest_modification即可。奔潰恢復也只需要從記錄的checkpoint點開始掃描即可。在高并發的場景下，有很多線程需要把自己的local日志拷貝到全局緩存，會造成鎖熱點，另外在全局日志寫入日志文件的地方，也需要加鎖，進一步造成了鎖的爭搶。此外，這個數據庫的緩存(Buffer Pool)只有一個臟頁鏈表，性能也不高。這種方式存在于早期的InnoDB代碼中，通俗易懂，但在現在的多核系統上，顯然不能做到很好的擴展性。

MySQL 5.5，5.6，5.7版本的處理方式

這三個版本是目前主流的MySQL版本，很多分支都在上面做了不少優化，但是主要的處理邏輯變化依然不大：

日志進入全局緩存:

mutex_enter(log_sys->mutex);
copy?local?redo?log?to?global?log?buffer
mtr.start_lsn?=?log_sys->lsn
mtr.end_lsn?=?log_sys->lsn?+?log_len?+?log_block_head_or_tail_len
increase?global?lsn:?log_sys->lsn,?log_sys->buf_free
mutex_enter(log_sys->log_flush_order_mutex);
mutex_exit(log_sys->mutex);for?every?page?in?mtr???if?(lock?==?exclusive?lock)????if?(page?is?dirty)????????
if?(page.oldest_modification?==?0)??//This?means?this?page?is?not?in?flush?list
????????page.oldest_modification?=?mtr.start_lsn
????????????????add?to?flush?list?according?to?its?buffer?pool?instance
mutex_exit(log_sys->log_flush_order_mutex);for?every?lock?in?mtr
????release?all?lock?directly

日志寫入磁盤：

mutex_enter(log_sys->mutex);log_sys->write_lsn?=?log_sys->lsn;
write?log?to?log?file
mutex_exit(log_sys->mutex);

更新checkpoint:

for?ervery?flush?list:
????page?=?get_first_page(curr_flush_list);????if?current_oldest_modification?>?page.oldest_modification
????current_oldest_modification?=?page.oldest_modification
checkpoint_lsn?=?current_oldest_modification
write?checkpoint_lsn?to?log?file

奔潰恢復：

read?checkpoint_lsn?from?log?filestart?parse?and?apply?redo?log?from?checkpoint_lsn?point

主流的版本中最重要的一個優化是，除了log_sys->mutex外，引入了另外一把鎖log_sys->log_flush_order_mutex。在臟頁加入到臟頁鏈表的操作中，不需要log_sys->mutex保護，而是需要log_sys->log_flush_order_mutex保護，這樣減少了log_sys->mutex的臨界區，從而減少了熱點。此外，引入多個臟頁鏈表，減少了單個鏈表帶來的沖突。 注意，主流的分支還做了很多其他的優化，例如：

1. 引入雙全局日志緩存。如果只有一個全局日志緩存，當這個日志緩存在寫盤的時候，會導致后續的用戶線程無法往里面拷貝日志，直到刷盤結束。有了雙日志緩存，其中一個用來接收用戶提交過來的日志，另外一個可以用來把之前的日志刷盤，這樣用戶線程不需要等待。

2. 日志自動擴展。如果發現當前需要拷貝的日志比全局的日志緩存一半還大，就會自動把全局日志緩存給擴大一倍。注意，只要擴大后，就不會再縮小了。

3. 日志對齊。早期的磁盤都是512原子寫，現代的SSD磁盤大部分是4K原子寫。如果小于4K的寫入，會導致先把4K先讀取出來，然后內存中修改，再寫下去，性能低下。但是有了日志對齊這個優化后，可以以指定大小刷日志，不夠大的后面填0補齊，能提高寫入效率。 這里貼一個優化后的日志寫入磁盤的偽代碼：

   mutex_enter(log_sys->write_mutex);
   check?if?other?thead?has?done?write?for?us
   mutex_enter(log_sys->mutex);
   calculate?the?range?log?need?to?be?write
   switch?log?buffer?so?that?user?threads?can?still?copy?log?during?writing
   mutex_exit(log_sys->mutex);
   align?log?to?specified?size?if?needed
   write?log?to?log?file?
   log_sys->write_lsn?=?log_sys->lsn;
   mutex_exit(log_sys->write_mutex);

   可以看到log_sys->mutex被進一步縮小。往日志文件里面寫日志的階段已經不許要log_sys->mutex保護了。 有了以上的優化，MySQL的日志子系統在大多數場景下不會達到瓶頸。但是，用戶線程往全局日志緩存拷貝日志以及臟頁加入臟頁鏈表這兩個操作，依然是基于鎖機制的，很難發揮出多核系統的性能。

MySQL 8.0版本的處理方式

之前的版本雖然做了很多優化，但是沒有真正做到lock free，在高并發下，可以看到很多鎖沖突。官方因此在這塊下了大力氣，徹頭徹尾的大改了一番。 詳細細節可以參考上個月這篇月報。 這里再簡單概括一下。 在日志寫入階段，通過atomic變量分配保留空間，由于atomic變量增長是個原子操作，所以這一步不要加鎖。分配完空間后，就可以拷貝日志，由于上一步中空間已經被預留，所以多線程可以同時進行拷貝，而不會導致日志有重疊。但是不能保證拷貝完成的先后順序，有可能先拷貝的，后完成，所以需要有一種機制來保證某個點之前的日志已經都拷貝到全局日志緩存了。這里，官方就引入了一種新的lock free數據結構Link_buf，它是一個數組，用來標記拷貝完成的情況。每個用戶線程完成拷貝后，就在那個數組中標記一下，然后后臺再開一個線程來計算是否有連續的塊完成拷貝了，完成了就可以把這些日志刷到磁盤。 在臟頁插入臟頁鏈表這一塊，官方也提出了一種有趣的算法，它也是基于新的lock free數據結構Link_buf。基本思想是，臟頁鏈表的有序性可以被部分的打破，也就是說，在一定范圍內可以無序，但是整體還是有序的。這個無序程序是受控的。假設臟頁鏈表第一個數據頁的oldest_modification為A, 在之前的版本中，這個臟頁鏈表后續的page的oldest_modification都嚴格大于等于A，也就是不存在一個數據頁比第一個數據頁還老。在MySQL 8.0中，后續的page的oldest_modification并不是嚴格大于等于A，可以比A小，但是必須大于等于A-L，這個L可以理解為無序度，是一個定值。那么問題來了，如果臟頁鏈表順序亂了，那么checkpoint怎么確定，或者說是，奔潰恢復后，從那個checkpoint_lsn開始掃描日志才能保證數據不丟。官方給出的解法是，checkpoint依然由臟頁鏈表中第一個數據頁的oldest_modification的確定，但是奔潰恢復從checkpoint_lsn-L開始掃描(有可能這個值不是一個mtr的邊界，因此需要調整)。 所以可以看到，官方通過link_buf這個數據結構很巧妙的解決了局部日志往全局日志拷貝的問題以及臟頁插入臟頁鏈表的問題。由于都是lock free算法，因此擴展性會比較好。 但是，從實際測試的情況來看，似乎是因為用了太多的條件變量event，在我們的測試中沒有官方標稱的性能。后續我們會進一步分析原因。

POLARDB FOR MYSQL的處理方式

POLARDB作為阿里云下一代關系型云數據庫，我們自然在InnoDB日志子系統做了很多優化，其中也包含了上述的領域。這里可以簡單介紹一下我們的思路:

每個buffer pool instance都額外增加了一把讀寫鎖(rw_locks)，主要用來控制對全局日志緩存的訪問。 此外還引入兩個存儲臟頁信息的集合，我們這里簡稱in-flight set和ready-to-process set。主要用來臨時存儲臟頁信息。

日志進入全局緩存:

release?all?share?locks?holded?by?this?mtr's?page
acquire?log_buf?s-locks?for?all?buf_pool?instances?for?which?we?have?dirty?pages
reserver?enough?space?on?log_buf?via?increasing?atomit?variables????????//Just?like?MySQL?8.0
copy?local?log?to?global?log?buffer
add?all?pages?dirtied?by?this?mtr?to?in-flight?set
release?all?exclusive?locks?holded?by?this?mtr's?page
release?log_buf?s-locks?for?all?buf_pool?instances

日志寫入磁盤：

mutex_enter(log_sys->write_mutex)
check?if?other?thead?has?done?write?for?us
mutex_enter(log_sys->mutex)
acquire?log_buf?x-locks?for?all?buf_pool?instances
update?log_sys->lsn?to?newest
switch?log?buffer?so?that?user?threads?can?still?copy?log?during?writing
mutex_exit(log_sys->mutex)
release?log_buf?x-locks?for?all?buf_pool?instances
align?log?to?specified?size?if?needed
write?log?to?log?file?
log_sys->write_lsn?=?log_sys->lsn;
mutex_exit(log_write_mutex)

刷臟線程(每個buffer pool instance)：

acquire?log_buf?x-locks?for?specific?buffer?pool?instance
toggle?in-flight?set?with?ready-to-process?set.?Only?this?thread?will?toggle?between?these?
two.release?log_buf?x-locks?for?specific?buffer?pool?instancefor?each?page?in?ready-to-process???
add?page?to?flush?listdo?normal?flush?page?operations

更新checkpoint:

for?ervery?flush?list:
????acquire?log_buf?x-locks?for?specific?buffer?pool?instance
????ready_to_process_lsn?=?minimum?oldest_modification?in?ready-to-process?set
????flush_list_lsn?=?get_first_page(curr_flush_list).oldest_modification
????min_lsn?=?min(ready_to_process_lsn,?flush_list_lsn)????release?log_buf?x-locks?for?specific?buffer?pool?instance
????if?current_oldest_modification?>?min_lsn
????current_oldest_modification?=?min_lsn
checkpoint_lsn?=?current_oldest_modification
write?checkpoint_lsn?to?log?file

奔潰恢復：

read?checkpoint_lsn?from?log?filestart?parse?and?apply?redo?log?from?checkpoint_lsn?point

在局部日志拷貝入全局日志這塊，與官方MySQL 8.0類似，首先利用atomic變量的原子增長來分配空間，但是MySQL 8.0是使用link_buf來保證拷貝完成，而在POLARDB中，我們使用讀寫鎖的機制，即在拷貝之前加上讀鎖，拷貝完才釋放讀鎖，而在日志寫入磁盤前，首先嘗試加上寫鎖，利用寫鎖和讀鎖互斥的特性，保證在獲取寫鎖時所有讀鎖都釋放，即所有拷貝操作都完成。 在臟頁進入臟頁鏈表這塊，官方MySQL允許臟頁鏈表有一定的無序度(也是通過link_buf保證)，然后通過在奔潰恢復的時候從checkpoint_lsn-L開始掃描的機制，來保證數據的一致性。在POLARDB中，我們解決辦法是，把臟頁臨時加入到一個集合，在刷臟線程工作前再按順序加入臟頁鏈表，通過獲取寫鎖來保證在加入臟頁鏈表前，整個集合是完整的。換句話說，假設這個臟頁集合最小的oldest_modification為A，那么可以保證沒有加入臟頁集合的臟頁的oldest_modification都大于等于A。 從臟頁集合加入到臟頁鏈表的操作，我們沒有加鎖，所以在更行checkpoint的時候，我們需要使用min(ready_to_process_lsn, flush_list_lsn)來作為checkpoint_lsn。在奔潰恢復的時候，直接從checkpoint_lsn掃描即可。 此外，我們在POLARDB上，還做了額外的優化:

1. 提前釋放page的共享鎖。如果一個數據頁被加了共享鎖，說明沒有被修改，只是被讀取而已，我們可以提前釋放掉，這有助于減少熱點數據頁的鎖沖突。

2. 在日志進入全局緩存時，我們沒有及時更新log_sys->lsn，而是先更新另外一個變量，當在日志寫入磁盤前，即獲取log_buf寫鎖后，然后在更新log_sys->lsn。主要是為了減少沖突。

最后我們測試了一下性能，在non_index_updates的全內存高并發測試下，性能有10%的提高。

Upstream?5.6.40:?71KMySQL-8.0:?132KPolarDB?(master):?162KPolarDB(master?+?mtr_optimize):?178K

當然，這不是我們最高的性能，可以小小透露一下，通過對事務子系統的優化，我們可以達到200K的性能。 更多更好用的功能都在路上，歡迎使用POLARDB！

總結

日志子系統是關系型數據庫不可獲取的模塊，也是數據庫內核開發者非常感興趣的模塊，本文結合代碼分析了MySQL不同版本的WAL機制的實現，希望對大家有所幫助。