Current demand for scalability in databases leads to an architecture of loosely-coupled computer nodes which can be expanded or contracted at will. Demand for 24/7 availability leads to requirements for online reorganization. To satisfy these demands, this project develops algorithms for migrating data from one node to another in a distributed system while still allowing users to access the data. First, several schemes for deciding which data to move are considered. While the goal is load balancing, performance of the migration algorithm itself is also a consideration. Algorithms must move only a small amount of the data, not reassign everything to a new node. Experiments are run to measure the "goodness" (coefficient of variance) of load balancing as well as the cost of migration. Second, index maintenance during migration is considered. When only a relatively small amount of data is moved, creating new indexes is more expensive than merging indexes or index entries of moved data into already existing indexes at destination nodes. This merging process must also be online so that users have access to all the data almost all of the time. Experiments measure both efficiency and concurrency for index merging algorithms. Broader impacts of this research include (1) educating the future educators of our technological workforce, (2) enabling efficient online reorganization of massive databases, such as occurs when government agencies are combined and (3) aiding the database industry in satisfying customer demand for scalability and 24/7 availability. More information about this project is available at www.ccs.neu.edu/research/dblab/
