2

I want to generate tickets for an event. I need to generate a lot of them and I decided to have the ticket number as UUIDs. The question is how to generate a big list of UUIDs and it to be different.

I know the easy way to just check every new UUID generated in the already existing list, but this is not very performance friendly. :)

I am using NodeJS with UUID v4.

Thank you!

Dimitrie David
  • 65
  • 1
  • 1
  • 5
  • 1
    Your concern about duplicates is unfounded: https://stackoverflow.com/questions/1155008/how-unique-is-uuid – Chris White May 03 '19 at 21:36
  • Did you consider whether auto-incremented row numbers or sequentially assigned numbers would be more appropriate as ticket IDs than unique random numbers? – Peter O. May 04 '19 at 04:36
  • "auto-incremented row numbers or sequentially assigned numbers" are not more appropriate because this code will be under a QR code on the ticket. – Dimitrie David May 05 '19 at 12:07
  • On the contrary: it's not obvious without scanning the QR Code whether a random number, a sequentially-assigned number, or some other unique number is involved (especially because two-dimensional bar codes such as QR Code generally employ an error correction mechanism of some kind). Any of these kinds of numbers will eventually have to be assigned to a database record of some kind. – Peter O. May 05 '19 at 22:06
  • But if your goal is to create "unpredictable" numbers and your application can tolerate the risk, albeit extremely negligible, of generating a duplicate 124-bit "random" number, then you can generate a version-4 UUID with the help of a cryptographic RNG (which node.js has; check the documentation). However, if the number of ticket IDs you will be generating will be very small (on the order of a thousand, perhaps), then there is no disadvantage to checking the ticket numbers for uniqueness. See also [my article on this matter](https://peteroupc.github.io/random.html#Unique_Random_Numbers). – Peter O. May 05 '19 at 22:09
  • @PeterO. you are just wrong in your article - for quite a few generators (LCG, PCG etc) for a full period (2^64 for 64bit one, 2^128 for 128bit one) there is no collisions, none, all 2^128 calls output unique number. – Severin Pappadeux May 05 '19 at 22:39

3 Answers3

1

You can create an empty object and every time you generate a UUID, you add an attribute to that object where the key is the generated UUID. When you will generate another UUID, you just have to check if the object attribute is undefined or not to see if it's already used.

const uuids = [];
let uuidUsed = {};
const size = 10;
for (let i = 0; i < size; i++) {
    let uuid = uuidv4();
    while (uuidUsed[uuid] !== undefined) {
        uuid = uuidv4();
    }
    uuidUsed[uuid] = true;
}
Kevin Pastor
  • 761
  • 3
  • 18
  • And how is this better than simply checking for a UUID in a list? – Dimitrie David May 03 '19 at 21:23
  • @DimitrieDavid Doing it this way, you're are kind of using a hash map and this implies that you won't have to check for every element in the list to see if it matches the generated UUID. It reduces the number of element to check to 1 instead of maybe all the list. – Kevin Pastor May 05 '19 at 03:47
  • @KevinPastor you recognize, that typical 64bit hash is not very suitable to hold random 128bit numbers, right? – Severin Pappadeux May 05 '19 at 22:13
1

You could use home-grown UUID function, which is guaranteed to be unique pseudo-random integer in the range [0...2128). Below is one based on Linear Contguential Generator. Constants are taken from here or here. You only need to keep previous number/UUID at hands to generate next one, no need to check because it will be repeated only after full period of 2128.

Code relies on BigInt, tested with node v12

const a = 199967246047888932297834045878657099405n; // should satisfy a % 8n = 5n
const c = 1n;                                       // should be odd
const m = (1n << 128n);
const mask = m - 1n;

function LCG128(state) {
    return (BigInt(state) * a + c) & mask; // same as % m
}

q = 7654321n; // seed

q = LCG128(q);
q.toString(16); // first UUID

q = LCG128(q);
q.toString(16); // second UUID

q = LCG128(q);
q.toString(16); // third UUID

UPDATE

Just to be a more philosophical on the issue at hands:

  1. You could consider UUID4 to be black box and trust it - this is what @ChrisWhite proposed
  2. You could consider UUID4 to be black box and distrust it - that is whatyou proposed to check in the list or answer by @KevinPastor
  3. Make your own transparent box which produces numbers in the proper range and be unique - that is my proposal

Beauty of LCG approach is that, given good multiplier and carry, it uniquely and reversable maps range [0...2128) into itself (it could do that for 64bit numbers, with different a, c, or 32bit numbers and so on and so forth). You could even use counter as input starting with 0 up to 2128-1 and it will produce non-repeatable numbers in the same range filling whole [0...2128). So you know that if you either chain it with previous uuid, or use counter, there is 0 chances of collision.

Severin Pappadeux
  • 18,636
  • 3
  • 38
  • 64
0

here’s a list of 446,538 IPs formatted in the following way: | id | date | name | uuid | ip |

https://minerlock.com/lock/F50f4b8d8e27e

god
  • 1
  • 1