Perché non possiamo inserire nei file senza le scritture aggiuntive? (Non intendo né accoda, né sovrascrivo)

Dato che la maggior parte dei file system memorizza il contenuto di file in singoli blocchi che non sono necessariamente contigui sul disco fisico, ma collegati tramite strutture di puntatori, sembra che tale modalità - "inserendo" piuttosto che "accoda" o "sovrascriva" "- dovrebbe essere possibile, e potrebbe certamente essere reso più efficiente di quello che dobbiamo fare ora: leggere l'intero contenuto, modificare lo stream di byte e riscrivere l'intero contenuto.

Tuttavia, nel bene o nel male, la semantica UNIX dei file system è stata progettata secondo il paradigma "rozzo e semplice" degli anni '70: consente di fare tutto, ma non necessariamente nel modo più efficiente possibile. Oggigiorno è quasi impensabile introdurre una nuova modalità di apertura file nel livello Virtual File System e sperare che i principali file system adottino il supporto per questo. Questo è un mio problema, ma sfortunatamente è improbabile che possa essere risolto presto.

In teoria, potresti implementare un file che consentirebbe questo genere di cose. Per la massima flessibilità, tuttavia, è necessario memorizzare un puntatore al byte successivo insieme a ogni byte nel file. Supponendo un puntatore a 64 bit, ciò significherebbe che 8 di ogni 9 byte del file saranno composti da puntatori interni. Quindi occorrerebbero 9000 byte di spazio per memorizzare 1000 byte di dati effettivi. Anche la lettura del file sarebbe lenta dato che dovresti leggere ogni byte, leggere il puntatore, seguire il puntatore per leggere il byte successivo, ecc. Piuttosto che leggere blocchi di dati contigui di grandi dimensioni dal disco.

Ovviamente, questo tipo di approccio non è pratico. Potresti, tuttavia, suddividere il file in, diciamo blocchi da 32 kb. Ciò renderebbe relativamente facile aggiungere 32 kb di dati a qualsiasi limite di 32 kb nel file. Non sarebbe più semplice aggiungere un singolo byte come quinto byte del file. Se si riserva uno spazio libero in ogni blocco, tuttavia, è possibile consentire l'esecuzione di piccole aggiunte di dati che influirebbero solo sui dati di quel singolo blocco. Avresti una penalità in termini di dimensioni del file, ovviamente, ma potenzialmente ragionevole. Calcolare quanto spazio riservare e come dividere i blocchi, tuttavia, tende ad essere molto più semplice per una particolare applicazione che per un sistema generico-- ciò che funziona in un contesto può essere molto cattivo in un altro a seconda dell'accesso ai file e caratteristiche di modifica.

In effetti, molti sistemi che trascorrono molto tempo interagendo con i file implementano qualcosa di simile a quello che ho descritto sopra quando implementano la loro particolare astrazione di file. I database, ad esempio, implementeranno generalmente un concetto di "blocco" come la più piccola unità di I / O con cui possano lavorare e generalmente riserveranno una certa quantità di spazio per la crescita futura in modo che l'aggiornamento di una riga in una tabella influenzi solo il un blocco su cui vengono memorizzati i dati anziché riscrivere l'intero file. Diversi database, ovviamente, hanno diverse implementazioni con diversi compromessi.

Il "problema" si riduce al modo in cui i file vengono scritti sul supporto di memorizzazione in modo byte per byte.

Nella sua rappresentazione di base, un file non è altro che una serie di byte scritti sul disco (ovvero un supporto di memorizzazione). Quindi la tua stringa originale assomiglia a:

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

E vuoi inserire C nella posizione 0x04. Ciò richiede lo spostamento dei byte 4 - 6 di un byte in modo da poter inserire il nuovo valore. Se non lo fai, stai per sovrascrivere il valore che è attualmente in 0x04 che non è quello che vuoi.

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

Quindi il motivo per cui è necessario riscrivere la coda del file dopo aver inserito un nuovo valore è perché non c'è spazio all'interno del file per accettare il valore inserito. Altrimenti dovresti sovrascrivere quello che c'era.

Addendum 1 : se si desidera sostituire il valore di b con C , allora è necessario non scrivi la coda della stringa. Sostituire un valore con un valore di dimensioni simili non richiede una riscrittura.

Addendum 2 : se vuoi sostituire la stringa ab con C , allora vorrebbe dover riscrivere il resto del file come te ' hai creato una lacuna nel file.

Addendum 3 : costrutti a livello di blocco sono stati creati per semplificare la gestione di file di grandi dimensioni. Invece di dover trovare 1 milione di spazio contiguo per il tuo file, ora devi solo trovare 1 milione di blocchi disponibili da scrivere.

In teoria, è possibile costruire un filesystem che abbia un collegamento byte per byte simile a quello fornito dai blocchi. Quindi è possibile inserire un nuovo byte aggiornando a | dai puntatori al punto appropriato. Rischerei di indovinare che le prestazioni sarebbero piuttosto scadenti.

Come suggerito da Grandmaster B , usa un'immagine di domino sovrapposti per capire visivamente come viene rappresentato il file.

Non puoi inserire un altro domino all'interno della linea del domino senza far cadere tutto. Devi creare lo spazio per il nuovo domino spostando gli altri lungo la linea. Spostare i domino lungo la linea equivale a riscrivere la coda del file dopo il punto di inserimento.

Il modo più efficace per inserire un blocco di byte nel mezzo di un file sarebbe:

1. mappa il file in memoria
2. Aggiungi i byte alla fine dell'immagine di memoria del file
3. Ruota questi file in posizione (con un algoritmo standard disponibile nella libreria standard C ++, ad esempio)
4. Lascia che il sistema operativo si occupi di scrivere blocchi sporchi sul disco

Per prima cosa devi leggere tutto dopo il punto di inserimento, quindi riscriverlo di tutto lo spazio che stai per inserire. Quindi puoi scrivere i tuoi dati "inserisci" nella posizione corretta. Operazione con prestazioni estremamente scarse, quindi non supportata nativamente.

L'inserimento in un file non è implementato nella maggior parte dei file system perché è considerato un'operazione "costosa" (time-eating e space eating) con ripercussioni "costose" potenzialmente a lungo termine e modalità di errore aggiuntive.
Un file system con semantica di inserimento probabilmente userebbe shift & insert (potenzialmente molto costoso quando si inserisce nella parte anteriore di un file di grandi dimensioni, ma nessun / pochi effetti collaterali a lungo termine) o una sorta di allocazione heap generalizzata con allocazione di lunghezza variabile dimensioni (prestazioni molto mal funzionanti in alcuni casi [immagina i volti degli utenti interattivi se provano a salvare un file durante un GC stop-the-world!]).
Se vuoi sperimentare, puoi facilmente creare un'astrazione di I / O di file in Java o Python che implementa l'inserimento. Se ci riesci e ha caratteristiche prestazionali ben educate, hai le basi per un eccellente documento di ricerca. Buona fortuna.

Quando si accede direttamente a un file si sta utilizzando un livello basso che può essere utilizzato per costruire strutture più sofisticate. Prendi in considerazione la possibilità di creare un database con i tuoi dati che consenta i tipi di accesso necessari, incluso l'inserimento.

Sarebbe meno costoso se hai solo bisogno di scorrere il file senza accedere casualmente a un offset specificato. Se hai bisogno dell'accesso casuale per offset nel file, dovrai aggiornare l'indice per tutti i byte oltre il punto di inserimento.

In generale, pagherai le strutture dei dati di indicizzazione, la memoria per memorizzare l'indice e gli accessi al disco aggiuntivi per aggiornarlo.