Persistencia: árboles de datos almacenados como árboles de directorio

Question

Me preguntaba sobre los aspectos prácticos de almacenar una estructura de árbol en memoria como árbol de directorio para propósitos de persistencia. En mi caso, el sistema de archivos de destino será ZFS, y una vez que se haya creado la estructura, se accederá a ella mediante múltiples procesos con poca frecuencia.

¿Cómo funciona el rendimiento de un árbol de directorios como mecanismo de persistencia para los árboles de datos?

Answer 1

Para leer y escribir su árbol, llamará al sistema de archivos varias veces por nodo. Esto es mucho más costoso que cualquier código cuerdo que pueda idear para recorrer una imagen de memoria.

Si se trata de un enfoque sensato depende de cuál sea su patrón de uso. Si en una invocación típica de su código espera leer en toda la estructura de árbol, trabajar en él y luego escribirlo en su totalidad, es mejor ordenarlo en un solo archivo. Sin embargo, si espera leer / trabajar en / mutar solo unos pocos nodos, sin leer en la mayor parte del árbol, la diferencia en el rendimiento entre recorrer la estructura del directorio y hacer múltiples búsquedas / lecturas para atravesar un árbol almacenado en un solo archivo será mucho más pequeño, y puede valer la pena hacer lo primero por simplicidad / claridad / evitando reinventar las ruedas. Además, si varios procesos están haciendo esto simultáneamente, el bloqueo de nodos y subárboles se vuelve mucho más fácil con el enfoque basado en directorios.

Tenga en cuenta que para algunos sistemas de archivos de uso común, el tiempo para abrir una entrada de directorio depende del número total de entradas en el directorio.

EDITAR: He hecho cosas similares con ext3 para el backend CGI de un sitio; no reinventar la rueda hizo que la creación de prototipos fuera más rápida y el mantenimiento más sencillo, las lecturas / escrituras / bloqueo se escalaron bastante bien, pero los cambios muy frecuentes, del orden de cientos por segundo, en la estructura del directorio en sí funcionaron mal en el almacenamiento real ; Al final, reestructuré las cosas para que las secciones del árbol de directorios a las que se agregarían / ??eliminaran las entradas de directorio con mucha frecuencia terminaran en un volumen tmpfs; para mí, este conjunto de estado podría (costosamente) reconstruirse del almacenado en un almacenamiento menos volátil después de un reinicio. Tengo poca experiencia con ZFS y no conozco el patrón de uso previsto, así que no sé si esto sería un problema para usted. Si ahora estuviera haciendo esto para un sitio muy utilizado, probablemente rodaría mi propia biblioteca de bloqueo con nombre.

Answer 2

La mayoría de los sistemas de archivos están optimizados para acceder a un archivo abierto, por lo que abrir / cerrar un archivo lleva un tiempo considerable. Si cada hoja de su árbol es pequeña, leer / escribir toda la estructura llevaría mucho más tiempo del necesario.

Además, la mayoría de los sistemas de archivos tienen un bloque de asignación mínimo, generalmente alrededor de 2-8 KB. si tus hojas son mucho más pequeñas que eso, estarás desperdiciando mucho espacio.

En resumen, cuanto más pequeñas son tus hojas, peor es la idea.

Answer 3

Si lo entiendo correctamente, estás hablando de construir una estructura de árbol que daría una representación en código de tu sistema de archivos, por lo que sospecho que incurrirás en gastos generales al principio cuando estás leyendo en tu estructura de árbol, pero las búsquedas y recorridos posteriores del árbol probablemente sean más rápidos que llegar al almacenamiento en disco cada vez.

Answer 4

Posibles problemas:

• Puede hacer un uso ineficiente del espacio en disco (en muchos sistemas de archivos un directorio es un archivo y, como tal, ocupa un bloque completo en el disco ...)
• Será lento leer / escribir porque haces muchos accesos al sistema de archivos
• El sistema de archivos puede / impondrá límites en la longitud de cada nombre de elemento y / o caracteres que puede usar para nombres
• Será fácil para otros procesos corromper sus datos y / o requerir un costo de bloqueo considerable
• Cuando se usan `` discos '' de estado sólido, esto puede generar más escrituras que otros métodos y acortar la vida útil de los medios

Conclusión: puede que no valga la pena.