白 皓，張延園，張向彬

(西北工業(yè)大學計算機學院，陜西 西安 710129)

0 引言

云數據庫是SaaS(Software as a Service，軟件即服務)成為應用趨勢的大背景下發(fā)展起來的云計算技術，而鍵值存儲模型是云數據庫最常采用的數據模型。目前 Facebook 的 Cassandra［1］、Amazon 的 Dynamo［2］(開源實現(xiàn) Voldemort［3］)、Google 的 Bigtable［4］等實際上都采取了類鍵值存儲的方法。

鍵值存儲系統(tǒng)［5］的目的是存儲海量半結構化和非結構化數據，以系統(tǒng)橫向擴展［6］的方法應對數據量和用戶規(guī)模的不斷擴展。由于現(xiàn)實應用的需求，傳統(tǒng)關系型數據庫的SQL訪問方法及事務特性［7］，鍵值存儲系統(tǒng)也需要具備，所以需要在鍵值系統(tǒng)上建立關系型數據庫的訪問層，以兼具鍵值存儲系統(tǒng)和關系型數據庫的優(yōu)點。傳統(tǒng)的關系型數據庫在多節(jié)點情況下的事務控制方法，即兩階段提交協(xié)議［8］，由于復雜的控制邏輯與頻繁的網絡訪問，不適應在大規(guī)模集群應用，具有十分嚴重的效率低下問題［9］。

Google的MegaStore［10］提出了支持實體組內事務的概念，實際上是傳統(tǒng)事務的一個子集，目的是避免過于復雜和昂貴的分布式事務。通過預先定義事務的處理范圍，將特定事務的控制實際上分配在特定單個節(jié)點。但是，MegaStore是Google內部使用的系統(tǒng)，與其業(yè)務密切相關，其實現(xiàn)細節(jié)并不對外公開，本文描述基于開源軟件并且借鑒關系型數據庫的技術來實現(xiàn)類似的事務機制，具有更好的可定制以及可擴展的能力。

1 鍵值存儲的事務控制策略

1.1 系統(tǒng)總體設計思想

傳統(tǒng)的DBMS都存在一個事務存儲管理器［11］，它包含相互緊密結合的4個組件:(1)負責并發(fā)控制的鎖管理器;(2)負責恢復的日志管理器;(3)進行分批I/O處理的數據緩沖池;(4)負責如何在磁盤上存放數據的訪問控制方法。

在云數據庫的時代，產生了對事務服務和數據管理進行分離的需求，這種分離方法支持在云數據庫中實現(xiàn)比較靈活的事務處理［12］。存儲引擎分成兩個部分，即事務組件(事務日志管理器)和數據組件(存儲器)。事務組件只在邏輯層面工作，即它知道事務以及事務的邏輯并發(fā)控制和恢復，但是并不知道底層存儲的結構;數據組件知道物理存儲結構，它可以支持面向記錄的原子訪問操作，但是不知道事務。

根據事務服務和數據管理進行分離的設計思想，事務管理中涉及的組件列舉如下:

(1)查詢執(zhí)行引擎;(2)事務日志管理器;(3)存儲器(持久存儲數據，實為Voldemort實現(xiàn));(4)更新器(將事務日志異步更新至存儲器，又稱SYNC)。

事務系統(tǒng)結構圖如圖1所示。

圖1 事務系統(tǒng)結構圖

查詢執(zhí)行引擎執(zhí)行應用程序的關系型語句，需要訪問存儲器和事務日志管理器。當實體組內事務提交成功，它將該事務中所有的寫操作交給事務日志管理器來進行存儲，事務日志負責保存那些還沒有應用到存儲器中的數據，數據更新器根據數據布局負責將事務日志應用到存儲器。

1.2 數據布局與實體組

數據布局與實體組的概念，決定數據組件(存儲器)和事務組件(事務日志管理器)的數據存儲內容以及對應關系，是決定事務操作對象的核心。由于本文的主要內容是討論事務的實現(xiàn)，因此只舉一個最簡單的例子，詳細的描述請參照文獻［13］。

在具有關系型數據的表1中，PK代表主鍵，TK代表事務鍵，具有相同的事務鍵的數據屬于一個實體組。

表1 數據布局與實體組劃分

在存儲器上存儲時，以PK為key，整條記錄為value進行存儲。在事務日志管理器上存儲時，以TK為key，將事務日志存儲在value中。需要注意的是，事務日志中并不是將同一個實體組中的所有元組錄入，而只是跟該事務相關的元組。所以，事務日志管理器的負荷來自于事務的多少及每個事務的大小，而存儲器的負荷是所有元組的總量的大小，方便系統(tǒng)針對不同應用情況進行橫向擴展。

