Modern data-centric applications frequently need to store and read data with low latency. These requirements are difficult to achieve, even on high performance processors paired with fast solid state drives (SSDs). To this end, LSM tree is widely used in many systems such as in RocksDB and considered as an ideal index structure that fits SSDs. However, in spite of many improvements to LSM tree over the years, fundamental problems of limited read performance and expensive compaction operations remain. Microsoft Research proposed Bw-tree, a variant of B+ tree layered on top of log structured storage. Bw-tree achieves fast ingestion of data, similar to LSM tree, meanwhile it has less drawback on read performance and compaction. However, except for Microsoft, the industrial strength implementation of Bw-tree is rare. The open source OpenBw-Tree from Carnegie Mellon University was designed only for main memory. This paper describes Bwe-tree, an implementation and a significant evolution of Bw-tree on fast storage. It makes two contributions. First, Bwe-tree addresses reliability and performance issues revealed during running Bw-tree on fast storage in production, by revising structural modification operations, introducing page concurrency control, and storing large-size values off-tree. Performance improvements over Bw-tree are verified by experiments. Second, it demonstrates that Bw-tree is an effective alternative tree structure on SSDs. Compared to RocksDB (LSM tree) and BerkeleyDB (B+ tree), Bwe-vtree performs dramatically better (up to 3X or more) for the YCSB workloads. Our Bwe-vtree implementation has been integrated into production systems in Alibaba, including a flagshin cloud-native database service.

Exploiting a storage hierarchy is critical to cost-effective data management. However, most systems are challenged when data is not in cache because of the additional I/O to move data between SSD and main memory. To improve both cost and performance, some systems use a log structured store to write a batch of pages instead of a "block-at-a-time". However, host-based log structuring incurs the additional cost and complexity of garbage collection and recovery, duplicating similar SSD FTL functionality. In prior work, we presented a customized SSD controller implementation for an Open-Channel SSD to enable host computers to write batches of fixed size pages. This current work is a major redesign to support a batched write interface with variable size pages. Variable size pages can enable easy support of data compression and encryption, as well as reducing internal page storage fragmentation, e.g, within a B-tree. Thus it further improves I/O performance while making it easier and more efficient to support these capabilities.

Modern storage devices do not support update-in-place. Rather, flash and shingled disks, are forms of log structured stores. Such a store writes a number of diverse and non-contiguous logical pages into a unit of contiguous storage we call a segment instead of using a write I/O to update each page in place. The result is that pages need to be relocated and remapped on every write. Log structuring was invented for and used initially to improve performance in file systems. Segments need to be garbage collected, but can be only when they no longer house any current pages. A process of "cleaning" produces an empty segment by, when necessary, moving (re-writing) still current pages of the segment to another location. Cleaning effectiveness has a major impact on the performance of modern storage devices, and for flash, impacts the rate of wear and hence the lifetime of the device. We analyze cleaning performance and introduce a cleaning strategy that uses a new way to prioritize the order in which segments are cleaned. Our cleaning strategy approximates an "optimal cleaning strategy". Simulation studies confirm the results of the analysis. This strategy is a significant improvement over previous cleaning strategies.

Recent work on "learned indexes" has changed the way we look at the decades-old field of DBMS indexing. The key idea is that indexes can be thought of as "models" that predict the position of a key in a dataset. Indexes can, thus, be learned. The original work by Kraska et al. shows that a learned index beats a B+ tree by a factor of up to three in search time and by an order of magnitude in memory footprint. However, it is limited to static, read-only workloads. In this paper, we present a new learned index called ALEX which addresses practical issues that arise when implementing learned indexes for workloads that contain a mix of point lookups, short range queries, inserts, updates, and deletes. ALEX effectively combines the core insights from learned indexes with proven storage and indexing techniques to achieve high performance and low memory footprint. On read-only workloads, ALEX beats the learned index from Kraska et al. by up to 2.2X on performance with up to 15X smaller index size. Across the spectrum of read-write workloads, ALEX beats B+ trees by up to 4.1X while never performing worse, with up to 2000X smaller index size. We believe ALEX presents a key step towards making learned indexes practical for a broader class of database workloads with dynamic updates.

Exploiting a storage hierarchy is critical to cost-effective data management. One can achieve great performance when working solely on main memory data. But this comes at a high cost. Systems that use secondary storage as the "home" for data have much lower storage costs as they can not only make the data durable but reduce its storage cost as well. Performance then becomes the challenge, reflected in an increased execution cost. Log structured stores, e.g. Deuteronomy, improve I/O cost/performance by batching writes. However, this incurs the cost of host-based garbage collection and recovery, which duplicates SSD flash translation layer (FTL) functionality. This paper describes the design and implementation in a controller for an Open Channel SSD of a new FTL that supports multi-page I/O without host-based log structuring. This both simplifies the host system and improves performance. The new FTL improves I/O cost/performance with only modest change to the current block at a time, update-in-place interface.

