Proposal to fix long filenames

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Proposal to fix long filenames

Ben Escoto
Time to fix rdiff-backup's oldest bug?  In this message I'll describe
the problem and one way to fix it.

The problem:

rdiff-backup has a problem with long filenames.  For instance,
rdiff-backup may not be able to backup a file whose name has 250
characters in it, when the maximum allowable filename is 255
characters.

There are three different ways I can see this happening:

1)  A source file's length is close to the maximum and additional
    suffix pushes it over the limit.  For instance, <long filename>
    has a length of 250.  The mirror file is created successfully, but
    increments can be, for instance, <long
    filename>.2005-11-11T23:59:49-06:00.snapshot.gz which is 288
    filename>characters long.

        I think this is the most common case.

2)  A source file's length is close to the maximum, and quoting takes
    it over the edge.  In this case, both the mirror and the increment
    files are too long to write.

3)  The source filesystem supports longer filenames than the
    destination.  In this case the mirror file may be too long to
    write even without any quoting.  I've never heard of this actually
    happening.


One way to fix it:

The mirror_metadata file could have two additional optional fields,
called "MirrorFilename" and "IncrementFilename".  If MirrorFilename is
set, rdiff-backup reads the mirror file from the
rdiff-backup-data/long_filename_data/<mirror filename> file, instead
of from the normal location in the mirror directory.

Similarly, if IncrementFilename is set, increment data will not be
read from rdiff-backup-data/increments/<whatever>.<suffix> but from
rdiff-backup-data/long_filename_data/<increment filename>.<suffix>

The alternate filenames would have boring but plentiful names like
1, 2, etc.

When backing up, rdiff-backup could examine the length of each file
before it writes it to the repository, and figure out if the mirror
and increments would be too long, and write the data in the
appropriate location, setting those optional fields if necessary.


Drawback:

Originally I thought that the fix for long filenames might somehow be
integrated into a scheme to detect and compress renamed files.  But
now I doubt any renaming scheme is forthcoming.


So, any comments?  Anyone see any other drawbacks/problems?


--
Ben Escoto

_______________________________________________
rdiff-backup-users mailing list at [hidden email]
http://lists.nongnu.org/mailman/listinfo/rdiff-backup-users
Wiki URL: http://rdiff-backup.solutionsfirst.com.au/index.php/RdiffBackupWiki

attachment0 (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Proposal to fix long filenames

Sheldon Hearn
On Saturday 12 November 2005 08:22, Ben Escoto wrote:
> So, any comments?  Anyone see any other drawbacks/problems?

I think this is another edge case that speaks to the value of entirely
virtualizing the backup store.  In other words, don't rely AT ALL on
the capabilities of the filesystem used to store backups, except for
those capabilities common to all documented as being supported for
rdiff-backup servers.  In real terms, this leaves you with pretty short
names and just about nothing else.

Instead, use the backup store's filesystem only to store the data
associated with backed up objects (files, directories and links), and
use metadata to express all other attributes of those objects.

At the extreme, every object gets a serial number which is used as its
name in the backup store's filesystem.  That serial number is used to
index into the metadata store, to discover the properties of the object
as it should be restored, including ownership, permissions, extended
attributes, NTFS permissions, creation, modification and access times
and checksums.

Directories can be virtualized in the same way.

This addresses more than just long filenames.  It also addresses my
"Write-once read-many problem" issue, as well as the issue of
rdiff-backup losing permissions when backing up from NTFS to UFS and
then restoring back to NTFS.

It sidesteps an entire family of problems that arises out of what I
consider to be a design limitation -- rdiff-backup does not seem to
have been originally designed to be as cross-platform a utility as
people would now like it to be.

This is one of the challenges that successful software inevitably
faces. :-)

Ciao,
Sheldon.

_______________________________________________
rdiff-backup-users mailing list at [hidden email]
http://lists.nongnu.org/mailman/listinfo/rdiff-backup-users
Wiki URL: http://rdiff-backup.solutionsfirst.com.au/index.php/RdiffBackupWiki

attachment0 (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Proposal to fix long filenames

Chris Wilson-5
In reply to this post by Ben Escoto
Hi Ben,

> Time to fix rdiff-backup's oldest bug?  In this message I'll describe
> the problem and one way to fix it.

Great idea! Just a few small points:

> There are three different ways I can see this happening:
[...]
> 3)  The source filesystem supports longer filenames than the
>    destination.  In this case the mirror file may be too long to
>    write even without any quoting.  I've never heard of this actually
>    happening.

There is a fourth case: where the destination path is deeper into the
destination filesystem than the source path is. For example, I backup many
machines root directories (/) into /mnt/backup/<machine-name>/rdiff on my
backup servers. In this case, both the original filename and the
increments may be too long to back up.

The increments in the rdiff-backup-data directory also have
"rdiff-backup-data/" prepended to the name. In this case, the increment
names may be too long.