1.3 事務分散方法

事務分散方法是指通過預先定義的事務處理范圍，明確任何一個數據元組(key-value對)的歸屬(實體組)，并且任何一個事務都應該局限于一個實體組中。同一個事務組內的各事務日志存儲在事務日志管理器的某一節(jié)點。

圖2 數據分散與事務范圍

如圖2所示，不管其來自任何客戶端，任何事務的操作對象都應該被分配在一個確定的實體組中?？梢钥吹?，圖2中虛線連接的2個事務破壞了這條規(guī)則，它們是非法的，應該在提交時失敗。結合1.2節(jié)中的數據，舉例如下。

(1)合法事務(事務的操作對象局限在TK=1的實體組內)。

(2)非法事務(事務的操作對象分別在TK=1和Tk=2的實體組)。

2 查詢執(zhí)行引擎

查詢執(zhí)行引擎由一個或多個查詢執(zhí)行節(jié)點組成，各節(jié)點之間無關，是應用程序與系統(tǒng)的連接部分，將用戶輸入的每個SQL語句進行編譯為一個執(zhí)行計劃，執(zhí)行該計劃，并返回結果。執(zhí)行計劃為key-value對的操作的集合，key-value對的操作為get、put和delete共3種。圖3為一個事務的執(zhí)行過程示意圖。

圖3 一個事務的執(zhí)行過程

應用程序輸入語句和事務語句后，通過與查詢執(zhí)行引擎連接，將SQL語句和事務語句傳輸給查詢執(zhí)行引擎。當查詢執(zhí)行引擎執(zhí)行事務(開始執(zhí)行事務和提交事務)時，訪問事務日志管理器。開始執(zhí)行事務時，讀該事務所屬事務組的日志集合(WAL)。在查詢執(zhí)行引擎中，基于有限訪問模式的SQL優(yōu)化器、SQL解析器/編譯器訪問元數據，然后產生查詢計劃。執(zhí)行引擎和事務管理器使用樂觀并發(fā)控制的方式來執(zhí)行該查詢計劃，這中間可能需要訪問存儲器(data)來得到尚未在事務日志中緩存的數據，并緩存所有的寫操作。最后，使用鍵值存儲中的put-if-current原子操作來提交事務至該事務所屬事務組的日志集合。在執(zhí)行過程中，事務管理器識別事務鍵的值并使用它來提交一個事務。由于各個查詢執(zhí)行節(jié)點并不相關聯(lián)，所以查詢執(zhí)行引擎的橫向擴展只需單純地增加節(jié)點即可。

3 事務日志管理器

3.1 事務日志管理器構成

事務日志管理器是由多個服務器組成的Voldemort集群，用來處理分布式的事務日志。事務日志管理器為每個事務組分發(fā)一個固定的key，通過一個特定的哈希函數將該key映射到一維空間上，落在一維空間的某一分區(qū)，由負責該分區(qū)的節(jié)點進行處理，從而將分布式事務轉化為在單個節(jié)點上處理的事務。該節(jié)點對同一個事務組內的事務日志進行存儲和管理，每個提交的事務形成一個事務日志，并按提交時間的順序具有唯一的時間戳，這些日志構成事務組事務日志的集合。每個事務日志用于更新存儲器中的不相關聯(lián)的數據集合。由于Voldemort本身具有非常好的擴展性，事務日志管理器和存儲器的橫向擴展是非常容易的。

3.2 事務提交和沖突檢查

當同一事務組內多個事務并發(fā)時，它們在提交時都需要經過沖突檢查，才能成功提交，轉化為一個事務日志。沖突檢查機制采用并發(fā)版本系統(tǒng)的方法，并且充分利用鍵值對象的特征，針對key進行檢查，而不是對數據元組進行對比，提高了檢查的效率。

在進行檢查時，沒有發(fā)生沖突的日志條目，就稱檢查成功。如果當前正在進行提交的事務在事務提交前讀取了一個鍵值對象，然后其他事務對這個鍵值對象進行了寫操作產生了日志條目，則這個正在提交的事務就與產生的日志條目發(fā)生了沖突。

一個檢查通過一個時間戳和一系列的讀集合來進行呈現(xiàn)。檢查的時間戳是由事務啟動時得到的值。

一個讀集合包含了在同一個實體組中的一系列的key值。

如圖4所示，進行檢查時，事務管理器檢查是否有任何位于Tc和Current之間的寫操作與讀集合發(fā)生沖突，Tc為檢查的時間戳。如果 Tc的值小于OLDEST，則事務管理器無法保證沖突沒有發(fā)生。在這種情況下，檢查返回的結果為false。

