摘 要： 對于讀密集型的云計算應(yīng)用，現(xiàn)有系統(tǒng)很難同時滿足它們對性能、一致性與可用性的需求。因此提出了一種基于事務(wù)內(nèi)存和云存儲技術(shù)的編程與存儲模型TMC，能為云應(yīng)用提供可配置的事務(wù)特性與數(shù)據(jù)存儲服務(wù)。TMC包括事務(wù)與存儲兩個組件，事務(wù)組件允許所有只讀事務(wù)無需遠(yuǎn)程驗證即可順利提交，其他事務(wù)則采用2PC算法提交；存儲組件負(fù)責(zé)實現(xiàn)系統(tǒng)的可擴(kuò)展性與可用性。仿真實驗結(jié)果表明，TMC具有較高的性能與可用性。系統(tǒng)若經(jīng)進(jìn)一步改進(jìn)和優(yōu)化，將具有應(yīng)用于實際生產(chǎn)環(huán)境中的潛力，可為用戶提供高質(zhì)量的云計算服務(wù)。

關(guān)鍵詞： 讀密集； 事務(wù)內(nèi)存； 云計算； 數(shù)據(jù)副本； 一致性

中圖分類號：TP302 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-8228（2014）02-11-04

0 引言

事務(wù)內(nèi)存[1]是一種通過事務(wù)來實現(xiàn)并發(fā)控制的編程范式，事務(wù)的ACI特性由事務(wù)內(nèi)存引擎來保證，無需開發(fā)者關(guān)心。與其他并發(fā)控制方法（例如鎖）相比，事務(wù)內(nèi)存具有安全、易用等優(yōu)點，近年來在學(xué)術(shù)界受到了廣泛關(guān)注。在云計算環(huán)境下，為了讓系統(tǒng)管理員和應(yīng)用開發(fā)者充分地利用云計算帶來的強(qiáng)擴(kuò)展和可用性，設(shè)計實現(xiàn)新型的適用于云計算的編程模型是一項極其緊迫的任務(wù)。當(dāng)前已初露端倪的云計算編程模型以MapReduce[2]為代表，其他大體上是其變種，MapReduce的缺點是需要遵循復(fù)雜的開發(fā)模式，實際效率低下。事務(wù)內(nèi)存是另一種可以作為云計算編程模型的技術(shù)，在開發(fā)復(fù)雜的分布式應(yīng)用程序過程中，使用事務(wù)內(nèi)存技術(shù)可以加快生產(chǎn)率，縮短開發(fā)周期，提高代碼質(zhì)量。但現(xiàn)有的事務(wù)內(nèi)存研究多集中于共享內(nèi)存多處理器的單機(jī)環(huán)境下，而適用于分布式環(huán)境、能滿足云計算應(yīng)用需求的研究迄今尚未出現(xiàn)。

現(xiàn)實中存在著大量讀密集型應(yīng)用（例如數(shù)據(jù)倉庫），本文提出的面向讀密集型應(yīng)用的事務(wù)內(nèi)存云（Transactional Memory Cloud，以下簡稱TMC），基于事務(wù)內(nèi)存與云存儲技術(shù)，設(shè)計了一種新型云計算編程存儲模型，保證所有的只讀事務(wù)均不會被撤銷，系統(tǒng)可用性與可靠性則通過異步數(shù)據(jù)副本策略實現(xiàn)。以上特性使得TMC適用于對性能、可擴(kuò)展性和數(shù)據(jù)一致性均有嚴(yán)格要求的讀密集型應(yīng)用。

1 相關(guān)工作

云計算為工業(yè)和學(xué)術(shù)界帶來了大機(jī)遇，同時也為有效利用云中各類資源提出了挑戰(zhàn)。盡管不同的云計算應(yīng)用存在一定差異，但總的來說云計算應(yīng)用的支撐平臺應(yīng)具有良好的性能、可擴(kuò)展性和可靠性。

當(dāng)前已有的商用云計算系統(tǒng)大多不支持事務(wù)特性，但各類相關(guān)應(yīng)用對事務(wù)支持的需求卻從未停止，例如社交網(wǎng)絡(luò)、協(xié)作編輯、在線游戲等。將一致性檢查等工作交給上層用戶處理是目前常見的策略[3]，但其方法增加了開發(fā)者負(fù)擔(dān)，顯然不是一種有效的手段。利用事務(wù)內(nèi)存技術(shù)實現(xiàn)對云計算應(yīng)用事務(wù)特性的支持是一種可行的新思路，但在研究應(yīng)用過程中需要注意對各種云計算系統(tǒng)特性的權(quán)衡。

