Page 21 - 《软件学报》2021年第10期
P. 21
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(10):29933013 [doi: 10.13328/j.cnki.jos.006026] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563
基于着色 Petri 网的 HDFS 数据一致性建模与分析
1
1
1
1
乔嘉林 , 黄向东 , 杨义繁 , 王建民 , 吴 凯 2
1
(清华大学 软件学院 大数据研究中心,北京 100084)
2
(新疆金风科技股份有限公司,新疆 乌鲁木齐 830026)
通讯作者: 黄向东, E-mail: huangxdong@tsinghua.edu.cn
摘 要: HDFS 分布式文件系统作为 Apache Hadoop 的核心组件之一,在工业界得到了广泛应用.HDFS 采用了多
副本机制保证数据的可靠性,但是由于多副本的存在,在节点失效、网络中断、写入失败时可能会导致数据不一致.
与传统文件系统相比,HDFS 被认为其数据一致性有所降低,但用户并不知道何时会出现不一致的情况,目前也没有
相关工作对其一致性机制进行验证说明.当数据存在一致性问题时,会增加上层应用的不确定性.可见,对数据一致
性的研究十分必要.HDFS的软件规模庞大,且在分布式环境下运行,针对这些特点,采用了着色Petri网建模和状态空
间分析的方法,完成了以下工作:(1) 使用着色 Petri 网对 HDFS 的读写流程建立模型,该模型详细刻画了 HDFS 内部
各个组件的功能及相互协作的机制;(2) 基于着色 Petri 网模型,使用状态空间工具分析了 HDFS 的数据层一致性和
操作层一致性,验证并详细说明了 HDFS 出现不一致的条件;(3) 在分析过程中,提出了“时点重复读”的操作层一致
性验证方法,采用串行化的重复读策略降低了状态空间复杂度.基于以上工作,针对HDFS上层应用的开发给出建议,
帮助提高应用的数据一致性.此外,在建模过程中提出的建模技巧给基于 CPN Tools 工具分析其他系统提供了借鉴.
关键词: HDFS;一致性;建模;着色 Petri 网;CPN Tools
中图法分类号: TP311
中文引用格式: 乔嘉林,黄向东,杨义繁,王建民,吴凯.基于着色 Petri 网的 HDFS 数据一致性建模与分析.软件学报,2021,32
(10):29933013. http://www.jos.org.cn/1000-9825/6026.htm
英文引用格式: Qiao JL, Huang XD, Yang YF, Wang JM, Wu K. HDFS data consistency modelling and analysis based on
colored Petri net. Ruan Jian Xue Bao/Journal of Software, 2021,32(10):29933013 (in Chinese). http://www.jos.org.cn/1000-
9825/6026.htm
HDFS Data Consistency Modelling and Analysis Based on Colored Petri Net
1
1
1
1
QIAO Jia-Lin , HUANG Xiang-Dong , YANG Yi-Fan , WANG Jian-Min , WU Kai 2
1
(School of Software, Tsinghua University, Beijing 100084, China)
2
(Xinjiang GoldWind Sci & Tech Co., Ltd., Urumqi 830026, China)
Abstract: As one of the core components of Apache Hadoop, the Hadoop distributed file system (HDFS) has been widely used in the
industry. HDFS adopts a multiple replicas mechanism to ensure data reliability, which may incur inconsistency because of node failure,
network partition, and write failure. HDFS is considered to have reduced data consistency compared to traditional file systems, which is
difficult for users to understand when there will be inconsistent. At present, there is no relevant work to verify the consistency mechanism.
When the data is inconsistent, it will increase the uncertainty of the upper applications. Thus, research for data consistency model is
required. The large scale of HDFS makes the analysis more difficult. Code reading, abstracting, colored Petri net modeling, and
state-space analysis are conducted to comprehend the system. The works are listed as the following. (1) Colored petri nets are used to
model HDFS’s process of reading and writing files, the model describes the functions of inner components and their cooperation
基金项目: 国家自然科学基金(71690231, 61802224)
Foundation item: National Natural Science Foundation of China (71690231, 61802224)
收稿时间: 2018-11-14; 修改时间: 2019-07-02, 2019-09-16, 2020-01-18; 采用时间: 2020-02-27
