6 ms·
I feel like FAT and FAT32 back in the DOS days were so simple and easy to explain, that my generation of programmers have the "sweet point" in terms of learning
by dragontamer 5y ago
I feel like FAT and FAT32 back in the DOS days were so simple and easy to explain, that my generation of programmers have the "sweet point" in terms of learning technology.
FAT / FAT32 wasn't about B-trees or balancing or anything. It was a simple linked list, that got severely tangled up during use and required an hour of "defragmenting" to make your hard drive go back at high speed.
As a computer user of the time, I was too young / ignorant to know why it happened like that, but that experience stuck with me until college. In college, I learned about how FAT32 filesystem worked fundamentally (though obsolete, its so simple its a great introduction).
From there, I learned why we have moved onto more advanced data-structures like B-Trees. Why things like B-trees are less prone to fragmentation. Etc. etc.
----------
A big part of my learning process was the hours of waiting I'd put in to defrag my hard drive back in the day. Those memories stuck with me, I know what the "downsides" are if I don't use a self-balancing B-Tree to store data on a hard drive.
Perhaps today, we're no longer at a point where we can just convince legions of new computer-users (or programmers) to use inferior file systems like FAT32 in their daily lives. But we can at least tell stories about those times, so that they can understand why we put so much complexity into our modern filesystem data-structures.
- nanidin 5y agoWasn’t defragmentation more important in general on spinning media to reduce random seeks? And now most performance oriented things are happening on SSD?
- dragontamer 5y agoI'm very confused by your question. I don't think FAT or FAT32 was ever a performance-oriented filesystem. Back then, we were just happy having a personal computer. I'm sure there was better tech being used somewhere. But MS-DOS / Windows was just your cheap $99 OS in an age when other compilers and OSes cost you something like $1000 to $10,000. You formatted your hard-drive in FAT because MS-DOS used FAT. You used MS-DOS because that's what PCs and PC-clones came with. There was no alternative, and PCs were already considered a pretty luxury / nerd item. (I know people brag about their DEC Alphas, Unix copies or OS/2... but you got enough "nerd cred" back then if you simply had a PC at all) Its just how computers worked back then. Every PC was using FAT, and every few months of regular use the disk reads/writes would get so slow that performance was unbearable. At that point, you spent an hour defragmenting the hard drive, and everything worked great again. ------- Eventually 4GB hard drives were made, and you upgraded your computer to FAT32. Soon after that, Windows promised an end to defragmenting with its next-generation NTFS filesystem (based off of the B-trees discussed in this article) and we never looked back.
- NikolaNovak 5y ago>>"Windows promised an end to defragmenting with its next-generation NTFS filesystem" I thought this mostly reduced fragmentation of the filesystem metadata; but not the fragmentation of actual datafiles themselves?
- nanidin 5y agoWell, one purpose of defragging a drive was to put data from the same file in one place in order to reduce random seeks while reading sequential data. One would defrag in order to increase performance in this regard. On an SSD, the random seek time is much lower. There may be some gains from sequential reads, but the gains from having data physically defragmented are not as stated as with spinning media.
- NikolaNovak 5y agoDefragmentation was indeed more important on spinning disks; I think your "to reduce random seeks" is largely correct: another way to think about it is that it was ensuring sequential reads ("read in this 10MB file") did not become random seeks ("Sure, but that 10MB file is in these 5,381 chunks all over the place") You are correct that SSDs do not require defragmentation, and to a certain degree defragmentation is somewhat harmful in the sense that it forces unnecessary read/write cycles.
- nayuki 5y agoIf I understand correctly, NTFS describes a file as a sequence of cluster ranges, e.g. [7,12), [0,4), [20,25). So the more fragments a file or folder has, the more space is required to describe how it's stored. This applies to the file system and is independent of HDD/SSD technology. As for SSDs, they need some degree of garbage collection - it's considered bad for an erasable block (e.g. 1 MiB) to contain a mix of live pages and deleted pages (4 KiB each).
- wirthjason 5y agoGone are the days of selling software to magically to make you computer faster. Half of them just ran defrag under the hood.
- rasz 5y agoHow would btrees on their own solve fragmentation problem? The source of slowdown was random seek speed, not data structure used. You can optimize FAT32 driver to always fit files into sequential gaps, early Windows implementations didnt.
- dragontamer 5y agoFiles grow and shrink. Think about even the simplest "log" file (ex: Apache logs) appending constantly to the end of the file. First you have an access.log (+1 line to the end). Then Apache opens the error.log and adds some info to the end. Then PHP has something logged somewhere, again opening and closing a new set of files. Even if these files were all perfectly allocated in sequential order at the beginning, a few operations like this quickly fragments the files. -------------- I don't recall all the files MS-DOS or Win95 opened / closed on a regular basis, but play a video game (save file changed), open a word document, edit a photo, and come back to the video game... and the save file will now start getting fragmented as the size of the save files change and new allocated blocks need to be figured out.
- rasz 5y ago- How would btrees help with that? - can you name couple of games saving state by appending/modifying files in place on disk?
- dragontamer 5y ago> - can you name couple of games saving state by appending/modifying files in place on disk? Hmm, maybe the video game wasn't the example I should have chosen. But swap the order around: open a word doc (which creates an "auto-save" file which is almost certainly modified in place), and then do the other stuff and I think it applies. ------ > - How would btrees help with that? At a minimum, your indices are all together and in order and are read together all at once. From there, you can build the file's representation in RAM with much fewer random-traversals than the FAT32 linked-list approach. Perhaps "fixing fragmentation" is the wrong description. B-Trees mitigate the random-reads associated with fragmentation. There are much fewer seeks from a b-tree based representation than a FAT/linked-list style representation. ----------------- Consider this scenario. You have a FAT/Linked list of the following: 0 -> 10 -> 5 -> 7 -> 2 -> 1 So you need to move-head to 0, read, move-head to 10, read, move-head to 5, read, (etc. etc.). That's 6 times you move the head randomly. Now lets say you have a b-tree of [0, 10, 5, 7, 2, 1]. Exactly the same order of nodes as the linked list, but you can optimize much better. You read initially the b-tree, and then you read 0, 1, 2, 5, 7, 10 in order. You probably only move the head twice: first you move the head to 0, to read [0, 1, 2] as a sequential scan. Then, you move the head to 5, and read [5, 6, 7, 8, 9, 10] in order. Except you throw away the results for 6, 8, and 9. So long as you have sufficient RAM to re-order the data after you've read them from disk, you're gold. ---------- There's no way to optimize the FAT32's reads, because the indicies are scattered across the linked list. You only know that 10 is the "next" FAT32 node after you've read the page at 0. You only know that 5 follows 10 after you've read 10.