Filesystem in Userspace

Miklos Szeredi <miklos@...> writes:

> Here is my first try at a "delta" filesystem.  It takes two
> directories, one of which is a read-only base, and the other is where
> the differences are stored.  It stores data, metadata and directory
> modifications without copying up whole files from the read-only
> branch.
>
> The layout of the delta store may look similar to the writable branch
> of a union fs, but this is basically just coincidence (it was easier
> to start out this way).
>
> Currently it's implemented with fuse and it's not optimized at all, so
> performance may suck in some cases.  But I think this is a useful
> concept and a better model, than trying to fit writable branches into
> a union filesystem.
>
> Comments, bug reports are welcome.
>
> Thanks,
> Miklos

Wouldn't it make more sense to start with unionfs-fuse and add a delta
feature to it? unionfs-fuse already has all you need except that it
will copy the whole file (if on a read-only branch) on write.

MfG
        Goswin

On Saturday 28 February 2009, Goswin von Brederlow wrote:
> Miklos Szeredi <miklos@...> writes:
> > Here is my first try at a "delta" filesystem.  It takes two
> > directories, one of which is a read-only base, and the other is where
> > the differences are stored.  It stores data, metadata and directory
> > modifications without copying up whole files from the read-only
> > branch.
> >
> > The layout of the delta store may look similar to the writable branch
> > of a union fs, but this is basically just coincidence (it was easier
> > to start out this way).
> >
> > Currently it's implemented with fuse and it's not optimized at all, so
> > performance may suck in some cases.  But I think this is a useful
> > concept and a better model, than trying to fit writable branches into
> > a union filesystem.
> >
> > Comments, bug reports are welcome.
> >
> > Thanks,
> > Miklos
>
> Wouldn't it make more sense to start with unionfs-fuse and add a delta
> feature to it? unionfs-fuse already has all you need except that it
> will copy the whole file (if on a read-only branch) on write.

Well yes, but it would need to be configurable by the user. IMMHO, the 'delta' 
ansatz has a big problem - what happens if the admin decides to modify the 
underlying ro-branch, which is a distribution chroot seen by all clients as 
their '/'? Any time files may be modified or even deleted on this branch when 
the admin does an update.
This is also the exactly the problem why none of the kernel unionfs 
implementation fits my needs and why I started to work on unionfs-fuse. Only, 
the delta approach makes it even worse ;)


Cheers,
Bernd

Miklos Szeredi wrote:
> Here is my first try at a "delta" filesystem.  It takes two
> directories, one of which is a read-only base, and the other is where
> the differences are stored.  It stores data, metadata and directory
> modifications without copying up whole files from the read-only
> branch.
> 
> The layout of the delta store may look similar to the writable branch
> of a union fs, but this is basically just coincidence (it was easier
> to start out this way).
> 
> Currently it's implemented with fuse and it's not optimized at all, so
> performance may suck in some cases.  But I think this is a useful
> concept and a better model, than trying to fit writable branches into
> a union filesystem.
> 
> Comments, bug reports are welcome.
Well just as a quick idea - wouldn't it be possible to create a fuse 
filesystem on top of a git repository? They are pretty much already 
doing deltas all the time...

Bernd Schubert <bs_lists@...> writes:

> On Saturday 28 February 2009, Goswin von Brederlow wrote:
>> Miklos Szeredi <miklos@...> writes:
>> > Here is my first try at a "delta" filesystem.  It takes two
>> > directories, one of which is a read-only base, and the other is where
>> > the differences are stored.  It stores data, metadata and directory
>> > modifications without copying up whole files from the read-only
>> > branch.
>> >
>> > The layout of the delta store may look similar to the writable branch
>> > of a union fs, but this is basically just coincidence (it was easier
>> > to start out this way).
>> >
>> > Currently it's implemented with fuse and it's not optimized at all, so
>> > performance may suck in some cases.  But I think this is a useful
>> > concept and a better model, than trying to fit writable branches into
>> > a union filesystem.
>> >
>> > Comments, bug reports are welcome.
>> >
>> > Thanks,
>> > Miklos
>>
>> Wouldn't it make more sense to start with unionfs-fuse and add a delta
>> feature to it? unionfs-fuse already has all you need except that it
>> will copy the whole file (if on a read-only branch) on write.
>
> Well yes, but it would need to be configurable by the user. IMMHO, the 'delta' 
> ansatz has a big problem - what happens if the admin decides to modify the 
> underlying ro-branch, which is a distribution chroot seen by all clients as 
> their '/'? Any time files may be modified or even deleted on this branch when 
> the admin does an update.
> This is also the exactly the problem why none of the kernel unionfs 
> implementation fits my needs and why I started to work on unionfs-fuse. Only, 
> the delta approach makes it even worse ;)
>
>
> Cheers,
> Bernd

Obviously with delta storage the underlying branches really MUST be
read-only. As for configuration I see no problem in clasifying a
branch as RO, RW or D. If the user wants a modifiable RO branch then
he can not have any D branch. Easy enough.

MfG
        Goswin

On Sun, Mar 01, 2009 at 09:09:59AM +0100, LCID Fire wrote:
> Miklos Szeredi wrote:
> > Here is my first try at a "delta" filesystem.  It takes two
> > directories, one of which is a read-only base, and the other is where
> > the differences are stored.  It stores data, metadata and directory
> > modifications without copying up whole files from the read-only
> > branch.
> > 
> > The layout of the delta store may look similar to the writable branch
> > of a union fs, but this is basically just coincidence (it was easier
> > to start out this way).
> > 
> > Currently it's implemented with fuse and it's not optimized at all, so
> > performance may suck in some cases.  But I think this is a useful
> > concept and a better model, than trying to fit writable branches into
> > a union filesystem.
> > 
> > Comments, bug reports are welcome.
> Well just as a quick idea - wouldn't it be possible to create a fuse 
> filesystem on top of a git repository? They are pretty much already 
> doing deltas all the time...

