0

In the context of e.g. ext4 fs, I often stumble upon both 'fragment' and 'extent' words.

They appear to be both related to fragmentation, extents for example are pretty extensively (duh) explained here.

What's the difference between them?

ledonter
  • 173

2 Answers2

1

Just to add confusion, there are two kinds of fragments and three kinds of fragmentation.

  • A fragmented file is a file that is stored in multiple chunks (or fragments, each of which might be an extent), so that when the file is read sequentially, the OS has to read all the pieces from different places on the disk, which can slow down the reading of the file. ext4fs has algorithms to try to prevent this by allocating blocks for the file as contiguously as possible. A file with multiple extents is said to be fragmented. However, the file could also be stored as a single fragment (i.e., not fragmented) that is a list of contiguous blocks and is not an extent.. so that is how fragments and extents are related.

  • A fragment can also be a file that is smaller than a block or the last piece of a file that is smaller than a block that is stored as a fragment in a full block with other fragments. When block sizes are large and you have a large number of small files, storing multiple file fragments in a single block saves a lot of space and possibly increases performance, especially if you are trying to read all of the files that share a block.

From the filesystem perspective, you can have internal fragmentation and external fragmentation.

  • Internal fragmentation is within a single file, same as in the first type of fragmentation above.

  • External fragmentation occurs when you have related files all in one directory that are scattered all over the disk. If you are trying to read every file in the directory, this can case as much performance issues as internal fragmentation does. The ext4fs algorithms also attempt to minimize external fragmentation by attempting to allocate blocks for files in the same cylinder group as other files in the same directory.

Historical note:

Linux ext4fs is an evolution of ext3fs and ext2fs and extfs. extfs was patterned on (but not based on) UFS. UFS was based on the BSD Fast File System (FFS). The algorithms above were key in FFS and largely exist in ext4 but many others in FFS (especially those dealing with rotational latency) are obsolete and were probably thrown away for UFS. Some of the terminology above is (at least) two generations from linux and the terms themselves may have drifted, but the algorithms are still there.

Cylinder groups from FFS were originally correlated with tracks and sectors (which were used for rotational latency optimization), but were really just contiguous cylinders. Blocks haven't cleanly mapped to tracks/sectors for at least 30 years, and probably not since floppies were common. But cylinder groups are still contiguous groups of blocks and still help optimize seek times. Seek times may be irrelevant for solid state disks, but contiguous block allocation still helps them.

Optimization from cylinder groups is almost a side effect (but an intentional one), as inodes belong to a cylinder group, and inodes within a directory have a tendency to be allocated sequentially, and there is an attempt to allocate blocks for an inode in the same cylinder group.

Note that cylinder groups are not the only algorithm used to reduce performance issues from fragmentation. Even FFS tried to delay block allocation to try to get larger contiguous block allocations within a file.

The use of the term 'fragmentation' has always been used in a sloppy way in unix with little or no clarity of which type of fragmentation was being referred to without carefully reading context. After searching and referencing multiple historical documents for both BSD and Linux, I was unable to find any formal definition of the words internal or external fragmentation and their usage seems to have never been fixed, and the term 'fragmentation' itself sometimes is used to reference both types at the same time.

