Index of Bibliography Topics

Discusses distributed query processing with QoS guarantees for each query (not query class). Query evaluation plans are adapted on-the-fly.

A generic approach to feedback of control of systems based on the Nelder-Mead simplex method. Application is to buffer pool configuration.

Describes the Quartermaster system, with application to database buffer configuration.

Special Issue on Self-Tuning Databases and Application Tuning

Describes the class fencing technique buffer management technique.

Special Issue on Data Placement for Parallelism

Feedback control of concurrency. Assumes that the relationship between level of concurrency and throughput is unimodal. Proposes two control mechanisms. Incremental steps is a proportional control mechanism. Parabolic approximation mechanism fits recent concurrency/throughput measurements to a parabola and uses the peak of the parabola to choose a target concurrency level. Considers the use of admission control and transaction aborts to achieve the target level of concurrency.

Formulates the concurrency control problem as a control problem for discrete-event dynamical systems.

Gatekeeper system tracks sliding average service time for each type of servlet in the application server. System also obtains an off-line estimate of system capacity, which is expressed as an offered service time load. To implement admission control, Gatekeeper tracks to the current load, which is the sum of the estimated service times of currently-running servlets. It blocks execution of new servlets if the execution would bring the current load above the system capacity. To obtain an off-line estimate of system capacity, system throughput is measured at various levels of offered load. Throughput as a function of offered load is assumed to have a single peak - the maximum offered load at which peak throughput occurs is taken to be the system capacity.

Describes a system that implements N-tier admissions controls and n-tier multiprogramming level control. Uses hill climbing to search configuration space and a queueing model to predict performance of a target configuration. Single-tier queueing models are composed to build an N-tier model. Monitoring system measures QoS constraint compliance and resource utilizations to feed to the queueing model.

Considers a version of the database physical design problem in which the input is a sequence of queries and updates. The goal is to recommend a target physical design for each query or update in the sequence, taking into account both the effect of the physical design on the cost of executing the query or update and the cost of changing the physical design.

Assumes that the optimizer requests indexes that it thinks might be useful for a particular query. These requested indexes form the initial configuration, which is then modified to meet a space constraint.

Uses random queries that are generated from templates. Templates constrain generated queries to ensure that they are reasonable and that they can benefit from indexing.

General approach is to generate candidate MVs and indexes based on the workload, and then filter to meet a space constraint. Multiquery optimization is used when generating candidate MVs.

Automatic hash-based relation partitioning in shared nothing systems.

This is a one-page description of a SIGMOD demo.

Hardcopy on file. This is the journal version of [chna00]. A variety of heuristic techniques for choosing minimal sets of heuristics in such a way that the quality of plans produced by the optimizer is not reduced.

The journal version of this paper is [chna01].

Adaptive declustering in shared-nothing systems using a two-level, tree-structured index.

General recommendation method is to add virtual indexes to the schema, optimize the query, and check whether any virtual statistics are used in the optimal plan. Statistics for virtual indexes are inferred from existing column statistics. To recommend indexes for a workload, recommend for each query in the workload in sequence and then greedily select a subset of the recommended indexes.

How to implement hypothetic database configurations, so that workload costs can be estimated under those configurations. Configuration includes hypothetic indexes and statistics that allow the optimizer to decide whether such an index should be used. Proposes that sampling be used to collect the statistics. Allows specification of scale factors so configurations with larger/smaller databases can be simulated. Presents an analysis interface that supports workload analysis and configuration analysis for current and hypothetical configurations.

Assumes that an upper bound is given on the number of indexes. Workload is specified as a set of SQL DML statements, including insert, delete and update. Search space includes both single and multi-attribute indexes. Index configurations are evaluated by the DBMS optimizer, and several techniques are used to reduce the number of configurations for which optimizer evaluation is required. To generate a set of candidate indexes, this method determines an optimal index configuration independently for each query in the workload. The initial candidate set is then taken as the union of the indexes in the single-query optimal configurations. A hybrid exhaustive/greedy approach is used to control search. To find a k-index configuration, first find the optimal m-index configuration (m <= k) using exhaustive search, then add k-m indexes greedily. Multi-column indexes are handled by first finding an good configuration with single-column indexes, then generating and adding a set of candidate two-column indexes, and then rerunning the optimizer on the new candidate set. This is repeated to handle indexes with more than two columns.

