4 ms·

I've moved to using backup tools using content-based ids with rolling window hashes, which allows deduplicating content even between different hosts—and crucial

by _flux 3y ago

I've moved to using backup tools using content-based ids with rolling window hashes, which allows deduplicating content even between different hosts—and crucially handles moving content from one host to another efficiently—even though in other scenarios I'm guessing rdiff-algorithm can produce smaller backups. The problem I have with duplicity and backups tools of its kind is that you still need to create a full backup again periodically, unless you want to have an ever-growing sequence of increments from the day you started doing backups. Content-addressed backups avoid that, because all snapshots are complete (even if the backup process itself is incremental), but their content blobs are shared and eventually garbage collected when no references exist to them. My tool of choice is kopia. Also borgbackup does similar things (though borgbackup is still unable to back up to the same repo from multiple hosts at the same time, though I haven't checked this for a while). Both do encryption, but its symmetric, so the client will have keys to opening the backups as well. If you require asymmetric encryption then these tools are not for you—though I guess this is not a technical requirement for this approach, so maybe one day a content-addressed backup tool with asymmetric encryption will appear?

mizzao 3y ago
Content-addressed backups sound something like how git stores data, is that the best way to think about them? And if so, what would be the main differences between just committing to a git repo for example?
- KMag 3y ago
  The "rolling window hashes" from the comment suggests sub-file matching at any offset. (See Bently-McIlroy diff algo/how rsync efficiently finds matches, for example.) I'm not aware that git performs this sort of deduplication. Better yet would be to use a rolling hash to decide where to cut the blocks, and then use a locality-aware hash (SimHash, etc.) to find similar blocks. Perform a topological sort to decide which blocks to store as diffs of others. Microsoft had some enterprise product that performed distribution somewhat like this, but also recursively using similarity hashes to see if the diffs were similar to existing files on the far machine.
  - jiggawatts 3y ago
    Microsoft's implementation is called Remote Differential Compression: https://learn.microsoft.com/en-us/previous-versions/windows/desktop/rdc/remote-differential-compression https://learn.microsoft.com/en-us/previous-versions/windows/... It's available as a built-in component of Windows, it's just a library with an API. Essentially the MS RDC protocol is just rsync run twice in a row, with the rsync metadata copied via rsync to compress it further.
    - KMag 3y ago
      > Essentially the MS RDC protocol is just rsync run twice in a row, with the rsync metadata copied via rsync to compress it further. There's an important difference is that RDC uses a locality-sensive hash algorithm (MinHash, IIRC) to find files likely to have matching sections, whereas rsync only considers the version of the same file sitting on the far host. rsync encodes differences on each file in isolation, whereas RDC looks at the entire corpus of files on the volume. For example, if you do the Windows equivalent of cat local/b.txt >> local/a.txt, rsync is going to miss the opportunity to encode local/a.txt -> remote/a.txt using matching runs from a common local/b.txt and remote/b.txt. However, RDC has the opportunity to notice that the local/a.txt -> remote/a.txt diff is very similar to remote/b.txt and further delta-encode the diff as a diff against remote/b.txt.
  - adrianmonk 3y ago
    Git does delta compression on packfiles, and if the same data occurs in different in different files, it actually can deduplicate it, even if it's not at the same offset. Here's a demo. First, create two test files. The files both contain the same two 1-megabyte chunks of random bytes, but in the opposite order: $ openssl rand 1000000 > a $ openssl rand 1000000 > b $ cat a b > ab $ cat b a > ba $ du -sh ab ba 2.0M ab 2.0M ba Commit them to Git and see that it requires 4 MB to store these two 2 MB files: $ git init Initialized empty Git repository in /tmp/x/.git/ $ git add ab ba $ git commit -m 'add two files' [master (root-commit) 7f75af0] add two files 2 files changed, 0 insertions(+), 0 deletions(-) create mode 100644 ab create mode 100644 ba $ du -sh .git 4.0M .git Run garbage collection, which creates a packfile. Note "delta 1" and note that disk usage dropped to a bit over the size of one of the files. $ git gc Enumerating objects: 4, done. Counting objects: 100% (4/4), done. Delta compression using up to 6 threads Compressing objects: 100% (4/4), done. Writing objects: 100% (4/4), done. Total 4 (delta 1), reused 0 (delta 0), pack-reused 0 $ du -sh .git 2.1M .git I'm not sure as if it's as sophisticated as some backup tools, though.
Linux-Fan 3y ago
> Content-addressed backups sound something like how git stores data, is that the best way to think about them? I think it is a valid way to consider them. Another option is to think of the backup as a special kind of file system snapshot that manifests itself as real files as opposed to data on a block device. > And if so, what would be the main differences between just committing to a git repo for example? The main difference is that good backup tools allow you to delete backups and free up the space whereas git is not really designed for this.
- nijave 3y ago
  Also git is not good with binary and sort of bolts on git-lfs as a workaround
EuAndreh 3y ago
> though borgbackup is still unable to back up to the same repo from multiple hosts at the same time Wouldn't that mean that, when using encrypted backups, secrets would have to be shared across multiple clients? If I'm understanding it correctly, it sounds like an anti-feature. Do other backup tools do that?
- _flux 3y ago
  Yes, it seems to be the case; only the data in the server is encrypted, while the key is shared between clients sharing the same repository. I'm not sure if content-addressed storage is feasible to implement otherwise. Maybe use the hash of the the unencrypted or shared-key-encrypted as the key, and then encrypt the per-block keys with keys of the clients who have the contents would do it. In any case, I'm not aware of such backup tools (I imagine most just don't encrypt anything).
  - formerly_proven 3y ago
    CAS-based backup tools leak metadata like a sieve, so they're generally not the best choice for the most paranoid people, which should probably stick to uncompressed tar archives (or zips, which avoid compressing unrelated files together, which leaks data) padded to full 100 megs or so and then encrypted en bloc.
AgentME 3y ago
Restic also works like this, and has the following benefits over Borg: multiple hosts can back up to the same repo, and it supports "dumb" remote file hosts that aren't running Borg like S3 or plain SFTP servers.
- radlad 3y ago
  I really like restic, and am personally happy to use it via the command line. It's very fast and efficient! However, I do wish there was better tooling / wrappers around it. I'd love to be able to set something simple up on my partner's Macbook. For example, Pika Backup, and Vorta are popular UIs for Borg of which no equivalent exists for Restic, while Borgmatic seems to be a de-facto standard for profile configuration. For my own purposes, I've been using a script I found on Github[0] for a while, but it only really supports Backblaze B2 AFAIK.[1] I've been meaning to try autorestic[2] and resticprofile[3] as they are potentially more flexible than the script I'm currently using but the fact that there are so many competing tools - many of which are no longer maintained - makes it difficult to choose a specific one. Prestic[4] looks intriguing for my partner's use, although it seems to have very few users. :\ A fork of Vorta[5] seems to have fizzled out six years ago. [0] https://github.com/erikw/restic-automatic-backup-scheduler https://github.com/erikw/restic-automatic-backup-scheduler [1] https://github.com/erikw/restic-automatic-backup-scheduler/issues/99#issuecomment-1216568162 https://github.com/erikw/restic-automatic-backup-scheduler/i... [2] https://github.com/cupcakearmy/autorestic https://github.com/cupcakearmy/autorestic [3] https://github.com/creativeprojects/resticprofile https://github.com/creativeprojects/resticprofile [4] https://github.com/ducalex/prestic https://github.com/ducalex/prestic [5] https://github.com/Mebus/restatic https://github.com/Mebus/restatic
  - e12e 3y ago
    > For example, Pika Backup, and Vorta are popular UIs for Borg of which no equivalent exists for Restic Have you considered?: https://github.com/netinvent/npbackup https://github.com/netinvent/npbackup Or (not FOSS, but restore-compatible): https://relicabackup.com/features https://relicabackup.com/features
nijave 3y ago
>borgbackup is still unable to back up to the same repo from multiple hosts at the same time, Basically still an issue. The machine takes an exclusive lock and it also adds override since each machine has to update it's local data cache (or whatever it's called) because they're constantly getting out of sync when another machine backs up bupstash looks promising as a close-to-but-more-performant borg alternative but it's still basically alpha quality It's unfortunate peer-to-peer Crashplan died
- nh2 3y ago
  What is alpha quality about bupstash? It has less features than Kopia, but what's there looks like high-quality to me. (I'm also using it to back up 150 TB (300 million files), on which all other dedup programs run out of memory.)
  - nijave 3y ago
    I guess the docs call it "beta" so maybe that's more accurate. Last I looked a couple months ago there's still a fair bit of corruption issues cropping up
