吉林大学学报(工学版) ›› 2017, Vol. 47 ›› Issue (1): 227-234.doi: 10.13229/j.cnki.jdxbgxb201701033

• 论文 • 上一篇    下一篇

基于多管理节点的乐观锁协议

郝娉婷, 胡亮, 姜婧妍, 车喜龙   

  1. 吉林大学 计算机科学与技术学院,长春 130022
  • 收稿日期:2016-06-28 出版日期:2017-01-20 发布日期:2017-01-20
  • 通讯作者: 车喜龙(1982-),男,副教授,博士.研究方向:并行计算,机器学习.E-mail:chexilong@jlu.edu.cn
  • 作者简介:郝娉婷(1990-),女,博士研究生.研究方向:分布式计算,计算机网络.E-mail:susan454@sohu.com
  • 基金资助:
    欧盟第七框架国际合作项目(GA-2011-295222); 国家自然科学基金项目(61073009); 国家科技支撑计划项目(2014BAH02F03); 吉林省青年科学基金项目(20160520011JH).

Optimistic lock protocol of multi-managed nodes

HAO Ping-ting, HU Liang, JIANG Jing-yan, CHE Xi-long   

  1. College of Computer Science and Technology, Jilin University, Changchun 130022, China
  • Received:2016-06-28 Online:2017-01-20 Published:2017-01-20

摘要: 针对悲观锁机制并行性不足的缺点,改进了Zookeeper的悲观锁机制并设计了一种乐观锁协议。通过研究分布式锁机制和Zookeeper的工作原理,提出了一种可以降低总执行时间的乐观锁协议,从理论上与三种不同协议进行了对比和分析,在保证数据一致性的同时,得出乐观锁协议为最优化设计,且对该协议的互斥性、死锁性和公平性加以证明。实验结果表明,乐观锁协议使系统性能有较大幅度提升,并且与其他协议相比,在总执行时间、占有带宽等方面均有一定优势。

关键词: 计算机系统结构, 分布式系统, 分布式锁, 乐观锁, Zookeeper

Abstract: In order to improve the parallelism of pessimistic lock mechanism, an optimistic lock protocol was designed and applied for modifying the original lock mechanism in Zookeeper. By studying the mechanism of distributed lock and the working principle of Zookeeper, the execution time was decreased by the optimistic lock protocol. Theoretically compared with three other protocols, the optimistic lock protocol is the most optimized. Based on ensuring consistency maintenance, the optimistic lock protocol possesses mutual exclusion, non-deadlock and fairness. Simulation results show that the optimistic lock protocol significantly improves the data access performance, and outperforms the other lock protocols in execution time and bandwidth occupancy.

Key words: computer system architecture, distributed system, distributed lock mechanism, optimistic lock, Zookeeper

中图分类号: 

  • TP393
