導(dǎo)語：計算機(jī)硬件在飛速發(fā)展，數(shù)據(jù)規(guī)模在急速膨脹，但是數(shù)據(jù)庫仍然使用是十年以前的架構(gòu)體系，WiredTiger 嘗試打破這一切块促，充分利用多核與大內(nèi)存時代荣堰，開發(fā)一種真正滿足未來大數(shù)據(jù)管理所需的數(shù)據(jù)庫。本文由袁榮喜向「高可用架構(gòu)」投稿竭翠，介紹對 WiredTiger 源代碼學(xué)習(xí)過程中對數(shù)據(jù)庫設(shè)計的感悟振坚。

袁榮喜，學(xué)霸君工程師斋扰，2015年加入學(xué)霸君渡八，負(fù)責(zé)學(xué)霸君的網(wǎng)絡(luò)實時傳輸和分布式系統(tǒng)的架構(gòu)設(shè)計和實現(xiàn)，專注于基礎(chǔ)技術(shù)領(lǐng)域传货，在網(wǎng)絡(luò)傳輸屎鳍、數(shù)據(jù)庫內(nèi)核、分布式系統(tǒng)和并發(fā)編程方面有一定了解问裕。

WiredTiger 從被 MongoDB 收購到成為 MongoDB 的默認(rèn)存儲引擎的一年半哥艇，得到了迅猛的發(fā)展，也逐步被外部熟知僻澎。

現(xiàn)代計算機(jī)近 20 年來 CPU 的計算能力和內(nèi)存容量飛速發(fā)展，但磁盤的訪問速度并沒有得到相應(yīng)的提高十饥，WT 就是在這樣的一個情況下研發(fā)出來窟勃，它設(shè)計了充分利用 CPU 并行計算的內(nèi)存模型的無鎖并行框架，使得 WT 引擎在多核 CPU 上的表現(xiàn)優(yōu)于其他存儲引擎逗堵。

針對磁盤存儲特性秉氧，WT 實現(xiàn)了一套基于 BLOCK/Extent 的友好的磁盤訪問算法，使得 WT 在數(shù)據(jù)壓縮和磁盤 I/O 訪問上優(yōu)勢明顯蜒秤。實現(xiàn)了基于 snapshot 技術(shù)的 ACID 事務(wù)汁咏，snapshot 技術(shù)大大簡化了 WT 的事務(wù)模型，摒棄了傳統(tǒng)的事務(wù)鎖隔離又同時能保證事務(wù)的 ACID作媚。WT 根據(jù)現(xiàn)代內(nèi)存容量特性實現(xiàn)了一種基于 Hazard Pointer 的 LRU cache 模型攘滩，充分利用了內(nèi)存容量的同時又能擁有很高的事務(wù)讀寫并發(fā)。

在本文中纸泡，我們主要針對 WT 引擎的事務(wù)來展開分析漂问，來看看它的事務(wù)是如何實現(xiàn)的。說到數(shù)據(jù)庫事務(wù)女揭，必然先要對事務(wù)這個概念和 ACID 簡單的介紹蚤假。

基本概念：事務(wù)與 ACID

什么是事務(wù)？

事務(wù)就是通過一系列操作來完成一件事情吧兔，在進(jìn)行這些操作的過程中磷仰，要么這些操作完全執(zhí)行，要么這些操作全不執(zhí)行境蔼，不存在中間狀態(tài)灶平，事務(wù)分為事務(wù)執(zhí)行階段和事務(wù)提交階段伺通。一般說到事務(wù)，就會想到它的特性— ACID民逼，那么什么是 ACID 呢泵殴？我們先用一個現(xiàn)實中的例子來說明：AB 兩同學(xué)賬號都有 1,000 塊錢，A 通過銀行轉(zhuǎn)賬向 B 轉(zhuǎn)了 100拼苍，這個事務(wù)分為兩個操作,即從 A 同學(xué)賬號扣除 100笑诅，向 B 同學(xué)賬號增加 100。

原子性（Atomicity）

組成事務(wù)的系列操作是一個整體疮鲫，要么全執(zhí)行吆你，要么不執(zhí)行。通過上面例子就是從 A 同學(xué)扣除錢和向 B 同學(xué)增加 100 是一起發(fā)生的俊犯，不可能出現(xiàn)扣除了 A 的錢妇多，但沒增加 B 的錢的情況。

一致性（Consistency）：

在事務(wù)開始之前和事務(wù)結(jié)束以后燕侠，數(shù)據(jù)庫的完整性和狀態(tài)沒有被破壞者祖。這個怎么理解呢？就是 A绢彤、B 兩人在轉(zhuǎn)賬錢的總和是 2,000七问，轉(zhuǎn)賬后兩人的總和也必須是 2,000。不會因為這次轉(zhuǎn)賬事務(wù)破壞這個狀態(tài)茫舶。

隔離性（Isolation）：

多個事務(wù)在并發(fā)執(zhí)行時械巡，事務(wù)執(zhí)行的中間狀態(tài)是其他事務(wù)不可訪問的。A 轉(zhuǎn)出 100 但事務(wù)沒有確認(rèn)提交饶氏，這時候銀行人員對其賬號查詢時讥耗，看到的應(yīng)該還是 1,000，不是 900疹启。