> The mirror_metadata file could have two additional optional fields,
> called "MirrorFilename" and "IncrementFilename".  If MirrorFilename is
> set, rdiff-backup reads the mirror file from the
> rdiff-backup-data/long_filename_data/<mirror filename> file, instead
> of from the normal location in the mirror directory.

The MirrorFilename seems like a good idea in principle, but it means that
the mirror files are not located in their usual place in the mirror
filesystem. I don't think that's a good thing, as it makes it
significantly harder to examine or restore the latest version "by hand",
and compute the disk space used by it.

> Similarly, if IncrementFilename is set, increment data will not be
> read from rdiff-backup-data/increments/<whatever>.<suffix> but from
> rdiff-backup-data/long_filename_data/<increment filename>.<suffix>

Similarly, it means that some increments are not where we expect them to
be.

> The alternate filenames would have boring but plentiful names like
> 1, 2, etc.

I'd like to propose a compromise:

rdiff-backup figures out the longest possible filename and deepest
possible path for itself when examining the filesystem capabilities.

If, during backup, any path or file to be written to the destination
exceeds those lengths, it's terminated near the maximum length, and a
number appended. The relevant IncrementFilename or MirrorFilename
directive is written to the metadata at the same time. So for example:


  /a/really/long/path/on/a/short/path/file/system

might become

  /a/really/long/path/on/a/short/path/file/s~1

and if the filesystem's limits are so short that directories must be
renamed as well, then keep at least the first character of each one:

  /a/really/long/p~1/on/a/s~1/p~1/f~1/s~1

and if that's not enough, then just replace the directory names with
numbers:

  /1/1/1/1/1/1/1/1/1/1

and if that's not enough, I don't know what else you can do! :-) Shoot the
admin, perhaps.

> Originally I thought that the fix for long filenames might somehow be
> integrated into a scheme to detect and compress renamed files.  But
> now I doubt any renaming scheme is forthcoming.

That's a pity, since I think it would now be really easy: just make a
hash table of the SHA-1 checksums in the mirror, and compare the checksum
of each newly added file to this list, to see if it's a duplicate or a
moved file. This shortcuts the need to transfer the file again.

Cheers, Chris.
--
_ ___ __     _
  / __/ / ,__(_)_  | Chris Wilson <0000 at qwirx.com> - Cambs UK |
/ (_/ ,\/ _/ /_ \ | Security/C/C++/Java/Perl/SQL/HTML Developer |
\ _/_/_/_//_/___/ | We are GNU-free your mind-and your software |



_______________________________________________
rdiff-backup-users mailing list at [hidden email]
http://lists.nongnu.org/mailman/listinfo/rdiff-backup-users
Wiki URL: http://rdiff-backup.solutionsfirst.com.au/index.php/RdiffBackupWiki
Reply | Threaded
Open this post in threaded view
|

Re: Proposal to fix long filenames

Ben Escoto
>>>>> Chris Wilson <[hidden email]>
>>>>> wrote the following on Sat, 12 Nov 2005 12:25:09 +0000 (GMT)
>
> There is a fourth case: where the destination path is deeper into the
> destination filesystem than the source path is. For example, I backup many
> machines root directories (/) into /mnt/backup/<machine-name>/rdiff on my
> backup servers. In this case, both the original filename and the
> increments may be too long to back up.

Very good point.  rdiff-backup can also have this problem with too
long paths, and it might be best to solve both problems at once.

> I'd like to propose a compromise:
>
> rdiff-backup figures out the longest possible filename and deepest
> possible path for itself when examining the filesystem capabilities.
>
> If, during backup, any path or file to be written to the destination
> exceeds those lengths, it's terminated near the maximum length, and a
> number appended. The relevant IncrementFilename or MirrorFilename
> directive is written to the metadata at the same time. So for example:
>
>
>   /a/really/long/path/on/a/short/path/file/system
>
> might become
>
>   /a/really/long/path/on/a/short/path/file/s~1
>
> and if the filesystem's limits are so short that directories must be
> renamed as well, then keep at least the first character of each one:
>
>   /a/really/long/p~1/on/a/s~1/p~1/f~1/s~1
I would like to do something like this, because it preserves more of
the mirror flavor, but there are three issues:

1)  What happens when the mirror uses one of the "spare" filenames
    that rdiff-backup has used for long filenames?  For instance, in
    your example above, what if someone writes /a/really/long/p~1 to
    the mirror?

2)  This change wouldn't be backwards-compatible, because currently a
    file p~1 in the mirror directory means there was a source file
    also called p~1.

3)  rdiff-backup only makes one pass, and it would be a pain to change
    this (besides making things much slower).  It doesn't know in
    advance what the deepest path would be, and so doesn't know to
    rename a directory if paths in the directory are too long.