Data in traditional "caching" data systems resides on secondary storage, and is read into main memory only when operated on. This limits system performance. Main memory data stores with data always in main memory are much faster. But this performance comes at a cost. In this paper, we analyze the costs of both in-memory operations and secondary storage operations where data is not "in cache". We study the performance impact of cache misses on caching system performance. The analysis considers both execution and storage costs. Based on our analysis, we derive cost/performance results for a data caching system [Deuteronomy and its Bw-tree] and a main memory system [MassTree] to understand where each demonstrates the best cost per operation, what is driving the cost differences, and the scale of the differences. This analysis (1) provides insight into why data caching systems continue to dominate the market; (2) points to higher performance that does not rely on simply increasing main memory cache size; and (3) suggests a path to lower costs and hence better cost/performance.

A caching data store, e.g., a traditional dbms, moves data between main memory and secondary storage as dictated by access patterns. Such a system provides good cost/performance by hosting hot data in expensive DRAM, while moving cold data to cheaper SSD storage. Data caching system success is demonstrated by the health of the traditional database systems market, and its growth with new vendors offering data caching systems. However, achieving both high performance and low cost using any database system, including data caching systems, has been a challenge. We describe how this problem has been attacked, including in our Deuteronomy project.

Transaction time databases can be put to a number of valuable uses, auditing, regulatory compliance, readable backups, and enabling multi-version concurrency control. While additional storage for retaining multiple versions is unavoidable, compression and the declining cost of disk storage largely removes that impediment to supporting multi-version data. Not clear has been whether effective indexing of historical versions, can be achieved at high performance. The current paper shows how temporal indexing can exploit the latch-free infrastructure provided for the Bw-tree by the LLAMA cache/storage subsystem to support high performance. Further, it demonstrates how the LLAMA mapping table can be exploited to simultaneously enable migration of historical data, e.g. to cloud storage, while overcoming the index node time splitting difficulty that has arisen in the past when historical nodes are migrated.

The Deuteronomy transactional key value store executes millions of serializable transactions/second by exploiting multi-version timestamp order concurrency control. However, it has not supported range operations, only individual record operations (e.g., create, read, update, delete). In this paper, we enhance our multi-version timestamp order technique to handle range concurrency and prevent phantoms. Importantly, we maintain high performance while respecting the clean separation of duties required by Deuteronomy, where a transaction component performs purely logical concurrency control (including range support), while a data component performs data storage and management duties. Like the rest of the Deuteronomy stack, our range technique manages concurrency information in a latch-free manner. With our range enhancement, Deuteronomy can reach scan speeds of nearly 250 million records/s (more than 27 GB/s) on modern hardware, while providing serializable isolation complete with phantom prevention.

Azure DocumentDB is Microsoft's multi-tenant distributed database service for managing JSON documents at Internet scale. DocumentDB is now generally available to Azure developers. In this paper, we describe the DocumentDB indexing subsystem. DocumentDB indexing enables automatic indexing of documents without requiring a schema or secondary indices. Uniquely, DocumentDB provides real-time consistent queries in the face of very high rates of document updates. As a multi-tenant service, DocumentDB is designed to operate within extremely frugal resource budgets while providing predictable performance and robust resource isolation to its tenants. This paper describes the DocumentDB capabilities, including document representation, query language, document indexing approach, core index support, and early production experiences.

Recent OLTP support exploits new techniques, running on modern hardware, to achieve unprecedented performance compared with prior approaches. In SQL Server, the Hekaton main-memory database engine embodies this new OLTP support. Hekaton uses the Bw-tree to achieve its great indexing performance. The Bw-Tree is a latch-free B-tree index that also exploits log-structured storage when used "beyond" Hekaton as a separate key value store. It is designed from the ground up to address two hardware trends: (1) Multi-core and main memory hierarchy: the Bw-tree is completely latch-free, using an atomic compare-and-swap instruction to install state changes on a "page address" mapping table; it performs updates as "deltas" to avoid update-in-place. These improve performance by eliminating thread blocking while improving cache hit ratios. (2) Flash storage: the Bw-tree organizes secondary storage in a log-structured manner, using large sequential writes to avoid entirely the adverse performance impact of random writes. We demonstrate the architectural versatility and performance of the Bw-tree in two scenarios: (a) running live within Hekaton and (2) running as a standalone key value store compared to both BerkeleyDB and a state-of-the-art in-memory range index (latch-free skiplists). Using workloads from real-world applications (Microsoft XBox Live Primetime and enterprise deduplication), we show the Bw-tree is 19x faster than BerkeleyDB and 3x faster than skiplists.

The emergence of new hardware and platforms has led to reconsideration of how data management systems are designed. However, certain basic functions such as key indexed access to records remain essential. While we exploit the common architectural layering of prior systems, we make radically new design decisions about each layer. Our new form of B-tree, called the Bw-tree achieves its very high performance via a latch-free approach that effectively exploits the processor caches of modern multi-core chips. Our storage manager uses a unique form of log structuring that blurs the distinction between a page and a record store and works well with flash storage. This paper describes the architecture and algorithms for the Bw-tree, focusing on the main memory aspects. The paper includes results of our experiments that demonstrate that this fresh approach produces outstanding performance.