持久性（Durability）

事務(wù)一旦提交生效古程，其結(jié)果將永久保存，不受任何故障影響喊崖。A 轉(zhuǎn)賬一但完成籍琳，那么 A 就是 900，B 就是 1,100贷祈，這個結(jié)果將永遠(yuǎn)保存在銀行的數(shù)據(jù)庫中趋急，直到他們下次交易事務(wù)的發(fā)生。

WT 如何實現(xiàn)事務(wù)

知道了基本的事務(wù)概念和 ACID 后势誊，來看看 WT 引擎是怎么來實現(xiàn)事務(wù)和 ACID呜达。要了解實現(xiàn)先要知道它的事務(wù)的構(gòu)造和使用相關(guān)的技術(shù)，WT 在實現(xiàn)事務(wù)的時使用主要是使用了三個技術(shù)：

snapshot（事務(wù)快照）

MVCC（多版本并發(fā)控制）

redo log（重做日志）

為了實現(xiàn)這三個技術(shù)粟耻，它還定義了一個基于這三個技術(shù)的事務(wù)對象和全局事務(wù)管理器查近。事務(wù)對象描述如下

wt_transaction{

transaction_id: ? ?本次事務(wù)的全局唯一的ID眉踱，用于標(biāo)示事務(wù)修改數(shù)據(jù)的版本號

snapshot_object: ? 當(dāng)前事務(wù)開始或者操作時刻其他正在執(zhí)行且并未提交的事務(wù)集合,用于事務(wù)隔離

operation_array: ? 本次事務(wù)中已執(zhí)行的操作列表,用于事務(wù)回滾。

redo_log_buf: ? ? ?操作日志緩沖區(qū)霜威。用于事務(wù)提交后的持久化

State: ? ? ? ? ? ? 事務(wù)當(dāng)前狀態(tài)

}

WT 的多版本并發(fā)控制

WT 中的 MVCC?是基于 key/value 中 value 值的鏈表谈喳，這個鏈表單元中存儲有當(dāng)先版本操作的事務(wù) ID 和操作修改后的值。描述如下：

wt_mvcc{

transaction_id: ? ?本次修改事務(wù)的ID

value: ? ? ? ? ? ? 本次修改后的值

}

WT 中的數(shù)據(jù)修改都是在這個鏈表中進(jìn)行 append 操作戈泼，每次對值做修改都是 append 到鏈表頭上婿禽，每次讀取值的時候讀是從鏈表頭根據(jù)值對應(yīng)的修改事務(wù) transaction_id 和本次讀事務(wù)的 snapshot 來判斷是否可讀，如果不可讀大猛，向鏈表尾方向移動扭倾，直到找到讀事務(wù)能都的數(shù)據(jù)版本。樣例如下：

圖1挽绩，點擊圖片可以全屏縮放

上圖中膛壹，事務(wù) T0 發(fā)生的時刻最早，T5 發(fā)生的時刻最晚唉堪。T1/T2/T4 是對記錄做了修改模聋。那么在 MVCC list 當(dāng)中就會增加 3 個版本的數(shù)據(jù)，分別是 11/12/14唠亚。如果事務(wù)都是基于 snapshot 級別的隔離链方，T0 只能看到 T0 之前提交的值 10，讀事務(wù) T3 訪問記錄時它能看到的值是 11趾撵，T5 讀事務(wù)在訪問記錄時，由于 T4 未提交共啃，它也只能看到 11 這個版本的值占调。這就是 WT 的 MVCC 基本原理。

WT 事務(wù) snapshot

上面多次提及事務(wù)的 snapshot移剪，那到底什么是事務(wù)的 snapshot 呢究珊？其實就是事務(wù)開始或者進(jìn)行操作之前對整個 WT 引擎內(nèi)部正在執(zhí)行或者將要執(zhí)行的事務(wù)進(jìn)行一次快照，保存當(dāng)時整個引擎所有事務(wù)的狀態(tài)纵苛，確定哪些事務(wù)是對自己見的桩匪，哪些事務(wù)都自己是不可見砾嫉。說白了就是一些列事務(wù) ID 區(qū)間。WT 引擎整個事務(wù)并發(fā)區(qū)間示意圖如下：

圖2，點擊圖片可以全屏縮放

WT 引擎中的 snapshot_oject 是有一個最小執(zhí)行事務(wù) snap_min胸梆、一個最大事務(wù) snap max 和一個處于 [snap_min, snap_max] 區(qū)間之中所有正在執(zhí)行的寫事務(wù)序列組成。如果上圖在 T6 時刻對系統(tǒng)中的事務(wù)做一次 snapshot护赊，那么產(chǎn)生的

snapshot_object = {

snap_min=T1,

snap_max=T5,

snap_array={T1, T4, T5},

};