Also it's not clear that the long path problem is the same as the long
filename problem.  I think that OSes don't care about the absolute
length of a file's path---the limitation only applies to commands used
to manipulate the paths.  So I think chdir'ing when appropriate would
fix the problem without requiring any change to the format of the
repository.

> That's a pity, since I think it would now be really easy: just make
> a hash table of the SHA-1 checksums in the mirror, and compare the
> checksum of each newly added file to this list, to see if it's a
> duplicate or a moved file. This shortcuts the need to transfer the
> file again.

This could be possible, but I was keeping separate the means of
transfer (which might include tricks like that one), and the format of
the repository.  The problem of the long filename is a problem with
the repository format, and can't be fixed just by transferring files
in an innovative way.

There could be some rename-detecting plan which affected the
repository format:  for instance, if I file was renamed we put a
special kind of diff which indicates a change not from the later
version of that file, but from another file.  Or if a file's SHA1 hash
matched another file, we don't bother to write both files separately
to the mirror.  There might be some trickery here which would also fix
the long filename problem, but I doubt there's anything that would be
worth the complexity.


--
Ben Escoto

_______________________________________________
rdiff-backup-users mailing list at [hidden email]
http://lists.nongnu.org/mailman/listinfo/rdiff-backup-users
Wiki URL: http://rdiff-backup.solutionsfirst.com.au/index.php/RdiffBackupWiki