LLAMA is a subsystem designed for new hardware environments that supports an API for page-oriented access methods, providing both cache and storage management. Caching (CL) and storage (SL) layers use a common mapping table that separates a page's logical and physical location. CL supports data updates and management updates (e.g., for index re-organization) via latch-free compare-and-swap atomic state changes on its mapping table. SL uses the same mapping table to cope with page location changes produced by log structuring on every page flush. To demonstrate LLAMA's suitability, we tailored our latch-free Bw-tree implementation to use LLAMA. The Bw-tree is a B-tree style index. Layered on LLAMA, it has higher performance and scalability using real workloads compared with BerkeleyDB's B-tree, which is known for good performance.

Recently, there has been much renewed interest in re-architecting database systems to exploit new hardware. While some efforts have suggested that one needs specialized engines ("one size does not fit all"), the approach pursued by Microsoft's SQL Server has been to integrate multiple elements into a common architecture. This brings customers what they want by reducing data impedance mismatches between database systems that they are using for multiple purposes. This integration is, of course, more easily said than done. But this is, in fact, precisely what the SQL Server team has done.

A database supporting multiple versions of records may use the versions to support queries of the past or to increase concurrency by enabling reads and writes to be concurrent. We introduce a new concurrency control approach that enables all SQL isolation levels including serializability to utilize multiple versions to increase concurrency while also supporting transaction time database functionality. The key insight is to manage a range of possible timestamps for each transaction that captures the impact of conflicts that have occurred. Using these ranges as constraints often permits concurrent access where lock based concurrency control would block. This can also allow blocking instead of some aborts that are common in earlier multi-version concurrency techniques. Also, timestamp ranges can be used to conservatively find deadlocks without graph based cycle detection. Thus, our multi-version support can enhance performance of current time data access via improved concurrency, while supporting transaction time functionality.

Cloud SQL Server is a relational database system designed to scale-out to cloud computing workloads. It uses Microsoft SQL Server as its core. To scale out, it uses a partitioned database on a shared-nothing system architecture. Transactions are constrained to execute on one partition, to avoid the need for two-phase commit. The database is replicated for high availability using a custom primary-copy replication scheme. It currently serves as the storage engine for Microsoft's Exchange Hosted Archive and SQL Azure.

The current database market is fairly evenly split between shared nothing and data sharing systems. While shared nothing systems are easier to build and scale, data sharing systems have advantages in load balancing. In this paper we explore adding data sharing functionality as an extension to a shared nothing database system. Our approach isolates the data sharing functionality from the rest of the system and relies on well-studied, robust techniques to provide the data sharing extension. This reduces the difficulty in providing data sharing functionality, yet provides much of the flexibility of a data sharing system. We present the design and implementation of Chimera -- a hybrid database system, targeted at load balancing for many workloads, and scale-out for read-mostly workloads. The results of our experiments demonstrate that we can achieve almost linear scalability and effective load balancing with less than 2% overhead during normal operation.

New hardware platforms, e.g. cloud, multi-core, etc., have led to a reconsideration of database system architecture. Our Deuteronomy project separates transactional functionality from data management functionality, enabling a flexible response to exploiting new platforms. This separation requires, however, that recovery is described logically. In this paper, we extend current recovery methods to work in this logical setting. While this is straightforward in principle, performance is an issue. We show how ARIES style recovery optimizations can work for logical recovery where page information is not captured on the log. In side-by-side performance experiments using a common log, we compare logical recovery with a state-of-the art ARIES style recovery implementation and show that logical redo performance can be competitive.