T6 能訪問的事務(wù)修改有兩個區(qū)間：所有小于 T1 事務(wù)的修改 [0, T1) 和[snap_min, snap_max]區(qū)間已經(jīng)提交的事務(wù) T2 的修改给赞。換句話說，凡是出現(xiàn)在 snap_array 中或者事務(wù) ID 大于 snap_max 的事務(wù)的修改對事務(wù) T6 是不可見的蓬坡。如果 T1 在建立 snapshot 之后提交了猿棉，T6 也是不能訪問到 T1 的修改磅叛。這個就是 snapshot 方式隔離的基本原理。

全局事務(wù)管理器

通過上面的 snapshot 的描述萨赁，我們可以知道要創(chuàng)建整個系統(tǒng)事務(wù)的快照截屏弊琴，就需要一個全局的事務(wù)管理來進(jìn)行事務(wù)快照時的參考，在 WT 引擎中是如何定義這個全局事務(wù)管理器的呢杖爽？在 CPU 多核多線程下敲董，它是如何來管理事務(wù)并發(fā)的呢？下面先來分析它的定義：

wt_txn_global{

current_id: ? ? ? 全局寫事務(wù)ID產(chǎn)生種子掂林，一直遞增

oldest_id: ? ? ? ?系統(tǒng)中最早產(chǎn)生且還在執(zhí)行的寫事務(wù)ID

transaction_array: 系統(tǒng)事務(wù)對象數(shù)組臣缀，保存系統(tǒng)中所有的事務(wù)對象

scan_count: ?正在掃描transaction_array數(shù)組的線程事務(wù)數(shù)，用于建立snapshot過程的無鎖并發(fā)

}

transaction_array 保存的是圖 2 正在執(zhí)行事務(wù)的區(qū)間的事務(wù)對象序列泻帮。在建立 snapshot 時精置，會對整個 transaction_array 做掃描，確定 snap_min/snap_max/snap_array 這三個參數(shù)和更新 oldest_id锣杂，在掃描的過程中脂倦，凡是 transaction_id 不等于 WT_TNX_NONE 都認(rèn)為是在執(zhí)行中且有修改操作的事務(wù)，直接加入到 snap_array 當(dāng)中赖阻。整個過程是一個無鎖操作過程,這個過程如下：

圖3踱蠢，點擊圖片可以全屏縮放

創(chuàng)建 snapshot 快照的過程在 WT 引擎內(nèi)部是非常頻繁，尤其是在大量自動提交型的短事務(wù)執(zhí)行的情況下苇侵，由創(chuàng)建 snapshot 動作引起的 CPU 競爭是非常大的開銷企锌，所以這里 WT 并沒有使用 spin lock，而是采用了上圖的一個無鎖并發(fā)設(shè)計撕攒，這種設(shè)計遵循了我們開始說的并發(fā)設(shè)計原則。

事務(wù) ID

從 WT 引擎創(chuàng)建事務(wù) snapshot 的過程中萍鲸，現(xiàn)在可以確定擦俐，snapshot 的對象是有寫操作的事務(wù)，純讀事務(wù)是不會被 snapshot 的，因為 snapshot 的目的是隔離 MVCC list 中的記錄藕咏，通過 MVCC 中 value 的事務(wù) ID 與讀事務(wù)的 snapshot 進(jìn)行版本讀取秽五，與讀事務(wù)本身的 ID 是沒有關(guān)系孽查。

在 WT 引擎中坦喘，開啟事務(wù)時，引擎會將一個WT_TNX_NONE(= 0)的事務(wù) ID 設(shè)置給開啟的事務(wù)瓣铣，當(dāng)它第一次對事務(wù)進(jìn)行寫時，會在數(shù)據(jù)修改前通過全局事務(wù)管理器中的 current_id 來分配一個全局唯一的事務(wù) ID梦碗。這個過程也是通過 CPU 的 CAS_ADD 原子操作完成的無鎖過程。

WT 的事務(wù)過程

一般事務(wù)是兩個階段：事務(wù)執(zhí)行和事務(wù)提交洪规。在事務(wù)執(zhí)行前循捺，我們需要先創(chuàng)建事務(wù)對象并開啟它，然后才開始執(zhí)行念赶，如果執(zhí)行遇到?jīng)_突和或者執(zhí)行失敗，我們需要回滾事務(wù)（rollback）叉谜。如果執(zhí)行都正常完成牺勾，最后只需要提交（commit）它即可正罢。

從上面的描述可以知道事務(wù)過程有：創(chuàng)建開啟驻民、執(zhí)行履怯、提交和回滾叹洲。從這幾個過程中來分析 WT 是怎么實現(xiàn)這幾個過程的。

事務(wù)開啟

WT 事務(wù)開啟過程中，首先會為事務(wù)創(chuàng)建一個事務(wù)對象并把這個對象加入到全局事務(wù)管理器當(dāng)中闻葵，然后通過事務(wù)配置信息確定事務(wù)的隔離級別和 redo log 的刷盤方式并將事務(wù)狀態(tài)設(shè)為執(zhí)行狀態(tài)癣丧，最后判斷如果隔離級別是 ISOLATION_SNAPSHOT（snapshot 級的隔離），在本次事務(wù)執(zhí)行前創(chuàng)建一個系統(tǒng)并發(fā)事務(wù)的 snapshot厢钧。至于為什么要在事務(wù)執(zhí)行前創(chuàng)建一個 snapshot嬉橙，在后面 WT 事務(wù)隔離章節(jié)詳細(xì)介紹。