totetsu 3y ago
Could this help dedupe 20 years of ad-hoc drive dumps from Changing systems…
rkagerer 3y ago
For those of us who prefer not to ship to the cloud, have you used Kopia Repository Server and is it any good? Does it run on Windows? The documentation refers to files and directories. Does the software let you take a consistent, point-in-time snapshot of a whole drive (or even multiple volumes), e.g. using something like VSS? Or if you want that have you got to use other software (like Macrium Reflect) to produce a file? Where does the client cache your encryption password/key? (or do you have to enter it each session)
- CrendKing 3y ago
  I wrote this part of the documentation: https://kopia.io/docs/advanced/actions/#windows-shadow-copy https://kopia.io/docs/advanced/actions/#windows-shadow-copy If you have problem using it, please let me know.
  - rkagerer 3y ago
    Neat, thanks!
- _flux 3y ago
  > For those of us who prefer not to ship to the cloud, have you used Kopia Repository Server and is it any good? Does it run on Windows? I haven't. I use local Ceph S3 for backups, and then use kopia to mirror that to one a local RAID just in case my Ceph dies ;-). It stores the password, base64-encoded, to ~/.config/kopia/repository.config.kopia-password. I suppose it would be nice, at least for workstations, if it supported keyrings—and it might, I haven't looked into it.
