18-746/15-746: Storage Systems (Spring 2013)

For some class meetings, readings will be assigned. Usually, these readings will consist of relevant technical papers, articles or instructor-prepared notes. Paper copies of assigned readings and notes will be provided in class and online. However, please note that online versions of the readings are only available when accessed from a 128.2.* (CMU) IP address or a local-only CMU IP address.

The readings listed should be read BEFORE class on the assigned day.

April 17: Guest speaker

The Hadoop Distributed File System, Konstantin Shvachko, Hairong Kuang, Sanjay Radia, Robert Chansler, 20th IEEE Conference on Massive Data Storage (MSST), 2010.

April 15: Guest speaker

Optimizing a hybrid SSD/HDD HPC storage system based on file size distributions. Brent Welch, Geoffrey Noer. 29th IEEE Conference on Massive Data Storage (MSST'13), May 6-10, 2013, Long Beach, CA. (pdf)
Scalable performance of the Panasas Parallel File System. Brent Welch, Marc Unangst, et al. USENIX Conference on File and Storage Technology (FAST08), February 2008 (pdf).

April 10: Guest speaker (no readings)

April 8 (L17): Multi-core issues for FS/storage

An Analysis of Linux Scalability to Many Cores. Silas Boyd-Wickizer, Austin T. Clements, Yandong Mao, Aleksey Pesterev, M. Frans Kaashoek, Robert Morris, and Nickolai Zeldovich. Appears in OSDI 2010. (pdf)
Recommended optional reading:
- Ryan Johnson, Ippokratis Pandis, Nikos Hardavellas, Anastasia Ailamaki, and Babak Falsafi, "Shore-MT: A Scalable Storage Manager for the Multicore Era," EDBT'09, March 24-26, 2009. (pdf)

April 3 (L16): More reliability techniques

Architectures and Algorithms for On-Line Failure Recovery in Redundant Disk Arrays. Mark Holland, Garth A. Gibson, and Daniel P. Siewiorek. Appears in the Journal of Distributed and Parallel Databases, Vol. 2, No. 3, July 1994. (available here)
Scalable performance of the Panasas Parallel File System. (from Lecture 14 below).

April 1 (L15): Storage for data-intensive computing

The Google File System. Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung. Appears in ACM Symposium on Operating Systems Principles (SOSP), 2003. (pdf)
Bigtable: A Distributed Storage System for Structured Data. Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber. Appears in USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2006. (pdf)
Recommended optional reading:
- MapReduce: Simplified Data Processing on Large Clusters. Jeffrey Dean and Sanjay Ghemawat. Appears in USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2004. (pdf)

March 27 (L14): Parallel File Systems

GPFS: A Shared-Disk File System for Large Computing Clusters. Frank Schmuck and Roger Haskin. Appears in FAST, January 2002. (pdf)
Scalable performance of the Panasas Parallel File System. Brent Welch, Marc Unangst, et al. Appears in FAST, February 2008. (pdf)

March 25 (L13): CloudFS and more Distributed file systems and NAS Interfaces, cont'd

Same readings as Lecture L12.
Recommended optional reading:
- Serverless Network File Systems (xFS). Thomas E. Anderson, Michael D. Dahlin, Jeanna M. Neefe, David A. Patterson, Drew S. Roselli, Randolph Y. Wang. Appears in the ACM Transactions on Computer Systems, Vol. 14, No. 1. February 1996. (pdf)

March 18 (L12): CloudFS and more Distributed file systems and NAS Interfaces

The Design and Implementation of the 4.4BSD Operating System (Marshall Kirk McKusick, Keith Bostic, Michael J. Karels, and John S. Quarterman, 1996)

Chapter 9 (The Network Filesystem) (pdf)

Recommended optional reading:
- Scale and Performance in a Distributed File System. John H. Howard, Michael L. Kazar, Sherri G. Menees, David A. Nichols, M. Satyanarayanan, Robert N. Sidebotham, Michael J. West. Appears in the ACM Transactions on Computer Systems, Vol. 6, No. 1, Pages 51-81. February 1988. (pdf)
Optional reading:
- Optional reading: "NFS Version 3 Protocol Specification" (RFC 1813: B. Callaghan, B. Pawlowski, P. Staubach, June 1995) (txt)

March 6 (L11): Backup and disaster recovery

Designing for disasters. Kimberly Keeton, Cipriano Santos, Dirk Beyer, Jeffrey Chase, John Wilkes. Appears in the Proceesings of the Third Usenix Conference of File and Storage Technologies (FAST'04). (pdf)

February 26 and 28 (L10): Flash Storage

DFS: A File System for Virtualized Flash Storage, William K. Josephson, Lars A. Bongo, David Flynn, Kai Li. Published in FAST 2010.
Recommended: Operating System Support for NVM+DRAM Hybrid Main Memory, Jeffrey C. Mogul, Eduardo Argollo, Mehul Shah, Paolo Faraboschi. Published in Hotos 2009.
Recommended: Principles of Operation for Shingled Disk Devices", Garth Gibson, Greg Ganger. Published as Carnegie Mellon PDL Technical Report CMU-PDL-11-107.

February 20 (L9): Disk array systems

RAID: High-Performance, Reliable Secondary Storage (Peter M. Chen, Edward K. Lee, Garth A. Gibson, Randy H. Katz, and David A. Patterson, 1994) (same as L8)

February 18 (L8): Disk array organization

RAID: High-Performance, Reliable Secondary Storage (Peter M. Chen, Edward K. Lee, Garth A. Gibson, Randy H. Katz, and David A. Patterson, 1994)(pdf)

February 11 (L7): Caching and FS integrity

Soft Updates: A Solution to the Metadata Update Problem. Gregory R. Ganger, Markall Kirk McKusick, Craig A.N. Soules, Yale N. Patt. ACM Transactions on Computer Systems. May 2000. (pdf)
Practical File System Design with the Be File System (Dominic Giampaolo, 1999)

Chapter 7 (Journaling) (pdf)

Verifying File System Consistency at Runtime. Daniel Fryer, Kuei Sun, Rahat Mahmood, TingHao Cheng, Shaun Benjamin, Ashvin Goel, Angela Demke Brown. Conference on File and Storage Technologies (FAST), 2012. (pdf)

February 6 (L6): On-disk data layout

The Design and Implementation of the 4.4BSD Operating System (Marshall Kirk McKusick, Keith Bostic, Michael J. Karels, and John S. Quarterman, 1996)

Chapter 8 (Local filestores) (pdf)

TableFS: Enhancing Metadata Efficiency in the Local File System. Kai Ren and Garth Gibson. Published as Technical Report CMU-PDL-13-102, January 2013. (pdf)

February 4 (L5): File system organization

Practical File System Design with the Be File System. Dominic Giampaolo. 1999.

Chapter 2 (What is a file system?) (pdf)

UNIX Internals: The New Frontiers. Uresh Vahalia. 1996.

Chapter 8 (File system interface and framework) (pdf)

January 30 (L4 and L4a): Disk drive firmware and request optimization

An Introduction to Disk Drive Modeling. Chris Ruemmler and John Wilkes, 1994. (pdf)
Microbenchmark-based Extraction of Local and Global Disk Characteristics. Nisha Talagala, Remzi H. Arpaci-Dusseau, and David Patterson (pdf)
Scheduling Algorithms for Modern Disk Drives. Bruce L. Worthington, Gregory R. Ganger, and Yale N. Patt. Appears in the Proceedings of the ACM Sigmetrics Conference. May, 1994. (ps)

January 23 and 28 (L3): Disk drive operation

Digital Large System Mass Storage Handbook. Paul Massiglia. 1986.

Chapter 2 (Magnetic disk technologies): read pages 2-1 to 2-20 (pdf) and 2-38 to 2-52 (pdf).
Chapter 12 (System considerations): read pages 12-1 to 12-11. (pdf)

January 16 (L2): Metrics of I/O system quality

Computer Architecture: A Quantitative Approach, 3rd ed. John L. Hennessy and David A. Patterson. 2002. (pdf)

Section 7.7: "I/O performance measures"
Section 7.8: "A Little queuing theory"
Section 7.9: "Benchmarks of storage performance and availability"

MTBF Description, Kevin Dally. 1995. (txt)
Probability Refresher. Mor Harchol-Balter. 2000. (pdf)

January 14 (L1): Introduction and overview of storage systems

This first meeting will be more than just organizational in nature. We will discuss how the class is going to work and what will (and won't) be covered. See the 15-746/18-746 overview for a recap of the general information. We will also dive into the course by overviewing the area of storage systems.