李 凱， 韓富晟

(阿里巴巴集團，北京 100020)

?

OceanBase內存事務引擎

李 凱， 韓富晟

(阿里巴巴集團，北京 100020)

OceanBase是一個分布式可擴展的關系數據庫，采用基線靜態(tài)數據與動態(tài)增量數據分離存儲的架構設計.其內存事務引擎提供了動態(tài)數據的存儲、寫入和查詢服務，用戶寫入的數據被存儲在內存中稱為Memtable的數據結構中.Memtable及其周邊的事務管理結構共同組成了內存數據庫引擎，來實現事務的ACID特性.在事務引擎中，通過多版本的并發(fā)控制技術實現讀寫相互不阻塞，實現只讀事務滿足“快照隔離”級別；通過經典的行鎖方式實現多個寫之間的并發(fā)控制，實現最高滿足“已提交讀”的事務隔離級別.

關系數據庫； 分布式系統(tǒng)； 事務； 互聯網

0 引 言

在互聯網高速發(fā)展的今天，互聯網公司不僅有大量非結構化的數據，例如網站訪問日志等；也有很多結構化的數據，例如Google的搜索廣告、淘寶/天貓的商品搜索廣告的計費.淘寶/天貓、Amazon和eBay等的網上和移動購物，支付寶的網上和移動支付，等等，都是商務交易和金融交易.對這些數據的處理依賴于嚴格的數據庫事務語義，即原子性(Atomicy)、一致性(Consistency)、隔離性(Isolation)和持久性(Durability)的保證.同時也對數據庫的存儲容量和事務處理能力提出了越來越高的要求.

使用商業(yè)數據庫、配置高端服務器和存儲設備，在一段時間內確實能夠解決互聯網公司對數據庫的需求，但是隨著業(yè)務的發(fā)展，對存儲容量和事務處理能力的需求越來越高，購買商業(yè)解決方案的成本變得難以接受，并且也同樣遇到軟硬件處理能力的瓶頸.一些公司開始轉向使用開源數據庫軟件如MySQL，搭配廉價服務器，使用分庫分表的方式對業(yè)務數據進行拆分存儲，而拆分后的數據庫擴展困難，運維成本高，不支持跨域分庫分表的事務，且基于傳統(tǒng)數據設計的MySQL并不能充分發(fā)揮當前大容量內存加SSD的主流服務器配置優(yōu)勢.一些新興的內存數據庫如MemSQL，能夠充分利用大容量內存的優(yōu)勢，但是由于數據必須全部存放在內存中，而數據容量有限成本偏高，基于單機數據的設計，使得擴展能力也有限.Google的MegaStore基于BigTable/GFS開發(fā)，有良好的可擴展性和較低的成本，但是對數據庫事務支持有限，無法應用在對事務要求嚴格的電子商務領域.阿里巴巴集團自主研發(fā)的數據庫OceanBase，適應電子商務領域對數據庫事務的嚴格要求，充分發(fā)揮大容量內存和SSD發(fā)展的優(yōu)勢，以較低的成本提供海量存儲和高性能事務，良好的可擴展性和容錯能力很大程度上降低了運維成本.

OceanBase是一個分布式的關系數據庫，采用基線數據與動態(tài)數據分離存儲的架構設計，其中基線數據被劃分為多個有序的分塊，稱為Tablet，每個Tablet存儲若干個副本隨機地分布在機群的多臺機器上；動態(tài)數據就是一段時間內的數據更新記錄，每次查詢需要將基線數據與動態(tài)數據合并后產生最終結果返回給客戶端.整個機群主要由4個模塊組成：Chunkserver提供基線數據的存儲和查詢服務，定期將本地保存的基線數據與動態(tài)數據合并，生成新版本的基線數據；Updateserver提供動態(tài)數據的存儲、查詢和寫入服務，每隔一段時間將當前動態(tài)數據“凍結”，并分配一個“凍結版本號”，用于Chunkserver合并新版本的基線數據；Rootserver提供Tablet在多臺Chunkserver上位置信息的存儲和查詢服務，負載平衡、遷移、復制等的調度管理，以及Schema信息的管理；Mergeserver實現SQL接口，處理客戶端的查詢和寫入請求，將SQL請求轉化為Updateserver和Chunkserver認識的執(zhí)行計劃，同時負責從多臺機器接收查詢結果后的合并和處理.

如上所述，Updateserver提供了動態(tài)數據的存儲、寫入和查詢服務，任何數據寫入都將最終被發(fā)送到Updateserver執(zhí)行，并存儲在內存中稱為Memtable的數據結構，上面提到的凍結則意味著當前Memtable停止數據寫入，構造新的Memtable來接收后續(xù)寫入的數據.Memtable及其周邊的事務管理結構共同組成了Updateserver的內存事務引擎，實現滿足ACID特性的數據庫事務.

內存事務引擎提供交互式事務接口，使用多版本的并發(fā)控制技術實現讀寫相互不阻塞，提供快照讀事務；經典的兩階段行鎖方式實現寫的并發(fā)控制[1].使用logging ahead方法的記錄redolog來持久化事務[2]，并且通過同步實時的備機來保證服務的持續(xù)可用.通過批處理、預解鎖、并發(fā)提交等技術，來優(yōu)化事務提交性能.本文第1節(jié)概述內存事務引擎，第2節(jié)介紹并發(fā)事務設計，第3節(jié)介紹事務引擎的持久化與恢復，第4節(jié)介紹性能優(yōu)化技術，最后對整個OceanBase內存事務引擎做出總結，展望未來的發(fā)展方向.

