Replace Math.random to prevent duplicate event IDs

[christoph-buente]

According to the definition of a V4 UUID, event_id is supposed to be unique for every event. Unfortunately we see the same event_id more than once in our collected data.

Our example data set has 13,406,731 events from which 13,235,475 have unique event_ids. This means that there are about 1.3% events that have duplicated event_id. These events may come in completely different times and from different ip's. As an example, there are 15 different events with event_id = "f2d4f27d-077a-4086-8cce-5789b10fbfda". See the graphics below.

We even have a larger data set with more recent JS tracker versions (2.5.x and 2.6.x), and the duplicate ratio is even worse ~= 1.8%

[alexanderdean]

Are you running the event fingerprint enrichment? Could you reshare the above table with the event fingerprint output as well? Trying to understand what type of duplicates these are.

[christoph-buente]

For this dataset, which is a bit older, we did not have that enrichment enabled. (If it even was available back then.) I'll check for the current SP stack, if we have it running.

But hashing the whole event does not make a difference. If time, IP address and user agent are different. It will most definitively result in a different hash!

[alexanderdean]

Thanks @christoph-buente !

[christoph-buente]

Looking at the user agent i came to the suspicion that the actual implementation of the uuid algorithm falls back to Math.random() in certain browsers. Can this be confirmed? That would be a bug in the underlying uuid npm module, right?

[bogaert]

Hi @christoph-buente. This is an issue we have written about before: http://discourse.snowplowanalytics.com/t/de-deduplicating-events-in-hadoop-and-redshift-tutorial/248 (in case the solutions outlined there are useful).

[christoph-buente]

@bogaert thx Chris, i read that article. But i hoped there is a chance to fix that issue instead of working around it later down the data pipeline.

[bogaert]

@christoph-buente That makes sense. We'll look into it (cc @jbeemster).

[christoph-buente]

Bump 😄

[bogaert]

Hi @christoph-buente. It was good meeting in Berlin! This is something we'll keep investigating, but in the meantime we're also working on an improved deduplication step in the pipeline: https://github.com/snowplow/snowplow/issues?q=is%3Aopen+is%3Aissue+milestone%3A%22R8x+%5BHAD%5D+Synthetic+dedupe%22

[alexanderdean]

See snowplow/snowplow#2967

[alexanderdean]

From @falschparker82:

Hi Snowplowers,

we've got heavy problems here due to some bots (especially Googlebot, googleweblight and others) apparently using a broken version of Math.random(), leading to duplicated event_ids. This gets especially annoying with the resulting huge cartesian joins resulting from significant context use.

I could track down the problem down into the uuid library of the implementation that the Javascript collector uses: https://github.com/kelektiv/node-uuid/blob/master/lib/rng-browser.js#L17 - which happens to fall eventually back down to Math.random() if no better randomness sources are available.

Unfortunately, the implementation of Math.random() is left to the JS interpreter, which is broken on several systems - sources:

http://stackoverflow.com/a/24224089/1281376
https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d#.keeelkt8v

I'd like to propose the following solution for this problem:

1. Replace Math.random() with a seedable Mersenne twister: https://github.com/pigulla/mersennetwister (probably needs upstream patching of npm uuid package). While this is not suitable for cryptographic uses, all that's needed is good entropy here to prevent event ID duplication. Also, the cycle length of >2^19000 far surpasses the capacity of a UUIDv4 (2^128).

1a) Make it possible to seed the RNG by invoking sp.js with an additional parameter &rnd_seed=a4b120f48... (if the page isn't cached or served via CDN, this should be possible rather easily with templating from multiple languages) - which then gets inserted by a seed vector into the twister.

1b) Alternatively - or as a fallback to 1a) - generate the seed vector from the following entropy sources:

• Hash of URL value
• getHour(),getMinutes(),getSeconds(),getMilliseconds()
• Additionally generated floating point entropy: https://github.com/keybase/more-entropy
• Difference of Snowplow cookie date to current time
• Injecting Math.random() at least can't hurt

Thoughts?

Right now I've got a little too much on my plate, so feel free to grab it - but if we happen to do ourselves eventually it we'd love to upstream in case you're interested.