Page 22 - 《软件学报》2021年第10期

2994 Journal of Software 软件学报 Vol.32, No.10, October 2021

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

Hadoop 是提供分布式存储和计算的一套开源软件系统 [1,2] ,通过多年的发展,Hadoop 已经成为分布式存储
计算领域事实上的行业标准,得到了广泛的应用.Hadoop 分布式文件系统(Hadoop distributed file system,简称
[3]
HDFS)是为 Hadoop 提供文件存储支撑的重要组成部分,是谷歌文件系统(Google file system) 的开源实现,它能
够基于普通商用机器集群,提供高吞吐量、高可靠性及高可用性的存储服务.
HDFS 的设计目标主要有两方面:一是最大化系统吞吐率,二是提供可靠、高可用的服务.根据 CAP 定理
[4]
(CAP theorem) ,系统在一致性(consistency,即所有节点在同一时间访问相同数据的特性)、可用性(availability,
即保证请求能收到回应的特性)和分区容忍度(partition tolerance,即在信息丢失或部分节点失效的情况下继续
提供服务的特性)这 3 种特性上必须做出取舍,不可能同时满足.HDFS 为了达到设计目标,优先满足可用性,其次
考虑分区容忍度,牺牲了一致性 [5,6] .
HDFS 的弱一致性具有重要的研究价值,因为它不能保证在同一时刻不同节点访问相同数据,这会给使用
系统服务的上层应用带来设计的复杂性.为了在进行应用开发时对数据不一致进行恰当的处理,就必须深入理
解 HDFS 的一致性模型.
为了研究 HDFS 的数据一致性,必须要克服如下 3 个技术难点:首先,HDFS 系统规模庞大,如何将与一致性
分析相关的代码筛选出来是一个难点;其次,作为分布式系统,HDFS 是由位于不同服务器上的多个组件组成的,
节点自身需要完成哪些工作、需要响应哪些请求、节点之间如何进行消息传递、如何进行协同操作,是分析分
布式系统的重点问题;最后,分布式系统难以验证,如何建模系统状态并进行一致性检查,是一项巨大的挑战.
[7]
为了解决以上问题,本文基于着色 Petri 网 实现了 HDFS 数据一致性分析.研究对象为 hadoop-1.0.1,代码
包为 org.apache.hadoop.hdfs,共包含 182 个 Java 文件,33 965 行 Java 代码,文献[7]中的数据结构建模及读写流程
建模均与此代码相对应.研究过程如下:(1) 通过阅读源码对写文件和读文件两个流程中的重要的数据结构、本
[8]
地操作以及系统组件之间的协作进行分析;(2) 使用 CPN Tools 建立着色 Petri 网模型,准确刻画 HDFS 在数据
一致性方面的算法流程;(3) 使用 CPN Tools 的状态空间分析工具进行数据一致性分析.本文分析的目标是寻找
HDFS 系统不一致状态的发生条件及其后果,思路是用模型模拟系统的运行,并分析各中间结果的状态.
本文关注两种层面的一致性场景:(1) 数据层的一致性,即关注每个状态下同一份数据的多个副本之间是
否一致;(2) 操作层的一致性,即关注当同时有多个客户端并发读一份数据时,是否能读到相同的数据.研究方式
为暂停所有写操作的流程,并执行多个读操作,比较这些读操作返回结果是否一致.
本文的主要贡献包括:
(1) 使用着色 Petri 网对 HDFS 的读写流程建立模型.详细刻画了 HDFS 内部各个组件的功能及相互协作
的机制;
(2) 使用状态空间工具分析了 HDFS 的数据层一致性和操作层一致性.提出面向一致性分析的数据模型
简化方法,在满足一致性检验要求的前提下简化模型;提出“时点重复读”的操作层一致性判定方法;
(3) 使用 CPN Tools 对实际系统进行了完整的分析,分析了 HDFS 存在的一致性问题,对上层应用开发提
出了实用的建议,可以增强上层应用的一致性,并且为分析其他分布式系统的一致性提供了可参考的
方法.
本文第 1 节介绍相关工作,包括 HDFS 系统建模、着色 Petri 网和 CPN Tools.第 2 节分析 HDFS 的核心数
据结构并对其建模.第 3 节介绍 HDFS 的读写文件流程,并详细介绍了建模网络结构.第 4 节介绍状态空间工具
集的功能,使用该工具集对 HDFS 的一致性进行分析,从数据层一致性和操作层一致性这两个维度,分别在无错