[gentoo-scm] Git Validation - Update

[Rich Freeman]

I got my git walker working under hadoop / starcluster on EC2.  Sources are at:
git://github.com/rich0/gitvalidate.git

It can run fine serially from the shell - edit parestrees.py and
maptree.py to fix the hard-coded path to the git repo.  Parsetrees.py
takes as an option how far down the tree to go - just enter a number >
1.3M or so to get the whole thing, or less if you just want to test
it.  The output of that is the input to maptree.py.  The output of
maptree.py needs sorting, and then is the input to reducetree.py.

This is an iterative algorithm, and I found about 12 rounds were
needed.  The first three are quite slow, and after that you're only
really traversing the profiles which goes pretty fast.  You can do it
all at once with a big pipe parse | map | sort | reduce | map | sort |
reduce, but as the number of commits included grows you'll need lots
of temp space for the sorting.

You can run that under hadoop with the streaming module.  I ran it on
ec2 with 6 m1.large instances and got through it all in about 2.5
hours or so.  The first 2 rounds took over an hour each, after that it
went pretty fast.  That algorithm should parallelize up to maybe
10-100k nodes, so it can run arbitrarily fast.  The downside to hadoop
is the hassle of getting that working, and that you need to move the
1+GB git repository over to your cluster (which isn't terribly fast in
my case - even with FIOS and EC2).  That is a fixed overhead we really
can't do much about.

I'm going to set aside the git part of the problem for now as that is
just optimization.  Next steps would be to find some easy way to run
that in parallel without hadoop.  For anybody interested in taking a
whack at that, you can chop up the input at line boundaries and run
the map steps as parallel as you want to.  You then need to cat/sort
the output of all the maps.  Then the output of that can be split
going into the reduce step, but you have to keep lines with the same
key together (the first tab-delimited column).  I think I could
probably do that on the cheap with some bash scripting and gnu
parallel - just set up temp dirs for input/output and dump every job
into a separate file.  I suspect that Hadoop will be hard to beat if
you want to cluster it, but for a single node you could make it a lot
simpler.

Next step is to get cvs into a similar format.  My initial thoughts:

1.  Just run cvs log in the root, chop it up at file boundaries,
base64 encode each blob, and dump that into a text file one file per
line.
2.  Distribute processing of each file, turning it into one line per
commit with all the info my git program dumps, save the file hash.
3.  Distribute reading those lines, checking out that one version of
one file, calculating the hash, and outputting the full info.

Steps 1/2 might be cheaper to just combine since you have to scan the
whole thing to chop it up and the parsing can't be THAT expensive.

If there are libs to make any of this easier I'm all ears, but it
seems like there isn't much out there - nothing like pygit2.

Once I have both I can start working on validation rules and perhaps
get feedback to the conversion team.  We'll need to work out what does
and doesn't count as OK.  We're doing transformation of data during
migration, so I need to take that into account.  Either the logic goes
into the compare function, or the logic goes into the dump side so
that the compares work out the same.  Timestamps might force us to do
logic during compare anyway.

So, that's all for now.  If anybody wants my notes for running hadoop
let me know - maybe I'll digest those and make it into a blog entry.
However, it would be worthwhile to see if we can ditch hadoop.  If we
are stuck with it then we can probably get the time down to 30min with
< 100 nodes.

Rich