There is one already, except it hasn't been updated in a while. The
other problem is that git doesn't have a stable API, which makes
building something like this, at least in C, a big problem.

Mike

LCID Fire <lcid-fire@...> writes:

> Miklos Szeredi wrote:
>> Here is my first try at a "delta" filesystem.  It takes two
>> directories, one of which is a read-only base, and the other is where
>> the differences are stored.  It stores data, metadata and directory
>> modifications without copying up whole files from the read-only
>> branch.
>> 
>> The layout of the delta store may look similar to the writable branch
>> of a union fs, but this is basically just coincidence (it was easier
>> to start out this way).
>> 
>> Currently it's implemented with fuse and it's not optimized at all, so
>> performance may suck in some cases.  But I think this is a useful
>> concept and a better model, than trying to fit writable branches into
>> a union filesystem.
>> 
>> Comments, bug reports are welcome.
> Well just as a quick idea - wouldn't it be possible to create a fuse 
> filesystem on top of a git repository? They are pretty much already 
> doing deltas all the time...

http://www.sfgoth.com/~mitch/linux/gitfs/

MfG
        Goswin

Miklos Szeredi:
> Here is my first try at a "delta" filesystem.  It takes two
	:::
> Comments, bug reports are welcome.

As I wrote before, it is unclear how do you implment mmap.
I am afrid you need to copyup the entire file to support MAP_SHARED.

Since you don't care the inum, the hardlink will not work correctly. For
instance,
$ cd /base
$ echo a > a
$ ln a b
$ cd /deltafs
$ echo a >> a
$ cat b

By the way, are you going to review the aufs2-tmp-ro branch which I made
it responding you.


J. R. Okajima

hooanon05@... writes:

> Miklos Szeredi:
>> Here is my first try at a "delta" filesystem.  It takes two
> 	:::
>> Comments, bug reports are welcome.
>
> As I wrote before, it is unclear how do you implment mmap.
> I am afrid you need to copyup the entire file to support MAP_SHARED.

Why? When a page is accessed the filesystem gets a read request and
reads it either from the RO branch or the delta branch. Why should it
need to copy up the full file?

MfG
        Goswin

Goswin von Brederlow:
> Why? When a page is accessed the filesystem gets a read request and
> reads it either from the RO branch or the delta branch. Why should it
> need to copy up the full file?

For example,
- you have two mmap for a single file
- the first mapping is done, it may map the file on the lower rdonly
  layer
- the other mapping modifies the contents
- can the first mapping see the new content?

Of course, it may depend on the implementation.


J. R. Okajima

On Tue, 2009-03-03 at 22:11 +0900, hooanon05@... wrote:
> Goswin von Brederlow:
> > Why? When a page is accessed the filesystem gets a read request and
> > reads it either from the RO branch or the delta branch. Why should it
> > need to copy up the full file?
> 
> For example,
> - you have two mmap for a single file
> - the first mapping is done, it may map the file on the lower rdonly
>   layer
> - the other mapping modifies the contents
> - can the first mapping see the new content?

The lower read-only file would not appear to user-space as the same file
at all.  It would have its own address space.  It clearly would not see
the new content.

There wouldn't be any problem with reading pages from the lower file for
the upper file one at a time as they are faulted.

Shaggy
-- 
David Kleikamp
IBM Linux Technology Center

Dave Kleikamp:
> The lower read-only file would not appear to user-space as the same file
> at all.  It would have its own address space.  It clearly would not see
> the new content.
> 
> There wouldn't be any problem with reading pages from the lower file for
> the upper file one at a time as they are faulted.

I am afraid that I cannot understand fully what you wrote (due to my
poor English).
Do you mean that the entire file copyup will be necessary?


J. R. Okajima

On Wed, 2009-03-04 at 00:50 +0900, hooanon05@... wrote:
> Dave Kleikamp:
> > The lower read-only file would not appear to user-space as the same file
> > at all.  It would have its own address space.  It clearly would not see
> > the new content.
> > 
> > There wouldn't be any problem with reading pages from the lower file for
> > the upper file one at a time as they are faulted.
> 
> I am afraid that I cannot understand fully what you wrote (due to my
> poor English).
> Do you mean that the entire file copyup will be necessary?

No.  I was saying the opposite.  Nothing that happens to the upper
address space would be visible to the lower address space.  The upper
file could read from the lower file system on-demand as pages are
faulted.  There is no need to copy everything at once.

Shaggy
-- 
David Kleikamp
IBM Linux Technology Center

Dave Kleikamp:
> No.  I was saying the opposite.  Nothing that happens to the upper
> address space would be visible to the lower address space.  The upper
> file could read from the lower file system on-demand as pages are
> faulted.  There is no need to copy everything at once.

So you mean,
- you have two mmap for a single file
- the first mapping is done, it may map the file on the lower rdonly
  layer
- the other mapping modifies the contents
- when a page in the first mapping accessed again, the page is read from
  the upper layer.
Right?


J. R. Okajima

On Wed, 2009-03-04 at 01:02 +0900, hooanon05@... wrote:
> Dave Kleikamp:
> > No.  I was saying the opposite.  Nothing that happens to the upper
> > address space would be visible to the lower address space.  The upper
> > file could read from the lower file system on-demand as pages are
> > faulted.  There is no need to copy everything at once.
> 
> So you mean,
> - you have two mmap for a single file

Explain what you mean by a single file.  If there are two mmaps to the
upper file, they will see the same changes.  If one is to the upper
file, and one is to the lower file, they will NOT be mmap'ed to the same
file.

> - the first mapping is done, it may map the file on the lower rdonly
>   layer