Special Issue on Data Placement for Parallelism

Query features are response time, CPU utilization during query execution, sequential and random I/O throughput during query execution, and the join degree. Queries are then clustered in feature space, using singular value decomposition and semi-discrete decomposition. TPC-H was used for evaluation.

A workload is a weighted set of SQL statements. Problem is to find a subset of these statements that can be used to replace the original workload as an input to certain applications, such that the substitution has little impact on the application's output. Applications considered are automatic index selection and approximate query answering.

Presents some statistics characterizing the database workload generated by some kind of corporate accounting application. Both structural statistics (e.g., number of statements of different types, number of predicates and attributes used in each statement, transaction sizes) and statement execution statistics (e.g., number of tuples retrieved) are collected. There is no attempt to demonstrate that these statistics are useful for any specific purpose.

Extends Karma ([yafa07]) two a two-tier scenario in which multiple clients which share data also share a second-tier cache. Space is partitioned among clients, with one additional partition used for shared data. Within each partition, space is managed using Karma.

Includes lower and upper bounds on optimal off-line performance for multi-level caches. Proposes a scheme called PROMOTE for managing multi-tier caches. As a requested page is passed up through the cache tiers, each cache decides whether it will be responsible for caching the page. Once a cache has decided to cache the page, it notifies the higher level caches of this by attaching a flag to the page as it is passed up through tiers. The higher level caches then do not cache the page. This enforces exclusiveness among the caches. Pages that are repeatedly requested should tend to migrate to higher level caches. Behaviour on writes is not specified, e.g, can a write affect which cache is responsible for a particular page. This policy requires modification of the caching policies at every tier, as each tier must abide by caching decisions made at lower tiers, and must inform upper tiers of its decisions.

Assumes caches support read, read-save, and demote. Requires that blocks by grouped into ranges by the application. Application must also specify the frequency of access and access pattern for each range. Each range is assigned some space in some cache in the hierarchy, and each range's space is then managed using a separate replacement policy. Experiments used PostgreSQL explain to generate range and access pattern hints - however, explain data covers the situation before the DBMS cache.

Compares “hierarchically aware” approachs to “aggressively-collaborative” approaches. The former are transparent to the storage client (e.g., the DBMS), the latter are not. Aggressively-collaborative approaches include two types of hint-passing: access patterns and application semantics. Example of semantic hint is a hint that a block will be read only one time. Even more aggressive is content-aware caching, where the caches try explicitly to avoid duplication. Also considers some additional optimizations: Quick eviction of duplicated blocks (DU) removes pages from the buffer when they are read, Semantics-Directed Caching (SE) uses “importance” values from the storage client (in an ill-specified way) to affect buffering at the storage server. General conclusion is that the agressively-collaborative approaches do not help much compared to the hierarchically-aware approaches.

Presents a trace-based characterization of access patterns for second-tier (L2) buffer caches, noting that L2 cache reference streams don't exhibit any small reuse distances. Presents the MQ algorithm for managing L2 cache. MQ uses multiple LRU queues. Pages are promoted to higher queues according to frequency of reference. Replacements happen in low queues first. An aging mechanism is used to demote pages that cool down. Also describes so-called global replacement algorithms, in which the L2 cache is informed when replacements are made at L1. Evaluation is by trace-driven simulation and also by experiment with an storage system cache implementation.

Eviction-based placement means that a page is loaded into the storage cache when it is evicted from the storage client's cache, as opposed to when it is requested by the client. Proposes tracking evictions transparently by monitoring the target addresses of read requests. Evicted pages are prefetched from disk into the storage system cache at the time of predicted eviction from the storage client cache.

ARC maintains two LRU queues, one for pages that have been referenced once and one for pages that have been referenced more than once. For each queue, there is also a ghost queue that tracks additional pages. The sizes of the two queues are adjusted dynamically. A hit in the single-reference ghost queue causes the single-reference queue to grow. A hit in the multi-reference ghost queue causes the multi-referenced queue to grow.

