Filesystem con hashing

[etr]

Ciao a tutti,

leggendo il funzionamento di un servizio di backup online (non faccio nome per evitare spam), vedo che hanno sviluppato un filesystem che confrontando gli spezzoni di file verifica se ne esistono di uguali e in tal caso crea solo un riferimento senza riscrivere la parte di file risparmiando un po' di spazio. Se non sbaglio questo sistema è utilizzato anche da Gmail.

Bene, entrambi sono filesystem proprietari ... sapete per caso se ne esistono di liberi ? (con libero intendo gratuiti e non ma acquistabili/scaricabili)

Secondo voi, che risparmio si può avere in percentuale ?

Non so con che keywords googlare ... hints ?

Grasssie

[Uno]

Sei sicuro che sia un filesystem?
Perchè una cosa così la puoi fare anche in semplice php (oppure in qualcosa di più perfomante se occorre e sei sul tuo)

Se il file è al di sotto di una certa dimensione fai l'hash e lo metti in db (l'hash), se è sopra una certa dimensione carichi solo il primo pezzo, >hash > db.
Al confronto se non risulta nulla uguale, vuol dire che è un file nuovo, se risultano file/hash che sembrano uguali un ulteriore controllo per essere sicuri che sia veramente doppio e crei la nuova posizione su db che fa riferimento sempre all'altro file vecchio

Così al volo..... poi ci sono da inserire controlli etc...

[etr]

Loro parlano di filesystem.
Effettivamente è una bella idea... anche perchè risparmi un bel po' di spazio.
Infatti, spezzettando i file in piccole parti, statisticamente ce ne saranno tante uguali, con notevole risparmio di spazio ...

[gorkon]

*POTREBBE* esistere qualcosa per fuse, ma non ho indagato più di tanto.
Anche se - onestamente - non userei fuse in produzione neanche se avessi una pistola puntata alla nuca

[TheVice]

la tecnica è buona ma rende solo in caso di file particolarmente grandi e in numero spropositato. In più gli spezzoni in cui si dividono i files devono essere di lunghezza massima fissa (grosso limite). In buona sostanza funziona come la tecnica di compressione zip (LZ77) solo che viene usato l'hash come token di compressione.

[etr]

Si, in sistemi con molti file torna utile...ad esempio il sistema di backup da cui ho preso l'idea. Effettivamente se gli utenti hanno in maggioranza windows xp, ad esempio, le dll di sistema che la maggioranza backupperà sono tutte uguali e sarebbero un 300 MB ad utente (sparo a caso!) ... immaginiamo un migliaio di utenti .... sarebbero 300 GB "sprecati".

I files andrebbero spezzati in parti più piccole possibili (più piccola è la parte, più probabilità ho di averne già una uguale). In pratica il fs sarebbe diviso in due .. il vero storage con tante caselline formate da spezzone di file + hash e una parte di "corrispondenza" dove si salva la struttura logica del fs quindi "file salvato" formato dagli indirizzi delle celle dove sono salvati gli spezzoni. Ovviamente, se non ho una certa ripetitività dei files, questo porterebbe solo ad uno spreco di spazio ...

[Siggy]

I files andrebbero spezzati in parti più piccole possibili (più piccola è la parte, più probabilità ho di averne già una uguale).

Occhio pero' che piu' piccola e' la parte piu' grande sara' l'indice per fare il mapping per ogni utente....

[Uno]

Si, in sistemi con molti file torna utile...ad esempio il sistema di backup da cui ho preso l'idea. Effettivamente se gli utenti hanno in maggioranza windows xp, ad esempio, le dll di sistema che la maggioranza backupperà sono tutte uguali e sarebbero un 300 MB ad utente (sparo a caso!) ... immaginiamo un migliaio di utenti .... sarebbero 300 GB "sprecati".

I files andrebbero spezzati in parti più piccole possibili (più piccola è la parte, più probabilità ho di averne già una uguale). In pratica il fs sarebbe diviso in due .. il vero storage con tante caselline formate da spezzone di file + hash e una parte di "corrispondenza" dove si salva la struttura logica del fs quindi "file salvato" formato dagli indirizzi delle celle dove sono salvati gli spezzoni. Ovviamente, se non ho una certa ripetitività dei files, questo porterebbe solo ad uno spreco di spazio ...

Un conto però è solo evitare file uguali, basterebbe solo l'inizio e controlli sui positivi, se invece su grandi numeri si spera di spezzare i file in modo che un pezzetto sia utile a più file, non so se ci si guadagna come uso di risorse.

[etr]

Occhio pero' che piu' piccola e' la parte piu' grande sara' l'indice per fare il mapping per ogni utente....

Si, vero. Bisogna quindi spezzare il file in parti di una dimensione ottima. Probabilmente, per questo viene in auito la statistica o il calcolo delle probabilità. Basterebbe infatti capire in che percentuale le parti sarebbero uguali ... più è alta la percentuale più spezzoni comuni ho, meno occupano spazio. L'indice con il mapping: utente-file, in teoria, occupa poco ... (rispetto ai files intendo ...)

Sarebbe una sorta di database parallelo allo storage vero e proprio ...

[TheVice]

il best fit lo si ottiene creando un "dizionario" a lunghezza variabile in cui collocare i tokens (hash) dei files ... come fa l'algoritmo LZW usato nei file gif . La compressione si ottiene creando il dizionari e il dizionario lo si crea su elementi granularmete piccoli (1 byte) che man mano si accodano a quelli già presenti nel dizionario.
Tuttavia nello specifico una simile granularità non è ammissibile perchè potrebbe generare contenuti indice di dimensioni maggiori rispetto al file originale (l'hash è un codice poco "adattivo" e comunque lungo)

[etr]

Già, il sistema del dizionario non avrebbe molto senso in un contesto come questo ...

Ad esempio, MD5 produce un hash di 128 bits. A logica quindi non si dovrebbero creare spezzoni di file più piccoli di 128 bits. 128 bits sono 16 bytes ... secondo me in un "filesystem" medio esistono tantissimi spezzoni da 16 bytes uguali ... come dici tu vice, la cosa migliore sarebbe creare spezzoni variabili ... si potrebbe però partire con spezzoni fissi e poi in stile "fschk" verificare se nel filesystem per ogni utente ci sono n spezzoni consecutivi uguali; in quel caso si possono riunire i tre blocchi e nella parte di mapping mettere il nuovo hash. Vantaggio: si occupano (n-1)*128 bits in meno. Svantaggio: i nuovi files non potranno più beneficiare degli n spezzoni riunificati.

[GrG]

Mi viene in mente una cosa, però:

Risparmi HD, ma a processori e ram come sei messo?

[etr]

Ma in un sistema di storage CPU e RAM servono a poco ....

[GrG]

( Già, in uno normale, ma nel tuo quanto si devono sbattere? )

[etr]

eh vabbe ... si comprano per farli lavorare ...mica per restare in idle