This mapping will only ever see the lower contents

> - the other mapping modifies the contents

The upper mapping will contain data pages with modified content.  Only
those pages accessed will be copied (if necessary) from the lower file.

> - when a page in the first mapping accessed again, the page is read from
>   the upper layer.

No.  The first mapping is not even aware of the second mapping.  It
continues to see the read-only data

> Right?
No

Shaggy
-- 
David Kleikamp
IBM Linux Technology Center

Dave Kleikamp:
> > - you have two mmap for a single file
> 
> Explain what you mean by a single file.  If there are two mmaps to the
> upper file, they will see the same changes.  If one is to the upper
> file, and one is to the lower file, they will NOT be mmap'ed to the same
> file.

A regular file on the lower readonly layer. Not a single block/page is
copied-up yet.


> No.  The first mapping is not even aware of the second mapping.  It
> continues to see the read-only data

Should the first mapping see the latest (modified) content?


J. R. Okajima

On Wed, 2009-03-04 at 01:19 +0900, hooanon05@... wrote:
> Dave Kleikamp:
> > > - you have two mmap for a single file
> > 
> > Explain what you mean by a single file.  If there are two mmaps to the
> > upper file, they will see the same changes.  If one is to the upper
> > file, and one is to the lower file, they will NOT be mmap'ed to the same
> > file.
> 
> A regular file on the lower readonly layer. Not a single block/page is
> copied-up yet.

I understand the file physically resides on the lower layer.  The delta
file system will presents a new file on a different path that initially
has the contents of the lower file.  If you are mmapping the file
presented by the delta files system, then both mmaps will see the same
modified data.

Any mmaps to the original path of the read-only file system will not see
any modified data.

dd if=/dev/zero of=/ro/a bs=4096 count=1000
# /ro/a contains 1000 pages of zeros
mount -o remount,ro /ro # make sure it's read-only
mount -t deltafs /ro /rw
 mmap(addr1, "/ro/a", ...);
 mmap(addr2, "/rw/a", ...);
mmap(addr3, "/rw/a", ...);

If you modify the file through addr3, addr2 will see the changes.  the
address space for /rw/a is shared.  However, addr1 will only see the
read-only data.  /ro/a will not be modified.

deltafs (does this filesystem have a name yet?) does not need to copy
all 1000 pages from the lower file.  It can read from the lower file as
needed when a page is accessed.  The modified data will be present in
the upper address space's page cache.  I assume it will eventually be
written as a "delta" in the upper file system.

> > No.  The first mapping is not even aware of the second mapping.  It
> > continues to see the read-only data
> 
> Should the first mapping see the latest (modified) content?

If you're asking about the case of addr2 and addr3 above, then yes.  For
addr1, no.

-- 
David Kleikamp
IBM Linux Technology Center

Dave Kleikamp:
> I understand the file physically resides on the lower layer.  The delta
> file system will presents a new file on a different path that initially
> has the contents of the lower file.  If you are mmapping the file
> presented by the delta files system, then both mmaps will see the same
> modified data.

Ok, I will read fuse (instead of deltafs.c) again.
Thank you.


J. R. Okajima

On Sun, 01 Mar 2009, Goswin von Brederlow wrote:
> Obviously with delta storage the underlying branches really MUST be
> read-only. As for configuration I see no problem in clasifying a
> branch as RO, RW or D. If the user wants a modifiable RO branch then
> he can not have any D branch. Easy enough.

Not necessarily.  A delta filesystem could support automatic or manual
merges very well.  This is not really possible with a writable union.

Miklos

hooanon05@... writes:

> Dave Kleikamp:
>> I understand the file physically resides on the lower layer.  The delta
>> file system will presents a new file on a different path that initially
>> has the contents of the lower file.  If you are mmapping the file
>> presented by the delta files system, then both mmaps will see the same
>> modified data.
>
> Ok, I will read fuse (instead of deltafs.c) again.
> Thank you.
>
>
> J. R. Okajima

By the way. If you mmap a file in fuse shared twice wouldn't the
kernel share the physical pages. So the first access calls fuse and
loads the data into memory, the second access would just get the same
physical page mapped. Right?

MfG
        Goswin

hooanon05@... writes:

> Goswin von Brederlow:
>> Why? When a page is accessed the filesystem gets a read request and
>> reads it either from the RO branch or the delta branch. Why should it
>> need to copy up the full file?
>
> For example,
> - you have two mmap for a single file

On open you have to create an internal FD structure that keeps track
of the delta informtaions and the read-only and delta filedescriptors
(one or both can be -1). If the same file is opened again you have to
use the same internal FD structure so both share the same delta
informations.

> - the first mapping is done, it may map the file on the lower rdonly
>   layer
> - the other mapping modifies the contents
> - can the first mapping see the new content?

Both mmaps would be to the internal FD and thus share any change made
by one of them.

> Of course, it may depend on the implementation.

Sure. If you don't create an internal FD structure and share it
between open calls things will break. Not just mmap.

MfG
        Goswin

On Wed, 2009-03-04 at 12:52 +0100, Goswin von Brederlow wrote:
> hooanon05@... writes:
> 
> > Dave Kleikamp:
> >> I understand the file physically resides on the lower layer.  The delta
> >> file system will presents a new file on a different path that initially
> >> has the contents of the lower file.  If you are mmapping the file
> >> presented by the delta files system, then both mmaps will see the same
> >> modified data.
> >
> > Ok, I will read fuse (instead of deltafs.c) again.
> > Thank you.
> >
> >
> > J. R. Okajima
> 
> By the way. If you mmap a file in fuse shared twice wouldn't the
> kernel share the physical pages. So the first access calls fuse and
> loads the data into memory, the second access would just get the same
> physical page mapped. Right?