1 內存事務引擎概述

1.1 總體架構

如圖1所示，內存事務引擎主要由TableMgr、SessionMgr、LockMgr和TransExecutor組成，其中TableMgr管理了多個版本的凍結Memtable和一個活躍Memtable.數據總是被寫入活躍Memtable，而達到凍結的觸發(fā)條件時，活躍Memtable被轉為凍結，然后構造新的活躍Memtable來接收數據寫入.SessionMgr為每個活躍事務維護一個描述符到事務上下文結構SessionCtx的映射.LockMgr為事務執(zhí)行過程中提供行鎖加鎖和解鎖實現，在每個讀寫事務的上下文中維護兩階段鎖.TransExecutor是事務完整流程的執(zhí)行器，在它維護的線程池中調用上述TableMgr、SessionMgr和LockMgr的接口執(zhí)行事務預處理和提交.

圖1 內存引擎結構

● 事務執(zhí)行流程

需要注意的是，本文所說的事務，既包括begin...commit這種形式的事務，同時也包括單條autocommit的語句.如圖2所示，事務在執(zhí)行分為3個階段，分別是預提交、提交和發(fā)布.在預提交階段，由多線程對并發(fā)的事務執(zhí)行預處理，包括加行鎖和進行邏輯判斷(如能否執(zhí)行insert/update/delete語句，以及上述語句中where條件的判斷和數據讀取)，然后將待更新數據寫入事務上下文的臨時空間.在確定事務要提交(收到commit或單條autocommit)的情況下，由多線程執(zhí)行提交操作：即申請事務版本號、提交對數據的修改和釋放行鎖.提交操作完成后，由單個線程執(zhí)行發(fā)布操作：即同步redolog和原子性地發(fā)布當前事務.發(fā)布階段完成后，事務對數據的修改才可以被后續(xù)開始的其他事務讀取到.

● Memtable內存結構

Memtable是內存事務引擎用于存儲數據和處理查詢的核心結構，數據以行為單位在Memtable中存儲，每行數據所使用的內存從Memtable內部的內存池分配，通過基于行主鍵的索引提供查詢功能，包括btree范圍索引和hash單行索引.其中Memtable與事務管理器(SessionMgr)配合實現多版本并發(fā)控制，而與鎖管理器(LockMgr)配合實現兩階段鎖并發(fā)控制，這2種并發(fā)控制將在后面的章節(jié)中詳細說明.

1.2 內存存儲格式

在經典的數據庫實現中，每行數據以稠密格式存儲在數據塊中，對行內容的修改將在數據塊上就地修改，同時保存undo信息用于處理事務回滾和一致性讀.而在OceanBase內存事務引擎中，為了更好地管理和使用內存，存儲的則是對數據修改的操作記錄，每次讀取時需要將內存事務引擎中的數據修改記錄應用到基線數據上[3].因此，每行數據以稀疏格式存儲，僅僅保存被修改的列的值(或修改操作如“+1”).

圖2 事務執(zhí)行流程

如圖3所示，每次事務對行數據的更新記錄都保存在一個變長的內存塊中，多次事務保存的內存塊按時間順序串成鏈表，讀取到這一行的時候，從最早的數據塊開始遍歷，將對同一列的更新記錄合并，然后應用到基線數據上并生成最終數據.隨著對同一行多次執(zhí)行更新，上述鏈表會變得越來越長，讀取時合并計算的代價也會越來越大，因此在鏈表超過配置的長度后，多個塊將被合并為一個塊(稱為RowCompaction)，減少讀取時遍歷鏈表合并的代價.

圖3 多次修改的合并

因為活躍表被“凍結”后，將會與基線數據進行合并，合并完成之后的讀寫操作將不再需要這個凍結表，其占用的內存也可以被整體釋放掉，因此Memtable采用了最為簡單的內存管理策略，活躍表在處理數據更新時申請的內存，只申請不釋放，而是在凍結表被釋放的時候一次性釋放掉.如上述執(zhí)行RowCompaction后，3個塊合并成1個塊，原先的3個塊不會立即被釋放，而是等待凍結后集中釋放.

由于采用了上述簡單的內存管理方式，在活躍表整個生存周期內，它管理的內存只申請不釋放.因此，為了節(jié)省內存的使用，在上述變長內存塊中，多列數據以壓縮格式存儲，每次讀取的時候需要將數據解壓縮后再進行處理.數據壓縮算法簡單但行之有效：對于整數類型(整數和時間類型)根據其數值大小分別存儲為1/2/4/8 byte，對于字符串類型如果長度小于8 byte則在內存塊中就地存儲，否則使用8 byte保存指向外部存儲空間的指針.

1.3 并發(fā)索引結構

內存引擎提供針對行主鍵的單行和范圍查詢，為了實現最優(yōu)的查詢性能，實現了B+tree和Hash的雙主鍵索引設計，范圍查詢通過B+tree來服務，單行的隨機查詢則通過hash來服務.由于我們使用了SessionMgr和LockMgr實現了事務的并發(fā)控制，使用Memtable管理內存，因此對于底層索引結構的需求則弱化為可支持并發(fā)讀寫的KeyValue結構.下面將對兩種索引結構進行逐一說明.

