從mongoDB 3.0版本引入WiredTiger存儲引擎(以下稱為WT)以來，一直有同學反應在高速寫入資料時WT引擎會間歇性寫挂起，有時候寫延遲達到了幾十秒，這确實是個嚴重的問題。引起這類問題的關鍵在于WT的LRU cache的設計模型，WT在設計LRU cache時采用分段掃描标記和hazardpointer的淘汰機制，在WT内部稱這種機制叫eviction cache或者WT cache，其設計目标是充分利用現代計算機超大記憶體容量來提高事務讀寫并發。在高速不間斷寫時記憶體操作是非常快的，但是記憶體中的資料最終必須寫入到磁盤上，将頁資料（page）由記憶體中寫入磁盤上是需要寫入時間，必定會和應用程式的高速不間斷寫産生競争，這在任何資料庫存儲引擎都是無法避免的，隻是由于WT利用大記憶體和寫無鎖的特性，讓這種不平衡現象更加顯著。下圖是一位網名叫chszs同學對mongoDB 3.0和3.2版本測試高速寫遇到的hang現象.
圖1
從上圖可以看出，資料周期性出現了hang現象，筆者在單獨對WT進行高并發順序寫時遇到的情況和上圖基本一緻，有時候挂起長達20秒。針對此問題我結合WT源碼和調試測試進行了分析，基本得出的結論如下：
1. WT引擎的eviction cache實作時沒有考慮lru cache的分級淘汰，隻是通過掃描btree來标記，這使得它和一些獨占式btree操作(例如：checkpoint)容易發生競争。
2. WTbtree的checkpoint機制設計存在bug，在大量并發寫事務發生時，checkpoint需要很長時間才能完成，造成刷入磁盤的資料很大，寫盤時間很長。容易引起cache 滿而挂起所有的讀寫操作。
3. WT引擎的redo log檔案超過1GB大小後就會另外建立一個新的redo log檔案來繼續存儲新的日志，在作業系統層面上建立一個檔案的是需要多次I/O操作，一旦和checkpoint資料刷盤操作同時發生，所有的寫也就挂起了。
要徹底弄清楚這幾個問題，就需要對從WT引擎的eviction cache原理來剖析，通過分析原理找到解決此類問題的辦法。先來看eviction cache是怎麼實作的，為什麼要這麼實作。
eviction cahce原理
eviction cache是一個LRU cache，即頁面置換算法緩沖區，LRU cache最早出現的地方是作業系統中關于虛拟記憶體和實體記憶體資料頁的置換實作，後被資料庫存儲引擎引入解決記憶體和磁盤不對等的問題。是以LRU cache主要是解決記憶體與資料大小不對稱的問題，讓最近将要使用的資料緩存在cache中，把最遲使用的資料淘汰出記憶體，這是LRU置換算法的基本原則。但程式代碼是無法預測未來的行為，隻能根據過去資料頁的情況來确定，一般我們認為過去經常使用的資料比不常用的資料未來被通路的機率更高，很多LRU cache大部分是基于這個規則來設計。
WT的eviction cache也不例外的遵循了這個LRU原理，不過WT的eviction cache對資料頁采用的是分段局部掃描和淘汰，而不是對記憶體中所有的資料頁做全局管理。基本思路是一個線程階段性的去掃描各個btree，并把btree可以進行淘汰的資料頁添加到一個lru queue中，當queue填滿了後記錄下這個過程目前的btree對象和btree的位置（這個位置是為了作為下次階段性掃描位置）,然後對queue中的資料頁按照通路熱度排序，最後各個淘汰線程按照淘汰優先級淘汰queue中的資料頁，整個過程是周期性重複。WT的這個evict過程涉及到多個eviction thread和hazard pointer技術。
WT的evict過程都是以page為機關做淘汰，而不是以K/V。這一點和memcache、redis等常用的緩存LRU不太一樣，因為在磁盤上資料的最小描述機關是page block，而不是記錄。
eviction線程模型
從上面的介紹可以知道WT引擎的對page的evict過程是個多線程協同操作過程，WT在設計的時候采用一種叫做leader-follower的線程模型，模型示意圖如下:
圖2
Leader thread負責周期性掃描所有記憶體中的btree索引樹，将符合evict條件的page索引資訊填充到eviction queue，當填充queue滿時，暫停掃描并記錄下最後掃描的btree對象和btree上的位置，然後對queue中的page按照事務的操作次數和通路次做一次淘汰評分，再按照評分從小到大做排序。也就是說最評分越小的page越容易淘汰。下個掃描階段的起始位置就是上個掃描階段的結束位置，這樣能保證在若幹個階段後所有記憶體中的page都被掃描過一次，這是為了公平性。這裡必須要說明的是一次掃描很可能隻是掃描記憶體一部分btree對象，而不是全部，是以我對這個過程稱為階段性掃描（evict pass），它不是對整個記憶體中的page做評分排序。這個階段性掃描的間隔時間是100毫秒，而觸發這個evict pass的條件就是WT cache管理的記憶體超出了設定的門檻值，這個在後面的eviction cache管理的記憶體小節中詳細介紹。
在evict pass後，如果evction queue中有等待淘汰的page存在就會觸發一個作業系統信号來激活follower thread來進行evict page工作。雖然evict pass的間隔時間通常是100毫秒，這裡有個問題就是當WT cache的記憶體觸及上限并且有大量寫事務發生時，讀寫事務線程在事務開始時會喚醒leader thread和follower thread,這就會産生大量的作業系統上下文切換，系統性能急劇下降。好在WT-2.8版本修複了這個問題，leader follower通過搶鎖來成為leader,通過多線程信号合并和周期性喚醒來follower,而且leader thread也承擔evict page的工作，可以避免大部分的線程喚醒和上下文切換。是不是有點像Nginx的網絡模型？
hazard pointer
hazard pointer是一個無鎖并發技術，其應用場景是單個線程寫和多個線程讀的場景，大緻的原理是這樣的，每個讀的線程設計一個與之對應的無鎖數組用于标記這個線程引用的hazard pointer對象。讀線程的步驟如下：
1. 讀線程在通路某個hazard pointer對象時，先将在自己的标記數組中标記通路的對象。
2. 讀線程在通路完畢某個hazard pointer對象時，将其對應的标記從标記數組中删除。
寫線程的步驟大緻是這樣的，寫線程如果需要對某個hazard pointer對象寫時，先判斷所有讀線程是否标記了這個對象，如果标記了，放棄寫。如果未标記，進行寫。
關于hazard pointer理論可以通路https://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf
Hazardpointer是怎樣應用在WT中呢？我們這樣來看待這個事情，把記憶體page的讀寫看做hazard pointer的讀操作，把page從記憶體淘汰到磁盤上的過程看做hazard pointer的寫操作，這樣瞬間就能明白為什麼WT在頁的操作上可以不遵守The FIX Rules規則，而是采用無鎖并發的頁操作。要達到這種通路方式有個條件就是記憶體中page本身的結構要支援lock free通路，這個在《剖析WiredTiger資料頁無鎖及壓縮》一文中介紹過了。從上面的描述可以看出evict page的過程中首先要做一次hazard pointer寫操作檢查，而後才能進行page的reconcile和資料落盤。
hazard pointer并發技術的應用是整個WT存儲引擎的關鍵，它關系到btree結構、internal page的構造、事務線程模型、事務并發等實作。Hazard pointer使得WT不依賴The Fix Rules規則，也讓WT的btree結構更加靈活多變。
Hazard pointer是比較新的無鎖程式設計模式，可以應用在很多地方，筆者曾在一個高并發媒體伺服器上用到這個技術，以後有機會把裡面的技術細節分享出來。
eviction cache管理的記憶體
evictioncache其實就是記憶體管理和page淘汰系統，目标就是為了使得管轄的記憶體不超過實體記憶體的上限，而觸發淘汰evict page動作的基礎依據就是記憶體上限。eviction cache管理的記憶體就是記憶體中page的記憶體空間，page的記憶體分為幾部分：
1. 從磁盤上讀取到已經刷盤的資料，在page中稱作disk buffer。如果WT沒有開啟壓縮且使用的MMAP方式讀寫磁盤，這個disk buffer的資料大小是不計在WT eviction cache管理範圍之内的。如果是開啟壓縮，會将從MMAP讀取到的page資料解壓到一個WT 配置設定的記憶體中，這個新配置設定的記憶體是計在WT eviction cache中的。
2. Page在記憶體中新增的修改事務資料記憶體空間，計入在eviction cache中。
3. Page基本的資料結構所有的記憶體空間，計入在eviction cache中。
PS:關于page結構和記憶體相關的細節請檢視《剖析WiredTiger資料頁無鎖及壓縮》。
WT在統計page的記憶體總量是通過一個footprint機制來統計兩項資料，一項是總的記憶體使用量mem_size，一項是增删改造成的髒頁資料總量dirty_mem_size。統計方式很簡單，就是每次對頁進行載入、增删改、分裂和銷毀時對上面兩項資料做原子增加或者減少計數，這樣可以精确計算到目前系統中WT引擎記憶體占用量。假設引擎外部配置最大記憶體空間為cache_size,記憶體上限觸發evict的比例為80%，記憶體髒頁上限觸發evict的比例為75%.那麼系統觸發evict pass操作的條件為：
mem_size> cache_size * 80%
或者
dirty_mem_size> cache_size * 75%
滿足這個條件leader線程就會進行evict pass階段性掃描并填充eivction queue,最後驅使follower線程進行evict page操作。
evict pass政策
前面介紹過evict pass是一個階段性掃描的過程，整個過程分為掃描階段、評分排序階段和evict排程階段。掃描階段是通過掃描記憶體中btree，檢查btree在記憶體中的page對象是否可以進行淘汰。掃描步驟如下：
1. 根據上次evict pass最後掃描的btree和它對應掃描的位置最為本次evict pass的起始位置,如果目前掃描的btree被其他事務線程設成獨占通路方式，跳過目前btree掃描下個btree對象。
2. 進行btree周遊掃描，如果page滿足淘汰條件，将page的索引對象添加到evict queue中，淘汰條件為：
ü 如果page是資料頁，必須page目前最新的修改事務必須早以evict pass事務。
ü 如果page是btree内部索引頁，必須page目前最新的修改事務必須早以evict pass事務且目前處于evict queue中的索引頁對象不多于10個。
ü 目前btree不處于正建立checkpoint狀态
3. 如果本次evict pass目前的btree有超過100個page在evict queue中或者btree處于正在建立checkpoint時，結束這個btree的掃描，切換到下一個btree繼續掃描。
4. 如果evict queue填充滿時或者本次掃描周遊了所有btree，結束本次evict pass。
PS:在開始evict pass時，evict queue可能存在有上次掃描且未淘汰出記憶體的page,那麼這次evict pass一定會讓queue填滿（大概400個page）。
評分排序階段是在evict pass後進行的，當queue中有page時，會根據每個page目前的通路次數、page類型和淘汰失敗次數等計算一個淘汰評分，然後按照評分從小打到進行快排，排序完成後，會根據queue中最大分數和最小分數計算一個淘汰邊界evict_throld，queue中所有大于evict_throld的page不列為淘汰對象。
WT為了讓btree索引頁盡量儲存在記憶體中，在評分的時候索引頁的分值會加上1000000分，讓btree索引頁免受淘汰。
evict pass最後會做個判斷，如果有follower線程存在，用系統信号喚醒follower進行evict page。如果系統中沒有follower，leader線程進行eivct page操作。這個模型在WT-2.81版本已經修改成搶占模式。
evict page過程
evictpage其實就是将evict queue中的page資料先寫入到磁盤檔案中，然後将記憶體中的page對象銷毀回收。整個evict page也分為三個階段：從evict queue中擷取page對象、hazard pointer判斷和page的reconcile過程，整個過程的步驟如下：
1. 從evict queue頭開始擷取page，如果發現page的索引對象不為空，對page進行LOCKED原子性标記防止其他讀事務線程引用并将page的索引從queue中删除。
2. 對淘汰的page進行hazard pointer，如果有其他線程對page标記hazard pointer, page不能被evict出記憶體，将page的評分加100.
3. 如果沒有其他線程對page标記hazard pointer,對page進行reconcile并銷毀page記憶體中的對象。
evict page的過程大部分是由follower thread來執行，這個在上面的線程模型一節中已經描述過。但在一個讀寫事務開始之前，會先檢查WT cache是否有足夠的記憶體空間進行事務執行，如果WT cache的記憶體容量觸及上限門檻值，事務執行線程會嘗試去執行evict page工作，如果evict page失敗，會進行線程堵塞等待直到 WT cache有執行讀寫事務的記憶體空間（是不是讀寫挂起了？）。這種狀況一般出現在正在建立checkpoint的時候，那麼checkpoint是怎麼引起這個現象的呢？下面來分析緣由。
eviction cache與checkpoint之間的事
衆所周知，建立checkpoint的過程是将記憶體中所有的髒頁（dirty page）同步刷入磁盤上并将redo log的重演位置設定到最後修改送出事務的redo log位置，相對于WT引擎來說，就是将eviction cache中的所有髒頁資料刷入磁盤但并不将記憶體中的page淘汰出記憶體。這個過程其實和正常的evict過程是沖突的，而且checkpoint過程中需要更多的記憶體完成這項工作，這使得在一個高并發寫的資料庫中有可能出現挂起的狀況發生。為了更好的了解整個問題的細節，我們先來看看WT checkpoint的原理和過程。
btree的checkpoint
WT引擎中的btree建立checkpoint過程還是比較複雜的，過程的步驟也比較多，而且很多步驟會涉及到索引、日志、事務和磁盤檔案等。我以WT-2.7(mongoDB 3.2)版本為例子，checkpoint大緻的步驟如下圖：
圖3
在上圖中，其中綠色的部分是在開始checkpoint事務之前會将所有的btree的髒頁寫入檔案OS cache中，如果在高速寫的情況下，寫的速度接近也reconcile的速度，那麼這個過程将會持續很長時間，也就是說OS cache中會存在大量未落盤的資料。而且在WT中btree采用的copy on write(寫時複制)和extent技術，這意味OS cache中的檔案資料大部分是在磁盤上是連續存儲的，那麼在綠色框最後一個步驟會進行同步刷盤，這個時候如果OS cache的資料量很大就會造成這個操作長時間占用磁盤I/O。這個過程是會把所有送出的事務修改都進行reconcile落盤操作。
在上圖的紫色是真正開始checkpoint事務的步驟，這裡需要解釋的是由于前面綠色步驟刷盤時間會比較長，在這個時間範圍裡會有新的寫事務發生，也就意味着會新的髒頁，checkpint必須把最新送出的事務修改落盤而且還要防止btree的分裂，這個時候就會獲得btree的獨占排他式通路，這時 eviction cache不能對這個btree上的頁進行evict操作（在這種情況下是不是容易造成WT cache滿而挂起讀寫事務？）。
PS:WT-2.8版本之後對checkpoint改動非常大，主要是針對上面兩點做了拆分，防止讀寫事務挂起發生，但大體過程是差不多的。
寫挂起
通過前面的分析大概知道寫挂起的原因了，主要引起挂起的現象主要是因為寫記憶體的速度遠遠高于寫磁盤的速度。先來看一份記憶體和磁盤讀寫的速度的資料吧。順序讀寫的對比：
圖4
從上圖可以看出，SATA磁盤的順序讀寫1MB資料大概需要8ms, SSD相對快一點，大概隻需2ms.但記憶體的讀寫遠遠大于磁盤的速度。SATA的随機讀取算一次I/O時間，大概在8ms 到10ms，SSD的随機讀寫時間比較快，大概0.1ms。
我們來分析checkpoint時挂起讀寫事務的幾種情況，假設系統在高速寫某一張表（每秒以100MB/S的速度寫入），每1分鐘做一次checkpoint。那麼1分鐘後開始進行圖3中綠色的步驟，這個步驟會在這一分鐘之内寫入的髒資料壓縮先後寫入到OS cache中，OS Cache可能存有近2GB的資料。這2GB的sync刷到磁盤上的時間至少需要10 ~ 20秒，而且磁盤I/O是被這個同步刷盤的任務占用了。這個時候有可能發生幾件事情：
1. 外部的寫事務還在繼續，事務送出時需要寫redo log檔案，這個時候磁盤I/O被占用了，寫事務挂起等待。
2. 外部的讀寫事務還在繼續，redo log檔案滿了，需要建立一個新的redo log檔案，但是建立檔案需要多次随機I/O操作，磁盤I/O暫時無法排程來建立檔案，所有寫事務挂起。
3. 外部讀寫事務線程還在繼續，因為WT cache觸發上限門檻值需要evict page。Evict page時也會調用reconcile将page寫入OS cache,但這個檔案的OS cache正在進行sync，evict page隻能等sync完成才能寫入OS cache，evict page線程挂起，其他讀寫事務在開始時會判斷是否有足夠的記憶體進行事務執行，如果沒有足夠記憶體，所有讀寫事務挂起。
這三種情況是因為階段性I/O被耗光而造成讀寫事務挂起的。
在圖3紫色步驟中，checkpoint事務開始後會先獲得btree的獨占排他通路方式，這意味這個btree對象上的page不能進行evict,如果這個btree索引正在進行高速寫入，有可能讓checkpoint過程中資料頁的reconcile時間很長，進而耗光WT cache記憶體造成讀寫事務挂起現象，這個現象極為在測試中極為少見（碰見過兩次）。 要解決這幾個問題隻要解決記憶體和磁盤I/O不對等的問題就可以了。
記憶體和磁盤I/O的權衡
引起寫挂起問題的原因多種多樣，但歸根結底是因為記憶體和磁盤速度不對稱的問題。因為WT的設計原則就是讓資料盡量利用現代計算機的超大記憶體，可是記憶體中的髒資料在checkpoint時需要同步寫入磁盤造成瞬間I/O很高，這是沖突的。要解決這些問題個人認為有以下幾個途徑：
1. 将MongoDB的WT版本更新到2.8，2.8版本對evict queue模型做了分級，盡量避免evict page過程中堵塞問題,2.8的checkpoint機制不在是分為預前刷盤和checkpoint刷盤，而是采用逐個對btree直接做checkpoint刷盤，緩解了OS cache緩沖太多的檔案髒資料問題。
2. 試試direct I/O或許會有不同的效果，WT是支援direct I/O模式。筆者試過direct I/O模式，讓WT cache徹底接管所有的實體記憶體管理，寫事務的并發會比MMAP模式少10%，但沒有出現過超過1秒的寫延遲問題。
3. 嘗試将WT cache設小點，大概設定成整個記憶體的1/4左右。這種做法是可以緩解OS cache中瞬間緩存太多檔案髒資料的問題，但會引起WT cache頻繁evict page和頻繁的leader-follower線程上下文切換。而且這種機制也依賴于OS page cache的刷盤周期，周期太長效果不明顯。
4. 用多個磁盤來存儲，redo log檔案放在一個單獨的機械磁盤上，資料放在單獨一個磁盤上，避免redo log與checkpoint刷盤發生競争。
5. 有條件的話，換成将磁盤換成SSD吧。這一點比較難，mongoDB現在也大量使用在OLAP和大資料存儲，而高速寫的場景都發生這些場景，成本是個問題。如果是OLTP建議用SSD。
這些方法隻能緩解讀寫事務挂起的問題，不能說徹底解決這個問題，WT引擎發展很快，開發團隊正對WT eviction cache和checkpoint正在做優化，這個問題慢慢變得不再是問題，尤其是WT-2.8版本，大量的模型和代碼優化都是集中在這個問題上。
後記
WT的eviction cache可能有很多不完善的地方，也确實給我們在使用的過程造成了一些困撓，應該用中立的角度去看待它。可以說它的讀寫并發速度是其他資料庫引擎不能比的，正是由于它很快，才會有寫挂起的問題，因為磁盤的速度就那麼快。以上的分析和建議或許對碰到類似問題的同學有用。
WT團隊的研發速度也很快，每年會釋出2 到3個版本，這類問題是他們正在重點解決的問題。在國内也有很多mongoDB這方面相關的專家，他們在解決此類問題有非常豐富的經驗，也可以請求他們來幫忙解決這類問題。
在本文問題分析過程中得到了阿裡雲張友東的幫助，在此表示感謝。