Block suballocation

Block suballocation is a feature of some computer file systems 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. [us patent|6041407 (Fundamental patent.)]

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 fragmentation. Block sizes are typically multiples of 512 due to the size of hard disk sectors. When files are allocated by the traditional file system, 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) to occupy only a part of the block, resulting in what is called internal fragmentation (not to be confused with external fragmentation). This wastage in space can be significant if the file system stores many small files.

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

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 readahead features on modern operating systems – 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.

Efficiency

In some scenarios where the majority of files are shorter than half the block size, such as in a folder of small source code files or small bitmap images, tail packing can increase storage efficiency even more than twofold, compared to file systems without tail packing.cite web|author = Hans Reiser|date = 2001|title = Hard Disk usage, ReiserFS and Ext2fs |url = http://www.namesys.com/disk_usage.html|accessdate = 2006-12-14]

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. [cite web|author = Hans Reiser|date = 2001|title = ReiserFS file system design|url = http://www.namesys.com/X0reiserfs.html|accessdate = 2006-12-14]

As of 2007, the most widely used read-write file systems with support for block suballocation are ReiserFS, Reiser4 and FreeBSD UFS2 [citation|url = http://www.pacnog.org/pacnog1/day1/freebsd/intro-freebsd-additional-topics.pdf|first = Allen|last = Hervey |date = 2005-06-20|title = Introduction to FreeBSD, PacNOG I Workshop, Additional Topics, UFS2 and Soft Updates make for a powerful combination|page = 23|accessdate = 2007-11-04|work = PacNOG I] (where it is ambiguously named "block level fragmentation").

Several read-only file systems do not use blocks at all and are thus implicitly suballocated; such file systems double as archive formats.

Criticism

The ReiserFS file system is often criticized for its complexity, and being more prone to fragmentation than many other file systemsFact|date=July 2008, both potentially introduced by the tail packing functionality. This has led some people to suggest turning off tail packing (through the notail mount option) for performance-critical file systems.

See also

* File system
* Internal fragmentation
* Locality of reference

References


*


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • block suballocation —    A mechanism used in Novell NetWare that allows files to share the same block space by dividing each 8K hard disk block into smaller 512 byte segments. Files needing extra space can use these smaller segments rather than wasting a whole new… …   Dictionary of networking

  • Block (data storage) — In computing (specifically data transmission and data storage), block is a sequence of bytes or bits, having a nominal length (a block size ). Data thus structured is said to be blocked . The process of putting data into blocks is called blocking …   Wikipedia

  • Comparison of file systems — The following tables compare general and technical information for a number of file systems. Contents 1 General information 2 Limits 3 Metadata 4 Features …   Wikipedia

  • Unix File System — Infobox filesystem full name = UNIX file system name = UFS developer = CSRG introduction os = 4.2BSD introduction date = partition id = directory struct = table file struct = bad blocks struct = max file size = 2^73 bytes (8 ZiB) max files no =… …   Wikipedia

  • Ext3 — infobox filesystem name = ext3 full name = Third extended file system developer = Stephen Tweedie introduction os = Linux 2.4.15 introduction date = November 2001 partition id = 0x83 (MBR) EBD0A0A2 B9E5 4433 87C0 68B6B72699C7 (GPT) directory… …   Wikipedia

  • Reiser4 — Developer Namesys Full name Reiser4 Introduced 2004 (Linux) Partition identifier Apple UNIX SVR2 (Apple Partition Map) 0x83 (MBR) Basic data partition (GPT) …   Wikipedia

  • NetWare File System — NWFS Developer Novell Full name NetWare File System Limits Max file size 4 GiB Max volume size 1 TiB Features …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.