Asignador de bloques Orlov

El asignador de bloques de Orlov es un algoritmo para definir dónde residirá un archivo particular en un sistema de archivos determinado (por bloques), a fin de acelerar las operaciones del disco.

El esquema debe su nombre a 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 luego se utilizó en las variantes del kernel BSD Fast Filesystem .

El rendimiento de un sistema de archivos depende de muchas cosas; uno de los factores cruciales es cómo ese sistema de archivos distribuye los archivos en el disco. En general, es mejor mantener juntos los elementos relacionados. Los sistemas de archivos ext2 y ext3 de Linux , por ejemplo, han intentado distribuir directorios en los cilindros del disco. Imagine configurar 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, puede que no quede espacio para el contenido de esos directorios. Los archivos de usuario, por lo tanto, terminan ubicándose lejos de los directorios que los contienen, y el rendimiento se ve afectado.

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

Básicamente, el algoritmo de Orlov intenta distribuir directorios de "nivel superior" asumiendo que cada uno de ellos no está relacionado con 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 agregó un indicador de inodo especial que permite al administrador del sistema marcar otros directorios como directorios de nivel superior también. Si /homereside en el sistema de archivos raíz, un comando simple chattrhará que el sistema lo trate como un directorio de nivel superior.

Al crear un directorio que no está en un directorio de nivel superior, el algoritmo de Orlov intenta colocarlo en el mismo grupo de cilindros que su directorio padre. Sin embargo, se tiene un poco más de cuidado para garantizar que el contenido del directorio también pueda caber en ese grupo de cilindros; si no hay muchos inodos o bloques disponibles en el grupo, el directorio se colocará en un grupo de cilindros diferente que tenga más recursos disponibles. El resultado de todo esto, con suerte, es una localidad mucho mejor para los archivos que están realmente relacionados entre sí y es probable que se acceda a ellos juntos.

Se ha demostrado que el asignador de bloques Orlov ofrece mejoras de rendimiento en cargas de trabajo que recorren árboles de directorios ^[2] en FreeBSD. Hasta octubre de 2007 ^[actualizar], sólo se ha publicado un resultado de evaluación comparativa ^[3] para ext3, utilizando el asignador. Los resultados son prometedores: el tiempo necesario para recorrer un árbol de kernel de Linux se redujo en aproximadamente un 30%.

El esquema Orlov necesita una evaluación comparativa más rigurosa; también necesita algunas 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 Orlov
• Asignador de bloques Orlov para ext3 Correo electrónico de Theodore Ts'o a Linus Torvalds y Alexander Viro