Do two passes instead of just sequentially writing all chunks to the standard output. On the first pass, all "chunk emit" instructions are remembered together with their output positions indexed by bundle id, and all "byte emit" instructions are executed using seeks. On the second pass, all remembered "chunk emit" instructions are executed in the bundle order. This makes zbackup decompress every used bundle only ONCE instead of doing it (basically the same work) many times while reading different chunks. This allows for bigger bundle sizes (I use 32M), which reduces the number of files in the repository and makes it more cloud-storage-sync friendly, and further improves the compression ratio.
|7 years ago|
|cmake||8 years ago|
|licenses||8 years ago|
|tartool||8 years ago|
|tests||8 years ago|
|.gitignore||7 years ago|
|.travis.yml||7 years ago|
|CMakeLists.txt||8 years ago|
|CONTRIBUTORS||7 years ago|
|README.md||7 years ago|
|adler32.hh||8 years ago|
|appendallocator.cc||8 years ago|
|appendallocator.hh||8 years ago|
|backup_collector.cc||7 years ago|
|backup_collector.hh||7 years ago|
|backup_creator.cc||8 years ago|
|backup_creator.hh||8 years ago|
|backup_exchanger.cc||8 years ago|
|backup_exchanger.hh||7 years ago|
|backup_file.cc||8 years ago|
|backup_file.hh||8 years ago|
|backup_restorer.cc||7 years ago|
|backup_restorer.hh||7 years ago|
|bundle.cc||7 years ago|
|bundle.hh||7 years ago|
|check.hh||8 years ago|
|chunk_id.cc||8 years ago|
|chunk_id.hh||8 years ago|
|chunk_index.cc||7 years ago|
|chunk_index.hh||7 years ago|
|chunk_storage.cc||7 years ago|
|chunk_storage.hh||7 years ago|
|compression.cc||7 years ago|
|compression.hh||8 years ago|
|config.cc||7 years ago|
|config.hh||7 years ago|
|debug.cc||8 years ago|
|debug.hh||8 years ago|
|dir.cc||8 years ago|
|dir.hh||8 years ago|
|encrypted_file.cc||8 years ago|
|encrypted_file.hh||8 years ago|
|encryption.cc||8 years ago|
|encryption.hh||8 years ago|
|encryption_key.cc||8 years ago|
|encryption_key.hh||8 years ago|
|endian.hh||7 years ago|
|ex.hh||8 years ago|
|file.cc||7 years ago|
|file.hh||7 years ago|
|hex.cc||8 years ago|
|hex.hh||8 years ago|
|index_file.cc||8 years ago|
|index_file.hh||8 years ago|
|message.cc||8 years ago|
|message.hh||8 years ago|
|mt.cc||8 years ago|
|mt.hh||8 years ago|
|nocopy.hh||8 years ago|
|objectcache.cc||8 years ago|
|objectcache.hh||8 years ago|
|page_size.cc||8 years ago|
|page_size.hh||8 years ago|
|random.cc||8 years ago|
|random.hh||8 years ago|
|rolling_hash.cc||8 years ago|
|rolling_hash.hh||8 years ago|
|sha256.cc||8 years ago|
|sha256.hh||8 years ago|
|sptr.hh||8 years ago|
|static_assert.hh||8 years ago|
|storage_info_file.cc||8 years ago|
|storage_info_file.hh||8 years ago|
|tmp_mgr.cc||7 years ago|
|tmp_mgr.hh||8 years ago|
|unbuffered_file.cc||7 years ago|
|unbuffered_file.hh||7 years ago|
|utils.hh||8 years ago|
|version.cc||8 years ago|
|version.hh||8 years ago|
|zbackup.cc||7 years ago|
|zbackup.proto||8 years ago|
|zbackup_base.cc||7 years ago|
|zbackup_base.hh||7 years ago|
|zutils.cc||7 years ago|
|zutils.hh||7 years ago|
zbackup is a globally-deduplicating backup tool, based on the ideas found in rsync. Feed a large
.tar into it, and it will store duplicate regions of it only once, then compress and optionally encrypt the result. Feed another
.tar file, and it will also re-use any data found in any previous backups. This way only new changes are stored, and as long as the files are not very different, the amount of storage required is very low. Any of the backup files stored previously can be read back in full at any time. The program is format-agnostic, so you can feed virtually any files to it (any types of archives, proprietary formats, even raw disk images -- but see Caveats).
This is achieved by sliding a window with a rolling hash over the input at a byte granularity and checking whether the block in focus was ever met already. If a rolling hash matches, an additional full cryptographic hash is calculated to ensure the block is indeed the same. The deduplication happens then.
The program has the following features:
- Parallel LZMA or LZO compression of the stored data
- Built-in AES encryption of the stored data
- Possibility to delete old backup data
- Use of a 64-bit rolling hash, keeping the amount of soft collisions to zero
- Repository consists of immutable files. No existing files are ever modified
- Written in C++ only with only modest library dependencies
- Safe to use in production (see below)
- Possibility to exchange data between repos without recompression
cmake>= 2.8.2 (though it should not be too hard to compile the sources by hand if needed)
libssl-devfor all encryption, hashing and random numbers
protobuf-compilerfor data serialization
liblzo2-devfor compression (optional)
zlib1g-devfor adler32 calculation
To build and install:
cd zbackup cmake . make sudo make install # or just run as ./zbackup
zbackup init --non-encrypted /my/backup/repo tar c /my/precious/data | zbackup backup /my/backup/repo/backups/backup-`date '+%Y-%m-%d'` zbackup restore /my/backup/repo/backups/backup-`date '+%Y-%m-%d'` > /my/precious/backup-restored.tar
If you have a lot of RAM to spare, you can use it to speed-up the restore process -- to use 512 MB more, pass
--cache-size 512mb when restoring.
If encryption is wanted, create a file with your password:
# more secure to use an editor echo mypassword > ~/.my_backup_password chmod 600 ~/.my_backup_password
Then init the repo the following way:
zbackup init --password-file ~/.my_backup_password /my/backup/repo
And always pass the same argument afterwards:
tar c /my/precious/data | zbackup --password-file ~/.my_backup_password backup /my/backup/repo/backups/backup-`date '+%Y-%m-%d'` zbackup --password-file ~/.my_backup_password restore /my/backup/repo/backups/backup-`date '+%Y-%m-%d'` > /my/precious/backup-restored.tar
If you have a 32-bit system and a lot of cores, consider lowering the number of compression threads by passing
--threads 4 or
--threads 2 if the program runs out of address space when backing up (see why below, item 2). There should be no problem on a 64-bit system.
- While you can pipe any data into the program, the data should be uncompressed and unencrypted -- otherwise no deduplication could be performed on it.
zbackupwould compress and encrypt the data itself, so there's no need to do that yourself. So just run
tar cand pipe it into
zbackupdirectly. If backing up disk images employing encryption, pipe the unencrypted version (the one you normally mount). If you create
.rarfiles, use no compression (
-m0) and no encryption.
- Parallel LZMA compression uses a lot of RAM (several hundreds of megabytes, depending on the number of threads used), and ten times more virtual address space. The latter is only relevant on 32-bit architectures where it's limited to 2 or 3 GB. If you hit the ceiling, lower the number of threads with
- Since the data is deduplicated, there's naturally no redundancy in it. A loss of a single file can lead to a loss of virtually all data. Make sure you store it on a redundant storage (RAID1, a cloud provider etc).
- The encryption key, if used, is stored in the
infofile in the root of the repo. It is encrypted with your password. Technically thus you can change your password without re-encrypting any data, and as long as no one possesses the old
infofile and knows your old password, you would be safe (note that ability to change repo type between encrypted and non-encrypted is not implemented yet -- someone who needs this is welcome to create a pull request -- the possibility is all there). Also note that it is crucial you don't lose your
infofile, as otherwise the whole backup would be lost.
- Right now the only modes supported are reading from standard input and writing to standard output. FUSE mounts and NBD servers may be added later if someone contributes the code.
- The program keeps all known blocks in an in-RAM hash table, which may create scalability problems for very large repos (see below).
- The only encryption mode currently implemented is
PKCS#7padding. If you believe that this is not secure enough, patches are welcome. Before you jump to conclusions however, read this article.
- It's only possible to fully restore the backup in order to get to a required file, without any option to quickly pick it out.
tarwould not allow to do it anyway, but e.g. for
zipfiles it could have been possible. This is possible to implement though, e.g. by exposing the data over a FUSE filesystem.
Most of those limitations can be lifted by implementing the respective features.
Is it safe to use
zbackup for production data? Being free software, the program comes with no warranty of any kind. That said, it's perfectly safe for production, and here's why. When performing a backup, the program never modifies or deletes any existing files -- only new ones are created. It specifically checks for that, and the code paths involved are short and easy to inspect. Furthermore, each backup is protected by its
SHA256 sum, which is calculated before piping the data into the deduplication logic. The code path doing that is also short and easy to inspect. When a backup is being restored, its
SHA256 is calculated again and compared against the stored one. The program would fail on a mismatch. Therefore, to ensure safety it is enough to restore each backup to
/dev/null immediately after creating it. If it restores fine, it will restore fine ever after.
To add some statistics, the author of the program has been using an older version of
zbackup internally for over a year. The
SHA256 check never ever failed. Again, even if it does, you would know immediately, so no work would be lost. Therefore you are welcome to try the program in production, and if you like it, stick with it.
The repository has the following directory structure:
/repo backups/ bundles/ 00/ 01/ 02/ ... index/ info
backupsdirectory contain your backups. Those are very small files which are needed for restoration. They are encrypted if encryption is enabled. The names can be arbitrary. It is possible to arrange files in subdirectories, too. Free renaming is also allowed.
bundlesdirectory contains the bulk of data. Each bundle internally contains multiple small chunks, compressed together and encrypted. Together all those chunks account for all deduplicated data stored.
indexdirectory contains the full index of all chunks in the repository, together with their bundle names. A separate index file is created for each backup session. Technically those files are redundant, all information is contained in the bundles themselves. However, having a separate
indexis nice for two reasons: 1) it's faster to read as it incurs less seeks, and 2) it allows making backups while storing bundles elsewhere. Bundles are only needed when restoring -- otherwise it's sufficient to only have
index. One could then move all newly created bundles into another machine after each backup.
infois a very important file which contains all global repository metadata, such as chunk and bundle sizes, and an encryption key encrypted with the user password. It is paramount not to lose it, so backing it up separately somewhere might be a good idea. On the other hand, if you absolutely don't trust your remote storage provider, you might consider not storing it with the rest of the data. It would then be impossible to decrypt it at all, even if your password gets known later.
The program does not have any facilities for sending your backup over the network. You can
rsync the repo to another computer or use any kind of cloud storage capable of storing files. Since
zbackup never modifies any existing files, the latter is especially easy -- just tell the upload tool you use not to upload any files which already exist on the remote side (e.g. with
gsutil cp -R -n /my/backup gs:/mybackup/).
To aid with creating backups, there's an utility called
tartool included with
zbackup. The idea is the following: one sprinkles empty files called
.no-backup across the entire filesystem. Directories where
.backup files are placed are marked for backing up. Similarly, directories with
.no-backup files are marked not to be backed up. Additionally, it is possible to place
.backup-XYZ in the same directory where
XYZ is to mark
XYZ for backing up, or place
.no-backup-XYZ to mark it not to be backed up. Then
tartool can be run with three arguments -- the root directory to start from (can be
/), the output
includes file, and the output
excludes file. The tool traverses over the given directory noting the
.no-backup* files and creating include and exclude lists for the
tar utility. The
tar utility could then be run as
tar c --files-from includes --exclude-from excludes to store all chosen data.
This section tries do address the question on the maximum amount of data which can be held in a backup repository. What is meant here is the deduplicated data. The number of bytes in all source files ever fed into the repository doesn't matter, but the total size of the resulting repository does.
Internally all input data is split into small blocks called chunks (up to
64k each by default). Chunks are collected into bundles (up to
2MB each by default), and those bundles are then compressed and encrypted.
There are then two problems with the total number of chunks in the repository:
- Hashes of all existing chunks are needed to be kept in RAM while the backup is ongoing. Since the sliding window performs checking with a single-byte granularity, lookups would otherwise be too slow. The amount of data needed to be stored is technically only 24 bytes for each chunk, where the size of the chunk is up to
64k. In an example real-life
18MBare taken by in its hash index. Multiply this roughly by two to have an estimate of RAM needed to store this index as an in-RAM hash table. However, as this size is proportional to the total size of the repo, for
2TBrepo you could already require
2GBof RAM. Most repos are much smaller though, and as long as the deduplication works properly, in many cases you can store terabytes of highly-redundant backup files in a
- We use a 64-bit rolling hash, which allows to have an
O(1)lookup cost at each byte we process. Due to birthday paradox, we would start having collisions when we approach
2^32hashes. If each chunk we have is
32kon average, we would get there when our repo grows to
128TB. We would still be able to continue, but as the number of collisions would grow, we would have to resort to calculating the full hash of a block at each byte more and more often, which would result in a considerable slowdown.
All in all, as long as the amount of RAM permits, one can go up to several terabytes in deduplicated data, and start having some slowdown after having hundreds of terabytes, RAM-permitting.
- We use a 64-bit modified Rabin-Karp rolling hash (see
rolling_hash.hhfor details), while most other programs use a 32-bit one. As noted previously, one problem with the hash size is its birthday bound, which with the 32-bit hash is met after having only
2^16hashes. The choice of a 64-bit hash allows us to scale much better while having virtually the same calculation cost on a typical 64-bit machine.
MD5as its strong hash. While
MD5is known to be fast, it is also known to be broken, allowing a malicious user to craft colliding inputs.
SHA1instead. The cost of
SHA1calculations on modern machines is actually less than that of
openssl speed md5 sha1on yours), so it's a win-win situation. We only keep the first 128 bits of the
SHA1output, and therefore together with the rolling hash we have a 192-bit hash for each chunk. It's a multiple of 8 bytes which is a nice properly on 64-bit machines, and it is long enough not to worry about possible collisions.
PKCS#7padding is used for encryption. This seems to be a reasonbly safe classic solution. Each encrypted file has a random IV as its first 16 bytes.
- We use Google's protocol buffers to represent data structures in binary form. They are very efficient and relatively simple to use.
zbackup uses LZMA to compress stored data. It compresses very well, but it will slow down your backup
(unless you have a very fast CPU).
LZO is much faster, but the files will be bigger. If you don't want your backup process to be cpu-bound, you should consider using LZO. However, there are some caveats:
- LZO is so fast that other parts of
zbackupconsume significant portions of the CPU. In fact, it is only using one core on my machine because compression is the only thing that can run in parallel.
- I've hacked the LZO support in a day. You shouldn't trust it. Please make sure that restore works before you assume that your data is safe. That may still be faster than a backup with LZMA ;-)
- LZMA is still the default, so make sure that you use the
-o bundle.compression_method=lzoargument when you init the repo or whenever you do a backup.
You can mix LZMA and LZO in a repository. Each bundle file has a field that says how it was compressed, so
zbackup will use the right method to decompress it. You could use an old
zbackup respository with only LZMA
bundles and start using LZO. However, please think twice before you do that because old versions of
won't be able to read those bundles.
There's a lot to be improved in the program. It was released with the minimum amount of functionality to be useful. It is also stable. This should hopefully stimulate people to join the development and add all those other fancy features. Here's a list of ideas:
- Ability to change bundle type (between encrypted and non-encrypted).
- Improved garbage collection. The program should support ability to specify maximum index file size / maximum index file count (for better compatibility with cloud storages as well) or something like retention policy.
- A command to fsck the repo by doing something close to what garbage collection does, but also checking all hashes and so on.
- Parallel decompression. Right now decompression is single-threaded, but it is possible to look ahead in the stream and perform prefetching.
- Support for mounting the repo over FUSE. Random access to data would then be possible.
- Support for exposing a backed up file over a userspace NBD server. It would then be possible to mount raw disk images without extracting them.
- Support for other encryption types (preferably for everything
opensslsupports with its
- Support for other compression methods.
- You name it!
- The program's website is at http://zbackup.org/.
- Development happens at https://github.com/zbackup/zbackup.
- Discussion forum is at https://groups.google.com/forum/#!forum/zbackup. Please ask for help there!
The author is reachable over email at firstname.lastname@example.org. Please be constructive and don't ask for help using the program, though. In most cases it's best to stick to the forum, unless you have something to discuss with the author in private.
zbackup is certainly not the first project to embrace the idea of using a rolling hash for deduplication. Here's a list of other projects the author found on the web:
- bup, based on storing data in
gitpacks. No possibility of removing old data. This program was the initial inspiration for
- ddar, seems to be a little bit outdated. Contains a nice list of alternatives with comparisons.
- rdiff-backup, based on the original
rsyncalgorithm. Does not do global deduplication, only working over the files with the same file name.
- duplicity, which looks similar to
rdiff-backupwith regards to mode of operation.
- Some filesystems (most notably ZFS and Btrfs) provide deduplication features. They do so only at block level though, without a sliding window, so they can not accomodate to arbitrary byte insertion/deletion in the middle of data.
- Attic, which looks very similar to
Copyright (c) 2012-2014 Konstantin Isakov (email@example.com) and ZBackup contributors, see CONTRIBUTORS. Licensed under GNU GPLv2 or later + OpenSSL, see LICENSE.
This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.