● B+tree

對于并發(fā)B+tree，可以使用精細控制的小粒度鎖來處理并發(fā)寫入，使用copy on write技術來實現讀寫互不阻塞[4].而與經典的B+tree實現不同，雖然數據都存儲在葉子節(jié)點，但是為了簡化并發(fā)處理的邏輯，不同于傳統(tǒng)的B+樹，因此并沒有將葉子節(jié)點串聯起來.如下圖所示，插入Key-Value到B+tree的過程為以下3個步驟：

圖4 B+tree結構

(1) 從根節(jié)點開始遍歷查詢KV要插入的位置，并在遍歷過程中對路徑上的節(jié)點加共享鎖；

(2) 將葉子節(jié)點的共享鎖升級為互斥鎖，拷貝當前葉子節(jié)點，將KV插入拷貝出的葉子節(jié)點，如果節(jié)點不分裂，則原子的修改其父節(jié)點中指向它的指針即可；

(3) 如果節(jié)點需要分裂，則將其父節(jié)點的共享鎖升級為互斥鎖，拷貝父節(jié)點，然后將分裂后的索引插入拷貝出的父節(jié)點，如果父節(jié)點還需要分裂則遞歸執(zhí)行此操作；

需要注意的是，由于共享鎖的獲取方向是自頂向下，而互斥鎖則是隨著分裂自底向上，為了避免出現死鎖，獲取共享鎖的方式為try_lock，在加鎖失敗的情況下，將路徑上已經加成功的鎖釋放掉，然后重新遍歷.

● Copy on write內存回收的處理

在修改B+tree節(jié)點的過程中，除了原子替換子節(jié)點指針外，對節(jié)點的修改都需要先拷貝一次，在拷貝出的副本上進行修改，而在這個過程中原節(jié)點可能還會被讀取到，因此，原節(jié)點不能立即刪除，而是需要暫時保存直到確認不會再被讀取時才刪除.

這需要引入多版本的概念，為每次對B+tree修改操作維護一個VersionNode對象，當前修改操作過程中拷貝的多個原節(jié)點指針都保存在這個VersionNode中；維護一個全局版本號V，每次修改操作開始前將V加1，并將加1后的值保存在VersionNode中，修改操作結束后將VersionNode保存在線程本地，等待后續(xù)的內存回收.每次讀寫操作開始前，將當前全局版本號保存在線程本地，讀取操作執(zhí)行完成后將線程本地保存的版本號置為無效.

當線程本地緩存的VersionNode關聯的內存過多時，則執(zhí)行內存回收邏輯，遍歷所有線程局部的有效版本號，取得最小值MinV.表示版本號小于MinV的VersionNode引用的B+tree節(jié)點都不會再被引用，可以回收[5].

遍歷的多線程問題，因為遍歷多個線程局部版本號的操作并非原子，可能出現遍歷得到的MinV大于實際MinV的情況(如線程拿到全局版本號后，到保存到線程本地的過程中，遍歷操作就執(zhí)行完了)，因此每次執(zhí)行讀寫操作，線程將全局版本號保存在本地前，先將全局版本號保存到臨時變量中，然后將這個臨時變量保存到線程本地之后，對其進行二次檢查，如果全局版本號已經變化，則重新執(zhí)行上述操作；對于回收邏輯，則需要在遍歷線程局部版本號之前，先單獨保存當前全局版本號到臨時變量中，取MinV與這個臨時變量的最小值作為最終的MinV.

按操作時序舉例說明如下：

1. 當前全局版本號為10；

2. 只讀操作T1 (a) 將全局版本號10保存在線程本地 (b) 檢查全局版本號10是否變化，如果變化則重新執(zhí)行(a)

3. 讀寫操作T2： (a) 將全局版本號10保存在線程本地 (b) 檢查全局版本號10是否變化，如果變化則重新執(zhí)行(a) (c) 將全局版本號加1得到11 (d) 構造對象VersionNode，將11保存在VersionNode中，T1執(zhí)行過程中拷貝的源 節(jié)點指針都保存在這個VersionNode中 (e)T2結束，將線程本地保存的版本號改為INT64_MAX (f) 將VersionNode串在全局鏈表中等待回收邏輯處理

4. 回收操作 (a) 保存當前全局版本號11 (b) 遍歷所有線程中保存的版本號取得最小值為10 (c) 取得min(11,10)為10作為內存回收的最大版本號 (d) 遍歷全局VersionNode鏈表，回收版本小于10的VersionNode

5. 只讀操作T1 (a)T1結束，將線程本地保存的版本號改為INT64_MAX

6. 回收操作 (a) 保存當前全局版本號11 (b) 遍歷所有線程中保存的版本號取得最小值為INT64_MAX (c) 取得min(11,INT64_MAX)為11作為內存回收的最大版本號 (d) 遍歷全局VersionNode鏈表，回收版本小于11的VersionNode

● Hash

