Whitepaper questions

[gronostajo]

I'm interested in how Duplicati stores backups, so I'm reading the whitepaper and I have some questions that you could hopefully answer.

Q1.

However, there are two complications relating to this setup. One problem is that the list of hashes can become very large. For a setup with a block size of 100KiB using an SHA­256 hash, a 1TiB file will fill up more than 300MiB hash data, which would need to be stored in the filelist. That was the reason, to store the hash lists as binary blobs. As each SHA­256 hash is 32 bytes, a list of hashes is simply the 32 bytes written, then the next 32 bytes, etc. The hash lists are stored as blocks in the same way that the actual data is stored. This reduces the size of the hash list with a factor of blocksize / hashsize, or for the same 1TiB, the hash list in the filelist becomes around 100KiB. This introduces a level of indirection, but does not add further file or data types. If a single byte is changed in the 1 TiB file, the block itself needs to be updated, as well as the binary blob that contains the block’s hash, resulting in two blocks being updated.

I think I understand where the 300 MiB number comes from:

1 TiB / 100 KiB/hash = 10,737,418.2 hashes
10,737,418.2 hashes * 32 bytes/hash = 327.68 MiB of hashes

This calculation assumes hashes are stored in binary, so this number can't be optimized any further, right? Do I understand correctly that the 100 KiB number mentioned in the paper is just total size of hashes of binary hash lists? That would be 3,200 hash list hashes, ~3,355 hashes in each list (100 KiB/hash * 3,355 hashes/file = 335,5 KiB/file), and that 328 MiB of hash lists must still be stored in blocks, it just doesn't make filelists huge.

Q2.

The other complication is, that over time, the volumes that contain the blocks will start to contain unused data.

I think what's implied here is that deleting backups can drop reference counts of some blocks to 0, thus making volumes that contain them wasteful. But then I can't figure out this part:

It is possible to do some strategic compacting that will exploit the fact that old blocks are less likely to become obsolete than new blocks.

Intuitively I'd say that old blocks are more likely to become obsolete, as old backups are more likely to be deleted than recent ones. That's also the assumption you seem to be making earlier:

When a backup grows over time, users usually want to delete the oldest backups first which is not possible with the chain of dependant patches.

Am I missing something here?

Q3.

Is filelist a nested structure, or a flat one like git's trees? In other words, does a single filelist represent entire root of a backup source, or does it only enumerate direct children of a directory, in particular including other filelists for child directories? If it's the latter, are filelists grouped into volumes too?

Q4.

The whitepaper doesn't state clearly at which level the encryption takes place. I guess volumes are encrypted as a whole? What about filelists? As a malicious actor how much knowledge could I gain by looking at encrypted backups?

Q5.

Are you applying any kind of compression to uploaded files?

---

By the way, your idea looks pretty solid. Unfortunately my first attempt at using Duplicati failed, but I may give it another try.

[Pectojin]

Q1:
The implication here isn't that we do not store 300MiB of hashes. It's just that we moved the 300MiB into a block file instead. Then we can reference that block instead of listing all the block hashes in the filelist.

Q2:
There is an important distinction here between backups and blocks. Old blocks may have been created for an old backup, but if they're used by a new backup then it doesn't matter that the old backup gets deleted, because the block will still have references.

So blocks that are already weeks or months old are likely to stem from files that do not change. Meanwhile every backup is likely to have blocks from files that will change before the next backup.

Q3:
Filelists are self contained. They only reference block data and you can delete any filelist without worrying about the others. This obviously assumes that the local database knows that filelist is deleted, else Duplicati will assume there has been backend data corruption.

Q4:
All encryption happens at the volume level. So all files on the storage backend are just compressed encrypted files. The only information provided to an attacker is which encrypted file is a fileset and which is a block.

Q5:
Yes, all volumes are compressed right before encryption happens on the volume level.

[gronostajo]

Thanks for the response!

Q2:

There is an important distinction here between backups and blocks. Old blocks may have been created for an old backup, but if they're used by a new backup then it doesn't matter that the old backup gets deleted, because the block will still have references.

This doesn't clear things up for me. My question is why would new blocks be more likely to become obsolete? Blocks that are referenced more than once don't affect this at all because they don't become obsolete. If such a block is used in both old and new backup, then deleting any of them won't free up the block. So I think if old backups are more likely to be deleted, then old blocks should be statistically more likely to be deleted too, because there's no reason for a block to become obsolete other than backup deletion.