白 皓，張延園，張向彬

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

0 引言

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

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

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

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

1.1 系統總體設計思想

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

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

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

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

事務系統結構圖如圖1所示。

圖1 事務系統結構圖

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

1.2 數據布局與實體組

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

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

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

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

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é)點之間無關，是應用程序與系統的連接部分，將用戶輸入的每個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é)點并不相關聯，所以查詢執(zhí)行引擎的橫向擴展只需單純地增加節(jié)點即可。

3 事務日志管理器

3.1 事務日志管理器構成

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

3.2 事務提交和沖突檢查

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

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

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

一個讀集合包含了在同一個實體組中的一系列的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語句數。

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

4.2 開銷分析

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

5 結束語

本文探討了如何在分布式鍵值存儲系統中實現有限制的高速事務，使其滿足ACID特性。在分布式系統鍵值存儲系統中，事務的分布式控制是非常復雜的，網絡訪問非常耗時并且?guī)砹烁嗟膹碗s性，本系統通過限制事務數據的范圍，減少網絡訪問的次數。在提交驗證時，也充分利用鍵值系統的特點，并結合傳統關系型數據庫事務控制的方法，從而實現了在鍵值系統上的事務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，Fekete 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］.計算機與現代化，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.