> "There is a lot more to this, but I'll stop there."

Go on with your explanation. I'm not grokking it yet.

Does my response to jganetsk help at all?

For the record, I found the explanation sufficient to make me understand and interest me, but I'm not qualified to assess HashFold w.r.t. MapReduce. Keep writing and keep us (on HN) updated.

Yes it does thank you.

Does the local folding process all inputs, or only those inputs whose keys would end up being local to the node?

Both. First it does a local fold on local inputs, then it does a global fold across all of the local fold results.

i.e. Assume we have three nodes and one key, "our_key", and values for "our_key" are distributed across the 3 nodes:

node1 : our_key : [ 1, 2, 3, 4, 5]

node2 : our_key : [ 6, 7, 8, 9, 10]

node3 : out_key : [11, 12, 13, 14, 15]

and our fold function ( which must be associative) is +. First we fold each node:

node1 : fold(+, [ 1, 2, 3, 4, 5]) = our_key : [15]

node2 : fold(+, [ 6, 7, 8, 9, 10]) = our_key : [40]

node3 : fold(+, [11, 12, 13, 14, 15]) = our_key : [65]

When each node is done with its local inputs, the key-value pairs are redistributed so that each key and its values are on a single node. In this case, assume our hash function moved "our_key" to node 2. Node 2 would now have:

node2 : our_key : [15, 40, 65]

And we would fold against that and get:

node2: our_key : 120

This is how we achieve massive scalability. The nodes can do all of their processing in parallel without any intercommunication except for the key-redistribution phase.

Two key things to point out are that HashFold does the folding as the data becomes available (we don't wait for all values to start folding... this reduces memory usage because we don't need to store the list of values, only the result of the fold as it progresses), and the framework described here is sufficient to perform any computation that MapReduce can do which should make the transition easier (as a lot of major data processing tasks are currently framed for MapReduce)

How do you build the hash table at the first place? "We look up the key in the hash table and get a value (referred to as v2)."

Do you know Haskell a bit? Try to write your examples in real Haskell, a friendly type system helps a lot to clean up your pseudo-code.

Think of the hashtable as a defaultdict or the fold as having an initial value for when the key doesn't have a value yet.

Sure, but what value is it?

Ah, that would be specific to the job. If your doing a sum, maybe 0, or if you're building a list, it'd be an empty list. I suspect that a good default would just be whatever the first value generated by the mapper is, in which case the first value of any key wouldn't be folded, but rather just set in the hash table. But that is all job specific. If you can recommend a better solution, I'm all ears.

Furthermore, I should have explained the types better. As described, the HashFold framework would require the output of the map, the arguments of the fold, and the output of the fold all be the same type. This isn't as limiting as it sounds and if it turns out to be limiting for some problem domains, there are solutions to each of those.

Thanks, that makes sense.

do you have any code to play with?

Here ( http://files.getdropbox.com/u/196807/peaktraffic.tgz ) is a proof of concept of HashFold that I used for my solution for the facebook puzzle ( http://www.facebook.com/careers/puzzles.php?puzzle_id=8 ).

It's written in python. You can run it with './peaktraffic input'. It has 5 different use cases for HashFold: a counter, two different filters, an adjacency list builder, and a cluster finder. The README explains the solution, but does so in terms of MapReduce.

This code wasn't written with the intent of public consumption, so take it as you may.

Any questions, let me know.