¿Por qué no podemos insertar en archivos sin las escrituras adicionales? (No me refiero a añadir, ni sobre-escribir)

8

Esto ocurre como un problema independiente del lenguaje de programación para mí.

Tengo un archivo con el contenido

aaabddd

Cuando quiero insertar Cdetrás, bentonces mi código debe reescribirse dddpara obtener

aaabCddd

¿Por qué no puedo simplemente insertar Cen esta posición?

No puedo hacer esto en Java, Python, .... No puedo hacer esto en Linux, Windows, .... Estoy en lo cierto?

No entiendo por qué Cno se puede insertar simplemente sin las escrituras adicionales. ¿Alguien podría explicar por qué esto es así?

Usuario
fuente
2
Piense en lo que sucede con los bits en el disco cuando desea "insertar" algo en el byte 128 de un archivo de 2 gigabytes.
¿Quieres decir sin sistema operativo y sin sistema de archivos intermedio? Entonces no funcionará. Con los otros dos en su lugar, no tengo idea de por qué no puede funcionar.
Usuario
12
Tome 500 fichas de dominó y colóquelas de extremo a extremo en una línea. Ahora intente insertar uno en esa línea sin mover los otros.
GrandmasterB
2
@MichaelT En el mundo de mis sueños, solo deberías insertar otro bloque en la cadena de bloques que componen el archivo y distribuir el contenido del primer bloque actual en los primeros dos bloques. Por supuesto, esto requeriría los ejecutores del sistema de archivos para manejar bloques de tamaño irregular - pero en las situaciones en las que no necesita esta operación, sería mejorar la eficiencia tanto que ni siquiera es gracioso.
Kilian Foth
1
@User las preguntas sobre la fragmentación del sistema de archivos y cómo funciona Ext4 se mueve firmemente en el ámbito de SuperUser. Recuerde especificar completamente su problema o volverán a preguntar sobre bytes. Está preguntando sobre bloques y sistemas de archivos y gestores de volúmenes lógicos y similares.

Respuestas:

8

Dado que la mayoría de los sistemas de archivos almacenan el contenido de los archivos en bloques individuales que no son necesariamente contiguos en el disco físico, pero están vinculados a través de estructuras de puntero, parece que dicho modo - "insertar" en lugar de "agregar" o "sobrescribir" - debería ser posible, y ciertamente podría hacerse más eficiente que lo que tenemos que hacer ahora: leer todo el contenido, editar la secuencia de bytes y volver a escribir todo el contenido.

Sin embargo, para bien o para mal, la semántica UNIX de los sistemas de archivos se diseñó siguiendo el paradigma "aproximado y simple" en la década de 1970: le permite hacer todo, pero no necesariamente de la manera más eficiente posible. Hoy en día es casi impensable introducir un nuevo modo de apertura de archivos en la capa del Sistema de archivos virtual y tener alguna esperanza de que los principales sistemas de archivos adopten soporte para ello. Este es un motivo favorito mío, pero desafortunadamente es poco probable que se resuelva pronto.

Kilian Foth
fuente
2
Edificio que podría ser un proyecto paralelo interesante por un tiempo ...
FrustratedWithFormsDesigner
1
El almacenamiento a nivel de bloque complica la pregunta un paso más allá. Siguiendo con el ejemplo original del OP, las dos versiones de la cadena deberían caber en un solo bloque. Los bytes deben escribirse secuencialmente y eso es lo que necesita desplazar la cola de la cadena hacia abajo en cualquier cantidad insertada.
Solo sería eficiente si tiene que insertar exactamente la cantidad de datos que se pueden almacenar en un bloque, exactamente en el borde entre dos bloques existentes.
Idan Arye
Kilian Forth parece estar en lo cierto. Le pregunté a un profesor sobre esto y él me dijo lo mismo: el diseño "aproximado y simple" permite la portabilidad y, por lo tanto, se usa más ampliamente. No muchos sistemas de archivos permiten la inserción y menos aún los sistemas operativos lo exponen, para aplicarlo a una interfaz portátil. @ GlenH7 Dos personas que editaron mi pregunta hicieron que pareciera que preguntaría acerca de los bytes y revirtieron mi aclaración. La verdadera pregunta es sobre la interfaz que utilizamos.
Usuario
Sí, los bloques están vinculados mediante punteros y, por lo tanto, el contenido del archivo no tiene que almacenarse contiguamente, pero cuando se almacenan contiguamente, el hardware puede leer bloque tras bloque sin tener que reducir la velocidad. Si tuviera que seguir puntero por puntero, entonces el cabezal de lectura se movería constantemente. Es por eso que la desfragmentación ayuda a acelerar su computadora. Pone los punteros de bloque para archivos en bloques contiguos. Entonces el comando no es leer el bloque 1, leer el bloque 3, leer el bloque 9, leer el bloque n ... se convierte en leer los bloques 1 a n. El hardware puede hacer eso, mucho más eficientemente.
Dunk
12

