FATES DATABASE STORAGE
Current database systems use data layouts that can exploit unique features of only one level of the memory hierarchy (cache/main memory or on-line storage). Such layouts optimize for the predominant access pattern of one workload (e.g., DSS), while trading off performance of another workload type (e.g., OLTP). Achieving efficient execution of different workloads without this trade-off or the need to manually re-tune the system for each workload type is still an unsolved problem. The "Fates" database system project answers this challenge.
The Fates Architecture
The goal of the Fates architecture is to offer efficient execution at all levels of memory hierarchy and optimize data layout to improve performance, by exploiting the unique characteristics available at each level. This is done, primarily, by decoupling of the in-memory data layout from the on-disk storage layout. Where traditional database systems are forced to fetch and store unnecessary data as an artifact of a chosen data layout, the Fates database system can request, retrieve, and store just the needed data, catering to the needs of a specific query. This conserves storage device bandwidth, memory capacity, and avoids cache pollution-all of which improves query execution time.
Borrowing from the Greek mythology of The Three Fates–Clotho,
Lachesis, and Atropos–who spin, measure, and cut the thread of
life, the three components of our database system (bearing the Fates'
respective names) establish proper abstractions in the database query
execution engine. These abstractions cleanly separate the functionality
of each component while allowing efficient query execution along the
entire path through the database system.
Clotho ensures efficient query execution at the cache/main-memory level and figures at the inception of a request for particular data. It employs a new in-memory page layout and query-specific organization to offer efficient access to all data. Trade-offs are eliminated as the query engine fetches only the data desired.
The Lachesis database storage manager handles the mapping and access to minipages located within the LBNs of on-line storage devices. It makes I/O execution efficient for concurrent workloads competing for a storage device by using explicit, device-independent performance hints. It elimates the need for manual I/O performance tuning and divides reponsibilities equally amongst the storage devices being accessed.
Atropos is a disk array logical volume manager for the orchestrated and efficient use of disks. This is acheived as Atropos provides logical to physical mapping, issues I/Os to individual disks, and exposes important device attributes to facilitate efficient queries such as track aligned accesses, possible semi-sequential access patterns, and efficient access paths in 2D data structures.
People
FACULTY
Anastassia Ailamaki
Greg Ganger
STUDENTS
Minglong Shao
Publications
- On Multidimensional Data and Modern Disks. Steven
W. Schlosser, Jiri Schindler, Stratos Papadomanolakis , Minglong Shao
Anastassia Ailamaki, Christos Faloutsos, Gregory R. Ganger. Proceedings
of the 4th USENIX Conference on File and Storage Technology (FAST
'05). San Francisco, CA. December 13-16, 2005.
Abstract / PDF [220K]
- MultiMap: Preserving disk locality for multidimensional datasets. Minglong Shao, Steven W. Schlosser, Stratos Papadomanolakis, Jiri
Schindler, Anastassia Ailamaki, Christos Faloutsos, and Gregory R.
Ganger. Technical Report CMU-PDL-05-102. Carnegie-Mellon University,
April 2005.
Abstract / PDF [318K]
- Clotho: Decoupling Page Layout from Storage Organization.
Minglong Shao, Jiri Schindler, Steven W. Schlosser, Anastassia Ailamaki,
Gregory R. Ganger. Proceedings of the 30th VLDB Conference. Toronto,
Canada, 29 August - 3 September 2004. Supercedes Carnegie Mellon University
Parallel Data Lab Technical Report CMU-PDL-04-102, March 2004.
Abstract / PDF [203K]
- Matching Application Access Patterns to Storage Device Characteristics. Jiri Schindler. Carnegie Mellon University Ph.D Dissertation. CMU-PDL-03-109,
May 2004.
Abstract / PDF [1.14M]
- Atropos: A Disk Array Volume Manager for Orchestrated Use of
Disks. Jiri Schindler, Steven W. Schlosser, Minglong Shao, Anastassia
Ailamaki, Gregory R. Ganger. Proceedings of the 3rd USENIX Conference
on File and Storage Technologies (FAST '04). San Francisco, CA. March
31, 2004. Supercedes Carnegie Mellon University Parallel Data Lab
Technical Report CMU-PDL-03-101, December, 2003.
Abstract / PDF [281K]
- Lachesis: Robust Database Storage Management Based on
Device-specific Performance Characteristics.
Jiri Schindler, Anastassia Ailamaki, Gregory R. Ganger. VLDB 03, Berlin, Germany, Sept 9-12, 2003. Also available as Carnegie Mellon University Technical Report CMU-CS-03-124, April 2003.
Abstract / Postscript [510K] / PDF [152K]
- Data Page Layouts for Relational Databases on Deep Memory Hierarchies.
A. Ailamaki, D.J. DeWitt, and M.D. Hill. The VLDB Journal 11(3), 2002.
Abstract / Postscript [977K] / PDF [177K]
Acknowledgements
We thank the members and companies of the PDL Consortium: Amazon, Bloomberg, Datadog, Google, Honda, Intel Corporation, IBM, Jane Street, Meta, Microsoft Research, Oracle Corporation, Pure Storage, Salesforce, Samsung Semiconductor Inc., Two Sigma, and Western Digital for their interest, insights, feedback, and support.
The Three Fates
 |
|
The Triumph of Death, or The 3 Fates Flemish Tapestry (probably Brussels, ca. 1510-1520) The three fates, Clotho, Lachesis and Atropos, who spin, draw out and cut the thread of Life, represent Death in this tapestry, as they triumph over the fallen body of Chastity. This is the third subject in Petrarch's poem The Triumphs. First, Love triumphs; then Love is overcome by Chastity, Chastity by Death, Death by Fame, Fame by Time and Time by Eternity. (click photo for larger view) |