面向讀密集型應用的事務內存云研究

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

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

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

0 引言

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

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

1 相關工作

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

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

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

2 系統建模

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

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

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

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

3 事務組件

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

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

3.1 內存事務的讀寫操作

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

4 存儲組件

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

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

4.1 存儲組件的擴展性

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

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

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

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

4.2 數據一致性

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

5 實驗

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

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

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

6 結束語

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

由于受實驗條件和環境的限制，課題組只對TMC原型進行了簡單的仿真模擬實驗，尚未開發實現完整的可用于生產環境下的系統。我們計劃在本文工作基礎上，完成對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] 徐俊剛，邵佩英.分布式數據庫系統及其應用（第三版）[M].科學出版社，2012.

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

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