Class 17: Flash!

Posted: Tue 01 April 2014

Because of insufficient "MU" answers on Exam 2, there is an Extra Exam required for all students and due at 11:69pm today, 1 April. (Note: if you have not yet received a theory textbook, you can skip the theory questions 1 and 2, but since cs3330 is a prerequisite for this course, everyone is expected to answer the architecture questions 3 and 4.) Note: please make sure you follow RFC 3514 when downloading the exam.


Part III of the OSTEP Book is all about persistent storage. None of these readings are "required", but some of these chapters may be helpful to you in designing and implementing your file system for PS4 (and the others are interesting also).

Dialogue on Persistence
I/O Devices

How the OS communicates with devices.
Hard Disk Drives
How to store data on hard drives to minimize seek times.
Redundant Arrays of Inexpensive Disks
We cover this some in class tody, but the chapter has lots of details we don't get into.
Files and Directories
File System Implementation
This is the section you will find most directly relevant to PS4 (although your filesystem can be even simpler than the very simple file system described in the section.
Locality and the Fast File System
Crash Consistency: FSCK and Journaling
Log-structured File Systems
Data Integrity and Protection
Summary Dialogue

Making a File

Requirements for Modern File Systems

Improving Reliability


It's for people who have Mac OS, who have any data, and who really like their data. Whether on a single-drive laptop or on a massive server, it'll store your petabytes with ragingly redundant RAID reliability, and it'll keep the bit-rotted bleeps and bloops out of your iTunes library.

Merkle Trees

When one block changes, how many hashes need to be updated?


David Patterson, Garth Gibson, and Randy Katz. A Case of Redundant Arrays of Inexpensive Disks (RAID) (SIGMOD 1988)

With RAID 3, if Disk 2 fails, how can it be recovered?

Adaptive Replacement Cache

What should cause the recently used cache size to increase?

What should cause the recently used cache size to shrink?

Modern Storage Systems

Fujio Masuoka, Masaki Momodomi, Yoshihisa Iwata, and Riichiro Shirota. New Ultra High Density EPROM and Flash EEPROM with NAND Structure Cell. IEEE Electron Devices Meeting, 1987.

What does it mean for storage to be solid state?

What does it mean for storage to be non-volatile?

How should file systems be re-designed to account for SSDs and networked storage?

Log-Structured File Systems

Mendel Rosenblum and John K. Ousterhout, The Design and Implementation of a Log-Structured File System. 13th Symposium on Operating System Principles (SOSP) 1991.

What are the advantages of doing all writes sequentially on the disk?

How is garbage collection different for a LSFS compared to in-memory garbage collection?

Flash Memory File Systems

Why is a Log-Structured File System more appropriate for flash memory than a traditional Unix-style file system?

Bunny Huang, On Hacking MicroSD Cards, December 2013.

For more interesting hardware hacks, see Karsten Nohl's talk on SIM Card Hacking from last year's course, and his public talk:

comments powered by Disqus