GTP 3y ago
> their content blobs are shared Doesn't this increase the chance of data loss? If a blob gets corrupted, then all the backups referencing that blob will have the same corrupted file(s). This is similar to having a corrupted index in an incremental backup chain (or maybe in this case you would lose everything?), but in the case of incremental backups the risk is mitigated by periodically performing full backups. Also my gut feeling is that you will save space with content-addressed backups only if you're backing up multiple machines that share files, but in the tipical average user scenario where one is backing up a single PC you get a similar space usage. Keep in mind that you tipically delete bacups older than a certain threshold. Could you maybe comment on my points?
- Matumio 3y ago
  Most backup tools allow you to verify a random subset, say 0.1% of the backup. If you do that together with every backup you would eventually notice.
- sliken 3y ago
  Sure you could have multiple level-0 backups to increase the odds of whatever blob you have corrupted can be found in other copies, but that's inefficient. It's much more efficient to deduplicate, then add redundancy. Like say storing said blobs on a RAIDz3. Or use backblaze's approach and split the blob into 17 pieces, add 3 pieces of redundancy, and distribute the chunks across 20 racks. If you are serious of course you'd have an onsite backup, deduplicated, with added redundancy AND the same offsite.

by _flux 3y ago

mizzao 3y ago

Content-addressed backups sound something like how git stores data, is that the best way to think about them? And if so, what would be the main differences between just committing to a git repo for example?

KMag 3y ago
The "rolling window hashes" from the comment suggests sub-file matching at any offset. (See Bently-McIlroy diff algo/how rsync efficiently finds matches, for example.) I'm not aware that git performs this sort of deduplication. Better yet would be to use a rolling hash to decide where to cut the blocks, and then use a locality-aware hash (SimHash, etc.) to find similar blocks. Perform a topological sort to decide which blocks to store as diffs of others. Microsoft had some enterprise product that performed distribution somewhat like this, but also recursively using similarity hashes to see if the diffs were similar to existing files on the far machine.
- jiggawatts 3y ago
  Microsoft's implementation is called Remote Differential Compression: https://learn.microsoft.com/en-us/previous-versions/windows/desktop/rdc/remote-differential-compression https://learn.microsoft.com/en-us/previous-versions/windows/... It's available as a built-in component of Windows, it's just a library with an API. Essentially the MS RDC protocol is just rsync run twice in a row, with the rsync metadata copied via rsync to compress it further.
  - KMag 3y ago
    > Essentially the MS RDC protocol is just rsync run twice in a row, with the rsync metadata copied via rsync to compress it further. There's an important difference is that RDC uses a locality-sensive hash algorithm (MinHash, IIRC) to find files likely to have matching sections, whereas rsync only considers the version of the same file sitting on the far host. rsync encodes differences on each file in isolation, whereas RDC looks at the entire corpus of files on the volume. For example, if you do the Windows equivalent of cat local/b.txt >> local/a.txt, rsync is going to miss the opportunity to encode local/a.txt -> remote/a.txt using matching runs from a common local/b.txt and remote/b.txt. However, RDC has the opportunity to notice that the local/a.txt -> remote/a.txt diff is very similar to remote/b.txt and further delta-encode the diff as a diff against remote/b.txt.
