[PATCH] [RFC] Generational repacking

[PATCH] [RFC] Generational repacking

[Sam Vilain]

This is a quick hack at generational repacking.  The idea is that you
successively do larger repack runs as the number of packs accumulates.

The commandline interface for this should be considered development
grade only, and of course there are no tests and very verbose output
:)

The useful invocation of this is git-repack -d -g

The -a option then becomes a degenerate case of generative repacking.

The intention is that this should end up light enough to be triggered
automatically whenever the (approximate) count of loose objects hits a
threshold, like 100 or 1000 - making git repositories "maintenance
free".
---
 git-repack.sh |   79 ++++++++++++++++++++++++++++++++++++++++++++++++--------
 1 files changed, 67 insertions(+), 12 deletions(-)

diff --git a/git-repack.sh b/git-repack.sh
index 8c32724..b26ca2a 100755
--- a/git-repack.sh
+++ b/git-repack.sh
@@ -3,19 +3,21 @@
 # Copyright (c) 2005 Linus Torvalds
 #
 
-USAGE='[-a] [-d] [-f] [-l] [-n] [-q] [--max-pack-size=N] [--window=N] [--depth=N]'
+USAGE='[-a] [-d] [-f] [-l] [-n] [-q] [-g] [--max-pack-size=N] [--window=N] [--depth=N]'
 SUBDIRECTORY_OK='Yes'
 . git-sh-setup
 
-no_update_info= all_into_one= remove_redundant=
-local= quiet= no_reuse= extra=
+no_update_info= generations= remove_redundant=
+local= quiet= no_reuse= extra= generation_width=
 while case "$#" in 0) break ;; esac
 do
 	case "$1" in
 	-n)	no_update_info=t ;;
-	-a)	all_into_one=t ;;
+	-a)	generations=0 ;;
 	-d)	remove_redundant=t ;;
 	-q)	quiet=-q ;;
+	-g)	generations=3 generation_width=10 ;;
+	-G)	generations=$2; generation_width=5; shift ;;
 	-f)	no_reuse=--no-reuse-object ;;
 	-l)	local=--local ;;
 	--max-pack-size=*) extra="$extra $1" ;;
@@ -40,24 +42,74 @@ PACKTMP="$GIT_OBJECT_DIRECTORY/.tmp-$$-pack"
 rm -f "$PACKTMP"-*
 trap 'rm -f "$PACKTMP"-*' 0 1 2 3 15
 
+generation=
+redundant=
+
 # There will be more repacking strategies to come...
-case ",$all_into_one," in
+case ",$generations," in
 ,,)
 	args='--unpacked --incremental'
 	;;
-,t,)
+,*,)
 	if [ -d "$PACKDIR" ]; then
+		max_gen=0
+		echo "Scanning for packs... generations: $generations, generation_width: $generation_width"
 		for e in `cd "$PACKDIR" && find . -type f -name '*.pack' \
 			| sed -e 's/^\.\///' -e 's/\.pack$//'`
 		do
+			echo -n "what about $e ? "
 			if [ -e "$PACKDIR/$e.keep" ]; then
 				: keep
+				echo "keep it - .keep exists"
 			else
-				args="$args --unpacked=$e.pack"
 				existing="$existing $e"
+				if [ -e "$PACKDIR/$e.gen" ]; then
+					gen=`cat $PACKDIR/$e.gen`
+				else
+					echo -n "assuming "
+					gen=1
+				fi
+				echo "generation $gen"
+				[ "$max_gen" -lt $gen ] && max_gen=$gen
+				eval "gen_${gen}=\"\$gen_${gen} $e\"";
+				eval "c_gen_${gen}=\$((\$c_gen_${gen} + 1))";
 			fi
 		done
