threads / rfc / 8469

patch[RFC] Generational repacking

Subject: [PATCH] [RFC] Generational repacking

## tl;dr

13 messages between Jun 6, 2007 and Jun 7, 2007. Diffs are folded; open one to read it.

replies: 12people: 5as markdown or json

Sam Vilain· Jun 6, 2007, 11:08 UTC · lore

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(-)
Show changes to git-repack.sh +67 −12
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
Junio C Hamano· Jun 6, 2007, 22:46 UTC · re: Sam Vilain · lore

Re: [PATCH] [RFC] Generational repacking

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"
Sam Vilain· Jun 6, 2007, 22:53 UTC · re: Junio C Hamano · lore

Re: [PATCH] [RFC] Generational repacking

Junio C Hamano wrote:
Show 12 quoted lines
> 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.
Dana How· Jun 7, 2007, 00:04 UTC · re: Sam Vilain · lore

Re: [PATCH] [RFC] Generational repacking

On 6/6/07, Sam Vilain <sam.vilain@catalyst.net.nz> wrote:
Show 15 quoted lines
> 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
Sam Vilain· Jun 7, 2007, 02:28 UTC · re: Dana How · lore

Re: [PATCH] [RFC] Generational repacking

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.

Show 5 quoted lines
> 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 ;)
Nicolas Pitre· Jun 7, 2007, 03:20 UTC · re: Sam Vilain · lore

Re: [PATCH] [RFC] Generational repacking

On Thu, 7 Jun 2007, Sam Vilain wrote:
Show 11 quoted lines
> 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
Sam Vilain· Jun 7, 2007, 05:13 UTC · re: Nicolas Pitre · lore

Re: [PATCH] [RFC] Generational repacking

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.

Show 8 quoted lines
>> 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.
Nicolas Pitre· Jun 7, 2007, 13:38 UTC · re: Sam Vilain · lore

Re: [PATCH] [RFC] Generational repacking

On Thu, 7 Jun 2007, Sam Vilain wrote:
Show 7 quoted lines
> 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.

Show 11 quoted lines
> >> 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
Sam Vilain· Jun 7, 2007, 21:29 UTC · re: Nicolas Pitre · lore

Re: [PATCH] [RFC] Generational repacking

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.

Show 5 quoted lines
>> 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.
Martin Langhoff· Jun 7, 2007, 19:46 UTC · re: Nicolas Pitre · lore

Re: [PATCH] [RFC] Generational repacking

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
Sam Vilain· Jun 7, 2007, 21:36 UTC · re: Martin Langhoff · lore

Re: [PATCH] [RFC] Generational repacking

Martin Langhoff wrote:
Show 17 quoted lines
> 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.
Martin Langhoff· Jun 7, 2007, 22:51 UTC · re: Sam Vilain · lore

Re: [PATCH] [RFC] Generational repacking

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
Nicolas Pitre· Jun 7, 2007, 03:05 UTC · re: Dana How · lore

Re: [PATCH] [RFC] Generational repacking

On Wed, 6 Jun 2007, Dana How wrote:
Show 9 quoted lines
> 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

← back to recent threads