文獻(xiàn)[4]提出的P-Store能夠保證云計算系統(tǒng)的可擴(kuò)展性和強(qiáng)一致性，但該協(xié)議要求只讀事務(wù)在提交時首先要完成分布式驗證，并有可能被回滾或撤銷，而本文的TMC則不存在以上限制。文獻(xiàn)[5]利用軟件事務(wù)內(nèi)存與多版本并發(fā)控制技術(shù)來支持分布式事務(wù)的一致性，但對其他諸如擴(kuò)展性、可用性等系統(tǒng)特性并未提及，TMC則通過將事務(wù)組件與存儲組件的解耦，對其進(jìn)行了統(tǒng)籌權(quán)衡的考慮。

2 系統(tǒng)建模

TMC包括事務(wù)和存儲兩大組件，事務(wù)組件提供邏輯上的并發(fā)事務(wù)處理，無需了解數(shù)據(jù)的物理位置；存儲組件負(fù)責(zé)存儲數(shù)據(jù)副本，并保證其一致性，但不必關(guān)心事務(wù)特性。TMC系統(tǒng)模型如圖1所示。

圖1中的DC為數(shù)據(jù)中心，這些數(shù)據(jù)中心可通過10Gb/s的專用以太網(wǎng)互聯(lián)（圖1中以環(huán)為例），被部署為“私有云”或“公有云”。在每個數(shù)據(jù)中心內(nèi)部，包含著成千上萬臺計算/存儲機(jī)器節(jié)點（簡稱節(jié)點）。事務(wù)組件負(fù)責(zé)通過協(xié)調(diào)管理每個節(jié)點上的事務(wù)組件代理來接收處理用戶通過互聯(lián)網(wǎng)發(fā)來的事務(wù)處理請求，存儲組件則通過共識協(xié)議和鏈路管理數(shù)據(jù)及其元數(shù)據(jù)的所有副本，并向事務(wù)組件提供一致、透明和彈性的數(shù)據(jù)訪問服務(wù)。

TMC是一個通過消息傳遞進(jìn)行通信的分布式系統(tǒng)，其中每個節(jié)點只能運(yùn)行一個內(nèi)存事務(wù)，令Γ={Tx1，…，Txn}表示系統(tǒng)中全體事務(wù)的集合。每個數(shù)據(jù)項則由三元組do=表示，其中do.id為數(shù)據(jù)項標(biāo)識，do.value為原始數(shù)據(jù)，do.ver為數(shù)據(jù)項版本號。對于某個數(shù)據(jù)項doi，rep（doi）表示存儲doi全部數(shù)據(jù)副本的節(jié)點集合。

任一個內(nèi)存事務(wù)Txi均由事務(wù)開始操作Start、針對數(shù)據(jù)項的讀（Read）寫（Write）操作序列、事務(wù)提交操作Commit或事務(wù)撤銷操作Abort三部分構(gòu)成。Txi可由任一個節(jié)點啟動并讀寫任一個數(shù)據(jù)項，事務(wù)集T（T?Γ）的歷史HIS（T）是由T上的事務(wù)操作（Start，Read，Write，Commit，Abort）事件組成的集合。每個Txi還需要維護(hù)三個屬性writeID、nextID和ts，writeID用于記錄Txi中最近提交的寫事務(wù)（至少包含一個寫操作）的時間戳；nextID用于記錄下一個將要提交的事務(wù)（至少訪問Txi中的一個數(shù)據(jù)項）的時間戳；ts用于記錄Txi執(zhí)行第一個讀操作Read1的時間戳，設(shè)Read1所訪問的數(shù)據(jù)項所在的內(nèi)存事務(wù)為Txj，則ts=max（Txi.writeID，Txj.writeID），Read1之后讀操作所訪問的數(shù)據(jù)項的版本號均不能大于ts。

3 事務(wù)組件

事務(wù)組件負(fù)責(zé)支持分布式事務(wù)內(nèi)存編程范式，并保證其正確性。為使所有讀事務(wù)不被撤銷，需要解決兩個問題：①建立系統(tǒng)全局快照，使所有內(nèi)存事務(wù)的讀操作可以從數(shù)據(jù)項的多個版本中選擇合適的一個；②為寫事務(wù)在提交階段建立全局串行化以保證事務(wù)性。

TMC基于兩階段提交算法[6]（2PC）和文獻(xiàn)[7]中的方法解決上述兩個問題。為了正確地實現(xiàn)事務(wù)串行化，事務(wù)組件會在每個Txi的讀操作后更新其nextID屬性。如果Txi的節(jié)點接收到了來自另一個事務(wù)Txj的讀請求并且Txj.ts>Txi.nextID，則推進(jìn)Txi.nextID至Txj.ts。

3.1 內(nèi)存事務(wù)的讀寫操作

