Orlov block allocator: Difference between revisions

Revision as of 15:45, 7 January 2010

Revision as of 00:28, 8 April 2010

Line 10:

== 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; [[Theodore_TsTheodore Ts'o|Ted]] 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.

Line 16:

== Performance ==

{{As of|2007|10}}, only one benchmark result<ref>{{cite|url=http://lwn.net/Articles/14631/|title=naive but spectacular ext3 HTREE+Orlov benchmark|author=Bert Hubert

}}</ref> with the new allocator seems to have have been posted. The results are promising: the time required to traverse through a Linux kernel tree was reduced by roughly 30%.

== Evolution ==