Truncar el archivo al frente

Question

Un problema en el que estaba trabajando recientemente me hizo desear cortar el frente de un archivo. Algo así como un "truncado al frente", si se quiere. Truncar un archivo en el back-end es una operación común, algo que hacemos sin siquiera pensar mucho en ello. Pero cortar el frente de un archivo? Suena ridículo al principio, pero solo porque hemos sido entrenados para pensar que es imposible. Pero una operación lop puede ser útil en algunas situaciones.

Un ejemplo simple (ciertamente no es el único o necesariamente el mejor ejemplo) es una cola FIFO. Está agregando nuevos elementos al final del archivo y sacando elementos del archivo desde el frente. El archivo crece con el tiempo y hay un gran espacio vacío en el frente. Con los sistemas de archivos actuales, hay varias formas de evitar este problema:

• medida que se elimina cada artículo, copie el elementos restantes hasta reemplazarlo, y truncar el archivo. Aunque funciona, esta solución es muy costosa en el tiempo.
• supervisar el tamaño del espacio vacío en la parte delantera, y cuando alcanza un tamaño o porcentaje del tamaño del archivo completo en particular, siga todo lo que hasta y truncar el archivo. Esto es mucho más más eficiente que la solución anterior , pero aún cuesta tiempo cuando los elementos se mueven en el archivo.
• Implemente una cola circular en el archivo , agregando nuevos elementos al agujero en al frente del archivo ya que los elementos están eliminados. Esto puede ser bastante eficiente, , especialmente si no te importa la posibilidad de que salga del orden en la cola. Si le importa el pedido , existe la posibilidad de que tenga que mover elementos. Pero en general , una cola circular es bonita fácil de implementar y gestiona bien el disco .

Pero si hubo una operación lop, eliminar un elemento de la cola sería tan fácil como actualizar el marcador de inicio de archivo. Tan fácil, de hecho, como truncar un archivo. ¿Por qué, entonces, no hay tal operación?

Entiendo un poco acerca de la implementación de sistemas de archivos, y no veo ninguna razón en particular por la que esto sea difícil. Me parece que todo lo que necesitaría es otra palabra (¿dword, quizás?) Por entrada de asignación para decir dónde se inicia el archivo dentro del bloque. Con unidades de 1 terabyte por menos de $ 100 dólares estadounidenses, parece un precio bastante pequeño para pagar por dicha funcionalidad.

¿Qué otras tareas serían más fáciles si pudieras cortar la parte frontal de un archivo con la misma eficiencia con la que puedes truncar al final?

¿Puede pensar en algún motivo técnico por el que esta función no se haya podido agregar a un sistema de archivos moderno? ¿Otros motivos no técnicos?

Answer 1

Truncar los archivos en el frente no parece ser difícil de implementar a nivel del sistema.

Pero hay problemas.

• El primero está en el nivel de programación. Al abrir el archivo en acceso aleatorio, el paradigma actual es usar desplazamiento desde el comienzo del archivo para señalar diferentes lugares en el archivo. Si truncamos al principio del archivo (o realizamos la inserción o eliminación desde la mitad del archivo) ya no se trata de una propiedad estable. (Mientras appendind o truncando desde el final no es un problema).

En otras palabras, truncar el comienzo cambiaría el único punto de referencia y eso es malo.

• En un nivel de sistema, los usos existen como usted señaló, pero son bastante raros. Creo que la mayor parte del uso de los archivos es de tipo lectura, muchos leen, por lo que incluso truncar no es una característica crítica y probablemente podríamos prescindir de ella (bueno, algunas cosas se volverían más difíciles, pero nada sería imposible).

Queremos más accesos complejos (y de hecho hay necesidad) abrimos archivos en modo aleatorio y agregamos algo de información de estructura interna. Esta información también se puede compartir entre varios archivos. Esto nos lleva al último problema que veo, probablemente el más importante.

• En cierto sentido, cuando utilizamos archivos de acceso aleatorio con cierta estructura interna ... aún usamos archivos pero ya no estamos usando el paradigma de archivos. El caso típico es la base de datos en la que queremos realizar la inserción o eliminación de registros sin preocuparnos en absoluto por su lugar físico. Las bases de datos pueden usar archivos como implementación de bajo nivel, pero para fines de optimización, algunos editores de bases de datos eligen omitir por completo el sistema de archivos (piense en las particiones de Oracle).

No veo ninguna razón técnica por la que no podríamos hacer todo actualmente se realiza en un sistema operativo con archivos que utilizan una base de datos como capa de almacenamiento de datos. Incluso escuché que NTFS tiene muchos puntos en común con las bases de datos en sus partes internas. Un sistema operativo puede (y probablemente lo hará en alguna característica no tan lejana) usar otro paradigma que los archivos uno.

Resumiendo, creo que no es un problema técnico, solo un cambio de paradigma y que eliminar el principio definitivamente no está en el paradigma de archivo actual, pero no es un cambio grande y útil para obligar a cambiar nada.

Answer 2

Creo que hay un pequeño problema de huevo y gallina: porque los sistemas de archivos no han soportado este tipo de comportamiento de manera eficiente, las personas no han escrito programas para usarlo y porque las personas no han escrito programas para Úselo, hay pocos incentivos para que los sistemas de archivos lo admitan.

Siempre puede escribir su propio sistema de archivos para hacer esto, o modificar uno existente (aunque los sistemas de archivos utilizados "en la naturaleza" son probablemente bastante complicados, puede ser más fácil comenzar de cero).Si la gente lo encuentra lo suficientemente útil, podría funcionar ;-)

Answer 3

En realidad, hay sistemas de archivos base de registro: IBM tiene uno y creo que DEC VMS también tenía esta función. Me parece recordar los dos permitidos (¿permitir? Supongo que todavía están alrededor) borrar e insertar en posiciones aleatorias en un archivo.

Answer 4

NTFS puede hacer algo como esto con su escaso soporte de archivos pero en general no es tan útil.

Answer 5

En los sistemas de archivos que admiten archivos dispersos "perforar" un agujero y eliminar datos en una posición de archivo arbitraria es muy fácil. El sistema operativo solo tiene que marcar los bloques correspondientes como "no asignados". La eliminación de datos desde el comienzo de un archivo es solo un caso especial de esta operación. Lo principal que se requiere es una llamada al sistema que implementará tal operación: ftruncate2 (int fd, off_t offset, size_t count).

En los sistemas Linux esto se aplica realmente con la llamada fallocate sistema especificando la bandera FALLOC_FL_PUNCH_HOLE a cero a cabo una serie y la bandera FALLOC_FL_COLLAPSE_RANGE para eliminar completamente los datos de ese rango. Tenga en cuenta que existen restricciones sobre los rangos que se pueden especificar y que no todos los sistemas de archivos admiten estas operaciones.

Answer 6

También hay un comando UNIX llamado head - por lo que podría hacerlo a través de:

head -n1000 file > file_truncated