CLOUD computing has been around long enough that we are all aware of it. However, it has not lived so long that major issues, technical and nontechnical, all have neat solutions. Cloud computing is at a stage similar to relational databases in the early 1980’s. Some technology exists, but there are many opportunities for improved technology and for turning the cloud into a profitable business. And, there is intense competition as vendors scramble to develop and deploy data centers and sell cloud services. The unique technical characteristic of the cloud is that it provides compute power, data storage, and communication bandwith on a scale that we have not really witnessed before. We now have enormous data centers supporting thousands of machines, attached by high speed, low latency communications, each with a number of attached high capacity disks. The emergence of cloud computing is driven by economics. Cloud data centers are typically located where power is cheap and land costs low. Hardware is purchased in high volume at rock bottom prices or specially assembled from even cheaper components. Many data centers approach lights-out automated operations to drive down costs. Customers pay for what they use instead of provisioning for their maximum load. In addition, cloud providers offer their customers excellent availability via data replication. The economics of the cloud are compelling, and will produce industry wide changes. The database community has a big role to play in exploiting cloud computing. We are, after all, in the business of efficiently storing and querying data. This special section on cloud computing covers a cross section of challenges posed by cloud computing. Query processing with Map-Reduce represents a very significant technical challenge. This special section has three papers in this area. There are, however other issues. The section also has one paper on monitoring the state (health) of cloud-based applications and another on how to price cloud services. This section begins with the three query processing papers. “Optimizing Multiway Joins in a Map-Reduce Environment,” by Foto N. Afrati and Jeffrey D. Ullman focuses on Map-Reduce systems and the optimization of multiway joins, paying particular attention to communication costs. “MAP-JOIN-REDUCE: Towards Scalable and Efficient Data Analysis on Large Clusters,” by Dawei Jiang, Anthony K.H. Tung, and Gang Chen describes a new filtering-join-aggregation strategy to improve scalability for data analysis when using Map-Reduce. Finally, “HeuristicsBased Query Processing for Large RDF Graphs Using Cloud Computing,” by Mohammad F. Husain, James McGlothlin, Mohammad M. Masud, Latifur R. Khan, and Bhavani Thuraisingham looks at the special problems presented by large RDF graphs, and how to effectively query them. Query processing is not the only cloud challenge. One would like to watch over your application and be kept informed of how things are going. This is called “state monitoring” and is treated in “State Monitoring in Cloud Datacenters,” by Shicong Meng, Ling Liu, and Ting Wang. And, of course, the cloud is also a business, and needs to be run like one. How one prices cloud services determines whether a clould provider grows and prospers or withers and dies. How to determine appropriate pricing is the subject of the last paper “Optimal Service Pricing for a Cloud Cache,” by Verena Kantere, Debabrata, Gregory Francois, Sofia Kyriakopoulou, and Anastasia Ailamaki. This special section was a direct result of Beng Chin Ooi asking me to do it, and I want to thank him for the invitation. It has been a great opportunity to learn more about this increasingly important topic. I need also to thank the authors, not only of the accepted papers, but all of those who submitted their work. Not only would special sections not be possible without the enthusiasm of authors, but progress in our field has an essential dependence on this enthusiasm. Finally, thanks are due to the reviewers who worked so hard to evaluate and, in some cases, assist authors in the process of making their papers the strong contributions that they are. I believe readers will be well rewarded for reading the papers in this special section. To them I say “Bon appetit!”

Immortal DB is a transaction time database system that is built into a commercial database system rather than being layered on top. This enables it to have performance that is very close to the performance of an unversioned current time database system. Achieving such competitive performance is essential for wide acceptance of this temporal functionality. In this paper we describe further performance improvements in two critical dimensions. First Immortal DB range search performance is improved for current time data via improved current version storage utilization, making this performance essentially the same as unversioned performance. Second, Immortal DB update performance is increased by further reducing the cost for the timestamping of versions. Finally, we show how a simple modification, integrated into the timestamping mechanism, can provide a foundation for auditing database activity. Our algorithms have been incorporated into a commercial database engine and experiments using this database engine demonstrate the effectiveness of our approach.

We have developed log-based recovery for middleware servers that access back-end transaction systems (DBMSs). Transactional consistency is provided between in-memory state stored in middleware servers and persistent state stored in transaction systems. A new logging method called results logging is exploited to ensure coordinated recovery of in-memory state with persistent database state. Results logging incurs low logging overhead for middleware servers and requires little or no modification to existing transaction systems. This makes our approach a practical coordinated recovery technique.

To adapt database technology to new environments like cloud platforms or multi-core hardware, or to try anew to provide an extensible database platform, it is useful to separate transaction services from data management elements that need close physical proximity to data. With "generic" transactional services of concurrency control and recovery in a separate transactional component (TC), indexing, cache and disk management, now in a data component (DC), can be simplified and tailored more easily to the platform or to a data type extension with a special purpose index. This decomposition requires that details of the DC's management of data be hidden from the TC. Thus, locking and logging need to be "logical", which poses a number of problems. One problem is the handling of locking for ranges of keys. Locks need to be taken at the TC prior to the records and their keys being known to the TC. We describe generic two approaches for dealing with this. (1) Make a "speculative" visit" to the DC to learn key values. (2) Lock a "covering resource" first, then learn and lock key values and ultimately release the covering resource lock. The "table" is the only logical (and hence known to the TC) covering resourse in the traditional locking hierarchy, but using it limits concurrency. Concurrency is improved with the introduction of new partition resources. We show how partitions as covering resources combine high concurrency with low locking overhead. Using partitions is sufficiently effective to consider adapting it for a traditional database kernel.

Immortal DB is a transaction time database system designed to enable high performance for temporal applications. It is built into a commercial database engine, Microsoft SQL Server. This paper describes how we integrated a temporal indexing technique, the TSB-tree, into Immortal DB to serve as the core access method. The TSB-tree provides high performance access and update for both current and historical data. A main challenge was integrating TSB-tree functionality while preserving original B+tree functionality, including concurrency control and recovery. We discuss the overall architecture, including our unique treatment of index terms, and practical issues such as uncommitted data and log management. Performance is a primary concern. To increase performance, versions are locally delta compressed, exploiting the commonality between adjacent versions of the same record. This technique is also applied to index terms in index pages. There is a tradeoff between query performance and storage space. We discuss optimizing performance regarding this tradeoff throughout the paper. The result of our efforts is a high-performance transaction time database system built into an RDBMS engine, which has not been achieved before. We include a thorough experimental study and analysis that confirms the very good performance that it achieves.

