El asignador de bloques de Orlov es un algoritmo para definir dónde residirá un archivo en particular en un sistema de archivos dado (por bloques), para acelerar las operaciones del disco.
Etimología
El esquema lleva el 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 luego se utilizó en las variantes del kernel BSD Fast Filesystem .
Fondo
El rendimiento de un sistema de archivos depende de muchas cosas; Uno de los factores cruciales es cómo ese sistema de archivos coloca los archivos en el disco. En general, es mejor mantener juntos los elementos relacionados. Los sistemas de archivos Linux ext2 y ext3 , por ejemplo, han intentado distribuir directorios en los cilindros del disco. Imagine configurar un sistema con los directorios de inicio de los usuarios en / home: si todos los directorios de primer nivel dentro de / home (es decir, los directorios de inicio de numerosos usuarios) se colocan uno al lado del otro, es posible que no quede espacio para el contenido de esos directorios. De esta forma, los archivos de usuario terminan por colocarse 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 del mismo directorio permanezcan más o menos contiguos a medida que aumenta su número y / o tamaño, pero hay algunas situaciones en las que esto provoca una distribución excesiva de los datos en la superficie del disco.
Cómo funciona
Esencialmente, el algoritmo de Orlov intenta distribuir directorios de "nivel superior" asumiendo que ninguno de ellos 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 /home
vive en el sistema de archivos raíz, un chattr
comando simple hará 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 ponerlo en el mismo grupo de cilindros que su padre. Sin embargo, se tiene un poco más de cuidado para asegurar 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 ubicación mucho mejor para los archivos que están realmente relacionados entre sí y es probable que se acceda a ellos juntos.
Actuación
Se demostró que el asignador de bloques de Orlov ofrece mejoras de rendimiento en cargas de trabajo que atraviesan árboles de directorios [2] en FreeBSD. En octubre de 2007[actualizar], parece que solo se ha 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 aproximadamente en un 30%.
Evolución
El esquema de 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.
Referencias
- ^ Grigoriy Orlov. "Algoritmo de asignación de directorio para FFS" . Archivado desde el original el 31 de enero de 2008.
- ^ Optimizaciones recientes del sistema de archivos en FreeBSD
- ^ Bert Hubert, ingenuo pero espectacular ext3 HTREE + Benchmark Orlov
enlaces externos
- 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