Right.  Some of my comments were a result of not being clear on what J.
R. meant when he asked about the first mapping being to the lower file.
Both mmaps to the same file in fuse would access the same physical
pages.

Shaggy
-- 
David Kleikamp
IBM Linux Technology Center

Miklos Szeredi <miklos@...> writes:

> On Sun, 01 Mar 2009, Goswin von Brederlow wrote:
>> Obviously with delta storage the underlying branches really MUST be
>> read-only. As for configuration I see no problem in clasifying a
>> branch as RO, RW or D. If the user wants a modifiable RO branch then
>> he can not have any D branch. Easy enough.
>
> Not necessarily.  A delta filesystem could support automatic or manual
> merges very well.  This is not really possible with a writable union.
>
> Miklos

Bernd and I ment the following scenario:

/dev/sda1 /union/read-only
tmpfs     /union/read-write

with a delta-fs merging the two. Then running "echo foo >
/union/read-only/path/file" could be desasterous to your data.

The underlying branch must not change on its own. The delta-fs could
change it on command but that wasn't what we where thinking of.

MfG
        Goswin

Dave Kleikamp:
> On Wed, 2009-03-04 at 12:52 +0100, Goswin von Brederlow wrote:
	:::
> > By the way. If you mmap a file in fuse shared twice wouldn't the
> > kernel share the physical pages. So the first access calls fuse and
> > loads the data into memory, the second access would just get the same
> > physical page mapped. Right?
> 
> Right.  Some of my comments were a result of not being clear on what J.
> R. meant when he asked about the first mapping being to the lower file.
> Both mmaps to the same file in fuse would access the same physical
> pages.

I didn't know how fuse implements mmap and sharing pages. Additionally
there is no mmap code in deltafs.c. So I wrote "it is unclear how do you
implment mmap".

Now I am reading fuse (instead of deltafs.c) and begin understanding
that fuse and deltafs work as you expected. But the implementation seems
different a little to me.
These two mappings are not sharing memory pages but keeping the latest
contents by re-reading, do they?


J. R. Okajima

On Wed, 04 Mar 2009, Goswin von Brederlow wrote:
> Bernd and I ment the following scenario:
> 
> /dev/sda1 /union/read-only
> tmpfs     /union/read-write
> 
> with a delta-fs merging the two. Then running "echo foo >
> /union/read-only/path/file" could be desasterous to your data.

Well, if the writable branch is really meant to be a clone of the
underlying fs, then yes.  But writable unions are _not_ clones either,
very far from that.

> The underlying branch must not change on its own. The delta-fs could
> change it on command but that wasn't what we where thinking of.

Delta-fs could deal with changes in the underlying filesystem, in some
cases much better than unionfs (for example if the file was renamed in
the delta-fs, and it was later modified in the underlying fs).

Thanks,
Miklos

Miklos Szeredi <miklos@...> writes:

> On Wed, 04 Mar 2009, Goswin von Brederlow wrote:
>> Bernd and I ment the following scenario:
>> 
>> /dev/sda1 /union/read-only
>> tmpfs     /union/read-write
>> 
>> with a delta-fs merging the two. Then running "echo foo >
>> /union/read-only/path/file" could be desasterous to your data.
>
> Well, if the writable branch is really meant to be a clone of the
> underlying fs, then yes.  But writable unions are _not_ clones either,
> very far from that.

The problem is that /delta-fs/path/file would suddenly be a composite
of the new file /union/read-only/path/file and any stored delta
information in /union/read-write/path/file of the old file.

In unionfs-fuse files are currently always completly copy-up-ed when
modified. There a change of /union/read-only/path/file will give the
new file if it wasn't modified or the old modified file if it was. But
never mix the two.

>> The underlying branch must not change on its own. The delta-fs could
>> change it on command but that wasn't what we where thinking of.
>
> Delta-fs could deal with changes in the underlying filesystem, in some
> cases much better than unionfs (for example if the file was renamed in
> the delta-fs, and it was later modified in the underlying fs).
>
> Thanks,
> Miklos

Ugh, no. The delta-fs has no way of knowing when a file in a branch
will be changed outside of delta-fs. And it would have to know that
before the change so it can copy-up relevant data before they change.

MfG
        Goswin

Goswin von Brederlow:
> The problem is that /delta-fs/path/file would suddenly be a composite
> of the new file /union/read-only/path/file and any stored delta
> information in /union/read-write/path/file of the old file.

Yes.
And I am afraid stat.st_blocks will be incorrect too. But it may be a
smaller problem for who think there is another bigger advantage. It
might be just a trade off.


J. R. Okajima

On Thu, 05 Mar 2009, Goswin von Brederlow wrote:
> Miklos Szeredi <miklos@...> writes:
> 
> > On Wed, 04 Mar 2009, Goswin von Brederlow wrote:
> >> Bernd and I ment the following scenario:
> >> 
> >> /dev/sda1 /union/read-only
> >> tmpfs     /union/read-write
> >> 
> >> with a delta-fs merging the two. Then running "echo foo >
> >> /union/read-only/path/file" could be desasterous to your data.
> >
> > Well, if the writable branch is really meant to be a clone of the
> > underlying fs, then yes.  But writable unions are _not_ clones either,
> > very far from that.
> 
> The problem is that /delta-fs/path/file would suddenly be a composite
> of the new file /union/read-only/path/file and any stored delta
> information in /union/read-write/path/file of the old file.

It can detect changes to the underlying file from the modification
time (which it can store together with the delta).

But having data deltas are in fact not even that interesting.  Files
are not often modified without being completely rewritten.  Appending:
that happens, but again that can be handled in an intelligent way by
the delta layer.

