¿Cómo puedo predecir el tamaño de un sistema de archivos ISO 9660?

Question

Estoy archivando datos en DVD, y quiero empacar los DVD por completo. Sé los nombres y tamaños de todos los archivos que quiero en el DVD, pero no sé cuánto espacio ocupan los metadatos. Quiero obtener tantos archivos como sea posible en cada DVD, así que estoy usando una heurística Bubblesearch con codicioso bin-packing. Intento 10,000 alternativas y obtengo la mejor. Actualmente conozco el tamaño de todos los archivos y, como no sé cómo se almacenan los archivos en un sistema de archivos ISO 9660, agrego mucha pendiente para los metadatos. Me gustaría reducir la basura.

Podría usar genisoimage -print-size excepto que es demasiado lento --- dado 40,000 archivos que ocupan 500MB, toma alrededor de 3 segundos. Tomar 8 horas por DVD no está en las tarjetas. Modifiqué la fuente genisoimage antes y no estoy realmente dispuesto a intentar exprimir el algoritmo del código fuente; Espero que alguien sepa una mejor manera de obtener un presupuesto o me pueda indicar una especificación útil.

---

Aclarar el problema y la pregunta:

• necesito para quemar archivos que se dividen en varios DVDs, típicamente alrededor de cinco a la vez. El problema que trato de resolver es decidir qué archivos colocar en cada DVD, para que cada DVD (excepto el último) esté lo más lleno posible. Este problema es NP-difícil.

• Estoy usando el algoritmo estándar de empaquetado codicioso donde coloca primero el archivo más grande y lo coloca en el primer DVD que tiene espacio suficiente. Así que j_random_hacker, definitivamente soy no comenzando de forma aleatoria. Empiezo por ordenado y uso Bubblesearch para perturbar el orden en que se empaquetan los archivos. Este procedimiento mejora mi empaque desde aproximadamente el 80% de la capacidad estimada a más del 99.5% de la capacidad estimada. Esta pregunta se trata de haciendo un mejor trabajo al estimar la capacidad; actualmente mi capacidad estimada es menor que la capacidad real.

• He escrito un programa que intenta 10.000 perturbaciones, cada uno de los cuales implica dos pasos:

  1. elegir un conjunto de archivos
  2. Estimar la cantidad de espacio dichos archivos tendrán en DVD

  El paso 2 es el paso que trato de mejorar. En este momento, estoy "equivocando por el lado de la precaución", como sugiere Tyler D. Pero me gustaría hacerlo mejor. No puedo permitirme usar genisomage -print-size porque es demasiado lento. Del mismo modo, no puedo atacar los archivos en el disco, porque solo es demasiado lento, pero un archivo tar no tiene el mismo tamaño que una imagen ISO 9660. Es el tamaño de la imagen ISO 9660 que necesito para predecir. En principio, esto podría hacerse con total precisión, pero no sé cómo hacerlo. Esa es la pregunta.

---

Nota: estos archivos se encuentran en una máquina con 3 TB de almacenamiento en disco duro. En todos los casos, el tamaño promedio de los archivos es de al menos 10 MB; a veces es significativamente más grande. Entonces, es posible que genisomage sea lo suficientemente rápido después de todo, pero lo dudo --- parece funcionar escribiendo la imagen ISO en/dev/null, y no me puedo imaginar que será lo suficientemente rápido cuando el tamaño de la imagen se acerca a 4.7GB. No tengo acceso a esa máquina en este momento o cuando publiqué la pregunta original. Cuando tenga acceso en la tarde, trataré de obtener mejores números para la pregunta.Pero no creo que genisomage vaya a ser una buena solución --- aunque podría ser una buena forma de aprender un modelo del sistema de archivos que me dice cómo funciona. Saber que el tamaño del bloque es 2KB ya es útil.

También puede ser útil saber que los archivos en el mismo directorio se graban en el DVD de samae, lo que simplifica la búsqueda. Deseo acceder directamente a los archivos, lo que descarta tar-before-burning. (La mayoría de los archivos son de audio o video, lo que significa que no tiene sentido tratar de golpearlos con gzip.)

Answer 1

Gracias por la actualización detallada. Estoy satisfecho de que su estrategia actual de embalaje de contenedores sea bastante eficiente.

En cuanto a la pregunta: "Exactamente la cantidad de sobrecarga hace un sistema de archivos ISO 9660 para el paquete en n archivos por un total de b bytes?" solo hay 2 respuestas posibles:

1. Alguien ya ha escrito una herramienta eficiente para medir exactamente esto. Sin embargo, una búsqueda rápida en Google no arrojó nada que sea desalentador. Es posible que alguien en SO responda con un enlace a su herramienta de construcción casera, pero si no obtienes más respuestas durante unos días, es probable que también lo sea.
2. Necesita leer el readily available ISO 9660 specs y construir una herramienta usted mismo.

En realidad, hay una tercera respuesta:

