基于鍵值存儲(chǔ)的事務(wù)控制策略

白 皓，張延園，張向彬

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，陜西 西安 710129)

0 引言

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

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

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

1 鍵值存儲(chǔ)的事務(wù)控制策略

1.1 系統(tǒng)總體設(shè)計(jì)思想

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

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

根據(jù)事務(wù)服務(wù)和數(shù)據(jù)管理進(jìn)行分離的設(shè)計(jì)思想，事務(wù)管理中涉及的組件列舉如下:

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

事務(wù)系統(tǒng)結(jié)構(gòu)圖如圖1所示。

圖1 事務(wù)系統(tǒng)結(jié)構(gòu)圖

查詢執(zhí)行引擎執(zhí)行應(yīng)用程序的關(guān)系型語(yǔ)句，需要訪問(wèn)存儲(chǔ)器和事務(wù)日志管理器。當(dāng)實(shí)體組內(nèi)事務(wù)提交成功，它將該事務(wù)中所有的寫操作交給事務(wù)日志管理器來(lái)進(jìn)行存儲(chǔ)，事務(wù)日志負(fù)責(zé)保存那些還沒(méi)有應(yīng)用到存儲(chǔ)器中的數(shù)據(jù)，數(shù)據(jù)更新器根據(jù)數(shù)據(jù)布局負(fù)責(zé)將事務(wù)日志應(yīng)用到存儲(chǔ)器。

1.2 數(shù)據(jù)布局與實(shí)體組

數(shù)據(jù)布局與實(shí)體組的概念，決定數(shù)據(jù)組件(存儲(chǔ)器)和事務(wù)組件(事務(wù)日志管理器)的數(shù)據(jù)存儲(chǔ)內(nèi)容以及對(duì)應(yīng)關(guān)系，是決定事務(wù)操作對(duì)象的核心。由于本文的主要內(nèi)容是討論事務(wù)的實(shí)現(xiàn)，因此只舉一個(gè)最簡(jiǎn)單的例子，詳細(xì)的描述請(qǐng)參照文獻(xiàn)［13］。

在具有關(guān)系型數(shù)據(jù)的表1中，PK代表主鍵，TK代表事務(wù)鍵，具有相同的事務(wù)鍵的數(shù)據(jù)屬于一個(gè)實(shí)體組。

表1 數(shù)據(jù)布局與實(shí)體組劃分

在存儲(chǔ)器上存儲(chǔ)時(shí)，以PK為key，整條記錄為value進(jìn)行存儲(chǔ)。在事務(wù)日志管理器上存儲(chǔ)時(shí)，以TK為key，將事務(wù)日志存儲(chǔ)在value中。需要注意的是，事務(wù)日志中并不是將同一個(gè)實(shí)體組中的所有元組錄入，而只是跟該事務(wù)相關(guān)的元組。所以，事務(wù)日志管理器的負(fù)荷來(lái)自于事務(wù)的多少及每個(gè)事務(wù)的大小，而存儲(chǔ)器的負(fù)荷是所有元組的總量的大小，方便系統(tǒng)針對(duì)不同應(yīng)用情況進(jìn)行橫向擴(kuò)展。

1.3 事務(wù)分散方法

事務(wù)分散方法是指通過(guò)預(yù)先定義的事務(wù)處理范圍，明確任何一個(gè)數(shù)據(jù)元組(key-value對(duì))的歸屬(實(shí)體組)，并且任何一個(gè)事務(wù)都應(yīng)該局限于一個(gè)實(shí)體組中。同一個(gè)事務(wù)組內(nèi)的各事務(wù)日志存儲(chǔ)在事務(wù)日志管理器的某一節(jié)點(diǎn)。

圖2 數(shù)據(jù)分散與事務(wù)范圍

如圖2所示，不管其來(lái)自任何客戶端，任何事務(wù)的操作對(duì)象都應(yīng)該被分配在一個(gè)確定的實(shí)體組中。可以看到，圖2中虛線連接的2個(gè)事務(wù)破壞了這條規(guī)則，它們是非法的，應(yīng)該在提交時(shí)失敗。結(jié)合1.2節(jié)中的數(shù)據(jù)，舉例如下。

(1)合法事務(wù)(事務(wù)的操作對(duì)象局限在TK=1的實(shí)體組內(nèi))。

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

