面向内存云的协调器选举策略

doi:10.11772/j.issn.1001-9081.2016.09.2402

计算机应用 ›› 2016, Vol. 36 ›› Issue (9): 2402-2408.DOI: 10.11772/j.issn.1001-9081.2016.09.2402

面向内存云的协调器选举策略

王跃飞^1,2, 于炯^1,2, 鲁亮²

1. 新疆大学软件学院, 乌鲁木齐 830008;
2. 新疆大学信息科学与工程学院, 乌鲁木齐 830046

收稿日期:2016-01-19 修回日期:2016-03-14 出版日期:2016-09-10 发布日期:2016-09-08
通讯作者: 王跃飞
作者简介:王跃飞(1991-),男,新疆乌鲁木齐人,博士研究生,主要研究方向:云计算、分布式计算;于炯(1964-),男,北京人,教授,博士生导师,博士,CCF高级会员,主要研究方向:网络安全、网格计算、分布式计算;鲁亮(1990-),男,新疆乌鲁木齐人,博士研究生,CCF会员,主要研究方向:云计算、分布式计算。
基金资助:
国家自然科学基金资助项目（61262088，61363083，61462079，61562086）。

Coordinator selection strategy based on RAMCloud

WANG Yuefei^1,2, YU Jiong^1,2, LU Liang²

1. School of Software, Xinjiang University, Urumqi Xinjiang 830008, China;
2. School of Information Science and Engineering, Xinjiang University, Urumqi Xinjiang 830046, China

Received:2016-01-19 Revised:2016-03-14 Online:2016-09-10 Published:2016-09-08
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61262088, 61363083, 61462079, 61562086).

摘要/Abstract

摘要： 针对ZooKeeper机制难以满足内存云（RAMCloud）低延迟、快恢复的问题，提出了一种面向内存云的协调器选举策略（CES）。首先根据内存云网络环境与协调器自身因素将协调器性能指标分为个体指标与协调器间指标两类并分别建立模型；然后将内存云的运行分为正常运行期与数据恢复期两阶段并分别建立适应度函数，再按时间比合并为总适应度函数；最后在备选协调器（RBC）的适应度值的基础上提出一个具备稳定择优性与随机性的新算子，CES首先通过筛选来排除性能较差的个体，缩小选择范围后再在理想协调器的集合中采用轮盘赌方法选择最终的个体。实验结果表明，在NS2仿真环境下CES选择的个体相比其他备选协调器数据处理延迟降低了19.35%；在搭建的内存云环境中，与ZooKeeper机制相比，CES的选择结果在快速恢复中时间减少了10.02%。在内存云的实际应用中，CES在处理单点失效问题上能有效选择性能更优的协调器，确保了低延迟、快恢复的要求。

关键词: 内存云, 协调器, 单点失效, 适应度函数, 选举策略

Abstract: Focusing on the issue that ZooKeeper cannot meet the requirement of low latency and quick recovery of RAMCloud, a Coordinator Election Strategy (CES) based on RAMCloud was proposed. First of all, according to the network environment of RAMCloud and factors of the coordinator itself, the performance indexes of coordinator were divided into two categories including individual indexes and coordinator indexes, and models for them were built separately. Next, the operation of RAMCloud was divided into error-free running period and data recovery period, their fitness functions were built separately, and then the two fitness functions were merged into a total fitness function according to time ratio. Lastly, on the basis of fitness value of RAMCloud Backup Coordinator (RBC), a new operator was proposed with randomness and the capacity of selecting an ideal target: CES would firstly eliminate poor-performing RBC by screening, as the range of choice was narrowed, CES would select the ultimate RBC from the collection of ideal coordinators by means of roulette. The experimental results showed that compared with other RBCs in the NS2 simulation environment, the coordinator selected by CES decreased latency by 19.35%; compared with ZooKeeper in the RAMCloud environment, the coordinator selected by CES reduced recovery time by 10.02%. In practical application of RAMCloud, the proposed CES can choose the coordinator with better performance, ensure the demand of low latency and quick recovery.

Key words: RAMCloud, coordinator, single-point failure, fitness function, election strategy

中图分类号:

TP393.02

