Use of fallocate in restore to prevent extreme fragmentation of (large) files

[mschmc]

Output of restic version

restic 0.9.6 (v0.9.6-148-gc03bc88b) compiled with go1.13.5 on linux/amd64
(Beta-Version needed because of problem to restore 'large files' in release-version.

What should restic do differently? Which functionality do you think we should add?

fallocate a file before restoring it's contents. At least optionally

What are you trying to do?

Get files with the least possible fragmentation and contiguously allocated space.

AFAIU: The current version creates the file as sparse and then restores the content "chunk by chunk" in essentially random order.
The resulting file is thus a) extremely fragmented and b) discontiguous.

For e.g.:
Yesterday i restored a 1.4TB VM-Image-File (Ploop with Ext4 inside).
Just mounting that restored-file needed 7 Minutes.
Then i rewrote said file: rsync -avP --preallocate restored-file new-file
Mounting that rewritten file now only takes 4 seconds as layout of the rewritten is "optimal".

[greatroar]

The restorer code has already been rewritten since 0.9.6 (#2195). You should recheck whether the file gets so fragmented.

[mschmc]

I had to use a recent daily-build (see description) for the restore, which contains said updated restore code AFAIU.

AFAIU2, the updated restore code is the actual cause of the fragmentation problem.
(But this is the first & only time i have restored a large file with restic. So i don't know if the previous code has a similar "problem".)

[greatroar]

Excuse me, I had misread the version number.

I am afraid that using fallocate would conflict with writing sparse files (files with holes), as in #2601, so one of them would need an option to turn it on/off.

[BuGlessRB]

What if restic would primarily try to append to existing files first, instead of doing random writes?

[ifedorenko]

What if restic would primarily try to append to existing files first, instead of doing random writes?

Single-threaded append-only restore is very slow (see #1719). Multi-threaded append-only restore needs significant amount of memory to work efficiently and overall is pretty complex (#2195). And files will probably still be fragmented after multi-threaded restore (and single-threaded too, if other processes write to the filesystem during restore).

Personally, I am in favour of using fallocate during restore (and I will comment in #2601 why I think guessing sparse files is not ideal).

[MichaelEischer]

It could also be possible to reduce the fragmentation a lot by processing the pack files in the order in which they are first referenced by a file in the backup. The current iteration order over the pack files is completely random, whereas processing the pack files in appearance order, quite likely, closely resembles consecutive file accesses.

[greatroar]

Allocating up front is a more localized change to the code, though.

[MichaelEischer]

I've taken a closer look at this, using a test file with just 2GB size. That file consisted of 1GB data read from /dev/urandom and is contained twice in the file. With the current master branch I ended up with approx. 200 file fragments after restoring according to filefrag on ext4 (Ubuntu 20.04).

Accessing the pack files in order of first appearance (just remember the order in which the filerestorer encounters a new pack file

restic/internal/restorer/filerestorer.go

Line 125 in 0fed6a8

packs[packID] = pack

, which amounts to a 4 line change) reduces the number of fragments to something a bit below 10 fragments. As the test file is setup to have each blob written to two locations in the restored file, this also serves as a simple stress test for files with blobs which are stored out of order in packs.

With fallocate the number of fragments is down at around 2-3, which is fine as each one is now probably several hundred MB large.

I'm currently working on a PR which includes both changes. As fallocate or a similar command is not available on every platform is probably a good idea to have a fallback to reduce the fragmentation even without such a command. (It would of course be possible, to start with (sequentially) zeroing the files before but that creates a lot of overhead)