Asignador de bloques de Orlov

El asignador de bloques de Orlov es un algoritmo que define dónde residirá un archivo en particular dentro de un sistema de archivos determinado (por bloques), con el fin de acelerar las operaciones de disco.

El esquema recibe su nombre de su creador, Grigoriy Orlov, quien publicó por primera vez, en 2000, una breve descripción e implementación para OpenBSD ^{[ 1 ]} de la técnica, que posteriormente se utilizó en las variantes del kernel BSD Fast Filesystem .

El rendimiento de un sistema de archivos depende de muchos factores; uno de los más importantes es cómo organiza los archivos en el disco. En general, lo ideal es mantener juntos los elementos relacionados. Los sistemas de archivos Linux ext2 y ext3 , por ejemplo, han intentado distribuir los directorios en los cilindros del disco. Imaginemos un sistema con los directorios personales de los usuarios en /home: si todos los directorios de primer nivel dentro de /home (es decir, los directorios personales de numerosos usuarios) se colocan uno al lado del otro, es posible que no quede espacio para el contenido de dichos directorios. En consecuencia, los archivos de usuario terminan ubicados lejos de los directorios que los contienen, lo que repercute negativamente en el rendimiento.

La distribución de directorios en el disco permite que los archivos de un mismo directorio permanezcan más o menos contiguos a medida que aumenta su número y/o tamaño, pero existen algunas situaciones en las que esto provoca una dispersión excesiva de los datos en la superficie del disco.

Básicamente, el algoritmo de Orlov intenta distribuir los directorios de nivel superior bajo el supuesto de que cada uno es independiente de los demás. Los directorios creados en el directorio raíz de un sistema de archivos se consideran directorios de nivel superior; Theodore Ts'o añadió un indicador de inodo especial que permite al administrador del sistema marcar otros directorios como directorios de nivel superior. Si /homereside en el sistema de archivos raíz, un simple chattrcomando hará que el sistema lo trate como un directorio de nivel superior.

Al crear un directorio que no se encuentra en un directorio de nivel superior, el algoritmo Orlov intenta ubicarlo en el mismo grupo de cilindros que su directorio padre. Sin embargo, se presta especial atención a que el contenido del directorio también quepa en dicho grupo de cilindros; si no hay suficientes inodos o bloques disponibles en el grupo, el directorio se ubicará en un grupo de cilindros diferente con más recursos disponibles. El resultado, idealmente, es una localidad mucho mejor para los archivos que están realmente relacionados entre sí y que probablemente se accedan de forma conjunta.

Se demostró que el asignador de bloques Orlov ofrece mejoras de rendimiento en cargas de trabajo que recorren árboles de directorios ^{[ 2 ]} en FreeBSD. A partir de octubre de 2007 , solo parece haberse publicado un resultado de referencia ^{[ 3 ] para ext3, utilizando el asignador. Los resultados son prometedores: el tiempo necesario para recorrer un árbol del kernel de Linux se redujo en aproximadamente un 30%.}

El método Orlov necesita una evaluación comparativa más rigurosa; también necesita pruebas de estrés serias para demostrar que el rendimiento no se degrada a medida que el sistema de archivos cambia con el tiempo.

• El asignador de bloques de Orlov
• Asignador de bloques Orlov para correo electrónico ext3 de Theodore Ts'o a Linus Torvalds y Alexander Viro