uuid v1 are not unique at all #43
Comments
|
Hmm, that's serious. I will investigate. based on your findings, it seems its not taking into account milliseconds or 100 nanosecond increments for things happening in the same millisecond. Theoretically this should support 10 million unique hashes a second with no collision. Thanks for bringing it to my attention. I will definitely work on fixing this today if I can, or at least figure out how this is happening. I think this is a common issues for v1 its why v4 is commonly the preferred UUID version. Also C#/Microsoft GUIDs are actually a little different. I forget which came first, but the RFC4122 UUID and the MS GUIDs aren't directly compatible even if very similar. |
|
So, I can't seem to reproduce it. I created the following test: test('Generate lots of codes to see if we get v1 collisions.', () {
var uuids = Set();
var collisions = 0;
for (var i = 0; i < 10000000; i++) {
var code = uuid.v1();
if (uuids.contains(code)) {
collisions++;
print("Collision of code: $code");
} else {
uuids.add(code);
}
}
expect(collisions, equals(0));
expect(uuids.length, equals(10000000));
});Generated 10,000,000 codes and no collisions. Took only a few seconds for it to run through fully and passed. I then noticed you use Can I get more info on where this is running? Flutter, Browser, Server-side? Might be something mobile or browser related if so. I will create more tests to figure out what might be happening there if so. |
|
Nothing special. An app with Flutter 1.10.17 for Android and 1.9.xxx for iOS. My pubspec.yaml: I always use I just noticed that because my actual database (Azure Tables) requires a pair primary key (so I'm using this Id and the UserId). No problems (even so, it will replace the data on collision without excceptions). When I tried to copy the database to a MSSQL server, I've noticed the conflicting Ids for different users (forcing me to use a composite key). I can't tell why =\ It just happened. I have 699 collisions. Look at this case:
They are two different persons in two different devices. Let's suppose those 2 users in 2 different devices did something at exactly the same millisecond. It should not generate the same id, because they are in different machines. UUID v1 requires the mac address to prevent that. You can use the deviceId for this (it is a string in Android and a Guid in iOS - it represents that app on that device), otherwise, you will get conflicts when there is a lot of concurrent users (I have 2000 concurrent users throught out the day, and about 32000 in some specific times (mostly 20:00, 20:30)). |
|
BTW, this is what I'm using in my new app's version. It takes in consideration the device id and the current authenticated user (the chances of conflict are quite reduced here). If you take out the userId part and do a better job turning the android deviceId in a hexa number, I think it will be random enough to replace the macaddress required in v1): static final _onlyHexPattern = RegExp("[^0-9a-f]", caseSensitive: false);
static final _baseDate = DateTime.utc(2020, 1, 1);
static int _seq = 0;
static String _prefix;
static Future<String> generateNewId() async {
if (_prefix == null) {
final deviceId = (await Device.instance).deviceId.replaceAll(_onlyHexPattern, "").toLowerCase().padLeft(10, "0");
final currentUser = await FirebaseAuth.instance.currentUser();
final userId = currentUser == null ? "" : currentUser.uid.replaceAll(_onlyHexPattern, "").toLowerCase().padLeft(8, "0").substring(0, 8);
_prefix = userId + "-" + deviceId.substring(0, 4) + "-" + deviceId.substring(4, 8) + "-" + deviceId.substring(8, 10);
}
final now = DateTime.now().toUtc();
final timestamp = now.difference(_baseDate).inMilliseconds.toRadixString(16).padLeft(12, "0");
final seq = _seq.toRadixString(16).padLeft(2, "0");
_seq = (_seq + 1) % 256;
return _prefix + seq + "-" + timestamp.substring(0, 12);
} |
|
Its a shame the timestamp doesnt go lower than seconds. I can't recreate the codes without the milliseconds and 100 nanosecond increments. But you are correct that even the way you are doing it, should not cause collisions, especially at so low numbers. I will setup a Flutter project and do some testing. As for MAC address. SInce I need to support so many platforms, I used the alternative method of generating an equivalent number where I just generate a 48 bit seed using random number generator. _seedBytes = (options['v1rng'] != null)
? Function.apply(options['v1rng'], v1PositionalArgs, v1NamedArgs)
: UuidUtil.mathRNG();
// Per 4.5, create a 48-bit node id (47 random bits + multicast bit = 1)
_nodeId = [_seedBytes[0] | 0x01, _seedBytes[1], _seedBytes[2], _seedBytes[3], _seedBytes[4], _seedBytes[5]];
// Per 4.2.2, randomize (14 bit) clockseq
_clockSeq = (_seedBytes[6] << 8 | _seedBytes[7]) & 0x3ffff;I never actually use the Mac Address. I just use random numbers. I do it in the constructor, so the seed is consistent if you dont recreate it. But since you recreate the object, it actually is MORE random. So I am not even sure how that is happening. So there is less reason for there to be a collision. Sorry that this is happening. I will do my best to figure this out. I will keep digging to see if I can figure out why this is happening. |
|
Ok, I have been trying on and off for a few weeks, on web, flutter/android, local. I cant hit any collisions. If you want me to keep looking into it, can you create minimal project that exhibits this problem and post it somewhere or send it over to me. Maybe I am just setting something up differently. |
Is not about a project, is about the amout of users. I have more than 2 million downloads, no less than 3000 users using the app at the same time. Eventually, some records on my database were duplicated =\ I'm not using this lib anymore because of those collisions (I'm using a custom made generator based on user's Firebase Id, current date time and a incremental to avoid local collisions). But, it is in development. Can't say I won't incur in the same collisions once is release for millions of users =\ |
|
Ok, I am sorry that I haven't been able to help. I'll close this ticket for now, but if you ever want to try again or something, feel free to reopen or start a new issue. I'll keep this in mind going forward and see if I ever stumble onto something that will exhibit this. |
I have an application with 751,446 users that generated 863,497 database records and there is a lot of conflicts.
Code used to generate the id:
Those 18 clashes generated these records:
Click here to expand
I think the problem is the granularity of the date (notice how those records were generated at the same hour, minute and second (but I really doubt about milliseconds)).
I copied the Guid Comb generator from the C# nHibernate ORM (available here: https://github.com/nhibernate/nhibernate-core/blob/master/src/NHibernate/Id/GuidCombGenerator.cs) with some minor adjustments as not generating the same Id in the exactly same millisecond (while generating in a loop) and taking the device id into account (didn't made any tests to check if it really works with 0 clashes, though):
Click here to expand
The text was updated successfully, but these errors were encountered: