自稳定的分布式事务内存模型及算法  

Self Stabilizing Distributed Transactional Memory Model and Algorithms

作　　者：林菲[1] 孙勇[2] 丁宏[1] 任一支[1] 

机构地区：[1]杭州电子科技大学软件工程学院,杭州310018 [2]浙江交通职业技术学院信息学院,杭州311112

出　　处：《计算机研究与发展》2014年第9期2046-2057,共12页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61100194);浙江省自然科学基金项目(LY12F02017);浙江省公益性技术应用研究计划项目(2013C31130;2013C33082)

摘　　要：针对具有瞬时故障的分布式系统,综合考虑系统鲁棒性和可扩展性,提出了一种自稳定的分布式事务内存模型(self-stabilizing distributed transactional memory,SSDTM).首先,利用分层技术和抵押组合理论建立模型框架,并对生成树算法进行了自稳定改进,以克服现有算法只能适应稳定环境的缺点;其次,将数据流技术与自稳定相结合,设计了数据对象操作方法,提高了系统的数据访问局部性;然后,在给出事务服务模型的基础上,提出了基于改进逻辑时钟的SSDTM并发控制算法;最后,结合理论推导,使用4个典型测试用例在SimJava环境下对SSDTM进行了多角度、大规模的分析和性能测试.结果表明,所提算法具有较强的参数鲁棒性和适用性,与其他模型相比,SSDTM具有更高的吞吐量和容错性.Aiming at the issue of transient fault tolerance in distributed system while taking into account the system＇s robustness and scalability,a self-stabilizing distributed transactional memory model,called SSDTM,is proposed.Firstly,the model frame is constructed by layered technology and collateral composition theory,which includes spanning tree layer,objects location layer,transaction proxy layer and application layer.Furthermore,the spanning tree algorithm is improved in selfstabilizing way,which can solve deficiencies of being only adaptive to stable environments based on existing methods.Then,data object manipulation algorithms are designed,which utilize data stream paradigm and self-stabilizing theory for locating objects and enhancing data access locality,and ensure mutually exclusive access to objects in distributed system with transient faults.Moreover,after building the transaction service model that defines the basic types of memory transaction states and operations,the concurrency control algorithms based on the improved logic clock are given.Finally,combining theoretical derivation and instance verification,the performance of SSDTM is verified and analyzed through multi-angle large-scale virtual tests based on 4classical benchmarks in SimJava environment.Experimental results show that the algorithms presented in the paper exhibit good robustness and applicability,and SSDTM has higher system throughput and better fault-tolerance compared with other models under the same conditions.

关 键 词：自稳定 事务内存 瞬时故障 生成树 弹道目标 逻辑时钟 

分 类 号：TP311.2[自动化与计算机技术—计算机软件与理论]