D-SQL分布式数据库系统的启动与恢复
|
摘要
随着数据库应用需求的拓展和计算机硬件环境，特别是网络技术的发展，分布式数据库系统应运而生，并成为计算机技术最活跃的研究领域之一。
分布式数据库系统通常包括以下几个部分：用户接口子系统、目录结构管理子系统、编译子系统、分布式事务管理和并发控制子系统、数据执行子系统、通讯子系统、恢复子系统、数据库。其中，恢复子系统是分布式数据库系统中保证数据库系统满足各种应用不可缺少的重要组成部分。它负责分布式数据库系统的启动与恢复过程，并针对任何可能出现的故障，提供相应的恢复措施，自动将数据库从故障状态恢复到一个已知的正常状态，并继续提供正常的数据库服务。
分布式数据库系统的启动与恢复是一个非常复杂的过程，在此过程中，分布式数据库系统不仅要初始化整个数据库系统，还需要按照一定的算法自动收集各结点信息，构造数据库目录，并通过恢复子系统将各结点数据库依照数据库目录恢复到一致的正常状态。
本文在对分布式数据库系统的深入研究的基础上，实现了D-SQL分布式数据库系统的启动与恢复，并提出了一种新的分布式数据库系统检查点和日志恢复机制，该算法无论在设置检查点过程中，还是在日志恢复过程中，均不会影响正常结点向用户提供数据库服务。从而避免了传统的全局检查点日志恢复算法中为建立全局检查点而停止数据库服务所付出的巨大代价，在正确有效地实现分布式数据库系统的启动与恢复的前提下保证了分布式数据库系统的高可用性，使日志恢复算法在分布式数据库中更为实用。
目前，对分布式数据库系统的研究很多，但是对分布式数据库系统的启动与恢复的理论和技术探讨相对较少，本课题对分布式数据库系统的启动和恢复进行了深入研究，并实现于D-SQL，为该领域的发展提供了一定的理论数据和实践经验。
本文第一章回顾了分布式数据库的历史和发展状况；第二章介绍了分布式数据库系统的启动与恢复过程；第三章介绍了D-SQL的系统结构；第四章介绍了D-SQL启动过程的设计与实现；第五章介绍了D-SQL的分布式恢复技术；第六章详细介绍了D-SQL独特的日志恢复与检查点算法及实现技术；第七章对D-SQL的性能进行了分析；最后，第八章总结全文，并对以后的研究作出了展望。
Alonging with the extensive application of distributed database system and the improvement of the computer and network technology, distributed database system (DDBS) has become an important field of information processing.
A distributed database system consists of user interface subsystem, directory management subsystem, compile subsystem, distributed transaction management and concurrency control subsystem, data implement system, recovery subsystem etc. And recovery subsystem is generally accepted as an essential part of distributed database system. It takes charge the startup and recovery process of distributed database system and makes sure that fault database site could recover from fault state to guarantee the consistence of the database.
The startup and recovery process is very complex in distributed database system. When the process begins, recovery subsystem initializes the whole distributed database system, then collects node information to create database directory, and rebuilds the consistent database according to the database directory.
On the basis of deeply researching in distributed database system, this paper designs and implements the startup and recovery process of distributed database system D-SQL. Especially, a new algorithm of log recovery based on consistent global checkpoint in distributed database is presented in this paper. In the algorithm, neither checkpointing nor recovering will affect other normal database activities, which guarantees the availability of distributed database.
The paper is organized as follows. Section 1 overviews the history of distributed database. Section 2 introduces the startup and recovery process of distributed database system. Section 3 describes the structure of D-SQL. Section 4 presents the implementation of startup process in D-SQL. Section 5 shows the design of recovery process in D-SQL. Section 6 introduces the new definition of consistent global checkpoint, then derives the algorithm and provides the proof of correctness. Section 7 discusses the performance of D-SQL. Finally, Section 8 concludes the paper.
分布式数据库系统通常包括以下几个部分：用户接口子系统、目录结构管理子系统、编译子系统、分布式事务管理和并发控制子系统、数据执行子系统、通讯子系统、恢复子系统、数据库。其中，恢复子系统是分布式数据库系统中保证数据库系统满足各种应用不可缺少的重要组成部分。它负责分布式数据库系统的启动与恢复过程，并针对任何可能出现的故障，提供相应的恢复措施，自动将数据库从故障状态恢复到一个已知的正常状态，并继续提供正常的数据库服务。
分布式数据库系统的启动与恢复是一个非常复杂的过程，在此过程中，分布式数据库系统不仅要初始化整个数据库系统，还需要按照一定的算法自动收集各结点信息，构造数据库目录，并通过恢复子系统将各结点数据库依照数据库目录恢复到一致的正常状态。
本文在对分布式数据库系统的深入研究的基础上，实现了D-SQL分布式数据库系统的启动与恢复，并提出了一种新的分布式数据库系统检查点和日志恢复机制，该算法无论在设置检查点过程中，还是在日志恢复过程中，均不会影响正常结点向用户提供数据库服务。从而避免了传统的全局检查点日志恢复算法中为建立全局检查点而停止数据库服务所付出的巨大代价，在正确有效地实现分布式数据库系统的启动与恢复的前提下保证了分布式数据库系统的高可用性，使日志恢复算法在分布式数据库中更为实用。
目前，对分布式数据库系统的研究很多，但是对分布式数据库系统的启动与恢复的理论和技术探讨相对较少，本课题对分布式数据库系统的启动和恢复进行了深入研究，并实现于D-SQL，为该领域的发展提供了一定的理论数据和实践经验。
本文第一章回顾了分布式数据库的历史和发展状况；第二章介绍了分布式数据库系统的启动与恢复过程；第三章介绍了D-SQL的系统结构；第四章介绍了D-SQL启动过程的设计与实现；第五章介绍了D-SQL的分布式恢复技术；第六章详细介绍了D-SQL独特的日志恢复与检查点算法及实现技术；第七章对D-SQL的性能进行了分析；最后，第八章总结全文，并对以后的研究作出了展望。
Alonging with the extensive application of distributed database system and the improvement of the computer and network technology, distributed database system (DDBS) has become an important field of information processing.
A distributed database system consists of user interface subsystem, directory management subsystem, compile subsystem, distributed transaction management and concurrency control subsystem, data implement system, recovery subsystem etc. And recovery subsystem is generally accepted as an essential part of distributed database system. It takes charge the startup and recovery process of distributed database system and makes sure that fault database site could recover from fault state to guarantee the consistence of the database.
The startup and recovery process is very complex in distributed database system. When the process begins, recovery subsystem initializes the whole distributed database system, then collects node information to create database directory, and rebuilds the consistent database according to the database directory.
On the basis of deeply researching in distributed database system, this paper designs and implements the startup and recovery process of distributed database system D-SQL. Especially, a new algorithm of log recovery based on consistent global checkpoint in distributed database is presented in this paper. In the algorithm, neither checkpointing nor recovering will affect other normal database activities, which guarantees the availability of distributed database.
The paper is organized as follows. Section 1 overviews the history of distributed database. Section 2 introduces the startup and recovery process of distributed database system. Section 3 describes the structure of D-SQL. Section 4 presents the implementation of startup process in D-SQL. Section 5 shows the design of recovery process in D-SQL. Section 6 introduces the new definition of consistent global checkpoint, then derives the algorithm and provides the proof of correctness. Section 7 discusses the performance of D-SQL. Finally, Section 8 concludes the paper.
引文
1．C.J.Date著，孟小峰等泽。2000。数据库系统导论。北京：机械工业出版社
2．王珊，陈红等。pbase体系结构与并行性。计算机学报1996年03期。
3．许向阳，冯玉才。并行数据库pdbms的设计与实现。计算机工程与应用1999年11期。
4．王于同。并行数据库性能研究。计算机工程与应用1997年01期。
5．沈娟，赵雄芳。对分布式数据库发展方向的分析。计算机工程与科学1994年01期。
6．昌月楼，杨利。分布式数据库技术的现状和发展方向。计算机工程与科学1995年03期。
7．阳国贵，金辉，王怀民。分布式数据库技术回顾。计算机工程与科学1995年03期。
8．毛法尧。分布式数据库系统。小型微型计算机系统1995年08期。
9．郭江。分布式数据库系统中的一些问题。计算机系统应用1994年02期。
10．李霖，周兴铭。分布式数据库研究新趋势。计算机工程与科学1997年03期。
11．杨利，昌月楼等编著。2000。并行数据库技术。长沙：国防科技大学出版社。
12．阳富民，冯玉才，吴永英，吴恒山。一种分布式数据库管理系统体系结构。计算机工程与应用1995年02期。
13．Abraham Silberschatz等著，杨冬青等译。2000。数据库系统概念。北京：机械工业出版社
14．邵佩英。2000。分布式数据库系统及其应用。北京：科学出版社
15．Hector Garicia-Molina等著，杨冬青等译。2001。数据库系统实现。北京：机械工业出版社
16．郑振楣，于戈，郭敏。1998。分布式数据库。北京：科学出版社
17．周龙骧。1998。分布式数据库系统实现技术。北京：科学出版社
18．萨师煊，王珊。1992。数据库系统概论。北京：科学出版社
19．施伯乐等。1994。数据库系统导论。北京：高等教育出版社。
20. Son S.H., Efficient decentralized checkpointing in distributed database systems, System Sciences, 1988. Vol. Ⅱ. Software Track, Proceedings of the Twenty-First Annual Hawaii International Conference on, 1988 Page(s): 554-560
21. Zambonelli F., On the effectiveness of distributed checkpoint algorithms for domino-free recovery, High Performance Distributed Computing, 1998. Proceedings. The Seventh International Symposium on, 1998 Page(s): 124-131
22. Manabe, Y., A distributed consistent global checkpoint algorithm for distributed mobile systems, Proceedings of the Internatoinal Conference on Parallel and Distributed Systems-ICPADS Jun 26-29 2001, IEEE p 125-132 In English
23． Helary J.-M.,Mostefaoui A.,Netzer R.H.B.,Raynal M.,Communication-based prevention of useless checkpoints in distributed computations,Distributed Computing 13 1 2000,Springer-Verlag GmbH & Company KG p 29-43 0178-2770 In English
24． Pilarski,S.,Kameda,T.,Checkpointing for distributed databases: starting from the basics,Parallel and Distributed Systems,IEEE Transact ions on,Volume: 3 Issue: 5,Sept.1992 Page(s): 602-610
25． Baldoni,Roberto; Helary,Jean-Michel; Mostefaoui,Achour; Raynal,Michel,Adaptive checkpointing in message passing distributed systems,International Journal of Systems Science v 28 n 11 Nov 1997,Taylor & Francis Ltd p 1145-1161 0020-7721 In English
26． Tanaka Katsuya,Higaki Hiroaki,Takizawa Makoto,Object-based checkpoints in distributed systems,Computer Systems Science and Engineering v 13 n 3 May 1998,CRL Publishing Ltd p 179-185 0267-6192 In English
27． Baldoni Roberto,Quaglia Francesco,Fornara Paolo,An Index-based checkpointing algorithm for autonomous distributed systems,IEEE Transactions on Parallel and Distributed Systems v 10 n 2 Feb 1999,IEEE Comp Soc p 181-192 1045-9219 In English
28． Roberto Baldoni,Giacomo Cioffi Dis,Jean-Michel Helary,Michel Raynal Irisa,Direct Dependency-Based Determination of Consistent Global Checkpoints, http://citeseer.nj.nec.com/17316． html
29． Islene C.Garcia,Luiz E.Buzato,Checkpointing using Local Knowledge about Recovery Lines,http://citeseer.nj.nee.com/garcia99checkpointing.html
30． Baldoni R.,Helary J.-M.,Mostefaoui A.,Raynal M.,A communication-induced check-pointing protocol that ensures rollback-dependency trackability,Fault-Tolerant Com-puting,1997,FTCS-27． Digest of Papers.,Twenty-Seventh Annual International Sympo-sium on,1997 Page(s): 68-77
31． C.Garcia,L.E.Buzato,Progressive construction of consistent global checkpoints,In 19th IEEE Int.Conf.on Distributed Computing Systems (ICDCS'99) ,Austin,Texas,EUA,June 1999
32． Miller E.,Long D.,Freeman W.,Reed B.,Strong security for distributed file systems,Performance,Computing,and Communications,2001． IEEE International Conference on,2001 Page(s): 34-40
33． Shirota Y.,Iizawa A.,Mano H.,Yano T.,The ECHO method: concurrency control method for a large-scale distributed database,Data Engineering,1999． Proceedings.,15th International Conference on ,1999 Page(s): 174-183
34． Martin Rennhackkamp: "Mobile Database Replication," DBMS 10,No.11(October 1997) .
35． Mikyong Han,Yongik Yoon,An implementation and performance analysis of backup system using concurrent log processing in real-time DBMS,Real-Time Computing Systems and Applications,1997． Proceedings.,Fourth International Workshop on ,1997,Page(s): 118-125
36． Qing Tian,Cox D.C.,Optimal replication algorithms for hierarchical mobility management in PCS networks,Wireless Communications and Networking Conference,2002． WCNC2002． 2002 IEEE,Volume: 2 Mar 2002 Page(s): 556-562
37． Panagos E.,Biliris A.,Jagadish H.V.,Rastogi R.,Client-based logging for high performance distributed architectures,Data Engineering,1996． Proceedings of the Twelfth International Conference on,1996,Page(s): 344-351
38． Date,C.J and H.Darwen,A Guid to the SQL Standard,Fourth Edition,Addison-Wesley,Reading MA ,1997．
39． B.Lampson and H.Sturgis,"Crash recorvery in a distributed data storage system," Technical report,Xerox Palo Alto Research Center,1976
40． David Bell and Jane Grimson: Distributed Database Systems.Reading,Mass.:Addison-Wesley(1992)
41． C.J.Date: "What is a Distributed Database System?" ,in Relational Database Writings 1985-1989,Reading,Mass.:Addison-Wesley(1990)
42． C.J.Date: "Distributed Database: A Closer Look." in C.J.Date and Hugh Darwen,Relational Database Writings 1989-1991,Reading,Mass.:Addison-Wesley(1986)
43． Rob Goldring: "A Discussion of Relational Database Replication Technology" InfoDB 8,No.1(Spring 1994)
44． M.R.Stonebraker and E.J.Neuhold: "A Distributed Data Base Version of Ingres" Proc.2nd Berkeley Conf.on Distributed Data Management and Computer Networks,Lawrence Berkeley Laboratory(May 1977) .
2．王珊，陈红等。pbase体系结构与并行性。计算机学报1996年03期。
3．许向阳，冯玉才。并行数据库pdbms的设计与实现。计算机工程与应用1999年11期。
4．王于同。并行数据库性能研究。计算机工程与应用1997年01期。
5．沈娟，赵雄芳。对分布式数据库发展方向的分析。计算机工程与科学1994年01期。
6．昌月楼，杨利。分布式数据库技术的现状和发展方向。计算机工程与科学1995年03期。
7．阳国贵，金辉，王怀民。分布式数据库技术回顾。计算机工程与科学1995年03期。
8．毛法尧。分布式数据库系统。小型微型计算机系统1995年08期。
9．郭江。分布式数据库系统中的一些问题。计算机系统应用1994年02期。
10．李霖，周兴铭。分布式数据库研究新趋势。计算机工程与科学1997年03期。
11．杨利，昌月楼等编著。2000。并行数据库技术。长沙：国防科技大学出版社。
12．阳富民，冯玉才，吴永英，吴恒山。一种分布式数据库管理系统体系结构。计算机工程与应用1995年02期。
13．Abraham Silberschatz等著，杨冬青等译。2000。数据库系统概念。北京：机械工业出版社
14．邵佩英。2000。分布式数据库系统及其应用。北京：科学出版社
15．Hector Garicia-Molina等著，杨冬青等译。2001。数据库系统实现。北京：机械工业出版社
16．郑振楣，于戈，郭敏。1998。分布式数据库。北京：科学出版社
17．周龙骧。1998。分布式数据库系统实现技术。北京：科学出版社
18．萨师煊，王珊。1992。数据库系统概论。北京：科学出版社
19．施伯乐等。1994。数据库系统导论。北京：高等教育出版社。
20. Son S.H., Efficient decentralized checkpointing in distributed database systems, System Sciences, 1988. Vol. Ⅱ. Software Track, Proceedings of the Twenty-First Annual Hawaii International Conference on, 1988 Page(s): 554-560
21. Zambonelli F., On the effectiveness of distributed checkpoint algorithms for domino-free recovery, High Performance Distributed Computing, 1998. Proceedings. The Seventh International Symposium on, 1998 Page(s): 124-131
22. Manabe, Y., A distributed consistent global checkpoint algorithm for distributed mobile systems, Proceedings of the Internatoinal Conference on Parallel and Distributed Systems-ICPADS Jun 26-29 2001, IEEE p 125-132 In English
23． Helary J.-M.,Mostefaoui A.,Netzer R.H.B.,Raynal M.,Communication-based prevention of useless checkpoints in distributed computations,Distributed Computing 13 1 2000,Springer-Verlag GmbH & Company KG p 29-43 0178-2770 In English
24． Pilarski,S.,Kameda,T.,Checkpointing for distributed databases: starting from the basics,Parallel and Distributed Systems,IEEE Transact ions on,Volume: 3 Issue: 5,Sept.1992 Page(s): 602-610
25． Baldoni,Roberto; Helary,Jean-Michel; Mostefaoui,Achour; Raynal,Michel,Adaptive checkpointing in message passing distributed systems,International Journal of Systems Science v 28 n 11 Nov 1997,Taylor & Francis Ltd p 1145-1161 0020-7721 In English
26． Tanaka Katsuya,Higaki Hiroaki,Takizawa Makoto,Object-based checkpoints in distributed systems,Computer Systems Science and Engineering v 13 n 3 May 1998,CRL Publishing Ltd p 179-185 0267-6192 In English
27． Baldoni Roberto,Quaglia Francesco,Fornara Paolo,An Index-based checkpointing algorithm for autonomous distributed systems,IEEE Transactions on Parallel and Distributed Systems v 10 n 2 Feb 1999,IEEE Comp Soc p 181-192 1045-9219 In English
28． Roberto Baldoni,Giacomo Cioffi Dis,Jean-Michel Helary,Michel Raynal Irisa,Direct Dependency-Based Determination of Consistent Global Checkpoints, http://citeseer.nj.nec.com/17316． html
29． Islene C.Garcia,Luiz E.Buzato,Checkpointing using Local Knowledge about Recovery Lines,http://citeseer.nj.nee.com/garcia99checkpointing.html
30． Baldoni R.,Helary J.-M.,Mostefaoui A.,Raynal M.,A communication-induced check-pointing protocol that ensures rollback-dependency trackability,Fault-Tolerant Com-puting,1997,FTCS-27． Digest of Papers.,Twenty-Seventh Annual International Sympo-sium on,1997 Page(s): 68-77
31． C.Garcia,L.E.Buzato,Progressive construction of consistent global checkpoints,In 19th IEEE Int.Conf.on Distributed Computing Systems (ICDCS'99) ,Austin,Texas,EUA,June 1999
32． Miller E.,Long D.,Freeman W.,Reed B.,Strong security for distributed file systems,Performance,Computing,and Communications,2001． IEEE International Conference on,2001 Page(s): 34-40
33． Shirota Y.,Iizawa A.,Mano H.,Yano T.,The ECHO method: concurrency control method for a large-scale distributed database,Data Engineering,1999． Proceedings.,15th International Conference on ,1999 Page(s): 174-183
34． Martin Rennhackkamp: "Mobile Database Replication," DBMS 10,No.11(October 1997) .
35． Mikyong Han,Yongik Yoon,An implementation and performance analysis of backup system using concurrent log processing in real-time DBMS,Real-Time Computing Systems and Applications,1997． Proceedings.,Fourth International Workshop on ,1997,Page(s): 118-125
36． Qing Tian,Cox D.C.,Optimal replication algorithms for hierarchical mobility management in PCS networks,Wireless Communications and Networking Conference,2002． WCNC2002． 2002 IEEE,Volume: 2 Mar 2002 Page(s): 556-562
37． Panagos E.,Biliris A.,Jagadish H.V.,Rastogi R.,Client-based logging for high performance distributed architectures,Data Engineering,1996． Proceedings of the Twelfth International Conference on,1996,Page(s): 344-351
38． Date,C.J and H.Darwen,A Guid to the SQL Standard,Fourth Edition,Addison-Wesley,Reading MA ,1997．
39． B.Lampson and H.Sturgis,"Crash recorvery in a distributed data storage system," Technical report,Xerox Palo Alto Research Center,1976
40． David Bell and Jane Grimson: Distributed Database Systems.Reading,Mass.:Addison-Wesley(1992)
41． C.J.Date: "What is a Distributed Database System?" ,in Relational Database Writings 1985-1989,Reading,Mass.:Addison-Wesley(1990)
42． C.J.Date: "Distributed Database: A Closer Look." in C.J.Date and Hugh Darwen,Relational Database Writings 1989-1991,Reading,Mass.:Addison-Wesley(1986)
43． Rob Goldring: "A Discussion of Relational Database Replication Technology" InfoDB 8,No.1(Spring 1994)
44． M.R.Stonebraker and E.J.Neuhold: "A Distributed Data Base Version of Ingres" Proc.2nd Berkeley Conf.on Distributed Data Management and Computer Networks,Lawrence Berkeley Laboratory(May 1977) .