+		i=$max_gen
+		packing=
+		while [ $i -gt 0 ]
+		do
+			c_gen=`eval "echo \\\$c_gen_$i"`
+			packs=`eval "echo \\\$gen_$i"`
+			if [ -n "$c_gen" -a $i -gt "$generations" ]
+			then
+				echo "saw $c_gen packs at generation $i"
+				echo "therefore, repacking everything"
+				packing=1
+				[ -z "$generation" ] && generation=$(($i + 1))
+			elif [ -n "$c_gen" -a "$c_gen" -ge "$generation_width" -a "$i" -lt "$generations" ]
+			then
+				echo -n "generation $i has too many packs "
+				echo "($c_gen >= $generation_width)"
+				echo "repacking at this level and below"
+				packing=1
+				[ -z "$generation" ] && generation=$(($i + 1))
+			fi
+			if [ -n "$packing" ]
+			then
+				for x in $packs; do
+					args="$args --unpacked=$x.pack"
+					redundant="$redundant $x"
+				done
+			fi
+			i=$(($i - 1))
+		done
+		if [ -n "$generation" ]; then
+			[ "$generation" -gt "$generations" ] && generation=$generations
+			[ "$generation" -eq 0 ] && generation=1
+		fi
 	fi
+
 	[ -z "$args" ] && args='--unpacked --incremental'
 	;;
 esac
@@ -95,20 +147,23 @@ for name in $names ; do
 		exit 1
 	}
 	rm -f "$PACKDIR/old-pack-$name.pack" "$PACKDIR/old-pack-$name.idx"
+	[ -n "$generation" ] && echo $generation > "$PACKDIR/pack-$name.gen"
 done
 
 if test "$remove_redundant" = t
 then
-	# We know $existing are all redundant.
-	if [ -n "$existing" ]
+    	echo "removing redundant packs"
+	# We know $redundant are all redundant.
+	if [ -n "$redundant" ]
 	then
 		sync
 		( cd "$PACKDIR" &&
-		  for e in $existing
+		  for e in $redundant
 		  do
 			case " $fullbases " in
-			*" $e "*) ;;
-			*)	rm -f "$e.pack" "$e.idx" "$e.keep" ;;
+			*" $e "*) echo "ignoring $e" ;;
+			*)	echo "removing $e.pack etc";
+				rm -f "$e.pack" "$e.idx" "$e.keep" ;;
 			esac
 		  done
 		)
-- 
1.5.2.0.45.gfea6d-dirty

Re: [PATCH] [RFC] Generational repacking

[Junio C Hamano]

Sam Vilain <sam.vilain@catalyst.net.nz> writes:

> +			c_gen=`eval "echo \\\$c_gen_$i"`
> +			packs=`eval "echo \\\$gen_$i"`

I used to write something like these myself when I was young
;-), but it is enough to write:

	eval 'c_gen=$c_gen_'$i
	eval "packs=\$gen_$i"

Re: [PATCH] [RFC] Generational repacking

[Sam Vilain]

Junio C Hamano wrote:
> Sam Vilain <sam.vilain@catalyst.net.nz> writes:
>   
>> +			c_gen=`eval "echo \\\$c_gen_$i"`
>> +			packs=`eval "echo \\\$gen_$i"`
>>     
>
> I used to write something like these myself when I was young
> ;-), but it is enough to write:
>
> 	eval 'c_gen=$c_gen_'$i
> 	eval "packs=\$gen_$i"
>   

Would've re-written it in Perl ages ago :P

Sam.

Re: [PATCH] [RFC] Generational repacking

[Dana How]

On 6/6/07, Sam Vilain <sam.vilain@catalyst.net.nz> wrote:
> This is a quick hack at generational repacking.  The idea is that you
> successively do larger repack runs as the number of packs accumulates.
>
> The commandline interface for this should be considered development
> grade only, and of course there are no tests and very verbose output
> :)
>
> The useful invocation of this is git-repack -d -g
>
> The -a option then becomes a degenerate case of generative repacking.
>
> The intention is that this should end up light enough to be triggered
> automatically whenever the (approximate) count of loose objects hits a
> threshold, like 100 or 1000 - making git repositories "maintenance
> free".