Notes that storage system caches are often LRU-based, and points out the multi-tier cache inclusion problem: that a second-tier LRU cache behind a first-tier LRU cache will contain many of the same pages as the first-tier cache. Defines a “demote” operation to deal with this problem. Demote sends to the second tier a block that has been evicted from the first tier. Argues that the cost of sending these blocks to the second tier is low because storage networks have lots of bandwidth. Also defines a “demote” buffer management policy for tier two. This puts blocks read by tier one at the LRU end of the buffer (like our +read-read policy) and puts blocks demoted by the first tier at the MRU end.

Describes a cooperative two-level caching system in which first-level caches may fetch blocks from other first-level caches. A hint is potentially inaccurate information about the locations of blocks in the first-level caches.

Simulation study of bi-level LRU caches for a distributed file system. Found that increasing client cache size quickly reduces the hit rate of the second tier cache.

Describes a scheme for synchronizing writes in batches, rather than individually.

User specified confidence threshold specifies how likely it should be that the actual cost of the plan is less than or equal to the reported (point) cost estimate. Cardinality estimates for base tables and intermediate query results are based on join synopses, under the restriction that only foreign-key joins are permitted. The cardinality distribution is determined using the join synopsis and Bayes' rule.

Represents uncertainty in operator estimates using intervals, and tries to identify plans that are robust (close to optimal) throughout the interval, or a set of switchable plans that cover the interval. Implements a run-time switch operation, and modifies other operators so that they initially produce a randomized sample of their output.

Hardcopy on file. Plan reoptimization is triggered by cardinality checking operators inserted into the plan. Checks determine whether the actual cardinality differs from the predicted cardinality by enough that the optimizer would have chosen a different plan. The plan transition cardinalities are determined at optimization time. Reoptimization considers the use of materialized intermediate results when reoptimizing the query.

Claims average 30% estimation time error with 3% of compilation time overhead to produce the estimate.

Classifies SPJ queries using features such as number of tables in the query, the number of SARGable predicates in the query, and the sizes of the tables. For each class of queries, the system maintains a plan template, which can be instantiated for any query in the class. To process a query, system first tries to match it to an existing class. If it can, the class plan template is instantiated and the resulting plan is used for the query. Otherwise, the query is compiled and used to start a new class.

How to produce dynamic query evaluation plans that include ChoosePlan operators. Generalizes the optimizer so that it understands that cost estimates may only partially order the candidate evaluation plans.

Studies the impact of several scaling issues: scheduling and concurrency control, load balancing, and query result caching.

Assumes predeclaration of access sets in the application. Goal is one-copy serializability in a cluster environment, where individual queries in a transaction may be routed to different servers in the cluster. Transactions are serialized by scheduler based on the predeclared access sets. Read-one, write-all is used to handle replicas. Version numbers are used to track which updates have been applied to each table, and it is assumed that the back-end DBMS will apply version-tagged updates in the desired order.

Transactions are classified, and the database is partitioned into conflict classes such that each transaction class uses a single conflict class. The conflict classes need not be disjoint. Each conflict class has a primary site. Replicas are updated lazily. Global serialization order is determined by an atomic broadcast mechanism which is used to deliver the transaction requests. This protocol needs to predict conflicts between transactions.

Eager replication protocol that uses atomic broadcast to help serialize transactions.

A classic.

This is an attempt to define the behavioural implications of policies (event-condition-action rules) so that a self-managing system can reason about which policies to use to adjust itself.

Describes a system called Muse for allocating data center resources to servers. Hosted services are assumed to be able to scale via the the allocation of more servers or the allocation of more of the resources of a given server. For energy-conscious provisioning, keep active servers at a target utilization level and put inactive servers into low-power mode. Proposes resource allocation policies based on a comparison of resource costs and benefits. Costs refer to the costs of providing resources. Benefit refers to the utility of a particular level of application performance. Muse is expected to understand the relationship between resource allocation and application performance levels so that it can optimize the allocation of available resources among the competing applications.