TMC采用延時讀寫策略，事務(wù)Txi執(zhí)行寫操作時先將要寫入的數(shù)據(jù)項do保存在Txi的寫集合ws中，Txi.ws只有在提交階段時才對外可見。Txi對數(shù)據(jù)項do的讀操作則分為本地讀（來自Txi）和遠(yuǎn)程讀（來自Txj）兩種類型。本地讀如算法1。

4 存儲組件

存儲組件以云的形式向事務(wù)組件（也可以直接面向最終用戶）提供數(shù)據(jù)存儲服務(wù)。從用戶角度來看，所有的讀寫操作只針對一個數(shù)據(jù)副本，數(shù)據(jù)一致性和可用性、系統(tǒng)可擴(kuò)展性由存儲組件透明地實現(xiàn)。TMC中的存儲組件是一群相互依存的服務(wù)集合，共同實現(xiàn)系統(tǒng)設(shè)計目標(biāo)，如圖3所示。

Locator服務(wù)將數(shù)據(jù)項id映射到數(shù)據(jù)中心，Router服務(wù)將消息轉(zhuǎn)發(fā)到節(jié)點，Allocator服務(wù)決定存放數(shù)據(jù)項及元數(shù)據(jù)的節(jié)點，Selector服務(wù)選擇存放數(shù)據(jù)副本的數(shù)據(jù)中心，MetaData與RawData服務(wù)用于存儲元數(shù)據(jù)和數(shù)據(jù)值，Logger服務(wù)記錄針對每個數(shù)據(jù)項的操作。

4.1 存儲組件的擴(kuò)展性

TMC存儲組件的設(shè)計目標(biāo)之一是系統(tǒng)吞吐量與容量同系統(tǒng)節(jié)點數(shù)之間成正比，即具有良好的可擴(kuò)展性。為實現(xiàn)這個目標(biāo)，課題組首先在前期工作基礎(chǔ)上[8]，采用機(jī)架選舉和多路線性散列算法，將工作負(fù)載均勻地分布到不同的數(shù)據(jù)中心以及每個數(shù)據(jù)中心的內(nèi)部節(jié)點，該過程不需要“中心節(jié)點”來管理，全體數(shù)據(jù)中心和節(jié)點各司其職，防止了系統(tǒng)瓶頸的產(chǎn)生。

為進(jìn)一步增強(qiáng)擴(kuò)展性，存儲組件的另一個設(shè)計目標(biāo)是將元數(shù)據(jù)（包括位置、大小、副本信息等）與數(shù)據(jù)項本身解耦，具體實現(xiàn)上采用了層次化的設(shè)計方法。最上層是定位層，在訪問每個數(shù)據(jù)項時，均需通過Locator服務(wù)計算出存儲其元數(shù)據(jù)的數(shù)據(jù)中心，為提高可用性，元數(shù)據(jù)也被多處存儲（見圖1），并使用強(qiáng)一致性協(xié)議同步，Locator從多個副本中根據(jù)預(yù)設(shè)策略（例如距離）選擇合適的元數(shù)據(jù)。

存儲組件第二層是操作層，由MetaData服務(wù)負(fù)責(zé)處理數(shù)據(jù)項的創(chuàng)建與刪除，并確保數(shù)據(jù)項與其id屬性間的一一對應(yīng)。

存儲組件的最下層是數(shù)據(jù)層，其中的Allocator服務(wù)根據(jù)數(shù)據(jù)項id計算其元數(shù)據(jù)和數(shù)據(jù)值的存儲節(jié)點；Router服務(wù)負(fù)責(zé)接收來自用戶或其他數(shù)據(jù)中心的請求，并將其轉(zhuǎn)發(fā)至相應(yīng)節(jié)點。本文假設(shè)所有數(shù)據(jù)中心均具有一定的穩(wěn)定性，每個數(shù)據(jù)中心均有一張全局成員信息表。每當(dāng)增加或移除一個數(shù)據(jù)中心時，需要更新所有信息表。

4.2 數(shù)據(jù)一致性

因為從用戶角度來看，所有讀寫操作只針對一個數(shù)據(jù)副本，所以需要使用數(shù)據(jù)一致性協(xié)議來更新其他副本。存儲組件共實現(xiàn)了三種數(shù)據(jù)一致性協(xié)議[6]供用戶在創(chuàng)建數(shù)據(jù)項時自由動態(tài)地選擇，見表1。

5 實驗

實驗的主要目的是為了驗證TMC能適用于讀密集型的云計算應(yīng)用，同時也應(yīng)具備良好性能和高可用性。本文利用澳大利亞墨爾本大學(xué)的開源系統(tǒng)CloudSim[9]作為測試平臺來模擬云計算環(huán)境，課題組實現(xiàn)了TMC原型及相關(guān)算法，并集成到CloudSim中。實驗機(jī)器的軟硬件配置為Windows 7 64bit+四核Intel Corei5 2.53GHz+內(nèi)存4GB。

