[rfc] git: combo-blobs

[Ingo Molnar <mingo@elte.hu>]

i think all of the 'repository size' and 'bandwidth' concerns could be 
solved via a new (and pretty much simple and transparent) object type: 
the 'combo-blob'.

Summary:
--------

This is a space/bandwidth-efficient blob that 'includes' arbitrary 
portions of (one, two, or more) simple blobs by reference [1], with byte 
granularity, plus an optional followup portion that includes the full 
constructed state, uncompressed. [2] It can also conserve more RAM 
compared to the current repository format.

Representation:
---------------

A combo-blob would have the 'simplest possible' and thus most obvious 
representation: a list (the 'include-table') of "include X bytes at 
offset Y from parent Z" operations:

  <parent-blob-ID> <offset> <size>
  [optional full constructed state]

e.g.:

  6d11b2dd7f169c29664ac0553090865b7b020973 0 64444
  6d374c972c04a0b1894cc6898dffa8ab0b273fcb 0 100
  6d11b2dd7f169c29664ac0553090865b7b020973 64545 163656

'punches' 100 bytes out of blob 6d1* at offset 64444, and replaces it 
with blob 6d3*'s 100 bytes. [offset/size would be stored in a binary 
form to have constant record sizes.]

in OS terms it's similar to an iovec representation. [3]

The hash of a combo-blob is calculated off the include-table alone: i.e.  
it's _not_ equivalent to the hash of the included contents. I.e. you 
cannot 'collapse' a combo-blob after the fact, it's an immutable part of
the history of the repository, similar to other stored objects. You can
freely cache/uncache (blow-up/collapse) it on the other hand.

[ NOTE: further below you can find a 'Notes' section as well, which
  might address some of the issues/ideas you might have at this point. ]

Cons:
-----

there are a number of disadvantages:

- performance hit. Linus is perfectly right, in terms of performance, 
  nothing beats having full objects.

  Hence i kept the option to include the full constructed blob [4]
  (uncompressed) as well in the combo-blob. When all combo-blobs are
  'blown up' then they can be better in terms of performance than the 
  current repository format. [they still carry the small slice & dice
  information as well]

  the performance hit can be reduced in a finegrained way by introducing 
  occasional full objects in the history. E.g. after every 8 steps one
  would include a full blob, to limit the number of blobs necessary to
  construct a previously unconstructed combo-blob. This would still cut
  the overhead of the current format substantially.

  clearly, the most important cache is the current directory cache, 
  which this abstraction does not hurt.

- complexity. It's all pretty straightforward, but checking the
  consistency of a combo object is not as simple as checking the 
  consistency of a simple object, as it would have to recursively check 
  all parent IDs as well. I think it's worth the price though.

- repository has optional components: the 'blown up' (cached) portion of 
  a combo-blob can be freely destructed. This means that two 
  repositories can now not only differ in their directory-cache, but 
  also in their objects/ hierarchy. I dont think this is a big issue, 
  BYMMV.

Pros:
-----

- the main advantage is space/bandwith: it's pretty much as efficient as 
  it gets: it can be used to represent compressed binary deltas. A fully 
  trimmed (uncached) repository is very efficient.

- the optional 'fully constructed' portion is not compressed, so once a
  repository is 'cached', it is faster to process (in areas outside the
  current directory cache) than the current repository format. (In fact,
  when a previously unused portion of a repository is accessed _first_, 
  it is IO-bound by nature - so we can very well spend the extra CPU
  cycles on uncompressing things.)

- a 'combo' blob will be more memory-efficient as well. So with given 
  amount of RAM one could access more history, with a small CPU cost - 
  as long as the level of 'history recursion' is kept in check (e.g. via 
  the previously mentioned 'at most 8-deep combinations').  
  Straightforward iovecs could be passed to Linux system-calls, when 
  constructing a 'view' of a file, without having to cache every step of 
  the file's history.

- a combo-blob directly represents the way humans code: combining 
  pre-existing pieces of information and adding relatively low amount of 
  new stuff. Having a natural representation for the type of activity 
  that a tool supports cannot hurt.

( - combo-blobs enable a per-chunk (or per-line) edit history. It's not
    an important feature though.  )

Notes:
------

[1] the combo-blob is not a 'delta' thing. It combines pre-existing 
parents. One of the parents may of course be a 'delta' that acts upon 
the other parent - but the combo-blob does not know and does not care.  
(A combo-blob might as well represent an act of someone consolidating 
multiple small files into a big file, or splitting up a big file into 
smaller files. Or a combo-blob might represent the trimming of a 
preexisting file.)

[2]: a combo-blob is conceptually still a simple object with blob data 
in it, nothing more. It can be referenced in other object types 
equivalently to other blobs. It just happens to be a combination of 
existing blobs, and hence the 'git filesystem' has to work harder (but 
still quite efficiently) to get to the contents.

[3]: a combo-blob might reference any parent blob, including combo 
blobs. This means that e.g. multiple small deltas can be represented 
via:

   <blob-#1>
      |
      |-----<blob-#2>
      |
   <combo-blob-#1>
      |
      |-----<blob-#3>
      |
   <combo-blob-#2>

where combo-blob-#2 is thus a combination of blob-#1,blob-#2,blob-#3.

[4] alternatively, it might also make sense to extend the simple 
combo-blob concept with the concept of a 'cache-blob': a cache-blob 
'blows up' combo blobs in that it fully constructs the blob contents, 
but it is otherwise identical to the blob it caches. Simple (non-combo) 
blob types are a cache of themselves.

	Ingo
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/