Describes some generic tools for embedding monitoring and control hooks into application software.

Emphasis is on QoS for multimedia streams.

Benchmarks defines two so-called tiers: performance and scale-up. The former considers latency and throughput as offered load increases with a fixed amount of resources. The latter looks at traditional scale-up (does performance stay flat as more data, offered load and resources are added) and elastic speedup (does performance improve if more resources are added under constant load). Benchmark is designed to be extensible, but core workload consists of randomized inserts, updates, reads and sequential scans of keyed records. Benchmark is implemented as a multi-threaded Java program with an interface layer used to customize interactions with specific data managers. Not clear whether this is a closed-loop or open-loop client.

Argues that many web applications need atomic multi-key access. Allows definition of transient, arbitrary key-groups, across which atomic operations are possible. Key groups are implemented by transferring ownership of all keys in a group to a single leader node in the underlying storage system, so that it can coordinate atomic operations without the need for a distributed coordination protocol. Leader uses write-ahead logging to support failure recovery at the leader node. However, it seems that while the leader is down, the group is unavailable.

Restricted application programming model supporting common architectural patterns for web services. Dataflow programming model with nodes representing computation and edges representing data flow.

Tech-lite article talking about virtualization on hand-held devices, about virtualization for software deployment, and about performance and management.

Proposes that data be assigned to one of three consistency levels: A, B, or C. Data assigned to level C have only session consistency and eventual consistency of updates. Data assigned to level A have serializable consistency. Data in the B category have adaptive consistency, switching between session consistency and serializability at runtime.

Snowflock implements an fork (clone) operation for running VMs. The is no implicit synchronization or communication between parent and clone after the fork - anything required must be coded explicitly. Cloned children live on a virtual network with the parent, and can only communicate within this network. SnowFlock starts clones with little initial state, and additional state is shipped on demand from the parent, which uses copy-on-write to preserve a snapshot of its state as of the time of cloning. Each clone gets a virtual disk which is a snapshot of the parent's as of the time of cloning. This is implemented with using copy-on-write at the parent, which serves pages to the clones (via blocktap) as necessary. This mechanism is intended for the root device, not for I/O intensive data devices.

Mostly a how-to guide for system admistrators, covering Containers, Solaris xVM and Solaris xVM VirtualBox.

demo paper

Compares Xen, OpenVZ, and base Linux configurations. Looks at two-tier (Apache+PHP and MySQL) system under a RUBiS workload. Considers a variety of configurations: both tiers on a single physical node, each tier on a different node, and multiple application stacks with the web tiers on one node and the database tiers on another node. Found higher CPU overhead in the Xen configuration, relative to OpenVZ and base Linux. Found that Xen DomU had much higher L2 cache miss count than the base Linux system, but is it not clear how much of this is from the kernel in DomU and how much is from the application.

Key space is partitioned into ranges called tablets. BigTable uses multiple independent tablet servers to serve tablets. Tablets are assigned to servers by a BigTable master node. One server at a time per tablet. Tablet server uses a commit log in GFS to commit updates. Recent updates are kept in memory in a memtable. When the memtable fills, it is written to GFS as an immutable SSTable file.

Resource providers make resources available to brokers, which in turn use them to satisy requests from clients. Clients get lease tickets from brokers, which understand which resources are available from which providers, and which implement polcies controlling which clients get which resources. Clients can redeem tickets with resource providers to obtain the lease, which gives the client access to resources for a fixed time window. Shirako is a toolkit to facilitate the constrution of clients, brokers, and resource providers.

Discusses the process of preparing software applications and application stacks for execution in a utility computing environment.

Proposes a programming model for highly parallelizable computations, and describes a system that implements this model. The computation input is a set of input key/value pairs, and the output is a set of output key/value pairs. The computation itself is defined by two functions. A Map function takes an input key value pair and produces a set of intermediate key/value pairs. A Reduce function takes an intermediate key and a set of values, and produces a single value.

Very nice paper describing the hardware virtualization approach used by Xen and changes it necessitates in the OS. Also includes some empirical performance evaluation.