The most interesting is the directory and metadata deltas, which do
make a delta-fs like implementation much more effective and nicer as a
dumb union type filesystem.  Mind, unionfs and aufs are rapidly
acquiring non-union traits, like inode number storage, virtual hard
links (not to speak of whiteouts).  Which makes them all the more
hackish, I much prefer a conceptually clean solution.

> In unionfs-fuse files are currently always completly copy-up-ed when
> modified. There a change of /union/read-only/path/file will give the
> new file if it wasn't modified or the old modified file if it was. But
> never mix the two.

So?  Some datasets may reside in multiple files, and inconsistencies
could just as as well present themselves in that case.

Thanks,
Miklos

hooanon05@... writes:

> Goswin von Brederlow:
>> The problem is that /delta-fs/path/file would suddenly be a composite
>> of the new file /union/read-only/path/file and any stored delta
>> information in /union/read-write/path/file of the old file.
>
> Yes.
> And I am afraid stat.st_blocks will be incorrect too. But it may be a
> smaller problem for who think there is another bigger advantage. It
> might be just a trade off.
>
>
> J. R. Okajima

I could think of three possible values:

1) the sum of the st_blocks of both branches (total space used)
2) min(size/blocksize, sum of st_blocks) (appox. what the file would use)
3) st_bocks of read-write branch (read-write space used only)

I could think of a use for any one of them. Although the 3rd can be
done by "du /union/read-write" if there is an identity mapping between
filenames.

MfG
        Goswin

Miklos Szeredi <miklos@...> writes:

> On Thu, 05 Mar 2009, Goswin von Brederlow wrote:
>> Miklos Szeredi <miklos@...> writes:
>> 
>> > On Wed, 04 Mar 2009, Goswin von Brederlow wrote:
>> >> Bernd and I ment the following scenario:
>> >> 
>> >> /dev/sda1 /union/read-only
>> >> tmpfs     /union/read-write
>> >> 
>> >> with a delta-fs merging the two. Then running "echo foo >
>> >> /union/read-only/path/file" could be desasterous to your data.
>> >
>> > Well, if the writable branch is really meant to be a clone of the
>> > underlying fs, then yes.  But writable unions are _not_ clones either,
>> > very far from that.
>> 
>> The problem is that /delta-fs/path/file would suddenly be a composite
>> of the new file /union/read-only/path/file and any stored delta
>> information in /union/read-write/path/file of the old file.
>
> It can detect changes to the underlying file from the modification
> time (which it can store together with the delta).

But then what do you do? You don't know what changed and it is to late
to recover any data that might be lost.

> But having data deltas are in fact not even that interesting.  Files
> are not often modified without being completely rewritten.  Appending:
> that happens, but again that can be handled in an intelligent way by
> the delta layer.
>
> The most interesting is the directory and metadata deltas, which do
> make a delta-fs like implementation much more effective and nicer as a
> dumb union type filesystem.  Mind, unionfs and aufs are rapidly
> acquiring non-union traits, like inode number storage, virtual hard
> links (not to speak of whiteouts).  Which makes them all the more
> hackish, I much prefer a conceptually clean solution.

That is certainly something for unionfs-fuse as far as it isn't done
already. Doesn't even need any delta algorithm, just seperate storage
of metadata and normal data. Iirc Bernd already did look into
preserving inodes in unionfs-fuse.

>> In unionfs-fuse files are currently always completly copy-up-ed when
>> modified. There a change of /union/read-only/path/file will give the
>> new file if it wasn't modified or the old modified file if it was. But
>> never mix the two.
>
> So?  Some datasets may reside in multiple files, and inconsistencies
> could just as as well present themselves in that case.
>
> Thanks,
> Miklos

MfG
        Goswin

On Fri, 06 Mar 2009, Goswin von Brederlow wrote:
> > It can detect changes to the underlying file from the modification
> > time (which it can store together with the delta).
> 
> But then what do you do? You don't know what changed and it is to late
> to recover any data that might be lost.

No data has been lost.  Or rather the data has been lost, when the
underlying filesystem was modified.  Oh, you didn't want that data to
be lost?  Why did you overwrite it then?  See?

All the data is there: the changes you made to the file are there in
the delta, and the underlying file is still there too, we just didn't
preserve the old version, but this is not what deltafs is about, and
it's not what unionfs is about either.

What to do about such a situation?  It's a policy decision, it could

 - return the underlying file and ignore the delta
 - ignore the changes made to the underlying file and mechanically
   merge the delta (possibly resulting in inconsistencies).
 - return an error (EIO or ESTALE)

In addition the user might have the option to merge the delta by hand,
this should be much easier than trying to merge two files, where you
know _nothing_ about the changes themselves.

In fact the delta format might not even want to implement data deltas,
or they could be made optional, or configurable per file.  Whatever.

> > The most interesting is the directory and metadata deltas, which do
> > make a delta-fs like implementation much more effective and nicer as a
> > dumb union type filesystem.  Mind, unionfs and aufs are rapidly
> > acquiring non-union traits, like inode number storage, virtual hard
> > links (not to speak of whiteouts).  Which makes them all the more
> > hackish, I much prefer a conceptually clean solution.
> 
> That is certainly something for unionfs-fuse as far as it isn't done
> already. Doesn't even need any delta algorithm, just seperate storage
> of metadata and normal data. Iirc Bernd already did look into
> preserving inodes in unionfs-fuse.

At which point it's less of a union and more of a delta.  A union is
taking two ordinary plain filesystems and merging them according to
some rules.  A delta is having a plain filesystem and merging a
special format one into this.  See where I'm going?

My main question in all this is: does it make sense to keep the union
semantics and tack on various features into separate storage?  Or is
it better to abandon the unioning altogether in favor of a more
efficient delta format?

Thanks,
Miklos