Teóricamente, podría implementar un archivo que permitiría este tipo de cosas. Sin embargo, para obtener la máxima flexibilidad, necesitaría almacenar un puntero al siguiente byte junto con cada byte en el archivo. Suponiendo un puntero de 64 bits, eso significaría que 8 de cada 9 bytes de su archivo estaría compuesto por punteros internos. Por lo tanto, se necesitarían 9000 bytes de espacio para almacenar 1000 bytes de datos reales. Leer el archivo también sería lento, ya que necesitaría leer cada byte, leer el puntero, seguir el puntero para leer el siguiente byte, etc., en lugar de leer bloques de datos grandes y contiguos del disco.

Obviamente, este tipo de enfoque no es práctico. Sin embargo, podría dividir el archivo en, por ejemplo, bloques de 32 kb. Eso haría que sea relativamente fácil agregar 32 kb de datos en cualquier límite de 32 kb en el archivo. No sería más fácil agregar un solo byte como el quinto byte del archivo. Sin embargo, si reserva algo de espacio libre en cada bloque, podría permitir que se realicen pequeñas adiciones de datos que solo afectarían los datos en ese bloque único. Tendría una penalización en términos de tamaño de archivo, por supuesto, pero potencialmente una razonable. Sin embargo, descubrir cuánto espacio reservar y cómo dividir bloques tiende a ser mucho más fácil para una aplicación en particular que para un sistema de propósito general; lo que funciona en un contexto puede ser muy malo en otro dependiendo del acceso al archivo y características de modificación.

De hecho, muchos sistemas que pasan mucho tiempo interactuando con archivos implementan algo como lo que describí anteriormente cuando implementan su abstracción de archivo particular. Las bases de datos, por ejemplo, generalmente implementarán algún concepto de un "bloque" como la unidad más pequeña de E / S con la que pueden trabajar y generalmente reservarán una cierta cantidad de espacio para el crecimiento futuro, de modo que actualizar una fila en una tabla solo afecte un bloque en el que se almacenan esos datos en lugar de reescribir todo el archivo. Diferentes bases de datos, por supuesto, tienen diferentes implementaciones con diferentes compensaciones.

Justin Cave
fuente
3
También mencionaría que el desafío de "buscar el bloque que está a 1 gigabyte de un archivo de 2 gigabytes" podría llevar un poco de tiempo con la lista vinculada de implementación de bytes.
El problema de lo que sucede durante las inserciones es motivo de gran consternación entre las personas que diseñan la desduplicación para sistemas de almacenamiento.
Blrfl
Gracias por entender que no quise hablar sobre bytes sino sobre la imagen más grande.
Usuario
8

El "problema" se reduce a cómo los archivos se escriben en el medio de almacenamiento byte a byte.

En su representación más básica, un archivo no es más que una serie de bytes escritos en el disco (también conocido como medio de almacenamiento). Entonces su cadena original se ve así:

Address  Value
0x00     `a`
0x01     `a`
0x02     `a`
0x03     `b`
0x04     `d`
0x05     `d`
0x06     `d`

Y desea insertar Cen la posición 0x04. Eso requiere desplazar los bytes 4 - 6 hacia abajo un byte para que pueda insertar el nuevo valor. Si no lo hace, sobrescribirá el valor que actualmente está en 0x04, que no es lo que desea.

Address  Value
0x00     `a`
0x01     `a`
0x02     `a`
0x03     `b`
0x04     `C`
0x05     `d`
0x06     `d`
0x07     `d`

Entonces, la razón por la que tiene que volver a escribir la cola del archivo después de insertar un nuevo valor es porque no hay espacio dentro del archivo para aceptar el valor insertado. De lo contrario, sobrescribiría lo que había allí.


Anexo 1 : Si desea reemplazar el valor de bcon, Centonces no necesita volver a escribir la cola de la cadena. Reemplazar un valor con un valor de tamaño similar no requiere una reescritura.

La adición 2 : Si desea reemplazar la cadena abcon el Centonces tendría necesidad de volver a escribir el resto del archivo que se ha creado un vacío en el archivo.

Anexo 3 : Las construcciones de nivel de bloque fueron creadas para hacer más fácil el manejo de archivos grandes. En lugar de tener que encontrar 1 millón de espacio contiguo para su archivo, ahora solo necesita encontrar 1 millón de bloques disponibles para escribir en su lugar.

En teoría, podría construir un sistema de archivos que vincule byte a byte de forma similar a lo que proporcionan los bloques. Luego puede insertar un nuevo byte actualizando el | de punteros en el punto apropiado. Me arriesgaría a adivinar que el rendimiento en eso sería bastante pobre.


Como sugirió el Gran Maestro B , use una imagen de fichas de dominó apiladas para comprender visualmente cómo se representa el archivo.

