数据网格副本选择策略的研究
摘要
数据网格是网格环境下共享和管理存储资源和分布式数据资源的大规模、可扩展的框架结构，它适应数据密集型应用对网格环境下数据共享和处理的需要，给用户提供了透明访问远程异构数据资源的机制。副本管理是数据网格中一个重要的组成部分，创建的数据副本可以降低远程访问该数据的网络延迟及带宽消耗，还可以提高网络的负载均衡，同时能够提高数据的安全性和可靠性以及系统的容错性等。良好的数据副本管理策略是提高数据网格服务质量的一个重要方面，副本管理策略中包括副本的创建、副本的选择和副本的定位等。其中副本选择是提高系统性能的一个重要环节。本文主要对副本管理策略中的副本选择策略展开了研究，主要做了以下工作：
(1)通过对目前已有的一些副本选择策略的研究，本文改进和扩展了基于拍卖协议和令牌技术的副本选择策略。
①引入了虚拟的概念，分析了虚拟令牌环与令牌环的区别和优势；
②基于虚拟令牌环和拍卖协议的副本选择策略。该策略采用拍卖协议来对众多数据副本进行选择，拍卖时使用令牌技术，由买方发送令牌到虚拟令牌环中，接收到令牌的卖方给出存储在该节点中的副本传送到买方的价格(传输代价)，并根据自己给出价格的大小决定是否修改令牌上的价格，买方根据传回的令牌上的信息，与给出价格最低的卖方建立连接，获取最佳副本。
③给出了最佳副本选择算法。
(2)在分析了存有副本的网格节点的自身情况(如CPU、内存、负载和信誉度等)和各种网络因素(带宽和可靠性等)及其重要性后，提出了一个的“价格”计算模型，该模型可以很好的衡量买方与卖方间的通信代价。可以通过对权重设定不同的值来体现买方侧重于哪些性能指标，这样能够很好的满足买方对性能指标不同要求。同时，还对该计算模型中性能指标的关系对价格的影响进行了评估。
(3)对所提出的副本选择策略在性能上进行了评估。将提出的算法与目前典型的基于轮转模型的副本选择算法进行比较分析，通过设定性能指标，得到两种算法的延时模型，并对两种算法的延时性能进行了仿真。仿真结果表明本文所提出的策略提供了高效查找的副本选择服务。
(4)针对提出的基于拍卖协议和虚拟令牌环技术的副本选择策略，定义了相关的类和方法并对该策略进行了设计与实现。
Data Grid architecture provides a large-scale, scalable infrastructure for the management of storage resources and data that are distributed across grid environments. Based on the requirement to data sharing and managing of data-intensive computing application, it provides the mechanisms for transparently remote accessing to heterogeneous data resources. Replica management is one of the critical parts in data grids. The replica created could reduce the network delay and bandwidth consumes when accessing to the data and improves load balance of network. It could also improve security, reliability and system tolerance of the data. Excellent replica management strategies are important to improve the QoS in data grids. Replica management strategies include replicas creation strategies, replicas selection strategies and replica location mechanism and so on. Replica selection strategies are an important tache in improving performance of the system. This paper investigates on replica selection strategies of replica management in data grids and the main work are as follows:
(1) This paper improves and expands a replica selection strategy based on auction agreement and token technology by studying some replica selection strategies exist.
(1)We import the concept of virtual and analysis the difference between virtual token-ring and token-ring.
(2)We improve and extend a replica selection strategy based on auction agreement and virtual token-ring. This strategy selects a data replica from many replicas using auction protocols and token technology. Purchaser sent token to virtual token-ring. Bargainer receiving the token gives a price from it to the purchaser. Bargainer will decide whether modify the price on the token according to the price on the token. Purchaser will connect with bargainer who gives the lowest price and get the best replica according the information on the token.
(3)This paper gives the arithmetic of purchaser and bargainer.
(2) This paper puts forward a price calculating model after analyzing the situation of the node storing the replica, the factor of the network and their essentiality. This model could well weigh the communication cost between the purchaser and bargainer. We can also set different weight to emphasize particularly on different performance index which could satisfy the requirement of different purchasers. We also evaluate the affection that the performance index to the price.
(3) This paper evaluates the performance of the replica selection strategy put forward. Comparing with the representative Robin selection strategy at present and set the performance index, we get two algorithmic delay models. We also emulate the delay performance of the two algorithmic models. We draw the conclusion that the strategy put forward provides an efficient search replica selection services.
(4) This paper defines correlative class and agreement and also design and realized in allusion to the replica selection strategy based on auction protocol and virtual token-ring technology.
(1)通过对目前已有的一些副本选择策略的研究，本文改进和扩展了基于拍卖协议和令牌技术的副本选择策略。
①引入了虚拟的概念，分析了虚拟令牌环与令牌环的区别和优势；
②基于虚拟令牌环和拍卖协议的副本选择策略。该策略采用拍卖协议来对众多数据副本进行选择，拍卖时使用令牌技术，由买方发送令牌到虚拟令牌环中，接收到令牌的卖方给出存储在该节点中的副本传送到买方的价格(传输代价)，并根据自己给出价格的大小决定是否修改令牌上的价格，买方根据传回的令牌上的信息，与给出价格最低的卖方建立连接，获取最佳副本。
③给出了最佳副本选择算法。
(2)在分析了存有副本的网格节点的自身情况(如CPU、内存、负载和信誉度等)和各种网络因素(带宽和可靠性等)及其重要性后，提出了一个的“价格”计算模型，该模型可以很好的衡量买方与卖方间的通信代价。可以通过对权重设定不同的值来体现买方侧重于哪些性能指标，这样能够很好的满足买方对性能指标不同要求。同时，还对该计算模型中性能指标的关系对价格的影响进行了评估。
(3)对所提出的副本选择策略在性能上进行了评估。将提出的算法与目前典型的基于轮转模型的副本选择算法进行比较分析，通过设定性能指标，得到两种算法的延时模型，并对两种算法的延时性能进行了仿真。仿真结果表明本文所提出的策略提供了高效查找的副本选择服务。
(4)针对提出的基于拍卖协议和虚拟令牌环技术的副本选择策略，定义了相关的类和方法并对该策略进行了设计与实现。
Data Grid architecture provides a large-scale, scalable infrastructure for the management of storage resources and data that are distributed across grid environments. Based on the requirement to data sharing and managing of data-intensive computing application, it provides the mechanisms for transparently remote accessing to heterogeneous data resources. Replica management is one of the critical parts in data grids. The replica created could reduce the network delay and bandwidth consumes when accessing to the data and improves load balance of network. It could also improve security, reliability and system tolerance of the data. Excellent replica management strategies are important to improve the QoS in data grids. Replica management strategies include replicas creation strategies, replicas selection strategies and replica location mechanism and so on. Replica selection strategies are an important tache in improving performance of the system. This paper investigates on replica selection strategies of replica management in data grids and the main work are as follows:
(1) This paper improves and expands a replica selection strategy based on auction agreement and token technology by studying some replica selection strategies exist.
(1)We import the concept of virtual and analysis the difference between virtual token-ring and token-ring.
(2)We improve and extend a replica selection strategy based on auction agreement and virtual token-ring. This strategy selects a data replica from many replicas using auction protocols and token technology. Purchaser sent token to virtual token-ring. Bargainer receiving the token gives a price from it to the purchaser. Bargainer will decide whether modify the price on the token according to the price on the token. Purchaser will connect with bargainer who gives the lowest price and get the best replica according the information on the token.
(3)This paper gives the arithmetic of purchaser and bargainer.
(2) This paper puts forward a price calculating model after analyzing the situation of the node storing the replica, the factor of the network and their essentiality. This model could well weigh the communication cost between the purchaser and bargainer. We can also set different weight to emphasize particularly on different performance index which could satisfy the requirement of different purchasers. We also evaluate the affection that the performance index to the price.
(3) This paper evaluates the performance of the replica selection strategy put forward. Comparing with the representative Robin selection strategy at present and set the performance index, we get two algorithmic delay models. We also emulate the delay performance of the two algorithmic models. We draw the conclusion that the strategy put forward provides an efficient search replica selection services.
(4) This paper defines correlative class and agreement and also design and realized in allusion to the replica selection strategy based on auction protocol and virtual token-ring technology.
引文
[1] 郁志辉，陈渝，刘鹏．网格计算[M]．北京：清华出版社，2002年11月
[2] Ian Foster,Carl Kesselman. The Grid:Blueprint for a New Computing Infrastructure[M]. Morgan Kaufmann, 1999
[3] Ian. Foster, Carl. Kesselman. The Grid[J]. 北京：电子工业出版社，2004-1，Pp224-262.
[4] I. Foster, C. Kesselman. The Grid:Blueprint for a New Computing Infrastructure [M]. Morgan Kaufman,2003
[5] I. Foster, C. Kesselman, S. Tuecke. The Anatomy of the Grid: Enabling Scalable Virtual Organizations [J]. International J. Supercomputer application, 2001. 15(3):200-222
[6] 何戈，徐志伟，数据网格技术研究[J]．微电子学与计算机，2003年4期：Pp3-4
[7] 吴豪，曾国荪，张季平．数据网格关键技术分析[J]．计算机工程与应用，2003年35期：Pp60-61
[8] 王意洁，肖侬，任浩，等．数据网格及其关键技术研究[J]．计算机研究与发展，2002年8期：Pp943-946
[9] M Baldonado, C Chang, L Gravano et al. The stanford digital library metadata architecture[J]. International Journal Digital Libraries. 1997,1 (2):pages: 108～121
[10] W Allcock, A Chervenak, I Foster et al. The data grid:Towards an architecture for the distributed management and analysis of large scientific datasets[J]. Network and Computer Applications,2000,23 (3):pages: 187～200
[11] Ian Foster, Carl Kesselman et al. Globus: A Metaeomputing Infrastructure Toolkit[J]. International Journal of Surpercomputer Applications, 1997, 11(2): P115-128
[12] Wo lfgang Ho schek, Javier Jaen2M artinez. Datamanagement in an international data grid project. In: ACM Int'lWork shop on Grid Computing (Grid'2000). Bangalore, India, 2000. 17-20
[13] M.Cai, A.Chervenak, M.Frank. A Peer-to-Peer Replica Location Service Based on A Distributed Hash Table[C], in Proceedings of the SC2004 Conference (SC2004), November
[14] Chaitanya Baru, Reagan Moore, Arcot Rajasekar et al. The SDSC storage resource broker[C]. In: Proc CA SCON'98 Conference. Toronto, Canada, 1998
[15] Ann Chervenak, Ewa Deelman, Ian Foster et al. Giggle:A Framework for Constructing Scalable Replica Location Services[C].In Proc. of the Int'l. IEEE Supercomputing Conference (SC 2002), Baltimore, USA, November 2002
[16] Freenet Home Page. http://Freenet, sourceforge.Net
[17] 曹鸿强，肖侬，卢锡城，等．一种基于市场机制的计算网格资源分配方法[J]．计算机研究与发展，2002．39(8)：Pp9132-9161
[18] Sudha Krishnamurthy, William H Sanders, Michel Cukier. Performance Evaluation of a Probabilistic Replica Selection Algorithm [C]. Proceeding of the 7th International Workshop on Object2Oriented Real-time Dependable Systems, 2002
[19] Yong Zhao, Yu Hul. GRESS: A Grid Replica Selection Service[Z]
[20] Sudharshan. Vazhkudai, Steven Tuecke, Ian Foster. Replica Selection in the Globus Data Grid. http://www.globus.org/research/papers.html/Data Grid.
[21] Y.Hu. IBL for replica selection in data intensive Grid applications. Master's Thesis, Department of Computer Science, University of Chicago, 2003.
[22] Sudharshan, Vazhkudai, Jennifer M. Schopf. Using Disk Throughput Data in Predictions of End-to-End Grid Data Transfer[J]. Proceedings of Grid 2002, Page:291-304,2002.
[23] Faerman M. Su, R. Wolski, F.Berman. Adaptive Performance Prediction for Distributed Data-Intensive Applications[C]. Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), 1999
[24] Baru C., R. Moore, A. Rajasekar et al. The SDSC Storage Resource Broker[C]. Proceedings of IBM Centers for Advanced Studies Conference, 1998
[25] Deron Liang, S. C.Chon, S .M.Yuan. A fault-tolerant object service in OMG's Object Management architecture [J]. Information and Software Technology, 1998 39(14/15): Page:965-973
[26] Jurgen Nehmer, Friedmann Mathern. Framework for the organization of cooperative services in distributed client-service systems [J]. Computer Communication, 1992, 15(4):261-269.
[27] Guy L, Kunszt P, Laure E. Replica Management in Data Grids[R]. Technical Report, Global Grid Forum-GGFS, Edinburgh, Scotland, July 2002
[28] The Globus Data Management Grop. A Replica Management Service for High-Performance Data Grids. Jan 2001
[29] 王茜，数据网格中的副本定位及选择服务：[硕士学位论文]．重庆：重庆大学计算机软件与理论，2006
[30] 闫晓东，徐惠民．一种可扩展的分布式副本定位方法[J]．北京邮电大学学报，2005年3期：Pp46-48
[31] Sudharshan Vazhkudai, Steven Tuccke, Ian Fosterl Replica Selection in the Globus Data Grid [C]. IEEE International Symposium on Cluster Computing and the Grid, 2001
[32] 孙海燕，数据网格副本管理关键技术研究：[硕士学位论文]．长沙：国防科学技术大学计算机科学与技术，2005
[33] The Globus Alliance. Http://www.globus.org
[34] 白雪柏．数据网格中副本管理服务原形系统的设计与实现：[硕士学位论文]．西安：西安交通大学，2004
[35] Mcafee R, Mcmillan J. Auction and bidding [J]. Journal of Economic Literature, 1987.25(6):699-738
[36] 章志明．电子拍卖协议的研究与实现：[硕士学位论文]．江西：江西师范大学计算机信息工程学院，2005
[37] Network Weather Service. http://nws.cs.ucsb.edu/ewiki/
[38] 郝继红，陈鸣，赵洪华，等．NWS预测子系统的应用[J]．解放军理工大学学报(自然科学版)，2004年6期：Pp1-3
[39] 赵新娟，刘伟．动态自适应网格资源管理模型研究[J]．计算机工程与设计，2004年6期：Pp：905-908
[40] WOLSKIR. Dynamically forecasting network performance to support dynamic scheduling using the network weather service [A]. In: Proceedings of 6th High-Performance Distributed Computing [C]. Portland: IEEE Inc, 1997.
[41] 胡亮，郭冰心，郭东．基于NWS模型的Windows平台CPU可用性预测系统[J]．计算机工程与应用，2006年6期：Pp94-97
[42] 申婷，基于令牌的单点登录协议及应用：[硕士学位论文]．西安：西安电子科技大学通信与信息系统，2006
[43] 游新冬，数据网格中的副本管理策略研究：[硕士学位论文]．辽宁省：东北大学计算机软件与理论，2005
[2] Ian Foster,Carl Kesselman. The Grid:Blueprint for a New Computing Infrastructure[M]. Morgan Kaufmann, 1999
[3] Ian. Foster, Carl. Kesselman. The Grid[J]. 北京：电子工业出版社，2004-1，Pp224-262.
[4] I. Foster, C. Kesselman. The Grid:Blueprint for a New Computing Infrastructure [M]. Morgan Kaufman,2003
[5] I. Foster, C. Kesselman, S. Tuecke. The Anatomy of the Grid: Enabling Scalable Virtual Organizations [J]. International J. Supercomputer application, 2001. 15(3):200-222
[6] 何戈，徐志伟，数据网格技术研究[J]．微电子学与计算机，2003年4期：Pp3-4
[7] 吴豪，曾国荪，张季平．数据网格关键技术分析[J]．计算机工程与应用，2003年35期：Pp60-61
[8] 王意洁，肖侬，任浩，等．数据网格及其关键技术研究[J]．计算机研究与发展，2002年8期：Pp943-946
[9] M Baldonado, C Chang, L Gravano et al. The stanford digital library metadata architecture[J]. International Journal Digital Libraries. 1997,1 (2):pages: 108～121
[10] W Allcock, A Chervenak, I Foster et al. The data grid:Towards an architecture for the distributed management and analysis of large scientific datasets[J]. Network and Computer Applications,2000,23 (3):pages: 187～200
[11] Ian Foster, Carl Kesselman et al. Globus: A Metaeomputing Infrastructure Toolkit[J]. International Journal of Surpercomputer Applications, 1997, 11(2): P115-128
[12] Wo lfgang Ho schek, Javier Jaen2M artinez. Datamanagement in an international data grid project. In: ACM Int'lWork shop on Grid Computing (Grid'2000). Bangalore, India, 2000. 17-20
[13] M.Cai, A.Chervenak, M.Frank. A Peer-to-Peer Replica Location Service Based on A Distributed Hash Table[C], in Proceedings of the SC2004 Conference (SC2004), November
[14] Chaitanya Baru, Reagan Moore, Arcot Rajasekar et al. The SDSC storage resource broker[C]. In: Proc CA SCON'98 Conference. Toronto, Canada, 1998
[15] Ann Chervenak, Ewa Deelman, Ian Foster et al. Giggle:A Framework for Constructing Scalable Replica Location Services[C].In Proc. of the Int'l. IEEE Supercomputing Conference (SC 2002), Baltimore, USA, November 2002
[16] Freenet Home Page. http://Freenet, sourceforge.Net
[17] 曹鸿强，肖侬，卢锡城，等．一种基于市场机制的计算网格资源分配方法[J]．计算机研究与发展，2002．39(8)：Pp9132-9161
[18] Sudha Krishnamurthy, William H Sanders, Michel Cukier. Performance Evaluation of a Probabilistic Replica Selection Algorithm [C]. Proceeding of the 7th International Workshop on Object2Oriented Real-time Dependable Systems, 2002
[19] Yong Zhao, Yu Hul. GRESS: A Grid Replica Selection Service[Z]
[20] Sudharshan. Vazhkudai, Steven Tuecke, Ian Foster. Replica Selection in the Globus Data Grid. http://www.globus.org/research/papers.html/Data Grid.
[21] Y.Hu. IBL for replica selection in data intensive Grid applications. Master's Thesis, Department of Computer Science, University of Chicago, 2003.
[22] Sudharshan, Vazhkudai, Jennifer M. Schopf. Using Disk Throughput Data in Predictions of End-to-End Grid Data Transfer[J]. Proceedings of Grid 2002, Page:291-304,2002.
[23] Faerman M. Su, R. Wolski, F.Berman. Adaptive Performance Prediction for Distributed Data-Intensive Applications[C]. Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), 1999
[24] Baru C., R. Moore, A. Rajasekar et al. The SDSC Storage Resource Broker[C]. Proceedings of IBM Centers for Advanced Studies Conference, 1998
[25] Deron Liang, S. C.Chon, S .M.Yuan. A fault-tolerant object service in OMG's Object Management architecture [J]. Information and Software Technology, 1998 39(14/15): Page:965-973
[26] Jurgen Nehmer, Friedmann Mathern. Framework for the organization of cooperative services in distributed client-service systems [J]. Computer Communication, 1992, 15(4):261-269.
[27] Guy L, Kunszt P, Laure E. Replica Management in Data Grids[R]. Technical Report, Global Grid Forum-GGFS, Edinburgh, Scotland, July 2002
[28] The Globus Data Management Grop. A Replica Management Service for High-Performance Data Grids. Jan 2001
[29] 王茜，数据网格中的副本定位及选择服务：[硕士学位论文]．重庆：重庆大学计算机软件与理论，2006
[30] 闫晓东，徐惠民．一种可扩展的分布式副本定位方法[J]．北京邮电大学学报，2005年3期：Pp46-48
[31] Sudharshan Vazhkudai, Steven Tuccke, Ian Fosterl Replica Selection in the Globus Data Grid [C]. IEEE International Symposium on Cluster Computing and the Grid, 2001
[32] 孙海燕，数据网格副本管理关键技术研究：[硕士学位论文]．长沙：国防科学技术大学计算机科学与技术，2005
[33] The Globus Alliance. Http://www.globus.org
[34] 白雪柏．数据网格中副本管理服务原形系统的设计与实现：[硕士学位论文]．西安：西安交通大学，2004
[35] Mcafee R, Mcmillan J. Auction and bidding [J]. Journal of Economic Literature, 1987.25(6):699-738
[36] 章志明．电子拍卖协议的研究与实现：[硕士学位论文]．江西：江西师范大学计算机信息工程学院，2005
[37] Network Weather Service. http://nws.cs.ucsb.edu/ewiki/
[38] 郝继红，陈鸣，赵洪华，等．NWS预测子系统的应用[J]．解放军理工大学学报(自然科学版)，2004年6期：Pp1-3
[39] 赵新娟，刘伟．动态自适应网格资源管理模型研究[J]．计算机工程与设计，2004年6期：Pp：905-908
[40] WOLSKIR. Dynamically forecasting network performance to support dynamic scheduling using the network weather service [A]. In: Proceedings of 6th High-Performance Distributed Computing [C]. Portland: IEEE Inc, 1997.
[41] 胡亮，郭冰心，郭东．基于NWS模型的Windows平台CPU可用性预测系统[J]．计算机工程与应用，2006年6期：Pp94-97
[42] 申婷，基于令牌的单点登录协议及应用：[硕士学位论文]．西安：西安电子科技大学通信与信息系统，2006
[43] 游新冬，数据网格中的副本管理策略研究：[硕士学位论文]．辽宁省：东北大学计算机软件与理论，2005