并發(fā)Hash的實現比較簡單，使用一個稱為BitLock的結構，為每個哈希桶維護一個bit的鎖標記，在查詢或修改這個桶的時候對這個bit原子置為1，表示互斥占用.為了實現簡單，哈希桶的數組使用了一整段連續(xù)內存而非2維數組形式，因此在大內存機器這個數組可能長達10G以上，為了處理初始化的時候對整個數組memset過慢的問題，引入延遲初始化的設計，即每64K大小的連續(xù)桶作為一個初始化單位，使用一個byte來作為初始化標記和并發(fā)鎖標記，當查詢或插入操作涉及到某個64K塊的時候，再對這塊內存調用memset，調用的時候要使用上面提到的bit標記避免多線程同事操作的問題.

2 并發(fā)事務設計

OceanBase使用mvcc技術實現只讀事務與讀寫事務相互不阻塞，每次對行列數據的修改并非在數據的存儲位置上就地修改，而是保存了一份以事務版本號標記的修改記錄，在不考慮每日合并機制的情況下，可以認為在內存表中保存了每一次事務的修改歷史，并且可以讀取每一行的任意歷史快照，但是實際上由于內存的限制，不可能一直保存數據的修改歷史.因此，在每次每日合并時，截至每日合并之前的所有修改歷史將被合并.如圖5所示，原本保存的四個歷史版本，在經過每日合并之后，snapshot[1-3]被合并為snapshot3當時的快照，后續(xù)只能讀到snapshot3和4這兩個歷史快照的數據，而snapshot3之前的snapshot1和2已經被丟棄.

圖5 多版本與每日合并

2.1 事務的隔離級別

OceanBase提供read commited和snapshot read兩種隔離級別的事務，其中snapshot read利用上一節(jié)提到的多版本技術，提供能夠持續(xù)較長時間(一個凍結周期內)的只讀事務，這里不再贅述.而read committed事務的行為與Oracle一致，即保證無論是否在事務(begin … commit)中，每條語句都能夠讀到這條語句開始之前，其他事務已經提交的修改.同時還保證了被Oracle稱為 Statement-Level Read Consistency的隔離行為[6]，即語句運行在當前語句開始之前的快照基礎上，如果語句產生的執(zhí)行計劃涉及到多次與內存事務引擎交互(如select子查詢，索引查詢，根據索引修改等)，那么在語句執(zhí)行過程中其他事務提交的修改，在當前語句執(zhí)行過程中都保證讀不到到這些修改.

● Transaction Set的保證[7]

上面提到的語句級別的read consistency，需要處理快照沖突的情況，即一條語句S涉及多次與內存事務引擎交互，在這個過程中有其他并發(fā)的事務修改并提交了行R，之后語句S要修改行R，因為每條語句要運行在當前語句開始之前的快照基礎上，同時還要避免lost update，因此當遇到這種情況時，語句S發(fā)現在自己運行過程中行R已經被其他事務修改，那么內存事務引擎就將語句S已經做的修改回滾，然后在一個最新的快照基礎上重試執(zhí)行語句S，重試若干次都失敗后，說明對行T的修改的并發(fā)度比較大，對客戶端返回執(zhí)行失敗.

2.2 多版本并發(fā)控制

(1) 事務版本號的分配

如上一段所述，在內存中為每次事務修改都保存了一份歷史記錄，這個記錄由一個全局唯一的事務版本號標記，而mvcc提供的快照讀取特性需要保證能夠讀到任意一個有效歷史時刻上的數據.比如，行A保存了版本號為1、3、5的事務已經提交的修改，行B保存了版本號為2、4、6的事務已經提交的修改，要讀取快照點為5的歷史版本，則要讀取行A上事務版本號為5的版本，和行B上事務版本號為4的版本.這里可以看出，事務版本號要滿足遞增特性，以保證讀取到正確的歷史版本.

某些數據庫在事務開始的時候即分配了事務版本號，在執(zhí)行事務過程中，寫入的數據都以這個版本號進行標記，這種情況下基本可以保證事務版本號的遞增特性，但是需要處理較早開始的事務分配了一個較小的版本號卻較晚提交的情況.比如，起始狀態(tài)，行A=1，行B=1.開啟事務T1，版本號為1，修改了行A=2，并標記事務版本號為1；之后開啟事務T2，版本號為2，修改了行B=3，并標記事務版本號為2；這時提交事務T2，記錄當前已提交的事務版本號為2；之后讀取T2提交之后的快照，即截至版本號為2的快照，如果直接讀取事務版本號小于2的數據，則行A上版本號為1的修改(即A=2)也會被讀取出來，不滿足事務隔離性，因此進行快照讀取的時候需要對當前尚未結束事務的修改進行過濾，如示例中的版本號為1事務的修改A=2，將不能被讀取出來，而只能讀取到A=1.MySQL使用了類似的實現方式，這種方式雖然事務版本號的維護比較簡單，但是快照讀取邏輯比較復雜，并且由于事務版本號順序沒有嚴格反映事務的提交順序，為備機保證與主機一致的事務性回放增加了處理難度[8].

因此內存事務引擎沒有采用在事務開啟時分配事務版本號的方式，而是在事務提交時按照嚴格的事務提交順序分配遞增的事務版本號.這意味需要在事務提交時將分配到的事務版本號寫回到本次事務修改的所有數據上去，對比Oracle的實現，考慮到向回滾塊(undo block)寫回事務版本號，可能需要將回滾塊從磁盤加載回內存，并且當事務修改的行過多時，也會使得寫回操作耗時過長，因此Oracle并沒有在提交事務的時候立即將事務版本號寫回所有的回滾塊，而是維護了一個全局事務槽[9]，在事務修改數據的過程中，將事務槽的地址保存在數據塊中.在事務提交時，將事務版本號保存在事務槽中，然后采用延遲的方式將事務版本號寫回數據塊.