Goswin von Brederlow:
> I could think of three possible values:
> 
> 1) the sum of the st_blocks of both branches (total space used)
> 2) min(size/blocksize, sum of st_blocks) (appox. what the file would use)
> 3) st_bocks of read-write branch (read-write space used only)

4) calculate st_blocks by merging based upon bitmap (dmpath)

Some applications may not like st_blksize either since it may be
different per block.

One more difficulty (hard to support issue).
- open a file on deltafs
- unlink it
- rmdir its parent
- write or fchmod to it
- rewind+read or mmap+read from the opened file
- cat it be read correctly?


J. R. Okajima

Miklos Szeredi:
> The most interesting is the directory and metadata deltas, which do
> make a delta-fs like implementation much more effective and nicer as a
> dumb union type filesystem.  Mind, unionfs and aufs are rapidly
> acquiring non-union traits, like inode number storage, virtual hard
> links (not to speak of whiteouts).  Which makes them all the more
> hackish, I much prefer a conceptually clean solution.

I agree that the delta is a good approach. But it is for filedata only.
As I wrote in another mail, how do you support hardlinks on the lower
readonly layer?


J. R. Okajima

Miklos Szeredi <miklos@...> writes:

> On Fri, 06 Mar 2009, Goswin von Brederlow wrote:
>> > The most interesting is the directory and metadata deltas, which do
>> > make a delta-fs like implementation much more effective and nicer as a
>> > dumb union type filesystem.  Mind, unionfs and aufs are rapidly
>> > acquiring non-union traits, like inode number storage, virtual hard
>> > links (not to speak of whiteouts).  Which makes them all the more
>> > hackish, I much prefer a conceptually clean solution.
>> 
>> That is certainly something for unionfs-fuse as far as it isn't done
>> already. Doesn't even need any delta algorithm, just seperate storage
>> of metadata and normal data. Iirc Bernd already did look into
>> preserving inodes in unionfs-fuse.
>
> At which point it's less of a union and more of a delta.  A union is
> taking two ordinary plain filesystems and merging them according to
> some rules.  A delta is having a plain filesystem and merging a
> special format one into this.  See where I'm going?
>
> My main question in all this is: does it make sense to keep the union
> semantics and tack on various features into separate storage?  Or is
> it better to abandon the unioning altogether in favor of a more
> efficient delta format?
>
> Thanks,
> Miklos

The union should be transparent to the user and applications. The
problem is that some application do look at the inode number,
m/a/ctime and so on. So to be transparent the metadata has to be
handled in a union as well. If you want to call it a delta filesystem
then fine. I would expect a delta filesystem to do deltaing of file
content though, not just be able to track metadata changes seperate
from file data. But that is nothing to fight over.

MfG
        Goswin

hooanon05@... writes:

> Goswin von Brederlow:
>> I could think of three possible values:
>> 
>> 1) the sum of the st_blocks of both branches (total space used)
>> 2) min(size/blocksize, sum of st_blocks) (appox. what the file would use)
>> 3) st_bocks of read-write branch (read-write space used only)
>
> 4) calculate st_blocks by merging based upon bitmap (dmpath)
>
> Some applications may not like st_blksize either since it may be
> different per block.
>
> One more difficulty (hard to support issue).
> - open a file on deltafs
> - unlink it
> - rmdir its parent
> - write or fchmod to it
> - rewind+read or mmap+read from the opened file
> - cat it be read correctly?
>
>
> J. R. Okajima

For unlink and rmdir you need whiteout files.

For all the rest you just have to keep the file descriptor(s) alive as
long as the file is opened and cache metadat in the internal FD
structure.

It isn't trivial but it isn't really hard.

MfG
        Goswin

hooanon05@... writes:

> Miklos Szeredi:
>> The most interesting is the directory and metadata deltas, which do
>> make a delta-fs like implementation much more effective and nicer as a
>> dumb union type filesystem.  Mind, unionfs and aufs are rapidly
>> acquiring non-union traits, like inode number storage, virtual hard
>> links (not to speak of whiteouts).  Which makes them all the more
>> hackish, I much prefer a conceptually clean solution.
>
> I agree that the delta is a good approach. But it is for filedata only.
> As I wrote in another mail, how do you support hardlinks on the lower
> readonly layer?
>
>
> J. R. Okajima

Use a filename -> inode indirection and delta based on inode
numbers. Although the you also have to consider the device id in case
there are multiple filesystem mounted in your read-only branch. So
filename -> (dev, inode).

MfG
        Goswin

Goswin von Brederlow:
> For unlink and rmdir you need whiteout files.
> 
> For all the rest you just have to keep the file descriptor(s) alive as
> long as the file is opened and cache metadat in the internal FD
> structure.
> 
> It isn't trivial but it isn't really hard.

Generally it is true.
Actually deltafs already has something like whiteout. It is a symlink to
"(null)".
When a user writes something to the file after unlink+rmdir, where can
deltafs copyup? At least in the current implementation, there is no
place for it.


J. R. Okajima

Goswin von Brederlow:
> > Miklos Szeredi:
> >> The most interesting is the directory and metadata deltas, which do
> >> make a delta-fs like implementation much more effective and nicer as a
> >> dumb union type filesystem.  Mind, unionfs and aufs are rapidly
> >> acquiring non-union traits, like inode number storage, virtual hard
> >> links (not to speak of whiteouts).  Which makes them all the more
> >> hackish, I much prefer a conceptually clean solution.
	:::
> Use a filename -> inode indirection and delta based on inode
> numbers. Although the you also have to consider the device id in case
> there are multiple filesystem mounted in your read-only branch. So
> filename -> (dev, inode).

Agreed.
While Miklos seems to dislike the inum table, it is necessary I think.


J. R. Okajima

hooanon05@... writes:

