skip to main content
Department of Computer Science University of Colorado Boulder
cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
home · events · thesis defenses · 2006-2007 · 

Thesis Defense - Woitaszek


Tornado Codes for Archival Storage
Computer Science PhD Candidate

This thesis examines the application of Tornado Codes, a class of low density parity check (LDPC) erasure codes, to archival storage systems based on massive arrays of idle disks (MAID). The fault tolerance of Tornado Code graphs is analyzed, and it is shown that it is possible to identify and mitigate worst-case failure scenarios in small (96 node) graphs through use of simulations that find and eliminate critical node sets that can cause Tornado Codes to fail even when almost all blocks are present. The resulting graph construction procedure is then used to construct a 96-device Tornado Code stripe storage system with capacity overhead equivalent to RAID 10 that tolerates any 4 device failures. This system is demonstrated to be superior to parity-based RAID.

After establishing the fault tolerance of Tornado Codes, a log-structured extent-based file system is constructed using Tornado Coded stripe storage. The file system is combined with a MAID simulator to emulate the behavior of a large-scale storage system, with the goal of employing Tornado Codes to increase fault tolerance in a power-constrained environment. The effect of power conservation constraints and design choices on system throughput is examined, and a policy of placing multiple data nodes on a single device is shown to increase read throughput at the cost of a measurable decrease in fault tolerance. Finally, the system is implemented on a 100-TB Lustre storage cluster, providing GridFTP accessible storage with higher reliability and availability than the underlying Lustre storage architecture.

Committee: Henry Tufo, Associate Professor (Chair)
John Bennett, Professor
Daniel Connors, Department of Electrical and Computer Engineering
Shivakant Mishra, Associate Professor
Manish Vachharajani, Department of Electrical and Computer Engineering

See also:
Department of Computer Science
College of Engineering and Applied Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
Send email to

Engineering Center Office Tower
ECOT 717
FAX +1-303-492-2844
XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado
Privacy · Legal · Trademarks
May 5, 2012 (13:40)