一种移动数据库的自适应缓存管理机制
|
摘要
随着无线通信技术和移动设备的飞速发展,移动环境日益成熟,移动计算成为一个新兴的热点研究领域。研究移动数据库技术,即支持移动环境的分布式数据库技术,已成为目前分布式数据库研究的一个新的方向。在移动数据库的关键技术中,缓存技术具有非常重要的地位,移动数据库的一个主要的目标就是要保证移动用户在断接情况下对数据的有效访问。因此,在客户端缓存经常存取的数据是一项提高移动环境性能的有效技术。
融合移动数据库的缓存与广播技术,建立了一种缓存与广播相结合的系统结构。该系统结构分为固定网络和无线网络两部分。固定网络,即连接固定设备的网络,连接着若干个服务器及本地移动支持站MSS。本地MSS负责连接广播服务器与移动客户机通信;无线网络,即移动设备组成的网络,无线网络中的移动客户机通过本地MSS与广播服务器通信,来维护缓存数据与服务器端数据的一致性。
在分析传统的基于失效报告的缓存失效机制的基础上,提出了一种移动数据库的自适应缓存管理机制(ACMS),通过在时间戳上引入计数器来记录向服务器提出请求的移动客户机数目。在服务器端,可以根据存取数据的移动客户机的数目,动态调整失效报告的内容及广播间隔,发送给移动客户机;在客户端,移动客户机根据接收到的内容,通过接收到的时间戳及时间间隔值来判断缓存中的内容是否有效,修改缓存的状态,从而实现缓存的动态管理。
对提出的机制,通过仿真实验进行了评估,实验结果表明这种方法能更有效地适应移动环境中网络带宽不足、上下行链路的不对称性及网络的频繁断接性等特点,有效地提高带宽利用率,从而提高移动环境下缓存的效率,提高移动数据库数据的可用性、一致性。
With the development of the wireless communication technology and mobile devices, the mobile environment increasingly mature, and mobile computing has become a hot research topic today. The research on mobile database technology that also called distributed databases technology which supports the mobile computing environment has become a new direction of the distributed database. Cache technology is one key technology of mobile database. One main object of mobile database is to ensure the validity of accessed data under disconnection. So caching of frequently accessed data at the mobile clients is an effective technology to improve mobile environmental performance.
A new model is presented on the basis of cache and data broadcast, which includes two parts: the fixed network and the wireless network. The fixed network, connecting the fixed devices, includes several broadcast server and Home Mobile Support Station. The MSS is responsible for connecting the broadcast server and mobile clients. The wireless network, composed of mobile devices, enables mobile clients communicating with the broadcast server by MSS to maintain data consistency between cache and the server.
A new adaptive cache management scheme (ACMS) for mobile database is proposed by analysis of the traditional cache invalidation mechanisms based on invalidation reports. In this mechanism, by utilizing a counter on the basis of the timestamps to record the number of mobile clients requesting to the server; at the server side, dynamically adjust the contents of invalidation reports and broadcast interval in accordance with the number of mobile clients accessing the data, and send to mobile clients; at the client side, the mobile clients judge the validity of the contents in cache by the timestamps and broadcast interval, and amend the state of cache so as to implement the dynamic management of the cache.
The proposed algorithm is evaluated by experimental simulation, results show that this method can adapt to the characteristics of the mobile environment much more effectively, such as the deficiency bandwidth, the asymmetry of up-down-stream link, and the frequent disconnect of the network, and effective improve the bandwidth utilization, thereby enhancing the efficiency of the cache technology, data availability and consistency of mobile database.
融合移动数据库的缓存与广播技术,建立了一种缓存与广播相结合的系统结构。该系统结构分为固定网络和无线网络两部分。固定网络,即连接固定设备的网络,连接着若干个服务器及本地移动支持站MSS。本地MSS负责连接广播服务器与移动客户机通信;无线网络,即移动设备组成的网络,无线网络中的移动客户机通过本地MSS与广播服务器通信,来维护缓存数据与服务器端数据的一致性。
在分析传统的基于失效报告的缓存失效机制的基础上,提出了一种移动数据库的自适应缓存管理机制(ACMS),通过在时间戳上引入计数器来记录向服务器提出请求的移动客户机数目。在服务器端,可以根据存取数据的移动客户机的数目,动态调整失效报告的内容及广播间隔,发送给移动客户机;在客户端,移动客户机根据接收到的内容,通过接收到的时间戳及时间间隔值来判断缓存中的内容是否有效,修改缓存的状态,从而实现缓存的动态管理。
对提出的机制,通过仿真实验进行了评估,实验结果表明这种方法能更有效地适应移动环境中网络带宽不足、上下行链路的不对称性及网络的频繁断接性等特点,有效地提高带宽利用率,从而提高移动环境下缓存的效率,提高移动数据库数据的可用性、一致性。
With the development of the wireless communication technology and mobile devices, the mobile environment increasingly mature, and mobile computing has become a hot research topic today. The research on mobile database technology that also called distributed databases technology which supports the mobile computing environment has become a new direction of the distributed database. Cache technology is one key technology of mobile database. One main object of mobile database is to ensure the validity of accessed data under disconnection. So caching of frequently accessed data at the mobile clients is an effective technology to improve mobile environmental performance.
A new model is presented on the basis of cache and data broadcast, which includes two parts: the fixed network and the wireless network. The fixed network, connecting the fixed devices, includes several broadcast server and Home Mobile Support Station. The MSS is responsible for connecting the broadcast server and mobile clients. The wireless network, composed of mobile devices, enables mobile clients communicating with the broadcast server by MSS to maintain data consistency between cache and the server.
A new adaptive cache management scheme (ACMS) for mobile database is proposed by analysis of the traditional cache invalidation mechanisms based on invalidation reports. In this mechanism, by utilizing a counter on the basis of the timestamps to record the number of mobile clients requesting to the server; at the server side, dynamically adjust the contents of invalidation reports and broadcast interval in accordance with the number of mobile clients accessing the data, and send to mobile clients; at the client side, the mobile clients judge the validity of the contents in cache by the timestamps and broadcast interval, and amend the state of cache so as to implement the dynamic management of the cache.
The proposed algorithm is evaluated by experimental simulation, results show that this method can adapt to the characteristics of the mobile environment much more effectively, such as the deficiency bandwidth, the asymmetry of up-down-stream link, and the frequent disconnect of the network, and effective improve the bandwidth utilization, thereby enhancing the efficiency of the cache technology, data availability and consistency of mobile database.
引文
[1]Imielinski T,Korth H.editors,Mobile computing,Kluwer Academic Publishers,1996.
[2]Margaret H.Dunham,Abdelsalam Helal.Mobile Computing and Database:anything newACM SIGMOD Record,1995,24(4):5-9.
[3]D.Barbara and T.Imielinski,Sleepers and workaholics:Caching in mobile distributed environments,in:Proceedings of the 1994 ACM-SIGMOD International Conference on Management of Data(June 1994)pp.1-12.
[4]A.Kahol,S.Khurana,S.K.S.Gupta,and P.K.Srimani,"A Strategy to Manage Cache Consistency in a Distributed Mobile Wireless Environment," IEEE Trans.Parallel and Distributed Systems,vol.12,no.7,pp.686-700,July 2001.
[5]Panos K.Chrysanthis.Transaction Processing in Mobile Computing Environment.IEEE on Advances in Parallel and Distributed Systems,1993,11(10):77-82.
[6]D.Barabara and T.Imielinski,"Sleepers and Workaholic:Caching Strategies in Mobile Environments," VLDB Journal,4,567-602,1995
[7]Panos K.Chrysanthis.Transaction Processing in Mobile Computing Environment.IEEE on Advances in Parallel and Distributed Systems,1993,11(10):77-82.
[8]周桓,移动环境中的Cache技术研究.博士学位论文,中国科学院软件研究所,2001.
[9]孟小峰,周龙骧,王珊.数据库技术发展趋势[J].软件学报,2004,15(12).
[10]D.Agrawal and A.EI Abbadi:The Tree Quorum technique:An Efficient Approach for Managing Replicated Data.In:Very Large Data Bases,2002.243-254.
[11]Sybase Corp.Sybase SQL Anywhere and Replication Server:the Enterprise-wide Replication Solution,1997.45-70.
[12]王珊,丁治明,张孝.移动数据库及其应用,计算机应用,2000,20(9).
[13]E.Pitoura and B.Bhargava,"Maintaining Consistency of Data in Mobile Distributed Environments".Proc.Of International Conference on Distributed Computing Systems,pp.404-413,1995.
[14]J.Cai,K.L.Tan and B.C Ooi,On incremental cache coherency schemes in mobile computing environment,in:Proceedings of the 13th International Conference on Data Engineering(April 1997)pp.114-123.
[15]Walborn G,Chrysanthis P K.PRO-MOTION:Support for Mobile Database Access.Personal Technologies,1997,1(3):171-181.
[16]Franklin M.J,Caching and memory management in Client-server database systems,PhD thesis,University of Wisconsin-Madison,1993.
[17]Y.Chan,Antonio Si,Hong V.Leong.Cache Management for Mobile Databases:Design and Evaluation ",In Proceedings of 14th Int.Conf.on Data Eng.,Feb,23-27,1998,Orlando Florida,pp.54-63.
[18]J Ⅱ Young Cbung and Chong-Sun Hwang," Transactional Cache Management with Aperiodic Invalidation Scheme 'in Mobile Environments ",Advances in Computing science,pp.50-61,1999.
[19]A.Kahol,S.Khurana,S.Gupta and P.Srimani,An efficient cache management scheme for mobile environment,in:The 20th Int.Conf.On Distributed Computing Systems(April 2000)pp.530-537.
[20]K.Lee,C.S.Hwang and H.C.Yu,"Supporting Transactional Cache Consistency in Mobile Database Systems," Proc.of ACM MobiDE,Seattle,WA,1999.
[21]Z.Wang,et al,"SACCS:Scalable Asynchronous Cache Consistency Scheme for Mobile Environments," Proc.Of Workshop on Mobile and Wireless Networks,2003.
[22]陈婵颖,薛贺,王良家,牛艳芳.缓存技术在移动数据库中的应用研究[J].计算机工程与设计,2006,27(9).
[23]M.J.Franklin,M.J.Carey and M.Livny,"Transactional Client-Server Cache Consistency:Alternatives and Performance ",ACM Transactional on Database Systems,Vol.22,No.3,pp.3 15-363,1997.
[24]G.Y.Liu and G.Q.McGuire Jr.,"A Mobility-Aware Dynamic Database Caching Scheme for Wireless Mobile Computing and Communications," Distributed and Parallel Databases,vol.4,no.5,pp.271-288,1996.
[25]Basu J.Associative Caching in Client-Server Databases:[PhD Dissertation][D]1Stanford University,1998.
[26]Sang Keun Lee,Chong-Sun Hwang,and HeonCbangYu,"Caching and Concurrency Control in Mobile Client Server Database Systems",Cooperative Databases and Applications,pp.227-238,1999.
[27]Cedric C.F.Fong,John C.S.Lui and M.H.Wong.Distributed Caching and Broadcast in a Wireless Mobile Computing Environment.The Computer Journal 1999,42(6):455-472.
[28]Aksoy D.,Altinel M.,Bose R.,Cetintemel U.,Franklin M.,Wang J.,and Zdonik S.,"Research in Data Broadcast and Dissemination",In Proc.of AMCP,LNCS,1554:194-207,1999.
[29]K.Stathatos,N.Roussopoulos,and J.Barns,"Adaptive Data Broadcast in Hybrid Networks," Proc.of the 23rdVLDB Conf.,1997.
[30]Jung-Ho Ahn,Hyoung-Joo Kim,SEOF:An Adaptable Object Prefetch policy for Object-Oriented Database Systems.ICDE 1997:4-13.
[31]罗军,陈洪波.基于异步数据广播技术的移动数据库缓存策略.计算机工程,2005,31(24).
[32]H.W.Leung:Concurrency Control for Data Broadcasts in Mobile Computing Systems.In:Department of Computer Science,City University of Hong Kong.2001.201-212.
[33]S.Acharya,M.Franklin,S.Zdonik:Dessemination-based Data Delivery Using Broadcast Disks.In:IEEE Personal Communications.2001.228-293.
[34]Acharya S.,Alonso R.,Franklin M.and Zdonik S.,"Broadcast Disks:Data Management for Asymmetric Communication Environments",In Proc.of ACM Sigmod,pp.199-210,1995.
[35]W.Lee,Q.Hu,and D.Lee,"A Study on Channel Allocation for Data Dissemination in Mobile Computing Environments," A CM//Baltzer Mobile Networks and Applications,pages 117-129,1999.
[36]G.Cao,"A Scalable Low Latency Cache Invalidation Strategy for Mobile Environments," Proc.of ACMMOBICOM,Boston,MA,2000.
[37]吴劲,卢显良,任立勇,周旭.移动计算环境中缓存失效策略的归类研究法.计算机科学,2004,31(1).
[38]Zaharioudakis M,Carey M,Highly concurrent cache consistency for indices in client-server database systems,In:ACM,SOGMOD International Conf on Management of Data,1995.
[39]J.C.Yuen,E.Chan,K.Lam,and H.W.Leung,"Cache Invalidation Scheme for Mobile Computing Systems with Real-Time Data," SIGMOD Record,Dec.2000.
[40]苏斐,慈林林,梁野.基于自适应数据广播的缓存一致性维护.北京理工大学学报,2005,25(9).
[41]Qinglong Hu,Dik Lun Lee:Adaptive Cache Invalidation Methods in Mobile Environments.HPDC 1997:264-273.
[42]J.Jing,A.Elmagarmid,A.Heal,R.Alonso,"Bit-Sequences:An Adaptive Cache Invalidation Method in Mobile Client/Server Environments," Mobile Networks and Applications,vol.2,no.2,pp.115-127,1997.
[43]Chung YII,Hwang C S.Transactional Cache Management with Aperiodic Invalidation Scheme in Mobile Environments[C]//In:Proceedings of the 5th Asian Computing Science Conference on Advances in Computing Science.London:Springer-Verlag,1999:50-61.
[44]Q.Hu and D.K.Lee,"Cache Algorithms Based on Adaptive Invalidation Reports for Mobile Environments," Cluster Computing,vol.1,no.1,pp.39-50,1998.
[45]G.Cao,"On Improving the Performance of Cache Invalidation in Mobile Environments," Mobile Networks and Applications,vol.7,pp.291-303,2002.
[46]K.L.Tan and J.Cai,Broadcast-based group invalidation:An energy efficient cache invalidation scheme,Information Sciences 100(1-4)(August 1997)229-254.
[47]J.Cai and K.L.Tan,Energy-Efficient Selective Cache Invalidation,Wireless Networks,vol.5,no.6,pp.489-502,1999.
[48]K.L.Wu,P.S.Yu and M.S.Chen,Energy-efficient caching for wireless mobile computing,in:Proceedings of the 12th International Conference on Data Engineering(February 1996)pp.336-343.
[49]K.Tan,J.Cai and B.Ooi,"An Evaluation of Cache Invalidation Strategies in Wireless Environments" IEEETPDS,vol.12,no.8,pp.789-807,Aug.2001.
[2]Margaret H.Dunham,Abdelsalam Helal.Mobile Computing and Database:anything newACM SIGMOD Record,1995,24(4):5-9.
[3]D.Barbara and T.Imielinski,Sleepers and workaholics:Caching in mobile distributed environments,in:Proceedings of the 1994 ACM-SIGMOD International Conference on Management of Data(June 1994)pp.1-12.
[4]A.Kahol,S.Khurana,S.K.S.Gupta,and P.K.Srimani,"A Strategy to Manage Cache Consistency in a Distributed Mobile Wireless Environment," IEEE Trans.Parallel and Distributed Systems,vol.12,no.7,pp.686-700,July 2001.
[5]Panos K.Chrysanthis.Transaction Processing in Mobile Computing Environment.IEEE on Advances in Parallel and Distributed Systems,1993,11(10):77-82.
[6]D.Barabara and T.Imielinski,"Sleepers and Workaholic:Caching Strategies in Mobile Environments," VLDB Journal,4,567-602,1995
[7]Panos K.Chrysanthis.Transaction Processing in Mobile Computing Environment.IEEE on Advances in Parallel and Distributed Systems,1993,11(10):77-82.
[8]周桓,移动环境中的Cache技术研究.博士学位论文,中国科学院软件研究所,2001.
[9]孟小峰,周龙骧,王珊.数据库技术发展趋势[J].软件学报,2004,15(12).
[10]D.Agrawal and A.EI Abbadi:The Tree Quorum technique:An Efficient Approach for Managing Replicated Data.In:Very Large Data Bases,2002.243-254.
[11]Sybase Corp.Sybase SQL Anywhere and Replication Server:the Enterprise-wide Replication Solution,1997.45-70.
[12]王珊,丁治明,张孝.移动数据库及其应用,计算机应用,2000,20(9).
[13]E.Pitoura and B.Bhargava,"Maintaining Consistency of Data in Mobile Distributed Environments".Proc.Of International Conference on Distributed Computing Systems,pp.404-413,1995.
[14]J.Cai,K.L.Tan and B.C Ooi,On incremental cache coherency schemes in mobile computing environment,in:Proceedings of the 13th International Conference on Data Engineering(April 1997)pp.114-123.
[15]Walborn G,Chrysanthis P K.PRO-MOTION:Support for Mobile Database Access.Personal Technologies,1997,1(3):171-181.
[16]Franklin M.J,Caching and memory management in Client-server database systems,PhD thesis,University of Wisconsin-Madison,1993.
[17]Y.Chan,Antonio Si,Hong V.Leong.Cache Management for Mobile Databases:Design and Evaluation ",In Proceedings of 14th Int.Conf.on Data Eng.,Feb,23-27,1998,Orlando Florida,pp.54-63.
[18]J Ⅱ Young Cbung and Chong-Sun Hwang," Transactional Cache Management with Aperiodic Invalidation Scheme 'in Mobile Environments ",Advances in Computing science,pp.50-61,1999.
[19]A.Kahol,S.Khurana,S.Gupta and P.Srimani,An efficient cache management scheme for mobile environment,in:The 20th Int.Conf.On Distributed Computing Systems(April 2000)pp.530-537.
[20]K.Lee,C.S.Hwang and H.C.Yu,"Supporting Transactional Cache Consistency in Mobile Database Systems," Proc.of ACM MobiDE,Seattle,WA,1999.
[21]Z.Wang,et al,"SACCS:Scalable Asynchronous Cache Consistency Scheme for Mobile Environments," Proc.Of Workshop on Mobile and Wireless Networks,2003.
[22]陈婵颖,薛贺,王良家,牛艳芳.缓存技术在移动数据库中的应用研究[J].计算机工程与设计,2006,27(9).
[23]M.J.Franklin,M.J.Carey and M.Livny,"Transactional Client-Server Cache Consistency:Alternatives and Performance ",ACM Transactional on Database Systems,Vol.22,No.3,pp.3 15-363,1997.
[24]G.Y.Liu and G.Q.McGuire Jr.,"A Mobility-Aware Dynamic Database Caching Scheme for Wireless Mobile Computing and Communications," Distributed and Parallel Databases,vol.4,no.5,pp.271-288,1996.
[25]Basu J.Associative Caching in Client-Server Databases:[PhD Dissertation][D]1Stanford University,1998.
[26]Sang Keun Lee,Chong-Sun Hwang,and HeonCbangYu,"Caching and Concurrency Control in Mobile Client Server Database Systems",Cooperative Databases and Applications,pp.227-238,1999.
[27]Cedric C.F.Fong,John C.S.Lui and M.H.Wong.Distributed Caching and Broadcast in a Wireless Mobile Computing Environment.The Computer Journal 1999,42(6):455-472.
[28]Aksoy D.,Altinel M.,Bose R.,Cetintemel U.,Franklin M.,Wang J.,and Zdonik S.,"Research in Data Broadcast and Dissemination",In Proc.of AMCP,LNCS,1554:194-207,1999.
[29]K.Stathatos,N.Roussopoulos,and J.Barns,"Adaptive Data Broadcast in Hybrid Networks," Proc.of the 23rdVLDB Conf.,1997.
[30]Jung-Ho Ahn,Hyoung-Joo Kim,SEOF:An Adaptable Object Prefetch policy for Object-Oriented Database Systems.ICDE 1997:4-13.
[31]罗军,陈洪波.基于异步数据广播技术的移动数据库缓存策略.计算机工程,2005,31(24).
[32]H.W.Leung:Concurrency Control for Data Broadcasts in Mobile Computing Systems.In:Department of Computer Science,City University of Hong Kong.2001.201-212.
[33]S.Acharya,M.Franklin,S.Zdonik:Dessemination-based Data Delivery Using Broadcast Disks.In:IEEE Personal Communications.2001.228-293.
[34]Acharya S.,Alonso R.,Franklin M.and Zdonik S.,"Broadcast Disks:Data Management for Asymmetric Communication Environments",In Proc.of ACM Sigmod,pp.199-210,1995.
[35]W.Lee,Q.Hu,and D.Lee,"A Study on Channel Allocation for Data Dissemination in Mobile Computing Environments," A CM//Baltzer Mobile Networks and Applications,pages 117-129,1999.
[36]G.Cao,"A Scalable Low Latency Cache Invalidation Strategy for Mobile Environments," Proc.of ACMMOBICOM,Boston,MA,2000.
[37]吴劲,卢显良,任立勇,周旭.移动计算环境中缓存失效策略的归类研究法.计算机科学,2004,31(1).
[38]Zaharioudakis M,Carey M,Highly concurrent cache consistency for indices in client-server database systems,In:ACM,SOGMOD International Conf on Management of Data,1995.
[39]J.C.Yuen,E.Chan,K.Lam,and H.W.Leung,"Cache Invalidation Scheme for Mobile Computing Systems with Real-Time Data," SIGMOD Record,Dec.2000.
[40]苏斐,慈林林,梁野.基于自适应数据广播的缓存一致性维护.北京理工大学学报,2005,25(9).
[41]Qinglong Hu,Dik Lun Lee:Adaptive Cache Invalidation Methods in Mobile Environments.HPDC 1997:264-273.
[42]J.Jing,A.Elmagarmid,A.Heal,R.Alonso,"Bit-Sequences:An Adaptive Cache Invalidation Method in Mobile Client/Server Environments," Mobile Networks and Applications,vol.2,no.2,pp.115-127,1997.
[43]Chung YII,Hwang C S.Transactional Cache Management with Aperiodic Invalidation Scheme in Mobile Environments[C]//In:Proceedings of the 5th Asian Computing Science Conference on Advances in Computing Science.London:Springer-Verlag,1999:50-61.
[44]Q.Hu and D.K.Lee,"Cache Algorithms Based on Adaptive Invalidation Reports for Mobile Environments," Cluster Computing,vol.1,no.1,pp.39-50,1998.
[45]G.Cao,"On Improving the Performance of Cache Invalidation in Mobile Environments," Mobile Networks and Applications,vol.7,pp.291-303,2002.
[46]K.L.Tan and J.Cai,Broadcast-based group invalidation:An energy efficient cache invalidation scheme,Information Sciences 100(1-4)(August 1997)229-254.
[47]J.Cai and K.L.Tan,Energy-Efficient Selective Cache Invalidation,Wireless Networks,vol.5,no.6,pp.489-502,1999.
[48]K.L.Wu,P.S.Yu and M.S.Chen,Energy-efficient caching for wireless mobile computing,in:Proceedings of the 12th International Conference on Data Engineering(February 1996)pp.336-343.
[49]K.Tan,J.Cai and B.Ooi,"An Evaluation of Cache Invalidation Strategies in Wireless Environments" IEEETPDS,vol.12,no.8,pp.789-807,Aug.2001.