Orlov block allocator
Encyclopedia
The Orlov block allocator is an algorithm
to define where a particular file
will reside on a given filesystem (blockwise), so as to speed up disk operations.
and ext3
filesystems, for instance, have tried to spread directories on the cylinders of the disk. Imagine setting up a system with users' home directories in /home: if all the first-level directories within /home (i.e. the home directories for numerous users) are placed next to each other, there may be no space left for the contents of those directories. User files thus end up being placed far from the directories that contain them, and performance suffers.
Spreading directories on the disc allows files in the same directory to remain more or less contiguous as their number and/or size grows, but there are some situations where this causes excessive spreading of the data on the disc's surface.
has added a special inode
flag that allows the system administrator to mark other directories as being top-level directories as well. If /home lives in the root filesystem (and people do set up systems that way), a simple chattr command will make the system treat it as a top-level directory.
When creating a directory which is not in a top-level directory, the Orlov algorithm tries to put it into the same cylinder group as its parent. A little more care is taken, however, to ensure that the directory's contents will also be able to fit into that cylinder group; if there are not many inodes or blocks available in the group, the directory will be placed in a different cylinder group which has more resources available. The result of all this, hopefully, is much better locality for files which are truly related to each other and likely to be accessed together.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
to define where a particular file
Computer file
A computer file is a block of arbitrary information, or resource for storing information, which is available to a computer program and is usually based on some kind of durable storage. A file is durable in the sense that it remains available for programs to use after the current program has finished...
will reside on a given filesystem (blockwise), so as to speed up disk operations.
Etymology
The scheme is named after its creator Grigory Orlov, who first posted a brief description and implementation for OpenBSD of the technique which was later used in the BSD Fast Filesystem kernel variants.Background
The performance of a file system is dependent on many things; one of the crucial factors is just how that filesystem lays out files on the disk. In general, it is best to keep related items together. The linux ext2Ext2
The ext2 or second extended filesystem is a file system for the Linux kernel. It was initially designed by Rémy Card as a replacement for the extended file system ....
and ext3
Ext3
The ext3 or third extended filesystem is a journaled file system that is commonly used by the Linux kernel. It is the default file system for many popular Linux distributions, including Debian...
filesystems, for instance, have tried to spread directories on the cylinders of the disk. Imagine setting up a system with users' home directories in /home: if all the first-level directories within /home (i.e. the home directories for numerous users) are placed next to each other, there may be no space left for the contents of those directories. User files thus end up being placed far from the directories that contain them, and performance suffers.
Spreading directories on the disc allows files in the same directory to remain more or less contiguous as their number and/or size grows, but there are some situations where this causes excessive spreading of the data on the disc's surface.
How it works
Essentially, the Orlov algorithm tries to spread out "top-level" directories, on the assumption that they are unrelated to each other. Directories created in the root directory of a filesystem are considered top-level directories; TedTheodore Ts'o
Theodore Y. "Ted" Ts'o is a software developer mainly known for his contributions to the Linux kernel, in particular his contributions to file systems.He graduated in 1990 from MIT with a degree in computer science...
has added a special inode
Inode
In computing, an inode is a data structure on a traditional Unix-style file system such as UFS. An inode stores all the information about a regular file, directory, or other file system object, except its data and name....
flag that allows the system administrator to mark other directories as being top-level directories as well. If /home lives in the root filesystem (and people do set up systems that way), a simple chattr command will make the system treat it as a top-level directory.
When creating a directory which is not in a top-level directory, the Orlov algorithm tries to put it into the same cylinder group as its parent. A little more care is taken, however, to ensure that the directory's contents will also be able to fit into that cylinder group; if there are not many inodes or blocks available in the group, the directory will be placed in a different cylinder group which has more resources available. The result of all this, hopefully, is much better locality for files which are truly related to each other and likely to be accessed together.
Performance
, only one benchmark result with the new allocator seems to have been posted. The results are promising: the time required to traverse through a Linux kernel tree was reduced by roughly 30%.Evolution
The Orlov scheme needs more rigorous benchmarking; it also needs some serious stress testing to demonstrate that performance does not degrade as the filesystem is changed over time.External links
- The Orlov block allocator
- Orlov block allocator for ext3 e-mail from Theodore Ts'o to Linus TorvaldsLinus TorvaldsLinus Benedict Torvalds is a Finnish software engineer and hacker, best known for having initiated the development of the open source Linux kernel. He later became the chief architect of the Linux kernel, and now acts as the project's coordinator...
and Alexander Viro