dominó

No puede insertar otro dominó dentro de la línea de dominó sin hacer que todo se caiga. Tienes que crear el espacio para el nuevo dominó moviendo a los demás por la línea. Mover fichas de dominó por la línea equivale a volver a escribir la cola del archivo después del punto de inserción.

Comunidad
fuente
Suponga que ab C yd no son caracteres sino gigabytes de caracteres. ¿Podría abordar esto en su respuesta? Me gusta la imagen, pero también creo que la gente se acercaría a insertar 1000 fichas de dominó en 2000 fichas de manera diferente que 1 ficha de dominó en 6 fichas de dominó.
Usuario
@Usuario: los GB de caracteres en lugar de bytes cambian fundamentalmente la naturaleza de su pregunta y ahora deben considerarse los bloques para el almacenamiento. En un nivel simple, la respuesta es la misma. No puede insertar algo dentro de una serie contigua de "lo que sea" sin crear espacio.
0

La inserción en un archivo no se implementa en la mayoría de los sistemas de archivos porque se considera una operación "costosa" (que consume mucho tiempo y espacio) con repercusiones "costosas" potencialmente a largo plazo y modos de falla adicionales.

Un sistema de archivos con semántica de inserción probablemente usaría shift & insert (potencialmente muy costoso cuando inserta al frente de un archivo grande, pero no tiene / tiene pocos efectos secundarios a largo plazo) o algún tipo de asignación de montón generalizada con tamaños de asignación de longitud variable ( rendimiento muy mal comportamiento en algunos casos [¡imagínense las caras interactivas de los usuarios si intentan guardar un archivo durante un GC para detener el mundo!]).

Si desea experimentar, puede crear fácilmente una abstracción de E / S de archivo en Java o Python que implemente la inserción. Si tiene éxito y tiene características de rendimiento de buen comportamiento, tiene la base para un excelente trabajo de investigación. Buena suerte.

Scott Leadley
fuente
esto no parece ofrecer nada sustancial sobre las 6 respuestas anteriores
mosquito
Puede escribir todo el software que desee, pero no cambiará la forma en que funciona el hardware. El hardware funciona leyendo / escribiendo en bloques / páginas. En un HDD, si esos datos no son contiguos, entonces el cabezal de lectura debe moverse, lo que reduce drásticamente el tiempo de acceso a los archivos. Cualquier operación de inserción "por el solo hecho de ser una inserción" debe almacenarse en otro lugar y no contiguamente. Así que seguro, la inserción posiblemente será más rápida (para archivos muy grandes) pero la lectura será mucho más lenta.
Dunk
0

La forma más eficiente de insertar un bloque de bytes en el medio de un archivo sería:

  1. Asigna el archivo a la memoria
  2. Agregue los bytes al final de la imagen de memoria del archivo
  3. Gire estos archivos en su lugar (con un algoritmo estándar disponible en la Biblioteca estándar de C ++, por ejemplo)
  4. Deje que el sistema operativo se encargue de escribir bloques sucios en el disco
Laurent LA RIZZA
fuente
-1

Primero debe leer todo después del punto de inserción, luego volver a escribirlo con el espacio que va a insertar. Luego puede escribir sus datos de "inserción" en el lugar correcto. Funcionamiento de rendimiento extremadamente pobre, por lo tanto, no es compatible de forma nativa

Brian Knoblauch
fuente
1
¿Qué hay de un SSD con acceso aleatorio? También los archivos se dividen en partes por el sistema de archivos. ¿Cómo se relaciona eso con escribir todo de nuevo?
Usuario
@Usuario seguro de que puede acceder al azar (aunque no está haciendo el acceso a nivel de bit, todavía está haciendo el nivel de bloque) ... pero ¿cómo dice qué byte viene después?
1
SSD todavía lee y escribe una página a la vez. Entonces, para escribir su 1 byte que desea insertar, tendría que escribir una página completa de datos junto con la actualización de todas las tablas / punteros del sistema de archivos correspondientes. No me sorprendería si los sistemas de archivos iniciales tuvieran una operación similar a una inserción, pero se dieron cuenta de que agregaban mucho más gastos generales de los que ahorraron.
Dunk
-1

Cuando accede directamente a un archivo, está utilizando un nivel bajo que puede usarse para construir estructuras más sofisticadas. Considere crear una base de datos con sus datos que permita los tipos de acceso que necesita, incluida la inserción.

Sería menos costoso si solo necesita recorrer el archivo sin hacer accesos aleatorios a un desplazamiento específico. Si necesita acceso aleatorio por desplazamiento en el archivo, deberá actualizar el índice para todos los bytes más allá del punto de inserción.

En general, pagará al indexar las estructuras de datos, la memoria para almacenar el índice y los accesos adicionales al disco para actualizarlo.

Patricia Shanahan
fuente