Flash-aware Database Transactions

Over the past 40 years, hard disks, the traditional building block of storage systems, have become increasingly slower when compared to the other system components such as the main memory and the CPU. Hard disks face mechanical constraints that cause their I/O bandwidth to lag behind capacity growth, while the access latency has remained virtually unchanged for the past 20 years. The growing gap between the main memory and the persistent storage brought us to a point where I/O accesses are the main bottleneck that limits the performance of database management systems. Several new solid-state storage technologies have been under development and are now commercially successful, with NAND flash memory being the most mature. Such technologies store data durably, have no mechanical constraints to limit their I/O performance, and can bridge the growing gap between the main memory and the persistent storage. Solid-state drives, however, have very different characteristics compared to hard disks, making it challenging to integrate such technology. For decades, database management systems have been implicitly developed and optimized around the model of a slow rotating hard disk. In this thesis, we focus on transactional database workloads composed of large numbers of small concurrent queries. Transactional workloads generate large numbers of scattered I/O requests at the level of the storage system that are traditionally challenging for hard disks to service. Solid-state drives, on the other hand, are a much better suited technology as they service natively I/O requests in parallel and their performance is not constrained by access locality. The approach we take in this thesis is to traverse the I/O stack of a database management system, i.e. the major software layers that define how data is stored and accessed, and show how these components can, with careful consideration of flash behavior and through novel algorithms, make efficient use of flash-based storage devices. The methodology we use is to observe the data access patterns and the data access frequencies at each level of the I/O stack and design new algorithms and data structures that match the characteristics of the workload with the constraints of flash memory. We use a bottom up approach to revisit the Storage Device, the Storage Manager, and the Caching layers of a data management system and show how each component can better exploit flash technology. At the level of the Storage Device, we show how a solid-state drive can minimize the overhead of storing data on the raw flash chips by exploiting the write skew present in real-life transactional workloads. We then introduce a log-structured data placement policy for the Storage Manager of a database system that can transparently adapt the data access pattern to eliminate all random I/O writes that are problematic for flash solid-state drives. Finally, we propose an architecture for the Caching layer that allows database systems to efficiently move data between main memory and a fast solid-state drive without having to incur the large overhead and limitations of the traditional buffer pool design.

Design and implementation of an efficient data stream processing system

Ali Salehi

In standard database scenarios, an end-user assumes that all data (e.g., sensor readings) is stored in a database. Therefore, one can simply submit any arbitrary complex processing in the form of SQL queries or stored procedures to a database server. Data stream oriented applications are typically dealing with huge volumes of data. Storing data and performing off-line processing on this huge dataset can be costly, time consuming and impractical. This work describes our research results while designing and implementing an efficient data management system for online and off-line processing of data streams in the field of environmental monitoring. Our target data sources are wireless sensor networks. Although our focus is on a specific application domain, the results of this thesis are designed in a generic way, so that they can be applied to wide variety of data stream oriented applications. This thesis starts by first presenting the state-of-the-art in data stream processing research specifically window processing concepts, continuous queries, stream filtering query languages and in-network data processing (particular focus on TinyOS-based approaches). We present key existing data stream processing engines, their internal architecture and how they are compared to our platform, namely Global Sensor Network (GSN) middleware. GSN middleware enables fast and flexible deployment and interconnection of sensor networks. It provides simple and uniform access to a comprehensive set of heterogeneous technologies. Additionally, GSN offers zero-programming deployment and data-oriented integration of sensor networks and supports dynamic re-configuration and adaptation at runtime. We present the virtual sensor concept, which offers a high-level view of arbitrary stream data sources, its powerful declarative specification and query tools. Furthermore, we describe design, conceptual, architectural and optimization decisions of GSN platform in detail. In order to achieve high efficiency while processing large volumes of streaming data using window-based continuous queries, we present a set of optimization algorithms and techniques to intelligently group and process different types of continuous queries. While adapting GSN to large scale sensor network deployments, we have encountered several performance bottlenecks. One of the challenges we faced was related to scalable delivery of streaming data for high data rate streams. We found out that we could dramatically improve the performance of a query processor by performing simple grouping of user queries hence sharing both the processing and memory costs among similar queries. Moreover, we encountered a similar performance issue while scheduling continuous queries. Problem of efficiently scheduling the execution of continuous queries with window and sliding parameters is not addressed in depth in literature. This problem becomes severe when one considers large volumes of high data rate streams. In these cases, an efficient query scheduler not only increases the performance at least by an order of magnitude but also, decreases the response time and memory requirements. Finally, we present how our GSN platform can get integrated with an external data sharing and visualization framework namely Microsoft's SenseWeb platform. Microsoft's SenseWeb platform, provides a sensor network data gathering and visualization infrastructure which is globally accessible to the end users. This integration (which is initiated by the Swiss Experiment project and demanded by GSN users) not only shows the scalability of GSN platform when combined with optimized algorithms, but also demonstrates its flexibility.

