Skip to content

Add a seedable UUIDv4 generator

Thomas Randolph requested to merge symlink-identifier/uuids into master

What does this MR do?

This MR adds a seedable UUIDv4 generator function, which has the signature:

uuids()
uuids(options)

options is an object with the following optional properties:

Option Description
seeds An array of integer or string values to seed the internal PRNG with.
count The number of UUIDs to generate

The return value is:

  • Array[<UUID>]

Why

As we're working toward a solution to #33867 and with an eye forward to uniquely identifying everything, it will help to be able to have a standard, unique ID generator.

UUID is - hands-down - the world's most popular and agreed-upon unique ID format.

Internally, it uses a Mersenne Twister to generate "random" numbers (not cryptographically secure random, but good enough for string IDs). A Mersenne Twister is by far the best (computationally cheap) Pseudo-Random Number Generator that fixes most problems with other PRNGs (and passes most statistical tests for randomness).1

Having this tool available to us will pave the path for more performant applications on the front end.

Screenshots

N/A, all ~backstage

Does this MR meet the acceptance criteria?

Conformity

Availability and Testing

One thing to note: a Mersenne Twister is a number generator. As such, it is not especially fast.
That said, we're talking "able to generate 1,500,000+ numbers per second" "slow", not "it takes 1 second to generate a number" slow.

The internal Mersenne Twister is asked to generate 16 numbers for every UUID requested (this is how many random numbers the UUID library needs to properly generate a value).

Due to this, the generation of one UUID takes around 0.006 milliseconds (6 microseconds).

Raw Node (14.3.0) performance data from inside our test suite
{
    "1m": {
      start: 1060.470398,
      end: 6836.521165,
      total: 5776.050767000001,
      perUuid: 0.005776050767,
      perNumber: 0.0003610031729375
    },
    "100k": {
      start: 1122.07602,
      end: 1765.2996640000001,
      total: 643.2236440000001,
      perUuid: 0.006432236440000002,
      perNumber: 0.0004020147775000001
    },
    "10k": {
      start: 1000.047282,
      end: 1058.441528,
      total: 58.39424600000007,
      perUuid: 0.0058394246000000065,
      perNumber: 0.0003649640375000004
    },
    "1k": {
      start: 971.93944,
      end: 978.894084,
      total: 6.95464400000003,
      perUuid: 0.006954644000000031,
      perNumber: 0.0004346652500000019
    }
}
Previous results before some optimizations
  {
      "1m": {
        "start": 1066.507532,
        "end": 11103.974058,
        "total": 10037.466526,
        "uuid": 0.010037466526,
        "number": 0.000627341657875
      },
      "100k": {
        "start": 11104.019287,
        "end": 12143.217934,
        "total": 1039.198647000001,
        "uuid": 0.01039198647000001,
        "number": 0.0006494991543750006
      },
      "10k": {
        "start": 12143.233454,
        "end": 12243.383197,
        "total": 100.14974299999994,
        "uuid": 0.010014974299999995,
        "number": 0.0006259358937499997
      }
  }
Number of UUIDs Requested Time Time per UUID Time per Random Number
1,000,000 5776ms 5.78μs 361ns
100,000 643ms 6.43μs 402ns
10,000 58ms 5.84μs 365ns
1,000 7ms 6.95μs 435ns
Previous performance before optimizations
Number of UUIDs Requested Time Time per UUID Time per Random Number
1,000,000 10037ms 10.037μs 627ns
100,000 1039ms 10.392μs 649ns
10,000 100ms 10.015μs 626ns
Removed internal `mersenne_twister`
Number of UUIDs Requested Time Time per UUID Time per Random Number
1,000,000 4983ms 4.983μs 311ns
100,000 493ms 4.93μs 308ns
10,000 58ms 5.8μs 363ns

We can expect reasonable performance when generating <=50,000 UUIDs, which should be sufficient for the vast majority of use-cases. Future improvements could target the Mersenne Twister or UUID generator for optimizations.

Security

If this MR contains changes to processing or storing of credentials or tokens, authorization and authentication methods and other items described in the security review guidelines:

  • [-] Label as security and @ mention @gitlab-com/gl-security/appsec
  • [-] The MR includes necessary changes to maintain consistency between UI, API, email, or other methods
  • [-] Security reports checked/validated by a reviewer from the AppSec team
Edited by Thomas Randolph

Merge request reports

Loading