Low Bandwidth Network Filesystem

Il Low Bandwidth Network Filesystem (LBFS) è un filesystem sviluppato all'MIT.

Il filesystem calcola l'hash di ciascun blocco del file e, per risparmiare nel trasferimento tra macchine in rete, solo i blocchi con differente checksum vengono trasferiti. Una suddivisione in blocchi di dimensione prefissata non è adeguata, in quanto l'aggiunta o rimozione di byte in un punto del file trasla il contenuto seguente, alterando tutti i blocchi successivi anche se il loro contenuto non è stato effettivamente cambiato. LBFS usa l'impronta di Rabin per la suddivisione in blocchi a grandezza variabile resistenti alla traslazione, calcolando l'impronta su una finestra di 48 byte e usando come breakpoint per i blocchi i punti nei quali i 13 bit meno significativi dell'impronta sono nulli. Essendo il risultato dell'impronta di Rabin un valore con buona approssimazione pseudo-casuale, la probabilità di una finestra di diventare breakpoint è nell'ordine di $2^{-13}$.

In principio, una qualsiasi funzione hash potrebbe essere usata per calcolare i breakpoint, ma essendo l'impronta di Rabin una funzione rolling hash, ha il vantaggio di essere economica da calcolare su una finestra scorrevole.