-3

I knew that by using De-duplication procedure we can save storage costs.

1) I know what is de-duplication but I don't know how it works. Can someone clearly explain how de-duplication procedure works?

2) Can de-duplication be applied across all users? (does any Cloud Service Provider like Google, Azure, AWS and Dropbox etc., use this method i.e., de-dupe across users?)

closed as too broad by Philip Kendall, candied_orange, Andy, gnat, Doc Brown Oct 15 '17 at 12:07

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • I am sorry, it is not that clear to me. I am beginning to understand things so if someone explains in simple terms with an example it will be good. (Also I am not sure how true are those web sites. I trust answers in stack exchange will be true.) – Sridharan Oct 15 '17 at 4:01
  • I'm voting to close this question as off-topic because it's a question that only Dropbox can answer. – Philip Kendall Oct 15 '17 at 5:43
  • @PhilipKendall I have edited the question. I think now it looks more generic!! – Sridharan Oct 15 '17 at 6:13
  • 1
    You haven't clearly defined what you don't understand. Until you do this question is to broad. – candied_orange Oct 15 '17 at 6:55
2

As mentioned, only someone from Dropbox could clearly answer your questions in a 100% accurate way, but the overall concept is pretty easy to understand.

First of all: "data de-duplication" is basically just a different term for "compression".


1. How does it work?

Similar to how there are tons of different compression algorithms available, there are also different approaches to data de-duplication. The basic idea is always very similar: Detect identical data and only cross-reference it. This can happen on multiple levels and is really up to the individual algorithm used.

  • Let's assume each and every file has its own data/file system entry. This includes its name and a reference to some kind of content descriptor.
  • If a second file has identical content, it points to the same content descriptor. This makes 100% identical files not use any space other than meta data. This is what's described as "single instance storage" in the linked blog post.
  • Each of these content descriptors refers to multiple data chunks making up the file. If content is repeated (inside one file or in others), the system once again reuses these data chunks. This is the "sub-file de-duplication". In the above example these chunks are supposed to be 4 MB slices of the file, but that's just another implementation detail.

Still too complex? Let's use a simple example.

Let's assume we want to store three text files:

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.

As you can see, two files are identical and one is slightly different. All three files are 38 characters (or bytes) long. So classic storage would require us to store (or transmit) a total of 114 bytes + meta data.

Now let's split the files into chunks. For simplicity we're allocating chunks with a size of 10 bytes:

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.##]

Note that I've added the # to denote empty/unused space and keep the chunks of equal length. The next step is to give each chunk it's own unique ID. For practical reasons this could be just a hash of its contents; let's just ignore the possibility of hash collisions (it's mentioned in the blog post as well). The list containing this ID to data information is called a dictionary. Let's just use index numbers as identifiers.

one.txt

0 + 1 + 2 + 3

two.txt

0 + 1 + 2 + 4

three.txt

0 + 1 + 2 + 3

Dictionary

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

As you can see, this reduced the individual file size to basically 4 bytes each (we'd have to reserve more space for each entry with a bigger max. dictionary size of course). Our dictionary is 50 bytes long. So we now store all our data in 62 bytes (plus metadata for the names).

Now in a last step, we can use the single instance storage to also put file contents into its own dictionary (I'm using letters as identifiers here) to once again remove duplicates:

one.txt

A

two.txt

B

three.txt

A

File Dictionary

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

Chunk Dictionary

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

This allows us to compress our data even more, although the difference isn't that big, considering our individual files are rather small anyway:

  • 1 byte per file, 3 bytes total
  • 8 bytes for the file dictionary
  • 50 bytes for the data dictionary
  • 61 bytes for everything (compared to the initial 114 bytes)

2. Can it be applies cross-user?

We can't tell (in DropBox's case). In theory it should be possible, but it would mean that their backend can't encrypt data on individual keys, so stuff would be far less secure. Of course they could use some trick to still secure it etc. we can't know. The things mentioned in the privacy policy could also refer to sub folders being shared with other users, which would essentially mean all data is still belonging to a single customer, but not necessarily visible to all contributors. So someone only having access to /folder a/ could in theory use the same approach as the blog author to try to pinpoint what's in /folder b/ someone else is using.

  • Actually, the author of the blog post mentions that he tested with friends, and the "instant upload" happened across accounts, i.e. if a friend has uploaded a file, then putting the same file in your Dropbox folder will upload it "instantly", thus indicating the Dropbox does de-duplicate globally. Or at least did, when the article was written. In fact, someone designed a file sharing scheme using this global de-duplication, but Dropbox asked him to take it down, because they feared a negative association of Dropbox with copyright violations. – Jörg W Mittag Oct 15 '17 at 17:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.