事務(wù)執(zhí)行

事務(wù)在執(zhí)行階段霞扬，如果是讀操作拾给，不做任何記錄祥得，因為讀操作不需要回滾和提交。如果是寫操作蒋得，WT 會對每個寫操作做詳細(xì)的記錄级及。在上面介紹的事務(wù)對象（wt_transaction）中有兩個成員额衙，一個是操作 operation_array饮焦，一個是 redo_log_buf县踢。這兩個成員是來記錄修改操作的詳細(xì)信息伟件，在 operation_array 的數(shù)組單元中，包含了一個指向 MVCC list 對應(yīng)修改版本值的指針谴返。詳細(xì)的更新操作流程如下：

創(chuàng)建一個 MVCC list 中的值單元對象（update）

根據(jù)事務(wù)對象的 transaction id 和事務(wù)狀態(tài)判斷是否為本次事務(wù)創(chuàng)建了寫的事務(wù) ID咧织，如果沒有，為本次事務(wù)分配一個事務(wù) ID习绢，并將事務(wù)狀態(tài)設(shè)成 HAS_TXN_ID 狀態(tài)。

將本次事務(wù)的 ID 設(shè)置到 update 單元中作為 MVCC 版本號奇颠。

創(chuàng)建一個 operation 對象放航，并將這個對象的值指針指向 update，并將這個 operation 加入到本次事務(wù)對象的 operation_array缺菌。

將 update 單元加入到 MVCC list 的鏈表頭上。

寫入一條 redo log 到本次事務(wù)對象的 redo_log_buf 當(dāng)中搜锰。

示意圖如下：

圖4蛋叼，點擊圖片可以全屏縮放

事務(wù)提交

WT 引擎對事務(wù)的提交過程比較簡單狈涮，先將要提交的事務(wù)對象中的 redo_log_buf 中的數(shù)據(jù)寫入到 redo log file（重做日志文件）中，并將 redo log file 持久化到磁盤上歌馍。清除提交事務(wù)對象的 snapshot object，再將提交的事務(wù)對象中的 transaction_id 設(shè)置為 WT_TNX_NONE暴浦，保證其他事務(wù)在創(chuàng)建系統(tǒng)事務(wù) snapshot 時本次事務(wù)的狀態(tài)是已提交的狀態(tài)晓锻。

事務(wù)回滾

WT 引擎對事務(wù)的回滾過程也比較簡單，先遍歷整個operation_array砚哆，對每個數(shù)組單元對應(yīng) update 的事務(wù) id 設(shè)置以為一個WT_TXN_ABORTED(= uint64_max)，標(biāo)示 MVCC 對應(yīng)的修改單元值被回滾纷铣，在其他讀事務(wù)進(jìn)行 MVCC 讀操作的時候关炼，跳過這個放棄的值即可匣吊。整個過程是一個無鎖操作色鸳，高效社痛、簡潔命雀。

WT 的事務(wù)隔離

傳統(tǒng)的數(shù)據(jù)庫事務(wù)隔離分為：

Read-Uncommited（未提交讀）

Read-Commited（提交讀）

Repeatable-Read（可重復(fù)讀）

Serializable（串行化）

WT 引擎并沒有按照傳統(tǒng)的事務(wù)隔離實現(xiàn)這四個等級，而是基于 snapshot 的特點實現(xiàn)了自己的 Read-Uncommited撵儿、Read-Commited 和一種叫做 snapshot-Isolation（快照隔離）的事務(wù)隔離方式淀歇。

在 WT 中不管是選用的是那種事務(wù)隔離方式浪默，它都是基于系統(tǒng)中執(zhí)行事務(wù)的快照來實現(xiàn)的缀匕。那來看看 WT 是怎么實現(xiàn)上面三種方式乡小？

圖5满钟，點擊圖片可以全屏縮放

Read-uncommited

Read-Uncommited（未提交讀）隔離方式的事務(wù)在讀取數(shù)據(jù)時總是讀取到系統(tǒng)中最新的修改零远，哪怕是這個修改事務(wù)還沒有提交一樣讀取牵辣，這其實就是一種臟讀。WT 引擎在實現(xiàn)這個隔方式時纬向，就是將事務(wù)對象中的 snap_object.snap_array 置為空即可，在讀取 MVCC list 中的版本值時琢岩，總是讀取到 MVCC list 鏈表頭上的第一個版本數(shù)據(jù)师脂。

舉例說明担孔，在圖 5 中糕篇，如果 T0/T3/T5 的事務(wù)隔離級別設(shè)置成 Read-uncommited 的話，T1/T3/T5 在 T5 時刻之后讀取系統(tǒng)的值時拌消，讀取到的都是 14挑豌。一般數(shù)據(jù)庫不會設(shè)置成這種隔離方式，它違反了事務(wù)的 ACID 特性墩崩∶ビⅲ可能在一些注重性能且對臟讀不敏感的場景會采用，例如網(wǎng)頁 cache鹦筹。

