File Systems

By Zach Bordofsky, Kevin Wu, and Chris Zhu

File Systems: IBM General Parallel File System (GPFS)

The GPFS is made up of 120 Petabytes of information stored across 200,000 hard drives.

Small drives are used to reduce cost and increase parallelism.

Multiple CPU's will be needed to control this, so that there is not a bottleneck for speed around the CPU. Instead the work is spread across multiple CPUs with access the drives.

Techniques to make this work:

• Striping: Store parts of files across different blocks so that one file is not all in one place. This increases the ability to run in parallel.
• Distributed Metadata: Spread metadata for files across many CPU;s so that many people can find files at one time. If all metadata was in one place, that CPU would get overwhelmed with requests to access and find files.
• Partition Awareness: Create copies of our files so that if a part of a network (like Chicago) goes down, people who aren't on the down part of the network will still be able to operate.
• Distributed Locking: Locks must exist across multiple CPU's to allow people writing or reading a file to be able to grab a lock.
• Efficient Directory Indexing: Because the system as a large number of files, a more efficient data structure must be used to store all of the files.

File System Definition:

Abstract organization of data on secondary storage (usually slow, big, persistent).

How abstract it is is quite controversial, as while there is agreement about some commands like read, write, delete, and allocate space, but disagreement about including search.

Paul Eggert's File System

In 1974, Eggert's professor told him, "Paul, I want you to build a file system for my UNIX competitor." At the time he knew nothing about operating systems because there were no OS classes.

Limitations on hardware during the old days:

• 16 Kilobytes of RAM
• 700 Gigabyte disk drive
• 512 byte sector

First he divides the disk into two regions. The first part of the file system would keep track of where all the files were which is essentially a table. Each entry of the table has 3 parts which would be kept track of in three columns.

1. Name
2. Starting sector
3. Size of the file in bytes

Notice that there are different units for the last two parts, sector count and byte count. There is a 2 byte sector count which contains the value of the sector number of the first sector in the file and there is a two byte byte count so we know how many leftover bytes we have.

Now he needs to think how big he wants to make the table. Eggert accomplishes this by scratching his head and randomly picking two sectors to be the size.

Next he makes the name length 8 bytes. If you have shorter than 8 bytes, that’s cool. Just use 0 fills (essentially add a bunch of nullbytes until you reach 8 bytes and then put it into the table). If you have longer than 8 bytes, you lose.

Now we have 12 bytes originally. At the time, Eggert also used 4 secret bytes (which he may have used as a timestamp or for some other reason) so he now has a total of 16 bytes. This results in 2^5 directory entries per sector which means the file system can store 2^6 total files.

~Other Details~

How do I represent a directory entry for a file that's not there? Eggert used all 0's to mean that it’s not in use and the user can use it if they want to make a file. This means a file name has to be at least one byte long. Empty file names are not allowed because the directory entry would be all 0's.

Downsides:

• Number of files limited by code (suppose you need more files just change the sector total count).
• Internal fragmentation of up to 511 bytes (on average 255.5 bytes).
• External fragmentation
• You have to tell OS how big the file is. (requires pre-allocation)

Internal fragmentation occurs because each file is stored into one sector regardless of its size so then there is a lot of wasted space if you store small files. External fragmentation is a major flaw with Eggert's file system which caused him to also tell his professor to throw away his garbage code. Essentially what happens is that pretend you're using the file system for a while. You're allocating files... reading, writing, deleting. The file system grows and shrinks. At some point, you'll have spaces that aren't being used in between files (essentially holes). When you have a lot of these holes, you're wasting a lot of space which can't be used by a bigger file than the holes. Essentially there is no way to "combine the holes" in order to save memory and allocate space for a file. As Eggert said, "External fragmentation is free space you can use but you can't use it for a particular request."

Pros

• Simple
• Sequencial access is fast. (it's efficient to read the next sector vs a random one)

Real time people care about predictability a lot and sequential access performance is predictable and can thus trump all flaws. They can place an upper bound on the amount of time it took to read the next sector of a file because they know the longest wait if the disk arm is about the right spot.

FAT File System

Representation of a disk layout in a FAT file system

• Boot Section - This part of the sector is never used
• Super Block - This part of the sector contains meta information of the file system such as the version of FAT that is being used, the size of the file, how many blocks are in use, root directory block number, etc.

File Allocation Table (F.A.T) - This part of the sector is split into 16 bit blocks. Each block will then point to the next FAT block in the file system. There will be a number in the FAT block that will represent something.

FAT Legend:

• -1: Free block
• 0 : End of file (last block in the current file)
• N : This is the index of the next file block in the file.

IMPORTANT things to note about FAT: Since it is using pointers, the file does not have to be in contiguous blocks of memory. However, this is also inconvenient, because how FAT works is that it needs a pointer to the next block which is 4 bytes. This creates the data block size to be 512 bytes - 4 bytes which is no longer a power of two which makes data alignment problems. FAT still has internal fragmentation - a process does not use all of the data in a given sector and it cannot be used by other processes (waste of data).

How does FAT represent directories?

FAT represents directories as files, albeit distinguished and special files. A directory is an array of directory entries which can be represented like this:

Pros of the FAT file system

• no external fragmentation
• external fragmentation - there are enough space on the disk, but it is not contiguous, and therefore, it cannot be allocated.
• FAT does not have external fragmentation because it is solved by the pointers.
• no pre-allocation
• FAT does not need to allocate the space beforehand, it can grow as needed as long we have space.
• number of files are not limited by file system
• FAT keeps creating files as long as we have disk space

Cons of the FAT file system

• loss of sequential access
• This is slow since FAT uses pointers, the disk must keep finding the next block.
• Can be solved by defragmentation, move the blocks until they are continuous, but this in itself is slow and risky to do. This is risky because while you are doing so, you might lose power and lose where you are on reboot causing corruption.
• lseek
• Slow, O(N), because you have to go through the linked list.
• renaming a FAT file
• renaming in the same file directory is easy and cheap: load directory block, find the file, and update its file name.
• However, if you rename it in different directories, you are managing two different blocks of memory, which can go wrong if, during renaming, the power goes out.