user10489
  • 6,740
  • I believe your definition of external fragmentation is completely wrong. See https://unix.stackexchange.com/questions/765943/what-is-external-fragmentation-in-a-file-system – ChennyStar Jan 03 '24 at 04:26
  • These definitions predate linux, and are part of the BSD fast filesystem definition, upon which ext2 was based. It is possible the terms have been reused for different purposes since then, but the algorithms described still exist in ext4. – user10489 Jan 03 '24 at 04:53
  • Note however that FFS implemented a large number of optimizations that did not make it into ext2. Some of those only made sense when there was a 1:1 mapping between sector/track and physical positions and sector position from one track to the next had some correlation, neither of which has been the case for at least 30 years. – user10489 Jan 03 '24 at 05:07
  • "The ext4fs algorithms also attempt to minimize external fragmentation by attempting to allocate blocks for files in the same cylinder group as other files in the same directory." Are you absolutely sure about this ? Could you point me to a source confirming this ? I couldn't find anything interesting (I did a web search of directory fragmentation). – ChennyStar Jan 03 '24 at 05:12
  • I am skeptical because packing files of a directory closely together on the disk conflicts with the need (if possible) to surround a file with free blocks, to prevent future file fragmentation. So, reducing directory fragmentation would conflict with reducing file fragmentation (i'm using the term directory fragmentation instead of external fragmentation, which has a different meaning, according to kernel.org https://ext4.wiki.kernel.org/index.php/Design_for_Large_Allocation_Blocks). – ChennyStar Jan 03 '24 at 05:18
  • Besides, related files (e.g., related in the sense that they need to be accessed simultaneously) aren't necessarily stored in a same directory. And files from different directories need sometimes to be accessed simultaneously (e.g., a launching a program usually involves files from /bin, /etc, /home, /tmp, and so on). So assuming that all files of a same directory need to be accessed simultaneously and trying to pack them together on the disk would be a poor assumption. And unless I find another source confirming this, I'll remain skeptical that EXT4 or the kernel aims at doing this. – ChennyStar Jan 03 '24 at 05:23
  • I didn't say it "packed" files in a directory together. I said it put them in the same cylinder group. This doesn't prevent fragmentation so much as minimize seek time between files which is what causes the performance penalty with this type of fragmentation. – user10489 Jan 03 '24 at 05:35
  • https://blog.koehntopp.info/2023/05/06/50-years-in-filesystems-1984.html discusses directory layout and file fragmentation. If a filesytsem uses CGs then it does this as a side effect. – user10489 Jan 03 '24 at 05:43
  • Thanks for your link, which indeed confirms your statement, for BSD FFS at least. Do you think it's still relevant today with other FS, like EXT4 (see my next comment). – ChennyStar Jan 03 '24 at 05:47
  • In an answer to another question (https://unix.stackexchange.com/questions/761283/in-ext4-are-extent-and-block-group-the-same-thing) : "In archaic terminology [a block group] is a "cylinder group", but it has been a very long time since this related to a cylinder on a physical disk.". If "cylinder groups" are no longer related to physical cylinders, then trying to group files of a same directory in the same cylinder groups doesn't make sense anymore, no ? – ChennyStar Jan 03 '24 at 05:48
  • Well, like I said, physical mapping between blocks and sector/cylinder has not existed for 30+ years. But blocks are still contiguous, or at least mostly so. So CGs might not actually be cylinders (and never were), but they are still mostly contiguous extents of disk blocks. – user10489 Jan 03 '24 at 06:00
  • Another interesting reading, partially confirming your statement : https://recoverhdd.com/blog/ufs1-and-ufs2-file-systems.html. "The main purpose of FFS was to consolidate all the contents of a directory (data and metadata) into one cylinder group.(...). However, due to the rapid increase in the disk size and the size of the files stored on them, this solution was no longer effective since the block size was increased to keep the performance at the proper level." Was the goal to store same dir files in the same CGs later dropped ? – ChennyStar Jan 03 '24 at 06:00
  • If you read the link I put in, they decided to allow large files to intentionally be fragmented into multiple CGs to allow other files in the CG to grow, while still keeping the large file in huge contiguous chunks for fast I/O. I don't know how much of this got into ext4, but I suspect the authors were aware of these things. – user10489 Jan 03 '24 at 06:02
  • OK. So, to sum things up : putting same dir files in adjacent CGs was, and probably still is, a thing in BSD FFS. And it may also be the case in EXT4, although there are less sources available to confirm this. But using the term external fragmentation for this conflicts with kernel.org's definition of external fragmentation. – ChennyStar Jan 03 '24 at 06:11
  • Do you have a (kernel) reference for internal/external fragmentation definitions? I feel the distro docs are not clear or correct in their usage and that may be where the drift came from. – user10489 Jan 03 '24 at 06:36
  • Not really, in fact. But most sites use external fragmentation for file fragmentation, vs internal fragmentation for the case where file size < block size. The way kernel.org uses those terms seems to confirm that, without defining them explicitly (https://ext4.wiki.kernel.org/index.php/Design_for_Large_Allocation_Blocks). – ChennyStar Jan 03 '24 at 08:14
  • +1 for adding the "Historical Note" section, which clarifies a few thing. I myself added an EDIT section to my post (https://unix.stackexchange.com/questions/765943/what-is-external-fragmentation-in-a-file-system) : basically my conclusion is that the terms "internal" and "external" fragmentation have never been formally defined in the context of file systems, and thus are used differently by different people. – ChennyStar Jan 04 '24 at 06:57
  • Just found a reliable source (kernel.org's wiki: https://ext4.wiki.kernel.org/index.php/Ext4_Disk_Layout#Block_and_Inode_Allocation_Policy) that confirms indeed that, like FFS/UFS does, EXT4 also tries to keep files from a same directory in a same block group: "all the inodes in a directory are placed in the same block group as the directory, when feasible. The working assumption here is that all the files in a directory might be related, therefore it is useful to try to keep them all together." – ChennyStar Jan 07 '24 at 04:04
0

You already cited a source that explains what an extent is.

As for a fragment, it's a subdivision of a block. This concept was introduced in FFS and still exists in UFS, but it doesn't exist in EXT4.

Sources :

Fragment Size (Oracle) :

As files are created or expanded, they are allocated disk space in either full logical blocks or portions of logical blocks called fragments. When disk space is needed for a file, full blocks are allocated first, and then one or more fragments of a block are allocated for the remainder. For small files, allocation begins with fragments.

The ability to allocate fragments of blocks to files, rather than just whole blocks, saves space by reducing fragmentation of disk space that results from unused holes in blocks.

You define the fragment size when you create a UFS file system. The default fragment size is 1 KB. Each block can be divided into 1, 2, 4, or 8 fragments, which results in fragment sizes from 8192 bytes to 512 bytes (for 4-KB file systems only). The lower bound is actually tied to the disk sector size, typically 512 bytes.

For multiterabyte file systems, the fragment size must be equal to the file system block size.

https://recoverhdd.com/blog/ufs1-and-ufs2-file-systems.html

The main purpose of FFS was to consolidate all the contents of a directory (data and metadata) into one cylinder group. It would greatly reduce the fragmentation level that occurred due to the severe spread of data across the disk’s surface. However, due to the rapid increase in the disk size and the size of the files stored on them, this solution was no longer effective since the block size was increased to keep the performance at the proper level. Accordingly, storing a large number of small files took up a lot of space.

It again forced the developers to develop the file system and based on FFS was created the revised file system “UFS1“, and later its revised version – “UFS2“, creation of which allowed providing reliability and speed thanks to the division of blocks into fragments, which are used to store the final bytes of the file (previously for this was allocated a whole block) and some new technologies.

Again, the concept doesn't exist in EXT3/4 :

What is a fragment size in an ext3 filesystem?

ext3fs doesn't support block fragmentation so a one byte file will use a whole 4096 block.

On the opposite, for example UFS supports four fragments in a block so small files won't fill a file system as fast as they will do on ext3fs.

Optimize ext4 partition for millions of 1KB files

AFAIK, ext4 is simply not a good choice for what you're doing, since it doesn't support block sub-allocation. You should really consider using UFS2 or BtrFS.

Note that # dumpe2fs of an EXT3/4 FS will show you a fragment size equal to the block size :

# dumpe2fs /dev/sde1 
(...)
Block size:               4096
Fragment size:            4096
(...)
ChennyStar
  • 1,743