- adrianmonk 3y ago
  Git does delta compression on packfiles, and if the same data occurs in different in different files, it actually can deduplicate it, even if it's not at the same offset. Here's a demo. First, create two test files. The files both contain the same two 1-megabyte chunks of random bytes, but in the opposite order: $ openssl rand 1000000 > a $ openssl rand 1000000 > b $ cat a b > ab $ cat b a > ba $ du -sh ab ba 2.0M ab 2.0M ba Commit them to Git and see that it requires 4 MB to store these two 2 MB files: $ git init Initialized empty Git repository in /tmp/x/.git/ $ git add ab ba $ git commit -m 'add two files' [master (root-commit) 7f75af0] add two files 2 files changed, 0 insertions(+), 0 deletions(-) create mode 100644 ab create mode 100644 ba $ du -sh .git 4.0M .git Run garbage collection, which creates a packfile. Note "delta 1" and note that disk usage dropped to a bit over the size of one of the files. $ git gc Enumerating objects: 4, done. Counting objects: 100% (4/4), done. Delta compression using up to 6 threads Compressing objects: 100% (4/4), done. Writing objects: 100% (4/4), done. Total 4 (delta 1), reused 0 (delta 0), pack-reused 0 $ du -sh .git 2.1M .git I'm not sure as if it's as sophisticated as some backup tools, though.

Linux-Fan 3y ago

> Content-addressed backups sound something like how git stores data, is that the best way to think about them? I think it is a valid way to consider them. Another option is to think of the backup as a special kind of file system snapshot that manifests itself as real files as opposed to data on a block device. > And if so, what would be the main differences between just committing to a git repo for example? The main difference is that good backup tools allow you to delete backups and free up the space whereas git is not really designed for this.

nijave 3y ago
Also git is not good with binary and sort of bolts on git-lfs as a workaround

EuAndreh 3y ago

> though borgbackup is still unable to back up to the same repo from multiple hosts at the same time Wouldn't that mean that, when using encrypted backups, secrets would have to be shared across multiple clients? If I'm understanding it correctly, it sounds like an anti-feature. Do other backup tools do that?

_flux 3y ago
Yes, it seems to be the case; only the data in the server is encrypted, while the key is shared between clients sharing the same repository. I'm not sure if content-addressed storage is feasible to implement otherwise. Maybe use the hash of the the unencrypted or shared-key-encrypted as the key, and then encrypt the per-block keys with keys of the clients who have the contents would do it. In any case, I'm not aware of such backup tools (I imagine most just don't encrypt anything).
- formerly_proven 3y ago
  CAS-based backup tools leak metadata like a sieve, so they're generally not the best choice for the most paranoid people, which should probably stick to uncompressed tar archives (or zips, which avoid compressing unrelated files together, which leaks data) padded to full 100 megs or so and then encrypted en bloc.

AgentME 3y ago

Restic also works like this, and has the following benefits over Borg: multiple hosts can back up to the same repo, and it supports "dumb" remote file hosts that aren't running Borg like S3 or plain SFTP servers.

radlad 3y ago
I really like restic, and am personally happy to use it via the command line. It's very fast and efficient! However, I do wish there was better tooling / wrappers around it. I'd love to be able to set something simple up on my partner's Macbook. For example, Pika Backup, and Vorta are popular UIs for Borg of which no equivalent exists for Restic, while Borgmatic seems to be a de-facto standard for profile configuration. For my own purposes, I've been using a script I found on Github[0] for a while, but it only really supports Backblaze B2 AFAIK.[1] I've been meaning to try autorestic[2] and resticprofile[3] as they are potentially more flexible than the script I'm currently using but the fact that there are so many competing tools - many of which are no longer maintained - makes it difficult to choose a specific one. Prestic[4] looks intriguing for my partner's use, although it seems to have very few users. :\ A fork of Vorta[5] seems to have fizzled out six years ago. [0] https://github.com/erikw/restic-automatic-backup-scheduler https://github.com/erikw/restic-automatic-backup-scheduler [1] https://github.com/erikw/restic-automatic-backup-scheduler/issues/99#issuecomment-1216568162 https://github.com/erikw/restic-automatic-backup-scheduler/i... [2] https://github.com/cupcakearmy/autorestic https://github.com/cupcakearmy/autorestic [3] https://github.com/creativeprojects/resticprofile https://github.com/creativeprojects/resticprofile [4] https://github.com/ducalex/prestic https://github.com/ducalex/prestic [5] https://github.com/Mebus/restatic https://github.com/Mebus/restatic
- e12e 3y ago
  > For example, Pika Backup, and Vorta are popular UIs for Borg of which no equivalent exists for Restic Have you considered?: https://github.com/netinvent/npbackup https://github.com/netinvent/npbackup Or (not FOSS, but restore-compatible): https://relicabackup.com/features https://relicabackup.com/features

nijave 3y ago

>borgbackup is still unable to back up to the same repo from multiple hosts at the same time, Basically still an issue. The machine takes an exclusive lock and it also adds override since each machine has to update it's local data cache (or whatever it's called) because they're constantly getting out of sync when another machine backs up bupstash looks promising as a close-to-but-more-performant borg alternative but it's still basically alpha quality It's unfortunate peer-to-peer Crashplan died

