From first principles
(See also
Filesystems HOWTO∞
A "thought experiment" hoping to derive the broad fundamentals of computer filesystems from nothing but thin air.
Anyone who saw my house would wonder what possessed me to take on the subject of file systems. I hate to throw anything away and I don't like to put stuff in drawers or boxes or cabinets because it's hidden and I tend to forget I have it. So my personal filing system is to constantly refresh my memory of what I have and where it is as I putter around the house. Probably this is not the most efficient use of available storage space.
So, how does one store a
file - say, a picture - in a computer so that it can be found again? Let's see if we can figure out an answer.
First, let's briefly explore the inner workings of a
hard drive since that's the standard repository. To simplify it to its essential elements, the hard drive is a spinning
disc - actually these days most hard drives contain several discs on a common shaft, but let's only consider the simplest case - onto which a stream of bits - 1s and 0s, if you will - can be "written" in some fashion. (Actually a hard drive can be analyzed as a communication channel of indefinite length, but that's beyond our brief.) CDs and DVDs use lasers but pretty much all hard drives write the bits by magnetizing a tiny area of the surface of the disc as it spins beneath a
record head. We'll arbitrarily say that magnetizing with the north pole up is a "one" and down is a "zero;" either way works. A
read head detects the magnetic fields, created by the record head on the surface of the disc, as the disc spins beneath the read head. The electrical signals generated in the read head by the spinning magnetized disc are decoded within the hard drive into ones and zeros. Both the read and record heads are mounted on a common arm which moves them across the surface of the disc, so that any spot on the surface of the spinning disc can be made to pass beneath them. The data is written in concentric circles, called
tracks, as the disc spins beneath the record head. For reasons having to do with performance, hard drives start their tracks at the outer rim of the disc. CD and DVD discs have one track: a continuous spiral several miles long, which starts at the center and reads outward toward the rim of the disc. Go figure.
So, ignoring for now such distractions as communications protocols, formatting, and data types, how could a lump of data, or file (our digitized picture for instance,) be recorded on a hard drive disc so that it can be found and read back?
Well, you
could simply look for an unused area on the hard drive disc, big enough to hold the file, and record the file there. Two immediately obvious implications of that scheme (that I can think of) are, how would you: 1.) find an unused area, and, 2.) find the file again when you wanted it? (The two things appear to have similarities, don't they? Could unused area be thought of as a blank file?) You
could search the disc starting from the beginning each time you wanted to record or read a file, rather like fast-forwarding through a video tape until you found the scene you wanted, but how would you tell if an area of the disc which has previously been written to is now free to use? There must be a better way than that. Okay, how about an index, or centralized record, of files on the disc and their locations. When you want a file you would just look up its location in the index rather than search the hard drive until you stumble across it - the way I find things in my house.
It would seem then that something like an
index, or table of contents, call it what you will, is a necessary beginning of any filing scheme. No matter what the media or how the data is formatted, to find it you start by looking it up in an index.
Here∞'s an article about the evolution of FAT12/16/32 filesystem(s).
Random thoughts on a Multisession DVD filesystem for Puppy Linux
31 May 2006: It seems like the better part of a year since I added anything to this. For several months I've been doing nearly all of my computing with Puppy Linux on a
multisession DVD. It has all the applications I need, and it's been reliable and fast enough for everything I want to do except ripping CDs and converting them to mp3. I convert a lot of audio books from CD to mp3 and the free
RealPlayer does that in Windows at least twice as fast as ripperX does it in Puppy.
What does all this have to do with filesystems? Well, I'm getting to it. It seems that the
Archive in multisession Puppy is only a placeholder. Barry hasn't yet found a way to implement it that he likes. Briefly, multisession Puppy's Archive is intended to be a place to put files that are no longer to be loaded when multisession Puppy boots. At present, when a file is put in the Archive it seems simply to be dropped from Puppy's filesystem. Not only is it not loaded at boot anymore, but there is no record it ever existed anywhere in Puppy. To retrieve it you have to mount the DVD and hunt through the folders of saved sessions for it. Since there can be hundreds of sessions saved on a multisession DVD this can take a while. Naturally I couldn't help but give the matter some thought, in my spare time. The more I pondered it the more it seems the Archive function needs to be an integral part of the design of multisession Puppy's filesystem, so I thought I'd put my thoughts here as a continuation of my maunderings on the general subject of filesystems.
So, let's noodle around with the conceptual design of an imaginary filesystem for running Puppy Linux from a multisession DVD.
(This is just for fun. For a detailed explanation of how Puppy actually works, see Barry Kauler's excellent
How Puppy Works∞
First, a general discussion of the advantages of CDs/DVDs vs hard disks:
Disk is better than tape
As mentioned before, data on CD and DVD (optical) discs is stored on a continuous spiral track several miles long. Similar to recording on tape, data is written to and read from the track in one direction only, moving outward from the center toward the rim of the disk along the spiral, so it seems to me that strategies developed for managing filesystems on tape would also apply to optical disks.
It seems to me that the most obvious operational difference between storing data on the spiral track of an optical disk and storing it on tape is that the optical disk drive can position the write/read head over a randomly chosen address on the disk much faster than a tape drive can get to an address on the tape. The write/read head of a disk drive is a lightweight assembly which can be moved very quickly across the spinning disk until the head is approximately over the desired address on the track, where with any luck it will quickly find the desired spot on the track and then begin reading or recording. Obviously, a disk drive can access an address anywhere at random on the track much quicker than could a tape drive. A tape drive cannot skip over any of the intervening tape. It must pull the tape back or forth through the head until it reaches the desired address.
That would be reason enough to replace tape drives with disk drives, but wait, there's more. An associated advantage disks have over tape is much less wear and therefore potentially greater reliability of both the drive and media. The write/read head never touches the spinning disk, whereas tape must be pulled across the face of the magnetic head of a tape drive, wearing both the tape and the head, not to mention all the bearings and other moving parts necessary to pull the tape past the head with the proper tension. A disk drive has far fewer moving parts and much less movement going on inside. A direct-drive motor spins the disk, eliminating the need for belts and gears. The write/read head only moves across the disk a total of an inch or two, and never touches its surface (or at least it's not supposed to.) As a result, a disk drive wears very little, compared with a tape drive capable of storing the same amount of data, while giving vastly superior performance.
DVDs beat Hard Disks
A hard disk drive can hold more data than hundreds of DVDs, and transfer that data much faster, and hard disk drives do last a long time. On the other hand they don't last forever, and when they fail they tend to do it catastrophically with little or no warning. As a practical matter disks cannot be removed from a hard disk drive, so everything they contain is lost when the drive fails. DVDs are cheap, and can hold many sessions as multisession storage disks. If the drive fails, the disk can be removed, the drive replaced, the disk put in the new drive and the computer restarted to get back in business with at most the loss of only the new files and changes that were in RAM when the drive failed. For the security conscious, or merely paranoid, the disk can be removed from the drive and stored elsewhere, leaving no record in the computer. And I'm pretty sure that DVD drives use less power than hard disk drives, except perhaps when writing. For the way most people use a computer, multisession DVD beats hard disk storage.
DVDs beat CDs
The DVD evolved from the CD. CDs had been around many years by the time DVDs were introduced. Naturally the DVD specification incorporates lessons learned from CDs. Most importantly for this discussion, it provided for multisession use from the start. One DVD holds about five times as much as a CD but only costs about twice as much as a CD of equal quality. DVD burners cost very little more than CD burners, and they write to and read from DVDs faster and more reliably than they do CDs. Physically a DVD is more robust than a CD. The data layer of a CD is on the backside of the polycarbonate (as in Lexan) disk of the CD, protected only by a thin coat of lacquer. The data layer of a DVD is much better protected from damage; DVDs are two polycarbonate disks, each half the thickness of a CD, with the data layer sandwiched in the middle.
Although files on a rewritable (RW) optical disk can be overwritten (called packet writing,) multisession Puppy does not use that feature. By design, once written, anything on a multisession Puppy DVD is there to stay; writing is only done at the end of the track -- until the disk is full.
Master Index to the rescue
The purpose of an operating system is to run application programs. A filesystem that allows for files to be modified is required to run most applications, but if data recorded on a multisession DVD cannot be changed, how can changes to files be recorded? It seems wasteful of disk space, not to mention time, to record the entire file anew each time anything about it is changed. The most obvious solution is to write at the end of the track a new file containing only the changes to the original file (I'll call this new file a fragment,) and keep in a Master Index the locations of the original file and its fragment(s). When the multisession DVD boots, Puppy will look in this Master Index for the address(es) of the original file and its fragment(s) containing changes, and combine them into the latest version of the file. This Master Index is the foundation of our hypothetical filesystem for multisession Puppy.
When our multisession DVD boots, the first thing the BIOS loads into RAM from the DVD is a minimal Linux operating system called isolinux. The BIOS then hands control to isolinux, which loads into RAM the last session that was written to the DVD (everything in the last session will always be loaded into RAM anyway, unless the boot option to skip loading that session is chosen) finds in it the Master Index to see which files to load into RAM from the DVD, and then proceeds through all the previous saved sessions, beginning with the earliest one found in the Master Index, loading from each session only those files and fragments found in the Master Index, and combines them into their final form for use.
This applies to all files loaded by isolinux, even those that comprise the full operating system, vmlinuz, which isolinux loads into RAM but does not pass control to until after all the later fragments have been combined with their original system files. Thus, when Puppy finishes booting from the multisession DVD it is up to date, having incorporated every modification made to the OS since the original iso was burned onto the DVD.
Categorizing the contents of the Master Index
To minimize the amount of RAM the computer needs, disk-based operating systems load most non-system files and programs into RAM only when needed. They get away with this because hard disks transfer data to and from RAM much faster than do optical disks. Multisession Puppy is of course stored on an optical disk, but Puppy Linux is so small (~70MB) that it can quickly load entirely into RAM, and this is what it is designed to do. However, it would be wasteful and inefficient to simply load the entire contents of the multisession DVD into RAM. It would take 4.7GB of RAM to hold everything that could fit on a DVD, most of which might rarely if ever be used (I tend to accumulate files that I never use but just give me a warm feeling knowing they're there,) or might be superseded and useless files and fragments. This suggests dividing the contents of our Master Index into three
categories: one for files that are always loaded into RAM, call them
System files; a second category for files that are loaded at boot if there is enough RAM, according to their size and frequency of use, call them
Intermediate files; and a third category of
Archived files. (A fourth category,
Deleted files, might be a good idea in order to make "undeleting" easy. They could be called Lazarus files, and after a certain amount of time they would be dropped from the Master Index altogether. This could be tied in with the desktop "Trash" icon.)
System files, the first category, would initially consist of all the files in the original Puppy iso, but of course files can be added to or removed from it. For example, to save RAM, unused or unwanted files and programs could be moved from the System category to the Archived category (discussed in more detail below) or Deleted. Dotpups might be added to System files.
Assuming there is any RAM left after the System files are loaded, Intermediate files, the second category in the Master Index, are loaded by rank until the RAM is full. Rank might be determined by dividing frequency of use (perhaps weighted by time since last used,) by size. Programs or files which are hardly ever, or never, used would therefore be given the lowest rank. Programs which are occasionally used, or haven't been used in a while, might still have a higher rank than, say,
OpenOffice, even if it is used often, if they are much smaller than
OpenOffice. It doesn't matter much if small programs are loaded into RAM at boot, but
OpenOffice takes a lot of RAM and a long time to load. If it isn't used all the time it probably shouldn't be loaded at boot.
Archived files are never loaded at boot but it is desirable that they still show up in Puppy's filesystem, so that we know they exist and are available on the DVD. (This is the difference between Deleting a file and Archiving it. Neither Archived nor Deleted files are actually erased from the DVD. A deleted file is simply removed from the Master Index. It would remain on the DVD but would never be loaded or show up anywhere in the Puppy filesystem again, except perhaps for a short time in the Deleted category of the Master Index.) Archived files are loaded into RAM from the DVD if they are clicked or otherwise invoked.
To review: a Master Index is created, to contain the complete history of every file currently on our multisession Puppy DVD. It is written to the disk with each session, and is used as a blueprint by isolinux and Puppy Linux at each boot to reconstruct the current filesystem.
Defragmenting
When a multisession DVD has a lot of sessions saved it takes a long time to boot. It might be possible to speed up booting by occasionally writing a complete file, rather than only its fragment, when a session is saved. That way, only the file from that session has to be loaded instead of the original file plus all the fragments scattered amongst a number of sessions. Essentially this would be doing the same thing as starting a new DVD when the old one is full, except not every file would be rewritten. It might speed up booting, at the expense of using up a bit more of the DVD. The Master Index would be the database used to monitor the files on the multisession DVD and suggest when "defragmenting" a file might be desirable. Of course, a file could also be defragmented on demand.
(Copied from
Basic Concept of Puppy∞ and edited for improved clarity)
Basic Concept of Puppy's filesysten
Puppy is actually a couple of compressed files:
vmlinuz, the Linux kernel
Loads into RAM when live-CD boots.
image.gz, the basic filesystem
When the live-CD boots 'image.gz' loads into a "ramdisk" (a filesystemthat's totally in RAM). The ".gz" means that the file is compressed, so it is uncompressed into the ramdisk and then becomes Puppy's basic filesystem (i.e., the "/" or top directory and all the subdirectories: /usr, /root, /bin, /sbin, /lib, /dev, /tmp, etc).
usr_cram.fs, mounted on /usr
All the files inside the /usr directory are compressed in a file called 'usr_cram.fs'.
Most of the files in Puppy are in /usr (same for any Linux distro).Usually there's no need to write to anything inside /usr (i.e., no needto edit, create or delete files there). Therefore, contents of /usrcould be compressed, and that's what Puppy does. This file is notuncompressed at bootup, it's mounted as-is on /usr (by means of what iscalled a "loopback device"). All of /usr is only a single file thatcontains a compressed and read-only filesystem.
pupXXX, mounted on /root
As the above 3 files are read-only, your settings (e.g., configurationchanges, email, browser history, etc.) can't be saved and are lost at shutdown. To deal with this we have the pupXXX file (where 'XXX' is three numeric digits, pup001 is used for live-CD and pup100 is used for USB installations currently).
'pup001' is a single file, but internally is a complete ext2 filesystem. After creating this file during first bootup, Puppy then mounts it onto the confusingly named directory /root, by means of what is called a "loopbackdevice". This directory /root is your home directory -- all yourpersonal stuff goes in there. Thus, when you shutdown, it will be there next time you start Puppy.
All directories in Puppy are read-only (any changes to them will disappear on reboot) except:
/root
/usr
/etc
/usr and /etc becomes read-write since Puppy version 1.0.1 with atechnique called UNIONFS. Any files written to /usr are actually storedin /root/.usr and mounted to /usr. '/root/.usr' is just a directoryinside pup001. As /root/.usr is actually inside pup001 then it will besaved at end of session and reloaded next time Puppy is booted. Thesame happens to /etc. Files written to /etc are stored in /root/.etc(which is inside pup001) and mounted to /etc.
So, vmlinuz is the Linux kernel, image.gz is a compressed file loadedinto ramdisk which then becomes the basic filesystem, usr_cram.fs is a compressed file with everything else (e.g., softwares), while pupXXX is a file that contains all the changes you made to Puppy.
To view the first three files, open the puppy iso file with programslike Winrar. If you have it burned to CD already, view the files justlike viewing files in any CD (i.e, browse to the CDrom drive folder).The last file, pupXXX, is created when puppy boots for the first timeif you've choosed to save your settings. Usually it's found in thefirst partition of your hard drive.
To know more see
How Puppy Works∞ |
Comparison of Filesystems∞ |
File Allocation Table (FAT)∞
--categories--
CategoryDocumentation
There are no comments on this page. [Add comment]