Solved Requesting a deeper understanding of allocation units.

[Danny S]

I've been trying to search Google for more than a basic, generic, over-simplified explanation of why storage space is treated as if divided into allocation units. One site used the analogy that it's easier to move large boxes than a bunch of sand. But the problem with that analogy is that I imagine multiple bits of data have to be read one by one regardless. I don't imagine that the read/write head can "move" multiple bits simultaneously. So why are computers programmed to pretend data is divided into "blocks"? How does doing this speed up read and write operations?

The only thing I can think of is that it's because of file fragmentation. But is fragmentation the only thing driving the need for allocation units? And, if so, does that mean that allocation units are somewhat obsolete in SSDs and flash drives, since the performance of those devices are not significantly affected by fragmentation? Should I, from now on, format my SSDs with the smallest available allocation unit size even if most of the files I intend to put on the drive are movies?

 

[dg1261]

One site used the analogy that it's easier to move large boxes than a bunch of sand. But the problem with that analogy is that I imagine multiple bits of data have to be read one by one regardless. I don't imagine that the read/write head can "move" multiple bits simultaneously.

Yes, they can. That's known as data bus width. A 64-bit CPU can work with 64 bits of data simultaneously. And SSD's are designed to buffer data 4096 bytes at a time from its memory blocks to the computer's faster RAM, where the CPU can work with it more quickly.


File "allocation units" (and its predecessor, sector "clusters") were in part to reduce the number of entries in the indexes -- the file allocation table (FAT) or the NTFS master file table (MFT) -- that point to the locations of each file's data blocks.

A smaller cluster size means a larger index to address the entirety of the partition's data storage space, and more lookups in the index to pull together the pieces of a given file, and potentially more file fragmentation (a particular problem for spinning disc platters). All of these translate to less efficiency.

A larger cluster size means less fragmentation and fewer index lookups, but also means more wasted space ("slack space"). For example, say you have a 9KB file. With 2KB clusters that file will be split across 5 clusters, with 1KB of the 5th cluster being unused. (It also can't be reused for another file because there are no FAT/MFT index entries pointing to partial clusters, only whole clusters -- that's the whole point of clusters.) In contrast, with 4KB clusters that 9KB file will be split across 3 clusters, so less potential fragmentation but 3KB of the last cluster is wasted instead of 1KB.

Given the mean size of files on a typical system, the choice of 4KB clusters was a practical tradeoff for the sake of efficiency.

For an analogy, let's say you're sending your buddy to the store for party supplies. It's easier to tell him to pick up three cases of beer, rather than telling him to get 72 bottles. He doesn't have to count bottles, he just grabs three units from the stack on the store's floor. It's more efficient that way.

For backward compatibility, solid-state drives used the same file system right from the outset, though the term "cluster" was modernized to "allocation unit". However, this was also a fortuitous break because the memory chips in SSDs are actually built from blocks of 4KB, so no SSD could have used smaller allocation units, anyway.

Incidentally, today's large spinning disc drives (known as "AF" or "Advanced Format") have also switched from 512-byte sectors to 4KB sectors natively, so the same principal applies.

BTW, this is a good place to also mention the topic of SSD "alignment". Unlike magnetic media (which can directly overwrite individual sectors), SSDs can only write 4KB blocks of memory at a time, and must do a block erase operation first because they cannot directly overwrite.

You don't want your file system to line up its file allocation units so that one a.u. spans across the end of one SSD memory block and the beginning of the next block. If you had to change the data in that one a.u., the SSD would have to read two memory blocks, save the beginning of one block and the end of the other, stitch in the new changing data, erase both SSD blocks, and then write the two stitched blocks back to the SSD media. That's massively inefficient.

Fortunately, modern OSes are smart enough to make sure they align their allocation units with the SSD's memory blocks when creating the file system.

Should I, from now on, format my SSDs with the smallest available allocation unit size even if most of the files I intend to put on the drive are movies?

SSDs must read/write data in blocks of 4KB at a time, so there is no point trying to use allocation units smaller than that. You'll just hamper its operation and make it hugely inefficient. The NTFS file system defaults to 4KB allocation units, so leave it alone.

 

[Danny S]

Thank you dg1261 for providing such a generous amount of information. I may need you to clarify some things though.


I am aware and acknowledge that CPUs and other hardware are capable of busing more than one bit at a time, but those buses are fixed as far as I know, whereas the allocation unit size can be chosen from a variety of options upon formatting and can be changed upon reformatting. So I think you might be using apples to explain oranges so to speak.


And being able to bus multiple bits simultaneously does not seem to explain or justify the tradition of not allowing more than one file to occupy (if only in part) the same cluster.


And even though a computer can bus multiple bits at the same time, it still has to keep track of every single bit. So in the beer bottle analogy, it doesn't seem to matter if cases are used, because every bottle still has to be counted. The only advantage the case offers is the ability to physically move the bottles without keeping track of each one. But if we're talking about an HDD (which I am talking about), there's only one case, and that's the entire disk. The surface of an HDD is not physically divided into "cases" that can be physically moved, carrying multiple bits at the same time without keeping track of what the bit values are. So, yes, parts of the computer can bus multiple bits simultaneously, but I don't see how that explains the use of allocation units.


I know nothing about how SSDs are constructed, but I'm guessing an SSD is little more than an array of logic gates. And I don't readily see how that technology benefits from allocation units any more than HDDs. I did think, for a moment, that block erasing might make a difference, but I'm now leaning towards the conclusion that it doesn't.


The kind of explanation that would satisfy me might be over my head, unfortunately. I do have a 4-year degree in electronics engineering technology, but I know very little about computer architecture.


The fragmentation argument is the only one that makes any sense to me. I understand the need to minimize file fragmentation. And I get that to do that means preventing a file from being divided into ever shrinking portions. What I don't get is why that means 3KB of space has to be wasted on a 1KB file. It seems like computers could be programmed to simply not allow a 1KB file to be fragmented without wasting 3KB of space.

SSDs must read/write data in blocks of 4KB at a time, so there is no point trying to use allocation units smaller than that. You'll just hamper its operation and make it hugely inefficient. The NTFS file system defaults to 4KB allocation units, so leave it alone.

I'll try to remember that. Thank you!

 

[dg1261]

I am aware and acknowledge that CPUs and other hardware are capable of busing more than one bit at a time
[...]
So I think you might be using apples to explain oranges so to speak.

Those comments were in response to your statement:

I imagine multiple bits of data have to be read one by one regardless

No, up to a certain multiple, they can be read simultaneously. The exact multiple is determined by the manufacturer and how they've designed the disk controller on that particular HDD.

And even though a computer can bus multiple bits at the same time, it still has to keep track of every single bit. So in the beer bottle analogy, it doesn't seem to matter if cases are used, because every bottle still has to be counted.

No, that's not true at all! At the checkout counter, the clerk isn't ringing up bottles one by one, he/she is ringing up only three items. The clerk couldn't care less how many bottles are in each case.

if we're talking about an HDD (which I am talking about), there's only one case, and that's the entire disk.

No, each case is equivalent to an allocation unit, not the entire disk. Buying one case of beer is not equivalent to buying out the store.

The surface of an HDD is not physically divided into "cases"

Actually, the surface is indeed physically divided--into sectors. No matter how much you may want to try, there's simply no way to access the surface of any HDD made by anything less than (at minimum) 512 bytes at a time.

And that's only with older, relatively small HDDs; modern HDDs use sectors of 4096 bytes, not 512 bytes.

... does not seem to explain or justify the tradition of not allowing more than one file to occupy (if only in part) the same cluster.

How big an index are you suggesting the disk controller should try to manage? A 4TB disk has 4 trillion bytes. You want an index with 4 trillion entries just so you can catalog what file each individual byte on the disk belongs to? That's not only impractical, it's ludicrous--if for no other reason than your index becomes larger than the amount of data being stored.

Even accessing sector-by-sector (instead of byte-by-byte) requires 4/512 trillion index entries; still too large to be practical.

And even if you could, what happens if the file you want to save is only 20 bytes? Are you suggesting the controller should be able to reuse the other 492 bytes of that one sector? There's simply no index entry that can point to the surface with that amount of granularity.

Besides, it is physically impossible to write only 20 bytes or only 492 bytes to the disk surface. It cannot be done. It's never been possible, going all the way back to the invention of the very first hard disk. No manufacturer can make that happen. And on modern AF ("Advanced Format") HDDs, it's physically impossible to write less than 4096 bytes at a time.

