Method for deduping reports

[tomwilkie]

With #13, the possibility of an app connecting to a probe multiple times has been introduced. This will allow an app to receive the same report more than once, and potentially double count. We need to disallow this.

Options:

• Make report merge fully idempotent ie r1.merge(r1) == r1 and so on
• Make probes only accept one connection per app
• Include a random unique id in each report, and dedupe on the app

I like (1), as it has nice properties for the future; but it is also the hardest.

[peterbourgon]

I like (1), too, but I can't think of a way to do it that isn't infeasibly inefficient, or explodes the complexity of managing (merging) reports. The other idea is having apps do discovery + leader election + request forwarding.

[tomwilkie]

I think one might be able to make it a relatively efficient operation, but I'm worries about an explosion in space. It basically boils down to idempotent counters.

Simple idea: Consider keeping the counter as a list of increments (an increment being an id and a value); you then keep a running summary and a bloom filter of ids. You can add to the summary count if you get a miss on the bloom filter; if you get a hit, you must re-count. I think thats close to O(1) probabilistic update cost, but O(N) size.

[tomwilkie]

Note this is effectively the same as (1), except one is done on the entire report, and assumes reports are only merged once.

[tomwilkie]

Whats more, make the running summary lazy; only calculate it on a read of the counter.

[tomwilkie]

Short-term we'll only accept one connection per app, based on source ip.

[peterbourgon]

Closed by #56