Database systems are the foundation of critical applications that maintain large amounts of data. Since single-processor performance plateaued a decade ago, increasing the number of processors or servers has become the only viable way of improving performance in distributed database management systems. Scalability is a daunting challenge in these systems due to the complex coordination among the large number of parallel tasks---a problem that this project seeks to solve. Most existing database systems determine the order among parallel tasks using conventional physical time. These systems require managing distributed locks, which leads to blocking and computation overhead. Other systems use logical time, which can be thought of as position in an order, to eliminate locking, but require centralized generation of the ordering, which is a serious scalability bottleneck as core count increases. This project breaks the abstraction of physical time and replaces it with a new definition of time that incorporates both logical and physical aspects. "Physiological" time, termed physiological time for ease of pronunciation, uses logical timestamps to order events and then breaks ties using physical time. This enables novel dependency-avoiding approaches to improving system performance and scalability.
This project applies physiological time to three components in a distributed database system. (1) At hardware level, a new hardware transaction memory (HTM) mechanism will be built, which allows more effective data movement in multi-core processors' caches. (2) A new distributed concurrency control protocol will be designed and implemented to coordinate large numbers of parallel tasks in a distributed database. (3) An efficient parallel indexing data structure will be proposed for both multi-core and distributed databases. All three parts of the project will be prototyped and deployed in hardware/software testbeds.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