對于OceanBase內存事務引擎來說，所有數據都在內存中存儲，不存在寫回和加載等數據塊的管理成本；并且面向互聯網應用，暫時不提供對長事務的支持(目前，OceanBase的設計只是針對單條事務的redolog不能超過2M).因此，并沒有按照Oracle延遲寫回事務版本號的方式，而是在提交時遍歷所有被修改的數據，在內存中將事務版本號寫回.

(2) 多版本數據的存儲

如圖6所示，在Memtable中，一次事務對一行數據的修改被保存為一個鏈表節(jié)點(稱為數據塊)，并在這個節(jié)點上標記事務版本號；而每行的行頭結構RowValue中保存了三個重要的指針，分別是undo list head，data list head和data list tail.

data list head和data list tail指向最近一次執(zhí)行RowCompaction之后的數據塊鏈表，如圖6所示，事務版本號為1-5的數據塊經過三次合并(1-2合并為2，2-4合并為4，4-5合并為5)后保存在TransID為5的數據塊中，后續(xù)寫入的TransID為6和7的數據塊串聯在鏈表尾部.

undo list head指向的鏈表中，每個節(jié)點保存了每次執(zhí)行RowCompaction之前的數據塊鏈表，如TransID為1和2的數據塊，被合并時構造了一個undo list node指向合并前的數據塊鏈表(即12)，然后將data list head和data list tail指向了合并后的數據塊鏈表；同理TransID為2，3，4的數據塊，被合并時構造了一個undo list node指向合并前的塊鏈表(234).

圖6 多版本數據的內存格式

執(zhí)行快照讀時，如果事務需要讀取TransID為5或之后的快照，則從data list head開始遍歷；而如果事務要讀取5之前的快照，因為已經做過了RowCompaction，所以需要遍歷UndoList，比如要讀取的快照點為4，則遍歷到第1個UndoListNode即可找到TransID為4的數據塊，再比如要讀取的快照點為1，則需要繼續(xù)遍歷UndoList，直到通過第3個UndoListNode找到TransID為1的數據塊.

(3) 事務提交與回滾

為了實現read committed級別的事務，內存引擎需要實現滿足ACID特性的事務，主要包括如下幾個關鍵特性：事務原子性提交，事務級別回滾，語句級別回滾，讀取事務內未提交數據.為每個事務維護一個被稱為事務上下文的結構，用于保存事務執(zhí)行過程中的未提交數據、鎖信息等.OceanBase為每條語句產生一個執(zhí)行計劃，這個執(zhí)行計劃結構中包括了必要的基線數據、操作類型(insert/update/delete/replace/select for update)、待寫入的數據、判斷條件等.內存引擎執(zhí)行這個計劃的過程主要包括：在當前活躍表中查詢必要的動態(tài)數據的行頭(即上一節(jié)提到的RowValue結構)并加鎖，如果行不存在，則寫入一個空的行頭，用于加行鎖；將一行待寫入的多列數據以緊縮格式保存在上一節(jié)提到的數據塊鏈表節(jié)點(稱為TransInfoNode)中.如圖7所示，每行的行頭指針與對應的TransInfoNode被保存在一個稱為UCInfoNode結構中(即uncommited info node)，事務內多行的UCInfoNode串聯在一起保存在事務上下文中.事務提交時，遍歷事務上下文中每行的UCInfoNode找到TransInfoNode，將事務版本號回填.

圖7 事務上下文中緩存的未提交數據

● 事務提交，全局維護了一個當前已提交的最大事務版本號(published_trans_id)，事務開啟時獲取當前的published_trans_id作為當前快照點.在事務提交時，先獲取事務版本號，完成提交操作后，將本事務版本你好原子性的更新到published_trans_id.而這里需要注意的是多個事務之間更新published_trans_id的順序要保證與獲取事務版本號的順序一致.

● 事務回滾，將事務上下文結構連同保存在它里面的UCInfoNode一起釋放即完成回滾.

● 語句級別的回滾，事務內單條語句的執(zhí)行失敗需要保證事務狀態(tài)回滾到語句開始之前，因此在事務上下文中需要在語句開始時記錄UCInfoNode鏈表的狀態(tài)，在語句回滾時將UCInfoNode鏈表的狀態(tài)回滾到語句開始之前.

● 讀取事務內的未提交數據，事務內修改的數據可能會被后面執(zhí)行的語句讀取到，因此在事務執(zhí)行過程中將上面提到的TransInfoNode提前接到每行data list tail的后面，但是不修改data list tail指針，而事務內的讀取邏輯遍歷data list時，并不按照事務開始時的快照點讀取，而是遍歷完整的鏈表，因為并未修改data list tail指針，因此事務回滾時也不需要額外的工作.

● 事務內多次修改同一行，單條語句對一行的修改可以保存為一個TransInfoNode，而事務內多條語句對一行的修改則對應了多個TransInfoNode，而為了處理上述“讀事務內未提交數據”的需求，需要保證一行內多個未提交的TransInfoNode能夠串聯到一起，因此在行頭結構中保存指向這一行UCInfoNode的指針，而在UCInfoNode中保存多次修改的TransInfoNode串聯成的鏈表.

