System Programming - Lecture 5, v3 - File Systems and Storage Devices

Summary

1. Why file systems and persistent storage are needed

• Main memory is fast but usually volatile: its contents are lost when power is removed. It is also limited in size and can be too small for large working datasets.
• Persistent devices such as HDDs and SSDs retain data and are generally less expensive per gigabyte than RAM.
• Data that does not fit in memory can still be processed in pieces. The lecture uses external merge sort as an example: sort portions of a large dataset, store them, then merge them. The same general approach appears in database systems such as log-structured merge trees.
• A file system can mean:
  • The collection of files and directories on a computer.
  • The format and structures used to encode files and directories as bytes on storage.
  • Sometimes, informally, a disk partition.
• The lecture emphasizes the second meaning: a file system is a format and set of rules for organizing and interpreting bytes. It provides names, storage structures, supported operations, and often access-control rules.

A file system is software and a format, not hardware. It can be placed over different kinds of byte storage, including RAM. Linux examples include tmpfs and ramfs; FUSE provides a way to implement file systems in user space. SSHFS, for example, makes a remote directory accessible through file operations by proxying them over a network.

2. Devices, drivers, and storage access

The lecture distinguishes three broad device types:

• Character devices: Provide sequential streams, such as keyboards, monitors, and printers.
• Block devices: Allow arbitrary access to addressable regions and have a limited capacity. HDDs and SSDs are the main examples.
• Network devices: Also transfer streams or frames, but have sufficiently different behavior to be treated separately.

A file system does not directly control physical hardware. Drivers connect the software to a device, translating requests into low-level operations such as reading or writing a range of bytes. The kernel commonly represents a device as a linear sequence of bytes; the driver or device controller handles any translation to the hardware’s own addressing scheme.

3. HDDs: mechanics, addressing, and performance

A hard disk drive contains magnetic platters, read/write heads, and a controller. The heads read the magnetic state of tiny regions on a platter and change that state when writing.

• HDDs organize physical locations using concepts such as cylinder, head, and sector (CHS). Sectors are commonly around 512 bytes, so even a request for one byte may involve reading or writing a whole sector.
• The kernel uses logical block addressing (LBA) to treat the device as a linear address space. The controller or driver translates these addresses into the device’s physical layout.
• HDD access is limited by mechanical movement and rotation. Random accesses can incur millisecond-scale delays, while sequential reads and writes are much more efficient.
• A practical optimization is to batch and organize I/O sequentially: combine writes into a larger buffer or read a larger contiguous region and extract the needed parts. This can reduce repeated mechanical movement.
• HDDs are vulnerable to mechanical wear and physical damage. The lecturer notes that ordinary magnets are not generally strong enough to erase an HDD.

4. SSDs: flash memory and write amplification

SSDs have no moving mechanical parts. They use flash-memory cells managed by a controller, which performs substantial work internally.

• A flash cell stores charge in an insulated structure. In simplified terms, whether charge is present represents the stored state.
• SSDs read and write in pages, while groups of pages form larger blocks. As with HDD sectors, a small logical request may require operating on a larger unit.
• A page generally cannot simply be overwritten in place. To update data, the SSD writes the updated version elsewhere and marks the old version invalid. It later copies still-valid pages and erases a whole block to reclaim space.
• This process creates write amplification: one logical write can cause multiple physical writes. The controller also performs garbage collection and wear leveling, distributing writes to help the device’s cells wear more evenly.
• Flash cells have a finite write lifetime. SSDs are usually faster than HDDs, especially for random access, but remain more costly per unit of capacity. Sequential access is still beneficial.

5. How file systems organize data

The lecture compares two file-system designs:

• FAT: Files are represented as chains of blocks, with each block identifying the next block. This is straightforward to implement, but files can become fragmented as they are created, extended, and deleted. Fragmentation can make HDD access especially inefficient.
• Ext2: Files and directories are described by inodes, which store metadata and references to data blocks. Ext2 uses direct references for smaller files and several levels of indirection for larger ones. The file system divides storage into block groups and uses bitmaps to locate free blocks and free inode entries efficiently. Copies of key metadata, including the superblock, help with recovery.