An overview of some data-related parts of the grid standardization process, including OGSA, DAIS (Data Access and Integration) for standarizing access to relational and XML data sources, OREP (OGSA Replication Services), and DFDL (Data Format and Description Language).

Extended version can be found at http://www.globus.org/research/papers/ogsa.pdf. This is an overview of the Open Grid Services Architecture (OGSA), which is defines something very much like a distributed object system.

Defines the core services of a data grid as a file-oriented storage service plus a distributed directory for meta-data. Also has some discussion of higher level services, like replication.

Explores response time vs. throughput tradeoff for I/O in MySQL. Argues that DBMS should maintain steady rather than bursty I/O request patterns to avoid idle I/O capacity. Describes a Linux implementation of prioritized I/O and measurements of its impact on MySQL's InnoDB.

Proposes to improve storage system performance allowing it to interpret some data written by a DBMS client. Types of interpreted information include log sequence numbers, block types, association of blocks with logical DB entities (tables, indexes), and access statistics explicitly generated by the DBMS to the storage system. Considers using this information in the storage system to ensure graceful degradation in case of device failures and to securely erase deleted data. Also considered extending the X-Ray [basi04] mechanism to improve the performance of the storage server cache.

A good, brief overview of SAN vs. NAS issues plus some discussion of storage virtualization and policy-based storage management.

Distinguishes hints that disclose from hints that advise, and advocates the former. Applications issue hints describing file access patterns: hints can be used to disclose sequential access to the whole file, or to disclose an access pattern described as a sequence of offset,length pairs.

Includes a configuration advisor and a run-time tiering mechanism. The advisor uses a storage workload trace to estimate the capacity required in each tier during each time period, assuming that the run-time mechanism is moving each extent to the lowest cost tier that can satisfy the extent's I/O requirements during each epoch. The advisor recommends provisioning according to the maximum demand at each tier over all epochs. Epochs are assumed to be minutes/hours in duration. At run-time, a dynamic tier manager adjusts the placement of extents after each epoch. It choose a tier for each extent that will minimize power consumption, amont tiers that can satisfy the performance extent's performance demands. Within a tier, it also assigns extents to specific devices, attempting to consolidate so that devices can be powered down. Necessary migrations are then scheduled to run gradually.

Describes a system that uses database query execution plans, storage layout and storage system configuration to attempt to pinpoint the cause of performance problems (e.g., slow queries) in a DBMS plus storage system stack.

Mechanism for proportional allocation of storage server bandwidth among multiple storage clients. Each client observes server response times to detect overload conditions, and then throttles it request stream by an amount determined by the share it expects to receive.

Considers how to apportion database and storage server buffer cache space and storage system bandwidth across multiple workloads.

Allocation of buffer space in the face of a multi-class workload with QoS (mean response time) requirements for each class. Dynamic algorithms.

Enforcement of SLOs for disk. SLOs are load/response time curves for reads and writes. Enforcement mechanism throttles requests from hosts to storage devices. Assumes offered loads are feasible for the underlying storage devices. Uses real-time scheduling (EDF) to put requests into device queues so that deadlines targets are met. Device queue lengths are managed with feedback control.

Given workload, configure block-level storage system. Workload is described as stores (logically contiguous set of blocks) and streams (details in [veke01]). Workload analysis tool can produce stream-based workload description from a request trace. A configuration consists of number of disks, grouping of disks into arrays, division of arrays into logical units, disk controller and cache settings, and a mapping of the stores in the workload onto the logical units. Includes a migration component to move the storage system between configurations. Details of configuration finder are in [anka01]. Iterative approach does not assume that workload remains constant as the system configuration changes.

Input includes a workload description in terms of, logical stores and streams of accesses to the stores, a description of the available physical devices, a set of constraint on how those devices may be configured, maximum utilizations, or total system cost, and finally a cost function that can be used to compare alternative configurations. The output includes a grouping of devices into RAID logical units (LUs) and settings for configuration parameters, such as stripe sizes. Search through the design space is heuristic. Cost functions are externally defined, so the system cannot exploit their structure to improve the search.

Provides an historical overview of an HP effort in automated storage system management. Provides examples of specification language used to describe workloads and system configurations.