> Goswin von Brederlow:
>> For unlink and rmdir you need whiteout files.
>> 
>> For all the rest you just have to keep the file descriptor(s) alive as
>> long as the file is opened and cache metadat in the internal FD
>> structure.
>> 
>> It isn't trivial but it isn't really hard.
>
> Generally it is true.
> Actually deltafs already has something like whiteout. It is a symlink to
> "(null)".
> When a user writes something to the file after unlink+rmdir, where can
> deltafs copyup? At least in the current implementation, there is no
> place for it.
>
>
> J. R. Okajima

In the delta branch create a meta/ and files/ directory. In the meta/
directory you keep whiteout files and stat updates. In files/ you
store only changes in the file data itself.

So "rm foo/bar/baz" will create meta/foo/bar/baz.whiteout. Then "echo
blafase >>foo/bar/baz" first searches for a file to copy-up, sees the
meta/foo/bar/baz.whiteout and knows the file was deleted. It then
creates a new files/foo/bar/baz. It might have to copy-up foo and
foo/bar for that though.

MfG
        Goswin

hooanon05@... writes:

> Goswin von Brederlow:
>> > Miklos Szeredi:
>> >> The most interesting is the directory and metadata deltas, which do
>> >> make a delta-fs like implementation much more effective and nicer as a
>> >> dumb union type filesystem.  Mind, unionfs and aufs are rapidly
>> >> acquiring non-union traits, like inode number storage, virtual hard
>> >> links (not to speak of whiteouts).  Which makes them all the more
>> >> hackish, I much prefer a conceptually clean solution.
> 	:::
>> Use a filename -> inode indirection and delta based on inode
>> numbers. Although the you also have to consider the device id in case
>> there are multiple filesystem mounted in your read-only branch. So
>> filename -> (dev, inode).
>
> Agreed.
> While Miklos seems to dislike the inum table, it is necessary I think.
>
>
> J. R. Okajima

Only if you want to fully support hardlinks. Do you know of anything
that really needs true hardlinks?

MfG
        Goswin

Goswin von Brederlow:
> Only if you want to fully support hardlinks. Do you know of anything
> that really needs true hardlinks?

Do you expect me the name of an application in real world?
I don't know. But I believe when fileA and fileB are hardlinked, users
and applications expect they always provide same filedata.
If deltafs never support hardlink, then I will say nothing about it.


J. R. Okajima

Goswin von Brederlow:
> hooanon05@... writes:
	::
> > When a user writes something to the file after unlink+rmdir, where can
> > deltafs copyup? At least in the current implementation, there is no
> > place for it.
	:::
> In the delta branch create a meta/ and files/ directory. In the meta/
> directory you keep whiteout files and stat updates. In files/ you
> store only changes in the file data itself.
> 
> So "rm foo/bar/baz" will create meta/foo/bar/baz.whiteout. Then "echo
> blafase >>foo/bar/baz" first searches for a file to copy-up, sees the
> meta/foo/bar/baz.whiteout and knows the file was deleted. It then
> creates a new files/foo/bar/baz. It might have to copy-up foo and
> foo/bar for that though.

??
What I am pointing out is systemcall level operation instead of command
level.
In your example (or implementation approach), can deltafs successfully
operate "write(2) to and read(2) from foo/bar/baz" after "rm -r foo/bar"?

(from my previous mail)
----------------------------------------------------------------------
- open a file on deltafs
- unlink it
- rmdir its parent
- write or fchmod to it
- rewind+read or mmap+read from the opened file
- cat it be read correctly?
----------------------------------------------------------------------


J. R. Okajima

hooanon05@... writes:

> Goswin von Brederlow:
>> hooanon05@... writes:
> 	::
>> > When a user writes something to the file after unlink+rmdir, where can
>> > deltafs copyup? At least in the current implementation, there is no
>> > place for it.
> 	:::
>> In the delta branch create a meta/ and files/ directory. In the meta/
>> directory you keep whiteout files and stat updates. In files/ you
>> store only changes in the file data itself.
>> 
>> So "rm foo/bar/baz" will create meta/foo/bar/baz.whiteout. Then "echo
>> blafase >>foo/bar/baz" first searches for a file to copy-up, sees the
>> meta/foo/bar/baz.whiteout and knows the file was deleted. It then
>> creates a new files/foo/bar/baz. It might have to copy-up foo and
>> foo/bar for that though.
>
> ??
> What I am pointing out is systemcall level operation instead of command
> level.
> In your example (or implementation approach), can deltafs successfully
> operate "write(2) to and read(2) from foo/bar/baz" after "rm -r foo/bar"?
>
> (from my previous mail)
> ----------------------------------------------------------------------
> - open a file on deltafs
> - unlink it
> - rmdir its parent
> - write or fchmod to it
> - rewind+read or mmap+read from the opened file
> - cat it be read correctly?
> ----------------------------------------------------------------------
>
>
> J. R. Okajima

As I said, keep the FDs open. In case of the split meta/files dirs you
would have orig_fd, meta_fd and delta_fd. And make read/write operate
on fi->fh only, not the path to the file. That way the delta-fs will
operate like any other userspace program doing read/write after an
unlink.

MfG
        Goswin

hooanon05@... writes:

> Goswin von Brederlow:
>> Only if you want to fully support hardlinks. Do you know of anything
>> that really needs true hardlinks?
>
> Do you expect me the name of an application in real world?
> I don't know. But I believe when fileA and fileB are hardlinked, users
> and applications expect they always provide same filedata.
> If deltafs never support hardlink, then I will say nothing about it.
>
>
> J. R. Okajima

Only place I use hardlinks is between binaries in a debian package and
backups. In both cases they are totaly read-only and only a space
saver. Not so that changes to one file will also show up in the other.

I can't think of anything that would break if hardlinks would have a
copy-on-write/copy-up semantic in delta-fs.

MfG
        Goswin

