ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2014, Vol. 51 ›› Issue (9): 2046-2057.doi: 10.7544/issn1000-1239.2014.20130058

• 软件技术 • 上一篇    下一篇

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

林菲1,孙勇2,丁宏3,任一支1   

  1. 1(杭州电子科技大学软件工程学院 杭州 310018);2(浙江交通职业技术学院信息学院 杭州 311112) (linfei@hdu.edu.cn)
  • 出版日期: 2014-09-01
  • 基金资助: 
    基金项目:国家自然科学基金项目(61100194);浙江省自然科学基金项目(LY12F02017);浙江省公益性技术应用研究计划项目(2013C31130,2013C33082)

Self Stabilizing Distributed Transactional Memory Model and Algorithms

Lin Fei1, Sun Yong2, Ding Hong1, Ren Yizhi1   

  1. 1(School of Software Engineering, Hangzhou Dianzi University, Hangzhou 310018) ;2(Department of Information Technology, Zhejiang Institute of Communications, Hangzhou 311112)
  • Online: 2014-09-01

摘要: 针对具有瞬时故障的分布式系统,综合考虑系统鲁棒性和可扩展性,提出了一种自稳定的分布式事务内存模型(self-stabilizing distributed transactional memory, SSDTM).首先,利用分层技术和抵押组合理论建立模型框架,并对生成树算法进行了自稳定改进,以克服现有算法只能适应稳定环境的缺点;其次,将数据流技术与自稳定相结合,设计了数据对象操作方法,提高了系统的数据访问局部性;然后,在给出事务服务模型的基础上,提出了基于改进逻辑时钟的SSDTM并发控制算法;最后,结合理论推导,使用4个典型测试用例在SimJava环境下对SSDTM进行了多角度、大规模的分析和性能测试.结果表明,所提算法具有较强的参数鲁棒性和适用性,与其他模型相比,SSDTM具有更高的吞吐量和容错性.

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

Abstract: 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 self-stabilizing 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 4 classical 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.

Key words: self stabilization, transactional memory, transient fault, spanning tree, ballistic target, logical clock

中图分类号: