42: Fragmentation & Defragmentation

When reading data from a magnetic based hard disk, the needle reading from the disk will have to move inside/outside the disk, depending on the location of the data needing querying, very similar to how a vinyl record works. When first starting up such a hard drive, data is saved to the first available space and gradually fills up the disk.

Of course, data is modified through its life on the disk. When editing a document, for example, the correction of typos or the removal of paragraphs, all signal changes to the underlying memory of the disk. This is usually ok: The computer reads memory from the disk, accesses files without any issue, and writes memory to available space on the disk. Everything runs smoothly.

But over time, something happens that affects the memory structures: the reading of data becomes slower. This has nothing to do with the underlying hardware however: The problem would persist, even if one were to copy all contents from one hard disk to another. Moreover, if one were to copy the contents into any other memory storage repository, the problem would not go away. In other words, the issue has something to do with the data on the disk, which I remind you, only consists of ‘1’s and ‘0’s.

Let’s think about how we would go about storing data on some memory. We follow the most straightforward algorithm we can think of: The OS finds a spot in the disk that isn’t used yet, marks it, and when some new data comes along that needs saving, it dumps all the data in that space. When first starting up a hard disk, the memory organization looks like this:

HD: aaaaaaaaa — — — — — — — — — — —

where the lines signify empty data lines, and the ‘a’ signifies a single data line where data is stored by file ‘a’. Because the data (read: data stored in memory lines) is adjacent to one another, this line of data is known as a line of contiguous memory. Suppose now, we wish to store two more files on the same disk. We perform the same algorithm: The computer finds the next data-unfilled space in the memory device, and fills it up with data, resulting in two new iterative configurations of the hard disk:

HD: aaaaaaaaabbbbbb — — — — — — —

HD: aaaaaaaaa**bbbbbb**cccc — — — — —

It’s a this stage, where the data problem can, in theory, arise. If we were to now delete the data that belongs to file b, then we open up a small amout of memory, which, though it is small, is still usable:

HD: aaaaaaaaa– — — cccc — — —

In other words, deleting files or modifying too many will inevitably create gaps like the one above. This is not a problem if the file is as big or smaller than the above mentioned gap. But if it is bigger, and it often is, new data is written in that gap, while the rest is written at a different location, linked with the first via a pointer (saved at the end of a contiguous line of memory, for example). The OS wants to be efficient and not waste space, so when it finds a “dataless” slot where it can store memory, it does so without hesitation, and saves whatever file in those lines.

HD: aaaaaaaaaddddddccccdddd —

Thus, when a large batch of data arrives that is larger than that space, the OS begins saving, regardless of how much it chops up the data into non-contiguous portions. This causes the file we are saving to become fragmented, i.e., split in space on the hard disk.

Logistically, this is not a problem whatsoever. The OS has the “jump” to the location marked to read out the next contiguous line of data, so that when it reaches the end of the first segment, it hops to the next memory location which belongs to the same file. In other words, the file can still be read by having the needle of the disk suspend its reading until it reaches the start of the next memory location to be read.

The hard disk. Courtesy of Wikimedia

Fragmentation, if done enough, will cause these jumps to add up to perceptible levels. Like quantum effects reaching our classical world during the double-slit experiment, the small effect of fragmentation reaches our notice when the files become too fragmented so that to read any file, the needle of the disk needs jump over some irrelevant memory to access the requested data. This is done in two ways:

1. The needle momentarily suspends its reading/writing to hop over a contiguous memory segment for a small number of bytes/kilobytes before continuing to read the file.
2. The needle suspends its reading/writing to mechanically modify the radius of the reading needle, so that it can read the data from a location on the hard disk that has a different distance to its center. This mechanical movement takes a relatively lot of time to adjust.

Suppose now you’d want to read a file that is fragmented several times over, spread out all through the disk. To read this file, you would now require the needle to change its radius multiple times to read, perhaps, only a couple of kilo/Megabytes of memory, which could have been done quickly if all the memory were present in the same “ring” on the hard disk.

