Pass file/offset information into mapper

[indygreg]

I found myself needing to perform data dedeplication for the update hotfix data. (Yes, I know incremental upload works better with map reduce.)

My ideal deduplication mechanism is:

1. Collect the upload date of all records with the same ID
2. Throw away all but the most recent record

i.e. last write wins

It is difficult to do this in telemetry-server today if N>1 mappers are involved because the mapper receives no metadata about upload time. Call this a deficiency in how the hotfix data stream is constructed if you want. You can do this with N=1 mappers, but it is absurdly slow (I have multiple cores and I want to use them, dammit). You can write out the original records in map() and have the reducer produce essentially new streams from the filtered output. But that involves tons of extra CPU and I/O. Why should I rewrite a multi-gigabyte data set where the duplication rate is low?

I propose adding the source file/offset information into map(). In my dedupe job, I can write the record ID and file/offset information. A reducer can then find IDs with multiple records and produce an output listing either the "good" or "bad" sets of file/offsets. I can then load this file into another MR job and filter incoming records against it. You pay a penalty for hash lookup on each record, but that should be fast if set is used.

I've already hacked up telemetry-server to pass this extra information to map(). But it breaks the API of map(). Next step is likely to hook up inspect.getargspec() to see if the callee supports the new arguments and pass them if it does. But I wanted to get feedback from people before I fully implement this, as the changes are probably a bit controversial.

[mreid-moz]

Deduplication is a generally useful thing to be able to do, so it would be nice if it could be baked in to the system. This problem is not limited to hotfix data either - it's a known problem with "idle daily" Telemetry submissions as well.

One thing I'll point out - the mappers do get at least coarse-grained metadata on upload time - the "submission date" is one of the dimensions passed in to the map() function.

Another thing is that I've got a few ideas about how to implement deduplication in general, outlined in this document:
https://docs.google.com/a/mozilla.com/document/d/1xfLqmE-op26wMjmvPVRkkpOARnTW_MQPJnZQSrWHALg/edit?pli=1#

Your file+offset approach is similar to the "Parallel DocID files" approach in this document (AIUI), but would generate these files in an initial pass, then use them in a second pass.

I personally lean towards option 1 in the above document, where the master reads records and distributes them to workers after dupes have been discarded. That being said, I would be happy with any approach that could be used to dedupe the data without a lot of hassle to the user, and without an excessive performance penalty.