This patch complicates git-repack.sh quite a bit and
I'm unclear on what _problem_ you're addressing.
The recent LRU preferred pack patch
reduces much of the value in keeping a repository tidy
("tidy" == "few pack files").

Already git-gc calls git-repack -a -d.  How do you plan to change this?
I wonder if you should be making git-gc more intelligent instead.

Also,  you introduce a new pack properties file (.gen) which seems
awkward to me.

Perhaps something like this would be useful on a huge repository
under active use.  But delta re-use makes full repacking quite quick for
a reasonably-sized repository already,  and I don't see this being very useful
for a repository which is large due to large objects.

Thanks,
-- 
Dana L. How  danahow@gmail.com  +1 650 804 5991 cell

Re: [PATCH] [RFC] Generational repacking

[Sam Vilain]

Dana How wrote:
> This patch complicates git-repack.sh quite a bit and
> I'm unclear on what _problem_ you're addressing.

The problem is simple, and it is partially in the eye of the beholder.

That is;

  1. without repacking, you get a lot of loose objects.
     - unnecessary disk space usage
     - bad performance on many OSes

  2. repack takes too long to run very regularly; it's an occasional
     command.

  3. the perception that git repositories are not maintenance free.

What I'm aiming for is something which is light enough that it might
even win back the performance loss you got from 1), and to solve the
perception problem of 3).

Much as users who don't like automatic database maintenance turn it off
and run it at the best time, advanced git users will want to disable
this feature in ~/.gitrc and run repack themselves when it suits them,
or via cron or whatever.  Or it's disabled by default and users that
whine get told to turn it on, it really doesn't matter.  I can already
do it with a commit hook, so I'm quite happy.

> The recent LRU preferred pack patch
> reduces much of the value in keeping a repository tidy
> ("tidy" == "few pack files").

Great, that is a good thing.

Pack files are an almost indistinguishable concept from database
partitions.  In terms of that, scaling problems with lots of partitions
can be managed, certainly.

For instance with database partitioning you would expect your query
planner (in this case, read_packed_sha1()) to be able to select the
right partition (pack) to go to first to avoid excessive index lookups.
 That a strategy for picking the best pack quickly N% of the time exists
for git is an excellent measure to reduce the impact of a large number
of pack files.  I think you would probably find measurable wins by
ensuring that the gross number of packs is kept limited.

Consider that I'm thinking of running this generational repack somewhere
such as a commit hook, if it found >100 loose objects, so that the first
generation repack is very quick and doesn't annoy me - and the second
generation will similarly be fairly quick as many deltas will already be
computed.  The exact behaviour will probably require tuning to get a
good balance between good delta computation and minimal interruption to
commit flow.  Someone on IRC floated the idea of making the first
generation do no delta computation to make it lightning fast.

Note that if you had 3 pack generations, only the first two levels will
ever be repacked - you'll end up with an unlimited number of third
generation packs, which will also end up in LRP* order.

> Already git-gc calls git-repack -a -d.  How do you plan to change this?
> I wonder if you should be making git-gc more intelligent instead.
> 
> Also,  you introduce a new pack properties file (.gen) which seems
> awkward to me.

This implementation is a simple demonstration of the logic which was
designed to communicate the idea and stimulate discussion.  I think the
logic could probably go elsewhere too, and yes the new file is a bit of
a hack.

It might be better to base the "generation" assessment of the file on
the actual size of the pack, for instance - ie, Instead of the number of
loose objects, the size of the loose objects, call 1st generation = <1MB
pack, 2nd generation = <5MB, etc.  When the combined size of 1st
generation packs gets above 5MB then that generation is full and a new
2nd generation pack is made.  Then no state file is required.

> Perhaps something like this would be useful on a huge repository
> under active use.  But delta re-use makes full repacking quite quick for
> a reasonably-sized repository already,  and I don't see this being very useful
> for a repository which is large due to large objects.

