Impact of high-speed wide area network response time dynamics on distributed database design
Salvatore T. March, J. David Naumann, Jesper M. Johansson · 1999
Prior work in Distributed Database Systems (DDB) focused on low-speed networks, which were common in the 1980's and into the early 1990's. However, recent advances in networking technology have dramatically increased network speeds. Current DDB design models are inadequate for designing databases distributed on high-speed networks. We extend prior DDB work by creating models specifically for these networks. These models include latency—the time needed for a message to propagate from sender to receiver over the network. Latency, which has been ignored in prior work, represents a fixed component of network response time. As such, it is unrelated to the size of the message transmitted. Latency changes the structure of the response time model such that updates, which were previously thought to be inexpensive, can be extremely costly. We demonstrate, through experiments, that the impact of latency is negligible in slow networks. However, in high-speed networks latency can contribute 90% or more of the network response time. In the presence of update operations latency thus significantly constrains the data distribution in order to minimize the number of update operations, thus increasing the response time of retrieval operations. This raises the need for approaches that afford a greater data distribution. Parallel execution models can be used for this purpose. Parallelism within multi-site queries is the notion that if a database operation requires several consecutive processing and communication steps, which are not serially dependent, these steps can proceed in parallel, thus lowering response time. Current models assume that such steps proceed serially. However, finding opportunities for parallelism is a complex problem. Current approaches find the best serial execution schedule and parallelize it. We develop an algorithm for finding such opportunities for multi-site updates, and a combination of an algorithm and a method for finding opportunities for parallelism in multi-site queries. These approaches do not rely on a previously generated serial schedule. Experimental evaluation shows that the parallel execution models significantly improve DDB performance. It is also shown that in DDBs, parallel execution plans must be generated under the parallel execution model. Parallelizing a sequential plan will result in sub-optimal performance.