We have developed new methods for log-based recovery for middleware servers which involve thread pooling, private in-memory states for clients, shared in-memory state and message interactions among middleware servers. Due to the observed rareness of crashes, relatively small size of shared state and infrequency of shared state read/write accesses, we are able to reduce the overhead of message logging and shared state logging while maintaining recovery independence. Checkpointing has a very small impact on ongoing activities while still reducing recovery time. Our recovery mechanism enables client private states to be recovered in parallel after a crash. On a commercial middleware server platform, we have implemented a recovery infrastructure prototype, which demonstrates the manageability of system complexity and shows promising performance results.

Transaction time databases retain and provide access to prior states of a database. An update "inserts" a new record while preserving the old version. Immortal DB builds transaction time database support into a database engine, not in middleware. It supports as of queries returning records current at the specified time. It also supports snapshot isolation concurrency control. Versions are stamped with the "clock times" of their updating transactions. The timestamp order agrees with transaction serialization order. Lazy timestamping propagates timestamps to transaction updates after commit. Versions are kept in an integrated storage structure, with historical versions initially stored with current data. Time-splits of pages permit large histories to be maintained, and enable time based indexing, which is essential for high performance historical queries. Experiments show that Immortal DB introduces little overhead for accessing recent database states while providing access to past states.

User written transaction code is responsible for the "C" in ACID transactions, i.e., taking the database from one consistent state to the next. However, user transactions can be flawed and lead to inconsistent (or invalid) states. Database systems usually correct invalid data using "point in time" recovery, a costly process that installs a backup and rolls it forward. The result is long outages and the "de-commit" of many valid transactions, which must then be re-submitted, frequently manually. We have implemented in our transaction-time database system a technique in which only data tainted by a flawed transaction and transactions dependent upon its updates are "removed". This process identifies and quarantines tainted data despite the complication of determining transactions dependent on data written by the flawed transaction. A further property of our implementation is that no backup needs to be installed for this because the prior transaction-time states provide an online backup.

Enterprise applications need to be highly available and scalable. In the past, this has required "stateless" applications, which essentially require the application to manage its state explicitly by storing it in transactional resource managers. Despite "stateful" applications being more natural and hence easier to write and get correct, having the system manage this state automatically has been considered too difficult and too costly. The Phoenix/App system showed how to manage state in stateful applications transparently, by logging interactions between components, guaranteeing "exactly once" execution of the application. By introducing some minor restrictions on Phoenix/App components, no logging need be done for middle tier components, thus making it easy to provide both availability and scalability. Because there is no logging, the performance of failure free application executions is excellent.

Our goal is to support transaction-time functionality that enables the coexistence of ordinary, non-temporal tables with transaction-time tables. In such a system, each transaction updating a transaction-time or snapshot table must include a timestamp for its updated data that correctly reflects the serialization order of the transactions, including transactions on ordinary tables. A serious issue is coping with SQL CURRENT/spl I.bar/TIME functions, which should return a time consistent with a transaction's timestamp and serialization order. Prior timestamping techniques cannot support such junctions with this desired semantics. We show how to compatibly extend conventional database functionality for transaction-time support by exploiting the database system lock manager and by utilizing a spectrum of optimizations.

Immortal DB builds transaction time database support into the SQL Server engine, not in middleware. Transaction time databases retain and provide access to prior states of a database. An update "inserts" a new record while preserving the old version. The system supports as of queries returning records current at the specified time. It also supports snapshot isolation concurrency control. Versions are stamped with the times of their updating transactions. The timestamp order agrees with transaction serialization order. Lazy timestamping propagates timestamps to all updates of a transaction after commit. All versions are kept in an integrated storage structure, with historical versions initially stored with current data. Time-splits of pages permit large histories to be maintained, and enable time based indexing. We demonstrate Immortal DB with a moving objects application that tracks cars in the Seattle area.

Phoenix/App supports software components whose states are made persistent across a system crash via redo recovery, replaying logged interactions. Our initial prototype force logged all request/reply events resulting from intercomponent method calls and returns. We describe an enhanced prototype that implements: (i) log optimizations to improve normal execution performance; and (ii) checkpointing to improve recovery performance. Logging is reduced in two ways: (1) we only log information required to remove nondeterminism, and we only force the log when an event "commits" the state of the component to other parts of the system; (2) we introduce new component types that provide our enhanced system with more information, enabling further reduction in logging. To improve recovery performance, we save the values of the fields of a component to the log in an application "checkpoint". We describe the system elements that we exploit for these optimizations, and characterize the performance gains that result.