EPFL2010

Flash in a DBMS: Where and How?

Anastasia Ailamaki, Manoussos Gavriil Athanassoulis, Radu Ioan Stoica

Over the past decade, new solid state storage technologies, with flash being the most mature one, have become increasingly popular. Such technologies store data durably, and can alleviate many handicaps of hard disk drives (HDDs). Nonetheless, they have very different characteristics compared to HDDs, making it challenging to integrate such technologies into data intensive systems, such as database management systems (DBMS), that rely heavily on underlying storage behaviors. In this paper, we ask the question: Where and how will flash be exploited in a DBMS? We describe techniques for making effective use of flash in three contexts: (i) as a log device for transaction processing on memory-resident data, (ii) as the main data store for transaction processing, and (iii) as an update cache for HDD-resident data warehouses.

2010

Solid-State Storage and Work Sharing for Efficient Scaleup Data Analytics

Manoussos Gavriil Athanassoulis

Today, managing, storing and analyzing data continuously in order to gain additional insight is becoming commonplace. Data analytics engines have been traditionally optimized for read-only queries assuming that the main data reside on mechanical disks. The need for 24x7 operations in global markets and the rise of online and other quickly-reacting businesses make data freshness an additional design goal. Moreover, the increased requirements in information quality make semantic databases a key (often represented as graphs using the RDF data representation model). Last but not least, the performance requirements combined with the increasing amount of stored and managed data call for high-performance yet space-efficient access methods in order to support the desired concurrency and throughput. Innovative data management algorithms and careful use of the underlying hardware platform help us to address the aforementioned requirements. The volume of generated, stored and queried data is increasing exponentially, and new workloads often are comprised of time-generated data. At the same time the hardware is evolving with dramatic changes both in processing units and storage devices, where solid-state storage is becoming ubiquitous. In this thesis, we build workload-aware data access methods for data analytics - tailored for emerging time-generated workloads - which use solid-state storage, either (i) as an additional level in the memory hierarchy to enable real-time updates in a data analytics, or (ii) as standalone storage for applications involving support for knowledge-based data, and support for efficiently indexing archival and time-generated data. Building workload-aware and hardware-aware data management systems allows to increase their performance and to augment their functionality. The advancements in storage have led to a variety of storage devices with different characteristics (e.g., monetary cost, access times, durability, endurance, read performance vs. write performance), and the suitability of a method to an application depends on how it balances the different characteristics of the storage medium it uses. The data access methods proposed in this thesis - MaSM and BF-Tree - balance the benefits of solid-state storage and of traditional hard disks, and are suitable for time-generated data or datasets with similar organization, which include social, monitoring and archival applications. The study of work sharing in the context of data analytics paves the way to integrating shared database operators starting from shared scans to several data analytics engines, and the workload-aware physical data organization proposed for knowledge-based datasets - RDF-tuple - enables integration of diverse data sources into the same systems.