2 查詢執(zhí)行引擎

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

圖3 一個(gè)事務(wù)的執(zhí)行過(guò)程

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

3 事務(wù)日志管理器

3.1 事務(wù)日志管理器構(gòu)成

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

3.2 事務(wù)提交和沖突檢查

當(dāng)同一事務(wù)組內(nèi)多個(gè)事務(wù)并發(fā)時(shí)，它們?cè)谔峤粫r(shí)都需要經(jīng)過(guò)沖突檢查，才能成功提交，轉(zhuǎn)化為一個(gè)事務(wù)日志。沖突檢查機(jī)制采用并發(fā)版本系統(tǒng)的方法，并且充分利用鍵值對(duì)象的特征，針對(duì)key進(jìn)行檢查，而不是對(duì)數(shù)據(jù)元組進(jìn)行對(duì)比，提高了檢查的效率。

在進(jìn)行檢查時(shí)，沒(méi)有發(fā)生沖突的日志條目，就稱檢查成功。如果當(dāng)前正在進(jìn)行提交的事務(wù)在事務(wù)提交前讀取了一個(gè)鍵值對(duì)象，然后其他事務(wù)對(duì)這個(gè)鍵值對(duì)象進(jìn)行了寫操作產(chǎn)生了日志條目，則這個(gè)正在提交的事務(wù)就與產(chǎn)生的日志條目發(fā)生了沖突。

一個(gè)檢查通過(guò)一個(gè)時(shí)間戳和一系列的讀集合來(lái)進(jìn)行呈現(xiàn)。檢查的時(shí)間戳是由事務(wù)啟動(dòng)時(shí)得到的值。

一個(gè)讀集合包含了在同一個(gè)實(shí)體組中的一系列的key值。

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

圖4 沖突檢查

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

當(dāng)事務(wù)請(qǐng)求提交時(shí)，查詢執(zhí)行引擎使用已經(jīng)記錄下的讀集合和時(shí)間戳Tc來(lái)進(jìn)行一個(gè)檢查操作。當(dāng)檢查請(qǐng)求返回true時(shí)，事務(wù)則成功提交;否則，事務(wù)被拒絕，查詢執(zhí)行引擎應(yīng)該重新開(kāi)始或者丟棄該事務(wù)。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 驗(yàn)證結(jié)果與分析

為了驗(yàn)證事務(wù)控制的正確性，采取了tpc-c［14］中的表結(jié)構(gòu)和事務(wù)來(lái)進(jìn)行實(shí)驗(yàn)。

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

表2 實(shí)驗(yàn)結(jié)果

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

經(jīng)過(guò)實(shí)驗(yàn)，本系統(tǒng)能在分布式的條件下具有較好的事務(wù)特性。

4.2 開(kāi)銷分析

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

5 結(jié)束語(yǔ)

本文探討了如何在分布式鍵值存儲(chǔ)系統(tǒng)中實(shí)現(xiàn)有限制的高速事務(wù)，使其滿足ACID特性。在分布式系統(tǒng)鍵值存儲(chǔ)系統(tǒng)中，事務(wù)的分布式控制是非常復(fù)雜的，網(wǎng)絡(luò)訪問(wèn)非常耗時(shí)并且?guī)?lái)了更多的復(fù)雜性，本系統(tǒng)通過(guò)限制事務(wù)數(shù)據(jù)的范圍，減少網(wǎng)絡(luò)訪問(wèn)的次數(shù)。在提交驗(yàn)證時(shí)，也充分利用鍵值系統(tǒng)的特點(diǎn)，并結(jié)合傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)事務(wù)控制的方法，從而實(shí)現(xiàn)了在鍵值系統(tǒng)上的事務(wù)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］中國(guó)存儲(chǔ)網(wǎng).什么是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］劉威.分布式數(shù)據(jù)庫(kù)及其技術(shù)［J］.長(zhǎng)春大學(xué)學(xué)報(bào)，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］林子雨，賴永炫，林琛，等.云數(shù)據(jù)庫(kù)研究［J］.軟件學(xué)報(bào)，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］宋慧，張延園，何娟娟.基于鍵值存儲(chǔ)上中間件技術(shù)的研究［J］.計(jì)算機(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.