Why might B-tree concurrency control still be interesting? For two reasons: (i) currently exploited "real world" approaches are complicated; (ii) simpler proposals are not used because they are not sufficiently robust. In the "real world", systems need to deal robustly with node deletion, and this is an important reason why the currently exploited techniques are complicated. In our effort to simplify the world of robust and highly concurrent B-tree methods, we focus on exactly where B-tree concurrency control needs information about node deletes, and describe mechanisms that provide that information. We exploit the B/sup link/ -tree property of being "well-formed" even when index term posting for a node split has not been completed to greatly simplify our algorithms. Our goal is to describe a very simple but nonetheless robust method.

Building highly available enterprise applications using Web-oriented middleware is hard. Runtime implementations frequently do not address the problems of application state persistence and fault-tolerance, placing the burden of managing session state and, in particular, handling system failures on application programmers. This paper describes Phoenix/APP, a runtime service based on the notion of recovery guarantees. Phoenix/APP transparently masks failures and automatically recovers component-based applications. This both increases application availability and simplifies application development. We demonstrate the feasibility of this approach by describing the design and implementation of Phoenix/APP in Microsoft's .NET runtime and present results on the cost of persisting and recovering component-based applications.

Our goal is to understand redo recovery. We define an installation graph of operations in an execution, an ordering significantly weaker than conflict ordering from concurrency control. The installation graph explains recoverable system state in terms of which operations are considered installed. This explanation and the set of operations replayed during recovery form an invariant that is the contract between normal operation and recovery. It prescribes how to coordinate changes to system components such as the state, the log, and the cache. We also describe how widely used recovery techniques are modeled in our theory, and why they succeed in providing redo recovery.

Database recovery does not mask failures to applications and users. Recovery is needed that considers data, messages and application components. Special cases have been studied, but clear principles for recovery guarantees in general multi-tier applications such as Web-based e-services are missing. We develop a framework for recovery guarantees that masks almost all failures. The main concept is an interaction contract between two components, a pledge as to message and state persistence, and contract release. Contracts are composed into system-wide agreements so that a set of components is provably recoverable with exactly-once message delivery and execution, except perhaps for crash-interrupted user input or output. Our implementation techniques reduce the data logging cost, allow effective log truncation, and provide independent recovery for critical server components. Interaction contracts form the basis for our Phoenix/COM project on persistent components. Our framework's utility is demonstrated with a case study of a web-based e-service.

High availability for both data and applications is rapidly becoming a business requirement. While database systems support recovery, providing high database availability, applications may still lose work because of server outages. When a server crashes, any volatile state associated with the application's database session is lost and the application may require an operator-assisted restart. This exposes server failures to end-users and always degrades application availability. Our Phoenix/ODBC system supports persistent database sessions that can survive a database crash without the application being aware of the outage, except for possible timing considerations. This improves application availability and eliminates the application programming needed to cope with database crashes. Phoenix/ODBC requires no changes to the database system, data access routines or applications. Hence, it can be deployed in any application that uses ODBC to access a database. Further, our generic approach can be exploited for a variety of data access protocols. In this paper, we describe the design of Phoenix/ODBC and introduce an extension to optimize the response time and to reduce overhead for OLTP workloads. We present a performance evaluation using the TPC-C and TPC-H benchmarks that demonstrate Phoenix/ODBC's extra overhead is modest.

Media recovery protects a database from failures of the stable medium by maintaining an extra copy of the database, called the backup, and a media recovery log. When a failure occurs, the database is “restored” from the backup, and the media recovery log is used to roll forward the database to the desired time, usually the current time. Backup must be both fast and “on-line”, i.e. concurrent with on-going update activity. Conventional online backup sequentially copies from the stable database, almost independent of the database cache manager, but requires page-oriented log operations. But results of logical operations must be flushed to a stable database (a backup is a stable database) in a constrained order to guarantee recovery. This order is not naturally achieved for the backup by a cache manager concerned only with crash recovery. We describe a “full speed” backup, only loosely coupled to the cache manager, and hence similar to current online backups, but effective for general logical log operations. This requires additional logging of cached objects to guarantee media recoverability. We then show how logging can be greatly reduced when log operations have a constrained form which nonetheless provides very useful additional logging efficiency for database systems.

article Phoenix: making applications robust Share on Authors: Roger Barga Microsoft Corporation, One Microsoft Way, Redmond, WA Microsoft Corporation, One Microsoft Way, Redmond, WAView Profile , David B. Lomet Microsoft Corporation, One Microsoft Way, Redmond, WA Microsoft Corporation, One Microsoft Way, Redmond, WAView Profile Authors Info & Claims ACM SIGMOD RecordVolume 28Issue 2June 1999 pp 562–564https://doi.org/10.1145/304181.304577Online:01 June 1999Publication History 10citation280DownloadsMetricsTotal Citations10Total Downloads280Last 12 Months8Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Recovery can be extended to new domains at reduced logging cost by exploiting “logical” log operations. During recovery, a logical log operation may read data values from any recoverable object, not solely from values on the log or from the updated object. Hence, we needn't log these values, a substantial saving. In [8], we developed a redo recovery theory that deals with general log operations and proved that the stable database remains recoverable when it is explained in terms of an installation graph. This graph was used to derived a write graph that determines a flush order for cached objects that ensures that the database remains recoverable. In this paper, we introduce a refined write graph that permits more flexible cache management that flushes smaller sets of objects. Using this write graph, we show how: (i) the cache manager can inject its own operations to break up atomic flush sets; and (ii) the recovery process can avoid redoing operations whose effects aren't needed by exploiting generalized recovery LSNs. These advances permit more cost-effective recovery for, e.g., files and applications.