Read-Commited

Read-Commited（提交讀）隔離方式的事務(wù)在讀取數(shù)據(jù)時總是讀取到系統(tǒng)中最新提交的數(shù)據(jù)修改债蓝，這個修改事務(wù)一定是提交狀態(tài)。這種隔離級別可能在一個長事務(wù)多次讀取一個值的時候前后讀到的值可能不一樣盛龄，這就是經(jīng)常提到的“幻象讀”饰迹。在 WT 引擎實現(xiàn) read-commited 隔離方式就是事務(wù)在執(zhí)行每個操作前都對系統(tǒng)中的事務(wù)做一次快照，然后在這個快照上做讀寫余舶。

還是來看圖 5啊鸭，T5 事務(wù)在 T4 事務(wù)提交之前它進(jìn)行讀取前做事務(wù)

snapshot={

snap_min=T2,

snap_max=T4,

snap_array={T2,T4},

};

在讀取 MVCC list 時，12 和 14 修改對應(yīng)的事務(wù) T2/T4 都出現(xiàn)在 snap_array 中匿值，只能再向前讀取 11赠制，11 是 T1 的修改，而且 T1 沒有出現(xiàn)在 snap_array挟憔，說明 T1 已經(jīng)提交钟些，那么就返回 11 這個值給 T5。

之后事務(wù) T2 提交绊谭，T5 在它提交之后再次讀取這個值政恍，會再做一次

snapshot={

snap_min=T4,

snap_max=T4,

snap_array={T4},

}，

這時在讀取 MVCC list 中的版本時达传，就會讀取到最新的提交修改 12篙耗。

Snapshot-Isolation

Snapshot-Isolation（快照隔離）隔離方式是讀事務(wù)開始時看到的最后提交的值版本修改，這個值在整個讀事務(wù)執(zhí)行過程只會看到這個版本宪赶，不管這個值在這個讀事務(wù)執(zhí)行過程被其他事務(wù)修改了幾次宗弯，這種隔離方式不會出現(xiàn)“幻象讀”。WT 在實現(xiàn)這個隔離方式很簡單搂妻，在事務(wù)開始時對系統(tǒng)中正在執(zhí)行的事務(wù)做一個 snapshot蒙保，這個 snapshot 一直沿用到事務(wù)提交或者回滾。還是來看圖 5欲主， T5 事務(wù)在開始時邓厕，對系統(tǒng)中的執(zhí)行的寫事務(wù)做

snapshot={

snap_min=T2,

snap_max=T4,

snap_array={T2,T4}

}逝嚎，

在他讀取值時讀取到的是 11。即使是 T2 完成了提交邑狸，但 T5 的 snapshot 執(zhí)行過程不會更新，T5 讀取到的依然是 11涤妒。

這種隔離方式的寫比較特殊单雾，就是如果有對事務(wù)看不見的數(shù)據(jù)修改，事務(wù)嘗試修改這個數(shù)據(jù)時會失敗回滾她紫，這樣做的目的是防止忽略不可見的數(shù)據(jù)修改硅堆。

通過上面對三種事務(wù)隔離方式的分析，WT 并沒有使用傳統(tǒng)的事務(wù)獨占鎖和共享訪問鎖來保證事務(wù)隔離贿讹，而是通過對系統(tǒng)中寫事務(wù)的 snapshot 來實現(xiàn)渐逃。這樣做的目的是在保證事務(wù)隔離的情況下又能提高系統(tǒng)事務(wù)并發(fā)的能力。

內(nèi)存設(shè)計如何保證 Durability：事務(wù)日志

通過上面的分析可以知道 WT 在事務(wù)的修改都是在內(nèi)存中完成的民褂，事務(wù)提交時也不會將修改的 MVCC list 當(dāng)中的數(shù)據(jù)刷入磁盤茄菊，WT 是怎么保證事務(wù)提交的結(jié)果永久保存呢？

WT 引擎在保證事務(wù)的持久可靠問題上是通過 redo log（重做操作日志）的方式來實現(xiàn)的赊堪，在本文的事務(wù)執(zhí)行和事務(wù)提交階段都有提到寫操作日志面殖。WT 的操作日志是一種基于 K/V 操作的邏輯日志，它的日志不是基于 btree page 的物理日志哭廉。說的通俗點就是將修改數(shù)據(jù)的動作記錄下來脊僚，例如：插入一個key = 10, value = 20的動作記錄在成：

{

Operation = insert,(動作)

Key = 10,

Value = 20

};

將動作記錄的數(shù)據(jù)以 append 追加的方式寫入到 wt_transaction 對象中 redo_log_buf 中，等到事務(wù)提交時將這個 redo_log_buf 中的數(shù)據(jù)已同步寫入的方式寫入到 WT 的重做日志的磁盤文件中遵绰。如果數(shù)據(jù)庫程序發(fā)生異沉苫希或者崩潰，可以通過上一個 checkpoint（檢查點）位置重演磁盤上這個磁盤文件來恢復(fù)已經(jīng)提交的事務(wù)來保證事務(wù)的持久性椿访。

如何通過操作日志實現(xiàn)?Durability乌企？

根據(jù)上面的描述，有幾個問題需要搞清楚：

1成玫、操作日志格式怎么設(shè)計?

2逛犹、在事務(wù)并發(fā)提交時，各個事務(wù)的日志是怎么寫入磁盤的梁剔？

3虽画、日志是怎么重演的？它和 checkpoint 的關(guān)系是怎樣的荣病？

在分析這三個問題前先來看 WT 是怎么管理重做日志文件的码撰，在 WT 引擎中定義一個叫做 LSN 序號結(jié)構(gòu)，操作日志對象是通過 LSN 來確定存儲的位置的个盆，LSN 就是 Log Sequence Number（日志序列號）脖岛，它在 WT 的定義是文件序號加文件偏移朵栖，

wt_lsn{

file: ? ? ?文件序號，指定是在哪個日志文件中

offset: ? ?文件內(nèi)偏移位置柴梆，指定日志對象文件內(nèi)的存儲文開始位置

}

WT 就是通過這個 LSN 來管理重做日志文件的陨溅。

日志格式設(shè)計

WT 引擎的操作日志對象（以下簡稱為 logrec）對應(yīng)的是提交的事務(wù)，事務(wù)的每個操作被記錄成一個 logop 對象绍在，一個 logrec 包含多個 logop门扇，logrec 是一個通過精密序列化事務(wù)操作動作和參數(shù)得到的一個二進(jìn)制 buffer，這個 buffer的數(shù)據(jù)是通過事務(wù)和操作類型來確定其格式的偿渡。

WT 中的日志分為 4 類臼寄，分別是：

建立 checkpoint 的操作日志（LOGREC_CHECKPOINT）

普通事務(wù)操作日志（LOGREC_COMMIT）

btree page 同步刷盤的操作日志（LOGREC_FILE_SYNC）

提供給引擎外部使用的日志（LOGREC_MESSAGE）

這里介紹和執(zhí)行事務(wù)密切先關(guān)的 LOGREC_COMMIT，這類日志里面由根據(jù) K/V 的操作方式分為：

LOG_PUT（增加或者修改K/V操作）

LOG_REMOVE（單 KEY 刪除操作）

范圍刪除日志

這幾種操作都會記錄操作時的 key溜宽，根據(jù)操作方式填寫不同的其他參數(shù)吉拳，例如：update 更新操作，就需要將 value 填上适揉。除此之外留攒，日志對象還會攜帶 btree 的索引文件 ID、提交事務(wù)的 ID 等嫉嘀，整個 logrec 和 logop 的關(guān)系結(jié)構(gòu)圖如下：

圖6稼跳，點擊圖片可以全屏縮放

對于上圖中的 logrec essay-header 中的為什么會出現(xiàn)兩個長度字段：logrec 磁盤上的空間長度和在內(nèi)存中的長度，因為 logrec 在刷入磁盤之前會進(jìn)行空間壓縮吃沪，磁盤上的長度和內(nèi)存中的長度就不一樣汤善。壓縮是根據(jù)系統(tǒng)配置可選的。

WAL 與無鎖設(shè)計的日志寫并發(fā)

WT 引擎在采用 WAL（Write-Ahead Log）方式寫入日志票彪，WAL 通俗點說就是說在事務(wù)所有修改提交前需要將其對應(yīng)的操作日志寫入磁盤文件红淡。在事務(wù)執(zhí)行的介紹小節(jié)中我們介紹是在什么時候?qū)懭罩镜模@里我們來分析事務(wù)日志是怎么寫入到磁盤上的降铸，整個寫入過程大致分為下面幾個階段：

1在旱、事務(wù)在執(zhí)行第一個寫操作時，先會在事務(wù)對象（wt_transaction）中的 redo_log_buf 的緩沖區(qū)上創(chuàng)建一個 logrec 對象推掸，并將 logrec 中的事務(wù)類型設(shè)置成 LOGREC_COMMIT桶蝎。

2、然后在事務(wù)執(zhí)行的每個寫操作前生成一個 logop 對象谅畅，并加入到事務(wù)對應(yīng)的 logrec 中登渣。

3、在事務(wù)提交時毡泻，把 logrec 對應(yīng)的內(nèi)容整體寫入到一個全局 log 對象的 slot buffer 中并等待寫完成信號胜茧。

4、Slot buffer 會根據(jù)并發(fā)情況合并同時發(fā)生的提交事務(wù)的 logrec，然后將合并的日志內(nèi)容同步刷入磁盤（sync file）呻顽，最后告訴這個 slot buffer 對應(yīng)所有的事務(wù)提交刷盤完成雹顺。

5、提交事務(wù)的日志完成廊遍，事務(wù)的執(zhí)行結(jié)果也完成了持久化嬉愧。

整個過程的示意圖如下：

圖7，點擊圖片可以全屏縮放

WT 為了減少日志刷盤造成寫 IO喉前，對日志刷盤操作做了大量的優(yōu)化没酣，實現(xiàn)一種類似 MySQL 組提交的刷盤方式。