圖4 沖突檢查

在事務執(zhí)行期間，查詢執(zhí)行引擎會緩存所有的寫操作和記錄下所有可能與其他事務發(fā)生沖突的讀集合。

當事務請求提交時，查詢執(zhí)行引擎使用已經記錄下的讀集合和時間戳Tc來進行一個檢查操作。當檢查請求返回true時，事務則成功提交;否則，事務被拒絕，查詢執(zhí)行引擎應該重新開始或者丟棄該事務。

4 實驗結果與分析

4.1 驗證結果與分析

為了驗證事務控制的正確性，采取了tpc-c［14］中的表結構和事務來進行實驗。

實驗環(huán)境為查詢執(zhí)行引擎若干臺，事務日志管理器3節(jié)點，存儲器3節(jié)點。采用的參照更新比例為95:5，實驗得到的數據如表2所示。

表2 實驗結果

表2中，qps表示每秒鐘執(zhí)行的SQL語句數。

經過實驗，本系統(tǒng)能在分布式的條件下具有較好的事務特性。

4.2 開銷分析

由于關系型查詢語句和事務的處理不可能只涉及某存儲節(jié)點上的某一條鍵值對的數據，在語句執(zhí)行時因需要訪問多個存儲節(jié)點上的數據會造成系統(tǒng)響應過慢而浪費網絡資源。因此，設定事務訪問的模式，然后根據事務處理的特點和訪問的方式，將事務處理過程中需要用到的數據從各個存儲節(jié)點上讀取出來，集中到事務日志管理器的對應節(jié)點中，從而使用該節(jié)點的數據來進行查詢和更新操作，保證了事務的ACID特性，減小了網絡資源的使用，極大地提升了事務處理的速度。

5 結束語

本文探討了如何在分布式鍵值存儲系統(tǒng)中實現(xiàn)有限制的高速事務，使其滿足ACID特性。在分布式系統(tǒng)鍵值存儲系統(tǒng)中，事務的分布式控制是非常復雜的，網絡訪問非常耗時并且?guī)砹烁嗟膹碗s性，本系統(tǒng)通過限制事務數據的范圍，減少網絡訪問的次數。在提交驗證時，也充分利用鍵值系統(tǒng)的特點，并結合傳統(tǒng)關系型數據庫事務控制的方法，從而實現(xiàn)了在鍵值系統(tǒng)上的事務ACID特性。

［1］Avinash Lakshman，Prashant Malik.Cassandra:A decentralized structured storage system［J］.ACM SIGOPS Operating Systems Review，2010，44(2):35-40.

［2］De Candia G，Hastorun D，Jampani M，et al.Dynamo:Amazon’s highly available key-value store［J］.ACM SIGOPS Operating Systems Review，2007，41(6):205-220.

［3］LinkedIn.Project Voldemort［EB/OL］.http://www.project-voldemort.com/voldemort/，2013-03-19.

［4］Chang F，Dean J，Ghemawat S，et al.Bigtable:A distributed storage system for structured data［J］.ACM Transactions on Computer Systems，2008，26(2):Article No.4.

［5］Wikipedia.NoSQL［EB/OL］.http://en.wikipedia.org/wiki/NoSQL，2012-07-07.

［6］中國存儲網.什么是Scale Up和Scale Out?［EB/OL］.http://www.chinastor.com/a/jishu/scale.html，2011-06-13.

［7］Jim Gray，Andreas Reuter.Transaction Processing:Concepts and Techniques［M］.Morgan Kaufmann，1992.

［8］劉威.分布式數據庫及其技術［J］.長春大學學報，2000，10(1):27-30.

［9］Browne J.Brewer’s CAP Theorem［DB/OL］.http://www.julianbrowne.com/article/viewer/brewers-cap-theorem，2009-01-11.

［10］Baker J，Bond C，Corbett J，et al.Megastore:Providing scalable，highly available storage for interactive services［C］//Proceedings of the 5th Biennial Conference on Innovative Data Systems Research.2011:223-234.

［11］林子雨，賴永炫，林琛，等.云數據庫研究［J］.軟件學報，2012，23(5):1148-1166.

［12］Lomet D，F(xiàn)ekete A，Weikum G，et al.Unbundling transaction services in the cloud［C］//Proceedings of the 4th Biennial Conference on Innovative Data Systems Research.2009.

［13］宋慧，張延園，何娟娟.基于鍵值存儲上中間件技術的研究［J］.計算機與現(xiàn)代化，2013(1):77-80.

［14］Meikel Poess，Chris Floyd.New TPC benchmarks for decision support and Web commerce［J］.ACM SIGMOD Record，2000，29(4):64-71.