We describe how to recover applications after system crashes using database recovery. Earlier efforts, based on frequent application checkpoints and/or logging values read, are very expensive. We treat application state as a cached object and log application execution as operations in the recovery framework of D. Lomet and M. Tuttle (1995). Logging application execution does not require logging the application state. Further logged application reads are mostly logical operations in which only the data source identity is logged. We describe a cache manager that handles the flush order dependencies introduced by these log operations and a recovery process that restores application state by replaying the application.

Database systems recover persistent data, providing high database availability. However, database applications, typically residing on client or "middle-tier" application-server machines, may lose work because of a server failure. This prevents the masking of server failures from the human user and substantially degrades application availability. This paper aims to enable high application availability with an integrated method for database server recovery and transparent application recovery in a client-server system. The approach, based on application message logging, is similar to earlier work on distributed system fault tolerance. However, we exploit advanced database logging and recovery techniques and request/reply messaging properties to significantly improve efficiency. Forced log I/Os, frequently required by other methods, are usually avoided. Restart time, for both failed server and failed client, is reduced by checkpointing and log truncation. Our method ensures that a server...

Order-preserving compression can improve sorting and searching performance, and hence the performance of database systems. We describe a new parsing (tokenization) technique that can be applied to variable-length "keys", producing substantial compression. It can both compress and decompress data, permitting variable lengths for dictionary entries and compressed forms. The key notion is to partition the space of strings into ranges, encoding the common prefix of each range. We illustrate our method with padding character compression for multi-field keys, demonstrating the dramatic gains possible. A specific version of the method has been implemented in Digital's Rdb relational database system to enable effective multi-field compression.

A new sort algorithm, called AlphaSort, demonstrates that commodity processors and disks can handle commercial batch workloads. Using Alpha AXP processors, commodity memory, and arrays of SCSI disks, AlphaSort runs the industry-standard sort benchmark in seven seconds. This beats the best published record on a 32-cpu 32-disk Hypercube by 8:1. On another benchmark, AlphaSort sorted more than a gigabyte in a minute.AlphaSort is a cache-sensitive memory-intensive sort algorithm. It uses file striping to get high disk bandwidth. It uses QuickSort to generate runs and uses replacement-selection to merge the runs. It uses shared memory multiprocessors to break the sort into subsort chores.Because startup times are becoming a significant part of the total time, we propose two new benchmarks: (1) Minutesort: how much can you sort in a minute, and (2) DollarSort: how much can you sort for a dollar.

To achieve high concurrency in a database system has meant building a system that copes well with important special cases. Recent work on multi-level systems suggest a systematic path to high concurrency. A multi-level system using locks permits restrictive low level locks of a subtransaction to be replaced with less restrictive high level locks when sub-transactions commit, enhancing concurrency. This is possible because sub-transactions can be undone via high level compensation actions rather than by restoring a prior lower level state. We describe a recovery scheme, called Multi-Level Recovery (MLR) that logs this high level undo operation with the commit record for the subtransaction that it compensates, posting log records to only a single log. A variant of the method copes with nested transactions, and both nested and multi-level transactions can be treated in a unified fashion.

Providing high concurrency in B+-trees has been studied extensively. But few efforts have been documented for combining concurrency methods with a recovery scheme that preserves well-formed trees across system crashes. We describe an approach for this that works for a class of index trees that is a generalization of the Blink-tree. A major feature of our method is that it works with a range of different recovery methods. It achieves this by decomposing structure changes in an index tree into a sequence of atomic actions, each one leaving the tree well-formed and each working on a separate level of the tree. All atomic actions on levels of the tree above the leaf level are independent of database transactions, and so are of short duration.

The Time-Split B-tree is an integrated index structure for a versioned timestamped database. It gradually migrates data from a current database to an historical database, records migrating when nodes split. Records valid at the split time are placed in both an historical node and a current node. This implies some redundancy. Using both analysis and simulation, we characterise the amount of redundancy, the space utilization, and the record addition (insert or update) performance for a spectrum of different rates of insertion versus update. Three splitting policies are studied which alter the conditions under which either time splits or key space splits are performed.

A new multiattribute index structure called the hB-tree is introduced. It is derived from the K-D-B-tree of Robinson [15] but has additional desirable properties. The hB-tree internode search and growth processes are precisely analogous to the corresponding processes in B-trees [1]. The intranode processes are unique. A k-d tree is used as the structure within nodes for very efficient searching. Node splitting requires that this k-d tree be split. This produces nodes which no longer represent brick-like regions in k-space, but that can be characterized as holey bricks, bricks in which subregions have been extracted. We present results that guarantee hB-tree users decent storage utilization, reasonable size index terms, and good search and insert performance. These results guarantee that the hB-tree copes well with arbitrary distributions of keys.