nh2 3y ago
What is alpha quality about bupstash? It has less features than Kopia, but what's there looks like high-quality to me. (I'm also using it to back up 150 TB (300 million files), on which all other dedup programs run out of memory.)
- nijave 3y ago
  I guess the docs call it "beta" so maybe that's more accurate. Last I looked a couple months ago there's still a fair bit of corruption issues cropping up

totetsu 3y ago

Could this help dedupe 20 years of ad-hoc drive dumps from Changing systems…

rkagerer 3y ago

For those of us who prefer not to ship to the cloud, have you used Kopia Repository Server and is it any good? Does it run on Windows? The documentation refers to files and directories. Does the software let you take a consistent, point-in-time snapshot of a whole drive (or even multiple volumes), e.g. using something like VSS? Or if you want that have you got to use other software (like Macrium Reflect) to produce a file? Where does the client cache your encryption password/key? (or do you have to enter it each session)

CrendKing 3y ago
I wrote this part of the documentation: https://kopia.io/docs/advanced/actions/#windows-shadow-copy https://kopia.io/docs/advanced/actions/#windows-shadow-copy If you have problem using it, please let me know.
- rkagerer 3y ago
  Neat, thanks!
_flux 3y ago
> For those of us who prefer not to ship to the cloud, have you used Kopia Repository Server and is it any good? Does it run on Windows? I haven't. I use local Ceph S3 for backups, and then use kopia to mirror that to one a local RAID just in case my Ceph dies ;-). It stores the password, base64-encoded, to ~/.config/kopia/repository.config.kopia-password. I suppose it would be nice, at least for workstations, if it supported keyrings—and it might, I haven't looked into it.

GTP 3y ago

> their content blobs are shared Doesn't this increase the chance of data loss? If a blob gets corrupted, then all the backups referencing that blob will have the same corrupted file(s). This is similar to having a corrupted index in an incremental backup chain (or maybe in this case you would lose everything?), but in the case of incremental backups the risk is mitigated by periodically performing full backups. Also my gut feeling is that you will save space with content-addressed backups only if you're backing up multiple machines that share files, but in the tipical average user scenario where one is backing up a single PC you get a similar space usage. Keep in mind that you tipically delete bacups older than a certain threshold. Could you maybe comment on my points?

Matumio 3y ago
Most backup tools allow you to verify a random subset, say 0.1% of the backup. If you do that together with every backup you would eventually notice.
sliken 3y ago
Sure you could have multiple level-0 backups to increase the odds of whatever blob you have corrupted can be found in other copies, but that's inefficient. It's much more efficient to deduplicate, then add redundancy. Like say storing said blobs on a RAIDz3. Or use backblaze's approach and split the blob into 17 pieces, add 3 pieces of redundancy, and distribute the chunks across 20 racks. If you are serious of course you'd have an onsite backup, deduplicated, with added redundancy AND the same offsite.