[GODRIVER-2361] Investigate using "x/exp/rand" or "google/uuid" packages to improve UUID generation Created: 30/Mar/22  Updated: 28/Oct/23  Resolved: 23/May/22

Status: Closed
Project: Go Driver
Component/s: None
Affects Version/s: None
Fix Version/s: 1.10.0, 1.10.0-beta1

Type: Improvement Priority: Unknown
Reporter: Matt Dale Assignee: Qingyang Hu
Resolution: Fixed Votes: 0
Labels: neweng, techdebt
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
is related to GODRIVER-2349 Prevent session ID reuse due to lower... Closed
is related to GODRIVER-2223 Use "math/rand" instead of "crypto/ra... Closed

 Description   

While investigating GODRIVER-2349, we discovered that the Go "math/rand" package Seed functions drop half of the 64 bits of entropy provided (see code here). There is also an open Go issue requesting more documentation on the behaviors and algorithms in the "math/rand" package (see this comment specifically asking about truncating the seed value). There is an open Go proposal to replace the pseudo-random number algorithms used in the "math/rand" package, either in a Go 1.x release or in Go 2.0. In both places, Rob Pike suggests using the golang.org/x/exp/rand package to replace "math/rand", with the caveat that there may be performance regression until the compiler supports using per-platform 64-bit multiply and add instructions, which it now does.

Additionally, the google/uuid package supports pooling random values for generating random UUIDv4 values, which may mitigate the performance impact of using "crypto/rand". We should consider using that dependency to replace the "uuid" package.

tldr; We should investigate if using the golang.org/x/exp/rand or github.com/google/uuid packages would make a meaningful improvement, either in simplicity of code or performance. If so, we should update the session ID UUID generator to use the best package.

Definition of done:

  • Prototype using "x/exp/rand" and "google/uuid" packages to see if they simplify the pseudo-random number generator use cases in the driver.
  • Benchmark UUID generation with "crypto/rand", "math/rand", "x/exp/rand", and using "google/uuid" (on macOS and on Linux) to see if there is a meaningful improvement in any case.
  • If there is a better approach, update the Go driver UUID generator to use "x/exp/rand", "google/uuid", or revert to using "crypto/rand".


 Comments   
Comment by Githook User [ 23/May/22 ]

Author:

{'name': 'Qingyang Hu', 'email': '103950869+qingyang-hu@users.noreply.github.com', 'username': 'qingyang-hu'}

Message: GODRIVER-2361 Refactor pseudo-random number and UUID generation with "golang.org/x/exp/rand" (#945)
Branch: master
https://github.com/mongodb/mongo-go-driver/commit/ef8ad53b17d04227ae5c835b1bab1cfbac818363

Comment by David Golden [ 09/May/22 ]

I see that mt19937 is unfortunately GPL3, but perhaps there are other MT libraries with more permissive licenses.  E.g. here's one: https://github.com/goark/mt with an MIT license.

As I suggested earlier, I think a mix of a static, per-process crypto portion plus per-UUID random bits from a (crypto-seeded) MT PRNG for the remaining bits is going to give the best safety/performance tradeoff.

Comment by David Golden [ 31/Mar/22 ]

For non-crypto PRNG, I suggest also benchmarking a Mersenne Twister PRNG like https://pkg.go.dev/github.com/seehuhn/mt19937

I'd also add that I'd strongly prefer strong uniqueness over performance unless there is some compelling reason why UUID generation is a hotspot in the code. In that regard, I'd look to develop a real-world benchmark that exercises UUID generation (inserting into lots of explicit sessions?) and see how much difference the UUID generator makes in that context.

As one final thought, you could consider applying the UUID RFC recommendation in section 4.5 and generate 47-bits from a CSPRNG once per process and use it for all UUIDs (with the rest of the bits filled in with a PRNG as you do today). This might balance uniqueness with generation speed.

Generated at Thu Feb 08 08:38:24 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.