A multiattribute index structure called the hB-tree is introduced. The hB-tree internode search and growth processes are precisely analogous to the corresponding processes in B-trees. The intranode processes are unique. A k-d tree is used as the structure within nodes for very efficient searching. Node splitting requires that this k-d tree be split. This produces nodes which do not represent brick-like regions in k-space but that can be characterized as holey bricks, i.e. bricks in which subregions have been extracted. Results are presented that guarantee hB-tree users decent storage utilization, reasonable-size index terms, and good search and insert performance regardless of key distribution.>

We present an access method designed to provide a single integrated index structure for a versioned timestamped database with a non-deletion policy. Historical data (superceded versions) is stored separately from current data. Our access method is called the Time-Split B-tree. It is an index structure based on Malcolm Easton's Write Once B-tree.

A bounded-disorder (BD) file is one in which data are organized into nodes that are indexed, e.g., by means of a B-tree. The data nodes are multibucket nodes that are accessed by hashing. In this paper we present two important improvements to the BD organization as originally described. First, records in a data node that overflow their designated primary bucket are stored in a single overflow bucket which is itself a bucket of the data node. Second, when file space needs to be increased, partial expansions are used that employ elastic buckets. Analysis and simulation results demonstrate that this variant of the BD organization has utilization, random access performance, and file growth performance that can be competitive with good extendible hashing methods, while supporting high-performance sequential access. The simplicity of the organization results in simple algorithms for realizing the organization.

A new way to increase file space in dynamically growing files is introduced in which substantial improvement in file utilization can be achieved. It makes use of partial expansions in which, instead of doubling the space associated with some part of the file, the space grows at a slower rate. Unlike previous versions of partial expansion in which the number of buckets involved in file growth is increased by less than a factor of two, the new method expands file space by increasing bucket size via “elastic buckets.” This permits partial expansions to be used with a wide range of indexed files, including B-trees. The results of using partial expansions are analyzed, and the analysis confirmed by a simulation study. The analysis and simulation demonstrate that the file utilization gains are substantial and that fears of excessive insertion cost resulting from more frequent file growth are unfounded.

A new key associative access method, called the bounded disorder method, is described. The method uses a combination of hashing and tree indexing. The method has very good random access performance, being comparable to the best hashing methods if its small index is stored entirely in main memory. The method's advantage compared with hashing is that range searches are possible while searching only a portion of the file proportional to the size of the range. It is possible to control index size by controlling node size. Node size can be increased without increasing the amount of data transferred during a random probe. Further, increasing node size has only a minor effect on key sequential access performance. Even quite large nodes, so long as they can be read into memory in their entirety, have good key sequential performance. The bounded disorder method is the only one of the methods employing large nodes that can cope well with arbitrary key distributions. These properties make the bounded disorder method a good choice as the only access method of a data base system.

A new file organization is proposed that combines the advantages of digital B-trees and extendible hashing methods into one organization that can be used universally. The method, like these predecessors, relies on digital searching. The key notions are: (i) that multipage nodes are addressed by the root and can have both data and index entries, the mix of entries changing over time; and (ii) that these nodes can be doubled with file growth and, when this occurs, data nodes at the next level of the tree are absorbed into the pages of these nodes, frequently keeping data closer to the root and simultaneously improving utilization. The result is an unbalanced tree that we call a digital lopsided tree or DL-tree. The paper describes DL-trees and their operations, and examines their properties. The most important engineering issues involve the doubling process and the methods used to optimize the tree properties. Ways of dealing with these issues are suggested.

Bounded index exponential hashing, a new form of extendible hashing, is described. It has the important advantages over most of the other extendible hashing variants of both (i) providing random access to any record of a file in close to one disk access and (ii) having performance which does not vary with file size. It is straightforward to implement and demands only a fixed and specifiable amount of main storage to achieve this performance. Its underlying physical disk storage is readily managed and record overflow is handled so as to insure that unsuccessful searches never take more than two accesses. The method's ability to access data in close to a single disk access makes it possible to organize a database, in which files have a primary key and multiple secondary keys, such that the result is a significant performance advantage over existing organizations.

A new method of organizing index entries in nodes of a B-tree is presented. The method is designed specifically to work with variable length keys. Thus it is particularly suited to take advantage of the variable length entries that result when key compression techniques are used. The paper analyses the characteristics of compressed keys. Based on this analysis, it is shown that the method results in significant space savings, leading to reduced disk accesses during random searches of a B-tree organized file. The search algorithms are shown to be competitive with the best of previous methods for treating variable length entries.

A new algorithm is presented for avoiding system deadlocks. Because its performance has little dependence on the number of lockable resources, it is particularly well suited to use in data base systems which may have millions of individually lockable records. A further advantage is that both exclusive and shared locking are accommodated. The algorithm is presented in some detail and its performance and functional characteristics discussed.