I agree with your point of view, however I think if the feature is out
there but disabled by default then this can be found through experience.
 As you can see all of the elements to implement it are already there -
and as you mention, combining packs is already quick.

Sam.

* Last Recently Packed ;)

Re: [PATCH] [RFC] Generational repacking

[Nicolas Pitre]

On Thu, 7 Jun 2007, Sam Vilain wrote:

> Dana How wrote:
> > This patch complicates git-repack.sh quite a bit and
> > I'm unclear on what _problem_ you're addressing.
> 
> The problem is simple, and it is partially in the eye of the beholder.
> 
> That is;
> 
>   1. without repacking, you get a lot of loose objects.
>      - unnecessary disk space usage
>      - bad performance on many OSes

No argument.

>   2. repack takes too long to run very regularly; it's an occasional
>      command.

It doesn't take long at all when you don't use -a.

>   3. the perception that git repositories are not maintenance free.

But this perception is true!  It is possible to automate it, but some 
maintenance is necessary at some point.

> What I'm aiming for is something which is light enough that it might
> even win back the performance loss you got from 1), and to solve the
> perception problem of 3).

Run git-repack without -a from some hook.  You can even launch it in the 
background.

Or what am I missing?


Nicolas

Re: [PATCH] [RFC] Generational repacking

[Sam Vilain]

Nicolas Pitre wrote:
>>   2. repack takes too long to run very regularly; it's an occasional
>>      command.
> It doesn't take long at all when you don't use -a.

Well that depends how many loose objects there are :)  I heard about on
Windows a case where packing 30k loose objects took over an hour.

>> What I'm aiming for is something which is light enough that it might
>> even win back the performance loss you got from 1), and to solve the
>> perception problem of 3).
> 
> Run git-repack without -a from some hook.  You can even launch it in the 
> background.
> 
> Or what am I missing?

If you repack every 100 objects without -a, sure it will be fast, but
you'll end up with too many packs.

Sam.

Re: [PATCH] [RFC] Generational repacking

[Nicolas Pitre]

On Thu, 7 Jun 2007, Sam Vilain wrote:

> Nicolas Pitre wrote:
> >>   2. repack takes too long to run very regularly; it's an occasional
> >>      command.
> > It doesn't take long at all when you don't use -a.
> 
> Well that depends how many loose objects there are :)  I heard about on
> Windows a case where packing 30k loose objects took over an hour.

And your patch cannot change anything to that, right?
You shouldn't wait until 30k loose objects accumulate before repacking.

> >> What I'm aiming for is something which is light enough that it might
> >> even win back the performance loss you got from 1), and to solve the
> >> perception problem of 3).
> > 
> > Run git-repack without -a from some hook.  You can even launch it in the 
> > background.
> > 
> > Or what am I missing?
> 
> If you repack every 100 objects without -a, sure it will be fast, but
> you'll end up with too many packs.

You just need to adjust this treshold of 100 objects.

And latest GIT behaves _much_ better with lots of packs, almost like if 
there was only one pack.  See the test results I posted to the list.


Nicolas

Re: [PATCH] [RFC] Generational repacking

[Sam Vilain]

Nicolas Pitre wrote:
> >> Well that depends how many loose objects there are :)  I heard about on
>> Windows a case where packing 30k loose objects took over an hour.
> > And your patch cannot change anything to that, right?
> You shouldn't wait until 30k loose objects accumulate before repacking.

Absolutely.  But the generational approach would make it practical to
repack very often, in fact automatically, and keep the time of that
repack reasonably bounded.  As I said in the original patch, the
intention is that this style of repacking works best when applied
automatically, perhaps on commit.

>> If you repack every 100 objects without -a, sure it will be fast, but
>> you'll end up with too many packs.
> You just need to adjust this treshold of 100 objects.
> And latest GIT behaves _much_ better with lots of packs, almost like if 
> there was only one pack.  See the test results I posted to the list.