attachment0 (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Proposal to fix long filenames

Ben Escoto
In reply to this post by Sheldon Hearn
>>>>> Sheldon Hearn <[hidden email]>
>>>>> wrote the following on Sat, 12 Nov 2005 12:02:45 +0200
>
> I think this is another edge case that speaks to the value of
> entirely virtualizing the backup store.  In other words, don't rely
> AT ALL on the capabilities of the filesystem used to store backups,
> except for those capabilities common to all documented as being
> supported for rdiff-backup servers.  In real terms, this leaves you
> with pretty short names and just about nothing else.
...
> At the extreme, every object gets a serial number which is used as
> its name in the backup store's filesystem.  That serial number is
> used to index into the metadata store, to discover the properties of
> the object as it should be restored, including ownership,
> permissions, extended attributes, NTFS permissions, creation,
> modification and access times and checksums.

This is the direction my original long-filename suggestion was moving,
since the repository filenames/paths don't have much to do with the
source filenames.  Also I think there could be a really great backup
program that worked like this.

But this is basically the way most backup programs work, and from the
beginning the premise of rdiff-backup was that it made a mirror.  The
best backup system that used your scheme would have a different
architecture, and might not have all that much in common with a
mirror+increment system.  (For instance, if I were to your scheme from
scratch I would optimize for random access of older data, so it could
be mounted with FUSE or similar with decent performance.)

> It sidesteps an entire family of problems that arises out of what I
> consider to be a design limitation -- rdiff-backup does not seem to
> have been originally designed to be as cross-platform a utility as
> people would now like it to be.

True, sticking with the "preserve everything, but also make a mirror"
idea leads to extra problems, but solving these new problems can also
be an advantage.  For instance, rdiff-backup has become a pretty
flexible copy/mirroring program that is better than rsync in many
ways.


--
Ben Escoto

_______________________________________________
rdiff-backup-users mailing list at [hidden email]
http://lists.nongnu.org/mailman/listinfo/rdiff-backup-users
Wiki URL: http://rdiff-backup.solutionsfirst.com.au/index.php/RdiffBackupWiki

attachment0 (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Proposal to fix long filenames

dean gaudet-4
On Sun, 13 Nov 2005, Ben Escoto wrote:

> >>>>> Sheldon Hearn <[hidden email]>
> >>>>> wrote the following on Sat, 12 Nov 2005 12:02:45 +0200
> > At the extreme, every object gets a serial number which is used as
> > its name in the backup store's filesystem.
...
> But this is basically the way most backup programs work, and from the
> beginning the premise of rdiff-backup was that it made a mirror.

i've been thinking along the lines of sheldon's proposal for a while
actually...

most of the times i want the mirror functionality it's only for a small
subtree at a time -- if i need the entire backup it's really better for me
to restore it (due to metadata).  for folks with posix filesystems with
hardlinks there's a relatively fast option to mirror subtrees out of a
"virtualized" mirror like sheldon is proposing -- rdiff-backup could
hardlink the existing mirror files into an appropriate directory on the
same partition.

then i can look about in that hardlinked tree and remove it when i'm done
perusing or copying whatever it is i was interested in.

you'd have to be careful about accidentally modifying the hardlinked
mirror, but no more careful than you have to be today when perusing the
mirror itself.  (actually we could remove write perms from all files and
directories by default no matter what we do about long filenames...
something to consider.)

this doesn't help people using less featureful filesystems though.

while the mirror property was something which initially attracted me to
rdiff-backup, it wasn't the primary factor ... i was more attracted by
rsync-style network usage, (relatively) efficient storage of increments,
and storing backups on hard disk instead of tape.  (i was already doing
backups to hd with tar incrementals because i can't stand tape... but it
wasn't as space or network efficient as rdiff-backup.)


> The
> best backup system that used your scheme would have a different
> architecture, and might not have all that much in common with a
> mirror+increment system.  (For instance, if I were to your scheme from
> scratch I would optimize for random access of older data, so it could
> be mounted with FUSE or similar with decent performance.)

you know i'm not so sure the goals conflict...

even if you wanted to do something like FUSE as you suggest you're going
to need to generate the already-patched blocks of older files ... so you'd
probably end up keeping a cache around at the FUSE level.

the only real optimisation i can think of is to store all the deltas for a
particular object together -- so that you only need to go to one place to
rebuild whatever ancestor you're interested in.  but realistically even if
you concatenate them together the filesystem isn't generally going to be
able to avoid fragmentation...

if i weren't lazy and were doing something like this from scratch i'd
optimize assuming FUSE exists and use a compact single-file-per-backup
representation and let a FUSE layer provide a mirror interface if it's
desired...

i'd go for a single-file-per-backup compressed in chunks with zlib (to
enable random access), and append an index.

a few motivations for doing this:

- reduce I/O overhead on the backup server by eliminating a lot of
  disk seeks.  (and probably reduce CPU overhead as well due to inode
  reduction.)

- simplify archival to DVD/wherever (even archival to another hard drive
  would be fast due to all sequential read/write).

- fold in the functionality of duplicity -- you could read/write through a
  gpg filter (chunks would be necessary still)

- my largest backup is throwing away at least 0.6GB disk space just for
  the tail fragments on all the rdiff-backup-data inodes ... this is for
  28 days of increments on a 1.5M inode fs -- there are an additional 0.5M
  inodes in rdiff-backup-data, of which 0.3M have a non-zero size, and
  so on avg waste 2048 bytes (4KiB blocks).

not that i'm trying to convince you either way... i'm just babbling
really.

-dean


_______________________________________________
rdiff-backup-users mailing list at [hidden email]
http://lists.nongnu.org/mailman/listinfo/rdiff-backup-users
Wiki URL: http://rdiff-backup.solutionsfirst.com.au/index.php/RdiffBackupWiki
Reply | Threaded
Open this post in threaded view
|

Re: Proposal to fix long filenames

Ben Escoto
>>>>> dean gaudet <[hidden email]>

>>>>> wrote the following on Sun, 13 Nov 2005 17:48:11 -0800 (PST)
> you know i'm not so sure the goals conflict...
>
> even if you wanted to do something like FUSE as you suggest you're
> going to need to generate the already-patched blocks of older files
> ... so you'd probably end up keeping a cache around at the FUSE
> level.
>
> the only real optimisation i can think of is to store all the deltas
> for a particular object together -- so that you only need to go to
> one place to rebuild whatever ancestor you're interested in.  but
> realistically even if you concatenate them together the filesystem
> isn't generally going to be able to avoid fragmentation...
I thought about this in some detail when I was thinking about how to
redesign duplicity.  (Unfortunately I never ended up having enough
time to actually do that.)

You mention some optimizations we could use to remove some seeks, but
it seems a bigger problem is that, as it is, random access doesn't
even have the right order of complexity.

For instance, listing the directory as it is requires that the entire
mirror_metadata file (which can be huge) be decompressed and parsed.
Reading the last block from an older compressed file may require that
all of all of the snapshots be decompressed.

Caching could help a bit with this, but I think it's a lost cause when
basic operations that applications think will take constant time
actually take linear time.

This being said, someone could take the current rdiff-backup format
and put together a FUSE interface that would be useful for many
applications.  I would just have the FUSE mount take the
mirror_metadata file and rebuild it with traditional directory-inode
pointers, and cache file blocks as you said.

> - my largest backup is throwing away at least 0.6GB disk space just
>   for the tail fragments on all the rdiff-backup-data inodes
>   ... this is for 28 days of increments on a 1.5M inode fs -- there
>   are an additional 0.5M inodes in rdiff-backup-data, of which 0.3M
>   have a non-zero size, and so on avg waste 2048 bytes (4KiB
>   blocks).

Yeah, rdiff-backup uses a lot of small files.  Eventually though most
filesystems should get tail-packing like reiserfs, so it won't be as
big of an issue.


--
Ben Escoto

_______________________________________________
rdiff-backup-users mailing list at [hidden email]
http://lists.nongnu.org/mailman/listinfo/rdiff-backup-users
Wiki URL: http://rdiff-backup.solutionsfirst.com.au/index.php/RdiffBackupWiki

attachment0 (196 bytes) Download Attachment