本實驗選用了TPC-C作為測試基準(zhǔn)和數(shù)據(jù)集，TPC-C是專門針對聯(lián)機(jī)交易處理系統(tǒng)（OLTP）的面向事務(wù)處理與數(shù)據(jù)庫性能的測試標(biāo)準(zhǔn)，可在其中模擬比較復(fù)雜并具有代表意義的OLTP應(yīng)用環(huán)境。實驗的比較對象包括另一種典型分布式事務(wù)內(nèi)存系統(tǒng)GenRSTM[10]和MySQL集群。實驗結(jié)果如下。

圖4所示吞吐量實驗中，首先通過CloudSim模擬出了五個數(shù)據(jù)中心，所有節(jié)點隨機(jī)均勻地分布其中，再將TPC-C測試集中的只讀事務(wù)比例設(shè)置為80%。對于MySQL，創(chuàng)建一張包含id和value字段的臨時表，將記錄作為數(shù)據(jù)項存取。從實驗結(jié)果中可看出，三個系統(tǒng)的吞吐量均可隨著節(jié)點數(shù)增多而線性增長，但在以讀任務(wù)為主的環(huán)境下，TMC的優(yōu)勢更為明顯。同時由于日志記錄等磁盤操作的影響，MySQL在讀密集環(huán)境下的吞吐量明顯低于另外兩種事務(wù)內(nèi)存系統(tǒng)。

6 結(jié)束語

在云計算環(huán)境下，存在著大量對數(shù)據(jù)密集型應(yīng)用的需求，傳統(tǒng)的分布并發(fā)式編程模型與數(shù)據(jù)存儲架構(gòu)的不足已日益凸顯，尤其是在需要同時應(yīng)對系統(tǒng)性能、可擴(kuò)展性和數(shù)據(jù)一致性需求的場合下。本文提出了一種基于事務(wù)內(nèi)存與云存儲技術(shù)面向讀密集型應(yīng)用的編程與存儲模型TMC，TMC分為事務(wù)組件與存儲組件兩大模塊，事務(wù)組件在保證數(shù)據(jù)一致性的前提下，允許所有只讀事務(wù)無需遠(yuǎn)程驗證即可順利提交，系統(tǒng)可擴(kuò)展性與可用性則通過存儲組件中的相關(guān)服務(wù)集合實現(xiàn)。以上特性使得TMC適用于對性能、可擴(kuò)展性和數(shù)據(jù)一致性均有嚴(yán)格要求的讀密集型云計算應(yīng)用。

由于受實驗條件和環(huán)境的限制，課題組只對TMC原型進(jìn)行了簡單的仿真模擬實驗，尚未開發(fā)實現(xiàn)完整的可用于生產(chǎn)環(huán)境下的系統(tǒng)。我們計劃在本文工作基礎(chǔ)上，完成對TMC在“云”中的測試，并對其商用化進(jìn)行更加深入的研究與實踐。

參考文獻(xiàn)：

[1] Tim Harris，et al. Transactional Memory： An Overview[J]. IEEEMicro，2007.27（3）：8-29

[2] Jeffrey Dean，Sanjay Ghemawat. MapReduce： simplified dataprocessing on large clusters[J]. Commun.ACM，2008.51（1）：107-113

[3] Avinash Lakshman， Prashant Malik. Cassandra： a decentralizedstructured storage system[J]. SIGOPS Oper. Syst. Rev.，2010.44（2）：35-40

[4] Nicolas Schiper， et al， P-Store：Genuine Partial Replication in WideArea Networks[C]. Proceedings of the 2010 29th IEEE Symposium on Reliable Distributed Systems，2010：214-224

[5] Bieniusa A， Fuhrmann T.Consistency in hindsight： A fully decentralized STM algorithm[C]. Proceedings of the 2010 IEEE International Symposium on Parallel and Distributed Processing，2010：1-12

[6] 徐俊剛，邵佩英.分布式數(shù)據(jù)庫系統(tǒng)及其應(yīng)用（第三版）[M].科學(xué)出版社，2012.

[7] Rachid Guerraoui，et al. Genuine atomic multicast in asynchronousdistributed systems[J]. Theor. Comput. Sci.，2001.254（1-2）：297-316

[8] 林菲，張萬軍，孫勇.一種分布式非結(jié)構(gòu)化數(shù)據(jù)副本管理模型[J].計算機(jī)工程，2013.39（4）：36-38

[9] R.N.Calheiros.CloudSim：a toolkit for modeling and simulation ofcloud computing environments and evaluation of resource provisioning algorithms[R]. NY， USA： Software： Practice and Experience，Wiley Press，2010.

[10] Nuno Carvalho，Generic replication of software transactional memory[C]. Proceedings of the 7th Middleware Doctoral Symposium，Bangalore，India，2010：14-19