Rubicon is a configurable tool for analyzing workload traces. Analysis is accomplished by Rubicon components (reporters, filters) which can be combined to form pipelines to accomplish analysis tasks.

This is the journal version of [yusr02].

Deals with subset of Xpath that is more general than twig queries. Defines a language for specifying access controls by annotating the document DTD, an algorithm for automatically deriving the security view (including a view DTD) from the access control specification, and an algorithm for rewriting queries defined over the view so that they can be evaluated against the base data.

Defines parameterized, user-specific authorization views over relational tables. Unlike [fach04], argues that query processing should be authorization transparent - that is, queries are expressed against the base tables, not the authorization views. Such a query is said to be valid if it can be rewritten using only authorization views. Invalid queries are rejected, so this is a go/no-go security model, like that SQL. Validity testing is undecidable unless the query language is restricted, e.g., to conjunctive queries.

This is a short overview of a SIGMOD tutorial.

Describes a transactional key-value store called Pileus which allows applications to define an SLA for each Get operation. SLA describes the application's preferred performance/consistency tradeoff. SLA is a list of latency/consistency/utility triples, with earlier items preferred to later items. System tries to achieve SLA by controlling which and how many replicas to use for each Get request.

Chops transactions into subtransactions, each of which executes at a single site. Uses static conflict analysis to determine whether subtransactions can be executed independently while ensuring the serializability of the whole outer transaction. User intiated aborts can only occur in the first subtransaction, and system acknowledges commit as soon as the first subtransaction succeeds. Implemented in a system called Lynx.

Describes a meta-system intended to abstract different types of NoSQL systems. Apps see the meta-system, which translates operations to underlying NoSQL systems. Uses an abstract schema consisting of structs, sets, and attributes.

Includes a description of Voldemort.

Stores versioned (timestamped) key to value mappings, replicated using Paxos. Paxos leader also implements a lock table and transaction manager. Transactions local to one group (Paxos instance) are handled by that leader, otherwise 2PC is used among group leaders. Groups span zones (datacenters). Underlying data are stored in Colossus (which is local to a data center?) Keys are grouped into common prefix directories, and directories are assigned to groups. (There are also tablets - difference between tablets and directories is not clear.) Responsibility for controlling replication split between apps and admin. Spanner admins specify a set of replication options (number and placement of copies), apps choose which of these options to use for each directory. Quasi-relational data model, with versioned values, is implemented on top of the basic key to value mapping. Relations are organized hierarchically, with rows linkage based on common key prefixes. Each unique key in the top level table corresponds to a directory.

Objective include high write bandwidth and low read latency. Relational data abstraction. Data are vertically partitioned (using a workload), and then horizontally partitioned within each vertical partition, resulting in tablets. Data are versioned. Interface is record oriented, includes get, put, insert, delete, scan. Each server maintains a single log for all tablets it is responsible for. Also, a multi-version index to locate records on reads. Index is checkpointed to disk periodically to reduce recovery time. Multi-version optimistic concurrency control used to provide SI over multiple records.

Discusses data and functional partitioning in fairly generic terms. Also includes a case study of scaleout for MySpace, using SQL Server.

Data is partitioned into entity groups, each independently and sychronously replicated over a wide area. Multiple data centers, each with a NoSQL data store (BigTable). Transactions allowed within entity groups, but not across. Transactions seem to be reads then writes. Uses Paxos to do wide area replication of a log that includes all transactions' updates, and get agreement on their order of execution. Concurrency control is effectively optimistic - if two transactions are writing in the same entity group at the same time, one may be aborted and retried.

Describes Cloud SQL Server, used by SQL Azure DBMS-as-a-service. Uses partitioning, transactions confined to a single partition. Each DBMS instance has private storage. Synchronous master-slave DBMS-level replication for HA.

Multiple multi-tenant DBMS, each hosting one or more workloads. Large workloads can be scaled-out over multiple DBMS using workload-aware partitioning.