2.3 兩階段鎖并發(fā)控制與沖突調度

內存事務引擎使用經典的兩階段鎖方式來處理并發(fā)的更新事務(比如insert，update，delete等)和select for update的事務，即在參與并發(fā)的所有事務中加鎖與解鎖是相互不重疊的兩個階段.事務中的DML語句在執(zhí)行過程中，涉及到被讀取或修改的行都將被加上互斥行鎖，語句執(zhí)行結束后并不釋放鎖，而是要在事務結束時才能釋放鎖.考慮到范圍鎖或謂詞鎖實現較復雜，以及互聯網應用的特點，OceanBase目前只提供read committed級別的事務，因此我們只實現了行級別的互斥鎖.每行的行頭使用4 byte保存鎖標志，其中最高位標記鎖狀態(tài)，其余的31位用于保存持有當前行鎖的事務的描述符(即鎖的擁有者).

● 鎖沖突調度

與傳統(tǒng)的數據庫實現不同，OceanBase內存事務引擎執(zhí)行事務操作都是在內存中進行的，沒有I/O操作，所以啟動的線程數量一般不會超過CPU核的數量.線程資源寶貴，因此不能出現線程阻塞，來等待某些事件發(fā)生或條件滿足的情況.事務執(zhí)行過程中可能會遇到加行鎖沖突，為了避免線程陷入鎖等待，將嘗試加鎖失敗的請求回滾，并放回任務隊列等待重新執(zhí)行，線程則繼續(xù)處理后面的請求.加鎖失敗時，可以獲取到持有當前行鎖的事務描述符，進而可以得到正在處理這個事務的線程ID.對于autocommit類型的事務，將加鎖失敗的任務放回這個線程自己的任務隊列排隊，待當前持有鎖的事務執(zhí)行完成后，從隊列中取出重試任務，從而避免在鎖未釋放的情況下其他線程的重試開銷.而對于begin…commit類型的事務，盡管事務持有鎖的時間由客戶端決定，但是將任務放回隊列的設計，從而保證了系統(tǒng)在繁忙時能夠正常處理其他沒有鎖沖突的請求，同時有機會重試加鎖失敗的請求.

3 事務持久化、恢復

3.1 批處理與提交

事務提交時，需要通過日志系統(tǒng)將事務的操作日志記錄在硬盤上，在保證事務的操作已經持久化后，事務才算真正地完成.操作日志的記錄順序需要與事務完成的順序一致，如果每完成一個事務就記錄一次操作日志，而記錄的日志需要保證刷到硬盤上，顯然，這種記錄日志的方式在性能方面是無法接受的.所以，每次都會將批量連續(xù)的一批事務日志，作為一次批處理單元，從而一次將這多個事務的操作日志刷到硬盤上.常見的數據庫是通過一個統(tǒng)一的日志緩沖區(qū)，加上一個定期工作的刷日志線程來完成這一功能.OceanBase沒有采用這種方案，而是采用了一種獨特的解決方案，下面將詳細描述這一方法.

內存事務引擎中有一系列負責執(zhí)行事務的線程Trans Executor.在顯示(用戶手動提交)和隱式(系統(tǒng)自動提交)兩種情況下，事務線程都會進行寫日志的操作，其中自動提交類型的事務，在語句執(zhí)行結束的時候會進行寫日志操作；而用戶顯式執(zhí)行Commit操作的事務，會在Commit執(zhí)行完成后進行寫日志操作.在OceanBase系統(tǒng)中，內存事務引擎有一個日志緩沖區(qū),見圖8所示的Log Buffer.日志緩沖區(qū)由若干個緩沖區(qū)塊(Buffer Block)組成，每個緩沖區(qū)塊是2MB大小.目前OceanBase系統(tǒng)不支持單個事務超過2MB的情況，所以一個事務的所有操作日志是可以在一個緩沖區(qū)塊中存儲的.

事務線程執(zhí)行寫日志操作有3個步驟：首先，要在日志緩沖區(qū)占位；然后，將事務線程準備好的事務操作日志數據寫到日志緩沖區(qū)中；最后，由緩沖區(qū)塊最后一個完成寫日志操作的事務線程負責將緩沖區(qū)塊發(fā)起寫硬盤和同步備機的操作.每個事務線程在緩沖區(qū)中填充完日志后，會判斷當前的負載情況，如果負載較低，則不管緩沖區(qū)是否已滿，而立即將緩沖區(qū)提交，以降低事務延遲.

圖8 日志緩沖區(qū)

在日志緩沖區(qū)中的占位操作，通過一個128位組合起來的數字來確定：

struct

{

int64_t block_id;

int32_t offset;

int32_t id;

}

block_id表示操作日志所在的緩沖區(qū)塊的編號，block_id嚴格遞增，緩沖區(qū)塊被循環(huán)使用.offset表示一次事務的操作日志在緩沖區(qū)塊內部的偏移量，id表示操作日志在緩沖區(qū)塊內部的序號.使用這樣的數據結構，事務線程在日志緩沖區(qū)中的占位操作就可以用一次操作系統(tǒng)的CAS指令完成.在CAS操作之前，先判斷當前正在使用的緩沖區(qū)塊還夠不夠存儲要寫入的日志，如果夠，則直接修改offset和id；如果不夠，那么使用下一個緩沖區(qū)塊，block_id遞增1，offset重置為0，id重置為1.然后用修改完的3元組原子替換之前的3元組，如果替換成功，則占位成功，如果原子替換沒成功，則重復之前的流程.

