Generic map/reduce

[caolan]

The idea is to add a generic map/reduce API that supports incremental updates by persisting intermediary reducer output alongside tree nodes.

Persisting intermediate results is important when 'forking' a remote hyperbee - as to recalculate the reducer output from scratch would require fetching the whole tree, breaking hyperbee's lightweight fork model.

However, exchanging intermediate reducer output presents some challenges. The output is only useful in combination with the code that produced it (at least for writes). This requires either shipping the code (like couchdb) and running it in a sandbox, or introducing some kind of versioning so programs consuming intermediate reducer output can determine if they have compatible code.

[caolan]

So far, I have experimented with persisting reducer output for subtrees alongside the tree node data. However, this requires the map/reduce output to be calculated on every write - since a failure to persist the data at that point would mean any later
attempt to perform map/reduce on that node would mean fetching the relevant (potentially remote) blocks every time.

Instead, I think we should persist the output of map/reduce calculations separate to the tree nodes. Perhaps adding a new top-level property to each batch that contains any recalculated map/reduce values and the nodes they apply to.

This solves a few issues:

1. map/reduce can be evaluated lazily when the output is requested instead of eagerly on each write
2. no need to fetch remote nodes every time for any map/reduce output that did not exist in the remote tree because it can be 'layered' on top of remote nodes in a local batch
3. by naming each map/reduce and changing names when the code changes (requires careful use by consumers of the library) and calculating and persisting output only when demanded, old versions of map/reduce views will naturally be weeded out of new blocks once their output is no longer demanded - otherwise we'd need some kind of register of map/reduce views to remove them from.
4. avoids the possible write amplification of adding map/reduce output to every node when nodes change frequently but map/reduce output is required only rarely (e.g. full text search?). This design allows batching of the map/reduce calculations and persistence.

In addition to the persisted (materialized?) map/reduce views, it might also make sense to provide an API for 'temporary' views that are never persisted. Perhaps the persisting of view output could be an additional call so a single reducer could be used in either way.