M09-File Systems - Tagged

CS 439 Principles of Computing Systems

Overview of File System Design Components

• File System Design Elements

• User Interface and Interaction

• Permissions & Security Considerations

• Accounting and Resource Management

• Reliability and Backup Strategies

• Data Layout and Storage Performance

• File System Compression and Logging

Key Elements of File System Design

File System API

• Functions: read, write, seek, create

• Naming: Hierarchical directory structure

• User Interface: Easy navigation

• Permissions: rwxrwxrwx (Read, Write, Execute)

• Accounting: Maintenance of quotas

• Reliability: Uses log-based structures

• Backup: Full and incremental back-ups

• Security: Encryption at file and volume levels

• Resilience: Overcoming failures

• Data Layout: Organizational structure of data

• Blocking & Unit of Storage: Storage management

• Performance: Attuned to specific hardware (e.g., SSD optimization)

• Versioning: Mechanisms that allow file recovery

• Basic Implementation: Underlying coding structure

• Compression: Techniques like Zlib on file level

Examples of File Systems

MacOS APFS

• API: read, write, seek, create

• Structure: Hierarchical directory

• Permissions: rwxrwxrwx

• Accounting: quotas for resource usage

• Reliability: log-based architecture

• Backup: supports full and incremental changes

• Security: encryption at both file and volume level

• Resilience: Innovative recovery options

• Data Layout and Performance: Optimized for SSD

• Versioning: Integrated with Time Machine

• Basic Implementation: Zlib for compression at the file level

ZFS

• API: read, write, seek, create

• Directory Structure: Hierarchical

• Permissions: rwxrwxrwx

• Accounting: quotas

• Reliability: mirroring and RAID-Z features

• Backup: full/incremental changes

• Security: block-level encryption

• Resilience and Performance: Advanced storage management

• Versioning: Snapshot functionality

• Basic Implementation: block-level compression strategies

Detailed Discussion

Flat File System Concept

• Implements a simplistic file system without complex naming

• Allows control for upper software layers

• Maintains attributes: location, size, modified dates, user info, protection

Flat File System Examples

Example 1: Contiguous Allocation

• Files allocated in contiguous storage blocks

• Pros: Fast read/write operations

• Cons: Disk space fragmentation; challenging for file growth

Example 2: Linked Allocation

• Files form linked lists of blocks

• Pros: Adapts easily for file size changes; avoids fragmentation

• Cons: Slower random access due to traversal requirements

Example 3: File Allocation Table (FAT)

• Used approach with a separate table for links between blocks

• Facilitates organized block management

Example 4: Indexed Allocation

• Uses multiple indexing strategies for access

• Efficient management and retrieval of files

Adding Permissions and Features

• I-nodes (index nodes) hold information per file: user ID, last accessed, modified dates, protection bits, type, size

Free Space Management Strategies

• Bit Vectors: Simple approach using bits for block availability

• Linked Lists: Chains all free blocks in a list for management

• Challenges: Managing metadata and efficiency concerns

Advanced Concepts

Sparse Files

• Files with "holes" allowing efficient storage of data

• Challenges implementation via sequence or linked allocations

File Blocks

• Size isn't uniform (e.g., Linux, APFS)

• Trade-offs between performance, efficiency, storage capacity

File Extents

• Allocating files in consecutive groups for efficiency.

• Employed by modern file systems like EXT4, APFS

SSD Optimizations

• Utilize low latency features of SSDs.

• Use compression to minimize data writes.

• Implement TRIM commands for enhanced performance.

Naming Structures and Hierarchies

• File names mapped to inodes in a directed acyclic graph

• Special names: use '/'; support hard and soft links

Hard Links and Soft Links

• Hard links let files share the same inode references

• Soft links indicate symbolic naming, allowing pointers to files

• Care must be taken to avoid cycles in naming structures

Data Integrity and Reliability Issues

• Challenges with sequential file updates leading to inconsistencies

• Power failures can disrupt operations creating corruption

Logging and Recovery Techniques

General Logging Process

• Log operations sequentially to track actions taken in the file system

• Write "commit" records post-operation, ensuring data accuracy

Logging for SSDs

• Need for compatibility with existing systems

• Replication of efforts needs managed to avoid write amplifications

Failure Recovery Procedures

• Check logs for current states

• Confirm discrepancies and correct using logged operations

Implementation Considerations

• Resource management for logs critical

• Balancing write durability versus read performance

• Measuring impacts on throughput and accuracy with logging strategies.