Block suballocation
Encyclopedia
Block suballocation is a feature of some computer file system
s which allows large blocks or allocation units to be used while making efficient use of "slack" space at the end of large files, space which would otherwise be lost for other use to internal fragmentation.
In file systems that don't support fragments, this feature is also called tail merging or tail packing because it is commonly done by packing the "tail", or last partial block, of multiple files into a single block.
. Block sizes are typically multiples of 512 due to the size of hard disk sector
s. When files are allocated by some traditional file systems, only whole blocks can be allocated to individual files. But as file sizes are often not multiples of the file system block size, this design inherently results in the last blocks of files (called tails) occupying only a part of the block, resulting in what is called internal fragmentation (not to be confused with external fragmentation). This waste of space can be significant if the file system stores many small files and can become critical when attempting to use higher block sizes to improve performance. FFS
and other derived UNIX file systems support fragments which greatly mitigate this effect.
Some block suballocation schemes can perform allocation at the byte level; most, however, simply divide up the block into smaller ones (the divisor usually being some power of 2). For example, if a 38 KiB
file is to be stored in a file system
using 32 KiB blocks, the file would normally span two blocks, or 64 KiB, for storage; the remaining 26 KiB of the second block becomes unused slack space. With a 8 KiB block suballocation, however, the file would occupy just 8 KiB of the second block, leave 2 KiB slack and free the other 24 KiB of the block for other files.
features on modern operating system
s – when dealing with short files, several tails may be close enough to each another to be read together, and thus a disk seek is not introduced. Such file systems often employ heuristics in order to determine whether tail packing is worthwhile in a given situation,
and defragmentation
software may use a more involved heuristic.
files or small bitmap images, tail packing can increase storage efficiency even more than twofold, compared to file systems without tail packing.
This not only translates into conservation of disk space, but may also introduce performance increases, as due to higher locality of reference
, less data has to be read, also translating into higher page cache
efficiency. However, these advantages can be negated by the increased complexity of implementation
.
, the most widely used read-write file systems with support for block suballocation are Btrfs
, ReiserFS
, Reiser4
, FreeBSD UFS2 (where it is ambiguously named "block level fragmentation").
Several read-only file systems do not use blocks at all and are thus implicitly using space as efficiently as suballocating file systems; such file systems double as archive formats
.
File system
A file system is a means to organize data expected to be retained after a program terminates by providing procedures to store, retrieve and update data, as well as manage the available space on the device which contain it. A file system organizes data in an efficient manner and is tuned to the...
s which allows large blocks or allocation units to be used while making efficient use of "slack" space at the end of large files, space which would otherwise be lost for other use to internal fragmentation.
In file systems that don't support fragments, this feature is also called tail merging or tail packing because it is commonly done by packing the "tail", or last partial block, of multiple files into a single block.
Rationale
File systems have traditionally divided the disk into equally sized blocks to simplify their design and limit the worst-case fragmentationFile system fragmentation
In computing, file system fragmentation, sometimes called file system aging, is the inability of a file system to lay out related data sequentially , an inherent phenomenon in storage-backed file systems that allow in-place modification of their contents. It is a special case of data fragmentation...
. Block sizes are typically multiples of 512 due to the size of hard disk sector
Disk sector
In computer disk storage, a sector is a subdivision of a track on a magnetic disk or optical disc. Each sector stores a fixed amount of user data. Traditional formatting of these storage media provides space for 512 bytes or 2048 bytes of user-accessible data per sector...
s. When files are allocated by some traditional file systems, only whole blocks can be allocated to individual files. But as file sizes are often not multiples of the file system block size, this design inherently results in the last blocks of files (called tails) occupying only a part of the block, resulting in what is called internal fragmentation (not to be confused with external fragmentation). This waste of space can be significant if the file system stores many small files and can become critical when attempting to use higher block sizes to improve performance. FFS
Unix File System
The Unix file system is a file system used by many Unix and Unix-like operating systems. It is also called the Berkeley Fast File System, the BSD Fast File System or FFS...
and other derived UNIX file systems support fragments which greatly mitigate this effect.
Suballocation schemes
Block suballocation addresses this problem by dividing up a tail block in some way to allow it to store fragments from other files.Some block suballocation schemes can perform allocation at the byte level; most, however, simply divide up the block into smaller ones (the divisor usually being some power of 2). For example, if a 38 KiB
Kibibyte
The kibibyte is a multiple of the unit byte for quantities of digital information. The binary prefix kibi means 1024; therefore, 1 kibibyte is . The unit symbol for the kibibyte is KiB. The unit was established by the International Electrotechnical Commission in 1999 and has been accepted for use...
file is to be stored in a file system
File system
A file system is a means to organize data expected to be retained after a program terminates by providing procedures to store, retrieve and update data, as well as manage the available space on the device which contain it. A file system organizes data in an efficient manner and is tuned to the...
using 32 KiB blocks, the file would normally span two blocks, or 64 KiB, for storage; the remaining 26 KiB of the second block becomes unused slack space. With a 8 KiB block suballocation, however, the file would occupy just 8 KiB of the second block, leave 2 KiB slack and free the other 24 KiB of the block for other files.
Tail packing
Some file systems have since been designed to take advantage of this unused space, and can pack the tails of several files in a single shared tail block. While this may, at first, seem like it would significantly increase file system fragmentation, the negative effect can be mitigated with readaheadReadahead
readahead is the file prefetching technology used in the Linux operating system. It is a system call that loads a file's contents into the page cache. When a file is subsequently accessed, its contents are read from physical memory rather than from disk, which is much faster.Many distributions of...
features on modern operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
s – when dealing with short files, several tails may be close enough to each another to be read together, and thus a disk seek is not introduced. Such file systems often employ heuristics in order to determine whether tail packing is worthwhile in a given situation,
and defragmentation
Defragmentation
In the maintenance of file systems, defragmentation is a process that reduces the amount of fragmentation. It does this by physically organizing the contents of the mass storage device used to store files into the smallest number of contiguous regions . It also attempts to create larger regions of...
software may use a more involved heuristic.
Efficiency
In some scenarios where the majority of files are shorter than half the block size, such as in a folder of small source codeSource code
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
files or small bitmap images, tail packing can increase storage efficiency even more than twofold, compared to file systems without tail packing.
This not only translates into conservation of disk space, but may also introduce performance increases, as due to higher locality of reference
Locality of reference
In computer science, locality of reference, also known as the principle of locality, is the phenomenon of the same value or related storage locations being frequently accessed. There are two basic types of reference locality. Temporal locality refers to the reuse of specific data and/or resources...
, less data has to be read, also translating into higher page cache
Page cache
In computing, page cache, sometimes ambiguously called disk cache, is a "transparent" buffer of disk-backed pages kept in main memory by the operating system for quicker access. Page cache is typically implemented in kernels with the paging memory management, and is completely transparent to...
efficiency. However, these advantages can be negated by the increased complexity of implementation
Implementation
Implementation is the realization of an application, or execution of a plan, idea, model, design, specification, standard, algorithm, or policy.-Computer Science:...
.
, the most widely used read-write file systems with support for block suballocation are Btrfs
Btrfs
Btrfs is a GPL-licensed copy-on-write file system for Linux.Development began at Oracle Corporation in 2007....
, ReiserFS
ReiserFS
ReiserFS is a general-purpose, journaled computer file system designed and implemented by a team at Namesys led by Hans Reiser. ReiserFS is currently supported on Linux . Introduced in version 2.4.1 of the Linux kernel, it was the first journaling file system to be included in the standard kernel...
, Reiser4
Reiser4
Reiser4 is a computer file system, successor to the ReiserFS file system, developed from scratch by Namesys and sponsored by DARPA as well as Linspire...
, FreeBSD UFS2 (where it is ambiguously named "block level fragmentation").
Several read-only file systems do not use blocks at all and are thus implicitly using space as efficiently as suballocating file systems; such file systems double as archive formats
File archiver
A file archiver is a computer program that combines a number of files together into one archive file, or a series of archive files, for easier transportation or storage...
.