王跃飞, 于炯, 鲁亮. 面向内存云的协调器选举策略[J]. 计算机应用, 2016, 36(9): 2402-2408.

WANG Yuefei, YU Jiong, LU Liang. Coordinator selection strategy based on RAMCloud[J]. Journal of Computer Applications, 2016, 36(9): 2402-2408.

参考文献

[1] 秦秀磊,张文博,魏峻,等.云计算环境下分布式缓存技术的现状与挑战[J].软件学报,2013,24(1):50-66.(QIN X L, ZHANG W B, WEI J, et al. Progress and challenges of distributed caching techniques in cloud computing[J]. Journal of Software, 2013, 24(1): 50-66.)
[2] 肖侬.数据密集型计算[J].中国计算机学会通讯,2011,7(7):6-7.(XIAO N. Data-intensive computing[J]. Communications of the CCF, 2011,7(7):6-7.)
[3] OUSTERHOUT J, AGRAWAL P, ERICKSON D, et al. The case for RAMClouds: scalable high-performance storage entirely in DRAM [J]. ACM SIGOPS Operating Systems Review, 2010, 43(4): 92-105.
[4] RUMBLE S M, KEJRIWAL A, OUSTERHOUT J. Log-structured memory for DRAM-based storage [C] // Proceedings of the 12th USENIX Conference on File and Storage Technologies. Berkeley, CA: USENIX Association, 2014: 1-16.
[5] OUSTERHOUT J, GOPALAN A, GUPTA A, et al. The RAMCloud storage system [J]. ACM Transactions on Computer Systems, 2015, 33(3): Articl No. 7.
[6] STUTSMAN R, LEE C, OUSTERHOUT J. Experience with rules-based programming for distributed, concurrent, fault-tolerant code [C]// Proceedings of the 2015 USENIX Conference on Usenix Annual Technical Conference. Berkeley, CA: USENIX Association, 2015: 17-30.
[7] TINNEFELD C, KOSSMANN D, GRUND M, et al. Elastic online analytical processing on RAMCloud [C]// Proceedings of the 16th International Conference on Extending Database Technology. New York: ACM, 2013: 454-464.
[8] TINNEFELD C, KOSSMANN D, BOESE J H, et al. Parallel join executions in RAMCloud [C]// Proceedings of the 2014 IEEE 30th International Conference on Data Engineering Workshops. Washington, DC: IEEE Computer Society, 2014: 182-190.
[9] 鲁亮,于炯,英昌甜,等.内存云架构的磁盘节能策略[J].计算机应用,2014,34(9):2518-2522.(LU L,YU J,YING C T, et al. Energy-efficient strategy for disks in RAMCloud[J]. Journal of Computer Applications, 2014, 34(9): 2518-2522.)
[10] 英昌甜,于炯,鲁亮,等.基于小文件的内存云存储优化策略[J].计算机应用,2014,34(11):3104-3108.(YING C T, YU J, LU L, et al. An optimization storing strategy based on small files in RAMCloud [J]. Journal of Computer Applications, 2014, 34(11): 3104-3108.)
[11] RIVETTI N, CORSARO A. State based Paxos[C]// Middleware Industry '13: Proceedings of the Industrial Track of the 13th ACM/IFIP/USENIX International Middleware Conference. New York: ACM, 2013: Article No. 4.
[12] JUNQUEIRA F P, REED B C, SERAFINI M. Zab: high-performance broadcast for primary-backup systems [C]// DSN '11: Proceedings of the 2011 IEEE/IFIP 41st International Conference on Dependable Systems & Networks. Washington, DC: IEEE Computer Society, 2011: 245-256.
[13] RUMBLE S M, ONGARO D, STUTSMAN R, et al. It's time for low latency [C]// Proceedings of the 13th USENIX Conference on Hot Topics in Operating Systems. Berkeley, CA: USENIX Association, 2011: 11.
[14] HUNT P, KONAR 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. Berkeley, CA: USENIX Association, 2010:11.
[15] ONGARO D, RUMBLE S M, STUTSMAN R, et al. Fast crash recovery in RAMCloud [C]// SOSP '11: Proceedings of the 23rd ACM Symposium on Operating Systems Principles. New York: ACM, 2011: 29-41.
[16] BORTHAKUR D. The hadoop distributed file system: architecture and design[EB/OL]. (2007-07-01) [2015-10-05]. http://web.mit.edu/~mriap/hadoop/hadoop-0.13.1/docs/hdfs_design.pdf.
[17] RUMBLE S. Memory and object management in RAMCloud [D]. Stanford: Stanford University, 2014: 5-22.
[18] OUSTERHOUT A J. Undergraduate durability and crash recovery in a distributed in-memory storage system [D]. Stanford: Stanford University, 2013: 17-47.
[19] FREEMAN L C. Centrality in social networks conceptual clarification [J]. Social Networks, 1979, 1(3): 215-239.
[20] 王元卓,于建业,邱雯,等.网络群体行为的演化博弈模型与分析方法[J].计算机学报,2015,38(2):282-300.(WANG Y Z, YU J Y, QIU W, et al. Evolutionary game model and analysis methods for network group behavior [J]. Chinese Journal of Computers, 2015, 38(2): 282-300.)
[21] The Apache Software Foundation. ZooKeeper: because coordinating distributed systems is a zoo [EB/OL].[2015-11-12]. https://zookeeper.apache.org/doc/r3.5.1-alpha/index.pdf.
[22] JUNQUEIRA F P, REED B C. The life and times of a ZooKeeper [C]// PODC '09: Proceedings of the 28th ACM Symposium on Principles of Distributed Computing. New York: ACM, 2009: 4.