When compared to sector-by-sector, the functioning of allocation units is just a matter of scale. As I explained, even on the individual sector level some slack space is inevitable, and allocation units that comprise more than single sectors risk more slack space. But if a file system makes that choice, it's conceding that a more manageable FAT or MFT index and more efficient data transfers is preferable to wasting a little more disk space.

(Incidentally, if anyone wants to explore this quantitatively, try right-clicking any file or folder and look at Properties. "Size" is amount of actual data the file or folder contains, "Size on disk" is the amount of sector space being allocated to those file(s), and the difference between those numbers represents the amount of slack space.)

 

[Danny S]

Thank you once again for taking the time to respond. I wish I could say everything's cleared up, but I'm still having trouble with some of your explanation.

No, that's not true at all! At the checkout counter, the clerk isn't ringing up bottles one by one, he/she is ringing up only three items. The clerk couldn't care less how many bottles are in each case.

I'm not understanding how a computer can move more than one bit without reading each individual bit. Your analogy isn't working for me. And the reason it doesn't work for me is because moving a bit of data is not a physical or literal movement; it's actually a duplication. And I don't see how a bit can be duplicated elsewhere without first being read.

No, each case is equivalent to an allocation unit, not the entire disk.

I know that's what you meant. But, again, the problem is that I don't understand how the analogy could be accurate or applicable. When I say the surface is not physically divided, I mean it's a single solid object. Now, yes, it's true that sectors are separated by "inter-sector gaps" (I just learned that word today), but that seems beside the point to me. The computer does not physically move sectors or clusters independently of each other. The only way to rearrange the data is to first read it and then write it somewhere else. Am I really wrong about all that? When a computer defragments a disk, does it lift pieces of the surface off the disk and move those pieces elsewhere? The data has to be read instead, right?

How big an index are you suggesting the disk controller should try to manage?

Well, I do admit that I'm a little deeper into assumption territory here. I'm assuming that only one entry is needed per fragment to specify where that fragment begins and ends. Is this not how computers work? Are you saying an entry is needed for every single cluster or sector even if the file isn't fragmented? If so, then why that is would need to be explained to me.

There's simply no index entry that can point to the surface with that amount of granularity.
. . . it's physically impossible to write less than 4096 bytes at a time.

Ok, let's say there's a sector with a 1KB file on it. Now, I'd like to save another 1KB file somewhere else on the same sector. Isn't it possible to design a computer to be able to first read the file that's already on the sector, then write both files on the same sector as if the two files were one file (except for the fact that the second file has its own entry in the index). Or is the computer only able to point to the beginning of sectors? Does it take an inter-sector gap for the computer to know where to start reading?

Even if the answer to both of those questions is yes, it still doesn't help me to understand why larger allocation units are available when formatting. If the only purpose is to reduce fragmentation, I don't see why sectors in a particular cluster that aren't being used by one file in that cluster can't be used by another file if the computer can point to those unused sectors. I should be able to check a box somewhere on my computer that says, "Don't fragment files less than 1MB," without wasting up to 1MB of space on files that aren't perfect multiples or even near perfect multiples of 1MB.

(Incidentally, if anyone wants to explore this quantitatively, try right-clicking any file or folder and look at Properties. "Size" is amount of actual data the file or folder contains, "Size on disk" is the amount of sector space being allocated to those file(s), and the difference between those numbers represents the amount of slack space.)

I did this recently when I was first trying to Google "allocation unit size". I had just dealt with "Size" and "Size on disk" a week earlier but never looked up the difference. Then, as I was learning about "allocation unit size," it struck me, so I went to confirm my suspicions.

 

[dg1261]

I'm not understanding how a computer can move more than one bit without reading each individual bit.

Since we're talking about disks, I'll read that as "I'm not understanding how a hard disk can [read or write] more than one bit without reading each individual bit."

Hard disks cannot read individual bits, nor even individual bytes. That's because the data is encoded with a form of modulation. The earliest hard disks for PCs used an encoding called Modified Frequency Modulation ("MFM"--akin to radio signals), and every hard disk since is based on more advanced algorithms from that same basic idea. Whether you're trying to write one bit, one byte, or 400 bytes, the read/write head has to write a full sector because it's encoded. Even if you only changed one bit, the disk has to read back the entire sector before the controller can start decoding the beginning of the sector.