In Linux, the term inode is used more broadly for a file-system entry, even when the underlying file system is not Ext2.

6. Partitions and file-system identification

The lecture describes how a system can determine what is stored on a device:

• A device may begin with an MBR (Master Boot Record), containing boot-related information and a partition table.
• The partition table records where partitions begin and end and identifies their types. MBR has room for up to four top-level partitions; other partitioning schemes can support additional partitions.
• A file system’s superblock contains identifying metadata, including a magic value that can help the kernel recognize the file-system type.

7. The Virtual File System (VFS)

Different file systems use different internal formats, but applications generally use common operations such as opening, reading, and writing files. The kernel’s VFS provides a common interface between those operations and individual file-system implementations.

• In C, this interface is represented using structures containing function pointers.
• Each file system supplies implementations of the operations it supports.
• Common kernel code can handle much of the file-operation path, branching into a particular file-system implementation only when needed.
• The lecture relates this to file descriptors: a user-space descriptor is an index into a kernel descriptor table, which leads to a file object and, for file-system entries, associated inode information.
• In user space, calls such as stat provide metadata such as entry type, size, permissions, and ownership. The lecture also mentions file-change notification as a possible use of inode-related information.

8. I/O scheduling

If every request went directly to a slow device in the order it arrived, access could be inefficient. An I/O scheduler can reorder or combine requests for a particular device.

The lecture outlines several scheduler designs:

• Linux elevator: Tries to merge adjacent requests and place other requests in an order that reduces unnecessary movement. It can prevent very old requests from being perpetually bypassed, but offers limited latency guarantees.
• Deadline: Maintains a general request queue as well as separate read and write queues with deadlines. It normally uses the more efficient general ordering, but serves requests whose deadlines expire. Reads may receive shorter deadlines, while limits on consecutive reads help prevent writes from being starved.
• Anticipatory scheduler: Waits briefly after certain reads in hopes that a sequential follow-up read will arrive. The lecturer says it was later removed.
• CFQ (Completely Fair Queuing): Uses per-process queues and allocates device time among processes, aiming for fairness while grouping requests.
• BFQ (Budget Fair Queuing): Extends this approach with flexible budgets and priorities.
• NOOP: A minimal scheduler that merges requests but does little else. Its low overhead can suit simple or low-power workloads.

The general lesson is that scheduling can improve device use, but it cannot eliminate the device’s underlying latency.

9. Page cache and buffered I/O

The kernel’s page cache keeps file data in RAM, indexed by its location on the device.

• On a read, the kernel checks the cache first. If the data is present, it can be returned without accessing the device. Otherwise, the kernel reads it from storage and caches the result.
• Writes are commonly buffered in memory and written to the device later. This can make writes faster and combine or eliminate redundant writes.
• The lecture distinguishes write policies: bypassing or invalidating the cache, writing through to both cache and device, or writing back later. It notes that fsync can be used when an application needs to request that buffered data be flushed.
• The lecturer cautions that cached or buffered writes do not necessarily mean the data has already reached physical storage.
• Buffering can also occur in user-space libraries—for example, formatted output may be held until a newline or buffer threshold.

10. Homework and key takeaways

The assigned homework is to implement a simple in-memory file system using a provided API resembling open, close, read, and write. The implementation is to:

• Store data only in memory, not on disk.
• Support files but not directories.
• Represent files using sequences of blocks, in a manner inspired by FAT.
• Fill in the provided functions whose implementations are missing.

The lecture’s central practical lessons are that file systems are software formats layered over storage, device characteristics shape performance, sequential I/O is generally advantageous, and the kernel uses common interfaces, scheduling, and caching to manage the differences among storage devices.

Speakers and sources featured

• Speaker: One lecturer or instructor; no personal name is given in the subtitles.
• Technical systems and examples referenced: Linux kernel and its VFS, drivers, file-system and I/O-scheduler implementations; FAT and Ext2; Minix; FUSE and SSHFS; tmpfs and ramfs; MBR and GPT; and database examples including Tarantool, MySQL/MyRocks, and RocksDB.
• Additional speakers or interviewees: None are featured in the subtitles.