Visualizza wikitesto di Low Bandwidth Network Filesystem

Il '''Low Bandwidth Network Filesystem''' (LBFS) è un filesystem sviluppato all'[[Massachusetts Institute of Technology|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 [[numeri pseudo-casuali|pseudo-casuale]], la probabilità di una finestra di diventare breakpoint è nell'ordine di <math>2^{-13}</math>.<ref>Athicha Muthitacharoen, Benjie Chen, David Mazières [https://pdos.csail.mit.edu/papers/lbfs:sosp01/lbfs.pdf "A Low-bandwidth Network File System"]</ref>

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.

== Note ==
<references />
{{portale|informatica}}

[[Categoria:File system]]