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

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

 使用着色 Petri 网工具 CPN Tools 对 HDFS 的读写流程建立模型,该模型是一个无时序的着色 Petri 网
模型,详细刻画了 HDFS 内部各个组件——名字节点、数据节点和客户端的内部数据结构、核心功能
及相互协作的机制;
 基于着色 Petri 网模型,使用状态空间工具分析了 HDFS 的数据层一致性和操作层一致性.如果任意时
刻存储在多个节点上的数据副本完全相同,则称系统满足数据层一致性.如果任意时刻多次读同一数
据返回的结果是完全相同的,则称系统满足操作层一致性.针对每一种一致性要求,都在无错条件和有
错条件下展开状态空间分析,对不一致状态的产生原因及演化方向进行了详细的分析,明确了系统在
各种条件下提供的一致性保障,本文研究包含了所有可能产生不一致的条件;
 本文以副本一致性为例,对 HDFS 系统进行了分析.如果需要对 HDFS 系统的其他细节进行分析,则可
以进行类似的建模.例如:如果需要进行 HDFS 的可用性、吞吐性能等分析,可以将本模型作为建模基
础,修改或增加相关的模型元素和状态空间的检验方法,实现对其他特性的分析.此外,尽管本文是针对
HDFS 进行建模,但是本文的工作思路同样适用于其他分布式系统,具有较强的普适性.
后续研究工作包含两个方向:(1) 本文提出了一种在应用层避免读取数据不一致的解决方法,可以本文建
模为基础,进一步分析 HDFS 中是否可以通过优化系统读写流程来提供一致的数据读取,为上层应用提供便
利;(2) 本文的建模方法和技巧可以作为参考,应用到其他系统的建模分析工作中,尤其适用于对其他分布式系
统的数据一致性进行建模,如分析 NoSQL 数据库的最终一致性等.

References:
[1] Hadoop. 2014. http://hadoop.apache.org/
[2] Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters. Communications of the ACM, 2008,51(1):
107113.
[3] Ghemawat S, Gobioff H, Leung ST. The Google file system. ACM SIGOPS Operating Systems Review, 2003,37(5).
[4] Brewer EA. Towards robust distributed systems. In: Proc. of the PODC. 2000.
[5] Motamari P. Snapshotting in Hadoop distributed file system for hadoop open platform as service [MS. Thesis]. KTH, 2014.
[6] Hakimzadeh K, Sajjad HP, Dowling J. Scaling HDFS with a strongly consistent relational model for metadata. In: Proc. of the IFIP
Int’l Conf. on Distributed Applications and Interoperable Systems. Berlin, Heidelberg: Springer-Verlag, 2014. 3851.
[7] Jensen K. Coloured Petri nets and the invariant-method. Theoretical Computer Science, 1981,14(3):317336.
[8] Ratzer VA, et al. CPN tools for editing, simulating, and analysing coloured Petri nets. In: Proc. of the Applications and Theory of
Petri Nets. 2003. 450462.
[9] Chen M, Mao SW, Liu YH. Big data: A survey. In: Proc. of the Mobile Networks and Applications. 2014. 139.
[10] Hadoop Wiki: Applications and organizations using hadoop. 2014. http://wiki.apache.org/hadoop/PoweredBy
[11] Valerio J, et al. Evaluating the price of consistency in distributed file storage services. In: Proc. of the Distributed Applications and
Interoperable Systems. 2013. 141154.
[12] Borthakur D, et al. Apache Hadoop goes realtime at Facebook. In: Proc. of the 2011 ACM SIGMOD Int’l Conf. on Management of
Data. ACM, 2011.
[13] Huang XD, Wang JM, Qiao JL, Zheng LF, Zhang JR, Wong RK. Performance and replica consistency simulation for quorum-based
NoSQL system Cassandra. In: Proc. of the Petri Nets. 2017. 7898.
[14] Osman R, Piazzolla P. Modelling replication in NoSQL datastores. In: Proc. of the QEST. 2014. 194209.
[15] Dipietro S, Casale G, Serazzi G. A queueing network model for performance prediction of apache Cassandra. In: Proc. of the
VALUETOOLS. 2016.
[16] Wang F, Lei BH. Research on the service-aware model of NGN architecture and key technologies. Telecommunications Science,
2010(12):9599 (in Chinese with English abstract).
[17] Wu YW, et al. Modeling of distributed file systems for practical performance analysis. IEEE Trans. on Parallel and Distributed
Systems, 2014,25(1):156166.