Procedura di deduplicazione [chiusa]

Come accennato, solo qualcuno di Dropbox potrebbe rispondere alle tue domande in modo accurato al 100%, ma il concetto generale è abbastanza facile da capire.

Prima di tutto: "la deduplicazione dei dati" è fondamentalmente solo un termine diverso per "compressione".

1. Come funziona?

Analogamente a quanto ci sono tonnellate di diversi algoritmi di compressione disponibili, esistono anche diversi approcci alla deduplicazione dei dati. L'idea di base è sempre molto simile: rileva i dati identici e fai solo un riferimento incrociato. Questo può accadere su più livelli ed è davvero all'altezza del singolo algoritmo utilizzato.

• Supponiamo che ogni file abbia la propria voce di dati / file system. Questo include il suo nome e un riferimento a qualche tipo di descrittore di contenuto.
• Se un secondo file ha un contenuto identico, punta allo stesso descrittore di contenuto. Ciò rende il 100% di file identici che non utilizzano nessuno spazio diverso dai metadati. Questo è ciò che viene descritto come "archiviazione a istanza singola" nel post del blog collegato.
• Ciascuno di questi descrittori di contenuto fa riferimento a più blocchi di dati che costituiscono il file. Se il contenuto viene ripetuto (all'interno di un file o in altri), il sistema riutilizza nuovamente questi blocchi di dati. Questa è la "deduplicazione dei file secondari". Nell'esempio precedente questi blocchi dovrebbero essere di 4 MB di sezioni del file, ma questo è solo un altro dettaglio di implementazione.

Ancora troppo complesso? Usiamo un semplice esempio.

Supponiamo di voler memorizzare tre file di testo:

one.txt

Hello World. This is some simple text.

two.txt

Hello World. This is some simple test.

three.txt

Hello World. This is some simple text.

Come puoi vedere, due file sono identici e uno è leggermente diverso. Tutti e tre i file sono lunghi 38 caratteri (o byte). Pertanto, l'archiviazione classica richiederebbe l'archiviazione (o la trasmissione) di un totale di 114 byte + metadati.

Ora dividiamo i file in blocchi. Per semplicità stiamo allocando chunk con una dimensione di 10 byte:

one.txt

[Hello Worl][d. This is][ some simp][le text.##]

two.txt

[Hello Worl][d. This is][ some simp][le test.##]

three.txt

[Hello Worl][d. This is][ some simp][le text.##]

Tieni presente che ho aggiunto # per indicare lo spazio vuoto / non utilizzato e mantenere i blocchi di uguale lunghezza. Il prossimo passo è dare a ogni pezzo un proprio ID univoco. Per motivi pratici questo potrebbe essere solo un hash dei suoi contenuti; ignoriamo la possibilità di collisioni hash (è menzionata anche nel post del blog). L'elenco che contiene questo ID per le informazioni sui dati è chiamato un dizionario. Usiamo solo i numeri di indice come identificatori.

one.txt

0 + 1 + 2 + 3

two.txt

0 + 1 + 2 + 4

three.txt

0 + 1 + 2 + 3

dizionario

0: [Hello Worl]
1: [d. This is]
2: [ some simp]
3: [le text.##]
4: [le test.##]

Come puoi vedere, questo ha ridotto le singole dimensioni del file a sostanzialmente 4 byte ciascuna (dovremmo riservare più spazio per ogni voce con una dimensione del dizionario massima più grande, ovviamente). Il nostro dizionario è lungo 50 byte. Quindi ora archiviamo tutti i nostri dati in 62 byte (più i metadati per i nomi).

Ora, in un ultimo passaggio, possiamo usare la memoria di una singola istanza per mettere anche il contenuto del file nel suo dizionario (sto usando le lettere come identificatori qui) per rimuovere nuovamente i duplicati:

one.txt

A

two.txt

B

three.txt

A

Dizionario file

A: 0 + 1 + 2 + 3
B: 0 + 1 + 2 + 4

Dizionario di blocchi

0: [Hello Worl]
1: [d. This is]
2: [ some simp]
3: [le text.##]
4: [le test.##]

Questo ci consente di comprimere i nostri dati ancora di più, anche se la differenza non è così grande, considerando comunque che i nostri singoli file sono piuttosto piccoli:

• 1 byte per file, 3 byte totali
• 8 byte per il dizionario di file
• 50 byte per il dizionario dati
• 61 byte per tutto (rispetto ai 114 byte iniziali)

2. Può essere applicato come utente incrociato?

Non possiamo dire (nel caso DropBox). In teoria dovrebbe essere possibile, ma significherebbe che il loro back-end non può crittografare i dati su singole chiavi, quindi la roba sarebbe molto meno sicura. Ovviamente potrebbero usare qualche trucco per proteggerlo ancora, ecc. Non possiamo saperlo. Le cose menzionate nella politica sulla privacy potrebbero anche riferirsi a sottocartelle condivise con altri utenti, il che significherebbe essenzialmente che tutti i dati appartengono ancora a un singolo cliente, ma non necessariamente visibili a tutti i contributori. Quindi qualcuno che ha accesso solo a /folder a/ potrebbe in teoria utilizzare lo stesso approccio dell'autore del blog per cercare di individuare cosa c'è in /folder b/ che qualcun altro sta usando.