RamCloud appears to apps as a simple key-value storage system. Tries to provide low-latency (5-10 us) access times - needs Infiniband to support this. Tables broken into tablets (contiguous ranges of keys in a tablet), each tablet is assigned to a server. Data are organized in memory as a log. On write, insert new record into the log and update a hash table which indicates where the record can be found. Also push the change to several backup copies of the log on other servers. Periodic garbage collection reclaims log segments. Backups buffer their copies of the log in memory and gradually flush it to disk (not on every update). Suggest use of battery backup or capacitors to ensure that unflushed updates can make it to disk in case power is lost to a backup server. Recovery is highly parallelized. Failed server's keys are repartitioned among multiple recovery masters, each of which recovers its part of the key space and becomes the master for that part of the key space.

Describes an abstraction called overlays for data migration in distributed key-value storage systems.

Excellent overview of hardware and high-level language memory models.

Discussion of technical and business strengths and weaknesses of the utility computing model, including security, lock-in and interoperability.

Discusses cloud service pricing, the cloud computing marketplace, and strategies the may be used by vendors to keep costs low, and weaknesses of current cloud SLAs. Then discusses requirements for Cloud 2.0, meaning cloud services intended to support critical enterprise applications. Issues include storage system performance - argues that access randomness and working set size are proportional to the number of applications supported by a shared storage service. Also discusses administration, SLAs and automation.

Writes collected in RAM and batched to SSD in chunks large enough to fill a flash page. Hash table in memory is used to index key,value pairs in the SSD. There is also a read cache in RAM. Berkeley DB is used to index key,value records on disk. Record read checks RAM read cache, then RAM write buffer, then SSD, then disk. All reads are added to the RAM read cache. Records are inserted into the SSD when they are written (after staging). SSD pages are organized as a ring buffer. When SSD fills, records on early pages are recycled - either by reinserting them into the SSD or by destaging them to the disk. A clock like algorithm (with recent-reference bit) is used to determine whether a record is reinserted into SSD or destaged to disk.