[1] 邵佩英. 分布式数据库系统及其应用[M]. 北京:科学出版社,2005:25-31.
[2] 伍之昂, 曹杰, 王有权. 一种改进的死锁和活锁避免资源联合分配协议[J]. 电子学报, 2011, 39(11): 19-27.
Wu Zhi-ang, Cao Jie, Wang You-quan. An improved deadlock and livelock free protocol for resource co-allocation[J]. Acta Electronica Sinica, 2011, 39(11):19-27.
[3] 钱迎进,肖侬,金士尧. Lustre分布式锁管理器的分析与改进[J]. 计算机工程与科学,2009,31(A01):146-149.
Qian Ying-jin, Xiao Nong, Jin Shi-yao.Analysis and improvement of Lustre distributed lock manager[J]. Computer Engineering & Sci-Ence 2009, 31(A01):146-149.
[4] 李章兵,车乌江. 基于全局目录的分布式数据库加锁管理算法[J]. 计算机技术与发展,2011,21(9):245-250.
Li Zhang-bing, Che Wu-jiang. Locking management algorithm based on global directory in distributed database[J]. Computer Technology and Development, 2011,21(9):245-250.
[5] Carns P, Harms N, Nimpe D, et al. A case for optimistic coordination in HPC storage systems[C]∥High Performance Computing, Networking, Storage and Analysis (SCC),Boston,MA,2012:48-53.
[6] Hunt P, Nonar M, Junqueira F P, et al. Zookeeper: wait-free coordination for internet-scale systems[C]∥Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference, 2010,8:9-23.
[7] Lamport L. Paxos made simple[J].ACM Sigact News, 2001,32(4):18-25.
[8] Narger D, Lehman E, Leighton T, et al. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web[C]∥Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing,EL Paso,TX,1997:654-663.
[9] Lamport L. Time, clocks, and the ordering of events in a distributed system[J].Communications of the ACM, 1978,21(7):558-565.
[10] 刘丹, 刘心松, 丘志杰, 等. 基于读写特征的分布式互斥算法[J]. 电子学报, 2004, 32(2): 326-329.
Liu Dan, Liu Xin-song, Qiu Zhi-jie, et al. A distributed mutual exclusion algorithm based on read/write character[J]. Acta Electronica Sinica, 2004. 32(2):326-329.
[11] Nalantari B, Schiper A. Addressing the Zookeeper Synchronization Inefficiency[M]. Springer Berlin Heidelberg, 2013:434-438.
[12] George Coulouris, Jean Dollimore, Tim Kindberg,et al. Distributed Systems: Concepts and Design[M].5th Ed,USA:Addison-Wesley, 2011:1-16.
[13] 王征,刘心松,李美安. 自适应 Ad hoc 分布式互斥算法[J]. 小型微型计算机系统,2007,28(8):1387-1392.
Wang Zheng, Liu Xin-song, Li Mei-an. Adaptive distributed mutual exclusion algorithm for Ad Hoc networks[J]. Journal of Chinese Computer Systems, 2007, 28(8):1387-1392.
[1] 余宜诚, 胡亮, 迟令, 初剑峰. 一种改进的适用于多服务器架构的匿名认证协议[J]. 吉林大学学报(工学版), 2018, 48(5): 1586-1592.
[2] 董坚峰, 张玉峰, 戴志强. 改进的基于狄利克雷混合模型的推荐算法[J]. 吉林大学学报(工学版), 2018, 48(2): 596-604.
[3] 赵博, 秦贵和, 赵永哲, 杨文迪. 基于半陷门单向函数的公钥密码[J]. 吉林大学学报(工学版), 2018, 48(1): 259-267.
[4] 刘磊, 刘利娟, 吴新维, 张鹏. 基于ECPMR的编译器测试方法[J]. 吉林大学学报(工学版), 2017, 47(4): 1262-1267.
[5] 董立岩, 王越群, 贺嘉楠, 孙铭会, 李永丽. 基于时间衰减的协同过滤推荐算法[J]. 吉林大学学报(工学版), 2017, 47(4): 1268-1272.
[6] 于斌斌, 武欣雨, 初剑峰, 胡亮. 基于群密钥协商的无线传感器网络签名协议[J]. 吉林大学学报(工学版), 2017, 47(3): 924-929.
[7] 邓昌义, 郭锐锋, 张忆文, 王鸿亮. 基于平衡因子的动态偶发任务低功耗调度算法[J]. 吉林大学学报(工学版), 2017, 47(2): 591-600.
[8] 魏晓辉, 刘智亮, 庄园, 李洪亮, 李翔. 支持大规模流数据在线处理的自适应检查点机制[J]. 吉林大学学报(工学版), 2017, 47(1): 199-207.
[9] 魏晓辉, 李翔, 李洪亮, 李聪, 庄园, 于洪梅. 支持大规模流数据处理的弹性在线MapReduce模型及拓扑协议[J]. 吉林大学学报(工学版), 2016, 46(4): 1222-1231.
[10] 车翔玖, 梁森. 一种基于大顶堆的SPIHT改进算法[J]. 吉林大学学报(工学版), 2016, 46(3): 865-869.
[11] 董悦丽, 郭权, 孙斌, 康玲. 药物分子对接动态任务迁移优化[J]. 吉林大学学报(工学版), 2015, 45(4): 1253-1259.
[12] 匡哲君,师唯佳,胡亮. 基于无线传感器网络的角色成员关系剩余能量新算法[J]. 吉林大学学报(工学版), 2015, 45(2): 600-605.
[13] 张忆文,郭锐锋. 实时系统混合任务低功耗调度算法[J]. 吉林大学学报(工学版), 2015, 45(1): 261-266.
[14] 张忆文1, 2, 郭锐锋1. 制的容错节能调度算法[J]. 吉林大学学报(工学版), 2014, 44(4): 1112-1117.
[15] 付帅1, 马建峰1, 李洪涛1, 王长广2. 改进的基于分簇无线传感器网络的数据聚合算法[J]. 吉林大学学报(工学版), 2014, 44(4): 1118-1125.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!