內存事務引擎在執(zhí)行事務時，會記錄事務中操作的數據，記錄的信息是以內存數據結構暫存在事務上下文中.當事務線程完成占位后，則將事務上下文中的事務信息以序列化的格式寫入緩沖區(qū)塊.

每個緩沖區(qū)塊會記錄塊內一共有多少個事務的日志，當事務線程完成寫日志后，會在緩沖區(qū)塊中計數，緩沖區(qū)塊中最后一個完成的事務，需要負責將這個緩沖區(qū)塊持久化.持久化的工作就是將操作日志寫到硬盤并且同步備機.這個操作不會占用事務線程很多時間，事務線程僅進行發(fā)起工作，將緩沖區(qū)塊交給寫盤的線程，并且發(fā)起異步的網絡請求即可.后續(xù)確認日志數據是否寫完，是在寫盤和網絡操作的回調函數中處理.

3.2 并發(fā)事務回放

數據庫的主機以并行方式執(zhí)行多個事務，數據庫的備機通過回放操作日志來追趕主機的數據狀態(tài)，經常會面臨性能問題.為了保證事務完成的順序性，回放很難做成并行的方式.OceanBase使用新的模式結合多版本并發(fā)控制實現了備機的并發(fā)日志回放，保證即使主機在以最大并發(fā)工作時，備機也可以追趕上主機.

如圖9所示，并發(fā)回放模塊由一個讀日志線程和若干個回放線程組成，讀日志線程從操作日志中讀取主機同步到備機的操作日志，并且解析成單獨的事務，然后將每個事務打包成回放任務，交給回放線程.所有的回放線程以消費者工作模式，只要拿到回放任務就進行回放操作，將操作日志中記錄的信息寫到內存表中.

圖9 日志回放線程

回放線程操作Memtable時，需要給所要回放的行加寫鎖，但是與主機進行事務操作不同的是，回放線程不加兩階段鎖.只在操作到具體的行的時候，在操作之前加上鎖，操作完成后，就解開了行鎖.這種方式讓兩個可能操作同一行的事務可以并行回放.

內存事務引擎使用多版本并發(fā)控制，事務回放的順序可能不同于主機操作事務的順序，但是操作過程中，行內插入數據時，保證鏈表內的數據是按照事務的版本有序的，即保證了備機和主機是同樣的Memtable.

4 性能優(yōu)化

本章介紹OceanBase內存事務引擎互聯網實際應用環(huán)境下幾個通用的性能優(yōu)化方案，包括針對并發(fā)熱點行事務的優(yōu)化和并發(fā)讀寫鎖和引用計數的優(yōu)化.事務兩階段鎖，在事務執(zhí)行過程中加鎖，事務回滾或提交redolog成功后才釋放鎖，對于多個并發(fā)事務修改不同行的情況不存在沖突問題，這些并發(fā)執(zhí)行的事務提交的redolog有機會組成一個group，一次I/O就寫到磁盤.但是對于并發(fā)修改同一行的事務，比如電子商務平臺的秒殺活動，幾十萬人同時在線對同一件商品下單，對于服務器來說就是大量并發(fā)事務同時執(zhí)行判斷并扣減商品庫存.

在兩階段鎖的設計中，因為事務在提交redolog成功后才釋放行鎖，在行鎖上沖突的其他事務才能繼續(xù)執(zhí)行，因此對于同一行的并發(fā)事務，只能夠與I/O串行化執(zhí)行，對熱點行事務的提交能力退化成磁盤的IOPS能力.因此對于熱點行的并發(fā)事務，我們對內存事務引擎進行了兩點優(yōu)化.

● 提前釋放鎖

對于autocommit事務，在事務預處理階段執(zhí)行成功，在日志緩沖區(qū)占位后，就可以立即釋放事務執(zhí)行過程加的行鎖，使后續(xù)對相同行的修改事務可以獲取到鎖開始預處理.這樣使得修改相同行的多個并發(fā)事務雖然預處理階段仍然是串行化的，但是耗時最多的寫redolog階段有機會組成一個組一次提交，增加引擎的整體吞吐能力[10].

盡管釋放了行鎖，因為事務還處于未提交的狀態(tài)，所以沒有提交redolog成功前，是不會給客戶端應答成功的，后續(xù)對讀取相同行的只讀事務也不會讀取到未提交的數據；而后續(xù)對相同行的修改事務則需要讀到未提交數據，以保證在前一個事務修改的基礎之上進行操作，比如每次判斷并扣減庫存要在上一次扣減結果的基礎上進行判斷和扣減.

對于redolog提交失敗的處理，當前事務要被回滾.對于只讀事務，因為不能讀取到未提交的數據，因此不受影響；而對于修改了相同行的事務，也要一起回滾，因為提交redolog是順序執(zhí)行的，當前事務提交redolog失敗，意味著它后續(xù)的事務尚未提交，所以回滾是安全的；而對于select…for update語句，對目標行加鎖成功后還需要等待提前釋放鎖的事務提交之后才能繼續(xù)讀取，否則可能出現讀到的未提交數據因為提交redolog失敗而被回滾的風險.

