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

關鍵詞： 讀密集； 事務內存； 云計算； 數(shù)據副本； 一致性

中圖分類號：TP302 文獻標志碼：A 文章編號：1006-8228（2014）02-11-04

0 引言

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

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

1 相關工作

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

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

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

2 系統(tǒng)建模

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

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

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

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

3 事務組件

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

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

3.1 內存事務的讀寫操作

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

4 存儲組件

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

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

4.1 存儲組件的擴展性

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

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

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

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

4.2 數(shù)據一致性

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

5 實驗

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

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

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

6 結束語

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

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

參考文獻：

[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ù)據庫系統(tǒng)及其應用（第三版）[M].科學出版社，2012.

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

[8] 林菲，張萬軍，孫勇.一種分布式非結構化數(shù)據副本管理模型[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