Incremental growth and reorganization in distributed database systems.

摘要

Organizations increasingly utilize Distributed Database Management Systems (DDBMS) technology to share common information files. However, increased dependability and use of these systems often result in system bottlenecks. To resolve the bottlenecks, the size of the distributed database system is typically expanded. Servers are added to the existing system and the optimal location of data files is completely recomputed to optimize the global objective function. Because of the associated high costs, such exhaustive computations and subsequent reorganizations cannot be performed frequently.; Researchers have provided an abundance of research in the area of DDBMS technology. Current topics of interest include concurrency control, server failure and recovery, query optimization, file allocation, data partitioning, hardware configurations, etc. An overview of previous research in distributed database technology can be found in (Bernstein 1987) and (Oszu and Valduriez 1991). Although researchers have addressed the issues of data allocation and data migration, this has only been done in isolation and has never been done in the context of system growth. We believe this is the first work to provide a comprehensive, tractable, and dynamic methodology to address incremental system growth and subsequent reorganization in distributed database systems.; In this research, we develop the Incremental Growth methodology, consisting of the heuristic Algorithm REALLOCATE for data reallocation and the heuristic Algorithm MIGRATE for dynamic data migration. Our iterative methodology introduces one new server at a time into the existing DDBMS; Algorithm REALLOCATE reoptimizes the data allocation by evaluating the effect on the global objective function of independently moving each relation to the new server. Once the new data allocation has been determined, Algorithm MIGRATE partitions the earmarked relations into a series of fixed-sized blocks and then dynamically relocates the blocks to the new server. The optimal block size for migration is mathematically derived.; We first demonstrate our algorithms using simple examples. Then, we describe SimDDBMS, a complex simulation software application, complete with an interactive Graphical User Interface (GUI), that has been developed in this research using Objective-C on the NeXT workstation platform. Using SimDDBMS, we run thousands of simulations and perform parametric studies to further demonstrate the robustness of our methodology.