Includes a performance evaluation of Early Lock Release (release locks before commit record goes to disk, but do not return results to client and ensure subsequent transaction's commits are dependent on this one). Also asynchronous log flushing (called flush pipelining) so that threads don't context-switch while waiting for log I/O. Also a technique for parallelizing log buffer insertion.

Describes Percolator, used to incrementally maintain Google's web search index. Provides multi-row transactions and snapshot isolation, using multi-versioning in BigTable. Some transactions may have high latency.

A whitepaper presenting motivation for the RAMCloud project.

Argues for modular and configurable DBMS to address new applications: warehousing, directory services, web search, mobile device caching, XML, streams.

Considers architecture with both flash and magnetic disk available for persistent storage. Each block lives persistently either on disk or on flash, not both. Assumes there is a demand-paged in-memory block cache that makes a placement decision on eviction of a dirty page. Proposed placement algorithms count page reads and writes uses the counts, as well as the costs of read and write operations on disk and flash, to decide where to place an evicted page. Placement decisions are made independently for each page. In particular, there are no capacity constraints and thus the algorithms may choose to place all blocks on the same device. Proposed cache replacement algorithm keeps some number of least-recently-used pages in four queues corresponding to whether the page is clean or dirty and whether the page is located on flash or disk. Always evict the page with the lowest eviction cost from among these least-recently used pages.

Power management for groups (ensembles) of servers, under the assumption that the servers in a group are likely to require peak power at different times. Goal is to reduce the amount of power overprovisioning required for the group.

CQL is the query language implemented by the Stanford STREAM database system.

Chubby cell has a primary and secondaries. Primary handles all reads and writes. Writes are replicated to secondaries and acked when a majority have acked. Primary holds master lease, which it will renew unless it fails. Primary failure causes election of new primary via distributed consensus protocol. Chubby exports a simple Unix-like file system interface. File's can act as reader/writer locks. Chubby also provides notifications of various events, such as modification of file contents or master failover. Clients maintain sessions, which a terminated if the client dies or the session becomes idle. Server guarantees a minimum idle lease time before it will determine session is idle and terminate it. Client also maintains a (conservative) session timeout and will eventually decide its session is expired. Sessions can potentially be preserved across master failovers.

Defines a fault-tolerant commit protocol called Paxos Commit, which makes progress as long as a majority of participants are available. Does not block on failure of a coordinator, as in standard 2PC.

Block level storage virtualization targeted at virtual machines. Uses copy-on-write and trie-based block indexing to support versioned device images. Virtualization is implemented in dedicated virtual machines, one for each node in a cluster.

How to distribute work in a cluster given that different nodes may have different performance and power characteristics. Objective is to minimize power consumption per unit of throughtput. Test implementation is in a cluster web server, and control is achieved by re-distributing the workload among the cluster nodes. Two distribution mechanisms are used: a simple front-end load balancer, and a peer-to-peer mechanism for redistributing requests among servers.

Builds a cost model by tracking costs of recent UDF invocations, including their costs and values of cost-related parameters, and then fitting a model to these data. Includes discussion of statistical issues like collinearity and removal of outliers and collinearity.

Considers cost models as linear functions of a set of explanatory variables for each query class. Initial model is constructed by regression over an initial set of labeled cost samples. Proposes two methods to incrementally maintain such models by folding in new samples and removing the effects of old samples. Assumes that queries from the application workload are labeled and used to train the model.

Discusses file system optimized for relatively small number of large files. Workload is large sequential reads and appends. Node failures are normal. Throughtput is more important than latency. Architecture has a single master and many chunk servers. Master stores metadata (namespace, access controls). Chunks are replicated. Local storage on each chunk node is via a Linux file system. Clients do metadata operations through master, then go directly to chunk servers for data retrieval. Implements a weak consistency model. Metadata operations are atomic and serialized. Concurrent writes of the same file range may get mixed, not serialized. Concurrent appends may lead to duplication. To update a chunk, client first determines (from the master or its cache) the locations of all replicas of the chunk. It first send the update to all replicas. It then sends a write request to the master replica, which serializes all such requests. The master forwards the request serialization order to the other replicas, which apply the updates (they already have) in master-chosen order.

Assumes joined tuples are ranked according to a monotone function of tuple ranks of join inputs. Defines physical join operators that can produce join results in rank order. Operator needs to queue up join results until it can be certain that it will produce them in the proper order.

Describes a methodology for thermal load balancing in server rooms. Thermal imbalances can be caused by imbalanced distribution of server workload and by peculiarities of the airflow in the server room, e.g., racks at the end of a row may be hotter than racks in the middle. Input includes server exhaust temperature readings and cold air temperature. Local thermal imbalances can be corrected by adjusting the allocation of work to the various servers.

A technique for finding twig query matches without first matching individual binary subrelationships in the twig, i.e., this is an N-way structural join. Description of related work is a succinct classification of previous work on twig query processing.

Automatic power management in a cluster of servers by concentrating load on as few machines as possible and turning others off. Implemented in a web server and in a cluster operation system.

A brief general overview of the the problem of energy conservation in data centers.

Presentation of the CAP conjecture.

Incremental, page-at-a-time database recovery on demand, rather than recovery of entire DB before transaction processing resumes. Disk portion of log has redo records only, grouped by the page they refer to. Parallel processes flush log records to disk and also apply logged updates to disk version of the page. Buffer manager also does page flushes (no steal policy). Safe-fetch rule says log updates are only applied to (disk copies) of pages that are in the buffer pool - not clear how this helps. Relies on non-vol RAM to store a map indicating which pages may be stale after a crash, so that they can be brought up to date before being read in after a failure. Targets shared memory multiprocessor, where logger and propagator (applies log updates to pages) can run on their own processors. Seems to rely on page-level locking for correctness.

Discusses scale-up and speed-up as two distinct parallelism objectives. Discusses shared-memory, shared-disk, and shared-nothing architectures and argues that the latter will provide the best scalability because it places the least demands on the interconnection network because interaction is minmized. Discusses data partitioning and parallelization of relational query operators.

Includes a proof of optimality of the MIN algorithm.

Multiple MySQL front ends, replicated partitioned data. Assignment of partitions to nodes can be adjusted to support elastic scale-out. Supports distributed query execution. Company offers database service, rather than software.