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

乔嘉林 等:基于着色 Petri 网的 HDFS 数据一致性建模与分析 3007

Fig.14 Reading/writing process model of HDFS
图 14 HDFS 读写模型
4 系统一致性分析

本文研究的一致性包括两个层面:数据层一致性和操作层一致性.如果任意时刻存储在多个节点上的数据
副本完全相同,则称系统满足数据层一致性.如果任意时刻多次读同一数据返回的结果是完全相同的,则称系统
满足操作层一致性.每个层面的一致性分析都包括两种情况:文件块被正确写入磁盘和存在(由网络传输超时、
节点失效、磁盘故障等引起的)本地写文件块失败.本文分别称这两种情况为无错情况和有错情况.
4.1 分析工具介绍

我们首先介绍 Petri 网的状态.Petri 网的状态由令牌在库所的分布决定,一个确定的分布即为一个状态.
Petri 网的状态空间表达了系统运行时所有可能的状态的集合,本文用来分析系统的一致性.我们使用 CPN
Tools 中的状态空间计算工具计算上述 HDFS 模型的状态空间.CPN Tools 提供了一套基于状态空间分析的工
具,包括网络状态空间计算、状态空间报告、状态图生成、状态空间查询等.使用这些工具能够很容易地生成
状态空间并作进一步分析,对研究系统一致性提供了有力的支持.
下面通过一个简单的着色 Petri 网模型为例,来介绍状态空间工具使用的方法.模型如图 15 所示,该图有两
条路径:一是触发 T1,使令牌进入 P3 库所;二是依次触发 T2、T3,使令牌进入 P3 库所.

Fig.15 An example of state space
图 15 状态空间样例

使用 CPN Tools 提供的状态空间计算工具,能够计算网络的全部状态空间.图 15 的状态图如图 16 所示,该
状态图包括 3 个状态节点.状态节点显示的内容包括:状态节点编号、该状态节点下所有库所中容纳的令牌信
息.弧显示的内容包括:弧编号、该弧对应的状态变迁所触发的变迁以及触发条件.在状态图中对库所和变迁的