The test run with 66 packs?  What about a repository with 300000 objects
that was repacked every 100 new objects, would it work well with with
3000 packs?  Surely there is some value in conglomerating older packs,
even though your LRU patch might make it very small (which I do find
impressive).  Do you really need me to prove this with a benchmark?

"Adjust the threshold" you have already said.  But the problem with that
is what to?  I want the automatic repack to be *fast*.  So making it
larger will make it slower.  But making it too small will make the packs
excessive.

Sam.

Re: [PATCH] [RFC] Generational repacking

[Martin Langhoff]

On 6/7/07, Nicolas Pitre <nico@cam.org> wrote:
> Run git-repack without -a from some hook.  You can even launch it in the
> background.

I posted an RFC patch a while ago doing exactly that, and Linus shot
it down, indicating we should instead print a message suggesting
repack to the user.

Relevant thread around
http://www.gelato.unsw.edu.au/archives/git/0606/22977.html

> Or what am I missing?

I don't think people were comfortable at the time with concurrent
repacks -- though the semantics are safe if we don't hit any bug. My
guess is that noone wants to risk the .001% chances of data corruption
for this nice-to-have.

It was also probably a bad idea in my patch that it said -a -- it should just be

  git repack -l -q &

[And I generally agree with the concerns about possibly broken
semantics, unexpected user actions and racing repacks. One of the main
reasons I've never advocated SVN is that the early stories of data
corruption using BDB backends made me very very very wary of it.
Perhaps because I lot months of work in the past to disk corruption in
a cvs repo, and have a good mental picture of the nervous breakdown
that followed.]

cheers,


m

Re: [PATCH] [RFC] Generational repacking

[Sam Vilain]

Martin Langhoff wrote:
> On 6/7/07, Nicolas Pitre <nico@cam.org> wrote:
>> Run git-repack without -a from some hook.  You can even launch it in the
>> background.
> 
> I posted an RFC patch a while ago doing exactly that, and Linus shot
> it down, indicating we should instead print a message suggesting
> repack to the user.
> 
> Relevant thread around
> http://www.gelato.unsw.edu.au/archives/git/0606/22977.html
> 
>> Or what am I missing?
> 
> I don't think people were comfortable at the time with concurrent
> repacks -- though the semantics are safe if we don't hit any bug. My
> guess is that noone wants to risk the .001% chances of data corruption
> for this nice-to-have.

Ok.  But if repack is generational you probably don't mind waiting for
it on commit so don't need to background it.

Sam.

Re: [PATCH] [RFC] Generational repacking

[Martin Langhoff]

On 6/8/07, Sam Vilain <sam@vilain.net> wrote:
> Ok.  But if repack is generational you probably don't mind waiting for
> it on commit so don't need to background it.

Agreed. The patch I posted back then was on fetch as a signle fetch is
more likely to bring a lot of new objects in. (Moreso than a commit)

Repack-on-commit if there's more than 1k unpacked objects makes sense.
Are fetches nowaways always using the "keep pack" and "fatten thin
pack" semantics? If yes, then

cheers,



martin

Re: [PATCH] [RFC] Generational repacking

[Nicolas Pitre]

On Wed, 6 Jun 2007, Dana How wrote:

> On 6/6/07, Sam Vilain <sam.vilain@catalyst.net.nz> wrote:
> > This is a quick hack at generational repacking.  The idea is that you
> > successively do larger repack runs as the number of packs accumulates.
> > 
> This patch complicates git-repack.sh quite a bit and
> I'm unclear on what _problem_ you're addressing.
> The recent LRU preferred pack patch
> reduces much of the value in keeping a repository tidy
> ("tidy" == "few pack files").
[...]

For the record... I didn't comment on this patch because I couldn't 
form 
a clear opinion about it.

But until its usefulness can be demonstrated I should side with Dana 
here.


Nicolas