李 凱， 韓富晟

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

?

OceanBase內(nèi)存事務(wù)引擎

李 凱， 韓富晟

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

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

關(guān)系數(shù)據(jù)庫； 分布式系統(tǒng)； 事務(wù)； 互聯(lián)網(wǎng)

0 引 言

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

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

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

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

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

1 內(nèi)存事務(wù)引擎概述

1.1 總體架構(gòu)

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

圖1 內(nèi)存引擎結(jié)構(gòu)

● 事務(wù)執(zhí)行流程

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

● Memtable內(nèi)存結(jié)構(gòu)

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

1.2 內(nèi)存存儲格式

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

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

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

圖3 多次修改的合并

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

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

1.3 并發(fā)索引結(jié)構(gòu)

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

● B+tree

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

圖4 B+tree結(jié)構(gòu)

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

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

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

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

● Copy on write內(nèi)存回收的處理

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

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

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

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

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

1. 當(dāng)前全局版本號為10；

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

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

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

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

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

● Hash

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

2 并發(fā)事務(wù)設(shè)計

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

圖5 多版本與每日合并

2.1 事務(wù)的隔離級別

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

● Transaction Set的保證[7]

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

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

(1) 事務(wù)版本號的分配

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

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

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

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

(2) 多版本數(shù)據(jù)的存儲

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

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

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

圖6 多版本數(shù)據(jù)的內(nèi)存格式

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

(3) 事務(wù)提交與回滾

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

圖7 事務(wù)上下文中緩存的未提交數(shù)據(jù)

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

● 事務(wù)回滾，將事務(wù)上下文結(jié)構(gòu)連同保存在它里面的UCInfoNode一起釋放即完成回滾.

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

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

● 事務(wù)內(nèi)多次修改同一行，單條語句對一行的修改可以保存為一個TransInfoNode，而事務(wù)內(nèi)多條語句對一行的修改則對應(yīng)了多個TransInfoNode，而為了處理上述“讀事務(wù)內(nèi)未提交數(shù)據(jù)”的需求，需要保證一行內(nèi)多個未提交的TransInfoNode能夠串聯(lián)到一起，因此在行頭結(jié)構(gòu)中保存指向這一行UCInfoNode的指針，而在UCInfoNode中保存多次修改的TransInfoNode串聯(lián)成的鏈表.

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

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

● 鎖沖突調(diào)度

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

3 事務(wù)持久化、恢復(fù)

3.1 批處理與提交

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

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

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

圖8 日志緩沖區(qū)

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

struct

{

int64_t block_id;

int32_t offset;

int32_t id;

}

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

內(nèi)存事務(wù)引擎在執(zhí)行事務(wù)時，會記錄事務(wù)中操作的數(shù)據(jù)，記錄的信息是以內(nèi)存數(shù)據(jù)結(jié)構(gòu)暫存在事務(wù)上下文中.當(dāng)事務(wù)線程完成占位后，則將事務(wù)上下文中的事務(wù)信息以序列化的格式寫入緩沖區(qū)塊.

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

3.2 并發(fā)事務(wù)回放

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

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

圖9 日志回放線程

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

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

4 性能優(yōu)化

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

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

● 提前釋放鎖

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

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

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

● 熱點行請求調(diào)度

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

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

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

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

5 總 結(jié)

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

[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 事務(wù)/鎖/多版本 實現(xiàn)分析[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.

(責(zé)任編輯 趙 偉)

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

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

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

TP333.1

A

10.3969/j.issn.1000-5641.2014.05.013