這種刷盤方式會將同時發(fā)生提交的事務(wù)日志合并到一個 slot buffer 中被饿，先完成合并的事務(wù)線程會同步等待一個完成刷盤信號四康，最后完成日志數(shù)據(jù)合并的事務(wù)線程將 slot buffer 中的所有日志數(shù)據(jù) sync 到磁盤上并通知在這個 slot buffer 中等待其他事務(wù)線程刷盤完成搪搏。

并發(fā)事務(wù)的 logrec 合并到 slot buffer 中的過程是一個完全無鎖的過程狭握，這減少了必要的 CPU 競爭和操作系統(tǒng)上下文切換。為了這個無鎖設(shè)計 WT 在全局的 log 管理中定義了一個 acitve_ready_slot 和一個 slot_pool 數(shù)組結(jié)構(gòu)疯溺，大致如下定義：

wt_log{

. . .

active_slot:準(zhǔn)備就緒且可以作為合并logrec的slot buffer對象

slot_pool:系統(tǒng)所有slot buffer對象數(shù)組论颅，包括：正在合并的、準(zhǔn)備合并和閑置的slot buffer囱嫩。

}

slot buffer 對象是一個動態(tài)二進(jìn)制數(shù)組恃疯，可以根據(jù)需要進(jìn)行擴(kuò)大。定義如下:

wt_log_slot{

. . .

state: ? ? ? ? ?當(dāng)前 slot 的狀態(tài)墨闲，ready/done/written/free 這幾個狀態(tài)

buf: 緩存合并 logrec 的臨時緩沖區(qū)

group_size: 需要提交的數(shù)據(jù)長度

slot_start_offset: 合并的logrec存入log file中的偏移位置

. . .

}

通過一個例子來說明這個無鎖過程今妄，假如在系統(tǒng)中 slot_pool 中的 slot 個數(shù)為16，設(shè)置的 slot buffer 大小為 4KB鸳碧，當(dāng)前 log 管理器中的 active_slot 的slot_start_offset=0盾鳞，有 4 個事務(wù)（T1、T2瞻离、T3腾仅、T4）同時發(fā)生提交，他們對應(yīng)的日志對象分別是 logrec1套利、logrec2推励、logrec3 和 logrec4。

Logrec1 size = 1KB, ?logrec2 szie = 2KB, logrec3 size = 2KB, logrec4 size = 5KB肉迫。他們合并和寫入的過程如下：

1验辞、T1事 務(wù)在提交時，先會從全局的 log 對象中的 active_slot 發(fā)起一次 JOIN 操作喊衫，join 過程就是向 active_slot 申請自己的合并位置和空間受神，logrec1_size + slot_start_offset < slot_size并且 slot 處于 ready 狀態(tài)，那 T1 事務(wù)的合并位置就是active_slot[0, 1KB],slot_group_size = 1KB

2格侯、這是 T2 同時發(fā)生提交也要合并 logrec鼻听，也重復(fù)第 1 部 JOIN 操作财著，它申請到的位置就是active_slot [1KB, 3KB], slot_group_size = 3KB。

3撑碴、在T1事務(wù) JOIN 完成后撑教，它會判斷自己是第一個 JOIN 這個 active_slot 的事務(wù)，判斷條件就是返回的寫入位置slot_offset=0醉拓。如果是第一個它立即會將 active_slot 的狀態(tài)從 ready 狀態(tài)置為 done 狀態(tài)伟姐，并未后續(xù)的事務(wù)從 slot_pool 中獲取一個空閑的 active_slot_new 來頂替自己合并數(shù)據(jù)的工作。

4亿卤、與此同時 T2 事務(wù) JOIN 完成之后愤兵，它也是進(jìn)行這個過程的判斷，T2 發(fā)現(xiàn)自己不是第一個排吴，它將會等待 T1 將 active_slot 置為 done.

5秆乳、T1 和 T2 都獲取到了自己在 active_slot 中的寫入位置，active_slot 的狀態(tài)置為 done 時钻哩，T1 和 T2 分別將自己的 logrec 寫入到對應(yīng) buffer 位置屹堰。假如在這里 T1 比 T2 先將數(shù)據(jù)寫入完成，T1 就會等待一個 slot_buffer 完全刷入磁盤的信號街氢，而 T2 寫入完成后會將 slot_buffer 中的數(shù)據(jù)寫入 log 文件扯键，并對 log 文件做 sync 刷入磁盤的操作，最高發(fā)送信號告訴 T1 同步刷盤完成珊肃，T1 和 T2 各自返回荣刑，事務(wù)提交過程的日志刷盤操作完成。

那這里有幾種其他的情況伦乔，假如在第 2 步運行的完成后厉亏，T3 也進(jìn)行 JOIN 操作，這個時候slot_size(4KB) < slot_group_size（3KB）+ logrec_size(2KB)评矩，T3 不 JOIN 當(dāng)時的 active_slot叶堆，而是自旋等待 active_slot_new 頂替 active_slot 后再 JOIN 到 active_slot_new。

