| 摘要: |
| HDFS分布式文件系统作为Apache Hadoop的核心组件之一，在工业界得到了广泛应用.HDFS采用了多副本机制保证数据的可靠性，但是由于多副本的存在，在节点失效、网络中断、写入失败时可能会导致数据不一致.与传统文件系统相比，HDFS被认为其数据一致性有所降低，但用户并不知道何时会出现不一致的情况，目前也没有相关工作对其一致性机制进行验证说明.当数据存在一致性问题时，会增加上层应用的不确定性.可见，对数据一致性的研究十分必要.HDFS的软件规模庞大，且在分布式环境下运行，针对这些特点，采用了着色Petri网建模和状态空间分析的方法，完成了以下工作：（1）使用着色Petri网对HDFS的读写流程建立模型，该模型详细刻画了HDFS内部各个组件的功能及相互协作的机制；（2）基于着色Petri网模型，使用状态空间工具分析了HDFS的数据层一致性和操作层一致性，验证并详细说明了HDFS出现不一致的条件；（3）在分析过程中，提出了“时点重复读”的操作层一致性验证方法，采用串行化的重复读策略降低了状态空间复杂度.基于以上工作，针对HDFS上层应用的开发给出建议，帮助提高应用的数据一致性.此外，在建模过程中提出的建模技巧给基于CPN Tools工具分析其他系统提供了借鉴. |
| 关键词: HDFS 一致性 建模 着色Petri网 CPN Tools |
| DOI：10.13328/j.cnki.jos.006026 |
| 分类号:TP311 |
| 基金项目:国家自然科学基金（71690231，61802224） |
|
| HDFS Data Consistency Modelling and Analysis Based on Colored Petri Net |
|
QIAO Jia-Lin1, HUANG Xiang-Dong1, YANG Yi-Fan1, WANG Jian-Min1, WU Kai2
|
|
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 mechanism in detail. (2) Data layer consistency and operation layer consistency of HDFS are analyzed with state-space tools based on a colored Petri net model, figuring out data consistency guaranteed by the system. (3) A time point repeatable read method is proposed to verify operation layer consistency and serial repeatable strategy is utilized to decrease state-space complexity. Based on the contribution above, the directions for HDFS application development are proposed, helping to improve the data consistency. The CPN modeling method and technique are applicated in the analysis of other distributed information systems. |
| Key words: HDFS consistency modelling colored Petri net CPN tools |
