We introduce a protocol for schema evolution in a globally distributed database management system with shared data, stateless servers, and no global membership. Our protocol is asynchronous--it allows different servers in the database system to transition to a new schema at different times--and online--all servers can access and update all data during a schema change. We provide a formal model for determining the correctness of schema changes under these conditions, and we demonstrate that many common schema changes can cause anomalies and database corruption. We avoid these problems by replacing corruption-causing schema changes with a sequence of schema changes that is guaranteed to avoid corrupting the database so long as all servers are no more than one schema version behind at any time. Finally, we discuss a practical implementation of our protocol in F1, the database management system that stores data for Google AdWords.

F1 is a distributed relational database system built at Google to support the AdWords business. F1 is a hybrid database that combines high availability, the scalability of NoSQL systems like Bigtable, and the consistency and usability of traditional SQL databases. F1 is built on Spanner, which provides synchronous cross-datacenter replication and strong consistency. Synchronous replication implies higher commit latency, but we mitigate that latency by using a hierarchical schema model with structured data types and through smart application design. F1 also includes a fully functional distributed SQL query engine and automatic change tracking and publishing.

Many of the services that are critical to Google's ad business have historically been backed by MySQL. We have recently migrated several of these services to F1, a new RDBMS developed at Google. F1 implements rich relational database features, including a strictly enforced schema, a powerful parallel SQL query engine, general transactions, change tracking and notification, and indexing, and is built on top of a highly distributed storage system that scales on standard hardware in Google data centers. The store is dynamically sharded, supports transactionally-consistent replication across data centers, and is able to handle data center outages without data loss.

Conventional data warehouses employ the query-at-a-time model, which maps each query to a distinct physical plan. When several queries execute concurrently, this model introduces contention, because the physical plans---unaware of each other---compete for access to the underlying I/O and computation resources. As a result, while modern systems can efficiently optimize and evaluate a single complex data analysis query, their performance suffers significantly when multiple complex queries run at the same time. We describe an augmentation of traditional query engines that improves join throughput in large-scale concurrent data warehouses. In contrast to the conventional query-at-a-time model, our approach employs a single physical plan that can share I/O, computation, and tuple storage across all in-flight join queries. We use an "always-on" pipeline of non-blocking operators, coupled with a controller that continuously examines the current query mix and performs run-time optimizations. Our design allows the query engine to scale gracefully to large data sets, provide predictable execution times, and reduce contention. In our empirical evaluation, we found that our prototype outperforms conventional commercial systems by an order of magnitude for tens to hundreds of concurrent queries.

Web++ is a prototype system that supports user transparent wide area replication of resources in order to improve the response time and reliability of the HTTP service. Our architecture is based on smart clients, and can be dynamically downloaded as mobile code into a user's application, presents a number of advantages. Clients keep track of the average HTTP latency that they experience from various servers and use that information in order to make to choose the replica of a resource that is expected to deliver the best response time for them. The clients also provide feedback on the observed request latencies to the servers, which allows helps the servers to determine which resources should be replicated and what would be the best locations for the replicas. We describe in this paper a distributed server-initiated approach for resource replication in which all servers can decide autonomously whether to replicate resources and the locations where the replicas should be allocated. In addition to the novel use of smart clients, our algorithm also avoids keeping track of complex network topologies by using the concept of logical segments. We present the results of experiments that show that our algorithm for resource allocation scale well with respect to the number of servers and the number of replicated resources.

We address the problem of assigning nonpartitioned files in a parallel I/O system where the file accesses exhibit Poisson arrival rates and fixed service times. We present two new file assignment algorithms based on open queuing networks which aim at minimizing simultaneously the load balance across all disks, as well as the variance of the service time at each disk. We first present an off-line algorithm, Sort Partition, which assigns to each disk file with similar access time. Next, we show that, assuming that a perfectly balanced file assignment can be found for a given set of files, Sort Partition will find the one with minimal mean response time. We then present an on-line algorithm, Hybrid Partition, that assigns groups of files with similar service times in successive intervals while guaranteeing that the load imbalance at any point does not exceed a certain threshold. We report on synthetic experiments which exhibit skew in file accesses and sizes and we compare the performance of our new algorithms with the vanilla greedy file allocation algorithm.

We developed Web++, a prototype system based on user-transparent geographic replication which aims at improving the response time and the reliability of the HTTP service. Web++ extends the current Web client/server architecture with additional capabilities. The extension is provided via Java servlets at the server side and applets at the client side. The servlets pre-process the requested documents such that each logical URL is replaced by a list of physical URLs corresponding to the list of the resource's replica. An applet is automatically downloaded to the client machines together with the first request of each new user session. For subsequent requests within a user session, the applet chooses the physical URT, that corresponds to a resource held by an available server that is expected to deliver the best response time for the server.

The response time of DSS (decision support system) queries is typically several orders of magnitude higher than the response time of OLTP (online transaction processing) queries. Since DSS queries are often submitted interactively, techniques for reducing their response time are becoming increasingly important. We argue that caching of query results is one such technique particularly well suited to the DSS environment. We have designed a query cache manager for such an environment. The cache manager can lookup query results from the cache either based on an exact query match or using a query split algorithm to efficiently find query results which subsume the submitted query. The cache manager dynamically maintains the cache content by deciding whether a newly generated query result should be admitted to the cache and if so, which query results should be evicted from the cache to free space for the new query result. The decisions are aimed at minimizing the query response time. The decisions are explicitly based on a cost function that considers the execution cost of each query, the size of each query result, the reference frequency to each result, the cost of maintenance of each result due to updates of the base tables, and the frequency of such updates. Experimental evaluation shows that our cache manager can improve performance on TPC-D like workloads.

Caching at proxy servers is one of the ways to reduce the response time perceived by World Wide Web users. Cache replacement algorithms play a central role in the response time reduction by selecting a subset of documents for caching, so that a given performance metric is maximized. At the same time, the cache must take extra steps to guarantee some form of consistency of the cached documents. Cache consistency algorithms enforce appropriate guarantees about the staleness of the cached documents. We describe a unified cache maintenance algorithm, LNC-R-WS-U, which integrates both cache replacement and consistency algorithms. The LNC-R-WS-U algorithm evicts documents from the cache based on the delay to fetch each document into the cache. Consequently, the documents that took a long time to fetch are preferentially kept in the cache. The LNC-R-W3-U algorithm also considers in the eviction consideration the validation rate of each document, as provided by the cache consistency component of LNC-R-WS-U. Consequently, documents that are infrequently updated and thus seldom require validations are preferentially retained in the cache. We describe the implementation of LNC-R-W3-U and its integration with the Apache 1.2.6 code base. Finally, we present a trace-driven experimental study of LNC-R-W3-U performance and its comparison with other previously published algorithms for cache maintenance.

This paper presents a distributed file organization for record-structured, disk-resident files with key-based exact-match access. The file is organized into buckets that are spread across multiple servers, where a server may hold multiple buckets. Client requests are serviced by mapping keys onto buckets and looking up the corresponding server in an address table. Dynamic growth in terms of file size and access load is supported by bucket splits and migration onto other existing or newly acquired servers.