Comment by dragontamer | Hacker News Reader

Comment by dragontamer | Hacker News Reader

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.

Gone are the days of selling software to magically to make you computer faster. Half of them just ran defrag under the hood.

Wasn’t defragmentation more important in general on spinning media to reduce random seeks? And now most performance oriented things are happening on SSD?

I'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.

>>"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?

Well, 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.

Defragmentation 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.

If 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).

How 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.

Files 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.

- How would btrees help with that?

- can you name couple of games saving state by appending/modifying files in place on disk?

> - 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.

Office autosave does not modify files in place, it creates new copy with some additional backup/history/unwritten mechanisms thrown in. Modifying files in place is very rare (pre allocation in case of many downloaders like bittorrent/aria2 etc, or straight up disk editing), appending is more common (logging).

>From there, you can build the file's representation in RAM with much fewer random-traversals than the FAT32 linked-list approach.

You can do same thing in FAT by reading whole cluster map at the start. Wiki: "Other high-level mechanisms may read in and process larger parts or the complete FAT on startup or on demand when needed and dynamically build up in-memory tree representations of the volume's file structures different from the on-disk structures." This passage references OS/2 documentation, but its unclear to me if OS/2 employed such optimizations. Later NT builds might have this, as Iv seen large files allocated into empty space in the middle of a disk instead of forcing writes into first available gap.

>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

after reading whole cluster map you have same representation in RAM, there is no information disparity. Its less elegant, slower to initialize and wasteful - 2TB FAT32 partition with 32KB clusters means >250MB cluster map on disk. But at the end of the day disk will have to perform same random seeks to read already fragmented file. The magic bullet for fragmentation is a map of free sectors letting OS pre plan where to put files in a smart way, and even NTFS doesnt use fancy data structures for that. NTFS $BITMAP is a https://en.wikipedia.org/wiki/Free_space_bitmap. exFAT has a nice feature of marking unfragmented files in the Directory entry removing the need for FAT traversal altogether.

>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.

or whole FAT table is cached in ram and there is no difference :)

Reply on news.ycombinator.com