Goswin von Brederlow:
> I can't think of anything that would break if hardlinks would have a
> copy-on-write/copy-up semantic in delta-fs.

What do you expect to the last "cat b"?
(from my old mail)
----------------------------------------------------------------------
Since you don't care the inum, the hardlink will not work correctly. For
instance,
$ cd /base
$ echo a > a
$ ln a b
$ cd /deltafs
$ echo a >> a
$ cat b
----------------------------------------------------------------------


J. R. Okajima

Goswin von Brederlow:
> As I said, keep the FDs open. In case of the split meta/files dirs you
> would have orig_fd, meta_fd and delta_fd. And make read/write operate

So your approach is that the files under meta/ and delta/ will be
created and opened in open(2) to deltafs...
While I am afraid it is not effective, I think I could understand your
approach.


J. R. Okajima

On Mon, 09 Mar 2009, Goswin von Brederlow wrote:
> hooanon05@... writes:
> 
> > Goswin von Brederlow:
> > (from my previous mail)
> > ----------------------------------------------------------------------
> > - open a file on deltafs
> > - unlink it
> > - rmdir its parent
> > - write or fchmod to it
> > - rewind+read or mmap+read from the opened file
> > - cat it be read correctly?
> > ----------------------------------------------------------------------
> >
> >
> > J. R. Okajima
> 
> As I said, keep the FDs open. In case of the split meta/files dirs you
> would have orig_fd, meta_fd and delta_fd. And make read/write operate
> on fi->fh only, not the path to the file. That way the delta-fs will
> operate like any other userspace program doing read/write after an
> unlink.

This is just an implementation detail.  In fact the current prototype
*does* support unlinked but still open files, but it does it
differently (with the help of the fuse library's hide-on-unlink
feature).

Miklos

Goswin von Brederlow <goswin-v-b@...> writes:
> hooanon05@... writes:
>
>> Goswin von Brederlow:
>>> > Miklos Szeredi:
>>> >> The most interesting is the directory and metadata deltas, which do
>>> >> make a delta-fs like implementation much more effective and nicer as a
>>> >> dumb union type filesystem.  Mind, unionfs and aufs are rapidly
>>> >> acquiring non-union traits, like inode number storage, virtual hard
>>> >> links (not to speak of whiteouts).  Which makes them all the more
>>> >> hackish, I much prefer a conceptually clean solution.
>> 	:::
>>> Use a filename -> inode indirection and delta based on inode
>>> numbers. Although the you also have to consider the device id in case
>>> there are multiple filesystem mounted in your read-only branch. So
>>> filename -> (dev, inode).
>>
>> Agreed.
>> While Miklos seems to dislike the inum table, it is necessary I think.
>
> Only if you want to fully support hardlinks. Do you know of anything
> that really needs true hardlinks?

storeBackup, for example (but I guess that's nothing you'd run on a
unionfs). 


Best,

   -Nikolaus

-- 
 »Time flies like an arrow, fruit flies like a Banana.«

  PGP fingerprint: 5B93 61F8 4EA2 E279 ABF6  02CF A9AD B7F8 AE4E 425C

hooanon05@... writes:

> Goswin von Brederlow:
>> I can't think of anything that would break if hardlinks would have a
>> copy-on-write/copy-up semantic in delta-fs.
>
> What do you expect to the last "cat b"?
> (from my old mail)
> ----------------------------------------------------------------------
> Since you don't care the inum, the hardlink will not work correctly. For
> instance,
> $ cd /base
> $ echo a > a
> $ ln a b
> $ cd /deltafs
> $ echo a >> a
> $ cat b
> ----------------------------------------------------------------------

The wrong thing, just 'a'. But the question remains: What software
breaks? I can live with this shortcomming.

MfG
        Goswin

hooanon05@... writes:

> Goswin von Brederlow:
>> As I said, keep the FDs open. In case of the split meta/files dirs you
>> would have orig_fd, meta_fd and delta_fd. And make read/write operate
>
> So your approach is that the files under meta/ and delta/ will be
> created and opened in open(2) to deltafs...
> While I am afraid it is not effective, I think I could understand your
> approach.
>
>
> J. R. Okajima

At a minimum I would open the file on the read-only branch unless the
file is already changed. You can create the meta/ and files/ FDs as
needed in any callback that modifies them. If the file is deleted at
that point you can create a dummy file and delete it while keeping the
FD. Just always creating the meta/ and files/ entries when a file is
opened for write seems simpler though and you need them anyway when
the first write call comes. If you track atime then you even need the
meta/ all the time.

But that is really justan implementation detail. It is how i would do it.

MfG
        Goswin

Goswin von Brederlow:
> The wrong thing, just 'a'. But the question remains: What software
> breaks? I can live with this shortcomming.

Then you won't meet the problem.


J. R. Okajima

> Goswin von Brederlow:
>> The wrong thing, just 'a'. But the question remains: What software
>> breaks? I can live with this shortcomming.

In my experience, KDE (3.x) always breaks if the filesystem it runs on doesn't support everything like hardlinks, and so on. It does a lot of tricky things with hardlinks.

Tomas M

Tomas M <tomas@...> writes:

>> Goswin von Brederlow:
>>> The wrong thing, just 'a'. But the question remains: What software
>>> breaks? I can live with this shortcomming.
>
> In my experience, KDE (3.x) always breaks if the filesystem it runs on doesn't support everything like hardlinks, and so on. It does a lot of tricky things with hardlinks.
>
> Tomas M

Works fine in unionfs-fuse without special hardlink fixing tricks.

MfG
        Goswin

> Goswin von Brederlow:
>> Only if you want to fully support hardlinks. Do you know of anything
>> that really needs true hardlinks?

A lot of KDE internals depend on real hardlinks ...


Tomas M