Magnetic disk technology requires this modulation because the magnetic flux changes recorded on the surface of spinning disks are very speed-sensitive. If you're trying to store a series of 12 zeroes, for example, when it's read back how can the controller know whether the lack of flux changes represents 11 zeroes, or 12, or 15 zeroes? Modulation guarantees there are frequent enough flux changes to avoid overly long gaps that could make retrieval ambiguous.

But modulation also means writing and reading must be done full sectors at a time.

I'm assuming that only one entry is needed per fragment to specify where that fragment begins and ends. Is this not how computers work? Are you saying an entry is needed for every single cluster or sector even if the file isn't fragmented?

The FAT or MFT is a table corresponding to each and every allocation unit on the partition, whether an a.u. is in use or not. (Note that file systems are applied at the partition level, not whole-disk level.)

The disk does not care what OS you've installed, nor what file system you're using on any given partition. It doesn't know about files, nor how long any file is. It doesn't know about allocation units--because that's a file system thing. All the disk knows about is sectors.

The OS consults the file system and asks it to retrieve file "abc". The file system looks up the filename in its index, then tells the disk controller, "retrieve sectors xxx, yyy, and zzz." There is simply no capacity within the file system to be able to ask the disk for "sector xxx-and-a-half".

If so, then why that is would need to be explained to me.

Then research the structure of the FAT file system. Once you understand FAT16 and FAT32, you can move on the NTFS, a more complex and sophisticated variation.

let's say there's a sector with a 1KB file on it. Now, I'd like to save another 1KB file somewhere else on the same sector. Isn't it possible to design a computer to be able to first read the file that's already on the sector, then write both files on the same sector as if the two files were one file (except for the fact that the second file has its own entry in the index). Or is the computer only able to point to the beginning of sectors?

If you're willing to expend the processing time, you can indeed create a program to merge multiple data segments into one allocation unit. But then what? You can't separate the pieces back out again--at least not without creating your own subsidiary index to keep track of partial sectors or allocation units ... but now things are just getting ridiculous.

When a sector is read back, the disk controller is going to see it as a single piece. When the sector(s) of a file allocation unit is passed back to the file system, its one-to-one lookup table is going to see that one a.u. as one piece.

 

[Danny S]

Thank you so much for your help. You've revealed a number of gaps and misconceptions in my understanding of magnetic media. There still remain some gaps in my understanding on this issue, but you have pointed the way for me to do additional research elsewhere, and I'm ready to bring this discussion to a close. And I suspect you are too.


Thank you!

 

[dg1261]

As you delve into the intricacies of magnetic hard disk technology, it will be helpful to keep in mind the below key point.

Back in the heyday of MFM and RLL hard disks, the disk controller and the physical disk mechanics were separate devices (and often from different manufacturers). With the advent of IDE ("Integrated Drive Electronics") disk drives in the early 1990's, though, the controller circuitry was merged with the mechanical parts. This gave the manufacturer a lot more control of the entire subsystem.

Internally, the read/write heads still have to be moved across the disk surface to physical coordinates of cylinder (track), head, and sector-on-track, but integrating the controller affords the manufacturer the opportunity to "translate" all of those coordinates into a linear string of sector numbers, from the beginning to the end of the disk. (See LBA, "Logical Block Addressing".)

As a consequence, this has led many people to the misconception that hard disks consist of a single, spiraling track, from the outside edge to inner hub like an old vinyl LP record. Hard disks don't actually work that way, though, so keep that factoid in the back of your mind as you're doing your research: the integrated controller masks what's really going on at the disk surface.

Aside: another side benefit of this controller-to-disk surface remapping is that it allows the end product to appear to be perfectly defect-free. All disk platters actually have defects in manufacturing, but when it goes through QA testing any defective spots are mapped out and another sector from a pool of spares is mapped in, in its place. The outside world beyond the controller's interface doesn't know the difference, and the disk drive seems to be 100% perfect. (This is the basis behind SMART, which is essentially a longer-term extension of the manufacturing QA process.)

 

[Danny S]

Thank you!