Transcript File System - Computer Science & Engineering

File System Basics
Adopted from
Fred B. Schneider
Department of Computer Science
Cornell University
1
Agenda
•
•
•
•
•
Definition
Position
Responsibilities
Design Principles
Examples
2
Storing Information
• Applications can store it in the process address
space
• Why is it a bad idea?
– Size is limited to size of virtual address space
• May not be sufficient for airline reservations, banking, etc.
– The data is lost when the application terminates
• Even when computer doesn’t crash!
– Multiple process might want to access the same data
• Imagine a telephone directory part of one process
3
File Systems
• 3 criteria for long-term information storage:
– Should be able to store very large amount of information
– Information must survive the processes using it
– Should provide concurrent access to multiple processes
• Solution:
– Store information on disks in units called files
– Files are persistent, and only owner can explicitly delete it
• Files are managed by the OS
• File Systems: How the OS manages files!
4
File System: Definition
• A software component that imposes structure on
the address space of one or more physical or
virtual disks so that applications may deal more
conveniently with abstract named data objects of
variable size (files). [SNIA]
• A method of storing and organizing computer
files and their data. Essentially, it organizes these
files into a database for the storage, organization,
manipulation, and retrieval by the computer's
operating system. [WIKI]
SNIA: http://www.snia.org/education/dictionary/f/ Wiki: http://en.wikipedia.org/wiki/File_system
5
Storage Hierarchy
6
Abstraction Layer
• Typically, file systems are used on storage
devices (e.g. hard drives) to maintain the
physical locations of files.
• As an important software component of OS, a
file system provides the OS abstraction that
average user is most familiar with
• Files, Directories, Access controls, …
7
Files
• A file is a collection of data with system
maintained properties like
– Owner, size, name, last read/write time, etc.
• Files often have “types” which allow users and
applications to recognize their intended use
• Some file types are understood by the file
system (mount point, symbolic link, directory)
• Some file types are understood by
applications and users (.txt, .jpg, .html, .doc,
...)
8
File Naming
• Motivation: Files abstract information stored on disk
– You do not need to remember block, sector, …
– We have human readable names
• How does it work?
– Process creates a file, and gives it a name
• Other processes can access the file by that name
• Naming conventions are OS dependent
– Usually names as long as 255 characters is allowed
– Digits and special characters are sometimes allowed
– MS-DOS and Windows are not case sensitive, UNIX family
is
9
File Extensions
• Name divided into 2 parts, second part is the
extension
• On UNIX, extensions are not enforced by OS
– However C compiler might insist on its extensions
• These extensions are very useful for C
• Windows attaches meaning to extensions
– Tries to associate applications to file extensions
10
File Attributes
• File-specific info maintained by the OS
– File size, modification date, creation time, etc.
– Varies a lot across different OSes
• Some examples:
–
–
–
–
–
–
–
Name – only information kept in human-readable form
Identifier – unique tag (number) identifies file within file system
Type – needed for systems that support different types
Location – pointer to file location on device
Size – current file size
Protection – controls who can do reading, writing, executing
Time, date, and user identification – data for protection,
security, and usage monitoring
11
Directories
• Directories provide a way for users to organize
their files *and* a convenient way for users to
identify and share data
• Logically directories store information like file
name, size, modification time etc (Not always
kept in the directory though..)
• Most file systems support hierarchical
directories (/usr/local/bin or C:\WINNT)
– People like to organize information hierarchically
12
Directories are special files
• Directories are files containing information to
be interpreted by the file system itself
• List of files and other directories contained in
this directory
• Some attributes of each child including where
to find it
13
Path Name Translation
• To find file “/foo/bar/baz”
– Find the special root directory
– In special root directory file, look for entry foo and
that entry will tell you where foo is
– Read special directory file foo and look for entry bar
to tell you where bar is
– Find special directory file bar and look for entry baz to
tell you where baz is
– Finally find baz
• FS can cache common prefixes for efficiency
14
Basic File Operations
• UNIX
–
–
–
–
–
–
–
–
–
create (name)
open (name, mode)
read (fd)
write(fd)
sync(fd)
seek(fd, pos)
close(fd)
unlink (name)
rename(old,new)
15
Basic File Operations
• Windows
–
–
–
–
–
–
–
–
–
–
CreateFile (name, CREATE)
CreateFile (name, OPEN)
ReadFile (handle)
WriteFile (handle)
FlushFileBuffers(handle)
SetFilePointer(handle)
CloseHandle(handl)
DeleteFile (name)
CopyFile (name)
MoveFile(name)
16
Core Modules
• Data organization
• Freespace management
• Metadata management
17
Design Principles
• Data organization
– Sequentiality
– Spatial Locality
18
“Unwritten Contract”
• Sequential accesses are best, much better than
non-sequential.
• An access to a block near the previous access in
LBN space is usually considerably more efficient
than an access to a block farther away.
• Ranges of the LBN space are interchangeable,
such that bandwidth and positioning delays are
affected by relative LBN addresses but not
absolute LBN addresses.
Source: MEMS-based storage devices and standard disk interfaces: A square peg in a round hole? FAST’04
19
Ext2 FS Data Layout
Source: http://www.linux-tutorial.info/modules.php?name=MContent&pageid=272
20
Freespace Management
• Freespace Allocation and Reclamation
• Linked list of free space
– Just put freed blocks on the end and pull blocks from front
to allocate
– Hard to manage spatial locality
• Bitmap
–
–
–
–
–
Divide all space into blocks
Bit per block (0 = free; 1 = allocated)
Easy to find groups of nearby blocks
Useful for disk recovery
How big? If had 40 GB disk, then have 10M of 4K blocks is
each needs 1 bit then 10M/8 = 1.2 MB for the bitmap
21
Metadata Management
• Metadata: the data used to describe the data
• Superblocks, Block bitmaps, Inode bitmaps,
Directories, …
• Occupies a small amount of storage capacity
• Absorbs a large numbers of IO requests
22
File Buffer Cache
• Cache Data Read
– Exploit temporal locality of access by caching pathname translation
information
– Exploit temporal locality of access by leaving recently accesses chunks
of a file in memory in hopes that they will be accessed again
– Exploit spatial locality of access by bringing in large chunks of a file at
once
• Data written is also cached
– For correctness should be write-through to disk
– Normally is write-behind
• FS periodically walks the buffer cache and “flushes” things older than 30
seconds to disk
• Unreliable!
• Usually LRU replacement
23
File Buffer Cache
• Typically cache is system wide (shared by all
processes)
– Shared libraries and executables and other
commonly accessed files likely to be in memory
already
• Competes with virtual memory system for
physical memory
– Processes have less memory available to them to
store code and data (address space)
– Some systems have integrated VM/FS caches
24
Examples
•
•
•
•
Ext2/Ext3/Ext4 (Linux)
FAT/NTFS (Windows)
HFS/HFS+ (Mac OS)
UFS (FreeBSD)
• In development:
• Btrfs: snapshots, checksums, multi-disk
spanning, optimized for SSD
25
•
•
•
•
•
Disk FS:
Network FS: NFS client-server
Distributed FS: Google FS
Special-Purpose: procfs /proc
……
26
Research Links
• File Systems and Storage Lab (FSL)
– http://www.fsl.cs.sunysb.edu/
– FiST, Tracefs, Avfs, VersionFS, I3FS, RAIF, UnionFS,
NcryptFS,…
• The ADvanced Systems Laboratory (ADSL)
– http://www.cs.wisc.edu/adsl/Publications/
– SDS, D-GRAID, IRON FS, EIO, SQCK, EnvyFS, …
27
Acknowledgement
• http://www.cs.cornell.edu/Courses/cs414/200
4su/slides/11_fsbasics.pdf
28