● 熱點行請求調度

盡管提前釋放行鎖解決了并發(fā)事務提交redolog的沖突，但是事務預處理操作仍然需要在加鎖成功后才能執(zhí)行，在并發(fā)壓力大的情況下，處理鎖沖突調度的代價仍然比較大.因此考慮到事務預處理既然要通過加鎖達到串行化處理的目標，那么可以直接將修改相同行的事務請求調度到相同的線程排隊處理，避免一次鎖沖突調度的開銷.

4.1 并發(fā)讀寫鎖與引用計數

在OceanBase內存事務引擎中，經常會使用到一些全局對象，比如Schema管理器、Memtable管理器等、Schema變更或活躍表凍結等管理變更操作時會修改這些對象，而處理一般的事務請求時則不會修改這些對象，因此使用讀寫鎖或引用計數保護這些全局對象，處理事務請求時加讀鎖，執(zhí)行管理變更操作時加寫鎖.OceanBase使用CAS原子操作實現讀寫鎖和引用計數，在CPU核心數量不多時性能較好，但是隨著CPU核的數量的增加原子操作對全局共享變量的讀寫代價變得明顯.

因此針對全局對象讀多寫少的特性，OceanBase實現了并發(fā)讀寫鎖和引用計數，通過減小讀鎖代價，增加寫鎖代價來優(yōu)化性能.即讀鎖的加鎖的解鎖，引用計數的增加和減少都只操作線程局部變量；要獲取寫鎖時，則需要遍歷所有線程，對每個線程局部的讀寫鎖都加上寫鎖；引用計數同理，要嘗試釋放對象時，遍歷所有線程局部的引用計數，確認都沒有引用的情況下才釋放對象，否則在每個線程局部打上標記，等減引用計數時再嘗試釋放對象.

5 總 結

OceanBase內存事務引擎是在動態(tài)數據靜態(tài)數據分離存儲架構下的產物，其在內存格式、并發(fā)控制、持久化和性能優(yōu)化等方面，參考了經典數據庫理論中成熟的方法.并在此基礎上充分發(fā)揮OceanBase架構特點，并結合當今電子商務的應用特性，為OceanBase高性能事務處理奠定了基礎.未來，OceanBase將持續(xù)優(yōu)化內存事務引擎性能，實現分布式Updateserver，在保證事務ACID特性的基礎上，增強可擴展性和容錯能力.

[1] BERENSON H, BERNSTEIN P, GRAY J, et al. A critique of ANSI SQL isolation levels[C]//ACM SIGMOD Record. ACM, 1995, 24(2): 1-10.

[2] MOHAN C, HADERLE D, LINDSAY B, et al. ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging[J]. ACM Transactions on Database Systems (TODS), 1992, 17(1): 94-162.

[3] CHANG F, DEAN J, GHEMAWAT S, et al. Bigtable: A distributed storage system for structured data[J]. ACM Transactions on Computer Systems (TOCS), 2008, 26(2): 4.

[4] RODEH O. B-trees, shadowing, and clones[J]. ACM Transactions on Storage (TOS), 2008, 3(4): 2.

[5] MICHAEL M M. Hazard pointers: Safe memory reclamation for lock-free objects[J]. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(6): 491-504.

[6] Oracle. Data Concurrency and Consistency[EB/OL].[2014-07-31]. http://docs.oracle.com/cd/B19306_01/server.102/b14220/consist.htm#i17841.

[7] Oracle. Transaction Set Consistency [EB/OL].[2014-07-31]. http://docs.oracle.com/cd/B28359_01/server.111/b28318/consist.htm#CNCPT1322.

[8] 何登成. InnoDB 事務/鎖/多版本 實現分析[EB/OL].[2014-07-31]. http://hedengcheng.com/?p=286.

[9] LEWIS J. Transactions and Consistency[M]//Oracle Core. New York:Apress, 2011: 25-58.

[10] JOHNSON R, PANDIS I, STOICA R, et al. Aether: a scalable approach to logging[J]. Proceedings of the VLDB Endowment, 2010, 3(1): 681-692.

(責任編輯 趙 偉)

Memory transaction engine of OceanBase

LI Kai, HAN Fu-sheng

(AlibabaGroup,Beijing100020,China)

OceanBase is a distributed scalable relational database.Its storage architecture is designed by separating baseline static data and increment dynamic data, whose memory transaction engine, namely Memtable, provide dynamic data storage, write, and query, clients wrote data to the in-memory data structure. Memtable and some transaction management structures together form the in-memory database engine, which can achieve the transaction ACID properties. By-based multi-version concurrency control techniques to prevent reading and writing from blocking each other to achieve read-only transactions to meet the“snapshot isolation”level; Provide multi-write concurrency control by using classic row-lock technology to meet the“read committed”transaction isolation level.

relational database system; distributed system; transaction; internet

1000-5641(2014)05-0149-15

2014-06

李凱，男，阿里巴巴集團技術專家，研究方向為分布式系統(tǒng)與數據庫.E-mail：yubai.lk@alipay.com.

韓富晟，男，阿里巴巴集團技術專家，研究方向為分布式系統(tǒng)與數據庫.E-mail：yanran.hfs@alipay.com.

TP333.1

A

10.3969/j.issn.1000-5641.2014.05.013