(3) que realmente no se preocupan por el uso de todos los último byte en cada DVD. En ese caso, tome un pequeño puñado representativo de archivos de diferentes tamaños (digamos 5), acóplelos hasta que sean múltiplos de 2048 bytes, y ponga todos los 2^5 subconjuntos posibles hasta genisoimage -print-size. A continuación, coloque la ecuación nx + y = iso_size - total_input_size en ese conjunto de datos, donde n = número de archivos en un plazo determinado, para encontrar x, que es el número de bytes de sobrecarga por archivo, y y, que es la cantidad constante de sobrecarga (el tamaño de un sistema de archivos ISO 9660 que no contiene archivos). Redondea x y y y usa esa fórmula para estimar el tamaño del sistema de archivos ISO para un conjunto determinado de archivos. Para mayor seguridad, asegúrese de utilizar los nombres de archivo más largos que aparecen en cualquier parte de su colección para los nombres de los archivos de prueba, y ponga cada uno en una jerarquía de directorios separada que sea tan profunda como la jerarquía más profunda en su colección.

Answer 2

¿No se puede usar el alquitrán para almacenar los archivos en el disco? No está claro si está escribiendo un programa para hacer esto, o simplemente haciendo algunas copias de seguridad.

Quizás haga algo de experimentación y, por el lado de la precaución, algo de espacio libre en un disco no dolerá.

De alguna manera, me imagino que ya has considerado esto, o que mi respuesta no tiene sentido.

Answer 3

No estoy seguro exactamente cómo se encuentra actualmente este - según mi googlear "Bubblesearch" se refiere a una manera de elegir una ordenación de elementos que es en cierto sentido cerca de un ordenamiento codicioso, pero en En su caso, el orden de agregar archivos a un DVD no cambia los requisitos de espacio, por lo que este enfoque desperdicia tiempo considerando múltiples órdenes diferentes que equivalen al mismo conjunto de archivos.

En otras palabras, si usted está haciendo algo como lo siguiente para generar una lista de archivos candidato:

1. ordenar de forma aleatoria al azar de la lista de archivos.
2. Comenzando en la parte superior de la lista, elija con avidez todos los archivos que calcule que caben en un DVD hasta que no lo haga más.

A continuación, busca: el espacio de soluciones de forma ineficiente - para cualquier conjunto candidato final de n archivos, que está potencialmente considerando todas n! formas de producir ese conjunto. Mi sugerencia:

1. Ordene todos los archivos en orden decreciente de tamaño de archivo.
2. Marque el archivo (más grande) como "incluido" y elimínelo de la lista. (Debe estar incluido en algunos DVD, así que también podríamos incluirlo ahora.)
3. ¿Se puede incluir el archivo más alto de la lista sin que el tamaño del sistema de archivos ISO (estimado) exceda la capacidad del DVD? Si es así:
   • con probabilidad p (por ejemplo p = 0,5), marcar el archivo como "incluido".
4. Elimina el archivo superior de la lista.
5. Si la lista está vacía, tiene una lista de archivos candidatos. De lo contrario, vaya a 3.

Repita esto muchas veces y elija la mejor lista de archivos.

La sugerencia de Tyler D también es buena: si tiene ~ 40000 archivos que suman ~ 500Mb, eso significa un tamaño de archivo promedio de 12.5Kb. ISO 9660 usa un tamaño de bloque de 2Kb, lo que significa que esos archivos están desperdiciando en promedio 1Kb de espacio en disco, o aproximadamente el 8% de su tamaño. Así que empaquetarlos junto con el alquitrán primero ahorrará alrededor del 8% del espacio.

Answer 4

Nice thinking, J. Random. Por supuesto que no necesito hasta el último byte, esto es principalmente por diversión (y los derechos de fanfarronear en el almuerzo). Quiero poder escribir du en el CD-ROM y tenerlo muy cerca de 4700000000.

Miré las especificaciones de ECMA pero como la mayoría de las especificaciones es medio doloroso y no tengo confianza en mi capacidad para hacerlo bien . También parece no hablar sobre extensiones de Rock Ridge, o si lo hace, lo extrañé.

Me gusta su idea n. ° 3 y creo que la llevaré un poco más lejos: intentaré construir un modelo bastante rico de lo que está sucediendo y luego usar genisoimage -print-size en una serie de catálogos para estimar los parámetros del modelo . Entonces puedo usar el modelo para hacer mi estimación. Este es un proyecto de pasatiempo, así que tomará un tiempo, pero lo haré eventualmente. ¡Publicaré una respuesta aquí para decir cuánto desperdicio se elimina!

Answer 5

Recientemente realicé un experimento para encontrar una fórmula para hacer una estimación de llenado similar en dvds, y encontré una fórmula simple con algunas suposiciones ...Desde su publicación original, esta fórmula probablemente sea un número bajo para usted, parece que tiene múltiples directorios y nombres de archivos más largos.

Supuestos:

• todos los archivos son exactamente 8,3 caracteres.
• todos los archivos están en el directorio raíz.
• sin extensiones como Joliet.

La fórmula:

174 + floor(count/42) + sum(ceil(file_size/2048)) 

• recuento es el número de archivos
• file_size es el tamaño de cada archivo en bytes
• el resultado es en 2048 bloques de bytes.

un script de ejemplo:

#!/usr/bin/perl -w 
use strict; 
use POSIX; 

sub sum { 
    my $out = 0; 
    for(@_) { 
     $out += $_; 
    } 
    return $out; 
} 

my @sizes = (2048) x 1000; 
my $file_count = @sizes; 

my $data_size = sum(map { ceil($_/2048) } @sizes); 
my $dir_size = floor($file_count/42) + 1; 
my $overhead = 173; 

my $size = $overhead + $dir_size + $data_size; 

$\ = "\n"; 
print $size; 

Verifiqué esto en discos con un máximo de 150k archivos, con tamaños que van desde 200 bytes a 1 MiB.