Such a mechanical problem is obviously only relevant for hard disks, given that other storage mechanisms do not use a reading/writing needle. For SSDs, fragmentation is less of a problem, given that memory is accessed electronically. A similar thing can be said about random access memory. Nonetheless, with the case of SSDs, the computer needs to make multiple requests to the SSD to access every fragment, which means that while there is no physical needle, a (new) bottleneck is created nonetheless: too many separate calls to memory locations will also slow down the access time.

This is a very small effect, but an effect nonetheless. Using the same SSD, it will take a long, long time before it becomes unusably slow. Improved hardware is, for this reason, not a solution: Fragmentation, regardless of the medium, is problematic.

One solution to make sure fragmentation does not happen in the first place. That is, we need to be smart about where data is saved. A large file should ideally be saved in its own contiguous segment instead of saving it anywhere on the disk where it can be saved. Because the computer needs to be aware of what segments are available, fragmentation avoidance requires additional computing power that, in the early days of computers, was not given out lightly.

For this reason, another, more primitive method was invented to avoid fragmentation. As the primary driver of fragmentation had to do with different file sizes, the dinosaur-computer-scientists, in the land before time, decided that files would only ever be a certain size. The unused memory would then still be available for the file if it wanted to make changes to the file, making fragmentation impossible. Such a technique is clearly undesirable, as some files might want to be larger than the predefined size.

For this reason, fragmentation eventually was accepted as the lesser of two evils, permanently ingraining it within our computer systems. While computers today can apply fragmentation avoidance, early computers didn’t have this luxury due to low computational power. For this reason, another technique was created to manage fragmentation, known as, surprise surprise, defragmentation.

During defragmentation, the OS deliberately looks through non-volatile memory to see which files are fragmented and makes a note of these. Once a contiguous memory spot had been found for a file of a certain size, the computer would copy the data in non-volatile storage from the fragmented portions to the contiguous one.

It was advisable to perform defragmentation for hard disk drives every couple of weeks for optimal performance. Solid-state Drives (SSDs) are more common nowadays, so defragging isn’t all too common: Given the ever-increasing computing power over the last twenty years, fragmentation is a problem that has more or less gone away via fragmentation avoidance. At least, it is unproblematic enough that it isn’t taught much in schools anymore.

How exactly fragmentation avoidance is implemented on computers, though, is a mystery to most people, even those who know of fragmentation, likely somewhere in the OS code, so that no one will have to consider this possibility. Even so, SSDs are intentionally not “defragged” too much because charge traps have a finite number of writes before they wear down and become unusable (around 100? 500?): Defragging risks breaking the SSD.

But because most memory back in the day was on hard drives, defragmentation was necessary. Back then, defragmentation was done on Windows machines by running a defragging program. As a kid, it was oddly satisfying to see the computer move files, i.e., different color boxes into contiguous chunks. My dad would start this operation in the evening, running it late into the night. By the time morning came around, all the colored dots were organized.

Defragmentation program on one of the older Microsoft Windows versions. Courtesy of Wikimedia.

The performance of the disk would (supposedly) be better, though I can’t recall. As a kid, everything happens too fast, so when things occur, we do not understand them until weeks, months, or even years later. While the performance have been better, we can’t always reinterpret these events. Only our perception of events are saved as memories, making our brains first of all, a bad relayer of history, and secondly, more importantly, datastore unto themselves.

In fact, what does it actually take to understand things anyway? Remember things? We can memorize all sorts of information, which we do when we cram for exams. ”Hey! I do know this stuff!” we’d say when we pass. But to really understand, we’d need to take this learned information and contextualize it.

Knowing that metals’ outer shells have many electrons is a cool fun fact. Knowing how digital logic diagrams work is also a cool bit of procedural knowledge to have. But saying that the lines in these diagrams are actual wires and that there is another hidden wire in the diagram that allows for batteries to create a “1” and “0” current, with which we can model neural cells as circuits… This requires a new level of thinking, a new level of piecing together, a new level of organizing our knowledge.

Organizing, in fact, our memories. Learning then, truthfully speaking, is just the defragmentation of our memories.