如果在第 2 步時斥杜，T4 也提交虱颗，因為logrec4(5KB) > slot_size(4KB)，T4 就不會進(jìn)行 JOIN 操作蔗喂，而是直接將自己的 logrec 數(shù)據(jù)寫入 log 文件忘渔，并做 sync 刷盤返回。在返回前因為發(fā)現(xiàn)有 logrec4 大小的日志數(shù)據(jù)無法合并缰儿，全局 log 對象會試圖將 slot buffer 的大小放大兩倍畦粮，這樣做的目的是盡量讓下面的事務(wù)提交日志能進(jìn)行 slot 合并寫。

WT 引擎之所以引入 slot 日志合并寫的原因就是為了減少磁盤的 I/O 訪問，通過無鎖的操作宣赔，減少全局日志緩沖區(qū)的競爭预麸。

事務(wù)恢復(fù)

從上面關(guān)于事務(wù)日志和 MVCC list 相關(guān)描述我們知道，事務(wù)的 redo log 主要是防止內(nèi)存中已經(jīng)提交的事務(wù)修改丟失儒将，但如果所有的修改都存在內(nèi)存中吏祸，隨著時間和寫入的數(shù)據(jù)越來越多，內(nèi)存就會不夠用钩蚊，這個時候就需要將內(nèi)存中的修改數(shù)據(jù)寫入到磁盤上贡翘。

一般在 WT 中是將整個 BTREE 上的 page 做一次 checkpoint 并寫入磁盤。WT 中的 checkpoint 是 append 方式管理砰逻，也就是說 WT 會保存多個 checkpoint 版本鸣驱。不管從哪個版本的 checkpoint 開始都可以通過重演 redo log 來恢復(fù)內(nèi)存中已提交的事務(wù)修改。整個重演過程就是就是簡單的對 logrec 中各個操作的執(zhí)行蝠咆。

這里值得提一下的是因為 WT 保存多個版本的 checkpoint踊东，那么它會將 checkpoint 做為一種元數(shù)據(jù)寫入到元數(shù)據(jù)表中，元數(shù)據(jù)表也會有自己的 checkpoint 和 redo log勺美，但是保存元數(shù)據(jù)表的 checkpoint 是保存在 WiredTiger.wt 文件中递胧，系統(tǒng)重演普通表的提交事務(wù)之前碑韵，先會重演元數(shù)據(jù)事務(wù)提交修改赡茸。后文會單獨用一個篇幅來說明 btree、checkpoint 和元數(shù)據(jù)表的關(guān)系和實現(xiàn)祝闻。

WT 的 redo log 是通過配置開啟或者關(guān)閉的占卧，MongoDB 并沒有使用 WT 的 redo log 來保證事務(wù)修改不丟，而是采用了 WT 的 checkpoint 和 MongoDB 復(fù)制集的功能結(jié)合來保證數(shù)據(jù)的完整性联喘。

大致的細(xì)節(jié)是如果某個 MongoDB 實例宕機(jī)了华蜒，重啟后通過 MongoDB 的復(fù)制協(xié)議將自己最新 checkpoint 后面的修改從其他的 MongoDB 實例復(fù)制過來。

后記

雖然 WT 實現(xiàn)了多操作事務(wù)模型豁遭，然而 MongoDB 并沒有提供事務(wù)叭喜，這或許和 MongoDB 本身的架構(gòu)和產(chǎn)品定位有關(guān)系。但是MongoDB 利用了 WT 的短事務(wù)的隔離性實現(xiàn)了文檔級行鎖蓖谢，對 MongoDB 來說這是大大的進(jìn)步捂蕴。

可以說 WT 在事務(wù)的實現(xiàn)上另辟蹊徑，整個事務(wù)系統(tǒng)的實現(xiàn)沒有用繁雜的事務(wù)鎖闪幽，而是使用 snapshot 和 MVCC 這兩個技術(shù)輕松的而實現(xiàn)了事務(wù)的 ACID啥辨，這種實現(xiàn)也大大提高了事務(wù)執(zhí)行的并發(fā)性。

除此之外盯腌，WT在各個事務(wù)模塊的實現(xiàn)多采用無鎖并發(fā)溉知，充分利用 CPU 的多核能力來減少資源競爭和 I/O 操作，可以說 WT 在實現(xiàn)上是有很大創(chuàng)新的。通過對 WiredTiger 的源碼分析和測試级乍，也讓我獲益良多舌劳，不僅僅了解了數(shù)據(jù)庫存儲引擎的最新技術(shù)，也對 CPU 和內(nèi)存相關(guān)的并發(fā)編程有了新的理解玫荣，很多的設(shè)計模式和并發(fā)程序架構(gòu)可以直接借鑒到現(xiàn)實中的項目和產(chǎn)品中蒿囤。

后續(xù)的工作是繼續(xù)對 Wiredtiger 做更深入的分析、研究和測試崇决，并把這些工作的心得體會分享出來材诽，讓更多的工程師和開發(fā)者了解這個優(yōu)秀的存儲引擎。（小編：請留意高可用架構(gòu)后續(xù) WiredTiger 文章）

轉(zhuǎn)自：http://h2ex.com/1120