面向内存云的协调器选举策略

Coordinator selection strategy based on RAMCloud

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	徐晓强, 秦品乐, 曾建朝. 基于改进粒子群优化算法的牙齿正畸路径规划方法[J]. 计算机应用, 2020, 40(7): 1938-1943.
[2]	王曙燕, 王瑞, 孙家泽. 基于改进细菌觅食算法的测试用例生成方法[J]. 计算机应用, 2019, 39(3): 845-850.
[3]	任智, 田洁丽, 游磊, 吕昱辉. 基于网络协调器高效切换的太赫兹无线个域网接入协议[J]. 计算机应用, 2018, 38(3): 728-733.
[4]	梁冰, 徐华. 基于改进人工蜂群的核模糊聚类算法[J]. 计算机应用, 2017, 37(9): 2600-2604.
[5]	韩明, 刘教民, 吴朔媚, 王敬涛. 粒子群优化的移动机器人路径规划算法[J]. 计算机应用, 2017, 37(8): 2258-2263.
[6]	朱春媚, 莫鸿强. 一类适应度函数的遗传算法编码[J]. 计算机应用, 2017, 37(7): 1972-1976.
[7]	褚征, 于炯, 鲁亮, 英昌甜, 卞琛, 王跃飞. 基于内存云的大块数据对象并行存取策略[J]. 计算机应用, 2016, 36(6): 1526-1532.
[8]	王跃飞, 于炯, 鲁亮. 面向内存云的数据块索引方法[J]. 计算机应用, 2016, 36(5): 1222-1227.
[9]	王宁宁, 鲁燃, 王智昊. 融合标签与人工蜂群的微博推荐算法[J]. 计算机应用, 2016, 36(10): 2789-2793.
[10]	颜宏文, 周雅梅, 潘楚. 基于宽度优先搜索的K-medoids聚类算法[J]. 计算机应用, 2015, 35(5): 1302-1305.
[11]	郭刚, 于炯, 鲁亮, 英昌甜, 尹路通. 内存云分级存储架构下的数据迁移模型[J]. 计算机应用, 2015, 35(12): 3392-3397.
[12]	潘楚罗可. 基于改进粒计算的K-medoids聚类算法[J]. 计算机应用, 2014, 34(7): 1997-2000.
[13]	郑高伟李淼高会议李录久. 协同进化理论及其在施肥模型中的应用[J]. 计算机应用, 2011, 31(06): 1685-1688.
[14]	李丽娟阳琼. 粗糙自适应遗传算法在图像恢复中的应用[J]. 计算机应用, 2011, 31(05): 1230-1232.
[15]	毛宇峰庞永杰. 改进粒子群在水下机器人路径规划中的应用[J]. 计算机应用, 2010, 30(3): 789-792.