Orlov block allocator

<h2 id="etymology">Etymology</h2>
<p>The scheme is named after its creator Grigoriy Orlov, who first posted, in 2000, a brief description and implementation for <a href="/facts/OpenBSD/xmPS9tek">OpenBSD</a><a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> of the technique, which was later used in the <a href="/facts/Berkeley_Software_Distribution/XQKcURrh">BSD</a> Fast Filesystem <a href="/facts/Kernel_(operating_system)/uEj4U3Rz">kernel</a> variants.
</p>
<h2 id="background">Background</h2>
<p>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 <a href="/facts/Ext2/ftyVw4Kv">ext2</a> and <a href="/facts/Ext3/VSEhX1WQ">ext3</a> filesystems, for instance, have tried to spread directories on the cylinders of the disk. Imagine setting up a system with users' <a href="/facts/Home_directory/cQpQ4nvp">home directories</a> 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.
</p><p>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 disk's surface.
</p>
<h2 id="how-it-works">How it works</h2>
<p>Essentially, the Orlov algorithm tries to distribute "top-level" directories on the assumption that each is unrelated to the others. Directories created in the root directory of a filesystem are considered top-level directories; <a href="/facts/Theodore_Ts%27o/BVxQ3Cqc">Theodore Ts'o</a> added a special <a href="/facts/Inode/Ej7JIzyP">inode</a> flag that allows the system administrator to mark other directories as being top-level directories as well. If /home lives in the root filesystem, a simple chattr command will make the system treat it as a top-level directory.
</p><p>When creating a directory that 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 that has more resources available. The result of all this, hopefully, is much better locality for files that are truly related to each other and likely to be accessed together.
</p>
<h2 id="performance">Performance</h2>
<p>The Orlov block allocator was shown to offer performance gains on workloads that traverse directory trees<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> on FreeBSD. As of October 2007<a href="https://en.wikipedia.org/w/index.php?title=Orlov_block_allocator&action=edit">[update]</a>, only one benchmark result<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> for ext3, using the 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%.
</p>
<h2 id="evolution">Evolution</h2>
<p>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.
</p>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://lwn.net/Articles/14633/">The Orlov block allocator</a></li>
<li><a href="https://lwn.net/Articles/14447/">Orlov block allocator for ext3</a> e-mail from Theodore Ts'o to <a href="/facts/Linus_Torvalds/EdDKP534">Linus Torvalds</a> and Alexander Viro</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Grigoriy Orlov. "Directory Allocation Algorithm For FFS". Archived from the original on 2008-01-31. <a href="https://web.archive.org/web/20080131082712/http://www.ptci.ru/gluk/dirpref/old/dirpref.html" target="_blank">https://web.archive.org/web/20080131082712/http://www.ptci.ru/gluk/dirpref/old/dirpref.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Recent Filesystem Optimisations in FreeBSD <a href="http://static.usenix.org/events/usenix02/tech/freenix/dowse.html" target="_blank">http://static.usenix.org/events/usenix02/tech/freenix/dowse.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Bert Hubert, Naive but spectacular ext3 HTREE+Orlov benchmark <a href="https://lwn.net/Articles/14631/" target="_blank">https://lwn.net/Articles/14631/</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Orlov block allocator open-in-new

Orlov block allocator