brtfs COW links and git

brtfs COW links and git

[Larry D'Anna]

I wish git could use COW links.  I wish I could put a large binary into git and
have the only underlying filesystem operation be to cp --reflink and to save the
metadata.  There are a few complications:

How does it know which files to reflink?  attributes?  a size limit?

What does git gc do with reflinks?

Should diff-delta be reflink-aware?  Perhaps it could query the fs for
blocklists.

Before I dive into implementing this, I'd like to get your comments and advice,
to maximize the chances of success.  

Thanks!

Re: brtfs COW links and git

[Jeff King]

On Sat, Mar 19, 2011 at 04:15:32PM -0400, Larry D'Anna wrote:

> I wish git could use COW links.  I wish I could put a large binary into git and
> have the only underlying filesystem operation be to cp --reflink and to save the
> metadata.  There are a few complications:

I have never used reflink, but my understanding is that the proposed
system call just lets us reflink one entire file. So basically the
useful points would be:

  1. on "git add", we could reflink the file into the object db

  2. on "git checkout", we could reflink the object into the working
     tree

The biggest stumbling block is that the object db does not currently
hold unadorned files. They have an object type and size header at the
beginning, and I believe even uncompressed files are stored with a zlib
header. So it would require a completely new section of the object db to
store these files (as opposed to the current loose objects and
packfiles).

Note also that during "git add" we will need to get the sha1 of the
data. So you'll still have to pull all the data from disk, though not
making a copy will save some space and time.

I'm not very knowledgeable on the current state of such things, but
is there any automatic de-duplication in btrfs? If so, does it depend on
data being at the same offsets within files?

> How does it know which files to reflink?  attributes?  a size limit?

Probably supporting both would make sense.

> What does git gc do with reflinks?

If we had a "giant literal blobs" section of the object database, we
would not want to pack those objects during a regular gc. It would kill
your reflink, but also there's just no point in copying some gigantic
file into a pack where it won't actually be delta-compressed.

> Should diff-delta be reflink-aware?  Perhaps it could query the fs for
> blocklists.

Wouldn't it just be sharing underlying data between the working tree and
the object database? How would that help us make deltas between objects?

> Before I dive into implementing this, I'd like to get your comments and advice,
> to maximize the chances of success.

I'm not exactly clear on what you want to implement.

-Peff

Re: brtfs COW links and git

[Larry D'Anna]

* Jeff King (peff@peff.net) [110321 08:00]:
> I'm not exactly clear on what you want to implement.

Neither was I, that's why I sent the vague email :-)

I think I have a better understanding now of what would need to be done:

* reading unadorned blobs, as a last resort if the object isn't found elsewhere.
  use reflink (if available) to copy an unadorned blob into the working directory 

* writing unadorned blobs, according to size limit / attribute.
  this also means computing the sha1 for the blob without reading
  the entire thing into memory all at once.

* leaving unadorned blobs alone in gc, unless explicitly told not to

* supporting the easy cases of binary diffs for git-upload-pack.  it shouldn't 
  have to send an entire copy of a huge file if only a little bit of the file 
  changed.   This could use fiemap, or maybe bup's rolling checksum, or maybe 
  either, depending on what's available.

* support for applying those binary diffs directly to the on-disk reflink.
  this could probably just mmap the file and call patch-delta.

I think these features would make some, but not all of the big file use cases
much more usable.  What do you think?

Re: brtfs COW links and git

[Jeff King]

On Mon, Mar 21, 2011 at 10:44:21PM -0400, Larry D'Anna wrote:

> * Jeff King (peff@peff.net) [110321 08:00]:
> > I'm not exactly clear on what you want to implement.
> 
> Neither was I, that's why I sent the vague email :-)

Fair enough. :)

> I think I have a better understanding now of what would need to be done:
> 
> * reading unadorned blobs, as a last resort if the object isn't found elsewhere.
>   use reflink (if available) to copy an unadorned blob into the working directory 
> 
> * writing unadorned blobs, according to size limit / attribute.
>   this also means computing the sha1 for the blob without reading
>   the entire thing into memory all at once.
> 
> * leaving unadorned blobs alone in gc, unless explicitly told not to

Yeah, all of these are sensible. I do get a little nervous because an
extra object-db area is a change to such a core part of git. I think the
performance improvement would have to be pretty impressive to be worth
the trouble (and I think it has the potential to be; I just think you
will need numbers to make this palatable for upstream inclusion).

You could also prototype it with something like git-media that is
external to git. If you haven't read this recent thread, take a look:

  http://thread.gmane.org/gmane.comp.version-control.git/165389/focus=165389

> * supporting the easy cases of binary diffs for git-upload-pack.  it shouldn't 
>   have to send an entire copy of a huge file if only a little bit of the file 
>   changed.   This could use fiemap, or maybe bup's rolling checksum, or maybe 
>   either, depending on what's available.

The good news is that we already handle binary diffs in upload-pack via
deltas. The trick is just efficiently generating them for large files.
If you have two large objects which are sharing blocks, one block is a
delta candidate for the other (i.e., the remote has told you he has one
but needs the other), and you have fiemap support on the sending end,
then you should be able to efficiently generate a delta on the fly.

In practice, I don't know how useful that is. One of the killer
applications people want for this kind of support is for media files.
But when they change, they tend to change a lot. I don't know if deltas
between two versions of an audio or video file will really be useful.
But that isn't to say it won't help for some other files. I think part
of showing good numbers would be defining a plausible workload.

> * support for applying those binary diffs directly to the on-disk reflink.
>   this could probably just mmap the file and call patch-delta.

The patch may need to expand a section in the middle of the file. I
don't know what kind of syscall support there is for that level of
tweaking with reflinked files.

> I think these features would make some, but not all of the big file use cases
> much more usable.  What do you think?

I think they could help, especially for gigantic files where just
copying the file is painful, and the extra storage kills you. But there
are a lot of other issues, too, like git assuming it can pull whole
blobs into memory during diffs. There is some low-hanging fruit there,
and that's why I put forward the SoC project idea.

-Peff